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 Failed to parse (unknown function "\e"): {\displaystyle \textstyle \e (n+1)/2} .