Number Systems, Weighted Codes & Error-Correction Codes

1. General Radix Positional Number Representation

In digital electronics, numbers are represented in a positional numeral system characterized by a base or radix ($r$). Any real number $N$ possessing an integer part of $n$ digits and a fractional part of $m$ digits is expanded mathematically as a polynomial power series:

where $d_i \in \{0, 1, \dots, r - 1\}$ represents the digit coefficient at weight $r^i$, and the period separating $d_0$ and $d_{-1}$ is the radix point. The four primary radices utilized in digital computation are:

• Binary ($r = 2$): Digits (bits) $d_i \in \{0, 1\}$. Direct physical mapping to transistor cut-off and saturation states.
• Octal ($r = 8 = 2^3$): Digits $d_i \in \{0, 1, 2, 3, 4, 5, 6, 7\}$. Exactly three binary bits map to one octal digit.
• Decimal ($r = 10$): Digits $d_i \in \{0, 1, \dots, 9\}$. Standard human arithmetic convention.
• Hexadecimal ($r = 16 = 2^4$): Digits $d_i \in \{0, 1, \dots, 9, \text{A}(10), \text{B}(11), \text{C}(12), \text{D}(13), \text{E}(14), \text{F}(15)\}$. Exactly four binary bits (one nibble) map to one hexadecimal digit. Widely used for byte addresses and machine opcode representations.

2. Base Conversion Algorithms

1. Radix-$r$ to Decimal: Directly evaluate the polynomial expansion $\sum d_i r^i$ using decimal arithmetic. For example:
   $$(11010.11)_2 = 1\cdot 2^4 + 1\cdot 2^3 + 0\cdot 2^2 + 1\cdot 2^1 + 0\cdot 2^0 + 1\cdot 2^{-1} + 1\cdot 2^{-2} = 16 + 8 + 2 + 0.5 + 0.25 = (26.75)_{10}$$
2. Decimal to Radix-$r$ (Successive Division / Multiplication):
   • Integer Part: Repeatedly divide the decimal integer by radix $r$. The remainder generated at division step $k$ forms digit $d_k$, terminating when the quotient reaches zero. The first remainder is the Least Significant Digit (LSD); the final remainder is the Most Significant Digit (MSD).
   • Fractional Part: Repeatedly multiply the fractional remainder by radix $r$. The integer carry extracted at each step forms digit $d_{-k}$, proceeding until the product terminates or reaches the desired precision. The first extracted integer is the most significant fractional digit $d_{-1}$.
3. Binary $\leftrightarrow$ Octal $\leftrightarrow$ Hexadecimal Grouping: Because $8 = 2^3$ and $16 = 2^4$, conversion between binary, octal, and hexadecimal requires zero polynomial arithmetic. Simply partition the binary string into groups of 3 bits (octal) or 4 bits (hexadecimal) radiating outward from the radix point, padding with leading and trailing zeros as necessary.

1. Binary Coded Decimal (BCD) & Weighted 4-Bit Codes

To interface digital hardware with decimal displays without full binary polynomial division, decimal digits $0 - 9$ are encoded individually using 4-bit binary codewords. In a weighted code, each bit position $j$ is assigned an explicit numerical weight $w_j$, such that the decimal value is:

• 8421 BCD (Natural BCD): The standard weights are $w_3 = 8, w_2 = 4, w_1 = 2, w_0 = 1$. The 10 decimal digits map directly to binary patterns $0000_2$ through $1001_2$. The remaining six 4-bit patterns ($1010_2$ to $1111_2$, values 10 to 15) are forbidden / invalid states that never occur in legitimate BCD words.
• Self-Complementing Codes (2421 & Excess-3): A code is self-complementing if the 9's complement of any decimal digit $D$ (i.e., $9 - D$) is obtained simply by taking the 1's complement (inverting all bits $b_j \to \bar{b}_j$) of its codeword.
  • 2421 Code (Aikens Code): Weights $(2, 4, 2, 1)$ where $\sum w_j = 9$. Digit $2$ is $0010_2$, and its 9's complement $7$ is $1101_2 = \overline{0010}_2$.
  • Excess-3 (XS-3) Code: An unweighted self-complementing code derived by adding $3_{10} = 0011_2$ to each natural 8421 BCD digit. For digit $0$: $0011_2$; for digit $9$: $1100_2 = \overline{0011}_2$. Excess-3 simplifies decimal subtraction in early mechanical and electronic ALUs.
