Error correction procedure

from Wikipedia, the free encyclopedia
To remove transmission errors caused by the earth's atmosphere (left), Goddard scientists used the Reed-Solomon error correction (right), which is commonly used in CDs and DVDs. Typical errors are missing pixels (white) and incorrect signals (black). The white stripe indicates a brief period of time during which the transmission was interrupted.

Error correction procedures , also known as Error Correcting Code or Error Checking and Correction  (ECC), are used to detect errors in the storage and transmission of data and, if possible, to correct them. Error detection methods are limited to determining whether there is an error. For this purpose, additional redundancy is added to the user data before data storage or transmission , usually in the form of additional bits , which are used on the target side to identify errors and to determine the error position (s).

history

As early as 1950, for example, the mathematician Richard W. Hamming and Marcel JE Golay developed the first error correction methods. Initially, these were mostly only able to correct single bit errors.

In 1960, methods were developed that were able to recognize and correct several errors, including those lying next to one another ( error burst ). The scientists Irving Stoy Reed and Gustave Solomon developed this process named after them, the Reed-Solomon code . Other scientists who were involved in the development of such processes are Philip Fire ( Fire Code 1959) Raj Chandra Bose , Dijen Kumar Ray-Chaudhuri and Alexis Hocquenghem ( BCH Code ).

Expression of the error

  • Noise: Noise can cause bit errors regardless of the cause . The probability of an error does not depend on the occurrence of previous errors, but only on the strength of the noise. Therefore, an even distribution of the errors in equally long time intervals can be expected.
    • Thermal and electronic noise lead to a broadening of the decision thresholds in the eye diagram . Therefore, the error threshold is exceeded from time to time.
    • Generates largely evenly distributed errors (which do not require any special protective measures such as interleaving )
  • Short term disorders
    • Electric sparks, scratches on CDs
    • Several bits in a row are incorrect ( burst error), very uneven distribution of errors
    • cosmic or ionizing radiation
  • Signal deformation
    • Attenuation and phase response of a transmission channel
  • Crosstalk
    • Unwanted influence of neighboring digital channels, for example via capacitive coupling

Types of errors

  • Bunch errors : (also burst errors, block errors, cluster errors or English error bursts ) are errors that occur depending on others (correlation function is a peak). In telecommunications, this type of error often occurs due to interference such as lightning, relay circuits , etc. An error bundle is characterized by a coherent sequence of symbols (e.g. bits) in which the first and the last symbol are error-prone and there is no coherent partial sequence of correctly received symbols within the error bundle. The integer parameter is also scope ( English belt guard ) of the burst error mentioned. Step z. If, for example, two trunking errors occur in a transmission, the distance between the last symbol of the first trunking error and the first symbol of the second trunking error must be correct bits or more. The parameter should therefore be specified if a bundle error is to be described.
  • Synchronization errors: These are (usually longer) bundle errors which, in addition to a loss of the content of the symbols received, also lead to a loss of information about how many symbols have been lost. This means that subsequent correct symbols can no longer be used, since it is no longer known where the received symbols belong. With Ethernet z. B. Single bit errors to synchronization errors.

Error detection in device technology

The Error Correction Mode (ECM) can, for example, detect transmission errors when sending and receiving faxes due to line interference. Incorrect pages may be sent again.

Error detection in information technology

Hamming distance and calculation

Recognition and correction of codes with Hamming distance H

Examples

If we assume that eight bits of user data are to be transmitted using the Hamming ECC method, four additional error correction bits are required for this. A total of twelve bits must be transmitted.

Usage data:

Bit 8th 7th 6th 5 4th 3 2 1
content 0 0 1 1 0 0 1 0

Data to be transferred:

Bit 12 11 10 9 8th 7th 6th 5 4th 3 2 1
content 0 0 1 1 ? 0 0 1 ? 0 ? ?

