Electronics Guide

Binary Number System (Base 2)

The binary number system forms the foundation of all digital electronics because it maps directly to the two-state nature of electronic switches. Binary uses only two digits: 0 and 1, corresponding to low and high voltage levels, off and on states, or the presence and absence of current.

In binary, each position represents a power of 2. Reading from right to left, positions represent 2⁰ = 1, 2¹ = 2, 2² = 4, 2³ = 8, and so on. For example, the binary number 1011 represents:

1 × 2³ + 0 × 2² + 1 × 2¹ + 1 × 2⁰ = 8 + 0 + 2 + 1 = 11 (decimal)

Binary arithmetic follows the same rules as decimal arithmetic but with only two digits. Addition produces a carry when the sum exceeds 1:

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 10 (0 with carry of 1)

Binary fractions work similarly, with positions to the right of the binary point representing 2⁻¹ = 0.5, 2⁻² = 0.25, 2⁻³ = 0.125, and so forth. The binary number 0.101 equals 0.5 + 0.125 = 0.625 in decimal.

Octal Number System (Base 8)

Octal uses digits 0 through 7 and provides a compact representation of binary numbers because each octal digit corresponds exactly to three binary digits. This relationship made octal popular in early computing systems, particularly those with word lengths that were multiples of three bits, such as the 12-bit PDP-8 and the 36-bit IBM 7090 and PDP-10.

Converting between binary and octal is straightforward: group binary digits into sets of three (starting from the radix point and working outward), then convert each group to its octal equivalent. For example, 101110011 splits into 101, 110, and 011, which are the octal digits 5, 6, and 3:

101 110 011₂ = 563₈

While less common in modern systems, octal still appears in Unix file permissions and some legacy applications. The Unix permission mode 755, for instance, sets read, write, and execute permissions for the owner (7 = 111 binary), and read and execute for group and others (5 = 101 binary).

Hexadecimal Number System (Base 16)

Hexadecimal has become the preferred shorthand for binary in modern computing because each hexadecimal digit maps to exactly four binary digits, so an 8-bit byte splits neatly into two hexadecimal digits, one for each nibble (half-byte). Hexadecimal uses digits 0-9 and letters A-F to represent values 0 through 15.

Hexadecimal notation appears throughout electronics: memory addresses, color codes in graphics (FF0000 for red), MAC addresses, and debugging output. A common notation prefixes hexadecimal numbers with "0x" (as in 0x1A3F) or suffixes with "h" (1A3Fh).

Converting an 8-bit byte to hexadecimal produces a two-digit number (00 to FF), while a 16-bit value produces four digits, and a 32-bit value produces eight digits. This compact representation makes hexadecimal invaluable for examining memory contents and machine code.

Conversion Between Number Systems

Converting between number systems is a fundamental skill in digital electronics. Several methods exist, each suited to different situations.

Decimal to Binary: The repeated division method divides the decimal number by 2 repeatedly, recording the remainders. The binary number consists of the remainders read in reverse order. For example, converting 25:

• 25 / 2 = 12 remainder 1
• 12 / 2 = 6 remainder 0
• 6 / 2 = 3 remainder 0
• 3 / 2 = 1 remainder 1
• 1 / 2 = 0 remainder 1

Reading remainders bottom to top: 25 decimal = 11001 binary.

• Binary to Decimal: Multiply each binary digit by its positional weight (power of 2) and sum the results, as shown in the earlier example.
• Binary to Hexadecimal: Group binary digits into sets of four (padding with leading zeros if necessary), then convert each group to its hexadecimal equivalent. For example, 11001 becomes 0001 1001 = 19 hexadecimal.
• Decimal Fractions to Binary: The repeated multiplication method multiplies the fractional part by 2 repeatedly, recording the integer parts. For example, converting 0.625:

• 0.625 × 2 = 1.25, integer part = 1
• 0.25 × 2 = 0.5, integer part = 0
• 0.5 × 2 = 1.0, integer part = 1

Reading integer parts top to bottom: 0.625 decimal = 0.101 binary.

Note that some decimal fractions cannot be represented exactly in binary, leading to rounding errors. A fraction terminates in binary only when its denominator, in lowest terms, is a power of 2. For instance, 0.1 decimal produces the infinitely repeating binary fraction 0.000110011001100…, so any finite binary format can store only an approximation of it.

