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
Say a codeword is transmitted, and it is received as Then, the error vector is called a burst of length if the nonzero components of are confined to consecutive components. For example, is a burst of length
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
An error vector is called a cyclic burst error of length if its nonzero components are confined to cyclically consecutive components. For example, the previously considered error vector , is a cyclic burst of length , since we consider the error starting at position and ending at position . Notice the indices are -based, that is, the first element is at position .
For the remainder of this article, we will use the term burst to refer to a cyclic burst, unless noted otherwise.
Burst description 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 where 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 is the location, on the codeword, where the burst can be found.
For example, the burst description of the error pattern is . Notice that such description is not unique, because describes the same burst error. In general, if the number of nonzero components in is , then will have different burst descriptions each starting at a different nonzero entry of . 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 is denoted by
A corollary of the above theorem is that we cannot have two distinct burst descriptions for bursts of length
Cyclic codes for burst error correction
Cyclic codes are defined as follows: think of the symbols as elements in . Now, we can think of words as polynomials over 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 . Suppose that the generator polynomial has degree . Polynomials of degree that are divisible by result from multiplying by polynomials of degree . We have such polynomials. Each one of them corresponds to a codeword. Therefore, for cyclic codes.
Cyclic codes can detect all bursts of length up to . We will see later that the burst error detection ability of any code is bounded from above by . Cyclic codes are considered optimal for burst error detection since they meet this upper bound:
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 ), compute the remainder of this word when divided by . If the remainder is zero (i.e. if the word is divisible by ), 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 (i.e. it is going to be a valid codeword).
By the upper bound on burst error detection (), we know that a cyclic code can not detect all bursts of length . However cyclic codes can indeed detect most bursts of length . The reason is that detection fails only when the burst is divisible by . Over binary alphabets, there exist bursts of length . Out of those, only are divisible by . Therefore, the detection failure probability is very small () assuming a uniform distribution over all bursts of length .
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.
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 code that can detect all burst errors of length A natural question to ask is: given and , what is the maximum that we can never achieve beyond? In other words, what is the upper bound on the length of bursts that we can detect using any code? The following theorem provides an answer to this question.
Now, we repeat the same question but for error correction: given and , what is the upper bound on the length of bursts that we can correct using any code? The following theorem provides a preliminary answer to this question:
A stronger result is given by 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.
Remark. is called the redundancy of the code and in an alternative formulation for the Abramson's bounds is
Fire codes
Sources:
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 , we mean that all errors that a received codeword possess lie within a fixed span of digits.
Let be an irreducible polynomial of degree over , and let be the period of . The period of , and indeed of any polynomial, is defined to be the least positive integer such that Let be a positive integer satisfying and not divisible by , where and are the degree and period of , respectively. Define the Fire Code by the following generator polynomial:
We will show that is an -burst-error correcting code.
If we can show that all bursts of length 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.
Proof of Theorem Let and be polynomials with degrees and , representing bursts of length and respectively with The integers represent the starting positions of the bursts, and are less than the block length of the code. For contradiction sake, assume that and are in the same coset. Then, is a valid codeword (since both terms are in the same coset). Without loss of generality, pick . By the division theorem we can write: for integers and . We rewrite the polynomial as follows:
Notice that at the second manipulation, we introduced the term . We are allowed to do so, since Fire Codes operate on . By our assumption, is a valid codeword, and thus, must be a multiple of . As mentioned earlier, since the factors of are relatively prime, has to be divisible by . Looking closely at the last expression derived for we notice that is divisible by (by the corollary of Lemma 2). Therefore, is either divisible by or is . Applying the division theorem again, we see that there exists a polynomial with degree such that:
Then we may write:
Equating the degree of both sides, gives us Since we can conclude which implies and . Notice that in the expansion:
The term appears, but since , the resulting expression does not contain , therefore and subsequently This requires that , and . We can further revise our division of by to reflect that is Substituting back into gives us,
Since , we have . But is irreducible, therefore and must be relatively prime. Since is a codeword, must be divisible by , as it cannot be divisible by . Therefore, must be a multiple of . But it must also be a multiple of , which implies it must be a multiple of but that is precisely the block-length of the code. Therefore, cannot be a multiple of since they are both less than . Thus, our assumption of being a codeword is incorrect, and therefore and are in different cosets, with unique syndromes, and therefore correctable.
Example: 5-burst error correcting fire code With the theory presented in the above section, consider the construction of a -burst error correcting Fire Code. Remember that to construct a Fire Code, we need an irreducible polynomial , an integer , representing the burst error correction capability of our code, and we need to satisfy the property that is not divisible by the period of . With these requirements in mind, consider the irreducible polynomial , and let . Since is a primitive polynomial, its period is . We confirm that is not divisible by . Thus,
is a Fire Code generator. We can calculate the block-length of the code by evaluating the least common multiple of and . In other words, . Thus, the Fire Code above is a cyclic code capable of correcting any burst of length or less.
Binary Reed–Solomon codes 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 . Each symbol of the alphabet can be represented by bits. If is an Reed–Solomon code over , we can think of as an code over .
The reason such codes are powerful for burst error correction is that each symbol is represented by bits, and in general, it is irrelevant how many of those bits are erroneous; whether a single bit, or all of the 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 errors can affect at most symbols, and a burst of can affect at most symbols. Then, a burst of can affect at most symbols; this implies that a -symbols-error correcting code can correct a burst of length at most .
In general, a -error correcting Reed–Solomon code over can correct any combination of
or fewer bursts of length , on top of being able to correct -random worst case errors.
An example of a binary RS code