Syndrome Decoding for the Cyclic Codes , Syndrome Calculator for the Systematic Cyclic Codes

Difference between Source Coding, Line Coding and Error Detection Codes
We have discussed various sources coding techniques such as PCM, Delta modulation, ADM etc. Source coding techniques are used just to convert an analog signal to its digitally coded equivalent signal. Infact, the output of a source coder is a train of binary digits i.e., 0s and 1s.
The line coding techniques convert the stream of binary digits into a format or code which is more suitable for transmission over a cable or any other medium. This is because the data transmission must satisfy certain requirements such as synchronization, elimination of dc component, low crosstalk etc. The line code format must be such that the bandwidth requirements be as low as possible. Examples of line codes are RZ, NRZ AMI, Manchester and other formats.
The error detection code words consist of two blocks. One block consists of the message bits and the other one consists of check bits or parity bits. Error detection and correction both will be possible at the receivers, which is not possible with the source coding or line coding. As we have already discussed, examples of error codes are Hamming codes, cyclic codes etc. The parity bits are related to message bits in a particular way.
10.14.9. Syndrome Decoding for the Cyclic Codes
            When a code word X is transmitted over a noisy channel, errors are likely to get introduced into it. Thus, the received code word Y is different from X.
For a linear block code, the first step in decoding is to calculate the syndrome for the received code word. If the syndrome is zero, then there are no transmission errors in the received code word. But, if the syndrome is non-zero, then received code word contains transmission errors which requires correction.
In case of a cyclic code, in the systematic form, the syndrome can be calculated easily. Let the received code word be a polynomial of degree (n – 1) or less. Let it be given by,
y(p) = y₀ + y₁ (p) + … + y_n-1 p^n-1                                             …(10.45)
Now, we divide y(p) by the generator polynomial G(p). Let Q(p) represent the quotient polynomial and R(p) be the remainder polynomial.
Therefore,                     = Q(p) +                                                              …(10.46)
y(p) = Q(p) . G(p) + R(p)                                                  …(10.47)
The remainder R(p) is a polynomial with degree (n – k – 1) or less. It is called as the syndrome polynomial. The coefficients of the syndrome polynomial will make up the (n – k) by 1 syndrome S.
Thus, syndrome polynomial S(p) = Remainder of .
When the syndrome polynomial S(p) is non-zero, the presence of errors in the received code word is detected.
10.14.10. Syndrome Calculator for the Systematic Cyclic Codes
            Figure 10.39 shows the syndrome calculator, that is identical to the encoder for the (n, k) cyclic code. The only difference between these two is that, here the received bits are fed into the (n – k) stages of the feedback shift register from the left. Initially, the output switch is connected to position 1 and all the flip-flops are in their Reset mode. As soon, as all the received bits are shifted into the shift register, its contents will define the desired syndrome S. Once, we know the syndrome 5, we can determine the corresponding error pattern E and then make the appropriate corrections. After shifting all the incoming bits of signal Y, the output switch is transferred to position 2 and clock pulses are applied to the shift register to out the syndrome. The following example will make the concept of syndrome calculation obvious.
diagram
FIGURE 10.39 Syndrome calculator for an (n, k) cyclic code.
EXAMPLE 10.26. Design a syndrome calculator for a (7, 4) Hamming code, generated by the generator polynomial G(p) = 1 + p + p³, if the transmitted and received code words are given by,
            Transmitted code word,  X = (0 1 1 1 0 0 1)
            Received code word Y = (0 1 1  0 0 1)
                                                                   Error
