User:Script3r/sandbox

Motivation

There are many codes that 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 as burst errors because they are 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 channel. 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. This motivates burst error correcting codes.

Definitions

A burst of length $\textstyle l$ [8]

Say a codeword $\textstyle C$ is transmitted, and it is received as $\textstyle Y=C+E$. Then, the error vector $\textstyle E$ is called a burst of length $\textstyle l$ if the number of nonzero components of $\textstyle E$ is confined to $\textstyle l$ consecutive components. For example, $\textstyle E=(0{\textbf {1000011}}0)$ is a burst of length $\textstyle l=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 $\textstyle l$ [8]

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

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

Burst description [8]

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 a burst description to be a tuple $\textstyle (P,L)$ where $\textstyle 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 $\textstyle L$ is the location, on the codeword, where the burst can be found.

For example, the burst description of the error pattern $\textstyle E=(010000110)$ is $\textstyle D=(1000011,1)$. Notice that such description is not unique, because $\textstyle D'=(11001,6)$ is describing the same burst error. In general, if the number of nonzero components in $\textstyle E$ is $\textstyle w$, then $\textstyle E$ will have $\textstyle w$ different burst descriptions (each starting at a different nonzero entry of $\textstyle E$).

We now present a theorem that remedies some of the issues that arise by the ambiguity of burst descriptions.

Theorem: Uniqueness of burst descriptions

If $\textstyle E$ is an error vector of length $\textstyle n$ with two burst descriptions $\textstyle (P_{1},L_{1})$ and $\textstyle (P_{2},L_{2})$. If $\textstyle length(P_{1})+length(P_{2})\leq n+1$ (where $\textstyle length(y)$ is the number of symbols in the error pattern $\textstyle y$), then the two descriptions are identical (that is, their components are equivalent) [2]

Proof: Let $\textstyle w$ be the weight (or the number of nonzero entries) of $\textstyle E$. Then $\textstyle E$ has exactly $\textstyle w$ error descriptions. For $\textstyle w=0$ or $\textstyle w=1$, there is nothing prove. So, we consider the cases where $\textstyle w\geq 2$. Assume that the descriptions are not identical. We notice that each nonzero entry of $\textstyle E$ will appear in the pattern, and so, the components of $\textstyle E$ not included in the pattern will form a cyclic run of 0's, 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. Let's consider the zero runs for the error pattern $\textstyle E=(010000110)$.

We immediately observe that each burst description has a zero run associated with it. But most importantly, we notice that each zero run is disjoint. Since we have $\textstyle w$ zero runs, and each is disjoint, if we count the number of distinct elements in all the zero runs, we get we have a total of $\textstyle n-w$. With this observation in mind, we have a total of $\textstyle (n-length(P_{1}))+length(n-length(P_{2}))$ zeros in $\textstyle E$. But, since $\textstyle length(P_{1})+length(P_{2})\leq n+1$, this number is $\textstyle \geq n-1$, which contradicts that $\textstyle w\geq 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 $\textstyle (n+1)/2$.

Cyclic Codes for Burst Error Correction

Cyclic Codes are defined as follows: Think of the $\textstyle q$ symbols as elements in $\textstyle \mathbb {F} _{q}$. Now, we can think of words as polynomials over $\textstyle \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 "the generator polynomial." The codewords of this cyclic code are all the polynomials that are divisible by this generator polynomial.

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

Cyclic codes can detect all bursts of length up to $\textstyle l=n-k=r$. We will see later that the burst error detection ability of any $\textstyle (n,k)$ code is upper bounded by $\textstyle l\leq n-k$. Because cyclic codes meet that bound, they are considered optimal for burst error detection. This claim is proved by the following theorem:

Theorem: Cyclic Burst Correction Capability

Every cyclic code with generator polynomial of degree $\textstyle r$ can detect all bursts of length $\textstyle \leq r$.