Bits 1, 2, 4 and 8 serve as correction bits in this case and are always in the positions of the respective power of 2 (Pos = 2 x , x = 0, 1, 2, 3, ...), i.e. position 1 , 2, 4, 8, 16, 32 etc.

Now the values ​​of the correction bits have to be determined. To do this, each bit position in our transmission is assigned a value that corresponds to the binary value of the decimal position. The value has four digits here because we only need four bits for the correction. 

Pos:  1  Wert: 0001
Pos:  2  Wert: 0010
Pos:  3  Wert: 0011
Pos:  4  Wert: 0100
Pos:  5  Wert: 0101
Pos:  6  Wert: 0110
Pos:  7  Wert: 0111
Pos:  8  Wert: 1000
Pos:  9  Wert: 1001
Pos: 10  Wert: 1010
Pos: 11  Wert: 1011
Pos: 12  Wert: 1100
.......

Now the values ​​of those positions that would be 1 in our transfer are calculated with XOR, i.e. the values ​​of positions 5, 9 and 10. 

0101   Position 5
    1001   Position 9
XOR 1010   Position 10
---------
 =  0110

These are the values ​​of our error correction bits, which are now inserted into our transmission:

Data to be transferred:

Bit 12 11 10 9 8th 7th 6th 5 4th 3 2 1
content 0 0 1 1 0 0 0 1 1 0 1 0

Now our data is being transmitted and the recipient can check whether the information is correct. For this purpose, the calculated and the received correction value are linked exclusively or ( contravalence ):

received data:

Bit 12 11 10 9 8th 7th 6th 5 4th 3 2 1
content 0 0 1 1 0 0 0 1 1 0 1 0 
0101   Position 5
    1001   Position 9
XOR 1010   Position 10
---------
    0110   Korrekturbits berechnet
XOR 0110   Korrekturbits empfangen
---------
=   0000   ⇒ Korrekte Übertragung

Bit 5, for example, is now changed during transmission:

received data:

Bit 12 11 10 9 8th 7th 6th 5 4th 3 2 1
content 0 0 1 1 0 0 0 0 1 0 1 0 
1001   Position 9
XOR 1010   Position 10
---------
    0011   Korrekturbits berechnet
XOR 0110   Korrekturbits empfangen
---------
=   0101   ⇒ Wert der Position 5 ⇒ Bit 5 ist falsch!

The result of the calculation is always the position value of the changed bit or 0 if no error occurred. This also works if a correction bit was changed during transmission. If two bits are changed, only a statement can be made about the fact that bits have been changed, but not about the positions in which they are located.

Bug fix

Forward error correction

Advantages and disadvantages

Advantages:

  • Broadcast
  • High capacity utilization

Disadvantage:

  • "Reception" breaks down if the signal is too strong

Hybrid method of modulation and error detection / correction

In addition to the demodulated signal, the modulation also provides information about the quality of the signal. One way to do this is to include illegal codes. If these occur, you know that the data is very likely to be incorrect.

Code spreading

Code spreading is used, for example, in UMTS in mobile communications. This means the spreading of a binary 1 or 0 into a multiple thereof. Spread factor 8 would e.g. B. turn a one into a sequence of eight ones (1111 1111). Transmission errors can thus be easily recognized and corrected. Permissible spreading factors are all powers of two, in UMTS from 2, 4, 8, ... to 256. However, spreading reduces the usable bandwidth for data.

Error detection and correction codes

Error -detecting and error-correcting codes ( English error-detecting codes and English error-correcting codes ) are data encodings which, in addition to the encoded data, also contain information in order to identify or correct data errors. Depending on the coding used, more or fewer errors can be discovered or corrected.

Code selection

Error concealment

If error correction is not possible, the so-called. Is error concealment (error concealment) applied to the concealment of errors.

ECC and parity check

An error-correcting code (ECC) is a coding for error correction which, in contrast to the parity check , is able to correct a 1-bit error and to recognize a 2-bit error. The ECC method requires 6 check bits on 32 bits and 7 check bits on 64 bits.

