Burst error-correcting code

In coding theory, burst error-correcting codes employ methods of correcting burst errors, which are errors that occur in many consecutive bits rather than occurring in bits independently of each other.

Many codes have been designed to correct random errors. Sometimes, however, channels may introduce errors which are localized in a short interval. Such errors occur in a burst (called burst errors) because they occur in many consecutive bits. Examples of burst errors can be found extensively in storage mediums. These errors may be due to physical damage such as scratch on a disc or a stroke of lightning in case of wireless channels. They are not independent; they tend to be spatially concentrated. If one bit has an error, it is likely that the adjacent bits could also be corrupted. The methods used to correct random errors are inefficient to correct burst errors.

Definitions

A burst of length $\ell$

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 $\ell$ if the nonzero components of $E$ are confined to $\ell$ consecutive components. For example, $E=(0{\textbf {1000011}}0)$ is a burst of length $\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 $\ell$

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\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:

${\begin{aligned}n-w={\text{number of zeros in }}E&=(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{aligned}}$

This contradicts $w\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 ${\tfrac {1}{2}}(n+1).$

Cyclic codes for burst error correction

Cyclic codes are defined as follows: think of the $q$ symbols as elements in $\mathbb {F} _{q}$. Now, we can think of words as polynomials over $\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 $\leqslant n-1$. Suppose that the generator polynomial $g(x)$ has degree $r$. Polynomials of degree $\leqslant n-1$ that are divisible by $g(x)$ result from multiplying $g(x)$ by polynomials of degree $\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 $\ell =n-k=r$. We will see later that the burst error detection ability of any $(n,k)$ code is bounded from above by $\ell \leqslant n-k$. Cyclic codes are considered optimal for burst error detection since they meet this upper bound:

Theorem (Cyclic burst correction capability). Every cyclic code with generator polynomial of degree $r$ can detect all bursts of length $\leqslant r.$

Proof. We need to prove that if you add a burst of length $\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 $\leqslant r$ is divisible by $g(x)$. Such a burst has the form $x^{i}b(x)$, where $\deg(b(x))<r.$ 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 $\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 ($\ell \leqslant n-k=r$), we know that a cyclic code can not detect all bursts of length $\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^{\ell -2}$ bursts of length $\ell$. Out of those, only $2^{\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 $\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.

Theorem (Distinct Cosets). A linear code $C$ is an $\ell$-burst-error-correcting code if all the burst errors of length $\leqslant \ell$ lie in distinct cosets of $C$.

Proof. Let $\mathbf {e} _{1},\mathbf {e} _{2}$ be distinct burst errors of length $\leqslant \ell$ which lie in same coset of code $C$. Then $\mathbf {c} =\mathbf {e} _{1}-\mathbf {e} _{2}$ is a codeword. Hence, if we receive $\mathbf {e} _{1},$ we can decode it either to $\mathbf {0}$ or $\mathbf {c}$. In contrast, if all the burst errors $\mathbf {e} _{1}$ and $\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 $\ell$-burst-error-correcting code if and only if all the burst errors of length $\leqslant \ell$ lie in distinct cosets of $C$.

Theorem (Burst error codeword classification). Let $C$ be a linear $\ell$-burst-error-correcting code. Then no nonzero burst of length $\leqslant 2\ell$ can be a codeword.

Proof. Let $c$ be a codeword with a burst of length $\leqslant 2\ell$. Thus it has the pattern $(0,1,u,v,1,0)$, where $u$ and $v$ are words of length $\leqslant \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 $\leqslant \ell$. For binary linear codes, they belong to the same coset. This contradicts the Distinct Cosets Theorem, therefore no nonzero burst of length $\leqslant 2\ell$ can be a codeword.

Burst error correction bounds

Upper bounds on burst error detection and correction

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leqslant \ell.} A natural question to ask is: given Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} and $k$, what is the maximum Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell} that we can never achieve beyond? In other words, what is the upper bound on the length $\ell$ of bursts that we can detect using any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n, k)} code? The following theorem provides an answer to this question.

Theorem (Burst error detection ability). The burst error detection ability of any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n, k)} code is $\ell \leqslant n-k.$

Proof. First we observe that a code can detect all bursts of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leqslant \ell} if and only if no two codewords differ by a burst of length $\leqslant \ell$. Suppose that we have two code words Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{c}_1} and $\mathbf {c} _{2}$ that differ by a burst Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{b}} of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leqslant \ell} . Upon receiving $\mathbf {c} _{1}$, we can not tell whether the transmitted word is indeed Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{c}_1} with no transmission errors, or whether it is $\mathbf {c} _{2}$ with a burst error Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{b}} that occurred during transmission. Now, suppose that every two codewords differ by more than a burst of length $\ell .$ Even if the transmitted codeword Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{c}_1} is hit by a burst Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{b}} of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell} , it is not going to change into another valid codeword. Upon receiving it, we can tell that this is $\mathbf {c} _{1}$ with a burst Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{b}.} By the above observation, we know that no two codewords can share the first Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-\ell} symbols. The reason is that even if they differ in all the other Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell} symbols, they are still going to be different by a burst of length $\ell .$ Therefore, the number of codewords Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q^k} satisfies $q^{k}\leqslant q^{n-\ell }.$ Applying Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log_q} to both sides and rearranging, we can see that $\ell \leqslant n-k$.

