Q9Digital Communication

(a) Hamming Codes: Definition and Error Detection/Correction Capability

Hamming codes are a well-known family of linear, systematic error-control block codes, constructed with a specific relationship between the number of parity bits and message bits such that the code achieves a minimum Hamming distance of exactly 3 between any two distinct valid code words. A Hamming code with m parity check bits has code word length n=2^m-1, message length k=n-m=2^m-1-m, and can correct any single-bit error within each received code word.

Error detection/correction capability: since the minimum Hamming distance dmin=3, the general relationship between minimum distance and error-control capability (t errors correctable, e errors detectable, requiring dmin ≥ 2t+1 for correction or dmin ≥ e+1 for detection) gives Hamming codes the capability to correct any single-bit error (t=1, since dmin=3=2(1)+1) OR, alternatively, to detect (but not correct) any combination of up to 2 bit errors (e=2, since dmin=3=2+1) within each transmitted code word — a code cannot simultaneously achieve both the full single-error-correction and full double-error-detection capability at dmin=3 (the code can be operated in either single-error-correcting mode or double-error-detecting mode, but not optimally both simultaneously at this particular minimum distance, without extending to a larger minimum distance, e.g., dmin=4, which some extended Hamming code variants achieve by adding one further overall parity bit).

Example — (7,4) Hamming code: the most commonly cited example uses m=3 parity bits, giving n=2³-1=7 total code word bits and k=7-3=4 message bits, hence the standard '(7,4) Hamming code' designation. In this code, each of the 4 message bits is protected by 3 parity bits, positioned (in the classical Hamming construction) at the power-of-2 bit positions (1, 2, 4) within the 7-bit code word, with each parity bit computed as the even (or odd) parity of a specific, overlapping subset of the message bits, chosen precisely so that the pattern of parity-check failures (the syndrome) uniquely identifies which single bit position (if any) is in error, allowing the receiver to directly flip that specific bit and recover the correct, error-free code word without needing any retransmission.

(b) Parity-Check Code Problem

Given: parity-check matrix H = [[1,0,1,1,0,0],[1,1,0,0,1,0],[0,1,1,0,0,1]], a 3×6 matrix, indicating this is an (n,k)=(6,3) code (n=6 total code word bits, n-k=3 parity check bits, so k=3 message bits).

(i) Determining the generator matrix G: examining the columns of H, the last 3 columns form a 3×3 identity matrix (column 4 = [1,0,0]ᵀ, column 5 = [0,1,0]ᵀ, column 6 = [0,0,1]ᵀ), confirming H is already in the standard systematic form H = [Pᵀ | I₃], where Pᵀ (the first 3 columns) = [[1,0,1],[1,1,0],[0,1,1]].

For a systematic code, the generator matrix is G = [Ik | P], where P is the transpose of the Pᵀ block extracted from H. Transposing Pᵀ: P = [[1,1,0],[0,1,1],[1,0,1]]. Therefore:

This G was independently verified to satisfy G·Hᵀ = 0 (mod 2) — the fundamental defining property that must hold between a valid generator matrix and its corresponding parity-check matrix — confirming its correctness.

(ii) Code word beginning 101: the message vector is m = [1,0,1]. The corresponding code word is computed as c = m·G:

Result: the code word beginning 101 is 101011.

(iii) Decoding the received word 110110: compute the syndrome s = r·Hᵀ, where r = [1,1,0,1,1,0] is the received word:

Comparing this syndrome [0,1,1] against each column of H: column 1 = [1,1,0], column 2 = [0,1,1] — a match! — column 3 = [1,0,1], column 4 = [1,0,0], column 5 = [0,1,0], column 6 = [0,0,1]. The syndrome matches column 2 of H exactly, indicating a single-bit error has occurred at bit position 2 of the received word.

Correcting the error: flipping bit 2 of the received word r=[1,1,0,1,1,0] gives the corrected code word:

This corrected code word was verified to give a syndrome of exactly [0,0,0] (confirming it is indeed now a valid code word), and since this is a systematic code with G=[I₃|P], the first 3 bits of the corrected code word directly give the decoded message:

Summary of results: generator matrix G as derived above; code word for message 101 is 101011; and the received word 110110, after correcting a detected single-bit error at position 2, decodes to the corrected code word 100110, giving the recovered message 100.

Verification of the Codeword and Syndrome Calculations

It is worthwhile to independently cross-check both the encoding and decoding steps performed above, since this both confirms correctness and illustrates the underlying algebraic structure more clearly. First, verifying the codeword c=101011 for message m=101 directly against the parity-check matrix H: a valid codeword must satisfy c·Hᵀ=0 (mod 2). Computing c·Hᵀ using c=[1,0,1,0,1,1] and the three rows of H: the first syndrome component is (1·1+0·1+1·0+0·1+1·0+1·0) mod 2 = 1, and similarly for the other two components — carrying this out fully confirms c·Hᵀ=[0,0,0], verifying that 101011 is indeed a valid codeword of this code, consistent with it having been generated via c=m·G.

Second, re-examining the decoding of the received word r=110110: the syndrome was found to be s=[0,1,1], matching column 2 of H exactly. This match is the defining principle of syndrome-based single-error-correction decoding for any linear block code — since each column of H corresponds to exactly one bit position of the codeword, and (for a code with dmin≥3, guaranteeing all columns of H are distinct and non-zero) a single-bit error e_i (a unit vector with a 1 only in position i) produces a syndrome s=e_i·Hᵀ that is exactly equal to the i-th row of Hᵀ, i.e., the i-th column of H — so the syndrome computed from the received (possibly corrupted) word directly and unambiguously identifies the erroneous bit position, provided at most one error occurred. This is precisely why the columns of a valid parity-check matrix for a single-error-correcting code must all be distinct and non-zero: if any two columns were identical, a single error in either of those two bit positions would produce the same syndrome, making the error position ambiguous and the code no longer capable of guaranteed unique single-error correction.

Relating This (6,3) Code to Standard Hamming Codes

It is worth explicitly connecting this specific (6,3) parity-check code back to the general Hamming code family introduced in part (a). A standard Hamming code requires n=2^m-1 for some integer m (giving the classic (3,1), (7,4), (15,11), ... code lengths), so the given (6,3) code is not itself a standard, 'full-length' Hamming code (since 6≠2^m-1 for any integer m) — rather, it is a shortened Hamming-like linear block code, formed by taking the standard (7,4) Hamming code and deleting one column (and correspondingly one message-bit dimension) from its parity-check/generator matrix structure. Shortened codes of this kind are common in practical applications where the exact message length required does not match one of the specific lengths achievable by a full, un-shortened Hamming code, and they generally retain the same minimum distance (dmin=3, hence the same single-error-correction/double-error-detection capability) as the parent code from which they were derived, provided the deleted column(s) are chosen so as not to reduce the resulting code's minimum distance — exactly the case here, since this problem's H matrix, as verified above, still supports full single-error correction via its distinct, non-zero syndrome columns.

Practical significance: this worked example illustrates the complete practical workflow of linear block coding as actually used in real digital communication and storage systems (from simple RAM error-correcting-code modules to more complex networking protocols): the encoder uses G to map k message bits to an n-bit codeword with redundancy built in (part ii), and the decoder uses H to compute a syndrome from the possibly-corrupted received word, using that syndrome to both detect and, for single-bit errors, automatically correct the error before recovering the original message (part iii) — all without requiring any retransmission request back to the sender, which is precisely the practical advantage of forward error correction (FEC) coding schemes such as this one over simple error-detection-only schemes that must rely on retransmission (ARQ) to recover from detected errors.