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 formula_1
Say a codeword formula_2 is transmitted, and it is received as formula_3 Then, the error vector formula_4 is called a burst of length formula_1 if the nonzero components of formula_4 are confined to formula_1 consecutive components. For example, formula_8 is a burst of length formula_9
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 formula_1
An error vector formula_4 is called a cyclic burst error of length formula_1 if its nonzero components are confined to formula_1 cyclically consecutive components. For example, the previously considered error vector formula_14, is a cyclic burst of length formula_15, since we consider the error starting at position formula_16 and ending at position formula_17. Notice the indices are formula_18-based, that is, the first element is at position formula_18.
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 formula_20 where formula_21 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 formula_22 is the location, on the codeword, where the burst can be found.
For example, the burst description of the error pattern formula_14 is formula_24. Notice that such description is not unique, because formula_25 describes the same burst error. In general, if the number of nonzero components in formula_4 is formula_27, then formula_4 will have formula_27 different burst descriptions each starting at a different nonzero entry of formula_4. 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 formula_31 is denoted by formula_32
A corollary of the above theorem is that we cannot have two distinct burst descriptions for bursts of length formula_50
Cyclic codes for burst error correction.
Cyclic codes are defined as follows: think of the formula_51 symbols as elements in formula_52. Now, we can think of words as polynomials over formula_53 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 formula_54. Suppose that the generator polynomial formula_55 has degree formula_56. Polynomials of degree formula_54 that are divisible by formula_55 result from multiplying formula_55 by polynomials of degree formula_60. We have formula_61 such polynomials. Each one of them corresponds to a codeword. Therefore, formula_62 for cyclic codes.
Cyclic codes can detect all bursts of length up to formula_63. We will see later that the burst error detection ability of any formula_64 code is bounded from above by formula_65. 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 formula_54), compute the remainder of this word when divided by formula_55. If the remainder is zero (i.e. if the word is divisible by formula_55), 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 formula_55 (i.e. it is going to be a valid codeword).
By the upper bound on burst error detection (formula_87), we know that a cyclic code can not detect "all" bursts of length formula_88. However cyclic codes can indeed detect "most" bursts of length formula_89. The reason is that detection fails only when the burst is divisible by formula_55. Over binary alphabets, there exist formula_91 bursts of length formula_1. Out of those, only formula_93 are divisible by formula_55. Therefore, the detection failure probability is very small (formula_95) assuming a uniform distribution over all bursts of length formula_1.
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 formula_64 code that can detect all burst errors of length formula_128 A natural question to ask is: given formula_34 and formula_130, what is the maximum formula_1 that we can never achieve beyond? In other words, what is the upper bound on the length formula_1 of bursts that we can detect using any formula_64 code? The following theorem provides an answer to this question.
Now, we repeat the same question but for error correction: given formula_34 and formula_130, what is the upper bound on the length formula_1 of bursts that we can correct using any formula_64 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." formula_247 is called the redundancy of the code and in an alternative formulation for the Abramson's bounds is formula_248
Fire codes.
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 formula_1, we mean that all errors that a received codeword possess lie within a fixed span of formula_1 digits.
Let formula_251 be an irreducible polynomial of degree formula_252 over formula_253, and let formula_254 be the period of formula_251. The period of formula_251, and indeed of any polynomial, is defined to be the least positive integer formula_56 such that formula_258 Let formula_1 be a positive integer satisfying formula_260 and formula_261 not divisible by formula_254, where formula_254 is the period of formula_251. Define the Fire Code formula_265 by the following generator polynomial: 
We will show that formula_265 is an formula_1-burst-error correcting code.
A corollary to Lemma 2 is that since formula_310 has period formula_254, then formula_251 divides formula_313 if and only if formula_288.
If we can show that all bursts of length formula_1 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 formula_317 and formula_318 be polynomials with degrees formula_319 and formula_320, representing bursts of length formula_321 and formula_322 respectively with formula_323 The integers formula_324 represent the starting positions of the bursts, and are less than the block length of the code. For contradiction sake, assume that formula_325 and formula_326 are in the same coset. Then, formula_327 is a valid codeword (since both terms are in the same coset). Without loss of generality, pick formula_328. By the division theorem we can write: formula_329 for integers formula_330 and formula_331. We rewrite the polynomial formula_332 as follows:
Notice that at the second manipulation, we introduced the term formula_334. We are allowed to do so, since Fire Codes operate on formula_253. By our assumption, formula_332 is a valid codeword, and thus, must be a multiple of formula_55. As mentioned earlier, since the factors of formula_55 are relatively prime, formula_332 has to be divisible by formula_278. Looking closely at the last expression derived for formula_332 we notice that formula_342 is divisible by formula_278 (by the corollary of Lemma 2). Therefore, formula_344 is either divisible by formula_278 or is formula_18. Applying the division theorem again, we see that there exists a polynomial formula_270 with degree formula_348 such that:
Then we may write:
Equating the degree of both sides, gives us formula_351 Since formula_352 we can conclude formula_353 which implies formula_354 and formula_355. Notice that in the expansion:
the term formula_357 appears, but since formula_358, the resulting expression formula_359 does not contain formula_357, therefore formula_361 and subsequently formula_362 This requires that formula_363, and formula_364. We can further revise our division of formula_365 by formula_366 to reflect formula_367 that is formula_368. Substituting back into formula_332 gives us,
Since formula_371, we have formula_372. But formula_251 is irreducible, therefore formula_75 and formula_251 must be relatively prime. Since formula_332 is a codeword, formula_377 must be divisible by formula_251, as it cannot be divisible by formula_278. Therefore, formula_365 must be a multiple of formula_254. But it must also be a multiple of formula_261, which implies it must be a multiple of formula_383 but that is precisely the block-length of the code. Therefore, formula_365 cannot be a multiple of formula_34 since they are both less than formula_34. Thus, our assumption of formula_332 being a codeword is incorrect, and therefore formula_317 and formula_318 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 formula_390-burst error correcting Fire Code. Remember that to construct a Fire Code, we need an irreducible polynomial formula_251, an integer formula_1, representing the burst error correction capability of our code, and we need to satisfy the property that formula_261 is not divisible by the period of formula_251. With these requirements in mind, consider the irreducible polynomial formula_395, and let formula_15. Since formula_251 is a primitive polynomial, its period is formula_398. We confirm that formula_399 is not divisible by formula_400. Thus, 
is a Fire Code generator. We can calculate the block-length of the code by evaluating the least common multiple of formula_254 and formula_261. In other words, formula_404. Thus, the Fire Code above is a cyclic code capable of correcting any burst of length formula_390 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 formula_406. Each symbol of the alphabet can be represented by formula_252 bits. If formula_2 is an formula_239 Reed–Solomon code over formula_406, we can think of formula_2 as an formula_412 code over formula_413.
The reason such codes are powerful for burst error correction is that each symbol is represented by formula_252 bits, and in general, it is irrelevant how many of those formula_252 bits are erroneous; whether a single bit, or all of the formula_252 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 formula_417 errors can affect at most formula_418 symbols, and a burst of formula_419 can affect at most formula_420 symbols. Then, a burst of formula_421 can affect at most formula_422 symbols; this implies that a formula_423-symbols-error correcting code can correct a burst of length at most formula_424.
In general, a formula_423-error correcting Reed–Solomon code over formula_406 can correct any combination of
or fewer bursts of length formula_428, on top of being able to correct formula_423-random worst case errors.
An example of a binary RS code.
Let formula_265 be a formula_431 RS code over formula_432. This code was employed by NASA in their Cassini-Huygens spacecraft. It is capable of correcting formula_433 symbol errors. We now construct a Binary RS Code formula_434 from formula_265. Each symbol will be written using formula_436 bits. Therefore, the Binary RS code will have formula_437 as its parameters. It is capable of correcting any single burst of length formula_438.
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.
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 formula_468 array. Generally, formula_469 is length of the codeword.
Capacity of block interleaver: For an formula_468 block interleaver and burst of length formula_439 the upper limit on number of errors is formula_472 This is obvious from the fact that we are reading the output column wise and the number of rows is formula_229. By the theorem above for error correction capacity up to formula_474 the maximum burst length allowed is formula_475 For burst length of formula_476, the decoder may fail.
Efficiency of block interleaver (formula_477): It is found by taking ratio of burst length where decoder may fail to the interleaver memory. Thus, we can formulate formula_477 as 
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 formula_34 be the number of delay lines and formula_481 be the number of symbols introduced by each delay line. Thus, the separation between consecutive inputs = formula_482 symbols. Let the length of codeword formula_483 Thus, each symbol in the input codeword will be on distinct delay line. Let a burst error of length formula_1 occur. Since the separation between consecutive symbols is formula_485 the number of errors that the deinterleaved output may contain is formula_486 By the theorem above, for error correction capacity up to formula_423, maximum burst length allowed is formula_488 For burst length of formula_489 decoder may fail.
Efficiency of cross interleaver (formula_477): 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 
Thus, we can formulate formula_477 as follows: 
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. By far, the most common application of RS codes is in compact discs. 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. V. Philips of The Netherlands and Sony Corporation of Japan (agreement signed in 1979).
A compact disc comprises a 120 mm aluminized disc coated with a clear plastic coating, with spiral track, approximately 5 km in length, which is optically scanned by a laser of wavelength ~0.8 μm, at a constant speed of ~1.25 m/s. For achieving this constant speed, rotation of the disc is varied from ~8 rev/s while scanning at the inner portion of the track to ~3.5 rev/s at the outer portion. Pits and lands are the depressions (0.12 μm deep) and flat segments constituting the binary data along the track (0.6 μm width).
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 formula_494 or 4 formula_495 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 formula_496 where formula_497 and formula_498 are bytes from the left and right channels from the formula_499 sample of the frame.
Initially, the bytes are permuted to form new frames represented by formula_500 where formula_501represent formula_499 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 formula_503. This is two-error-correcting, being of minimum distance 5. This adds 4 bytes of redundancy, formula_504 forming a new frame: formula_505. 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 formula_506. 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 formula_507 errors and formula_508 erasures such that formula_509. 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) formula_510 and 1000 samples per minute at BER = formula_511 Undetectable error samples (clicks): less than one every 750 hours at BER = formula_511 and negligible at BER = formula_513.