Electronics Guide

Single Parity Bit

The single parity bit provides minimal protection at minimal cost. For a data word of n bits, adding one parity bit increases the overhead by only 1/(n+1). The sender counts the number of one bits in the data and sets the parity bit to achieve the desired parity. The receiver counts all bits including the parity bit and verifies that the count matches the expected parity.

Single parity reliably detects all single-bit errors and, more generally, any odd number of bit errors. However, it completely fails to detect even numbers of bit errors, including the common case of two-bit errors. If two bits flip, the parity remains correct even though the data is corrupted. This fundamental limitation restricts single parity to applications where multi-bit errors are rare.

Despite its limitations, single parity remains widely used due to its extreme simplicity. Memory systems have traditionally used parity protection for each byte, providing basic protection against soft errors. Serial communication protocols often include a parity bit as a simple check against transmission errors. The low overhead and trivial implementation make parity attractive when only basic protection is needed.

Two-Dimensional Parity

Two-dimensional parity extends the basic concept by arranging data in a rectangular array and computing parity for both rows and columns. This structure provides significantly better error detection and even limited error correction capability at the cost of additional redundancy.

In two-dimensional parity, the data bits are organized into rows and columns. A parity bit is computed for each row and each column, with an additional parity bit for the parity bits themselves. Because the scheme is the product of two single-parity-check codes, it has a minimum Hamming distance of four: it detects all single-, double-, and triple-bit errors, along with many patterns of four or more. A single-bit error can even be corrected by locating the intersection of the row and column whose parity fails.

The redundancy of two-dimensional parity depends on the array dimensions. For an m-by-n array of data bits, the scheme requires m + n + 1 parity bits, giving a redundancy of (m + n + 1)/(mn) which decreases as the array size increases. However, larger arrays increase the probability of undetectable error patterns.

Longitudinal Redundancy Check

The longitudinal redundancy check (LRC) applies the parity concept across multiple data words transmitted in sequence. Each bit position across all words in a block is protected by its own parity bit, forming a check character that follows the data block. This approach provides better protection than single parity while remaining computationally simple.

LRC is typically combined with character-level parity in what becomes a two-dimensional scheme applied to serial data streams. The combination detects burst errors that span multiple characters better than either technique alone. Many legacy communication protocols used LRC as part of their error detection strategy.

Simple Checksum

The simplest checksum approach sums all data words and uses the result, or a portion of it, as the check value. The receiver computes the same sum and compares it to the transmitted checksum. Addition is commutative and associative, making checksum computation straightforward to implement in either hardware or software.

Simple addition checksums detect any single-bit error because changing one bit necessarily changes the sum. However, certain error patterns escape detection, particularly errors that produce compensating changes whose effects cancel in the sum. Transposition of data words goes undetected because addition is commutative. These limitations motivated development of more sophisticated checksum algorithms.

The Internet checksum used in IPv4 headers, TCP, UDP, and ICMP treats the message as a sequence of 16-bit words, forms their ones' complement sum, and transmits the ones' complement of that sum. RFC 1071 documents the formulation. The end-around carry makes the sum independent of byte order, so the same arithmetic works on big-endian and little-endian machines, and the sum can be updated incrementally when one header field changes rather than recomputed across the whole datagram.

The same algebraic properties set the limits of the scheme. Because the sum is commutative and associative, reordering the 16-bit words leaves it unchanged. Because zero acts as an identity, inserting or deleting zero-valued words leaves it unchanged. Compensating errors in two different words cancel. A CRC of the same width detects every one of these patterns, so the Internet checksum trades detection strength for arithmetic that costs almost nothing. IPv6 removed the header checksum altogether and requires a UDP checksum instead, on the reasoning that link-layer CRCs and transport-layer checks already cover what the header checksum duplicated.

Fletcher Checksum

The Fletcher checksum, developed by John Fletcher at Lawrence Livermore National Laboratory, improves upon simple checksums by computing two running sums that incorporate positional information. This approach detects transposition errors that defeat simple checksums while adding minimal computational overhead.

The algorithm maintains two accumulators. The first accumulator sums the data values directly, while the second accumulator sums the running values of the first accumulator. This second sum effectively weights each data value by its position in the sequence, making the checksum sensitive to the order of data values. The final checksum combines both accumulators.

