Principles of Linear Block Codes

LINEAR BLOCK CODES

The (n, k) notation describes a family of parity check codes known as block codes. Forward error correction codes are implemented using block codes. Linear Block Codes are defined as block codes that have the property of linearity. Modulo-2 addition of any two codewords produces another acceptable codeword in a linear code. Linear Block codes can be used in several ways such as:

1. Hamming Codes

2. Cyclic Codes

3. BCH Codes

4. Golay Codes

5. Reed-Solomon codes

• Systematic linear block codes are linear block codes in which the superfluous bits are introduced in such a way that the message bits appear first, followed by the redundant bits.

• Non-systematic linear block codes are linear block codes in which superfluous bits are inserted in such a way that it is impossible to distinguish between message bits and redundant bits.

Principles of linear block codes

The functional diagram of a channel encoder for producing systematic linear block codes is shown in Figure 1.

Figure 1: Functional diagram of block coder

• A block of 'k' message bits is created from the incoming binary data sequence. As a result, each message block may be thought of as a message vector 'M'.

M = (m1 m2 …… mk) ---------------------- (1)

• Each block of message input is given (n-k) check bits (redundant bits) by the channel encoder. Allow n–k = q. According to the encoding rule, the 'q' check bits are calculated from the message bits. The check bits vector 'c' is then used.

C = (c1 c2 ….. cq) ---------- (2)

• In the encoder, 'q' check bits are inserted for each block of 'k' message bits. As a result, the codeword generated at the encoder's output has a total bit length of k + q = n. As a result, such codes are known as (n, k) linear block codes.

• At the encoder's output, the code vector 'X' is

X = (m1 m2 ……. mk c1 c2 ……. cq) = (M C) -------------- (3)

Here M is of order 1 x k

C is of order 1 x q, where q = n – k

and X is of order 1 x n

• Let G denote the k x n generator matrix used by the encoder to produce check bits.  The output code vector is given as:

X = M . G

This may be expressed as a matrix as

[𝑋]1 x 𝑛 = [𝑀]1 x 𝑘.[𝐺]𝑘 x 𝑛 --------------- (4)

• The generator matrix is determined by the linear block code type. It is generally shown as

[𝐺]𝑘 x 𝑛 = [𝐼𝑘 x 𝑘 𝑃𝑘 x 𝑞]𝑘 x 𝑛 -------------------- (5)

Where 𝐼𝑘 x 𝑘 = k x k Identity matrix given by

and 𝑃𝑘 x 𝑞 = k x q submatrix or coefficient matrix.

𝑃𝑘 x 𝑞 is given by

--------------- (6)

• The check bits vector may be obtained from this submatrix.

The check bits vector, [𝐶]1 x 𝑞 = [𝑀]1 x 𝑘 . [𝑃]𝑘 x 𝑞 -------------- (7)

• When we substitute the matrix form, we get

---------------------------- (8)

• The check bits vector may be obtained by solving the given matrix equation. The check bits are:

c1 = m1p11 Ꚛ m2 p21 Ꚛ …… Ꚛmk pk1

c2 = m1p12 Ꚛ m2 p22 Ꚛ ……  Ꚛ mk pk2 --------------- (9)

cq = m1p1q Ꚛ m2 p2q Ꚛ …… Ꚛ mkpkq

Here all the additions are mod-2 addition.

Sreejith Hrishikesan

Sreejith Hrishikesan is a ME post graduate and has been worked as an Assistant Professor in Electronics Department in KMP College of Engineering, Ernakulam. For Assignments and Projects, Whatsapp on 8289838099.

Post a Comment

Previous Post Next Post