CYCLIC CODES
Cyclic codes are special linear block codes. In a cyclic
code, if a codeword is cyclically shifted (rotated), the
result is another codeword.
Example:- if 1011000 is a codeword and if it is cyclically
left shift, then 0110001 is generated and it is also a
another codeword.
Cyclic Redundancy Check(CRC):
CRC is one of the cyclic codes is used in networks
such as LANs and WANs.
Table 1 A CRC code with C(7, 4)
In the Encoder, the dataword has k bits and the codeword
has n bits. We need a CRC code with C(n,k) ie C(7,4)
Figure 1 CRC encoder and decoder
In the Encoder (Sender Side), the dataword has k bits and the
codeword has n bits. The size of the dataword is augumented by adding
n-k 0’s to the righthand side of the word. The n bit result is fed into the
generator. The generator uses a divisior of size n-k+1 , predefined and
agreed upon. The generator divides the augumented dataword by the
divisor(modulo 2 division). The quotient of the division is discarded and
the remainder (r2,r1,r0) is appended to the dataword to create the
codeword.
The Decoder (Receiver side) receives the possibly corrupted
codeword. 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 bits, which is fed to the decision logic analyzer. If the syndrome bits
all are 0s , the 4 leftmost bits of the codeword are accepted as the
dataword (no error). Otherwise the 4 bits are discarded (error)
Figure Division in CRC encoder
Figure Division in the CRC decoder for two cases
CHECKSUM
The last error detection method is called the
checksum.
The checksum is used in the Internet by several
protocols although it will implemented at the data link
layer.
Example 1
Suppose our data is a list of five 4-bit numbers that we
want to send to a destination. In addition to sending
these numbers, we send the sum of the numbers. For
example, if the set of numbers is (7, 11, 12, 0, 6), we send
(7, 11, 12, 0, 6, 36), where 36 is the sum of the original
numbers. The receiver adds the five numbers and
compares the result with the sum. If the two are the
same, the receiver assumes no error, accepts the five
numbers, and discards the sum. Otherwise, there is an
error somewhere and the data are not accepted.
Example 2
We can make the job of the receiver easier if we
send the negative (complement) of the sum, called the
checksum. In this case, we send (7, 11, 12, 0, 6, −36).
The receiver can add all the numbers received
(including the checksum). If the result is 0, it assumes
no error; otherwise, there is an error.
Example 3
How can we represent the number 21 in one’s
complement arithmetic using only four bits?
Solution
The number 21 in binary is 10101 (it needs five bits). We
can wrap the leftmost bit and add it to the four rightmost
bits. We have (0101 + 1) = 0110 or 6.
Figure Example 5
Traditionally, the internet has been using a 16 bit
checksum. So the sender/receiver calculates the
checksum by using the following steps.
Sender site:
1. The message is divided into 16-bit words.
2. The value of the checksum word is set to 0.
3. All words including the checksum are
added using one’s complement addition.
4. The sum is complemented and becomes the
checksum.
5. The checksum is sent with the data.
Note
Receiver site:
1. The message (including checksum) is
divided into 16-bit words.
2. All words are added using one’s
complement addition.
3. The sum is complemented and becomes the
new checksum.
4. If the value of checksum is 0, the message
is accepted; otherwise, it is rejected.
Example 6
Let us calculate the checksum for a text of 8 characters
(“Forouzan”). The text needs to be divided into 2-byte (16-
bit) words. We use ASCII (see Appendix A) to change
each byte to a 2-digit hexadecimal number. For example,
F is represented as 46 and o is represented as 6F. Figure
shows how the checksum is calculated at the sender and
receiver sites. In part a of the figure, the value of partial
sum for the first column is 36. We keep the rightmost digit
(6) and insert the leftmost digit (3) as the carry in the
second column. The process is repeated for each column.
Note that if there is any corruption, the checksum
recalculated by the receiver is not all 0s.
Figure Example 6