Proof: To prove this, we need to prove that if you add a burst of length $\textstyle \leq r$ to a codeword (i.e. to a polynomial that is divisible by $\textstyle g(x)$), then the result is not going to be a codeword (i.e. the corresponding polynomial is not going to be divisible by $\textstyle g(x)$). It suffices to show that no burst of length $\textstyle \leq r$ is divisible by $\textstyle g(x)$. Such a burst has the form $\textstyle x^{i}b(x)$, where $\textstyle b(x)$ has degree < $\textstyle r$. Therefore, $\textstyle b(x)$ is not divisible by $\textstyle g(x)$ (because the latter has degree $\textstyle r$). $\textstyle g(x)$ is not divisible by $\textstyle x$ (Otherwise, all codewords would start with $\textstyle 0$). Therefore, $\textstyle x^{i}$ is not divisible by $\textstyle 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 $\textstyle \leq n-1$), compute the remainder of this word when divided by $\textstyle g(x)$. If the remainder is zero (i.e. if the word is divisible by $\textstyle 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 $\textstyle g(x)$ (i.e. it is going to be a valid codeword).

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

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 l-burst-error-correcting code iff all the burst errors of length $\textstyle l$ or less lie in distinct cosets of $\textstyle C$.

Proof: Consider two different burst errors e1 and e2 of length $\textstyle l$ or less which lie in same coset of codeword C. When we take difference between the errors e1 and e2, we get c $\textstyle (c=e1-e2)$ such that c is a code-word. Hence, if we receive e1, we can decode it either to 0 or c. In contrast, if all the burst errors e1 and e2 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 l-burst-error-correcting code if and only if all the burst errors of length $\textstyle l$ or less lie in distinct cosets of C.

Theorem: Burst Error Codeword Classification

Let C be an [n, k]-linear l-burst-error-correcting code. Then no nonzero burst of length $\textstyle 2l$ or less can be a codeword.

Proof: Consider existence of a codeword c which has the burst length less than or equal to $\textstyle 2l$. Thus, c has the pattern $\textstyle (0,1,u,v,1,0)$, where $u$ and $v$ are two words of length ≤ $\textstyle l$ − 1. Hence, the words $\textstyle w=(0,1,u,0,0,0)$ and $\textstyle c$ $\textstyle -$ $\textstyle w=(0,0,0,v,1,0)$ are two bursts of length ≤$\textstyle l$. For binary linear codes, they belong to the same coset. This is a contradiction to Theorem stated above. Thus it follows that no nonzero burst of length $\textstyle 2l$ or less can be a codeword.

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 $\textstyle (n,k)$ code that can detect all burst errors of length $\textstyle \leq l$. A natural question to ask is: given $\textstyle n$ and $\textstyle k$, what is the maximum $\textstyle l$ that we can never achieve beyond? In other words, what is the upper bound on the length $\textstyle l$ of bursts that we can detect using any $\textstyle (n,k)$ code? The following theorem provides an answer to this question.

Theorem: Burst Error Detection Ability

The burst error detection ability of any $\textstyle (n,k)$ code is $\textstyle l\leq n-k$. Proof: To prove this, we start by making the following observation: A code can detect all bursts of length $\textstyle \leq l$ if and only if no two codewords differ by a burst of length $\textstyle \leq l$. Suppose that we have two code words $\textstyle \mathbf {c} _{1}$ and $\textstyle \mathbf {c} _{2}$ that differ by a burst $\textstyle \mathbf {b}$ of length $\textstyle \leq l$. Upon receiving $\textstyle \mathbf {c} _{1}$, we can not tell whether the transmitted word is indeed $\textstyle \mathbf {c} _{1}$ with no transmission errors, or whether it is $\textstyle \mathbf {c} _{2}$ with a burst error $\textstyle \mathbf {b}$ that occurred during transmission. Now, suppose that every two codewords differ by more than a burst of length $\textstyle l$. Even if the transmitted codeword $\textstyle \mathbf {c} _{1}$ is hit by a burst $\textstyle \mathbf {b}$ of length $\textstyle l$, it is not going to change into another valid codeword. Upon receiving it, we can tell that this is $\textstyle \mathbf {c} _{1}$ with a burst $\textstyle \mathbf {b}$. By the above observation, we know that no two codewords can share the first $\textstyle n-l$ symbols. The reason is that even if they differ in all the other $\textstyle l$ symbols, they are still going to be different by a burst of length $\textstyle l$. Therefore, the number of codewords $\textstyle q^{k}$ satisfies $\textstyle q^{k}\leq q^{n-l}$. By taking the logarithm to the base $\textstyle q$ and rearranging, we can see that $\textstyle l\leq n-k$.

Now, we repeat the same question but for error correction: given $\textstyle n$ and $\textstyle k$, what is the upper bound on the length $\textstyle l$ of bursts that we can correct using any $\textstyle (n,k)$ code? The following theorem provides a preliminary answer to this question. However later on, we will see that the Rieger bound is going to provide a stronger answer..

Theorem: Burst Error Correction Ability

The burst error correction ability of any $\textstyle (n,k)$ code satisfies $\textstyle l\leq n-k-\mathrm {log} _{q}(n-l)+2$

Proof: We start with the following observation: A code can correct all bursts of length $\textstyle \leq l$ if and only if no two codewords differ by the sum of two bursts of length $\textstyle \leq l$. Suppose that two codewords $\textstyle \mathbf {c} _{1}$ and $\textstyle \mathbf {c} _{2}$ differ by two bursts $\textstyle \mathbf {b} _{1}$ and $\textstyle \mathbf {b} _{2}$ of length $\textstyle \leq l$ each. Upon receiving $\textstyle \mathbf {c} _{1}$ hit by a burst $\textstyle \mathbf {b} _{1}$, we could interpret that as if it was $\textstyle \mathbf {c} _{2}$ hit by a burst $\textstyle -\mathbf {b} _{2}$. We can not tell whether the transmitted word is $\textstyle \mathbf {c} _{1}$ or $\textstyle \mathbf {c} _{2}$. Now, suppose that every two codewords differ by more than two bursts of length $\textstyle l$. Even if the transmitted codeword $\textstyle \mathbf {c} _{1}$ is hit by a burst of length $\textstyle l$, it is not going to look like another codeword that has been hit by another burst. For each codeword $\textstyle \mathbf {c}$, let $\textstyle B(\mathbf {c} )$ denote the set of all words that differ from $\textstyle \mathbf {c}$ by a burst of length $\textstyle \leq l$. Notice that $\textstyle B(\mathbf {c} )$ includes $\textstyle \mathbf {c}$ itself. By the above observation, we know that for two different codewords $\textstyle \mathbf {c} _{i}$ and $\textstyle \mathbf {c} _{j}$, $\textstyle B(\mathbf {c} _{i})$ and $\textstyle B(\mathbf {c} _{j})$ are disjoint. We have $\textstyle q^{k}$ codewords. Therefore, we can say that $\textstyle q^{k}|B(\mathbf {c} )|\leq q^{n}$. Moreover, we have $\textstyle (n-l)q^{l-2}\leq |B(\mathbf {c} )|$. By plugging the latter inequality into the former, then taking the base $\textstyle q$ logarithm and rearranging, we get the above theorem. This theorem is weaker than the Rieger bound, which we will discuss later.

Rieger Bound

Theorem: The Rieger Bound

If $\textstyle l$ is the burst error correcting ability of an [n, k] linear block code, then $2l\leq n-k$.

Proof: Any linear code that can correct burst pattern of length l or less cannot have a burst of length $\textstyle 2l$ or less as a codeword. If it had burst of length $\textstyle 2l$ or less as a codeword, then a burst of length l could change the codeword to burst pattern of length $\textstyle l$, which also could be obtained by making a burst error of length $\textstyle l$ in all zero codeword. If vectors are non-zero in first $\textstyle 2l$ symbols, then the vectors should be from different subsets of an array so that their difference is not a codeword of bursts of length $\textstyle 2l$. Ensuring this condition, the number of such subsets is at least equal to number of vectors. Thus, number of subsets would be at least $q^{2l}$. Hence, we have at least $\textstyle 2l$ distinct symbols, otherwise, difference of two such polynomials would be a codeword that is a sum of 2 bursts of length ≤ $\textstyle l$. Thus, this proves Rieger Bound. A linear burst-error-correcting code achieving the above Rieger bound is called an optimal burst-error-correcting code.