Error Detection and Channel Coding

Introduction and Context

Digital communication systems are designed to reproduce information reliably despite noise, interference, fading, distortion, synchronization errors, and hardware imperfections. At the receiver, the detected sequence may differ from the transmitted sequence. Error detection and channel coding provide systematic methods for recognizing and correcting such differences.

Error detection adds structured redundancy so that a receiver can determine whether a received block is likely to be valid. Error-correcting channel coding goes further: it adds sufficient redundancy to identify and correct errors, usually without retransmission. These techniques are central to cellular networks, satellite links, optical systems, storage devices, wireless sensor networks, deep-space communication, and modern data networks.

A fundamental design tension exists. Redundancy improves reliability but reduces useful throughput and increases processing, bandwidth, latency, or energy requirements. At postgraduate level, channel coding should therefore be understood not merely as a collection of codes, but as an engineering discipline involving probability, algebra, information theory, algorithms, and system-level optimization.

Learning Objectives

After studying this chapter, the learner should be able to:

1. distinguish error detection, error correction, forward error correction, and automatic repeat request;
2. explain Hamming distance, minimum distance, code rate, and error patterns;
3. derive and apply the basic detection and correction bounds;
4. analyze parity-check, cyclic, CRC, block, convolutional, and modern iterative codes;
5. construct syndrome-based decoding procedures;
6. compare coding schemes using reliability, rate, complexity, latency, and bandwidth;
7. evaluate a coding design for a practical communication system.

1. Communication Errors and Coding Models

Let a binary information block be represented by a vector m of k bits. An encoder maps it to an n-bit codeword c. For a binary linear block code, this mapping may be written as

where G is a k × n generator matrix and arithmetic is over the binary field GF(2): addition is modulo 2 and multiplication follows ordinary binary multiplication. The code rate is

where R is dimensionless. A lower rate means more redundancy per information bit.

A common channel model is the binary symmetric channel (BSC). Each transmitted bit is independently inverted with probability p, called the crossover probability. If e is the error vector, the received vector is

where ⊕ denotes bitwise modulo-2 addition. The independent-error assumption is useful analytically, but real wireless channels can produce burst errors and correlated errors. Interleaving, burst-error codes, and channel-adaptive coding are then important.

For additive white Gaussian noise (AWGN), a received waveform is modeled as the transmitted waveform plus zero-mean Gaussian noise. Coding performance is often plotted against E_b/N_0, where E_b is energy per information bit and N_0 is the one-sided noise power spectral density. Comparisons must state whether energy is measured per coded bit or information bit, because the code rate changes the relationship.

2. Redundancy, Distance, and Fundamental Limits

2.1 Hamming weight and Hamming distance

The Hamming weight w_H(x) of a binary vector x is the number of nonzero positions. The Hamming distance between x and y is

For a linear code, the minimum distance d_min is the smallest Hamming weight among all nonzero codewords:

where C is the codebook. Geometrically, codewords are separated points in an n-dimensional binary space. Noise moves a transmitted point to a received point; decoding chooses a nearby valid codeword.

2.2 Detection and correction capability

A code with minimum distance d_min can detect every error pattern of weight up to d_min − 1. It can correct every error pattern of weight up to t, where

The detection result follows because an error of weight less than d_min cannot transform one valid codeword into another valid codeword. The correction result follows because Hamming spheres of radius t around distinct codewords do not overlap when 2t < d_min.

These are guaranteed worst-case properties, not exact probabilities of failure. A code may sometimes detect or correct patterns beyond these limits, but no guarantee is available for all such patterns.

For a binary linear block code with parameters (n,k,d_min), the redundancy is n − k bits, the rate is k/n, and the code contains 2^k codewords. A code is called systematic if the original k information bits appear explicitly in the codeword, with parity bits appended or interspersed.

2.3 Probability of undetected error

For a simple parity bit over a memoryless BSC with crossover probability p, an error is undetected when an even number of bit errors occurs. For a block of n transmitted bits including parity, the probability of undetected error is

The first term is the probability of an even number of errors, and the second term removes the zero-error case. This formula assumes independent bit errors and an ideal parity checker. For small p, undetected errors are much less likely than single-bit errors, but parity cannot detect any even-weight error pattern.

For a general code, undetected-error probability depends on the complete weight distribution and the decoder, not only on d_min. Consequently, d_min is essential but not sufficient for detailed performance prediction.

3. Linear Block Codes

