Q10Digital Communication

(a) Error Detecting and Correcting Capabilities of Convolutional Codes

Convolutional codes differ fundamentally from block codes (such as the Hamming and cyclic codes discussed elsewhere in this paper) in that they encode a continuous stream of input bits using a shift-register-based encoder with memory, where each output bit depends not only on the current input bit but also on a fixed number of previous input bits (determined by the encoder's constraint length K) — rather than encoding fixed-size, independent blocks of k message bits into n code word bits at a time, a convolutional encoder continuously processes the incoming bit stream, producing a continuous stream of output code bits whose value at any point depends on a 'sliding window' of recent input history.

Error correction mechanism: the error-correcting capability of a convolutional code is characterized by its free distance, dfree — the minimum Hamming distance between any two distinct possible encoded output sequences that the encoder could produce (analogous to the minimum distance dmin of a block code, but defined over the code's full, sequence-based structure rather than fixed-length code words). A convolutional code with free distance dfree can, in principle, correct up to ⌊(dfree-1)/2⌋ errors within any sufficiently localized error pattern (though the precise correction capability in practice is dependent on the specific error pattern and its distribution relative to the decoding algorithm used, rather than a simple fixed guarantee as in block codes).

Viterbi decoding: convolutional codes are most commonly decoded using the Viterbi algorithm, a dynamic-programming-based maximum-likelihood sequence estimation technique that efficiently searches through the encoder's state trellis (a graphical representation of all possible encoder state transitions over time) to find the most likely transmitted sequence given the actual received (possibly error-corrupted) sequence, without needing to exhaustively examine every possible transmitted sequence individually — the Viterbi algorithm's computational complexity grows only linearly with the sequence length (rather than exponentially, as a brute-force search would), making it practically feasible to decode convolutional codes over arbitrarily long data sequences.

Comparative characteristics: convolutional codes generally provide strong error-correction performance particularly well-suited to channels exhibiting continuously-distributed or randomly-scattered bit errors (such as typical additive-white-Gaussian-noise-dominated channels), and are widely used in combination with interleaving (to help spread out any bursty error clusters into a more randomly-distributed pattern better suited to the convolutional decoder's typical error-correction assumptions) in practical systems such as satellite communication, digital cellular telephony, and deep-space communication links; they are frequently used in concatenation with an outer block code (such as a Reed-Solomon code) in a combined coding scheme, exploiting the convolutional code's strength at correcting the more common, moderate-density random errors while relying on the outer block code to clean up any remaining occasional error bursts that exceed the convolutional decoder's own correction capability.

(b) (7,4) Cyclic Code with g(x) = 1+x+x³

Given: a (7,4) cyclic code (n=7 code word bits, k=4 message bits, hence n-k=3 parity check bits) with generator polynomial g(x) = 1+x+x³.

Step 1 — Non-systematic generator matrix: the k=4 rows of a basic (non-systematic) generator matrix for this cyclic code are formed by taking g(x) and its shifted versions x·g(x), x²·g(x), x³·g(x) (each padded to the full n=7-bit code word length):

Step 2 — Convert to systematic form [I₄|P]: applying Gaussian elimination (row operations, modulo 2) to reduce the first 4 columns of Gnonsys to the identity matrix I₄ (eliminating the off-diagonal 1s in the leading 4×4 block through successive row XOR operations):

Verification: each row of this systematic G was independently verified, by direct polynomial long division (modulo 2) against g(x)=1+x+x³, to have a zero remainder — confirming each row genuinely represents a valid code word of this cyclic code, as required for a correct generator matrix.

Step 3 — Encode the message d=(1,0,1,0): the code word is computed as c = d·G:

Result: the code word for message d=(1,0,1,0) is 1010001.

Interpretation: since G is in systematic form [I₄|P], the first 4 bits of the resulting code word (1010) directly reproduce the original message bits unchanged, while the last 3 bits (001) are the computed parity-check bits appended by the encoder — this systematic structure is a highly convenient practical property, since it allows the original message to be directly read off from the beginning of the received code word without needing to perform any decoding computation at all in the error-free case, with the appended parity bits used only when error detection/correction processing is actually required (via syndrome computation using the corresponding parity-check matrix H, derivable from this G exactly as demonstrated in the preceding Hamming code question).

Verification via Direct Polynomial Division

It is useful to verify the codeword 1010001 directly by polynomial methods, since cyclic codes are, by definition, most naturally described and manipulated via their polynomial representation rather than purely by matrix multiplication. The message d=(1,0,1,0) corresponds to the message polynomial d(x)=1+x², so a systematic cyclic encoding is obtained by first forming x^(n-k)d(x)=x³(1+x²)=x³+x⁵ (shifting the message into the upper n-k=3 bit positions of the codeword), then dividing by g(x)=1+x+x³ to obtain the remainder p(x), and finally setting the codeword polynomial c(x)=x³d(x)+p(x). Performing this division of x⁵+x³ by 1+x+x³ modulo 2 yields a remainder p(x)=1 (i.e., p=(1,0,0) in coefficient form for x⁰,x¹,x²), so the full codeword polynomial is c(x)=x⁵+x³+1, corresponding to coefficient vector (1,0,1,0,0,0,1) for (x⁰,x¹,...,x⁶) — matching exactly the 1010001 result obtained via the matrix-multiplication route above (reading the vector left to right as c0c1c2c3c4c5c6), confirming both methods agree.

Relating Cyclic Codes to Hamming Codes

This (7,4) cyclic code is, in fact, algebraically identical to the standard (7,4) Hamming code discussed in the preceding question — both are (7,4) linear block codes with minimum distance dmin=3, and it can be shown that the (7,4) Hamming code can always be represented as a cyclic code for a suitable choice of generator polynomial (here, g(x)=1+x+x³, an irreducible primitive polynomial of degree 3 over GF(2)) — this is a specific instance of the more general and practically important fact that essentially all commonly used Hamming codes admit an equivalent cyclic-code representation, and cyclic codes are generally preferred in practical hardware implementations because their encoding and syndrome-decoding operations can be efficiently realized using simple linear-feedback shift-register (LFSR) circuits performing polynomial division, rather than requiring general-purpose matrix-multiplication hardware — this is precisely the practical motivation for studying and using the cyclic-code formulation (generator polynomial g(x), as in this problem) as an alternative, hardware-efficient representation of the same underlying error-correcting code structure introduced via the parity-check-matrix approach in the preceding question.

Cyclic Property and Error-Detection Implications

A further practically important property of cyclic codes, not shared in general by arbitrary linear block codes, is that any cyclic shift of a valid codeword is itself also a valid codeword of the same code (the property from which the name 'cyclic' derives) — this structural property is what enables cyclic codes to be efficiently implemented and syndrome-checked using a single fixed-length LFSR that processes the received bit stream serially, and it is also the property exploited by Cyclic Redundancy Check (CRC) error-detection codes (a close practical relative of the error-correcting cyclic codes discussed here) that are ubiquitous in networking and storage systems (Ethernet frame checks, storage-block checksums, etc.) for fast, hardware-efficient burst-error detection, even though CRC codes are typically used purely for error detection (with retransmission on failure) rather than for the explicit single-error correction capability demonstrated for this (7,4) cyclic code and its equivalent Hamming-code representation.