Burst error-correcting code - Wikipedia (FazBrowse)

Contents
Cyclic codes for burst error correction
Burst error correction bounds
Upper bounds on burst error detection and correction
Proof of Theorem
Block interleaver
Convolutional interleaver

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.

Y=C+E. Then, the error vector E are confined to ℓ=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 ℓ if its nonzero components are confined to ℓ=5, since we consider the error starting at position 0-based, that is, the first element is at position 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 D=(1000011,1). Notice that such description is not unique, because w, then E. 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

Theorem (Uniqueness of burst descriptions)—Suppose (P1,L1) and w be the hamming weight (or the number of nonzero entries) of w error descriptions. For E will appear in the pattern, and so, the components of n−w distinct elements in all the zero runs. On the other hand we have: 12(n+1).

Cyclic codes for burst error correction
edit

Cyclic codes are defined as follows: think of the 𝔽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 generator polynomial. The codewords of this cyclic code are all the polynomials that are divisible by this generator polynomial.

Codewords are polynomials of degree r. Polynomials of degree g(x) by polynomials of degree k=n−r for cyclic codes.

Cyclic codes can detect all bursts of length up to ℓ⩽n−k. Cyclic codes are considered optimal for burst error detection since they meet this upper bound:
r</math> can detect all bursts of length <math>\\leqslant r.</math>\n\n{{math proof | proof = We need to prove that if you add a burst of length <math>\\leqslant r</math> to a codeword (i.e. to a polynomial that is divisible by <math>g(x)</math>), then the result is not going to be a codeword (i.e. the corresponding polynomial is not divisible by <math>g(x)</math>). It suffices to show that no burst of length <math>\\leqslant r</math> is divisible by <math>g(x)</math>. Such a burst has the form <math>x^i b(x)</math>, where <math>\\deg(b(x)) < r.</math> Therefore, <math>b(x)</math> is not divisible by <math>g(x)</math> (because the latter has degree <math>r</math>). <math>g(x)</math> is not divisible by <math>x</math> (Otherwise, all codewords would start with <math>0</math>). Therefore, <math>x^i</math> is not divisible by <math>g(x)</math> as well.}}"}},"i":0}}]}'>⩽r.
g(x)), then the result is not going to be a codeword (i.e. the corresponding polynomial is not divisible by g(x). Such a burst has the form b(x) is not divisible by g(x) is not divisible by xi is not divisible by g(x). If the remainder is zero (i.e. if the word is divisible by ℓ⩽n−k=r), we know that a cyclic code can not detect all bursts of length r"}}'>ℓ>r. However cyclic codes can indeed detect most bursts of length r"}}'>>r. The reason is that detection fails only when the burst is divisible by ℓ. Out of those, only 2−r) assuming a uniform distribution over all bursts of length

Theorem (Distinct Cosets)—A linear code ⩽ℓ lie in distinct cosets of 𝐞1,𝐞2 be distinct burst errors of length 𝐜=𝐞1−𝐞2 is a codeword. Hence, if we receive 𝐜. In contrast, if all the burst errors C is an C.

C</math> be a linear <math>\\ell</math>-burst-error-correcting code. Then no nonzero burst of length <math>\\leqslant 2\\ell</math> can be a codeword.\n\n{{math proof | proof = Let <math>c</math> be a codeword with a burst of length <math>\\leqslant 2\\ell</math>. Thus it has the pattern <math>(0,1,u,v,1,0)</math>, where <math>u</math> and <math>v</math> are words of length <math>\\leqslant \\ell -1.</math> Hence, the words <math>w = (0,1,u,0,0,0)</math> and <math>c-w = (0,0,0,v,1,0)</math> are two bursts of length <math> \\leqslant \\ell</math>. For binary linear codes, they belong to the same coset. This contradicts the Distinct Cosets Theorem, therefore no nonzero burst of length <math>\\leqslant 2\\ell</math> can be a codeword.}}"}},"i":0}}]}'>ℓ-burst-error-correcting code. Then no nonzero burst of length c be a codeword with a burst of length u and w=(0,1,u,0,0,0) and ⩽2ℓ can be a codeword.

Burst error correction bounds