A binary linear code is a vector subspace of GF(2)^n. It is closed under modulo-2 addition and includes the all-zero codeword. Two matrices describe it:

and

Here H is the (n − k) × n parity-check matrix. A valid received word must satisfy all parity checks. The syndrome of r is

If s = 0, the received word satisfies the parity checks. This does not prove that no error occurred: an error pattern that is itself a nonzero codeword produces zero syndrome and is undetected. If s ≠ 0, an error is detected.

Suppose r = c ⊕ e. Since Hc^T = 0,

Thus the syndrome depends only on the error pattern, not on the transmitted codeword. A syndrome decoder stores or computes the most likely error pattern associated with each syndrome and forms the estimate r ⊕ e.

Worked Example: Single-error syndrome correction

Consider the Hamming (7,4) code with parity-check matrix whose columns are the seven nonzero binary triples. Let the columns, from bit position 1 to 7, be 001, 010, 011, 100, 101, 110, and 111. If an error occurs in position 5, its error vector has a one only in position 5. The syndrome equals column 5, namely 101. Since every single-bit position has a unique nonzero column, the decoder identifies position 5 and flips that bit. The code has d_min = 3, so it corrects one error and detects two errors, although some two-error patterns may be miscorrected if treated as single errors.

3.1 Hamming codes and perfect codes

A binary Hamming code with m parity bits has block length n = 2^m − 1 and information length k = 2^m − m − 1. It has d_min = 3 and corrects one error. The parity-check columns enumerate all nonzero m-bit vectors, enabling direct syndrome-to-position mapping. Its rate approaches one as m increases, but its guaranteed correction remains one bit per block.

The Hamming bound describes a necessary condition for a t-error-correcting binary code:

where C(n,i) is the binomial coefficient. The left side counts the total volume of radius-t error spheres around all codewords. If equality holds, the code is perfect under the relevant metric. The single-error-correcting Hamming codes are important examples.

4. Cyclic Codes and CRC Error Detection

A cyclic code is a linear block code in which every cyclic shift of a codeword is also a codeword. Binary codewords can be represented as polynomials over GF(2). For a cyclic code of length n, a generator polynomial g(x) divides x^n − 1, and each codeword has the form

where m(x) is the message polynomial. A received polynomial r(x) is valid if the remainder after division by g(x) is zero.

Cyclic redundancy checks (CRCs) are optimized primarily for error detection rather than correction. In a systematic CRC, the message polynomial is shifted by r positions, divided by g(x), and the remainder is appended as the check field. Hardware implementation uses a linear-feedback shift register (LFSR), making CRCs fast and inexpensive.

Important CRC properties depend on the generator polynomial. If g(x) contains at least two nonzero terms, all single-bit errors are detected. If g(x) is divisible by x + 1, all odd-weight error patterns are detected. A generator of degree r detects all burst errors of length ≤ r, provided the usual nonzero-generator conditions hold. For longer bursts, the undetected fraction is often approximately 2^−r under a random-error assumption, but this is not a universal guarantee.

CRC is not encryption, authentication, or correction. An adversary who can modify data may deliberately create a valid CRC. Security-sensitive systems therefore require a cryptographic message authentication code or digital signature in addition to error detection.

5. Convolutional Codes and Trellis Decoding

Unlike a block code, a convolutional encoder processes a sequence continuously and produces output symbols dependent on current and previous input bits. A rate-1/2 encoder, for example, emits two coded bits for every input bit. Its memory creates a finite-state machine represented by a trellis.

The encoder is characterized by constraint length, generator sequences, and code rate. The free distance d_free is the smallest Hamming distance between distinct paths that diverge from and later remerge with the zero state. It plays a role analogous to minimum distance for long convolutional sequences.

The Viterbi algorithm performs maximum-likelihood sequence decoding for a convolutional code on a memoryless channel. It retains, for each state, only the path with the best accumulated metric. For hard decisions, the metric may be Hamming distance; for soft decisions, it is commonly an Euclidean or log-likelihood metric. Because inferior paths to the same state can never become better under additive future metrics, they may be discarded.

The computational complexity grows approximately with the number of states and trellis stages, not exponentially with the entire message length. This makes maximum-likelihood decoding practical for moderate constraint lengths. The trade-off is latency and memory, especially when traceback depth is increased to approach optimal performance.

6. Soft Decisions and Probabilistic Decoding

A hard-decision receiver converts each observation into 0 or 1 before decoding. A soft-decision receiver supplies reliability information, such as a log-likelihood ratio (LLR):