• Negative Weight Codes ($84\text{-}2\text{-}1$): Possesses weights $w_3 = 8, w_2 = 4, w_1 = -2, w_0 = -1$. For example, decimal $5$ is encoded as $1\cdot 8 + 0\cdot 4 + 1\cdot(-2) + 1\cdot(-1) = 8 - 3 = 5$, represented by $1011_2$.

2. The Unit-Distance Reflected Gray Code

Frank Gray (1953) developed the reflected binary Gray code, an unweighted cyclic code exhibiting the critical property of unit distance: between any two adjacent decimal numbers $k$ and $k+1$, exactly one bit changes state.

In electromechanical shaft optical encoders, converting angular position using natural binary can produce disastrous transient read errors. If a shaft transitions from $7$ ($0111_2$) to $8$ ($1000_2$), all four bits must flip simultaneously. Because physical photodetectors cannot switch with infinitesimal synchronicity, intermediate false states (e.g., $1111_2 = 15$) can be latched momentarily. The Gray code eliminates this hazard entirely.

Binary to Gray Conversion Algorithm: Given binary word $B = b_n b_{n-1} \dots b_0$ and Gray codeword $G = g_n g_{n-1} \dots g_0$:

Gray to Binary Conversion Algorithm:

1. The ASCII Alphanumeric Encoding Standard

Digital computer systems process non-numerical information (text characters, punctuation, control commands) through standardized alphanumeric binary lookup codes. The American Standard Code for Information Interchange (ASCII) is a 7-bit encoding scheme capable of defining $2^7 = 128$ distinct characters:

• 32 Control Characters ($00_{16} - 1\text{F}_{16}$): Non-printable device instructions (NUL: $00_{16}$, SOH: $01_{16}$, STX: $02_{16}$, ACK: $06_{16}$, BEL: $07_{16}$, BS: $08_{16}$, LF: $0\text{A}_{16}$, CR: $0\text{D}_{16}$, ESC: $1\text{B}_{16}$).
• 96 Printable Characters ($20_{16} - 7\text{E}_{16}$): Comprising space ($20_{16}$), decimal digits '0'-'9' ($30_{16} - 39_{16}$), uppercase letters 'A'-'Z' ($41_{16} - 5\text{A}_{16}$), lowercase letters 'a'-'z' ($61_{16} - 7\text{A}_{16}$), and mathematical/punctuation symbols. Note that toggling bit 5 ($20_{16}$) converts between uppercase and lowercase letters (e.g., 'A' is $01000001_2$, 'a' is $01100001_2$).
• Extended 8-Bit ASCII ($00_{16} - \text{FF}_{16}$): Adds 128 characters ($80_{16} - \text{FF}_{16}$) for accented European letters, box-drawing graphics, and Greek scientific symbols.

2. Parity Bit Generation & Single-Bit Error Detection

During data transmission across communication channels or memory buses, electrical noise, thermal fluctuations, or cosmic radiation can flip a binary bit ($0 \to 1$ or $1 \to 0$). The simplest hardware mechanism for error detection is the appendance of a parity bit ($P$):

• Even Parity: The parity bit $P$ is chosen so that the total count of 1s in the transmitted codeword (data bits plus parity bit) is strictly even. For an $n$-bit data vector $D = (d_{n-1}, \dots, d_0)$, the even parity bit is synthesized via cascaded XOR gates:
  $$P_{\text{even}} = d_{n-1} \oplus d_{n-2} \oplus \dots \oplus d_1 \oplus d_0$$
• Odd Parity: The parity bit $P$ is chosen so that the total count of 1s is strictly odd:
  $$P_{\text{odd}} = \overline{d_{n-1} \oplus d_{n-2} \oplus \dots \oplus d_0} = \overline{P_{\text{even}}}$$

