4.5.5 Linear Block Code Generation

In principle, block codes can be generated using orthogonal signal sets, which are decoded by correlators (or matched filters). However, for codes with a large number of codewords, this method becomes impractical: each codeword requires a distinct signal and thus a corresponding correlator. The resulting receiver complexity increases exponentially with code length. Similarly, while block codes can be generated and decoded using lookup tables, the sheer number of codewords in practical codes makes this computationally prohibitive.

A far more efficient approach employs algebraic linear codes, which can be generated and decoded using matrix operations rather than exhaustive search. In a linear code, codewords form a vector space over a finite field (typically GF(2)—see Appendix F), meaning that the set of codewords is closed under addition and scalar multiplication. In other words, the modulo-2 sum of any two codewords—or the scalar multiplication of a codeword by 0 or 1—produces another valid codeword.

The original data word can be represented as a k-bit vector:

D = [d_{1}, d_{2}, d_{3}, \dots d_{k}]

(4.15)

A codeword C is created by multiplying the data vector by a generator matrix, G:

C = D G

(4.16)

The elements of the generator matrix are fixed and known to both the transmitter and receiver.

Figure 4.12 shows the sixteen possible codewords for the (7,4) linear block code generated using the matrix:

G = [\begin{matrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{matrix}]

(4.17)

The codewords in Figure 4.12 are systematic, meaning the original data bits appear unchanged at the start of the transmitted word, followed by parity bits. This (7,4) Hamming code has a minimum distance of d_min=3, allowing detection of up to two errors and correction of one.