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. 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. 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.
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. 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. Each one of them corresponds to a codeword.
Cyclic codes are considered optimal for burst error detection since they meet this upper bound:. If the remainder is zero i. Otherwise, report an error. To correct this error, subtract this remainder from the transmitted word. 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.
By upper bound, we mean a limit on our error detection ability that we can never go beyond. The following theorem provides an answer to this question. The following theorem provides a preliminary answer to this question:. 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.
error control coding convolutional codes
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.
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.
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. Notice that in the expansion:. 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. 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. 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. 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.
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. In this case, the memory of interleaver can be calculated as.
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. This makes the RS codes particularly suitable for correcting burst errors.
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. Pits and lands are the depressions 0. The process is subject to both burst errors and random errors. Random errors include those due to jitter of reconstructed signal wave and interference in signal. It corrects error bursts up to 3, bits in sequence 2. The sound wave is sampled for amplitude at The amplitude at an instance is assigned a binary string of length This is two-error-correcting, being of minimum distance 5.
The resulting symbol codeword is passed through a These are then passed through C1 32,28,5 RS code, resulting in codewords of 32 coded output symbols.
Burst error-correcting code
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. Finally one byte of control and display information is added. 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.
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. From Wikipedia, the free encyclopedia.
An example of a block interleaver. An example of a convolutional interleaver. An example of a deinterleaver. Coding Theory: A First Course.
Hoboken, NJ: Wiley-Interscience, Error Control Coding: Fundamentals and Applications. Categories : Coding theory Error detection and correction Computer errors.
Hidden categories: Webarchive template wayback links.
Burst error correcting convolutional codes pdf converter