Code that corrects a length $s$ burst error

122 Views Asked by At

Show that exists an $(n,k)=(155,135)$ binary code that corrects burst errors of length $6$.

P.S. A Code with length $n$ fixes burst error (pattern) of length $s$ if the error set of this code consists of sets of length $n$ whose non-zero components are located in $s$ consecutive bits, that is, in each such set, the locations of the first and last non-zero components differ by no more than $s - 1$.

2

There are 2 best solutions below

0
On

Basically if you want to correct a burst of length $s,$ your code must have the property that no two codewords differ by the sum of two (non overlapping) bursts of length $s.$

This leads to the Rieger bound, that $n-k\geq 2s$. So your parameters satisfy this. However, you probably need to look up Fire codes which would actually achieve a so called burst error correction efficiency ratio given by $$ \frac{2s}{n-k} \geq 2/3. $$ Good luck.

1
On

The field of 32 elements, $GF(32)$ or $\Bbb{F}_{32}$, whichever name you prefer, has $31$ non-zero elements. Each element can be represented by a block of five bits in several ways. As $155=5\cdot31$, this is just what the doctor ordered.

A burst of length $6$ cannot disturb more than two (consecutive) $5$-bit symbols. Therefore a code correcting two symbol errors can handle bursts like this.

The Reed-Solomon codes are MDS, so a $32$-ary RS code with $(n,k)=(31,27)$ has minimum distance $d=n-k+1=5$. Therefore it can correct any two symbol errors, and the problem is solved as $135=5\cdot27$.


That RS-code does not care whether the two errorneous symbols are consecutive or not. Making this a bit of a cheat solution. But, hey, it works :-)