Burst error-correcting code#Fire codes

File:Burst Error,Length 5,Description.jpg

A burst of length {{math|ℓ}}{{cite arXiv |last=Fong |first=W.H. |date=2011|title=Coding Bounds for Multiple Phased-Burst Correction and Single Burst Correction Codes |class=cs.IT |eprint=1104.1408}}

Say a codeword $C$ is transmitted, and it is received as $Y\; =\; C\; +\; E.$ Then, the error vector $E$ is called a burst of length $\backslash ell$ if the nonzero components of $E$ are confined to $\backslash ell$ consecutive components. For example, $E\; =\; (0\backslash textbf\{1000011\}0)$ is a burst of length $\backslash ell\; =\; 7.$

Although this definition is sufficient to describe what a burst error is, the majority of the tools developed for burst error correction rely on cyclic codes. This motivates our next definition.

A cyclic burst of length {{math|ℓ}}

An error vector $E$ is called a cyclic burst error of length $\backslash ell$ if its nonzero components are confined to $\backslash ell$ cyclically consecutive components. For example, the previously considered error vector $E\; =\; (010000110)$, is a cyclic burst of length $\backslash ell\; =\; 5$, since we consider the error starting at position $6$ and ending at position $1$. Notice the indices are $0$-based, that is, the first element is at position $0$.

For the remainder of this article, we will use the term burst to refer to a cyclic burst, unless noted otherwise.

It is often useful to have a compact definition of a burst error, that encompasses not only its length, but also the pattern, and location of such error. We define a burst description to be a tuple $(P,L)$ where $P$ is the pattern of the error (that is the string of symbols beginning with the first nonzero entry in the error pattern, and ending with the last nonzero symbol), and $L$ is the location, on the codeword, where the burst can be found.