Now, we repeat the same question but for error correction: given Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} and $k$, what is the upper bound on the length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell} of bursts that we can correct using any $(n,k)$ code? The following theorem provides a preliminary answer to this question:

Theorem (Burst error correction ability). The burst error correction ability of any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n, k)} code satisfies Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell \leqslant n-k-\log_q (n-\ell)+2}

Proof. First we observe that a code can correct all bursts of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leqslant \ell} if and only if no two codewords differ by the sum of two bursts of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leqslant \ell.} Suppose that two codewords $\mathbf {c} _{1}$ and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{c}_2} differ by bursts $\mathbf {b} _{1}$ and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{b}_2} of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leqslant \ell} each. Upon receiving $\mathbf {c} _{1}$ hit by a burst Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{b}_1} , we could interpret that as if it was Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{c}_2} hit by a burst $-\mathbf {b} _{2}$. We can not tell whether the transmitted word is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{c}_1} or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{c}_2} . Now, suppose that every two codewords differ by more than two bursts of length $\ell$. Even if the transmitted codeword Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{c}_1} is hit by a burst of length $\ell$, it is not going to look like another codeword that has been hit by another burst. For each codeword Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{c},} let $B(\mathbf {c} )$ denote the set of all words that differ from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{c}} by a burst of length $\leqslant \ell .$ Notice that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B(\mathbf{c})} includes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{c}} itself. By the above observation, we know that for two different codewords $\mathbf {c} _{i}$ and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{c}_j, B(\mathbf{c}_i)} and $B(\mathbf {c} _{j})$ are disjoint. We have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q^k} codewords. Therefore, we can say that $q^{k}|B(\mathbf {c} )|\leqslant q^{n}$. Moreover, we have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n-\ell)q^{\ell-2} \leqslant |B(\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:

Theorem (Rieger bound). If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell} is the burst error correcting ability of an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n, k)} linear block code, then $2\ell \leqslant n-k$.

Proof. Any linear code that can correct any burst pattern of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leqslant \ell} cannot have a burst of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leqslant 2\ell} as a codeword. If it had a burst of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leqslant 2\ell} as a codeword, then a burst of length $\ell$ could change the codeword to a burst pattern of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell} , which also could be obtained by making a burst error of length $\ell$ in all zero codeword. If vectors are non-zero in first Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q^{2\ell}} . Hence, we have at least $2\ell$ distinct symbols, otherwise, the difference of two such polynomials would be a codeword that is a sum of two bursts of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leqslant \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.

Further bounds on burst error correction

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.

Theorem (number of bursts). For $1\leqslant \ell \leqslant {\tfrac {1}{2}}(n+1),$ over a binary alphabet, there are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n2^{\ell-1}+1} vectors of length $n$ which are bursts of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leqslant \ell} .==

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 $\ell$, we mean that all errors that a received codeword possess lie within a fixed span of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell} digits.

Let $p(x)$ be an irreducible polynomial of degree Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_2} , and let $p$ be the period of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p(x)} . The period of $p(x)$, and indeed of any polynomial, is defined to be the least positive integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} such that $p(x)|x^{r}-1.$ Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell} be a positive integer satisfying $\ell \leqslant m$ and $2\ell -1$ not divisible by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} , where $p$ is the period of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p(x)} . Define the Fire Code Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} by the following generator polynomial:

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

We will show that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} is an $\ell$-burst-error correcting code.

Lemma 1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd \left (p(x), x^{2\ell -1}+1 \right ) = 1.}

Proof. Let $d(x)$ be the greatest common divisor of the two polynomials. Since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p(x)} is irreducible, $\deg(d(x))=0$ or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \deg(p(x))} . Assume $\deg(d(x))\neq 0,$ then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p(x) = c d(x)} for some constant Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} . But, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1/c)p(x)} is a divisor of $x^{2\ell -1}+1$ since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d(x)} is a divisor of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^{2\ell -1}+1} . But this contradicts our assumption that $p(x)$ does not divide Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^{2\ell -1}+1.} Thus, $\deg(d(x))=0,$ proving the lemma.

Lemma 2. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p(x)} is a polynomial of period Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p(x)|x^k-1} if and only if $p|k.$

Proof. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p|k} , then $x^{k}-1=(x^{p}-1)(1+x^{p}+x^{2p}+\ldots +x^{k/p})$. Thus, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p(x)|x^k-1.}

