Algorithm93.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.
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{.}\)
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?
Algorithm94.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{.}\)
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{.}\)
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{.}\)
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.
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{.}\)
