Search Results for “burst error correcting code”

Source: 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

burst

= Burst description

Cyclic codes for burst error correction

Burst error correction bounds

= Upper bounds on burst error detection and correction

= Further bounds on burst error correction

Fire codes

= Proof of Theorem

code

, the resulting expression

d
(
x
)
(

x

2
ℓ
−
1

+
1
)

{\displaystyle d(x)(x^{2\ell -1}+1)}

does not contain

x

b

{\displaystyle x^{b}}

, therefore

d
(
x
)
=
0

{\displaystyle d(x)=0}

and subsequently

a
(
x
)
+

x

b

b
(
x
)
=
0.

{\displaystyle a(x)+x^{b}b(x)=0.}

This requires that

b
=
0

{\displaystyle b=0}

, and

a
(
x
)
=
b
(
x
)

{\displaystyle a(x)=b(x)}

. We can further revise our division of

j
−
i

{\displaystyle j-i}

by

g
(
2
ℓ
−
1
)

{\displaystyle g(2\ell -1)}

to reflect

b
=
0
,

{\displaystyle b=0,}

that is

j
−
i
=
g
(
2
ℓ
−
1
)

{\displaystyle j-i=g(2\ell -1)}

. Substituting back into

v
(
x
)

{\displaystyle v(x)}

gives us,

v
(
x
)
=

x

i

b
(
x
)

(

x

j
−
1

+
1

)

.

{\displaystyle v(x)=x^{i}b(x)\left(x^{j-1}+1\right).}

Since

deg
⁡
(
b
(
x
)
)
=

ℓ

2

−
1
<
ℓ

{\displaystyle \deg(b(x))=\ell _{2}-1<\ell }

, we have

deg
⁡
(
b
(
x
)
)
<
deg
⁡
(
p
(
x
)
)
=
m

{\displaystyle \deg(b(x))<\deg(p(x))=m}

. But

p
(
x
)

{\displaystyle p(x)}

is irreducible, therefore

b
(
x
)

{\displaystyle b(x)}

and

p
(
x
)

{\displaystyle p(x)}

must be relatively prime. Since

v
(
x
)

{\displaystyle v(x)}

is a codeword,

x

j
−
1

+
1

{\displaystyle x^{j-1}+1}

must be divisible by

p
(
x
)

{\displaystyle p(x)}

, as it cannot be divisible by

x

2
ℓ
−
1

+
1

{\displaystyle x^{2\ell -1}+1}

. Therefore,

j
−
i

{\displaystyle j-i}

must be a multiple of

p

{\displaystyle p}

. But it must also be a multiple of

2
ℓ
−
1

{\displaystyle 2\ell -1}

, which implies it must be a multiple of

n
=

lcm

(
2
ℓ
−
1
,
p
)

{\displaystyle n={\text{lcm}}(2\ell -1,p)}

but that is precisely the block-length of the code. Therefore,

j
−
i

{\displaystyle j-i}

cannot be a multiple of

n

{\displaystyle n}

since they are both less than

n

{\displaystyle n}

. Thus, our assumption of

v
(
x
)

{\displaystyle v(x)}

being a codeword is incorrect, and therefore

x

i

a
(
x
)

{\displaystyle x^{i}a(x)}

and

x

j

b
(
x
)

{\displaystyle x^{j}b(x)}

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

5

{\displaystyle 5}

-burst error correcting Fire Code. Remember that to construct a Fire Code, we need an irreducible polynomial

p
(
x
)

{\displaystyle p(x)}

, an integer

ℓ

{\displaystyle \ell }

, representing the burst error correction capability of our code, and we need to satisfy the property that

2
ℓ
−
1

{\displaystyle 2\ell -1}

is not divisible by the period of

p
(
x
)

{\displaystyle p(x)}

. With these requirements in mind, consider the irreducible polynomial

p
(
x
)
=
1
+

x

2

+

x

5

{\displaystyle p(x)=1+x^{2}+x^{5}}

, and let

ℓ
=
5

{\displaystyle \ell =5}

. Since

p
(
x
)

{\displaystyle p(x)}

is a primitive polynomial, its period is

2

5

−
1
=
31

{\displaystyle 2^{5}-1=31}

. We confirm that

2
ℓ
−
1
=
9

{\displaystyle 2\ell -1=9}

is not divisible by

31

{\displaystyle 31}

. Thus,

g
(
x
)
=
(

x

9

+
1
)

(

1
+

x

2

+

x

5

)

=
1
+

x

2

+

x

5

+

x

9

+

x

11

+

x

14