Now suppose $p(x)|x^{k}-1$. Then, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k \geqslant p} . We show that $k$ is divisible by $p$ by induction on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} . The base case $k=p$ follows. Therefore, assume Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k > p} . We know that $p(x)$ divides both (since it has period Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} )

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^p -1 = (x-1) \left (1 + x + \ldots + x^{p-1} \right ) \quad \text{and} \quad x^k - 1 = (x-1) \left (1 + x + \ldots + x^{k-1} \right ).}

But Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p(x)} is irreducible, therefore it must divide both $(1+x+\ldots +x^{p-1})$ and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1 + x + \ldots + x^{k-1})} ; thus, it also divides the difference of the last two polynomials, $x^{p}(1+x+\ldots +x^{p-k-1})$. Then, it follows that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p(x)} divides $(1+x+\cdots +x^{p-k-1})$. Finally, it also divides: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^{k-p}-1 = (x-1)(1 + x + \ldots + x^{p-k-1})} . By the induction hypothesis, $p|k-p$, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p | k} .

A corollary to Lemma 2 is that since $p(x)=x^{p}-1$ has period Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p(x)} divides $x^{k}-1$ if and only if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p|k} .

Theorem. The Fire Code is $\ell$-burst error correcting It is capable of correcting Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lfloor 33/2 \rfloor = 16} symbol errors. We now construct a Binary RS Code Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G'} from $G$. Each symbol will be written using Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lceil \log_2(255) \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle l = 121} .

Interleaved codes

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 receiver. 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.

Burst error correcting capacity of interleaver

Theorem. If the burst error correcting ability of some code is $\ell ,$ then the burst error correcting ability of its Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda} -way interleave is $\lambda \ell .$

Proof: Suppose that we have an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n, k)} code that can correct all bursts of length $\leqslant \ell .$ Interleaving can provide us with a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\lambda n, \lambda k)} code that can correct all bursts of length $\leqslant \lambda \ell ,$ for any given Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda} . If we want to encode a message of an arbitrary length using interleaving, first we divide it into blocks of length $\lambda k$. We write the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda k} entries of each block into a $\lambda \times k$ matrix using row-major order. Then, we encode each row using the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n, k)} code. What we will get is a $\lambda \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h} in the transmitted word, then each row will contain approximately ${\tfrac {h}{\lambda }}$ consecutive errors (More specifically, each row will contain a burst of length at least Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lfloor\tfrac{h}{\lambda}\rfloor} and at most $\lceil {\tfrac {h}{\lambda }}\rceil$). If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h \leqslant \lambda \ell,} then ${\tfrac {h}{\lambda }}\leqslant \ell$ and the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n, k)} code can correct each row. Therefore, the interleaved $(\lambda n,\lambda k)$ code can correct the burst of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h} . Conversely, if $h>\lambda \ell ,$ then at least one row will contain more than ${\tfrac {h}{\lambda }}$ consecutive errors, and the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n, k)} code might fail to correct them. Therefore, the error correcting ability of the interleaved $(\lambda n,\lambda k)$ code is exactly Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda \ell.} The BEC efficiency of the interleaved code remains the same as the original $(n,k)$ code. This is true because:

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

Block interleaver

The figure below shows a 4 by 3 interleaver.

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M \times N} array. Generally, $N$ is length of the codeword.

Capacity of block interleaver: For an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M \times N} block interleaver and burst of length $\ell ,$ the upper limit on number of errors is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac{\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t,} the maximum burst length allowed is $Mt.$ For burst length of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Mt+1} , the decoder may fail.

Efficiency of block interleaver ($\gamma$): It is found by taking ratio of burst length where decoder may fail to the interleaver memory. Thus, we can formulate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma} as

$\gamma ={\frac {Mt+1}{MN}}\approx {\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.

Convolutional interleaver

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 = Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle nd} symbols Let the length of codeword $\leqslant n.$ Thus, each symbol in the input codeword will be on distinct delay line. Let a burst error of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell} occur. Since the separation between consecutive symbols is $nd,$ the number of errors that the deinterleaved output may contain is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac{\ell}{nd+1}.} By the theorem above, for error correction capacity up to $t$, maximum burst length allowed is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (nd+1)(t-1).} For burst length of $(nd+1)(t-1)+1,$ decoder may fail.

Efficiency of cross interleaver (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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+\cdots +(n-1))d={\frac {n(n-1)}{2}}d.$

Thus, we can formulate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma} as follows:

$\gamma ={\frac {(nd+1)(t-1)+1}{{\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.

Applications

Compact disc

Without error correcting codes, digital audio would not be technically feasible. 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.

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_2^{16}} or 4 $\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_1 R_1 L_2 R_2 \ldots L_6 R_6} where $L_{i}$ and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 $\mathbb {F} _{256}$. This is two-error-correcting, being of minimum distance 5. This adds 4 bytes of redundancy, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_1 P_2} forming a new frame: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} errors and $f$ erasures such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2e+f<5} . 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 deinterlever 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 = Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 10^{-3}} Undetectable error samples (clicks): less than one every 750 hours at BER = $10^{-3}$ and negligible at BER = Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 10^{-4}} .

See also

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

Source

http://wikipedia.org/