Sign-Magnitude Representation

Sign-magnitude uses the most significant bit (MSB) as a sign indicator: 0 for positive, 1 for negative. The remaining bits represent the magnitude of the number. For an 8-bit representation, +5 is 00000101 and −5 is 10000101.

While intuitive for humans, sign-magnitude presents problems for hardware implementation. It has two representations for zero (+0 and −0), complicating comparisons. More significantly, arithmetic operations require separate circuits for addition and subtraction because the sign bit must be handled differently from magnitude bits.

Sign-magnitude finds use primarily in floating-point representations and some specialized applications where its simplicity outweighs its arithmetic complexity.

One's Complement

One's complement represents negative numbers by inverting all bits of the positive number. To negate a value, change all 0s to 1s and all 1s to 0s. For 8 bits, +5 (00000101) becomes −5 (11111010).

Addition in one's complement works by adding numbers as unsigned values, then adding any carry-out back to the result (end-around carry). This allows the same hardware to perform both addition and subtraction, since subtracting B from A equals adding the one's complement of B to A.

One's complement still has two representations for zero: 00000000 (+0) and 11111111 (−0). This dual zero and the complexity of end-around carry have led to its replacement by two's complement in most modern systems, though it survives in networking as the arithmetic of the Internet checksum used in IPv4, TCP, and UDP headers.

The range of an n-bit one's complement number is −(2ⁿ⁻¹ − 1) to +(2ⁿ⁻¹ − 1). For 8 bits, this is −127 to +127.

Two's Complement

Two's complement has become the dominant representation for signed integers in digital systems due to its elegant properties that simplify arithmetic hardware. To negate a number, invert all bits and add 1; in other words, the two's complement of a value is its one's complement plus 1. For an n-bit word, this makes the code for −x equal to 2ⁿ − x read as an unsigned number.

For 8 bits: +5 = 00000101, one's complement = 11111010, two's complement (add 1) = 11111011 = −5.

The key advantages of two's complement include:

• Single zero representation: Only 00000000 represents zero, eliminating comparison ambiguity
• Unified addition and subtraction: Addition and subtraction use the same hardware; subtraction is addition of the negated value, and no end-around carry is needed
• Overflow detection: Overflow occurs when the carry into the sign bit differs from the carry out
• Extended range: The range is −2ⁿ⁻¹ to +(2ⁿ⁻¹ − 1), one more negative value than one's complement

For 8 bits, two's complement represents −128 to +127. The most negative value (−128 = 10000000) has no positive counterpart within the same bit width, a characteristic that programmers must consider when negating values.

Reading a two's complement number: if the MSB is 0, interpret directly as positive. If the MSB is 1, the number is negative; negate it (invert and add 1) to find the magnitude. Equivalently, every bit keeps its usual positive weight except the MSB, which carries the weight −2ⁿ⁻¹:

11111011 = −128 + 64 + 32 + 16 + 8 + 0 + 2 + 1 = −5

Sign extension converts a two's complement number to a wider representation by replicating the sign bit. Extending 8-bit −5 (11111011) to 16 bits produces 1111111111111011, preserving the value. This property simplifies operations between values of different widths.

Excess-N (Biased) Representation

Excess-N representation adds a fixed bias to all values, shifting the range so that the encoded minimum value corresponds to all zeros. This representation simplifies comparisons because numeric ordering matches the binary ordering of encoded values.

Common biases include excess-127 (used in IEEE 754 single-precision floating-point exponents) and excess-1023 (double-precision exponents). In excess-127, the value 0 encodes as 01111111 (127 in unsigned binary), while −127 encodes as 00000000 and +128 encodes as 11111111. In an IEEE 754 exponent field those two extreme patterns are reserved for special values, as described below.

Excess-N finds primary use in floating-point exponent fields. Because the biased exponent sits above the fraction in the word, two non-negative floating-point numbers compare in the same order as their bit patterns read as unsigned integers, so a simple integer comparator can order them.

IEEE 754 Standard

The IEEE 754 standard, first published in 1985 and revised in 2008 and 2019, defines the floating-point formats that have become universal in computing. The 1985 edition specified single precision (32 bits), double precision (64 bits), and extended precision formats. The 2008 revision added half precision (binary16: 1 sign bit, 5 exponent bits, 10 fraction bits), quadruple precision (binary128: 1, 15, and 112 bits), and decimal formats. Alongside the formats, the standard defines rounding, special values, and exception handling.