Fletcher-16 operates on 8-bit data values and produces a 16-bit checksum using modulo-255 arithmetic. Fletcher-32 operates on 16-bit values producing a 32-bit checksum, using modulo-65535 arithmetic. The modular arithmetic keeps accumulator values bounded while maintaining the mathematical properties needed for error detection. A Fletcher checksum holds a Hamming distance of three up to a length that its modulus fixes, then falls to two. Maxino and Koopman measured the boundary for Fletcher-16 at a code word of 2,056 bits and calculated 1,048,592 bits for Fletcher-32; below those lengths every one- and two-bit error is detected. A Fletcher checksum also detects every burst shorter than the checksum width. This places it between the addition checksums and a well-chosen CRC: clearly better than addition at negligible extra cost, yet consistently at least one bit of Hamming distance behind a good CRC of the same width at the message lengths embedded networks actually carry.

The ISO transport protocol and many embedded systems use Fletcher checksums as a balance between protection and efficiency. The algorithm is particularly well-suited to software implementation on processors without hardware CRC support.

Adler-32

Adler-32 is a checksum algorithm developed by Mark Adler that is similar in structure to Fletcher-32 but uses different modular arithmetic. The algorithm was designed for the zlib compression library, so it guards every zlib stream, including the compressed image data inside a PNG file. The PNG chunks that wrap that data carry a CRC-32 rather than an Adler-32. The rsync file synchronization tool uses a rolling checksum built on the same construction.

Like Fletcher checksums, Adler-32 maintains two running sums. The first sum A is a simple sum of all bytes plus one, while the second sum B is the sum of all intermediate values of A. Both sums are computed modulo 65521, the largest prime less than 2¹⁶. The final checksum combines A and B into a single 32-bit value.

The prime modulus is widely assumed to mix the checksum bits better, and therefore to detect more errors, than the modulus of 2¹⁶ − 1 that Fletcher-32 uses. Measurement does not support the assumption. Maxino and Koopman found that the Adler checksum beats the Fletcher checksum only at 16 bits and only inside that width's Hamming-distance-three region, and that Adler detects bursts one bit shorter than Fletcher does, precisely because its modulus falls below 2¹⁶ − 1. Adler-32 is also slightly slower, because reduction modulo a prime costs more than reduction modulo an all-ones value.

Against a well-chosen CRC-32, Adler-32 gives up at least one bit of Hamming distance at the message lengths that ordinary files and packets occupy, and more at some lengths. The case for Adler-32 therefore rests on speed rather than on detection strength: it computes faster than a table-driven CRC-32 on processors without a CRC instruction, which is why zlib adopted it for a library whose compression and decompression throughput is the point.

Mathematical Foundation

CRC computation operates in the algebraic structure of polynomials over the binary field GF(2), where coefficients can only be 0 or 1 and addition is equivalent to exclusive-or. A data message is represented as a polynomial where each bit becomes a coefficient: the sequence 11010 represents x⁴ + x³ + x. Addition and subtraction coincide in this field, so the long division carries no borrows and reduces to a sequence of exclusive-or operations. This representation brings well-understood algebraic theory to bear on error detection.

To compute a CRC, the data polynomial is first multiplied by x^r, where r is the degree of the generator polynomial, effectively appending r zero bits. This extended polynomial is then divided by the generator polynomial, with the remainder becoming the CRC value. The transmitted message consists of the original data followed by the CRC remainder.

At the receiver, the complete message including CRC is divided by the same generator polynomial. If no errors have occurred, the remainder is zero. Any non-zero remainder indicates an error. One statement covers every detection guarantee that follows: an error escapes exactly when the pattern of flipped bits, read as a polynomial, is itself a nonzero multiple of the generator. Every other pattern leaves a nonzero remainder. Choosing a generator is therefore the work of choosing which patterns it divides.

Generator Polynomial Selection

The error detection capability of a CRC depends critically on the choice of generator polynomial. Different polynomials offer different guarantees, and published analysis has identified good choices for particular message lengths. The properties that matter are the degree of the polynomial, its factorization, and the Hamming distance it achieves at the length actually in use.

