Cyclic codes in Error Detection and Correction
Cyclic codes are special linear block codes with one extra property. In a cyclic code, if a code word is cyclically shifted (rotated), the result is another code word. For example, if 1011000 is a code word and we cyclically left-shift, then 0110001 is also a code word.
In this case, if we call the bits in the first word a0 to a6 and the bits in the second word b0 to b6, we can shift the bits by using the following:
b1=a0 b2=a1 b3=a2 b4=a3 b5=a4 b6=a5 b0=a6
Cyclic Redundancy Check:
One of the categories of cyclic codes called the cyclic redundancy check (CRC) that is used in networks such as LANs and WANs.
You May Also Like:
Types of Errors
Important Concepts in Error Detection and Correction
Block Coding Techniques
Hamming Distance
The following table shows an example of a CRC code which shows both the linear and cyclic properties of this code.
In the encoder, the data word has k bits (4 here); the code word has n bits (7 here). The size of the data word is augmented by adding n - k (3 here) 0s to the right-hand side of the word. The n-bit result is fed into the generator.
The generator uses a divisor of size n - k + I (4 here), predefined and agreed upon. The generator divides the augmented Data word by the divisor (modulo-2 division). The quotient of the division is discarded; the remainder (r2r1r0) is appended to the data word to create the code word.
The decoder receives the possibly corrupted code word. A copy of all n bits is fed to the checker which is a replica of the generator. The remainder produced by the checker is a syndrome of n - k (3 here) bits, which is fed to the decision logic analyzer.
The analyzer has a simple function. If the syndrome bits are all 0s, the 4 leftmost bits of the code word are accepted as the data word (interpreted as no error); otherwise, the 4 bits are discarded (error).
Encoder:
For example, consider the following figure where the encoder takes the data word and augments it with n - k number of 0s. It then divides the augmented data word by the divisor, as shown in Figure.
The process of modulo-2 binary division is the same as the familiar division process for decimal numbers. In each step, a copy of the divisor is XORed with the 4 bits of the dividend. The result of the XOR operation (remainder) is 3 bits (in this case), which is used for the next step after 1 extra bit is pulled down to make it 4 bits long. There is one important point we need to remember in this type of division. If the leftmost bit of the dividend (or the part used in each step) is 0, the step cannot use the regular divisor; we need to use an all-0s divisor.
When there are no bits left to pull down, we have a result. The 3-bit remainder forms the check bits (r2, r1 and r0). They are appended to the data word to create the code word.
Decoder:
The code word can change during transmission. The decoder does the same division process as the encoder. The remainder of the division is the syndrome. If the syndrome is all 0s, there is no error; the data word is separated from the received code word and accepted. Otherwise, everything is discarded. Consider the following figure which shows two cases: The left hand figure shows the value of syndrome when no error has occurred; the syndrome is 000. The right-hand part of the figure shows the case in which there is one single error. The syndrome is not all 0s (it is 011).
Advantages of Cyclic Codes:
The cyclic codes have a very good performance in detecting single-bit errors, double errors, an odd number of errors, and burst errors. They can easily be implemented in hardware and software. They are especially fast when implemented in hardware. This has made cyclic codes a good candidate for many networks.
You May Also Like:
Simple Parity Check Code
Hamming Codes
Checksum
Back to DCN Questions and Answers
