Error correction procedure

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
- Single bit errors: are errors that occur independently of others ( correlation coefficient is zero).
- 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.
- Trellis encodings
- 4B / 5B code (16 of 32 codes valid)
- 8B / 10B code (256 out of 1024 codes valid)
- EFM (256 of 16384 (or 131072) codes valid)
- EFMplus (256 of 16384 (or 65536) codes valid)
- A modulation used in IEEE 822.11
- AMI modulation
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.
|
|
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
- G.821
- Bit error rate
- Channel coding
- Coding theory
- Cross securing
- Fault Detection, Fault Isolation and Recovery Techniques
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
- The Error Correcting Codes (ECC) on eccpage.com
- Horst Völz: Error correction. (PDF) on horstvoelz.de
- Ulrich Brandt: Correctly correct errors. on elektroniknet.de
- Fault-tolerant storage protects against system failures and data loss - secure storage for PCs, servers and workstations. - ECC procedure. on TecChannel.de
- Jürgen Teich: Fundamentals of technical computer science - coding and error correction. (PDF) at informatik.uni-erlangen.de
Individual evidence
- ↑ ECC - Error Correcting Code. elektronik-kompendium.de, accessed on May 12, 2016 .
- ↑ 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 ).
- ^ H. Lohninger: Correction of errors. vias.org, May 31, 2008, accessed May 12, 2016 .
- ↑ Scott Mueller: PC Hardware Superbibel. The complete reference work. 16th edition. Markt & Technik-Verlag, Munich 2005, ISBN 3-8272-6794-3 .
- ↑ Error correction procedure. brother.de, accessed on May 12, 2016 .
- ↑ Giuliano Garrammone: Procedure for Recovering Lost and / or Corrupted Data. freepatentsonline.com, accessed May 12, 2016 .
- ^ 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 .
- ↑ Number of required parity bits