edit

Upper bounds on burst error detection and correction

edit

Theorem (Burst error detection ability)—The burst error detection ability of any

Proof

First we observe that a code can detect all bursts of length 𝐜1 and ⩽ℓ. Upon receiving 𝐜2 with a burst error 𝐜1 is hit by a burst 𝐜1 with a burst ℓ symbols, they are still going to be different by a burst of length qk⩽qn−ℓ. Applying n and (n,k) code? The following theorem provides a preliminary answer to this question:

(n, k)</math> code satisfies <math>\\ell \\leqslant n-k-\\log_q (n-\\ell)+2</math>\n\n{{math proof | proof = First we observe that a code can correct all bursts of length <math>\\leqslant \\ell</math> if and only if no two codewords differ by the sum of two bursts of length <math>\\leqslant \\ell.</math> Suppose that two codewords <math>\\mathbf{c}_1</math> and <math>\\mathbf{c}_2</math> differ by bursts <math>\\mathbf{b}_1</math> and <math>\\mathbf{b}_2</math> of length <math>\\leqslant \\ell</math> each. Upon receiving <math>\\mathbf{c}_1</math> hit by a burst <math>\\mathbf{b}_1</math>, we could interpret that as if it was <math>\\mathbf{c}_2</math> hit by a burst <math>-\\mathbf{b}_2</math>. We can not tell whether the transmitted word is <math>\\mathbf{c}_1</math> or <math>\\mathbf{c}_2</math>. Now, suppose that every two codewords differ by more than two bursts of length <math>\\ell</math>. Even if the transmitted codeword <math>\\mathbf{c}_1</math> is hit by a burst of length <math>\\ell</math>, it is not going to look like another codeword that has been hit by another burst. For each codeword <math>\\mathbf{c},</math> let <math>B(\\mathbf{c})</math> denote the set of all words that differ from <math>\\mathbf{c}</math> by a burst of length <math>\\leqslant \\ell.</math> Notice that <math>B(\\mathbf{c})</math> includes <math>\\mathbf{c}</math> itself. By the above observation, we know that for two different codewords <math>\\mathbf{c}_i</math> and <math>\\mathbf{c}_j, B(\\mathbf{c}_i)</math> and <math>B(\\mathbf{c}_j)</math> are disjoint. We have <math>q^k</math> codewords. Therefore, we can say that <math>q^k |B( \\mathbf{c})| \\leqslant q^n</math>. Moreover, we have <math>(n-\\ell)q^{\\ell-2} \\leqslant |B(\\mathbf{c})|</math>. By plugging the latter inequality into the former, then taking the base <math>q</math> logarithm and rearranging, we get the above theorem.}}"}},"i":0}}]}'>ℓ⩽n−k−logq(n−ℓ)+2

⩽ℓ. Suppose that two codewords 𝐛1 and 𝐜1 hit by a burst −𝐛2. We can not tell whether the transmitted word is ℓ. Even if the transmitted codeword 𝐜, let ⩽ℓ. Notice that 𝐜i and qk codewords. Therefore, we can say that q logarithm and rearranging, we get the above theorem.

Theorem (number of bursts)—For n which are bursts of length ⩽12(n+1), there is a unique burst description associated with the burst. The burst can begin at any of the ℓ. We can think of it as the set of all strings that begin with 2ℓ−1 possible such patterns, and a total of n2ℓ−1+1 vectors representing bursts of length

Theorem (Bound on the number of codewords)—If 2n/(n2ℓ−1+1) codewords.

n2ℓ−1+1 bursts of length ⩽ℓ. Say the code has M disjoint sets of M(n2ℓ−1+1)⩽2n which implies