{\displaystyle g(x)=(x^{9}+1)\left(1+x^{2}+x^{5}\right)=1+x^{2}+x^{5}+x^{9}+x^{11}+x^{14}}

is a Fire Code generator. We can calculate the block-length of the code by evaluating the least common multiple of

p

{\displaystyle p}

and

2
ℓ
−
1

{\displaystyle 2\ell -1}

. In other words,

n
=

lcm

(
9
,
31
)
=
279

{\displaystyle n={\text{lcm}}(9,31)=279}

. Thus, the Fire Code above is a cyclic code capable of correcting any burst of length

5

{\displaystyle 5}

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

F

2

m

{\displaystyle \mathbb {F} _{2^{m}}}

. Each symbol of the alphabet can be represented by

m

{\displaystyle m}

bits. If

C

{\displaystyle C}

is an

(
n
,
k
)

{\displaystyle (n,k)}

Reed–Solomon code over

F

2

m

{\displaystyle \mathbb {F} _{2^{m}}}

, we can think of

C

{\displaystyle C}

as an

[
m
n
,
m
k

]

2

{\displaystyle [mn,mk]_{2}}

code over

F

2

{\displaystyle \mathbb {F} _{2}}

.
The reason such codes are powerful for burst error correction is that each symbol is represented by

m

{\displaystyle m}

bits, and in general, it is irrelevant how many of those

m

{\displaystyle m}

bits are erroneous; whether a single bit, or all of the

m

{\displaystyle m}

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

(
m
+
1
)

{\displaystyle (m+1)}

errors can affect at most

2

{\displaystyle 2}

symbols, and a burst of

2
m
+
1

{\displaystyle 2m+1}

can affect at most

3

{\displaystyle 3}

symbols. Then, a burst of

t
m
+
1

{\displaystyle tm+1}

can affect at most

t
+
1

{\displaystyle t+1}

symbols; this implies that a

t

{\displaystyle t}

-symbols-error correcting code can correct a burst of length at most

(
t
−
1
)
m
+
1

{\displaystyle (t-1)m+1}

.
In general, a

t

{\displaystyle t}

-error correcting Reed–Solomon code over

F

2

m

{\displaystyle \mathbb {F} _{2^{m}}}

can correct any combination of

t

1
+
⌊
(
l
+
m
−
2
)

/

m
⌋

{\displaystyle {\frac {t}{1+\lfloor (l+m-2)/m\rfloor }}}

or fewer bursts of length

l

{\displaystyle l}

, on top of being able to correct

t

{\displaystyle t}

-random worst case errors.

= An example of a binary RS code

=
Let

G

{\displaystyle G}

be a

[
255
,
223
,
33
]

{\displaystyle [255,223,33]}

RS code over

F

2

8

{\displaystyle \mathbb {F} _{2^{8}}}

. This code was employed by NASA in their Cassini-Huygens spacecraft. It is capable of correcting

⌊
33

/

2
⌋
=
16

{\displaystyle \lfloor 33/2\rfloor =16}

symbol errors. We now construct a Binary RS Code

G
′