where y is the channel observation and x is the transmitted bit. The sign indicates the more likely bit, while the magnitude represents confidence. Soft decoding generally outperforms hard decoding because it preserves information discarded by thresholding.

For iterative codes, messages representing probabilities or LLRs are exchanged between a variable-node decoder and a check-node decoder. Turbo codes use constituent convolutional encoders and an interleaver. Low-density parity-check (LDPC) codes use sparse parity-check matrices and belief propagation. A factor graph or Tanner graph contains variable nodes for code bits and check nodes for parity constraints.

Belief propagation is exact on a cycle-free graph, but LDPC graphs contain cycles. With sufficiently long, well-designed codes, sparse graphs can nevertheless approach the Shannon limit under iterative decoding. Practical performance depends on block length, degree distribution, stopping criteria, quantization, scheduling, and channel estimation.

Polar codes use channel polarization: recursive transformations create synthesized bit channels that become relatively reliable or unreliable. Information bits are placed in reliable positions, while frozen bits occupy unreliable positions. Successive-cancellation list decoding improves finite-length performance. Polar codes and LDPC codes are both used in contemporary communication standards, with their selection depending on control/data channel requirements, block length, latency, and implementation architecture.

7. Interleaving, Burst Errors, and Hybrid ARQ

A code designed for independent errors may perform poorly when errors occur in bursts. An interleaver rearranges coded symbols before transmission, spreading a burst across several codewords. The deinterleaver reverses this operation at the receiver. Interleaving does not reduce the number of errors; it changes their distribution so that the decoder sees approximately independent errors. Its cost is latency and memory.

Forward error correction (FEC) corrects errors at the receiver without retransmission. Automatic repeat request (ARQ) detects errors and requests retransmission. Hybrid ARQ combines both: an initial coded transmission may be decoded immediately, while failed packets trigger retransmissions. Incremental redundancy sends additional parity information rather than repeating the complete packet. This can improve throughput over changing wireless channels, but it requires feedback, buffering, and protocol coordination.

The effective throughput of a coded system is influenced by code rate, packet error probability, retransmission probability, and overhead. A simplified goodput measure is

where G is useful information rate, R is code rate, P_e is packet-error probability, and R_s is the raw symbol or bit rate. This expression assumes a fixed packet-error model and no retransmission; systems using ARQ require a model including expected transmission count.

8. Code Design and Performance Evaluation

A coding scheme should not be selected solely by its nominal coding gain. Important criteria include:

Coding gain is commonly reported as the reduction in required E_b/N_0 for a fixed error-rate target relative to an uncoded system. Comparisons must use the same target error rate, modulation, channel model, receiver assumptions, information-bit energy convention, and bandwidth constraint.

The Shannon channel-capacity theorem gives a limit rather than a specific code. For a binary-input memoryless channel, capacity depends on the channel law. For an ideal band-limited AWGN channel with bandwidth B and received signal-to-noise ratio S/N, capacity is

where C is in bits per second if B is in hertz and S/N is dimensionless. Reliable communication with arbitrarily small error probability is theoretically possible when the information rate is below capacity, given sufficiently long codes and appropriate decoding. Real systems operate below this limit because of finite block length, complexity, channel uncertainty, power constraints, and latency.

9. Worked Design Example: Choosing a Code for a Telemetry Link

Consider an illustrative low-earth-orbit telemetry link sending 800 information bits per packet. The channel exhibits occasional fading-induced bursts, and retransmission is undesirable because the satellite pass is short. The engineering requirements are low packet-error probability, moderate decoding power, and bounded latency.

A simple parity bit adds negligible redundancy but detects only odd-weight errors and corrects none. A Hamming code can correct one error per block, but burst errors may place several errors in one block. A convolutional code with Viterbi decoding provides continuous operation and can be combined with interleaving, but traceback memory and decoder power increase. An LDPC or polar code can provide stronger performance, especially at moderate-to-long block lengths, but implementation complexity and short-block behavior must be evaluated.

A suitable architecture is a moderate-rate FEC code followed by a block interleaver. The interleaver depth is selected from the maximum tolerable latency and the expected burst length. The receiver computes soft reliability values from the demodulator, rather than passing hard bits to the decoder. A CRC is appended to the information payload so that the receiver can reject undetected decoder failures. If the link supports feedback, failed packets may use incremental-redundancy hybrid ARQ; otherwise, the system relies entirely on FEC.