An IEEE 754 number consists of three fields:

• Sign bit (S): 0 for positive, 1 for negative
• Exponent (E): Biased representation of the power of 2
• Fraction (F): The fractional part of the significand

The value of a normal number is:

value = (−1)^S × 1.F × 2^{E − bias}

Here 1.F is the binary number formed by a leading 1, the binary point, and the stored fraction bits, and the bias is 127 for single precision and 1023 for double precision. The "1." before the fraction is implicit (not stored), providing an extra bit of precision. Normalization adjusts the exponent of every normal number so that its significand has exactly one 1 before the binary point; the subnormal numbers described below are the exception.

Single Precision (32-bit)

Single-precision floating-point allocates: 1 sign bit, 8 exponent bits, and 23 fraction bits. The exponent uses excess-127 bias, allowing exponents from −126 to +127 (the stored exponent fields 0 and 255 are reserved for zero, subnormals, infinities, and NaNs).

Key characteristics:

• Approximate decimal precision: about 7 significant digits (24 significant bits, counting the implicit 1)
• Approximate range of normal numbers: 1.2 × 10⁻³⁸ to 3.4 × 10³⁸; subnormals extend down to about 1.4 × 10⁻⁴⁵
• Smallest positive normal number: 2⁻¹²⁶
• Largest finite number: (2 − 2⁻²³) × 2¹²⁷
• Machine epsilon, the gap between 1 and the next larger representable number: 2⁻²³ (approximately 1.19 × 10⁻⁷). The unit roundoff, the largest relative error that round to nearest can introduce, is half of that: 2⁻²⁴, approximately 5.96 × 10⁻⁸.

Example: Converting 12.375 to IEEE 754 single precision:

1. Convert to binary: 12 = 1100 and 0.375 = 0.011, so 12.375 = 1100.011
2. Normalize: 1.100011 × 2³
3. Sign bit: 0 (positive)
4. Exponent: 3 + 127 = 130 = 10000010
5. Fraction: 10001100000000000000000 (23 bits after the implicit 1)
6. Result: 0 10000010 10001100000000000000000, which regrouped into nibbles reads 0100 0001 0100 0110 0000 0000 0000 0000 = 0x41460000

Double Precision (64-bit)

Double-precision floating-point provides: 1 sign bit, 11 exponent bits, and 52 fraction bits. The exponent uses excess-1023 bias.

Key characteristics:

• Approximate decimal precision: 15 to 16 significant digits (53 significant bits, counting the implicit 1)
• Approximate range of normal numbers: 2.2 × 10⁻³⁰⁸ to 1.8 × 10³⁰⁸; subnormals extend down to about 4.9 × 10⁻³²⁴
• Smallest positive normal number: 2⁻¹⁰²²
• Largest finite number: (2 − 2⁻⁵²) × 2¹⁰²³
• Machine epsilon, the gap between 1 and the next larger representable number: 2⁻⁵² (approximately 2.22 × 10⁻¹⁶); the unit roundoff is half of that, 2⁻⁵³, approximately 1.11 × 10⁻¹⁶

Double precision is the default for most scientific and engineering calculations, providing sufficient range and precision for the vast majority of applications.

Special Values

IEEE 754 reserves certain bit patterns for special values:

• Zero: Exponent and fraction both zero. IEEE 754 has both +0 and −0, which compare equal but may produce different results in some operations.
• Infinity: Exponent all ones, fraction all zeros. Results from overflow or from dividing a nonzero number by zero. Positive and negative infinity exist.
• NaN (Not a Number): Exponent all ones, fraction nonzero. Results from undefined operations like 0/0, infinity minus infinity, or square root of a negative number. NaN propagates through calculations and compares unequal to everything, including itself.
• Subnormal (denormalized) numbers: Exponent zero, fraction nonzero. Represent values smaller than the minimum normal number, providing gradual underflow toward zero. The implicit leading 1 becomes 0, so these values carry progressively fewer bits of precision. Current editions of IEEE 754 call them subnormal; older texts use denormalized.

Floating-Point Arithmetic Considerations