The ECC method is often used in memory modules for server systems that require particularly high data integrity.

Compact Disc (CD)

The so-called CIRC error correction method is used with the compact disc . During the coding process, 24 bytes from the current data stream are combined to form an error correction frame and continued in parallel in the processor. The 24 bytes are equipped with 4 parity bytes (error correction bytes), which are determined with the help of a matrix calculation. The 4 parity bytes are sorted into the frame according to byte position 12. The frame then has 28 bytes. The bytes are then interleaved from many frames with parity bytes. The first bytes of the frame are not delayed, the second bytes of the frame are delayed by 4 frames, the third bytes by 8 frames, etc., the 28th byte is delayed by 108 frames. Since this is done in the current data stream, complete frames of 24 bytes plus 4 parity bytes are created again - apart from the first 108 frames, which remain incomplete. These new frames, which are now composed of completely different bytes, are again provided with 4 parity bytes using the same matrix calculation (only adapted to now 28 bytes to be protected against errors), which are inserted into the frame at byte positions 29 to 32.

A so-called subcode word is then inserted after each frame (98 subcode words always result in control and display information (including the address) for a so-called subcode frame). The data are then continued serially, EFM- modulated and provided with synchronization information (1000000000010000000000101) in front of each already modulated frame, so that the player can find the beginning of the frame again. The data processed in this way is recorded in NRZ-I notation in the form of pits and lands in a track on the disc (as with the CD-R) or recorded on a master. An injection molding tool is produced from the master, with which the individual discs are produced as copies. A bit here has a length of approx. 1 ⁄ 3 µm. The bits of approx. 150 bytes are recorded on one millimeter of the track. A scratch on the disc can easily damage the bits of 20, 50 or 100 bytes, i.e. the bytes of half a frame or a whole frame.

The scratched disc can still be read out with a CD player and played back without errors. The read-out signal is converted into bits, these are EFM-demodulated, the synchronization information and the subcode word are removed from the data stream and the bytes are routed in parallel again. Where the player could not read anything, dummy bits are clocked into the data stream.

The error correction frames are now again formed from a total of 32 bytes (24 information bytes and 2 × 4 parity bytes). The last four parity bytes supplied are then used to check whether all data have been read out correctly or whether a bit or a whole byte or even several bytes in the error correction block are identified as incorrect. The decoder can correct minor errors immediately. In the case of larger amounts of errors (e.g. scratches, so-called burst errors), this is not possible, but the incorrect bytes can be identified and provided with an error message.

The data are then sorted back into their original position (deinterleaving) and the original error correction frames are formed from 24 bytes plus 4 parity bytes. This is where the corrective effect of "interleaving" becomes apparent: The 20 or 50 bytes lying next to each other on the track damaged by the scratch originally all came from different error correction frames and are now distributed over these frames again. As a result, more than two bytes are now faulty in these frames in the rarest of cases. Indeed, faulty bytes occasionally appear in many error correction frames, but these can all be corrected with the help of the four parity bytes. At the end there is again the error-free serial data stream.

The calculation of the error correction bytes can be demonstrated in a very simplified way using the following example: The two bytes 

01001010 und

10010010

should be equipped with parity bytes. The binary operation "Exclusive NOT-OR" ( XNOR link ) is used as a rule for the calculation : "If 2 identical digits are below each other, a 1 is taken as the parity bit, if two unequal digits are below each other, a 0." This results following picture: 

01001010

10010010

00100111.

You can now z. B. delete the first byte and use the parity byte and the not deleted second byte to reconstruct the deleted byte by applying the same rule. Where two identical digits are below each other, a 1 is used as a correction bit, where two unequal digits are below each other, a 0. This has already happened for the first two bits, the reader can complete the correction himself: 

01

10010010

00100111.

You can proceed in the same way if the second byte is deleted and the first is still available.

In this example, 50% error correction data was used. On the CD, 8 error correction bytes are inserted per 24 bytes, so 33% additional (redundant) information must be saved here.