Three classical guarantees are often quoted as properties of CRCs in general. Each in fact rests on a specific property of the generator. Every single-bit error is detected when the generator has two or more nonzero terms, because the error polynomial xⁱ has no divisors except powers of x, so only a generator that is itself a bare power of x could hide one; every generator in practical use satisfies the condition, at any message length. Every error that flips an odd number of bits is detected when, and only when, x + 1 divides the generator, because x + 1 divides an error polynomial exactly when that polynomial has an even number of terms. Double-bit errors turn on the period of the generator: the error polynomial xⁱ + x^j factors as x^j(x^i−j + 1), so the pair escapes only when the generator divides x^k + 1 for k equal to the separation of the two flipped bits.

A primitive polynomial of degree r has period 2^r − 1, the longest available, which places every double-bit error inside a code word shorter than 2^r − 1 bits within the guarantee. A primitive polynomial is irreducible, however, so it cannot also have x + 1 as a factor. Many standard generators resolve the conflict by multiplying a primitive polynomial of degree r by x + 1, spending one extra degree to buy odd-error detection while keeping the double-bit reach. The 16-bit polynomials of HDLC and Modbus both take that route, each factoring into x + 1 times a primitive polynomial of degree 15. The CRC-32 of Ethernet does not.

Burst error detection is often the primary concern, since errors in cables, disks, and radio links arrive in clusters rather than independently. A generator of degree r detects every burst of length r or shorter, because such a burst cannot be a multiple of a polynomial of higher degree. A burst of exactly r + 1 bits has both end bits set and r − 1 free interior bits, and escapes only when it reproduces the generator itself, so one pattern in 2^r−1 escapes and the detection probability is 1 − 2^−(r−1). Bursts longer than r + 1 escape for one pattern in 2^r, giving 1 − 2^−r. For a 16-bit CRC that means a guaranteed reach of 16 bits, roughly 99.997 percent of 17-bit bursts, and roughly 99.9985 percent of everything longer. Note that the guaranteed reach is the degree of the generator, not some larger figure derived from the frame length.

Common CRC Standards

CRC-8 polynomials produce an 8-bit check value suitable for protecting small data units. ITU-T Recommendation I.432.1 specifies x⁸ + x² + x + 1 for the header error control field of an ATM cell, adding the constant 0x55 to the remainder so that an all-zero header does not yield an all-zero check value. Because the field covers only the four header bytes, an ATM receiver can use it to correct a single-bit error rather than merely report one. The same polynomial serves as the packet error code of the System Management Bus. Eight-bit CRCs suit short messages where overhead must stay minimal.

CRC-16 polynomials carry most serial and industrial traffic, and two of them dominate. The frame check sequence of HDLC and X.25 uses x¹⁶ + x¹² + x⁵ + 1, processed least significant bit first from a register preset to all ones and complemented on output. The polynomial x¹⁶ + x¹⁵ + x² + 1 appears under the names CRC-16, ARC, and CRC-16-IBM: Modbus RTU uses it reflected from an all-ones preset with no final complement, while USB uses the same polynomial and preset and does complement the result. USB does not rely on that check alone. Token and start-of-frame packets carry a five-bit CRC over x⁵ + x² + 1, and only data packets carry the 16-bit one. Both 16-bit polynomials are divisible by x + 1, so both detect every error that flips an odd number of bits.

CRC-32 protects larger blocks. The polynomial standardized for Ethernet, and reused almost everywhere else, is

x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1,

computed reflected from an all-ones preset and complemented on output. The same algorithm guards Ethernet frames, ZIP archives, and the chunks of a PNG file; a conforming implementation returns 0xCBF43926 for the nine characters 123456789, which is the customary way to confirm that two implementations agree. This polynomial has fifteen terms, an odd number, so x + 1 does not divide it and it does not detect every odd-bit error. It is instead primitive of degree 32, which brings every double-bit error inside a code word shorter than 2³² − 1 bits within the guarantee. The trade was deliberate, and it shows that a wider CRC is not automatically stronger against every class of error.

CRC-64 polynomials serve where a corrupted block could go unnoticed for years. ECMA-182, the interchange standard for 12.7 mm DLT tape cartridges, defines a 64-bit CRC that later file systems and archival formats reused. The extra computation is justified when the data outlives the equipment that wrote it.

Parameters Beyond the Polynomial

A polynomial alone does not specify a CRC. Four further parameters decide what check value a given message produces: the initial contents of the register, whether each byte enters least significant bit first or most significant bit first, whether the final register contents are reflected, and what constant the result is exclusive-ored with before transmission. Two implementations that agree on the polynomial and differ on any of these will reject each other's frames.