At the receiver, an identical XOR parity checker computes the parity of the received packet. If a single bit flips, the parity check fails, triggering an error interrupt. However, single-bit parity cannot detect double-bit errors (which restore parity count) and provides zero information regarding which specific bit flipped, rendering error correction impossible.

1. Richard Hamming's Geometric Code Distance Theory (1950)

To enable automated in-flight error correction in telecommunications and memory ECC (Error-Correcting Code), Richard Hamming introduced the concept of Hamming Distance ($d_{\text{min}}$), defined as the minimum number of bit positions in which any two valid codewords differ.

For a code to detect up to $t$ simultaneous bit errors and correct up to $c$ bit errors, the minimum Hamming distance must satisfy:

• To detect $t = 1$ single error: $d_{\text{min}} \ge 1 + 1 = 2$ (simple parity bit).
• To correct $c = 1$ single error: $d_{\text{min}} \ge 2(1) + 1 = 3$ (standard Hamming code).
• To correct single errors and detect double errors (SEC-DED): $d_{\text{min}} \ge 2(1) + 1 + 1 = 4$ (Hamming code with overall parity bit).

2. Construction of the Hamming (7,4) Single-Error-Correcting Code

Consider transmitting $m = 4$ data bits ($D_7, D_6, D_5, D_3$). To isolate the location of any single-bit error among the $n = m + k$ bits transmitted, or verify error-free transmission, the $k$ parity check bits must represent at least $n + 1$ distinct states:

For $m = 4$, setting $k = 3$ satisfies $2^3 = 8 \ge 4 + 3 + 1 = 8$. Thus, $n = 7$ total bits are transmitted: 4 data bits and 3 parity bits.

Parity Bit Placement: Parity bits $P_1, P_2, P_4$ are assigned to bit positions that are exact powers of 2 ($1, 2, 4$). The remaining positions ($3, 5, 6, 7$) hold the data bits:

Each parity bit enforces even parity over all bit positions whose binary index contains a 1 in that parity bit's respective binary position:

3. Syndrome Decoding and Hardware Error Correction

At the receiver, the 7 received bits ($r_7, r_6, r_5, r_4, r_3, r_2, r_1$) are processed by three parity-check XOR trees to calculate the 3-bit Syndrome Vector $S = (S_4 S_2 S_1)$:

• If $S = 000_2$: No error occurred; data is valid.
• If $S = S_4 S_2 S_1 \neq 0$: The binary integer value of $S$ points directly to the exact erroneous bit position ($1$ through $7$). The hardware simply inverts that specific bit ($r_S \leftarrow \overline{r_S}$) using an XOR gate driven by a 3-to-8 decoder, achieving automated instantaneous hardware error correction.

1. Combinational Code Conversion Architecture

A digital code converter is an $n$-input, $m$-output combinational logic circuit that accepts input words represented in code $\mathcal{A}$ and produces equivalent codewords in code $\mathcal{B}$. The synthesis procedure follows systematic Boolean optimization:

1. Construct a comprehensive truth table mapping each valid input codeword to its desired output codeword.
2. Treat unused or invalid input combinations as Don't Care states ($\times$) to maximize logic gate reduction.
3. Derive minimized Sum-of-Products (SOP) expressions for each output bit using Karnaugh maps or Quine-McCluskey tabulation.

2. Binary-to-Gray and Gray-to-Binary Hardware Circuits

From the conversion equations $g_i = b_{i+1} \oplus b_i$, a 4-bit Binary-to-Gray converter requires only three two-input XOR gates:

Similarly, the Gray-to-Binary converter $b_i = b_{i+1} \oplus g_i$ utilizes three XOR gates in a ripple-feedback cascade:

3. BCD-to-Excess-3 Hardware Synthesis

To convert an 8421 BCD digit $(B_3, B_2, B_1, B_0)$ to Excess-3 $(E_3, E_2, E_1, E_0)$, the circuit adds $0011_2$. For input minterms $m_{10}$ through $m_{15}$, the outputs are defined as Don't Cares ($\times$). Minimizing via 4-variable K-maps yields:

This compact logic network requires only four standard logic gates, illustrating the power of exploiting Don't Care conditions.