Error Trapping for Cyclic Codes

Print preview

Worksheet Error Trapping for Cyclic Codes

In this activity, we will investigate the error trapping algorithm for decoding certain kinds of errors with cyclic codes.

🔗

Algorithm 94. Error Trapping Decoding for Cyclic Codes.

Let \(C\) be a \(t\)-error correcting cyclic \([n,k]_q\) code with generator polynomial \(g(x)\text{.}\) Let \(s_i(x)\) denote the syndrome of \(x^i y(x)\) for a received word \(\vec{y}\text{.}\)

🔗

Let \(e(x)\) be an error pattern, \(w_H(\vec{e})\leq t\text{,}\) containing a cyclic run of at least \(k\) 0s. Then we can decode the received vector \(y(x)=c(x)+e(x)\) to \(c(x)\) as follows.

🔗

Compute the syndrome \(s_0(x)\) of \(y(x)\) from the division algorithm

\begin{equation*} y(x)=q(x)g(x)+s_0(x)\text{.} \end{equation*}

🔗

🔗
Set \(i=0.\)
🔗

🔗
If \(w_H(s_i(x))\leq t\text{,}\) then set \(e(x)=x^{n-i}(\vec{s}_i,\vec{0})\text{,}\) and decode to \(y(x)-e(x)\text{.}\)
🔗

🔗
Set \(i=i+1\text{.}\)
🔗

🔗
If \(i=n\) then stop; the error pattern is not trappable.
🔗

🔗
If \(\deg(s_{i-1}(x))\lt n-k-1,\) then set \(s_i(x)=x s_{i-1}(x)\text{.}\) Otherwise, set \(s_i(x)=x s_{i-1}(x)-s_{n-k-1} g(x)\text{,}\) where \(s_{n-k-1}\) is the leading coefficient of \(s_{i-1}(x)\text{.}\)
🔗

🔗
Go to step 3.
🔗

🔗

🔗

1.

Consider the binary cyclic \([15,7,5]\) code generated by \(g(x)=1+x^4+x^6+x^7+x^8\text{,}\) which is \(2\)-error decoding. What is the smallest cyclic run of 0s that must be present in an error pattern of weight at most 2?

🔗

Solution.

Without loss of generality by taking cyclic shifts we can assume the first 1 occurs in position one. Then the other one divides the remaining thirteen 0s into two cyclic runs. By the pigeonhole principle one of the two has at least seven 0s.

🔗

2.

Apply Error Trapping Decoding for Cyclic Codes to decode the received word \(\vec{y}=(0010\, 1100\, 1110\, 110)\text{.}\) (Perhaps you want to use Polynomial Operations over Finite Fields to do the initial computation of the syndrome.)

🔗

Solution.

We compute \(s_0(x)=x^5+x^4+x^3+x^2+x\) since

\begin{equation*} y(x)=x^2+x^4+x^5+x^8+x^9+x^{10}+x^{12}+x^{13}=(x^5+x^3+x)(1+x^4+x^6+x^7+x^8)+x^5+x^4+x^3+x^2+x\text{.} \end{equation*}

This has weight \(5\geq t=2\) so we start shifting. We have \(s_1=xs_0(x)\) since \(\deg(s_0)(x)=5\lt n-k-1=7\) so \(s_1=x^6+x^5+x^4+x^3+x^2\text{,}\) which still has weight \(5\text{.}\) In general the weight will not shift until we have to subtract \(g(x)\text{.}\)

🔗

Continuing, we find \(s_2=xs_1(x)=x^7+x^6+x^5+x^4+x^3\text{.}\) But this has degree \(n-k-1\) so

\begin{equation*} s_3(x)=x s_2(x) - g(x) = x^5+1 \end{equation*}

and this has weight 2, so we are done. Now we have \(e(x)=x^{15-3}s_3(x) \pmod{x^{15}-1}=x^2+x^12\) so the error vector was \(\vec{e}=(0001\, 0000\, 0000\, 100)\) and so the corrected codeword is \(\vec{c}=(0011\,1100\,1110\,010)\text{.}\)

🔗

Algorithm 95. Error Trapping for Cyclic Burst-Error Codes.

Let \(C\) be a cyclic \([n,k]_q\) code with generator polynomial \(g(x)\) capable of correcting all burst errors of length \(b\) or less. Let \(s_i(x)\) denote the syndrome of \(x^i y(x)\) for a received word \(\vec{y}\text{.}\)