Floating-point arithmetic introduces subtleties that digital designers must understand:

• Rounding errors: Most decimal fractions cannot be exactly represented in binary floating-point, leading to small errors that can accumulate
• Associativity loss: (a + b) + c may not equal a + (b + c) due to rounding at different magnitudes
• Catastrophic cancellation: Subtracting nearly equal numbers loses significant digits of precision
• Overflow and underflow: Under the default rounding, results too large in magnitude overflow to infinity, while results too small for the normal range lose precision as subnormals and eventually round to zero

IEEE 754-1985 defined four rounding modes: round to nearest with ties to even, round toward positive infinity, round toward negative infinity, and round toward zero. The 2008 revision added a fifth, round to nearest with ties away from zero, and calls all five rounding-direction attributes; it requires the new one only of decimal implementations, so binary hardware need provide only the original four. Round to nearest with ties to even is the default and avoids the statistical bias that always rounding halfway cases in one direction would accumulate.

BCD Encoding

In BCD, each decimal digit 0-9 maps to its natural binary equivalent using four bits:

• 0 = 0000, 1 = 0001, 2 = 0010, 3 = 0011, 4 = 0100
• 5 = 0101, 6 = 0110, 7 = 0111, 8 = 1000, 9 = 1001

The combinations 1010 through 1111 are unused in standard BCD, making it less space-efficient than binary. A two-digit BCD number requires 8 bits but can only represent 0-99 (100 values), while 8 bits of binary can represent 0-255 (256 values).

Example: The decimal number 47 in BCD is 0100 0111 (4 = 0100, 7 = 0111).

BCD Arithmetic

BCD arithmetic requires correction when results exceed the valid range 0-9. After adding two BCD digits, if the result exceeds 9 or produces a carry, add 6 (0110) to correct the result. Adding 6 skips the six unused codes 1010 through 1111; the carry case covers digit sums of 16 and above, which overflow the four-bit field before the correction is applied.

Example: Adding 8 + 5 in BCD:

• 1000 + 0101 = 1101 (13 in binary, but invalid BCD)
• Add correction: 1101 + 0110 = 10011
• Result: 0001 0011 = 13 in BCD (1 carry, 3 units)

Many processors include a decimal adjust instruction that performs this correction automatically after binary addition, such as DAA on the Intel 8080, the Zilog Z80, and x86 processors outside 64-bit mode. The MOS 6502 takes another route: a decimal-mode flag makes its add and subtract instructions operate directly on packed BCD.

Packed and Unpacked BCD

Packed BCD stores two decimal digits per byte, maximizing storage efficiency. This format is common in financial applications and databases where decimal accuracy is paramount.

Unpacked BCD stores one decimal digit per byte, typically in the lower nibble with the upper nibble set to zero or used for a zone field. This format simplifies processing at the cost of doubling storage requirements.

ASCII digits (0x30 to 0x39) form a type of unpacked BCD, with the upper nibble serving as a zone that identifies the character as a digit.

Applications of BCD

• Financial calculations: Banks and accounting systems use BCD or other decimal arithmetic to avoid the rounding errors of binary floating-point in monetary calculations
• Digital displays: Seven-segment displays connect naturally to BCD, with dedicated decoder chips converting BCD to segment patterns
• Real-time clocks: Many RTC chips store time values in BCD format
• Measurement instruments: Frequency counters and many older digital multimeters count in chains of BCD decade counters, so each counter can drive its display digit directly

Gray Code Sequence

The 4-bit Gray code sequence differs from natural binary:

Conversion Algorithms

Binary to Gray: The most significant bit remains the same. Each subsequent Gray bit is the XOR of the corresponding binary bit and the binary bit to its left.

With the bits numbered from 0 at the least significant end to n at the most significant:

Gray[n] = Binary[n] (for the MSB)

Gray[i] = Binary[i + 1] XOR Binary[i] (for the other bits)

Applied to the whole word at once, the Gray code is the binary number XORed with itself shifted right by one place. For example, binary 1011 (decimal 11) XOR 0101 gives Gray 1110, as the table shows.

Gray to Binary: The most significant bit remains the same. Each subsequent binary bit is the XOR of the corresponding Gray bit and the previously computed binary bit, so the conversion ripples from the MSB downward.