{\displaystyle G'}

from

G

{\displaystyle G}

. Each symbol will be written using

⌈

log

2

⁡
(
255
)
⌉
=
8

{\displaystyle \lceil \log _{2}(255)\rceil =8}

bits. Therefore, the Binary RS code will have

[
2040
,
1784
,
33

]

2

{\displaystyle [2040,1784,33]_{2}}

as its parameters. It is capable of correcting any single burst of length

l
=
121

{\displaystyle l=121}

.

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 transmitter. 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.

= Burst error correcting capacity of interleaver

= 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

M
×
N

{\displaystyle M\times N}

array. Generally,

N

{\displaystyle N}

is length of the codeword.
Capacity of block interleaver: For an

M
×
N

{\displaystyle M\times N}

block interleaver and burst of length

ℓ
,

{\displaystyle \ell ,}

the upper limit on number of errors is

ℓ
M

.

{\displaystyle {\tfrac {\ell }{M}}.}

This is obvious from the fact that we are reading the output column wise and the number of rows is

M

{\displaystyle M}

. By the theorem above for error correction capacity up to

t
,

{\displaystyle t,}

the maximum burst length allowed is

M
t
.

{\displaystyle Mt.}

For burst length of

M
t
+
1

{\displaystyle Mt+1}

, the decoder may fail.
Efficiency of block interleaver (

γ

{\displaystyle \gamma }

): It is found by taking ratio of burst length where decoder may fail to the interleaver memory. Thus, we can formulate

γ

{\displaystyle \gamma }

as

γ
=

M
t
+
1

M
N

≈

t
N

.

{\displaystyle \gamma ={\frac {Mt+1}{MN}}\approx {\frac {t}{N}}.}

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

n

{\displaystyle n}

be the number of delay lines and

d

{\displaystyle d}

be the number of symbols introduced by each delay line. Thus, the separation between consecutive inputs =

n
d

{\displaystyle nd}

symbols. Let the length of codeword

⩽
n
.

{\displaystyle \leqslant n.}

Thus, each symbol in the input codeword will be on distinct delay line. Let a burst error of length

ℓ

{\displaystyle \ell }

occur. Since the separation between consecutive symbols is

n
d
,

{\displaystyle nd,}

the number of errors that the deinterleaved output may contain is

ℓ

n
d
+
1

.

{\displaystyle {\tfrac {\ell }{nd+1}}.}

By the theorem above, for error correction capacity up to

t

{\displaystyle t}

, maximum burst length allowed is

(
n
d
+
1
)
(
t
−
1
)
.

{\displaystyle (nd+1)(t-1).}

For burst length of

(
n
d
+
1
)
(
t
−
1
)
+
1
,

{\displaystyle (nd+1)(t-1)+1,}

decoder may fail.

Efficiency of cross interleaver (

γ

{\displaystyle \gamma }

): 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

(
0
+
1
+
2
+
3
+
⋯
+
(
n
−
1
)
)
d
=

n
(
n
−
1
)

2

d
.

{\displaystyle (0+1+2+3+\cdots +(n-1))d={\frac {n(n-1)}{2}}d.}

Thus, we can formulate

γ

{\displaystyle \gamma }

as follows:

γ
=

(
n
d
+
1
)
(
t
−
1
)
+
1

n
(
n
−
1
)

2

d

.

{\displaystyle \gamma ={\frac {(nd+1)(t-1)+1}{{\frac {n(n-1)}{2}}d}}.}

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

F

2

16

{\displaystyle \mathbb {F} _{2}^{16}}

or 4

F

2

8

{\displaystyle \mathbb {F} _{2}^{8}}

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

L

1

R

1

L

2

R

2

…

L

6

R

6

{\displaystyle L_{1}R_{1}L_{2}R_{2}\ldots L_{6}R_{6}}

where

L

i

{\displaystyle L_{i}}

and

R

i

{\displaystyle R_{i}}

are bytes from the left and right channels from the

i

t
h

{\displaystyle i^{th}}

sample of the frame.
Initially, the bytes are permuted to form new frames represented by

L

1

L

3

L

5

R

1

R

3

R

5

L

2

L

4

L

6

R

2

R

4

R

6

{\displaystyle L_{1}L_{3}L_{5}R_{1}R_{3}R_{5}L_{2}L_{4}L_{6}R_{2}R_{4}R_{6}}

where

L

i

,

R

i

{\displaystyle L_{i},R_{i}}

represent

i

{\displaystyle i}

-th 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

F

256

{\displaystyle \mathbb {F} _{256}}

. This is two-error-correcting, being of minimum distance 5. This adds 4 bytes of redundancy,

P

1

P

2

{\displaystyle P_{1}P_{2}}

forming a new frame:

L

1

L

3

L

5

R

1

R

3

R

5

P

1

P

2

L

2

L

4

L

6

R

2

R

4

R

6

{\displaystyle L_{1}L_{3}L_{5}R_{1}R_{3}R_{5}P_{1}P_{2}L_{2}L_{4}L_{6}R_{2}R_{4}R_{6}}

. 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

R
=
24

/

32

{\displaystyle 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

e

{\displaystyle e}

errors and

f

{\displaystyle f}

erasures such that

2
e
+
f
<
5

{\displaystyle 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 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)

=

10

−
4

{\displaystyle =10^{-4}}

and 1000 samples per minute at BER =

10

−
3

{\displaystyle 10^{-3}}

Undetectable error samples (clicks): less than one every 750 hours at BER =

10

−
3

{\displaystyle 10^{-3}}

and negligible at BER =

10

−
4

{\displaystyle 10^{-4}}

.

Definitions

= Burst description

Cyclic codes for burst error correction

Burst error correction bounds

= Upper bounds on burst error detection and correction

= Further bounds on burst error correction

Fire codes

= Proof of Theorem

= Example: 5-burst error correcting fire code

Binary Reed–Solomon codes

= An example of a binary RS code

Interleaved codes

= Burst error correcting capacity of interleaver

= Block interleaver

= Convolutional interleaver

Applications

= Compact disc

See also

References

Kata Kunci Pencarian:

Recent Movies

Recent Movies

Categories

Recent Movies