Error Correction |
Each one of us has a special type of error correction built in. How many times have you asked " did you just say_____?"? What you thought you heard and what was actually said went through an error correction process. The mind hears the beginning of words. Often it will 'interpolate' the rest of the word as it tries to keep up. The same way that when you read, often you scan the words allowing your mind to 'error correct' the parts you do not focus on. The mind draws on a bank of allowable words that it interpolates into the words that you read. That is why , as you read this, the word pleuston will probably cause you to go back and reread the word as , unless you are a biologist, your brain has never stored a similar word for it to quickly interpolate. (pleuston is a plant that floats on water). As musicians we scan over the music , or take ear training as we try to teach the mind to quickly recognize notes and move on.
Ok...back to our digital bits.
Three
methods of error correction can be used.
Replace - conceal - mute
First, redundancy is used to check validity. Then -
1. The redundant information is used to replace bad blocks.
2. If the error can't be repaired, it is concealed.
3.
Some systems mute the output when uncorrectable
errors are delivered. The systems do this by turning all of the bits to a
value of 0 which effectively cancels the error.
Once an error is detected, replacing the faulty
data with the original data becomes a priority.
The simplest method is to have two tracks of identical data. If an error occurs, data in the second track is inserted into the faulty track replacing the error.
Of course, using duplicate tracks would require more storage and speed than most systems could handle. Especially in a multiple track configuration.
The same way parity check bits are used for error detection, they also can be used to create code for correction. the detection and correction codes are related. Using coded redundant data is the basis for various applications.
Hamming
distance - defines the potential error correctibility of a code. It
is the number of bits that a legal word must change to become another
legal word. The greater the distance - the better the correction.
Simple interleaving
(pp 157-160)
Interleaving is a very simple and powerful idea. To illustrate interleaving, assume that you have a frame consisting of several characters of information,
&n bsp; lebanonvalleycollege
Assume that you spill coffee on the disk and destroy several of the characters leaving
&n bsp; &nb sp; onvalleycollege
The first word is then very hard to reconstruct! However, you can take the original frame and scramble it as,
&n bsp; lebanonvalleycollege -> nelloloebnelavyenlcg
Then you can damage it,
&n bsp; loebnelavyenlcg
Then you can unscramble it,
&n bsp; lebnonvaleycleg
It is much easier to "interpolate" or "guess" the missing letters. (A bit like the later stages of "hangman"!)
Simple Error Detection and Correction Codes
Error detection and correction codes are fundamental to the operation of any digital storage system. There are literally thousands of such codes. These codes typically rely on using additional bits (usually called parity bits) to carry the error detection and correction information.
In a simple binary parity check, a parity bit is a single bit that represents whether the total number of "1s" in a particular data stream is even (1) or odd (0).
For example, assume that you are setting a parity bit over all the digits of the following word.
1101 0000
The total number of "1s" is odd, so the parity bit would be 1. The word might then be written as
1101 0000 1
where the last digit is the parity bit.
Even simple binary parity checks can become quite complex if more than one parity bit is used. For example, you may elect to have two parity bits -- one on the first four bits of the word and one on the last four.
1 1 0 1 0 0 0 0 P1 P2
P1 =x x x x 1 (bits 1,2,3,4) 1101
P2 =x x x x 0 (bits 5,6,7,8) 0000
If enough parity bits are used, then error can not only be detected -- they can also be corrected. For example, consider what happens if you use four parity bits. The first one is on the first four bits, the second one is on the second four bits, the third one is on the 1,2,5,6 bits and the fourth one is on the 2,3,6,7 bits.
1 1 0 1 0 0 0 0 P1 P2 P3 P4
1 1 0 1 0 0 0 0 1 0 0 1
P1=x x x x 1 (1101) (bits 1,2,3,4)
P2 =x x x x 0 (0000) (bits 5,6,7,8)
P3 =x x x x 0 (1100) (bits 1,2,5,6)
P4 =x x x x 1 (1000) (bits 2,3,6,7)
Now, assume that there was an error in the final bit.
TRANSMITTED WORD with PARITY
1 2 3 4 5 6 7 8 P1 P2 P3 P4
1 1 0 1 0 0 0 1 ; 1 0 0 1
PARITY CHECKED
P1 =x x x x 1 (bits 1,2,3,4)
P2 =x x x x 1 (bits 5,6,7,8) <--
P3 =x x x x 0 (bits 1,2,5,6)
P4 =x x x x 1 (bits 2,3,6,7)
[original parity] 1001 [transmitted parity]1101 error detected in bit 8
Parity bit P1 would agree with the parity bit in the transmitted word, P2 would NOT agree, P3 and P4 would
agree. Since P2 is the only parity bit not agreeing with the transmitted word -- then the error must be in the
8th bit (P2 only one with bit 8).
CORRECTION. Bit 8 is changed to 0.
Remember - single bit parity points where (locator) | word parity is used to correct (corrector).
Block codes
1. The digital stream is sectioned into blocks.
2. Words within the blocks are interleaved.
3. Each block is assigned parity words.
4. Each word in the block can also be assigned a parity bit or cyclic code.
More than a single word error can be detected but not corrected.
To enhance detection and correction, 2 parity words can be formed. This is well suited for digital audio applications.
TRANSMITTED DATA AND TWO PARITY WORDS.
WORD Value
W1 20 X 6 =120
W2 10 X 5 = 50
W3 30 X 4 = 120
W4 15 X 3 = 45
W5 20 X 2 = 40
W6 15 X 1 = 15
__ ___
parity (p) 110 (added # in green) weighted sum (q) 390 (added # in maroon)
Syndrome :
S1= W1(20) +W2 (10) +W3 (30) + W4 (15) + W5 (20) + W6 (15) - P(110) =0
S2=6W1 + 5W2 + 4W3 + 3W4 + 2W5 + 1W6 - Q = 0
120 + 50 + 120 + 45 + 40 + 15 - 390 = 0
RECEIVED DATA AND TWO PARITY WORDS. (with error)
W1 20 X6 = 120 error pointer
W2 20 (error) X 5 = 100 error pointer =(E2) 20 - 10 = 10 (difference)
W3 30 X 4 =120
W4 15 X 3 = 45
W5 20 X 2 = 40
W6 10 (error) X1 = 10 error pointer =(E6) 10 - 15 = -5 (difference)
+ ____ + ___
received p 115 received q 435
original p -130 original q -390
____ &nbs p; ____
-15 ; 45
error W2 = original W2 + error pointer 2
20 = 10 + 10 = 20
error W6 = original W6 + error pointer 6
10 = 15 + ( -5 ) = 10
SUBTRACT ORIGINAL FROM ERROR
S1 = E2+E6 or 10 + (-5) = -5
S2 = 5E2 + E6 or 5(10) + (-5) = 45
E2 = S1-E6 5E2 = S2 - E6
10 = (-5)-(-5) 5(10) = 45 - (-5)
E6 = S1 - E2
10 = 20 - 10
CORRECTION
W6 = W(ERROR)2 - E2
10 = 20 - 10
W6 = W( ERROR)6 - E6
15 = 10- (-5)
Double parity block coding used
W1 20 if 6S1 = S2 then W1 is in error
W2 10 5S1 = S2 W2
W3 30 4S1 = S2 W3
W4 15 3S1 = S2 W4
W5 20 2S1 = S2 W5
W6 15 1S1 = S2 W6
______
P = 110
Q = 390
if S1 (does not) =0 & S2 =0 then P is in error
if S1 = 0 & S2 (does not) =0 then Q is in error.
CORRECTION
transmitted received error word
W = W - S
PLEASE
READ pages 147-154 of the text. Error Correction Codes.
The examples above are based on these and we will go over all of the Syndromes
on 150-153 so please look at them before class.
Reed Solomon Code
A multiple error correcting code developed by Irving Reed and Gustav Soloman at MIT in 1960. At the time of development, technology had not reached the point where the Reed Solomon code could actually be used. When combined with cross interleaving (DEF) , is powerful enough to use in audio applications such as CD production, etc.
Reed-Solomon codes are special and widely implemented because they are "almost perfect" in the sense that the extra (redundant) letters added on by the encoder is at a minimum for any level of error correction, so that no bits are wasted.
Reed-Solomon codes are easier to decode than most other nonbinary codes.
Reed-Solomon codes allow the correction of "erasures". An erasure is like taking a pencil eraser and erasing a letter in a word. The letter that should be in that position is unknown, but the position of the erasure is known. Reed-Solomon codes can correct twice as many erasures as errors (where the decoder has no information about the error).
With Reed-Solomon error correction, you get more "bang for the buck" by being able to correct multiple randomly positioned bytes in error.
The actual encoding for error detection and correction is called the Cross Interleave Reed Solomon Code or CIRC. To describe this as simply as possible, the CIRC code consists of two parts: interleaving of data so that a dropout or damage will be spread over enough physical area (hopefully) to be reconstructed and a CRC like error correcting code. Taken together, these two techniques are capable of some remarkable error correction. The assumption here is that most errors will occur in bursts as a result of dust specs, scratches, imperfections such as pinholes in the aluminum coating of CDs, etc. For example, the codes are powerful enough to totally recover a burst error of greater than 4,000 consecutive bits - about 2.5 mm on a CD disc. With full error correction implemented (this is not always the case with every CD player), it is possible to put a piece of 2 mm tape radially on the disc and have no audio degradation. Some test CDs have just this type of defect introduced deliberately.
&n
bsp; (see page
167-168 of the text for more)
Two approaches are taken with uncorrectable errors: interpolation and muting. If good samples surround bad ones, then linear or higher order interpolation may be used to reconstruct them. If too much data has been lost, the audio is smoothly muted for a fraction of a second. Depending on where these errors occur in relation to the musical context, even these drastic measures may be undetectable to the human ear. (Note that the error correction for CD-ROM formats is even more involved than for CD audio as any bit error is unacceptable.)
Interpolation: (p 172) In this technique, some average is constructed using the valid data around an error. This average is then substituted in