Binary[n] = Gray[n] (for the MSB)

Binary[i] = Binary[i + 1] XOR Gray[i] (for the other bits)

Applications

• Absolute rotary encoders: An encoder disc carries one track per bit. With a Gray-coded disc only one track changes at each sector boundary, so a reading taken exactly on a boundary is off by at most one position; with a plain binary disc several tracks change together, and a slight misalignment can produce a reading far from the true one
• Karnaugh maps: Gray code ordering ensures adjacent cells differ by one variable, simplifying Boolean minimization
• Analog-to-digital converters: Some ADC designs, notably flash and folding converters, use Gray code internally so that a comparator that resolves late or wrongly near a code transition causes an error of about one code rather than a large jump
• FIFO pointers: Asynchronous FIFO designs pass their read and write pointers between clock domains in Gray code. Because only one bit changes per increment, a pointer sampled mid-transition reads as either its old or its new value, never as an unrelated one
• Genetic algorithms: Gray encoding of numeric parameters removes the "Hamming cliffs" of plain binary, where neighboring values such as 7 (0111) and 8 (1000) differ in every bit, so a single-bit mutation can reach an adjacent value

Excess-3 Encoding

Each excess-3 code is the four-bit binary form of d + 3, so the ten digits occupy the codes 0011 through 1100 and the three codes at each end of the range go unused.

Self-Complementing Property

The nine's complement of a decimal digit d is (9 − d). In excess-3, the one's complement (bit inversion) of any digit produces its nine's complement, because inverting the four bits of d + 3 gives 15 − (d + 3) = (9 − d) + 3:

• 0 (0011) inverted = (1100) = 9
• 3 (0110) inverted = (1001) = 6
• 4 (0111) inverted = (1000) = 5

This property simplifies decimal subtraction hardware by allowing subtraction through addition of the nine's complement plus one (similar to two's complement for binary).

Excess-3 addition has a second convenience. The sum of two excess-3 digits is (a + 3) + (b + 3) = a + b + 6, which overflows four bits exactly when the decimal sum a + b (plus any carry in from the digit below) exceeds 9, so the binary carry out of each digit is the correct decimal carry. The result then needs only a fixed correction: subtract 3 from a digit that produced no carry, and add 3 to one that did.

Historical Context

Excess-3 is also called the Stibitz code, after George Stibitz, the Bell Telephone Laboratories pioneer of relay calculators. It was used on some early computers that performed decimal arithmetic, and later in cash registers and the hand-held electronic calculators of the 1970s. While less common in modern systems, understanding excess-3 provides insight into the design considerations of early computing and the value of self-complementing codes.

ASCII Structure

ASCII divides its 128 code points into distinct regions:

• Control characters (0-31, 127): Non-printable characters for communication control, including NUL (0), TAB (9), LF/newline (10), CR/carriage return (13), and DEL (127)
• Punctuation and symbols (32-47, 58-64, 91-96, 123-126): Space (32) and the punctuation marks and symbols that fill the gaps around the digit and letter ranges
• Digits (48-57): Characters '0' through '9'. Note that subtracting 48 (or 0x30) converts an ASCII digit to its numeric value
• Uppercase letters (65-90): 'A' through 'Z'. Adding 32 converts to lowercase
• Lowercase letters (97-122): 'a' through 'z'. Subtracting 32 converts to uppercase

ASCII Properties

ASCII's design includes several useful properties:

• Numeric ordering: Character codes for digits and letters are sequential, enabling simple comparisons and sorting
• Case conversion: Uppercase and lowercase letters differ only in bit 5 (value 32, with bits numbered from 0 at the least significant end), enabling efficient case conversion with a single XOR or bit operation
• Digit extraction: ASCII digits 0-9 occupy codes 48-57 (0x30 to 0x39), so masking the lower four bits yields the numeric value
• Control characters: Control characters can be represented as Ctrl+letter, where the control character code equals the letter code with bits 5 and 6 cleared; Ctrl+M, for example, gives 13, the carriage return

Extended ASCII

Various 8-bit extensions to ASCII use codes 128-255 for additional characters. No single extension prevailed: standards bodies and vendors each defined their own, and the result was the "code page" system, in which the same byte means different characters in different regions and on different platforms. Common extensions include:

• ISO 8859-1 (Latin-1): Western European characters, accented letters
• Windows-1252: Similar to Latin-1 with additional characters in the 128-159 range
• Code page 437: Original IBM PC character set with line drawing and box characters

These incompatible extensions led to the development of Unicode as a universal character encoding standard.

Unicode Code Points

Unicode assigns each character a unique code point, written as U+ followed by at least four hexadecimal digits (U+0041 for the letter A, U+1F600 for an emoji). Unicode 18.0, released on 16 September 2026, encodes 172,808 characters across more than 160 scripts. Code points range from U+0000 to U+10FFFF, organized into 17 planes of 65,536 code points each, 1,114,112 code points in all:

• Basic Multilingual Plane (BMP, Plane 0): U+0000 to U+FFFF, containing most commonly used characters
• Supplementary Planes (1-16): U+10000 to U+10FFFF, containing less common scripts, historical characters, and emoji, with Planes 15 and 16 reserved for private use

The first 128 Unicode code points match ASCII exactly, ensuring backward compatibility with ASCII text, and the first 256 match ISO 8859-1.

UTF-8 Encoding

UTF-8 is a variable-length encoding that represents Unicode code points using one to four bytes. Its design maintains ASCII compatibility while efficiently encoding the full Unicode range:

• 1 byte (0xxxxxxx): ASCII characters (U+0000 to U+007F)
• 2 bytes (110xxxxx 10xxxxxx): Accented Latin letters and the Greek, Cyrillic, Hebrew, and Arabic alphabets, among others (U+0080 to U+07FF)
• 3 bytes (1110xxxx 10xxxxxx 10xxxxxx): The rest of the BMP, including CJK (U+0800 to U+FFFF, excluding the surrogate range described below)
• 4 bytes (11110xxx 10xxxxxx 10xxxxxx 10xxxxxx): Supplementary characters (U+10000 to U+10FFFF)

The x positions carry the bits of the code point, most significant first. U+1F600, for example, lies above U+FFFF and therefore takes the four-byte form, F0 9F 98 80.

UTF-8 advantages include ASCII compatibility, self-synchronization (a lead byte and a continuation byte can always be told apart, so a decoder can find the next character boundary from any position), and no byte-order issues. It has become the dominant encoding for web content and Unix-like systems.

UTF-16 and UTF-32

UTF-16 uses 16-bit code units. BMP characters require one code unit; supplementary characters require two (a surrogate pair). UTF-16 is used internally by Windows, Java, and JavaScript. Surrogate pairs use special code points (U+D800 to U+DFFF) reserved for this purpose and never assigned to characters. To form a pair, subtract 0x10000 from the code point, which leaves a 20-bit value; its upper 10 bits are added to 0xD800 to give the high surrogate, and its lower 10 bits to 0xDC00 to give the low surrogate. U+1F600 becomes D83D DE00.

UTF-32 uses 32-bit code units, directly encoding each Unicode code point. While simple and fixed-width, UTF-32 requires four bytes per character, making it memory-inefficient for most text. It finds use in internal processing where fixed-width simplifies algorithms.

Both UTF-16 and UTF-32 have byte-order variants (big-endian and little-endian), often indicated by a Byte Order Mark (BOM) at the beginning of the data.

Parity Bits

The simplest error-detecting code adds a single parity bit to each data word. The parity bit is set so that the total number of 1s in the combined word is either always even (even parity) or always odd (odd parity).

For even parity, the parity bit is the XOR of all data bits. If any single bit flips during transmission, the received parity will be incorrect, indicating an error.

Limitations of single-bit parity:

• Detects only odd numbers of bit errors (1, 3, 5, …)
• Cannot detect even numbers of errors (2, 4, 6, …)
• Cannot identify which bit is in error (no correction possible)

Despite limitations, parity remains useful for simple applications and as a component of more sophisticated schemes. Memory systems have traditionally used one parity bit per byte to detect single-bit errors in RAM, although error-correcting codes have largely taken over where memory is protected at all.

Checksums

Checksums compute a summary value from a block of data, appended to the block for verification. Simple checksums add all data values (bytes or words) and store the result. The receiver computes the same sum and compares.

Common checksum algorithms:

• Simple sum: Add all bytes, typically keeping only the lower bits. Can miss errors that cancel (swapping bytes or offsetting errors)
• One's complement sum: The Internet checksum of IPv4, TCP, and UDP; the sender transmits the complement of the end-around-carry sum, so the receiver can include the checksum in its own sum and expect all 1s
• Fletcher's checksum: Maintains two running sums, the second accumulating the first, so the result depends on the order of the data and catches most reordering that a simple sum misses
• Adler-32: Similar to Fletcher but computed modulo the prime 65,521; used in the zlib format

Cyclic Redundancy Check (CRC)

CRC treats data as a polynomial and computes the remainder when divided by a generator polynomial. CRCs provide strong error detection with efficient hardware implementation using shift registers and XOR gates.

Common CRC polynomials:

• CRC-8: 8-bit CRC for small data blocks
• CRC-16: Used in Modbus, USB, and other protocols
• CRC-32: Used in Ethernet, ZIP files, PNG images; polynomial 0x04C11DB7

CRC properties, each of which depends on the generator polynomial and some on the message length:

• Detects all single-bit errors, provided the generator has at least two terms, as every practical one does
• Detects all double-bit errors within any code word no longer than the period of the generator; a primitive generator of degree r has the longest possible period, 2^r − 1 bits
• Detects every error affecting an odd number of bits if and only if x + 1 divides the generator; the Ethernet CRC-32 polynomial lacks that factor
• Detects every burst error of r bits or fewer, where r is the degree of the generator and the width of the CRC

CRC computation can be implemented efficiently in hardware using linear feedback shift registers (LFSRs), or in software using lookup tables.

Hamming Codes

Hamming codes go beyond detection: they locate a single flipped bit, so the receiver can correct it by flipping it back.

Hamming codes place check bits at power-of-2 positions (1, 2, 4, 8, …). Each check bit covers the positions whose binary representation includes that power of 2, so every position is covered by a unique combination of check bits. When an error occurs, the check bits form a syndrome pointing to the error position. With r check bits, a Hamming code can protect up to 2^r − r − 1 data bits: 4 with 3 check bits, 11 with 4, and 120 with 7.

For a (7,4) Hamming code with 4 data bits and 3 check bits:

• Position 1 (check): covers positions 1, 3, 5, 7
• Position 2 (check): covers positions 2, 3, 6, 7
• Position 3 (data)
• Position 4 (check): covers positions 4, 5, 6, 7
• Positions 5, 6, 7 (data)

The syndrome (binary number formed by failed check bits) indicates the position of the error, enabling correction by flipping that bit. A worked example with even parity:

1. Place the data bits 1, 0, 1, 1 in positions 3, 5, 6, and 7.
2. Set each check bit to the XOR of the data bits it covers: position 1 = 1 XOR 0 XOR 1 = 0, position 2 = 1 XOR 1 XOR 1 = 1, and position 4 = 0 XOR 1 XOR 1 = 0. The transmitted word, positions 1 to 7, is 0110011.
3. Suppose position 6 flips in transit, so 0110001 arrives.
4. Recheck each group: positions 1, 3, 5, 7 still have even parity, but positions 2, 3, 6, 7 and positions 4, 5, 6, 7 do not.
5. The failed checks are 4 and 2, giving the syndrome 110 in binary, or 6. Flipping position 6 restores 0110011.

A plain Hamming code has a minimum distance of 3: enumerating the sixteen codewords of the (7,4) code shows that every nonzero codeword has at least three 1s, so any two codewords differ in at least three bits. That is enough to correct any single-bit error or, used for detection only, to detect any double-bit error, but not to do both at once. A double-bit error always produces a nonzero syndrome that points at a third bit, so a decoder set to correct turns it into a three-bit error without noticing.

Adding one overall parity bit, covering every other bit of the word, gives the extended Hamming code, such as the (8,4) code, with a minimum distance of 4. It corrects single-bit errors and detects double-bit errors at the same time, a capability called SECDED (single error correction, double error detection): a nonzero syndrome with the overall parity wrong marks a correctable single-bit error, and a nonzero syndrome with the overall parity correct marks an uncorrectable double-bit error. Conventional ECC memory applies a SECDED code to each 64-bit word, adding 8 check bits to form a 72-bit code word; in practice this is usually a Hsiao code, a close relative of the extended Hamming code with the same number of check bits.

