Linear Block Codes

LINEAR BLOCK CODES.

Error-Control Coding

Error-control coding techniques are used to detect and/or correct errors that occur in the message transmission in a digital communication system. The transmitting side of the error-control coding adds redundant bits or symbols to the original information signal sequence. The receiving side of the error-control coding uses these redundant bits or symbols to detect and/or correct the errors that occurred during transmission. The transmission coding process is known as encoding, and the receiving coding process is known as decoding.

There are two major classes in error-control code: block and convolutional. In block coding, successive blocks of K information (message) symbols are formed.

The coding algorithm then transforms each block into a codeword consisting of n symbols where n>k. This structure is called an (n,k) code. The ratiok/n is called the code rate. A key point is that each codeword is formed independently from other codewords.

An error-control code is a linear code if the transmitted signals are a linear function of the information symbols. The code is called a systematic code if the information symbols are transmitted without being altered. Most block codes are systematic, whereas most convolutional codes are nonsystematic.

Almost all codes used for error control are linear. The symbols in a code can be either binary or non-binary. Binary symbols are the familiar '0' and '1'.

Linear Block Codes

Linear block coding is a generic coding method. Other coding methods, such as Hamming and BCH codes, are special cases of linear block coding. The codeword vector of a linear block code is a linear mapping of the message vector. The codeword x and the message m have the relationship

x =mG

where G is a K-by-N matrix and is known as the generator matrix.

Linear block code is called a systematic linear code if the generator matrix has the form

G =[P Ik ]

where P is an (n-k)-by-k matrix and Ik is a k-by-k identity matrix. A systematic linear code renders a length k message into a length n codeword where the last k bits are exactly the original message and the first (n-k) bits are redundant. These redundant bits serve as parity-check digits.