Theorem (Abramson's bounds)—If n⩽2n−k−ℓ+1−1.

2k codewords. By our previous result, we know that n⩽2n−k−ℓ+1−2−ℓ+1. Since n⩽2n−k−ℓ+1−1.

Remark. ℓ, we mean that all errors that a received codeword possess lie within a fixed span of m over p(x). The period of p(x)|xr−1. Let 2ℓ−1 not divisible by p are the degree and period of g(x)=(x2ℓ−1+1)p(x).

We will show that

Proof

Let deg⁡(d(x))=0 or p(x)=cd(x) for some constant x2ℓ−1+1 since p(x) does not divide p, then

Proof

If p(x)|xk−1.

Now suppose k is divisible by k=p follows. Therefore, assume p"}}'>k>p. We know that xp−1=(x−1)(1+x+⋯+xp−1)andxk−1=(x−1)(1+x+⋯+xk−1). But (1+x+⋯+xk−1); thus, it also divides the difference of the last two polynomials, (1+x+⋯+xp−k−1). Finally, it also divides: p|k.

A corollary to Lemma 2 is that since p(x) divides ℓ 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

edit

Let ℓ1−1 and ℓ2 respectively with xia(x) and i⩽j. By the division theorem we can write: r,0⩽r<2ℓ−1. We rewrite the polynomial 2xi+rb(x). We are allowed to do so, since Fire Codes operate on g(x). As mentioned earlier, since the factors of x2ℓ−1+1. Looking closely at the last expression derived for x2ℓ−1+1 (by the corollary of Lemma 2). Therefore, 0. Applying the division theorem again, we see that there exists a polynomial a(x)+xbb(x)=d(x)(x2ℓ−1+1)

Then we may write: ℓ1,ℓ2⩽ℓ we can conclude b>δ. Notice that in the expansion: δ<b<2ℓ−1, the resulting expression d(x)=0 and subsequently a(x)=b(x). We can further revise our division of b=0, that is j-i = g(2\\ell -1)</math>."}},"i":0}}]}'>v(x)=xib(x)(xj−1+1).

Since p(x) is irreducible, therefore v(x) is a codeword, x2ℓ−1+1. Therefore, 2ℓ−1, which implies it must be a multiple of n since they are both less than xia(x) and p(x), an integer p(x). With these requirements in mind, consider the irreducible polynomial p(x) is a primitive polynomial, its period is 31. Thus, 2ℓ−1. In other words, 𝔽2m. Each symbol of the alphabet can be represented by (n,k) Reed–Solomon code over [mn,mk]2 code over m bits are erroneous; whether a single bit, or all of the 2 symbols, and a burst of tm+1 can affect at most (t−1)m+1.

In general, a t1+⌊(l+m−2)/m⌋ or fewer bursts of length G be a ⌊33/2⌋=16 symbol errors. We now construct a Binary RS Code ⌈log2(255)⌉=8 bits. Therefore, the Binary RS code will have λ-way interleave is (n,k) code that can correct all bursts of length ⩽λℓ, for any given λk entries of each block into a λ×n matrix. Now, this matrix is read out and transmitted in column-major order. The trick is that if there occurs a burst of length ⌊hλ⌋ and at most hλ⩽ℓ and the h. Conversely, if \\lambda \\ell,"}}'>h>λℓ, then at least one row will contain more than (λn,λk) code is exactly 2λℓλn−λk=2ℓn−k

Block interleaver

edit

The figure below shows a 4 by 3 interleaver.

An example of a block 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 M×N block interleaver and burst of length M. By the theorem above for error correction capacity up to Mt+1, the decoder may fail.

Efficiency of block interleaver (γ=Mt+1MN≈tN.

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
edit

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 nd symbols. Let the length of codeword nd, the number of errors that the deinterleaved output may contain is (nd+1)(t−1). For burst length of (0+1+2+3+⋯+(n−1))d=n(n−1)2d.

Thus, we can formulate 𝔽216 or 4 Li and L1L3L5R1R3R5L2L4L6R2R4R6 where 𝔽256. This is two-error-correcting, being of minimum distance 5. This adds 4 bytes of redundancy, R=24/32. 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 2e+f<5. 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 deinterleaver 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 burst 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) 10−3 and negligible at BER = McEliece, R.J. (2004). The Theory of Information and Coding (Student ed.). Cambridge University Press. ISBN 978-0-521-83185-7.
1 2 3 Lin, Shu; Costello, Daniel J. (2004). Error Control Coding: Fundamentals and Applications (2nd ed.). Pearson-Prentice Hall. ISBN 978-0-13-017973-9.

↑