Run-Length Encoding (RLE)

RLE replaces sequences of repeated values with a count and the value. It is effective for data with long runs of identical values, such as simple graphics or sparse data.

Example: "AAAAAABBBCC" becomes "6A3B2C" or in binary form, a sequence of count-value pairs.

RLE appears in PCX graphics format, fax transmission (Group 3 fax, which Huffman-codes the lengths of its runs of white and black pixels), and as a component of more complex schemes. It can actually expand data if runs are short, so practical implementations include escape codes or only encode runs above a minimum length.

Huffman Coding

Huffman coding assigns shorter codes to more frequent symbols and longer codes to less frequent symbols, minimizing average code length. The code is prefix-free: no code is a prefix of another, enabling unambiguous decoding.

Huffman tree construction:

1. Create a leaf node for each symbol with its frequency
2. Repeatedly combine the two lowest-frequency nodes into a new internal node
3. Continue until one root node remains
4. Assign 0 to left branches and 1 to right branches (or vice versa)
5. Read codes by traversing from root to each leaf

Huffman coding is optimal among codes that give each symbol its own whole number of bits, but it cannot exploit patterns across symbols, and because every code length is a whole number of bits, its average length can exceed the entropy of the source by up to nearly one bit per symbol when one symbol is very probable. It serves as the entropy-coding stage of baseline JPEG, MP3, DEFLATE, and many other compression formats.

Arithmetic Coding

Arithmetic coding represents an entire message as a single number between 0 and 1, achieving compression closer to the theoretical entropy limit than Huffman coding. Each symbol narrows the range based on its probability, with the final number uniquely identifying the message.

Arithmetic coding can approach optimal compression for any probability distribution and naturally handles adaptive models where probabilities change based on context. It is used in the MQ coder of JPEG 2000, in CABAC, the context-adaptive binary arithmetic coder of H.264 and H.265 video, and in other modern compression algorithms.

Dictionary-Based Compression

Dictionary-based methods replace repeated patterns with references to a dictionary of previously seen patterns:

• LZ77: Uses a sliding window as the dictionary; matches reference a position and length in recent data. It underlies DEFLATE, which pairs it with Huffman coding and is the format inside gzip, zlib, ZIP, and PNG.
• LZ78/LZW: Builds an explicit dictionary during encoding; references are dictionary indices. Used in GIF images and Unix compress.

Modern algorithms like LZMA (used in 7-Zip and xz) combine dictionary compression with sophisticated entropy coding for high compression ratios.

Choosing Number Representations

Selecting appropriate number representations depends on application requirements:

• Fixed-point vs. floating-point: Fixed-point offers deterministic timing and simpler hardware but limited range; floating-point provides wide range and automatic scaling but introduces rounding complexities
• Signed representation: Two's complement for general-purpose computing; sign-magnitude for floating-point significands; biased for floating-point exponents
• Precision requirements: Match word size to needed precision while considering memory and performance implications
• BCD vs. binary: Use BCD when decimal precision is critical and display conversion is frequent; use binary for general computation

Endianness

Multi-byte values can be stored with the most significant byte first (big-endian) or least significant byte first (little-endian). The 32-bit value 0x12345678 occupies four consecutive addresses as 12 34 56 78 in big-endian order and as 78 56 34 12 in little-endian order. This affects data interchange between systems:

• Big-endian: Most significant byte at the lowest address, matching the order in which numbers are written; used in network protocols (network byte order) and by processors such as the Motorola 68000 family and SPARC
• Little-endian: Least significant byte at the lowest address, so multi-byte arithmetic can start at the base address and a narrower read of the same address returns the low-order part; used by x86 and, in their usual configuration, by Arm processors, which cover most modern systems

When exchanging binary data between systems, explicit conversion using functions such as htons and ntohs (host to network short, network to host short) and their 32-bit counterparts htonl and ntohl ensures correct interpretation regardless of native byte order.

Code Selection for Specific Applications

• Position encoding: Gray code for encoders and sensors
• Error detection in storage: CRC for block verification, ECC for bit-level correction
• Communication protocols: CRC for frame checking, possibly with forward error correction for unreliable channels
• Text storage: UTF-8 for modern applications, ASCII for legacy compatibility
• Financial calculations: BCD or decimal floating-point to preserve exact decimal values