Each parameter exists for a concrete reason. A register initialized to zero is blind to leading zero bits, because zeros shifted into an empty register leave it empty; presetting to all ones removes that blind spot. Complementing the output makes the residue computed at the receiver a fixed nonzero constant rather than zero, so a frame truncated to nothing, or a dead link read as a run of zeros, does not present itself as valid. Bit ordering follows the order in which the serial hardware moves the bits, which is why protocols built on least-significant-bit-first links define reflected CRCs.

The name CRC-16-CCITT shows the confusion that follows from naming only the polynomial. At least two incompatible parameter sets travel under that name over x¹⁶ + x¹² + x⁵ + 1, differing in bit order and preset, and neither of them matches the HDLC frame check sequence, which presets to all ones and complements its output. Interoperation requires the full parameter set, or a published check value over an agreed reference string, not the polynomial by itself.

Hardware Implementation

CRC computation maps elegantly to hardware using linear feedback shift registers (LFSRs). An LFSR consists of a chain of flip-flops with exclusive-or gates feeding back from positions corresponding to the generator polynomial terms. As data bits shift through the register, the feedback connections perform the polynomial division automatically.

A serial LFSR implementation processes one bit per clock cycle, requiring r clock cycles to shift through all bits. For high-speed applications, parallel implementations process multiple bits simultaneously by deriving the combined effect of several serial steps. Modern communication chips routinely compute CRCs at line rate using parallel architectures.

Many contemporary processors include hardware CRC instructions that compute CRC values at speeds approaching memory bandwidth. Intel processors support CRC-32C through the SSE4.2 CRC32 instruction, while the Armv8-A architecture provides dedicated CRC32 and CRC32C instructions, mandatory since Armv8.1-A, together with polynomial-multiply instructions that accelerate other CRC variants. These hardware accelerators make CRCs practical even for the highest-performance applications.

Software Implementation

Software CRC computation typically uses lookup tables to process one or more bytes at each step. A table with 256 entries, indexed by byte value, contains the CRC contribution of each possible byte. The algorithm XORs each data byte with the current CRC, looks up the result in the table, and updates the CRC. This byte-at-a-time approach is simple and reasonably efficient.

Larger tables enable processing multiple bytes per lookup at the cost of memory. Slicing-by-4 and slicing-by-8 algorithms use multiple tables to process 4 or 8 bytes per iteration, achieving speeds several times faster than single-byte implementations. The optimal table size depends on cache characteristics and the relative costs of memory access and computation.

Bit-by-bit computation without tables is possible but slow, typically reserved for resource-constrained implementations or for verifying table-based implementations. The algorithm shifts and conditionally XORs based on the outgoing bit, directly mimicking the hardware LFSR implementation.

HMAC

HMAC (Hash-based Message Authentication Code) constructs a MAC from a cryptographic hash function and a secret key. The algorithm applies the hash function twice, first to the key XORed with an inner padding concatenated with the message, then to the key XORed with an outer padding concatenated with the first hash result. This nested structure provides security even if the underlying hash function has certain weaknesses.

HMAC can be used with any cryptographic hash function: HMAC-SHA256 uses SHA-256, HMAC-SHA384 uses SHA-384, and so on. The security of HMAC depends on the properties of the underlying hash function. With a strong hash function and sufficient key length, HMAC provides robust protection against forgery attempts.

HMAC is used extensively in security protocols including TLS, IPsec, and SSH. It provides integrity protection for communication channels and authentication for API requests. The algorithm is standardized in RFC 2104 and in FIPS 198-1.

CMAC and GMAC

CMAC (Cipher-based Message Authentication Code) constructs a MAC from a block cipher rather than a hash function. The algorithm processes the message through the cipher in CBC mode with a carefully designed final step that prevents certain attacks. CMAC with AES is standardized in NIST SP 800-38B and is used in various security protocols.

GMAC (Galois Message Authentication Code) is the authentication component of Galois/Counter Mode (GCM), providing both encryption and authentication. GMAC uses multiplication in a Galois field to compute the authentication tag, enabling efficient hardware implementation. When only authentication without encryption is needed, GMAC can be used standalone.

Poly1305

