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. This arrangement detects all single-bit errors, all double-bit errors, and many patterns of three or more errors. Single-bit errors can even be corrected by identifying the intersection of the row and column with incorrect parity.

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 IP, TCP, UDP, and other protocols employs ones' complement addition of 16-bit words. This formulation has useful properties including end-around carry that simplifies computation and the ability to update the checksum incrementally when headers change. The Internet checksum has protected billions of packets but is known to have weaknesses against certain error patterns.

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. The modular arithmetic keeps accumulator values bounded while maintaining the mathematical properties needed for error detection. Fletcher checksums achieve error detection capability comparable to cyclic redundancy checks while requiring fewer computational resources.

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 and is used in many applications including the PNG image format and the rsync file synchronization tool.

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^16. The final checksum combines A and B into a single 32-bit value.

The choice of a prime modulus provides somewhat better error detection properties than the power-of-two-minus-one moduli used by Fletcher checksums. However, Adler-32 is slightly slower due to the more complex modular reduction. For very short data, Adler-32 provides weaker protection than CRC-32, but for typical file and message lengths the difference is negligible for most applications.

Adler-32 can be computed efficiently in software and is significantly faster than CRC-32 on processors without hardware CRC support. This speed advantage made it the checksum of choice for zlib, where compression and decompression performance is critical.

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^4 + x^3 + x. This polynomial representation enables the application of well-understood algebraic theory to 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. The mathematical properties of polynomial division ensure that many error patterns produce non-zero remainders and are therefore detected.

Generator Polynomial Selection

The error detection capability of a CRC depends critically on the choice of generator polynomial. Different polynomials offer different detection guarantees, and extensive mathematical analysis has identified optimal polynomials for various applications. Key properties to consider include the degree of the polynomial, its factorization, and its Hamming distance.

An r-degree generator polynomial produces an r-bit CRC and detects all single-bit errors in messages up to 2^r - 1 bits. If the polynomial has x + 1 as a factor, all odd numbers of bit errors are detected. Primitive polynomials, which generate the maximum-length sequence, provide the best protection against random errors.

Burst error detection is often the primary concern for CRCs. An r-bit CRC detects all burst errors of length r or less, detects all but one in 2^(r-1) bursts of length r + 1, and detects all but one in 2^r bursts of length greater than r + 1. These properties make CRCs particularly effective for storage and communication systems where errors tend to cluster.

Common CRC Standards

CRC-8 polynomials produce an 8-bit check value suitable for protecting small data units. The polynomial x^8 + x^2 + x + 1, standardized as CRC-8-CCITT, protects bytes in protocols including ATM cell headers. Eight-bit CRCs provide adequate protection for short messages where overhead must be minimal.

CRC-16 polynomials are widely used in communication protocols. CRC-16-CCITT (x^16 + x^12 + x^5 + 1) protects HDLC frames and many serial protocols. CRC-16-IBM (x^16 + x^15 + x^2 + 1) is used in USB, Modbus, and many industrial protocols. These 16-bit CRCs provide strong protection for message sizes up to several thousand bytes.

CRC-32 polynomials provide robust protection for larger data blocks. The most common CRC-32 polynomial (x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1) protects Ethernet frames, ZIP files, PNG images, and countless other applications. With 32 bits of redundancy, CRC-32 provides a very low probability of undetected errors for messages of practical size.

CRC-64 polynomials are used when even stronger protection is required. ECMA-182 standardized a CRC-64 for high-speed data links, and variants appear in some file systems and archival formats. The additional computational cost of 64-bit CRCs is justified when data integrity is paramount.

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 via the CRC32 instruction, while ARM processors provide polynomial multiplication instructions that accelerate CRC computation. 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 FIPS 198.

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 uses polynomial evaluation over a large prime field, chosen to enable efficient implementation on modern processors. Poly1305 is typically used with a stream cipher (Poly1305-AES, Poly1305-ChaCha20) that provides a unique key for each message.

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 random n-bit error pattern, an r-bit check value provides a baseline probability of 2^(-r) that the error goes undetected. This assumes the error pattern is uniformly random over all possible patterns, which is rarely true in practice. Real error sources produce structured error patterns whose interaction with the detection code determines actual detection probability.

The Hamming distance of a code determines its guaranteed detection capability. A code with minimum Hamming distance d detects all error patterns of weight up to d-1 bits. CRCs typically achieve minimum distances of 4 to 6 for messages up to several thousand bits, meaning they detect all errors of 3 to 5 bits regardless of pattern.

Burst error detection is quantified by the burst error detection capability. An r-bit CRC detects all burst errors of length r or less. For longer bursts, the detection probability depends on the specific polynomial and burst pattern, but is typically close to 1 - 2^(-r) for bursts longer than r + 1.

Practical Considerations

Real systems experience bit error rates (BER) that depend on the physical medium and operating conditions. A communication link with BER of 10^(-6) produces one error per million bits, on average. For a system with 1 Gbps throughput, this means roughly 1000 errors per second, emphasizing the importance of robust error detection.

The probability of undetected error in a complete system depends on the error rate, the error pattern distribution, and the detection code properties. For most applications, CRC-32 provides adequate protection, yielding undetected error probabilities below 10^(-10) for typical error rates. Applications requiring higher reliability may use longer CRCs or additional error detection layers.

Multiple independent check values provide stronger protection than a single check of equivalent length. For example, two independent 16-bit CRCs may detect errors that would escape a single 32-bit CRC, particularly if the error patterns have special structure. Some protocols use multiple error detection codes at different layers for defense in depth.

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.