Solution : The given generator polynomial is
G(p) = p³ + 0 p² + p + 1                                                          …(i)
We know that the general form of generator polynomial is as under :
G(p) = p³ + g₂ p² + g₁ p + 1                                         …(ii)
Comparing equations (i) and (ii), we obtain
g₂ = 0
g₁ = 1
Therefore, the required syndrome calculator is shown in figure 10.40.
diagram
FIGURE 10.40 Syndrome calculator for the (7, 4) cyclic code generated by the polynomial G(p) = 1 + p + p³
EXAMPLE 10.27. Determine the syndrome for the received code word Y = (0 1 1 0 0 0 1) if the transmitted code word is X = (0 1 1 1 0 0 1), using the syndrome calculator of previous example.
Solution : The output switch of figure 10.40 will be initially in position 1. It will remain in this position until all the 7 bits of the received signal Y are shifted into register.
After that the output switch is switched to position 2. The clock pulses are then applied to the shift register to output the syndrome vector S.
Table 10.14 explains the process of syndrome generation for the received code word.
Table 10.14. Contents of the syndrome calculator
for the received word 0 1 1 0 0 0 1
 

 
At the end of the seventh shift, the contents of the shift register (shaded row in Table 10.14) represent the syndrome (0 1 1) corresponding to the received code word Y = (0 1 1 0 0 0 1)
Since the syndrome is non-zero, the received word is in error. From table 10.14, we can see that the error pattern corresponding to syndrome (0 1 1) is 0 0 0 ① 0 0 0.
The encircled one indicates that the fourth bit of the received word is in error which is indeed the case in this problem.
10.14.11. Decoder for Cyclic Codes
As discussed earlier, once we calculate the syndrome, an error pattern E is detected corresponding to this syndrome.
diagram
FIGURE 10.41 General form of a decoder for cyclic code.
This error vector is then added (modulo-2 addition) to the received code word Y, to get the corrected code vector X.
Therefore, Corrected code vector = X’ = Y Å E.                                    …(10.48)
The process of decoding has been illustrated in figure 10.41.
Working operation of the decoder
The switches S_in are closed and S_out are open circuited. The received code vector Y is then shifted into the buffer register and syndrome register. After shifting all the n bits of received code vector Y, the syndrome register holds the corresponding syndrome vector. Then, the contents of the syndrome register are read into the error pattern detector. This detector is a combinational logic circuit. A particular error pattern will be detected for each syndrome vector present in the syndrome register. Then the switches S_in are open circuited and S_out are closed. The contents of the buffer register, error register and syndrome register are then shifted. The received code vector Y (which is stored in the buffer register) , is then added with the error vector E(stored in the error register) bit by bit to obtain the corrected code word X at decoder output.
EXAMPLE 10.28. Construct the (7, 4) linear code word for the generator polynomial G(D) = 1 + D² + D³ for the message bits 1 0 0 1 and find the checksum for the same.
Solution : (i) First, we determine the message polynomial M(p).
(ii)        Then, we multiply M(p) by p^n-k to obtain p^n-k M(p)
(iii)       After that we divide p^n-k M(p) by the generator polynomial G(p).
(iv)       Lastly, we obtain the code word X as under :
X = [m₃ m₂ m₁ m₀ : c₂ c₁ c₀]
(i)         The given message is 1 0 0 1, therefore, there are 4 message bits.
Thus,                           [m₃ m₂ m₁ m₀] = [1 0 0 1]
Therefore,                    M(p) = m₀ + m₁ p + m₂ p² + m₃ p³
Substituting the values of message bits, we obtain
M(p) = 1 + 0p + 0 p² + p³
⸫                                 M(p) = 1 + p³                                                               …(1)
(ii)        Let us multiply M(p) by p^n-k.
Given code is (7, 4) code. Therefore, n = 7 and k = 4. Hence, (n – k) = 3.
Therefore, we have
p^n-k M(p) = m³ [1 + 0 p + 0 p² + p³]
p³ M(p) = p³ + 0 p⁴ + 0 p⁵ + p⁶                                                  …(2)
(iii)      Now, we divide p^n-k M(p) by G(p).
The division takes place as under :
EQUATION
Modulo – 2 additions →        equation
Modulo – 2 additions  →        equation
Mod – 2 additions                   →        equation
Modulo – 2 additions  →        equation
Therefore, remainder polynomial C(p) = p² + 0 p + 0                               …(iii)
(iv)       Lastly, let us obtain the codeword polynomial :
Codeword polynomial X(p) = p³ M(p) + C(p)
Substituting the values from equations (ii) and (iii) we get,
X(p) = [p⁶ + 0p⁵ + 0p⁴ + p³ + 0p² + 0p + 0] + [p² + 0p +0]
or         X(p) = p⁶ + 0p⁵ + 0p⁴ + p³ + p² + 0p + 0
Therefore, the codeword is given by
X = [m₃ m₂ m₁ m₀ : c₂ c₁ c₀] = [1 0 0 1 : 1 0 0]            Ans.
equation