Poly1305 is a high-speed MAC designed by Daniel J. Bernstein. The algorithm evaluates a polynomial modulo the prime 2¹³⁰ − 5, a structure chosen to enable efficient implementation on modern processors. Because Poly1305 is a one-time authenticator, each message requires a fresh key, which a cipher derives from a nonce: Poly1305-AES uses the AES block cipher for this step, while Poly1305-ChaCha20 uses the ChaCha20 stream cipher.

The combination of ChaCha20 and Poly1305, known as ChaCha20-Poly1305, has been adopted by TLS 1.3, OpenSSH, and many other protocols. Its excellent performance on processors without AES acceleration makes it particularly attractive for mobile and embedded applications.

Theoretical Analysis

For a uniformly random error pattern, an r-bit check value gives a baseline probability of 2^−r that the error goes undetected. That assumption of uniformity is rarely true. Real error sources produce structured patterns, and the interaction between that structure and the code determines the detection probability that a system actually experiences.

The Hamming distance of a code fixes its guaranteed detection capability: a code with minimum Hamming distance d detects every error pattern of weight up to d − 1 bits. For a CRC, that distance is a function of message length as well as of the polynomial, and it falls in steps as the message grows. Koopman's published performance tables give the boundaries for the standard polynomials. The Ethernet CRC-32 holds a Hamming distance of 6 only for data words up to 268 bits, 5 up to 2,974 bits, and 4 up to 91,607 bits; beyond that it holds only 3, so in a long enough frame a three-bit error can pass. The HDLC polynomial x¹⁶ + x¹² + x⁵ + 1 holds a Hamming distance of 4 up to 32,751 bits, the period of its degree-15 factor less the sixteen check bits. Quoting a Hamming distance without the length it applies to therefore says very little.

The familiar figure of 2⁻³² for a CRC-32 needs the same care. It describes the residual fraction of error patterns that escape once the pattern lies outside the Hamming-distance guarantee. It is not a blanket probability of undetected error, and it does not apply to the light patterns that the distance guarantee already covers completely, where the probability is zero. A CRC chosen for the wrong length can be far worse than 2⁻³² suggests, and within its guaranteed region it is far better.

Burst detection is stated separately, because a burst is the error pattern most storage and communication channels actually produce. A CRC with a generator of degree r detects every burst of length r or shorter, and detects longer bursts with probability 1 − 2^−(r−1) at length r + 1 and 1 − 2^−r beyond it. These figures hold for any generator with a nonzero constant term and do not depend on message length.

Practical Considerations

Real systems experience bit error rates (BER) that depend on the physical medium and operating conditions. A communication link with a BER of 10⁻⁶ produces one error per million bits on average. At 1 Gbps that is roughly 1,000 errors per second, which is why robust detection matters even on links that seem clean.

The probability of undetected error in a complete system depends on the error rate, the distribution of error patterns, and the properties of the code at the frame length in use. A CRC-32 leaves at most about 2.3 patterns in 10¹⁰ undetected once a pattern falls outside its Hamming-distance guarantee, which is what 2⁻³² amounts to. Ethernet frames stay comfortably inside the Hamming-distance-4 region of that polynomial, since a maximum-size payload of 1,500 bytes is 12,000 bits against a boundary of 91,607. Systems that need more either widen the CRC or add a second, independent check.

Layering several checks does not simply add detection strength. A single well-chosen 32-bit CRC generally outperforms two independent 16-bit CRCs over the same frame, because the wider polynomial can be selected for a longer Hamming-distance region than either narrow one reaches. The reason protocols stack checks is different: each check covers a different fault domain. A link-layer CRC is verified and regenerated at every hop, so it cannot see corruption introduced inside a router's memory between the two verifications, while an end-to-end transport checksum spans exactly that gap. Defense in depth here buys coverage, not arithmetic.

False Positive Considerations

Error detection codes may occasionally indicate errors when none exist, though this is extremely rare with properly implemented codes. Hardware faults in the check value storage or computation logic can produce false positives. Robust systems must distinguish between data errors and detection mechanism failures.

The probability of false positives from cosmic rays or other random disturbances affecting the detection logic is typically negligible compared to the probability of errors in the protected data. However, systematic faults from design errors or manufacturing defects can produce correlation between data errors and detection failures, undermining the protection.