🔗

Compute the syndrome \(s_0(x)\) of \(y(x)\) from the division algorithm

\begin{equation*} y(x)=q(x)g(x)+s_0(x)\text{.} \end{equation*}

🔗

🔗
Set \(i=0.\)
🔗

🔗
If \(s_i(x)\) is a (non-cyclic) burst of length \(b\) or less, then set \(e(x)=x^{n-i}(\vec{s}_i,\vec{0})\text{,}\) and decode to \(y(x)-e(x)\text{.}\)
🔗

🔗
Set \(i=i+1\text{.}\)
🔗

🔗
If \(i=n\) then stop; the error pattern is not trappable.
🔗

🔗
If \(\deg(s_{i-1}(x))\lt n-k-1,\) then set \(s_i(x)=x s_{i-1}(x)\text{.}\) Otherwise, set \(s_i(x)=x s_{i-1}(x)-s_{n-k-1} g(x)\text{,}\) where \(s_{n-k-1}\) is the leading coefficient of \(s_{i-1}(x)\text{.}\)
🔗

🔗
Go to step 3.
🔗

🔗

🔗

Notice that the only difference between this algorithm and Error Trapping Decoding for Cyclic Codes is the stop condition checked for each \(s_i(x)\text{.}\)

🔗

3.

Show that a code can correct any burst of length \(b\) or less only if no codeword is a burst of length \(2b\) or less.

🔗

This condition is hard to verify algebraically in general; often this is checked by brute-force computation for codes we wish to use for cyclic error decoding.

🔗

Solution.

We show the contrapositive: if there is a codeword which is a burst of length \(2b\) or less, then there are bursts of length \(b\) or less than cannot both be decoded. This follows by splitting the codeword \(\vec{c}\) which is a burst of length \(2b\) into two bursts \(\vec{e}_1,\vec{e}_2\) containing the first half and the negative of the second half of the burst. Then each of these is a burst of length at most \(b\) but their difference is a codeword, so they lie in the same coset of the code and thus are not both decodable.

🔗

4.

Conclude that for a code to correct all bursts of length \(b\) or less we must have \(n\geq k + 2b\text{.}\) Use this to show that the condition of Error Trapping for Cyclic Burst-Error Codes on burst length implies the condition of Error Trapping Decoding for Cyclic Codes on cyclic runs.

🔗

Solution.

Since we must have \(n\geq k+2b\text{,}\) we have \(n-k\geq 2b \gt b\text{,}\) so \(n-b\gt k\) and thus there is a cyclic run of at least \(k\) 0s in a burst of length \(b\text{.}\)

🔗

5.

Carry out the burst error-trapping algorithm on the received word \(y(x)=1+x+x^7\) for the binary cyclic \([15,9]\) code with generator \(g(x)=1+x+x^2+x^3+x^6\text{.}\)

🔗

Solution.

We have

\begin{align*} s_0 \amp= (101110) \amp \text{ burst of length 5}\\ s_1 \amp =x s_0 = (010111) \amp \text{ burst of length 5}\\ s_2 \amp =x s_1 - g(x) = (110111) \amp \text{ burst of length 5}\\ s_3 \amp =x s_2 - g(x) = (100111) \amp \text{ burst of length 4}\\ s_4 \amp =x s_3 - g(x) = (101111) \amp \text{ burst of length 5}\\ s_5 \amp =x s_4 - g(x) = (101011) \amp \text{ burst of length 5}\\ s_6 \amp =x s_5 - g(x) = (101001) \amp \text{ burst of length 4}\\ s_7 \amp =x s_6 - g(x) = (101000) \amp \text{ burst of length 3}\text{.} \end{align*}

So we conclude

\begin{equation*} e(x)=x^{15-7}s_7(x)\pmod{x^{15}-1} = x^{8}+ x^{10} \end{equation*}

and thus \(c(x)=1+x+x^7+x^8+x^{10}\text{.}\)

🔗

Prev Top Next

Print preview

Worksheet Error Trapping for Cyclic Codes

Algorithm 94. Error Trapping Decoding for Cyclic Codes.

1.

2.

Algorithm 95. Error Trapping for Cyclic Burst-Error Codes.

3.

4.

5.

Worksheet Error Trapping for Cyclic Codes