ADSL

With a regular ADSL connection, interleaving is activated by default for error correction. The data bits of several data blocks ("frames") are mixed together, so that the error correction works more effectively against impulse interference on the line.

Interleaving increases the latency ( ping ), but perfect data transmission is also possible without interleaving (depending on the line quality between the exchange and the subscriber line ).

Most DSL providers in Germany offer the deactivation of interleaving as a fast path function, although it is not an additional service but a deactivation of a functionality. Such connections are suitable for online gamers as well as for high user interactivity ( VoIP ) services where low latency is more important than data error rate. As an example, a minimal loss of volume or a low level of background noise, each <1 second, is more acceptable than a slow transmission with a voice connection via VoIP.

See also

literature

  • Jeremy J. Stone: Multiple burst error correction. In: Information and Control. Volume 4, No. 4. December 1, 1961, pp. 324-331, doi: 10.1016 / S0019-9958 (61) 80048-X .
  • Thomas Gries: Error correction method using Reed-Solomon codes for adaptive subband speech coders. Institute for Telecommunications, Berlin 1986, urn : nbn: de: kobv: 83-opus-17813 .
  • Robert J. McEliece: BCH Reed Solomon and related codes. In: The theory of information and coding. 2nd Edition. Cambridge University Press, Cambridge / New York 2002, ISBN 0-521-00095-5 , p. 230 ff.
  • Todd K. Moon: Error Correction Coding. Mathematical Methods and Algorithms. Wiley-Interscience, Hoboken NJ 2005, ISBN 0-471-64800-0 .
  • Shu Lin, Daniel J. Costello: Error Control Coding. Fundamentals and applications. 2nd Edition. Prentice Hall, Upper Saddle River NJ 2004, ISBN 0-13-042672-5 .
  • Frank J. Furrer: Error-correcting block coding for data transmission (= engineering textbooks and handbooks. 36). Birkhäuser, Basel 1981, ISBN 3-0348-5818-3 , urn : nbn: de: 1111-20130805882 .
  • Andres Keller: Error protection. In: Broadband cables and access networks. Technical principles and standards. Springer, Berlin / Heidelberg 2011, ISBN 978-3-642-17631-9 , pp. 62 ff. Urn : nbn: de: 1111-20110121222 , ( books.google.de ).
  • Matthias Hiller, Michael Pehl, Georg Sigl: Error correction method for secure key generation with physical unclonable functions. In: Data protection and data security - DuD. Volume 39, No. 4 April 9, 2015, pp. 229-233, ISSN  1614-0702 , doi: 10.1007 / s11623-015-0401-0 .

Web links

Individual evidence

  1. ↑ ECC - Error Correcting Code. elektronik-kompendium.de, accessed on May 12, 2016 .
  2. ↑ Philip Fire: A class of multiple-error-correcting binary codes for non-independent errors . In: Stanford Electronics Laboratories . tape 55 . Department of Electrical Engineering, Stanford University, Mountain View, California 1959, OCLC 25463867 ( books.google.de ).
  3. ^ H. Lohninger: Correction of errors. vias.org, May 31, 2008, accessed May 12, 2016 .
  4. ↑ Scott Mueller: PC Hardware Superbibel. The complete reference work. 16th edition. Markt & Technik-Verlag, Munich 2005, ISBN 3-8272-6794-3 .
  5. ↑ Error correction procedure. brother.de, accessed on May 12, 2016 .
  6. ↑ Giuliano Garrammone: Procedure for Recovering Lost and / or Corrupted Data. freepatentsonline.com, accessed May 12, 2016 .
  7. ^ Alan W. Nordstrom, John P. Robinson: An optimum nonlinear code . In: Information and Control . tape 11 , no. 5 , November 1, 1967, p. 613-616 , doi : 10.1016 / S0019-9958 (67) 90835-2 .
  8. ↑ Number of required parity bits