The design should be validated using packet-error-rate simulations over AWGN and measured fading traces. Tests must include synchronization slips, quantization, oscillator errors, burst lengths, decoder iteration limits, and radiation-induced hardware faults where applicable. The final decision is not simply the code with the best waterfall curve; it is the code that meets reliability, latency, power, memory, and interoperability constraints together.

Learning points from the case

1. The channel error model determines whether interleaving is necessary.
2. Soft information can materially improve decoding performance.
3. CRC and FEC serve different purposes and are complementary.
4. Coding rate must be evaluated jointly with packet error probability and available bandwidth.
5. Real implementation constraints can dominate theoretical coding performance.

10. Limitations, Security, and Best Practices

No error-detecting code guarantees detection of every possible corruption. An error pattern that is a codeword difference can remain undetected. Decoder output can also be confidently wrong when the received word lies closer to an incorrect codeword or when the channel model is inaccurate.

Coding cannot compensate indefinitely for a channel below operational viability. Increasing redundancy may reduce useful throughput and increase energy consumption. Very long blocks improve asymptotic coding performance but create latency and are vulnerable to channel nonstationarity. Iterative decoders may exhibit an error floor caused by trapping sets, absorbing sets, stopping sets, or implementation imperfections.

Reliable engineering practice includes: specify the channel model; distinguish bit, symbol, frame, and packet error rates; use soft information where feasible; test both random and burst errors; verify generator and parity-check matrices independently; protect synchronization and framing; retain a CRC or equivalent integrity check; analyze finite-block performance; and document code rate, puncturing, shortening, interleaving, decoder mode, and energy normalization.

Error detection is not data security. CRCs detect accidental corruption but do not provide confidentiality, authentication, freshness, or protection against intentional modification. Safety-critical and infrastructure systems should separate communication reliability from security controls and apply authenticated integrity mechanisms where threats exist. Standards compliance is also important because two systems using nominally similar codes may differ in bit ordering, polynomial representation, puncturing, termination, or interleaver rules.

Contemporary Developments

Modern systems increasingly use adaptive modulation and coding, in which modulation order, code rate, block length, and retransmission strategy respond to channel-quality estimates. Massive multiple-input multiple-output systems combine coding with spatial processing, and joint detection-decoding algorithms exchange soft information between channel estimators, demodulators, and decoders.

Research continues on short-blocklength information theory, energy-efficient decoders, nonbinary LDPC codes, spatially coupled codes, neural-assisted decoding, and coding for semantic or task-oriented communication. Machine learning can help estimate channels, select code rates, or approximate decoding, but learned systems require rigorous validation, robustness analysis, explainability appropriate to the application, and protection against distribution shift. In safety-critical links, conventional certified algorithms may remain preferable even when learned methods show promising average performance.

Chapter Summary

Error detection and channel coding introduce controlled redundancy to improve the reliability of digital communication. Hamming distance determines the guaranteed detection and correction capabilities of a code: d_min − 1 errors can always be detected, while floor((d_min − 1)/2) errors can always be corrected. Linear block codes use generator and parity-check matrices; syndromes allow efficient error localization. Hamming codes provide single-error correction, while cyclic codes and CRCs provide efficient structured detection, especially for burst errors.

Convolutional codes use memory and trellis decoding, with the Viterbi algorithm providing maximum-likelihood sequence decoding under appropriate channel assumptions. Turbo, LDPC, and polar codes exploit iterative or structured decoding to approach information-theoretic limits. Soft decisions preserve reliability information and generally outperform hard decisions. Interleaving converts burst errors into a pattern more suitable for correction, while hybrid ARQ combines coding with retransmission.

Practical code selection must balance reliability, rate, bandwidth, complexity, power, latency, block length, and security requirements. CRC is an integrity check against accidental errors, not a security mechanism. Sound design therefore combines an accurate channel model, appropriate coding and decoding, implementation-aware simulation, and independent integrity protection.

Key Terms

Error detection: Determining whether a received sequence violates the rules of a code.

Error correction: Estimating and recovering the transmitted sequence despite errors.

Redundancy: Additional structured symbols added to information for reliability.

Code rate: Ratio k/n of information symbols to transmitted coded symbols.

Hamming weight: Number of nonzero symbols in a vector.

Hamming distance: Number of positions in which two equal-length vectors differ.

Minimum distance: Smallest distance between distinct codewords.

Syndrome: Vector s = Hr^T indicating parity-check outcomes.

Generator matrix: Matrix that maps information vectors to codewords.

