Binary Cyclic Codes

Binary Cyclic Codes

A subtype of linear block codes is binary cyclic codes. They have a lot of important features. Errors caused by bursts of noise that influence multiple consecutive bits can be corrected using cyclic codes. Cyclic codes include Hamming, BCH, and Golay codes, all of which are excellent block codes.

If every cyclic shift of the code vector creates another code vector, the linear block code is said to be cyclic.

The characteristics of a cyclic code are as follows.

(i) Linearity Property: If the modulo-2 sum of any two codewords produces another acceptable codeword, the code is said to be linear.

(ii) Cyclic Property: If every cyclic shift of a codeword yields another acceptable code word, the code is said to be cyclic. Consider the n-bit codeword X = (xn-1, xn-2, ….. x1, x0) as an example.

When we cyclically shift the above code word to the left side by one bit, the resultant code word is

X’ = (xn-2, xn-3, ….. x1, x0, xn-1)

X' is also a suitable code word in this case. Another valid code vector X" is produced by one additional cyclic left shift.

X’’ = (xn-3, xn-4, ….. x1, x0, xn-1, xn-2)

Representation of codewords by a polynomial

• The cyclic property indicates that the elements of a codeword of length n can be treated as the coefficients of a degree polynomial (n-1).

• Consider the n-bit codeword,

X = (xn-1, xn-2, ….. x1, x0) ------------------- (1)

This code word may be expressed as a code word polynomial, as shown below:

X (p) = xn-1pn-1 + xn-2pn-2 + ….. + x1p + x0 ------------------ (2)

X (p) denotes the degree polynomial (n-1).

The variable p can be any real number. The coefficients are either 1s or 0s in binary codes.

The location of the codeword bits is represented by the 'p' power. pn-1 stands for MSB whereas p0 stands for LSB.

• In the polynomial X(p), each power of p represents a one-bit cyclic shift in time. As a result, multiplication of the polynomial X(p) by p can be regarded as a cyclic shift or rotation to the right, as long as pn = 1.

• We employ polynomial representation to express cyclic codes for the following reasons.

1. Algebraic codes are what they are. As a result, algebraic operations like addition, subtraction, multiplication, and division become exceedingly straightforward.

2. In a polynomial, the positions of the bits are represented by powers of p.

Generation of code vectors in the non-systematic form of cyclic codes

• Let M = (mk-1, mk-2, …… m1, m0) be ‘k’ bits of message vector. Then it can be represented by the polynomial as,

M(p) = mk-1pk-1 + mk-2pk-2 + ……+ m1p + m0 ------------- (3)

• The codeword polynomial X(P) is given as

X (P) = M(P) . G(P) (3.16)

where G(P) is called as the generating polynomial of degree ‘q’ (parity or check bits q = n – k). The generating polynomial is given as

G (P) = pq + gq-1pq-1+ …….. + g1p + 1 ------------------ (4)

Here gq-1, gq-2 ….. g1 are the parity bits.

• If M1, M2, M3, …… etc. are the other message vectors, then the corresponding code vectors can be calculated as,

X1 (P) = M1 (P) G (P) -------------- (5)

X2 (P) = M2 (P) G (P)

X3 (P) = M3 (P) G (P) and so on

• All the above code vectors X1, X2, X3 ….. are in non-systematic form and they satisfy the cyclic property.

Generation of code vectors in the systematic form of cyclic codes

• The code word for the systematic form of cyclic codes is given by

X = (k message bits q check bits)

=> X = (mk-1 mk-2 …….. m1 m0 cq-1 cq-2 ….. c1 c0) --------------- (6)

• In polynomial form, the check bits vector can be written as

C(p) = cq-1pq-1 + cq-2pq-2 + …….. + c1p + c0 ------------- (7)

• In systematic form, the check bits vector polynomial is obtained by

C(p) = rem[๐‘๐‘ž.๐‘€(๐‘)/๐บ(๐‘)] ------------------- (8)

where M(p) is message polynomial

G(p) is generating polynomial

‘rem’ is the remainder of the division

Advantages of Cyclic Codes

• Cyclic codes have an excellent mathematical structure and can repair burst mistakes that span several subsequent bits. This enables the creation of error-correcting codes that can repair numerous errors quite simply.

• Cyclic codes' encoding and decoding circuits can be readily constructed using shift registers; cyclic codes' error-correcting and decoding procedures are simpler and easier to build. These solutions remove the requirement for huge amounts of storage (memory) for lookup table decoding. As a result, the codes become more strong and more effective.

Disadvantages of cyclic codes

• Even though error detection is easier, error rectification is significantly more difficult. This is owing to the complexity of the error-correcting combinational logic circuit.

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