JNTU B.Tech III Year ERROR CORRECTING CODES Previous Question Paper (February - 2022 - R18)

A linear systematic (n, k) block code encodes a message of length k into a codeword of length n, where the first k bits are the original message bits (information bits) and the remaining (n-k) bits are parity check bits. The encoding process is defined by the generator matrix G = [I_k | P], where I_k is the k x k identity matrix and P is the k x (n-k) parity matrix.

The encoding circuit is constructed based on the generator polynomial g(x) of the code. For a systematic code, the parity bits are computed by dividing the message polynomial m(x) multiplied by x^(n-k) by the generator polynomial g(x). The remainder of this division provides the parity bits.

The hardware implementation typically uses a linear feedback shift register (LFSR) circuit consisting of the following components:

• A shift register of length (n-k) stages, corresponding to the degree of the generator polynomial g(x).
• XOR gates placed at positions determined by the coefficients of g(x).
• An input switch that allows the k message bits to be shifted into the register while simultaneously being sent to the output.
• A control mechanism that stops the input after k clock cycles and then shifts out the contents of the register to append the parity bits to the message.

The encoding operation proceeds in two phases:

1. Message Transmission Phase: The k message bits are shifted into the encoder and transmitted directly to the output. Simultaneously, these bits are shifted through the LFSR to compute the remainder.
2. Parity Transmission Phase: After k cycles, the input switch disconnects the message source, and the (n-k) parity bits stored in the register are shifted out and appended to the message bits, completing the n-bit codeword.

This systematic structure ensures that the original message is preserved, simplifying the decoding process as the receiver only needs to compute the syndrome to detect or correct errors.