Parity-check matrix: Matrix whose null space contains the valid codewords.

Linear block code: Code forming a vector subspace under field addition.

Cyclic code: Linear code closed under cyclic shifts.

CRC: Polynomial-based cyclic redundancy check used mainly for error detection.

Convolutional code: Code in which output depends on current and previous input symbols.

Trellis: State-transition representation used for convolutional encoding and decoding.

Viterbi algorithm: Dynamic-programming algorithm for maximum-likelihood trellis decoding.

Interleaver: Device that rearranges symbols to disperse burst errors.

Soft decision: Decoder input containing both a bit estimate and reliability information.

LDPC code: Sparse-parity-check code commonly decoded by belief propagation.

Hybrid ARQ: Combination of forward error correction and retransmission protocols.

Review Questions

Short Answer Questions

1. Define code rate and explain why lowering the rate can improve reliability.
2. What is the relationship between minimum Hamming distance and guaranteed error correction?
3. Explain the role of a syndrome in linear block-code decoding.
4. Why does interleaving help a code designed for random errors?
5. Distinguish a CRC from a cryptographic authentication code.

Long Answer Questions

1. Derive the detection and correction guarantees in terms of d_min, and explain the geometric interpretation using Hamming spheres.
2. Describe generator matrices, parity-check matrices, syndromes, and syndrome decoding for binary linear block codes.
3. Explain cyclic-code encoding using generator polynomials and discuss the burst-error properties of CRCs.
4. Compare convolutional, LDPC, turbo, and polar codes with respect to structure, decoding, performance, and implementation complexity.
5. Explain how code rate, soft decisions, interleaving, block length, and decoder complexity influence a practical communication-system design.

Analytical / Application Questions

1. A binary linear code has d_min = 7. Determine the maximum number of errors it is guaranteed to detect and the maximum number it is guaranteed to correct. Explain why these guarantees do not specify the complete error probability.
2. Design a telemetry-link coding architecture for a channel with burst errors, strict latency limits, and no retransmission path. Justify the code family, interleaver, integrity check, and receiver metric.
3. Compare two candidate systems: a rate-1/2 code with low-complexity hard decoding and a rate-3/4 code with high-complexity soft decoding. Identify the measurements and channel assumptions required before selecting one.

Multiple Choice Questions with Answers

Question 1

A binary code with minimum distance d_min = 5 is guaranteed to correct how many errors?

A. 1

B. 2

C. 3

D. 4

Correct Answer: B. 2

Question 2

For a linear block code, the syndrome of a received vector r is calculated as:

A. mG

B. rG^T

C. Hr^T

D. GH^T

Correct Answer: C. Hr^T

Question 3

The code rate of an (n, k) block code is:

A. n/k

B. k/n

C. n − k

D. k + n

Correct Answer: B. k/n

Question 4

Which technique primarily spreads burst errors across different coded symbols?

A. Interleaving

B. Threshold detection

C. Carrier recovery

D. Pulse shaping

Correct Answer: A. Interleaving

Question 5

The Viterbi algorithm is principally used for decoding:

A. Parity-only codes

B. Convolutional codes represented by a trellis

C. Cryptographic hashes

D. Analog filters

Correct Answer: B. Convolutional codes represented by a trellis

Question 6

A CRC is primarily intended to provide:

A. Confidentiality

B. Source compression

C. Error detection

D. Frequency synchronization

Correct Answer: C. Error detection

Question 7

For a code with d_min = 3, the guaranteed correction capability is:

A. Zero errors

B. One error

C. Two errors

D. Three errors

Correct Answer: B. One error

Question 8

Soft-decision decoding differs from hard-decision decoding because it uses:

A. Only the packet length

B. Reliability information from the channel observation

C. No redundancy

D. Only parity-bit positions

Correct Answer: B. Reliability information from the channel observation

Question 9

Which statement about a zero syndrome is correct?

A. It always proves that no error occurred.

B. It proves that the transmitted message was encrypted.

C. It indicates that the received vector satisfies all parity checks, although some errors may be undetected.

D. It means that every bit was inverted.

Correct Answer: C. It indicates that the received vector satisfies all parity checks, although some errors may be undetected.

Question 10

For the AWGN capacity expression C = B log₂(1 + S/N), S/N must be:

A. A dimensionless signal-to-noise power ratio

B. A quantity measured in hertz

C. A codeword length in bits

D. A Hamming distance

Correct Answer: A. A dimensionless signal-to-noise power ratio