Number Systems and Codes

Digital circuits work with two voltage levels, so they store numbers in binary. People prefer decimal, and programmers often use octal and hexadecimal as short forms of binary. This lesson covers moving between them.

Positional notation

In base (radix) r, the digits are 0 to r − 1 and each position is worth a power of r:

(d_n−1 … d₁ d₀ . d₋₁ d₋₂ …)_r = Σ dᵢ × rⁱ

For example (1011.101)₂ = 8 + 0 + 2 + 1 + 0.5 + 0 + 0.125 = (11.625)₁₀, and (3A7)₁₆ = 3 × 256 + 10 × 16 + 7 = (935)₁₀.

An n-digit base-r number can represent rⁿ values, from 0 to rⁿ − 1.

Converting from decimal

• Integer part: divide by r repeatedly; the remainders, read from last to first, are the digits.
• Fraction part: multiply by r repeatedly; the integer parts, read from first to last, are the digits. The process may never end (0.1 in decimal is 0.000110011… in binary, repeating), so it is cut off at the precision needed.

DIGITS = "0123456789ABCDEF"

def to_base(value, base, frac_digits=6):
    whole, frac = int(value), value - int(value)
    int_digits = ""
    while True:
        whole, rem = divmod(whole, base)
        int_digits = DIGITS[rem] + int_digits      # remainders, last to first
        if whole == 0:
            break
    frac_part = ""
    while frac and len(frac_part) < frac_digits:
        frac *= base
        frac_part += DIGITS[int(frac)]             # integer parts, first to last
        frac -= int(frac)
    return int_digits + ("." + frac_part if frac_part else "")

for v in [156, 11.625, 0.1, 935]:
    print(f"{v:>7}: binary {to_base(v, 2)}, octal {to_base(v, 8)}, hex {to_base(v, 16)}")

    156: binary 10011100, octal 234, hex 9C
 11.625: binary 1011.101, octal 13.5, hex B.A
    0.1: binary 0.000110, octal 0.063146, hex 0.199999
    935: binary 1110100111, octal 1647, hex 3A7

Binary, octal and hexadecimal

Since 8 = 2³ and 16 = 2⁴, each octal digit is exactly 3 bits and each hex digit exactly 4 bits. Convert by grouping bits from the binary point outwards (padding with zeros at the ends):

• (10011100)₂ → 010 011 100 → (234)₈
• (10011100)₂ → 1001 1100 → (9C)₁₆
• (725)₈ → 111 010 101 → (111010101)₂

To convert between octal and hex, go through binary.

Finding an unknown base

A typical question: if (121)ₓ = (100)₁₀, what is x? Expand: x² + 2x + 1 = 100, so (x + 1)² = 100 and x = 9. Remember that every digit must be smaller than the base.

Binary-coded decimal (BCD)

BCD (8421 code) stores each decimal digit in its own 4 bits: (947)₁₀ = 1001 0100 0111 in BCD. The bit patterns 1010 to 1111 are invalid. BCD is easy to convert to and from decimal (for displays), but wastes space: 4 bits per digit store only 10 of the 16 possible values. When two BCD digits are added and the sum exceeds 9 (or a carry occurs), 6 (0110) is added to correct the result.

Excess-3 code is BCD + 3 (decimal 4 → 0111). It is self-complementing: the 9's complement of a digit is obtained by inverting its bits.

Gray code

In a Gray code, consecutive values differ in exactly one bit. This avoids glitches when a value changes (rotary encoders) and is used to order Karnaugh maps.

• Binary to Gray: keep the leftmost bit; each next Gray bit is the XOR of neighbouring binary bits. In one step: G = B XOR (B >> 1).
• Gray to binary: keep the leftmost bit; each next binary bit is the previous binary bit XOR the current Gray bit.

def to_gray(b):
    return b ^ (b >> 1)

def from_gray(g):
    b = 0
    while g:
        b ^= g
        g >>= 1
    return b

print([format(to_gray(i), "03b") for i in range(8)])
print("13 in Gray:", format(to_gray(13), "04b"))
print("Gray 1011 in binary:", format(from_gray(0b1011), "04b"))

['000', '001', '011', '010', '110', '111', '101', '100']
13 in Gray: 1011
Gray 1011 in binary: 1101

Practice questions

print(format(13 ^ (13 >> 1), "04b"))