For example, the burst description of the error pattern $E\; =\; (010000110)$ is $D\; =\; (1000011,1)$. Notice that such description is not unique, because $D\text{'}\; =\; (11001,6)$ describes the same burst error. In general, if the number of nonzero components in $E$ is $w$, then $E$ will have $w$ different burst descriptions each starting at a different nonzero entry of $E$. To remedy the issues that arise by the ambiguity of burst descriptions with the theorem below, however before doing so we need a definition first.

Definition. The number of symbols in a given error pattern $y,$ is denoted by $\backslash mathrm\{length\}(y).$

{{math theorem | name = Theorem (Uniqueness of burst descriptions) | math_statement = Suppose $E$ is an error vector of length $n$ with two burst descriptions $(P\_1,L\_1)$ and $(P\_2,L\_2)$. If $\backslash mathrm\{length\}(P\_1)\; +\; \backslash mathrm\{length\}(P\_2)\; \backslash leqslant\; n\; +\; 1,$ then the two descriptions are identical that is, their components are equivalent.{{cite book |first=R.J. |last=McEliece |title=The Theory of Information and Coding |publisher=Cambridge University Press |edition=Student |date=2004 |isbn=978-0-521-83185-7 |pages= |url={{GBurl|bQ9fWH7fh3IC|pg=PR5}}}}

{{math proof | proof = Let $w$ be the hamming weight (or the number of nonzero entries) of $E$. Then $E$ has exactly $w$ error descriptions. For $w\; =\; 0,\; 1,$ there is nothing to prove. So we assume that $w\; \backslash geqslant\; 2$ and that the descriptions are not identical. We notice that each nonzero entry of $E$ will appear in the pattern, and so, the components of $E$ not included in the pattern will form a cyclic run of zeros, beginning after the last nonzero entry, and continuing just before the first nonzero entry of the pattern. We call the set of indices corresponding to this run as the zero run. We immediately observe that each burst description has a zero run associated with it and that each zero run is disjoint. Since we have $w$ zero runs, and each is disjoint, we have a total of $n-w$ distinct elements in all the zero runs. On the other hand we have: $$\backslash begin\{align\}$$

n-w = \text{number of zeros in } E &\geqslant (n - \mathrm{length}(P_1)) + (n - \mathrm{length}(P_2))\\

&= 2n - \left ( \mathrm{length}(P_1) + \mathrm{length}(P_2) \right ) \\

&\geqslant 2n - (n+1) && \mathrm{length}(P_1) + \mathrm{length}(P_2) \leqslant n+1 \\

&= n-1

\end{align}

This contradicts $w\; \backslash geqslant\; 2.$ Thus, the burst error descriptions are identical.}}}}

A corollary of the above theorem is that we cannot have two distinct burst descriptions for bursts of length $\backslash tfrac\{1\}\{2\}(n+1).$

Cyclic codes are defined as follows: think of the $q$ symbols as elements in $\backslash mathbb\{F\}\_q$. Now, we can think of words as polynomials over $\backslash mathbb\{F\}\_q,$ where the individual symbols of a word correspond to the different coefficients of the polynomial. To define a cyclic code, we pick a fixed polynomial, called generator polynomial. The codewords of this cyclic code are all the polynomials that are divisible by this generator polynomial.

Codewords are polynomials of degree $\backslash leqslant\; n-1$. Suppose that the generator polynomial $g(x)$ has degree $r$. Polynomials of degree $\backslash leqslant\; n-1$ that are divisible by $g(x)$ result from multiplying $g(x)$ by polynomials of degree $\backslash leqslant\; n-1-r$. We have $q^\{n-r\}$ such polynomials. Each one of them corresponds to a codeword. Therefore, $k=n-r$ for cyclic codes.

Cyclic codes can detect all bursts of length up to $\backslash ell\; =\; n-k\; =\; r$. We will see later that the burst error detection ability of any $(n,\; k)$ code is bounded from above by $\backslash ell\; \backslash leqslant\; n-k$. Cyclic codes are considered optimal for burst error detection since they meet this upper bound:

{{math theorem | name = Theorem (Cyclic burst correction capability) | math_statement = Every cyclic code with generator polynomial of degree $r$ can detect all bursts of length $\backslash leqslant\; r.$

{{math proof | proof = We need to prove that if you add a burst of length $\backslash leqslant\; r$ to a codeword (i.e. to a polynomial that is divisible by $g(x)$), then the result is not going to be a codeword (i.e. the corresponding polynomial is not divisible by $g(x)$). It suffices to show that no burst of length $\backslash leqslant\; r$ is divisible by $g(x)$. Such a burst has the form $x^i\; b(x)$, where Therefore, $b(x)$ is not divisible by $g(x)$ (because the latter has degree $r$). $g(x)$ is not divisible by $x$ (Otherwise, all codewords would start with $0$). Therefore, $x^i$ is not divisible by $g(x)$ as well.}}

}}

The above proof suggests a simple algorithm for burst error detection/correction in cyclic codes: given a transmitted word (i.e. a polynomial of degree $\backslash leqslant\; n-1$), compute the remainder of this word when divided by $g(x)$. If the remainder is zero (i.e. if the word is divisible by $g(x)$), then it is a valid codeword. Otherwise, report an error. To correct this error, subtract this remainder from the transmitted word. The subtraction result is going to be divisible by $g(x)$ (i.e. it is going to be a valid codeword).

By the upper bound on burst error detection ($\backslash ell\; \backslash leqslant\; n-k\; =\; r$), we know that a cyclic code can not detect all bursts of length $\backslash ell\; >\; r$. However cyclic codes can indeed detect most bursts of length $>\; r$. The reason is that detection fails only when the burst is divisible by $g(x)$. Over binary alphabets, there exist $2^\{\backslash ell-2\}$ bursts of length $\backslash ell$. Out of those, only $2^\{\backslash ell-2-r\}$ are divisible by $g(x)$. Therefore, the detection failure probability is very small ($2^\{-r\}$) assuming a uniform distribution over all bursts of length $\backslash ell$.

We now consider a fundamental theorem about cyclic codes that will aid in designing efficient burst-error correcting codes, by categorizing bursts into different cosets.

{{math theorem | name = Theorem (Distinct Cosets) | math_statement = A linear code $C$ is an $\backslash ell$-burst-error-correcting code if all the burst errors of length $\backslash leqslant\; \backslash ell$ lie in distinct cosets of $C$.

{{math proof | proof = Let $\backslash mathbf\{e\}\_1,\; \backslash mathbf\{e\}\_2$ be distinct burst errors of length $\backslash leqslant\; \backslash ell$ which lie in same coset of code $C$. Then $\backslash mathbf\{c\}\; =\; \backslash mathbf\{e\}\_1\; -\; \backslash mathbf\{e\}\_2$ is a codeword. Hence, if we receive $\backslash mathbf\{e\}\_1,$ we can decode it either to $\backslash mathbf\{0\}$ or $\backslash mathbf\{c\}$. In contrast, if all the burst errors $\backslash mathbf\{e\}\_1$ and $\backslash mathbf\{e\}\_2$ do not lie in same coset, then each burst error is determined by its syndrome. The error can then be corrected through its syndrome. Thus, a linear code $C$ is an $\backslash ell$-burst-error-correcting code if and only if all the burst errors of length $\backslash leqslant\; \backslash ell$ lie in distinct cosets of $C$.}}}}

{{math theorem | name = Theorem (Burst error codeword classification) | math_statement = Let $C$ be a linear $\backslash ell$-burst-error-correcting code. Then no nonzero burst of length $\backslash leqslant\; 2\backslash ell$ can be a codeword.

{{math proof | proof = Let $c$ be a codeword with a burst of length $\backslash leqslant\; 2\backslash ell$. Thus it has the pattern $(0,1,u,v,1,0)$, where $u$ and $v$ are words of length $\backslash leqslant\; \backslash ell\; -1.$ Hence, the words $w\; =\; (0,1,u,0,0,0)$ and $c-w\; =\; (0,0,0,v,1,0)$ are two bursts of length $\backslash leqslant\; \backslash ell$. For binary linear codes, they belong to the same coset. This contradicts the Distinct Cosets Theorem, therefore no nonzero burst of length $\backslash leqslant\; 2\backslash ell$ can be a codeword.}}

}}

By upper bound, we mean a limit on our error detection ability that we can never go beyond. Suppose that we want to design an $(n,\; k)$ code that can detect all burst errors of length $\backslash leqslant\; \backslash ell.$ A natural question to ask is: given $n$ and $k$, what is the maximum $\backslash ell$ that we can never achieve beyond? In other words, what is the upper bound on the length $\backslash ell$ of bursts that we can detect using any $(n,\; k)$ code? The following theorem provides an answer to this question.

{{math theorem | name = Theorem (Burst error detection ability) | math_statement = The burst error detection ability of any $(n,\; k)$ code is $\backslash ell\; \backslash leqslant\; n-k.$

{{math proof | proof = First we observe that a code can detect all bursts of length $\backslash leqslant\; \backslash ell$ if and only if no two codewords differ by a burst of length $\backslash leqslant\; \backslash ell$. Suppose that we have two code words $\backslash mathbf\{c\}\_1$ and $\backslash mathbf\{c\}\_2$ that differ by a burst $\backslash mathbf\{b\}$ of length $\backslash leqslant\; \backslash ell$. Upon receiving $\backslash mathbf\{c\}\_1$, we can not tell whether the transmitted word is indeed $\backslash mathbf\{c\}\_1$ with no transmission errors, or whether it is $\backslash mathbf\{c\}\_2$ with a burst error $\backslash mathbf\{b\}$ that occurred during transmission. Now, suppose that every two codewords differ by more than a burst of length $\backslash ell.$ Even if the transmitted codeword $\backslash mathbf\{c\}\_1$ is hit by a burst $\backslash mathbf\{b\}$ of length $\backslash ell$, it is not going to change into another valid codeword. Upon receiving it, we can tell that this is $\backslash mathbf\{c\}\_1$ with a burst $\backslash mathbf\{b\}.$ By the above observation, we know that no two codewords can share the first $n-\backslash ell$ symbols. The reason is that even if they differ in all the other $\backslash ell$ symbols, they are still going to be different by a burst of length $\backslash ell.$ Therefore, the number of codewords $q^k$ satisfies $q^k\; \backslash leqslant\; q^\{n-\backslash ell\}.$ Applying $\backslash log\_q$ to both sides and rearranging, we can see that $\backslash ell\; \backslash leqslant\; n-k$.}}

}}

Now, we repeat the same question but for error correction: given $n$ and $k$, what is the upper bound on the length $\backslash ell$ of bursts that we can correct using any $(n,\; k)$ code? The following theorem provides a preliminary answer to this question:

{{math theorem | name = Theorem (Burst error correction ability) | math_statement = The burst error correction ability of any $(n,\; k)$ code satisfies $\backslash ell\; \backslash leqslant\; n-k-\backslash log\_q\; (n-\backslash ell)+2$

{{math proof | proof = First we observe that a code can correct all bursts of length $\backslash leqslant\; \backslash ell$ if and only if no two codewords differ by the sum of two bursts of length $\backslash leqslant\; \backslash ell.$ Suppose that two codewords $\backslash mathbf\{c\}\_1$ and $\backslash mathbf\{c\}\_2$ differ by bursts $\backslash mathbf\{b\}\_1$ and $\backslash mathbf\{b\}\_2$ of length $\backslash leqslant\; \backslash ell$ each. Upon receiving $\backslash mathbf\{c\}\_1$ hit by a burst $\backslash mathbf\{b\}\_1$, we could interpret that as if it was $\backslash mathbf\{c\}\_2$ hit by a burst $-\backslash mathbf\{b\}\_2$. We can not tell whether the transmitted word is $\backslash mathbf\{c\}\_1$ or $\backslash mathbf\{c\}\_2$. Now, suppose that every two codewords differ by more than two bursts of length $\backslash ell$. Even if the transmitted codeword $\backslash mathbf\{c\}\_1$ is hit by a burst of length $\backslash ell$, it is not going to look like another codeword that has been hit by another burst. For each codeword $\backslash mathbf\{c\},$ let $B(\backslash mathbf\{c\})$ denote the set of all words that differ from $\backslash mathbf\{c\}$ by a burst of length $\backslash leqslant\; \backslash ell.$ Notice that $B(\backslash mathbf\{c\})$ includes $\backslash mathbf\{c\}$ itself. By the above observation, we know that for two different codewords $\backslash mathbf\{c\}\_i$ and $\backslash mathbf\{c\}\_j,\; B(\backslash mathbf\{c\}\_i)$ and $B(\backslash mathbf\{c\}\_j)$ are disjoint. We have $q^k$ codewords. Therefore, we can say that $q^k\; |B(\; \backslash mathbf\{c\})|\; \backslash leqslant\; q^n$. Moreover, we have $(n-\backslash ell)q^\{\backslash ell-2\}\; \backslash leqslant\; |B(\backslash mathbf\{c\})|$. By plugging the latter inequality into the former, then taking the base $q$ logarithm and rearranging, we get the above theorem.}}

}}

A stronger result is given by the Rieger bound:

{{math theorem | name = Theorem (Rieger bound) | math_statement = If $\backslash ell$ is the burst error correcting ability of an $(n,\; k)$ linear block code, then $2\backslash ell\; \backslash leqslant\; n\; -\; k$.

{{math proof | proof = Any linear code that can correct any burst pattern of length $\backslash leqslant\; \backslash ell$ cannot have a burst of length $\backslash leqslant\; 2\backslash ell$ as a codeword. If it had a burst of length $\backslash leqslant\; 2\backslash ell$ as a codeword, then a burst of length $\backslash ell$ could change the codeword to a burst pattern of length $\backslash ell$, which also could be obtained by making a burst error of length $\backslash ell$ in all zero codeword. If vectors are non-zero in first $2\backslash ell$ symbols, then the vectors should be from different subsets of an array so that their difference is not a codeword of bursts of length $2\backslash ell$. Ensuring this condition, the number of such subsets is at least equal to number of vectors. Thus, the number of subsets would be at least $q^\{2\backslash ell\}$. Hence, we have at least $2\backslash ell$ distinct symbols, otherwise, the difference of two such polynomials would be a codeword that is a sum of two bursts of length $\backslash leqslant\; \backslash ell.$ Thus, this proves the Rieger Bound.}}}}

Definition. A linear burst-error-correcting code achieving the above Rieger bound is called an optimal burst-error-correcting code.

There is more than one upper bound on the achievable code rate of linear block codes for multiple phased-burst correction (MPBC). One such bound is constrained to a maximum correctable cyclic burst length within every subblock, or equivalently a constraint on the minimum error free length or gap within every phased-burst. This bound, when reduced to the special case of a bound for single burst correction, is the Abramson bound (a corollary of the Hamming bound for burst-error correction) when the cyclic burst length is less than half the block length.{{cite book |last1=Ling |first1=San |first2=Chaoping |last2=Xing |title=Coding Theory: A First Course |publisher=Cambridge University Press |date=2004 |isbn=978-0-521-52923-5 |pages= |url={{GBurl|N1jiL8V3ISwC|pg=PR7}}}}

{{math theorem | name = Theorem (number of bursts) | math_statement = For $1\; \backslash leqslant\; \backslash ell\; \backslash leqslant\; \backslash tfrac\{1\}\{2\}(n+1),$ over a binary alphabet, there are $n2^\{\backslash ell-1\}+1$ vectors of length $n$ which are bursts of length $\backslash leqslant\; \backslash ell$.

{{math proof | proof = Since the burst length is $\backslash leqslant\; \backslash tfrac\{1\}\{2\}(n+1),$ there is a unique burst description associated with the burst. The burst can begin at any of the $n$ positions of the pattern. Each pattern begins with $1$ and contain a length of $\backslash ell$. We can think of it as the set of all strings that begin with $1$ and have length $\backslash ell$. Thus, there are a total of $2^\{\backslash ell-1\}$ possible such patterns, and a total of $n2^\{\backslash ell-1\}$ bursts of length $\backslash leqslant\; \backslash ell.$ If we include the all-zero burst, we have $n2^\{\backslash ell-1\}+1$ vectors representing bursts of length $\backslash leqslant\; \backslash ell.$}}}}

{{math theorem | name = Theorem (Bound on the number of codewords) | math_statement = If $1\; \backslash leqslant\; \backslash ell\; \backslash leqslant\; \backslash tfrac\{1\}\{2\}(n+1),$ a binary $\backslash ell$-burst error correcting code has at most $2^n/(n2^\{\backslash ell-1\}+1)$ codewords.

{{math proof | proof = Since $\backslash ell\; \backslash leqslant\; \backslash tfrac\{1\}\{2\}(n+1)$, we know that there are $n\; 2^\{\backslash ell-1\}+1$ bursts of length $\backslash leqslant\; \backslash ell$. Say the code has $M$ codewords, then there are $Mn2^\{\backslash ell-1\}$ codewords that differ from a codeword by a burst of length $\backslash leqslant\; \backslash ell$. Each of the $M$ words must be distinct, otherwise the code would have distance . Therefore, $M(2^\{\backslash ell-1\}+1)\; \backslash leqslant\; 2^n$ implies $M\; \backslash leqslant\; 2^n/(n2^\{\backslash ell-1\}+1).$}}}}

{{math theorem | name = Theorem (Abramson's bounds) | math_statement = If $1\; \backslash leqslant\; \backslash ell\; \backslash leqslant\; \backslash tfrac\{1\}\{2\}(n+1)$ is a binary linear $(n,k),\; \backslash ell$-burst error correcting code, its block-length must satisfy: $$n\; \backslash leqslant\; 2^\{n-k-\backslash ell+1\}\; -1.$$

{{math proof | proof = For a linear $(n,k)$ code, there are $2^k$ codewords. By our previous result, we know that

$$2^k\; \backslash leqslant\; \backslash frac\{2^n\}\{n2^\{\backslash ell-1\}+1\}.$$

Isolating $n$, we get $n\; \backslash leqslant\; 2^\{n-k-\backslash ell+1\}-2^\{-\backslash ell+1\}$. Since $\backslash ell\; \backslash geqslant\; 1$ and $n$ must be an integer, we have $n\; \backslash leqslant\; 2^\{n-k-\backslash ell+1\}-1$.}}}}

Remark. $r\; =\; n\; -\; k$ is called the redundancy of the code and in an alternative formulation for the Abramson's bounds is $r\; \backslash geqslant\; \backslash lceil\; \backslash log\_2(n+1)\; \backslash rceil\; +\; \backslash ell\; -1.$

{{See also|Cyclic code#Fire codes as cyclic bounds}}

Sources:{{cite book |first=Todd K. |last=Moon |title=Error Correction Coding: Mathematical Methods and Algorithms |publisher=Wiley |date=2005 |isbn=978-0-471-64800-0 |pages= |url={{GBurl|UMmbDwAAQBAJ|pg=PR13}}}}{{cite book |last1=Lin |first1=Shu |first2=Daniel J. |last2=Costello |title=Error Control Coding: Fundamentals and Applications |publisher=Pearson-Prentice Hall |date=2004 |edition=2nd |isbn=978-0-13-017973-9 |pages= |url=}}

While cyclic codes in general are powerful tools for detecting burst errors, we now consider a family of binary cyclic codes named Fire Codes, which possess good single burst error correction capabilities. By single burst, say of length $\backslash ell$, we mean that all errors that a received codeword possess lie within a fixed span of $\backslash ell$ digits.

Let $p(x)$ be an irreducible polynomial of degree $m$ over $\backslash mathbb\{F\}\_2$, and let $p$ be the period of $p(x)$. The period of $p(x)$, and indeed of any polynomial, is defined to be the least positive integer $r$ such that $p(x)\; |x^r\; -\; 1.$ Let $\backslash ell$ be a positive integer satisfying $\backslash ell\; \backslash leqslant\; m$ and $2\backslash ell\; -1$ not divisible by $p$, where $m$ and $p$ are the degree and period of $p(x)$, respectively. Define the Fire Code $G$ by the following generator polynomial:

$$g(x)\; =\; \backslash left\; (x^\{2\backslash ell\; -1\}\; +\; 1\; \backslash right\; )p(x).$$

We will show that $G$ is an $\backslash ell$-burst-error correcting code.

{{math theorem | name = Lemma 1 | math_statement = $\backslash gcd\; \backslash left\; (p(x),\; x^\{2\backslash ell\; -1\}\; +\; 1\; \backslash right\; )\; =\; 1.$

{{math proof | proof = Let $d(x)$ be the greatest common divisor of the two polynomials. Since $p(x)$ is irreducible, $\backslash deg(d(x))\; =\; 0$ or $\backslash deg(p(x))$. Assume $\backslash deg(d(x))\; \backslash neq\; 0,$ then $p(x)\; =\; c\; d(x)$ for some constant $c$. But, $(1/c)p(x)$ is a divisor of $x^\{2\backslash ell\; -1\}+1$ since $d(x)$ is a divisor of $x^\{2\backslash ell\; -1\}+1$. But this contradicts our assumption that $p(x)$ does not divide $x^\{2\backslash ell\; -1\}+1.$ Thus, $\backslash deg(d(x))\; =\; 0,$ proving the lemma.}}}}

{{math theorem | name = Lemma 2 | math_statement = If $p(x)$ is a polynomial of period $p$, then $p(x)|x^k-1$ if and only if $p|k.$

{{math proof | proof = If $p|k$, then $x^k-1\; =\; (x^p-1)(1\; +\; x^p\; +\; x^\{2p\}\; +\; \backslash dots\; +\; x^\{k/p\})$. Thus, $p(x)|x^k-1.$

{{pb}}

Now suppose $p(x)\; |\; x^k-1$. Then, $k\; \backslash geqslant\; p$. We show that $k$ is divisible by $p$ by induction on $k$. The base case $k\; =\; p$ follows. Therefore, assume $k\; >\; p$. We know that $p(x)$ divides both (since it has period $p$) $$x^p\; -1\; =\; (x-1)\; \backslash left\; (1\; +\; x\; +\; \backslash dots\; +\; x^\{p-1\}\; \backslash right\; )\; \backslash quad\; \backslash text\{and\}\; \backslash quad\; x^k\; -\; 1\; =\; (x-1)\; \backslash left\; (1\; +\; x\; +\; \backslash dots\; +\; x^\{k-1\}\; \backslash right\; ).$$ But $p(x)$ is irreducible, therefore it must divide both $(1\; +\; x\; +\; \backslash dots\; +\; x^\{p-1\})$ and $(1\; +\; x\; +\; \backslash dots\; +\; x^\{k-1\})$; thus, it also divides the difference of the last two polynomials, $x^p(1\; +\; x\; +\; \backslash dots\; +\; x^\{p-k-1\})$. Then, it follows that $p(x)$ divides $(1\; +\; x\; +\; \backslash cdots\; +\; x^\{p-k-1\})$. Finally, it also divides: $x^\{k-p\}-1\; =\; (x-1)(1\; +\; x\; +\; \backslash dots\; +\; x^\{p-k-1\})$. By the induction hypothesis, $p\; |\; k-p$, then $p\; |\; k$.

A corollary to Lemma 2 is that since $p(x)\; =\; x^p\; -\; 1$ has period $p$, then $p(x)$ divides $x^k-1$ if and only if $p|k$.}}}}

{{math theorem | math_statement = The Fire Code is $\backslash ell$-burst error correcting}}

If we can show that all bursts of length $\backslash ell$ or less occur in different cosets, we can use them as coset leaders that form correctable error patterns. The reason is simple: we know that each coset has a unique syndrome decoding associated with it, and if all bursts of different lengths occur in different cosets, then all have unique syndromes, facilitating error correction.

Let $x^i\; a(x)$ and $x^j\; b(x)$ be polynomials with degrees $\backslash ell\_1-1$ and $\backslash ell\_2-1$, representing bursts of length $\backslash ell\_1$ and $\backslash ell\_2$ respectively with $\backslash ell\_1,\; \backslash ell\_2\; \backslash leqslant\; \backslash ell.$ The integers $i,\; j$ represent the starting positions of the bursts, and are less than the block length of the code. For contradiction sake, assume that $x^i\; a(x)$ and $x^j\; b(x)$ are in the same coset. Then, $v(x)\; =\; x^i\; a(x)\; +\; x^j\; b(x)$ is a valid codeword (since both terms are in the same coset). Without loss of generality, pick $i\; \backslash leqslant\; j$. By the division theorem we can write: $j-i\; =\; g(2\backslash ell\; -1)+r,$ for integers $g$ and . We rewrite the polynomial $v(x)$ as follows:

$$v(x)\; =\; x^ia(x)\; +\; x^\{i\; +\; g(2\backslash ell\; -1)\; +\; r\}\; =\; x^ia(x)\; +\; x^\{i\; +\; g(2\backslash ell\; -1)\; +\; r\}\; +\; 2x^\{i+r\}b(x)\; =\; x^i\; \backslash left\; (a(x)\; +\; x^b\; b(x)\; \backslash right\; )\; +\; x^\{i+r\}b(x)\; \backslash left\; (x^\{g(2\backslash ell\; -1)\}+1\; \backslash right\; )$$

Notice that at the second manipulation, we introduced the term $2x^\{i+r\}b(x)$. We are allowed to do so, since Fire Codes operate on $\backslash mathbb\{F\}\_2$. By our assumption, $v(x)$ is a valid codeword, and thus, must be a multiple of $g(x)$. As mentioned earlier, since the factors of $g(x)$ are relatively prime, $v(x)$ has to be divisible by $x^\{2\backslash ell\; -1\}\; +\; 1$. Looking closely at the last expression derived for $v(x)$ we notice that $x^\{g(2\backslash ell\; -1)\}\; +\; 1$ is divisible by $x^\{2\backslash ell\; -1\}\; +\; 1$ (by the corollary of Lemma 2). Therefore, $a(x)\; +\; x^bb(x)$ is either divisible by $x^\{2\backslash ell\; -1\}\; +\; 1$ or is $0$. Applying the division theorem again, we see that there exists a polynomial $d(x)$ with degree $\backslash delta$ such that:

$$a(x)\; +\; x^b\; b(x)\; =\; d(x)\; (x^\{2\backslash ell\; -1\}+1)$$

Then we may write:

$$\backslash begin\{align\}$$

\delta + 2\ell -1 & = \deg \left (d(x) \left (x^{2\ell -1}+1 \right ) \right ) \\

&= \deg \left (a(x) + x^b b(x) \right ) \\

&= \deg \left (x^b b(x) \right ) && \deg(a(x)) = \ell_1 - 1 < 2\ell -1 \\

&= b + \ell_2 -1

\end{align}

Equating the degree of both sides, gives us $b\; =\; 2\backslash ell\; -\; \backslash ell\_2\; +\; \backslash delta.$ Since $\backslash ell\_1,\; \backslash ell\_2\; \backslash leqslant\; \backslash ell$ we can conclude $b\; \backslash geqslant\; \backslash ell\; +\; \backslash delta,$ which implies $b\; >\; \backslash ell\; -1$ and $b\; >\; \backslash delta$. Notice that in the expansion:

$$a(x)\; +\; x^bb(x)\; =\; 1\; +\; a\_1x\; +\; a\_2x^2\; +\; \backslash dots\; +\; x^\{\backslash ell\_1-1\}\; +\; x^b\; \backslash left\; (1\; +\; b\_1x\; +\; b\_2x^2\; +\; \backslash dots\; +\; x^\{\backslash ell\_2-1\}\; \backslash right\; ).$$

The term $x^b$ appears, but since , the resulting expression $d(x)(x^\{2\backslash ell\; -1\}\; +\; 1)$ does not contain $x^b$, therefore $d(x)\; =\; 0$ and subsequently $a(x)\; +\; x^b\; b(x)\; =\; 0.$ This requires that $b\; =\; 0$, and $a(x)\; =\; b(x)$. We can further revise our division of $j-i$ by $g(2\backslash ell\; -1)$ to reflect $b\; =\; 0,$ that is {{nowrap|$j-i\; =\; g(2\backslash ell\; -1)$.}} Substituting back into $v(x)$ gives us,

$$v(x)\; =\; x^i\; b(x)\; \backslash left\; (x^\{j-1\}+1\; \backslash right\; ).$$

Since , we have . But $p(x)$ is irreducible, therefore $b(x)$ and $p(x)$ must be relatively prime. Since $v(x)$ is a codeword, $x^\{j-1\}+1$ must be divisible by $p(x)$, as it cannot be divisible by $x^\{2\backslash ell\; -1\}\; +\; 1$. Therefore, $j-i$ must be a multiple of $p$. But it must also be a multiple of $2\backslash ell\; -1$, which implies it must be a multiple of $n\; =\; \backslash text\{lcm\}(2\backslash ell\; -1,p)$ but that is precisely the block-length of the code. Therefore, $j-i$ cannot be a multiple of $n$ since they are both less than $n$. Thus, our assumption of $v(x)$ being a codeword is incorrect, and therefore $x^i\; a(x)$ and $x^j\; b(x)$ are in different cosets, with unique syndromes, and therefore correctable.

With the theory presented in the above section, consider the construction of a $5$-burst error correcting Fire Code. Remember that to construct a Fire Code, we need an irreducible polynomial $p(x)$, an integer $\backslash ell$, representing the burst error correction capability of our code, and we need to satisfy the property that

$2\backslash ell\; -1$ is not divisible by the period of $p(x)$. With these requirements in mind, consider the irreducible polynomial $p(x)\; =\; 1\; +\; x^2\; +\; x^5$, and let $\backslash ell\; =\; 5$. Since $p(x)$ is a primitive polynomial, its period is $2^5\; -\; 1\; =\; 31$. We confirm that $2\backslash ell\; -\; 1\; =\; 9$ is not divisible by $31$. Thus,

$$g(x)\; =\; (x^9+1)\; \backslash left\; (1\; +\; x^2\; +\; x^5\; \backslash right\; )\; =\; 1\; +\; x^2\; +\; x^5\; +\; x^9\; +\; x^\{11\}\; +\; x^\{14\}$$

is a Fire Code generator. We can calculate the block-length of the code by evaluating the least common multiple of $p$ and $2\backslash ell\; -1$. In other words, $n\; =\; \backslash text\{lcm\}(9,31)\; =\; 279$. Thus, the Fire Code above is a cyclic code capable of correcting any burst of length $5$ or less.

Certain families of codes, such as Reed–Solomon, operate on alphabet sizes larger than binary. This property awards such codes powerful burst error correction capabilities. Consider a code operating on $\backslash mathbb\{F\}\_\{2^m\}$. Each symbol of the alphabet can be represented by $m$ bits. If $C$ is an $(n,k)$ Reed–Solomon code over $\backslash mathbb\{F\}\_\{2^m\}$, we can think of $C$ as an $[mn,mk]\_2$ code over $\backslash mathbb\{F\}\_\{2\}$.

The reason such codes are powerful for burst error correction is that each symbol is represented by $m$ bits, and in general, it is irrelevant how many of those $m$ bits are erroneous; whether a single bit, or all of the $m$ bits contain errors, from a decoding perspective it is still a single symbol error. In other words, since burst errors tend to occur in clusters, there is a strong possibility of several binary errors contributing to a single symbol error.

Notice that a burst of $(m+1)$ errors can affect at most $2$ symbols, and a burst of $2m\; +\; 1$ can affect at most $3$ symbols. Then, a burst of $tm+1$ can affect at most $t\; +\; 1$ symbols; this implies that a $t$-symbols-error correcting code can correct a burst of length at most $(t-1)m+1$.

In general, a $t$-error correcting Reed–Solomon code over $\backslash mathbb\{F\}\_\{2^m\}$ can correct any combination of

$$\backslash frac\{t\}\{1+\backslash lfloor\; (l+m-2)/m\; \backslash rfloor\}$$

or fewer bursts of length $l$, on top of being able to correct $t$-random worst case errors.

Let $G$ be a $[255,223,33]$ RS code over $\backslash mathbb\{F\}\_\{2^8\}$. This code was employed by NASA in their Cassini-Huygens spacecraft.{{cite web |url=http://quest.arc.nasa.gov/saturn/qa/cassini/Error_correction.txt |title=Cassini: What kind of error correction? |date=1999 |website=quest.arc.nasa.gov |archive-url=https://web.archive.org/web/20120627022807/http://quest.arc.nasa.gov/saturn/qa/cassini/Error_correction.txt |archive-date=2012-06-27}} It is capable of correcting $\backslash lfloor\; 33/2\; \backslash rfloor\; =\; 16$ symbol errors. We now construct a Binary RS Code $G\text{'}$ from $G$. Each symbol will be written using $\backslash lceil\; \backslash log\_2(255)\; \backslash rceil\; =\; 8$ bits. Therefore, the Binary RS code will have $[2040,1784,33]\_2$ as its parameters. It is capable of correcting any single burst of length $l\; =\; 121$.

Interleaving is used to convert convolutional codes from random error correctors to burst error correctors. The basic idea behind the use of interleaved codes is to jumble symbols at the transmitter. This leads to randomization of bursts of received errors which are closely located and we can then apply the analysis for random channel. Thus, the main function performed by the interleaver at transmitter is to alter the input symbol sequence. At the receiver, the deinterleaver will alter the received sequence to get back the original unaltered sequence at the transmitter.

File:Row_and_column_major_order.svg

{{math theorem | math_statement = If the burst error correcting ability of some code is $\backslash ell,$ then the burst error correcting ability of its $\backslash lambda$-way interleave is $\backslash lambda\; \backslash ell.$

{{math proof | proof = Suppose that we have an $(n,\; k)$ code that can correct all bursts of length $\backslash leqslant\; \backslash ell.$ Interleaving can provide us with a $(\backslash lambda\; n,\; \backslash lambda\; k)$ code that can correct all bursts of length $\backslash leqslant\; \backslash lambda\; \backslash ell,$ for any given $\backslash lambda$. If we want to encode a message of an arbitrary length using interleaving, first we divide it into blocks of length $\backslash lambda\; k$. We write the $\backslash lambda\; k$ entries of each block into a $\backslash lambda\; \backslash times\; k$ matrix using row-major order. Then, we encode each row using the $(n,\; k)$ code. What we will get is a $\backslash lambda\; \backslash times\; n$ matrix. Now, this matrix is read out and transmitted in column-major order. The trick is that if there occurs a burst of length $h$ in the transmitted word, then each row will contain approximately $\backslash tfrac\{h\}\{\backslash lambda\}$ consecutive errors (More specifically, each row will contain a burst of length at least $\backslash lfloor\backslash tfrac\{h\}\{\backslash lambda\}\backslash rfloor$ and at most $\backslash lceil\backslash tfrac\{h\}\{\backslash lambda\}\backslash rceil$). If $h\; \backslash leqslant\; \backslash lambda\; \backslash ell,$ then $\backslash tfrac\{h\}\{\backslash lambda\}\; \backslash leqslant\; \backslash ell$ and the $(n,\; k)$ code can correct each row. Therefore, the interleaved $(\backslash lambda\; n,\; \backslash lambda\; k)$ code can correct the burst of length $h$. Conversely, if $h\; >\; \backslash lambda\; \backslash ell,$ then at least one row will contain more than $\backslash tfrac\{h\}\{\backslash lambda\}$ consecutive errors, and the $(n,\; k)$ code might fail to correct them. Therefore, the error correcting ability of the interleaved $(\backslash lambda\; n,\; \backslash lambda\; k)$ code is exactly $\backslash lambda\; \backslash ell.$ The BEC efficiency of the interleaved code remains the same as the original $(n,\; k)$ code. This is true because:

$$\backslash frac\{2\backslash lambda\; \backslash ell\}\{\backslash lambda\; n\; -\; \backslash lambda\; k\}=\; \backslash frac\{2\backslash ell\}\{n-k\}$$}}

}}

The figure below shows a 4 by 3 interleaver.

File:Block,Interleaver,Example.jpg

The above interleaver is called as a block interleaver. Here, the input symbols are written sequentially in the rows and the output symbols are obtained by reading the columns sequentially. Thus, this is in the form of $M\; \backslash times\; N$ array. Generally, $N$ is length of the codeword.

Capacity of block interleaver: For an $M\; \backslash times\; N$ block interleaver and burst of length $\backslash ell,$ the upper limit on number of errors is $\backslash tfrac\{\backslash ell\}\{M\}.$ This is obvious from the fact that we are reading the output column wise and the number of rows is $M$. By the theorem above for error correction capacity up to $t,$ the maximum burst length allowed is $Mt.$ For burst length of $Mt+1$, the decoder may fail.

Efficiency of block interleaver ($\backslash gamma$): It is found by taking ratio of burst length where decoder may fail to the interleaver memory. Thus, we can formulate $\backslash gamma$ as

$$\backslash gamma=\backslash frac\{Mt+1\}\{MN\}\; \backslash approx\; \backslash frac\{t\}\{N\}.$$

Drawbacks of block interleaver : As it is clear from the figure, the columns are read sequentially, the receiver can interpret single row only after it receives complete message and not before that. Also, the receiver requires a considerable amount of memory in order to store the received symbols and has to store the complete message. Thus, these factors give rise to two drawbacks, one is the latency and other is the storage (fairly large amount of memory). These drawbacks can be avoided by using the convolutional interleaver described below.

Cross interleaver is a kind of multiplexer-demultiplexer system. In this system, delay lines are used to progressively increase length. Delay line is basically an electronic circuit used to delay the signal by certain time duration. Let $n$ be the number of delay lines and $d$ be the number of symbols introduced by each delay line. Thus, the separation between consecutive inputs = $nd$ symbols. Let the length of codeword $\backslash leqslant\; n.$ Thus, each symbol in the input codeword will be on distinct delay line. Let a burst error of length $\backslash ell$ occur. Since the separation between consecutive symbols is $nd,$ the number of errors that the deinterleaved output may contain is $\backslash tfrac\{\backslash ell\}\{nd+1\}.$ By the theorem above, for error correction capacity up to $t$, maximum burst length allowed is $(nd+1)(t-1).$ For burst length of $(nd+1)\; (t-1)\; +\; 1,$ decoder may fail.

File:Convolutional,Interleaver,Example.jpg

File:Deinterleaver,Example.jpg

Efficiency of cross interleaver ($\backslash gamma$): It is found by taking the ratio of burst length where decoder may fail to the interleaver memory. In this case, the memory of interleaver can be calculated as

$$(0\; +\; 1\; +\; 2\; +\; 3\; +\; \backslash cdots\; +\; (n-1))d\; =\; \backslash frac\{n(n-1)\}\{2\}\; d.$$

Thus, we can formulate $\backslash gamma$ as follows:

$$\backslash gamma\; =\; \backslash frac\{(nd+1)(t-1)+1\}\{\backslash frac\{n(n-1)\}\{2\}d\}.$$

Performance of cross interleaver : As shown in the above interleaver figure, the output is nothing but the diagonal symbols generated at the end of each delay line. In this case, when the input multiplexer switch completes around half switching, we can read first row at the receiver. Thus, we need to store maximum of around half message at receiver in order to read first row. This drastically brings down the storage requirement by half. Since just half message is now required to read first row, the latency is also reduced by half which is good improvement over the block interleaver. Thus, the total interleaver memory is split between transmitter and receiver.

Without error correcting codes, digital audio would not be technically feasible.Algebraic Error Control Codes (Autumn 2012) – Handouts from Stanford University The Reed–Solomon codes can correct a corrupted symbol with a single bit error just as easily as it can correct a symbol with all bits wrong. This makes the RS codes particularly suitable for correcting burst errors. By far, the most common application of RS codes is in compact discs. In addition to basic error correction provided by RS codes, protection against burst errors due to scratches on the disc is provided by a cross interleaver.

Current compact disc digital audio system was developed by N. V. Philips of The Netherlands and Sony Corporation of Japan (agreement signed in 1979).

A compact disc comprises a 120 mm aluminized disc coated with a clear plastic coating, with spiral track, approximately 5 km in length, which is optically scanned by a laser of wavelength ~0.8 μm, at a constant speed of ~1.25 m/s. For achieving this constant speed, rotation of the disc is varied from ~8 rev/s while scanning at the inner portion of the track to ~3.5 rev/s at the outer portion. Pits and lands are the depressions (0.12 μm deep) and flat segments constituting the binary data along the track (0.6 μm width).{{cite book |last=McEliece |first=Robert J. |title=The Theory of Information and Coding: A Mathematical Framework for Communication |publisher=Addison-Wesley |series=Advanced Book Program |date=1977}}

The CD process can be abstracted as a sequence of the following sub-processes:

• Channel encoding of source of signals
• Mechanical sub-processes of preparing a master disc, producing user discs and sensing the signals embedded on user discs while playing – the channel
• Decoding the signals sensed from user discs

The process is subject to both burst errors and random errors. Burst errors include those due to disc material (defects of aluminum reflecting film, poor reflective index of transparent disc material), disc production (faults during disc forming and disc cutting etc.), disc handling (scratches – generally thin, radial and orthogonal to direction of recording) and variations in play-back mechanism. Random errors include those due to jitter of reconstructed signal wave and interference in signal. CIRC (Cross-Interleaved Reed–Solomon code) is the basis for error detection and correction in the CD process. It corrects error bursts up to 3,500 bits in sequence (2.4 mm in length as seen on CD surface) and compensates for error bursts up to 12,000 bits (8.5 mm) that may be caused by minor scratches.

Encoding: Sound-waves are sampled and converted to digital form by an A/D converter. The sound wave is sampled for amplitude (at 44.1 kHz or 44,100 pairs, one each for the left and right channels of the stereo sound). The amplitude at an instance is assigned a binary string of length 16. Thus, each sample produces two binary vectors from $\backslash mathbb\{F\}\_2^\{16\}$ or 4 $\backslash mathbb\{F\}\_2^\{8\}$ bytes of data. Every second of sound recorded results in 44,100 × 32 = 1,411,200 bits (176,400 bytes) of data. The 1.41 Mbit/s sampled data stream passes through the error correction system eventually getting converted to a stream of 1.88 Mbit/s.

Input for the encoder consists of input frames each of 24 8-bit symbols (12 16-bit samples from the A/D converter, 6 each from left and right data (sound) sources). A frame can be represented by $L\_1\; R\_1\; L\_2\; R\_2\; \backslash ldots\; L\_6\; R\_6$ where $L\_i$ and $R\_i$ are bytes from the left and right channels from the $i^\{th\}$ sample of the frame.

Initially, the bytes are permuted to form new frames represented by $L\_1\; L\_3\; L\_5\; R\_1\; R\_3\; R\_5\; L\_2\; L\_4\; L\_6\; R\_2\; R\_4\; R\_6$ where $L\_i,R\_i$ represent $i$-th left and right samples from the frame after 2 intervening frames.

Next, these 24 message symbols are encoded using C2 (28,24,5) Reed–Solomon code which is a shortened RS code over $\backslash mathbb\{F\}\_\{256\}$. This is two-error-correcting, being of minimum distance 5. This adds 4 bytes of redundancy, $P\_1\; P\_2$ forming a new frame: $L\_1\; L\_3\; L\_5\; R\_1\; R\_3\; R\_5\; P\_1\; P\_2\; L\_2\; L\_4\; L\_6\; R\_2\; R\_4\; R\_6$. The resulting 28-symbol codeword is passed through a (28.4) cross interleaver leading to 28 interleaved symbols. These are then passed through C1 (32,28,5) RS code, resulting in codewords of 32 coded output symbols. Further regrouping of odd numbered symbols of a codeword with even numbered symbols of the next codeword is done to break up any short bursts that may still be present after the above 4-frame delay interleaving. Thus, for every 24 input symbols there will be 32 output symbols giving $R\; =\; 24/32$. Finally one byte of control and display information is added. Each of the 33 bytes is then converted to 17 bits through EFM (eight to fourteen modulation) and addition of 3 merge bits. Therefore, the frame of six samples results in 33 bytes × 17 bits (561 bits) to which are added 24 synchronization bits and 3 merging bits yielding a total of 588 bits.

Decoding: The CD player (CIRC decoder) receives the 32 output symbol data stream. This stream passes through the decoder D1 first. It is up to individual designers of CD systems to decide on decoding methods and optimize their product performance. Being of minimum distance 5 The D1, D2 decoders can each correct a combination of $e$ errors and $f$ erasures such that . In most decoding solutions, D1 is designed to correct single error. And in case of more than 1 error, this decoder outputs 28 erasures. The deinterleaver at the succeeding stage distributes these erasures across 28 D2 codewords. Again in most solutions, D2 is set to deal with erasures only (a simpler and less expensive solution). If more than 4 erasures were to be encountered, 24 erasures are output by D2. Thereafter, an error concealment system attempts to interpolate (from neighboring symbols) in case of uncorrectable symbols, failing which sounds corresponding to such erroneous symbols get muted.

Performance of CIRC: CIRC conceals long bust errors by simple linear interpolation. 2.5 mm of track length (4000 bits) is the maximum completely correctable burst length. 7.7 mm track length (12,300 bits) is the maximum burst length that can be interpolated. Sample interpolation rate is one every 10 hours at Bit Error Rate (BER) $=\; 10^\{-4\}$ and 1000 samples per minute at BER = $10^\{-3\}$ Undetectable error samples (clicks): less than one every 750 hours at BER = $10^\{-3\}$ and negligible at BER = $10^\{-4\}$.

• Error detection and correction
• Error-correcting codes with feedback
• Code rate
• Reed–Solomon error correction

{{Reflist|33em}}

Category:Coding theory

Category:Error detection and correction

Category:Computer errors