Error detection and correction

Error correction methods are used to detect errors in the storage and transmission of data and if possible, correct. Error detection methods are restricted to a pure error detection.

These will be added before the data storage or transmission of the user data additional redundancy in the form of additional bits, which is used on the landing page for the determination of faults and fault positions.

• 6.1 Forward Error Correction 6.1.1 Pros and Cons
• 6.1.2 Hybrid method of modulation and error detection / correction
• 6.1.3 limits

• 7.1 ECC and parity check
• 7.2 Compact Disc (CD)
• 7.3 ADSL

Causes

• Thermal and electronic noise → broadening of the decision thresholds in the eye diagram → now and the error threshold is exceeded
• Generated largely uniformly distributed errors (which do not require special protective measures such as interleaving )

• Electrical sparks, scratches on CDs
• Multiple bits in succession faulty ( burst errors ), very irregular error distribution
• Cosmic or ionizing radiation

• Attenuation and phase response of a transmission channel

• Unwanted influence of adjacent digital channels, for example, via capacitive coupling

Types of errors

Error detected on the device technology

Error detection in Information Technology

Error detection

Hamming distance and calculation

Detection and correction power of codes with Hamming distance H

Examples

Suppose it should be transferred eight bits user data with the Hamming ECC method, so four error correction bits are needed for addition. Altogether twelve bits to be transmitted.

User data:

Data to be transmitted:

The bits 1,2,4,8 in this case serve as a correction bits and are always at the positions of the respective power of 2 (pos = 2x, x = 0, 1, 2, 3, ... ), ie position 1, 2, 4, 8, 16, 32, etc.

Now the values ​​of the correction bits must be determined. For each bit position is assigned a value in our transmission, which corresponds to the binary value of the decimal point. The value here is four digits, since we only need four bits for the correction.

Pos: 1 Value: 0001 Pos: 2 Value: 0010 Pos: 3 Value: 0011 Pos: 4 Value: 0100 Pos: 5 Value: 0101 Pos: 6 Value: 0110 Pos: 7 Value: 0111 Pos: 8 Value: 1000 Pos: 9 Value: 1001 Pos: 10 Value: 1010 Pos: 11 Value: 1011 Pos: 12 Value: 1100 ....... Now the values ​​of those positions which would be 1 in our transmission, calculated with XOR together, so value / position 5, value / position 9 and value / position 10

0101 Position 5      1001 Position 9 XOR 1010 position 10 ---------   = 0110 These are the values ​​of our error correction bits which are now included in our transmission:

Data to be transmitted:

Now our data is transmitted, and the receiver can verify that it is correct information. This, the calculated and the received correction value is exclusive- ORed ( contra- ):

Data received:

0101 Position 5      1001 Position 9 XOR 1010 position 10 ---------      Calculated correction bits 0110 XOR received 0110 correction bits --------- = 0000 ⇒ Correct transmission Now, for example, bit 5 is altered during transmission:

Data received:

1001 Position 9 XOR 1010 position 10 ---------      Calculated correction bits 0011 XOR received 0110 correction bits --------- = 0101 ⇒ ⇒ value of the position 5 Bit 5 is wrong! Result of the calculation is always the position value of the changed bits, or 0 if no error occurred. This works even if a transmission is correction bit has been changed. For change of two bits can only be a statement be made that bits have been changed, but not exceed, at what positions they sit.

Error correction

Forward error correction

Pros and Cons

Advantages:

• Broadcast
• High capacity utilization

Cons:

• "Reception " collapses if too much signal

Hybrid method of modulation and error detection / correction

In addition to the demodulated signal, the modulation provides more information about the quality of the signal. One way to achieve this is not allowed to install code. If these on, you know that the data with high probability are flawed.

• Trellis codes
• 4B/5B-Code ( 16 of 32 codes valid)
• 8B/10B (256 of 1024 valid code )
• EFM (256 of 16384 (or 131072 ) codes valid)
• (Valid 256 of 16384 (or 65536) codes) EFM
• A modulation used in IEEE 822.11
• AMI modulation

Confines

Code spreading

Spreading code is used for example in UMTS mobile networks. This refers to the spreading of a binary 1 or 0 in a multiple thereof. Spreading factor 8 would make, for example, from a one a sequence of eight ones ( 1111 1111 ). Thus, transmission errors can be easily detected and corrected. Permissible spreading factors are all powers of two, in UMTS at 2, 4, 8, ... to 256 By spreading, however, reduces the usable bandwidth for data.

Error detecting and correcting codes

Error-detecting and error-correcting code ( error -detecting codes and Sheet Error-Correcting Code ) data codes are containing in addition to the coded data or information in order to recognize or to correct data error. Depending on the encoding used more or less errors can be detected or corrected.

• Convolutional code
• Fountain code
• Golay code
• Hamming code
• Low- density parity -check code ( LDPC )
• Nordstrom -Robinson Code
• Parity check (one-dimensional parity check can detect errors only, multidimensional also correct )
• Rank Code
• Reed -Solomon code (RS)
• Repeat - Accumulate Code (RA )
• Simplex code
• Slicing by Eight ( SB8 )
• Trellis coded modulation (TCM)
• Turbo code ( TCC, TPC, etc.)
• Repeat code
• Woven Code
• ( Cyclic Redundancy Check ) ( ZRP, English CRC for error detection; . Basis for ARQ )

Error concealment

Is not possible, error correction, the so-called error concealment (error concealment ) is used for concealing errors.

ECC and parity check

An Error-Correcting Code (ECC ) is a coding for error correction, which is in contrast to the parity check is able to correct a 1 -bit error and to detect a 2 -bit error. The ECC process requires 32 bits and 7 check bits to 64 bits 8 check bits.

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

Compact disc (CD)

When the compact disc, the so-called CIRC error correction method is used. In each case 24 bytes are grouped to an error -correction frame, and further in parallel within the processor during the coding of the current data stream. The 24 bytes (error correction bytes ) equipped with 4 parity bytes, which are determined by a matrix calculation. The 4 parity bytes are put into the frame by byte position 12. The frame has then 28 bytes. Then the bytes of so many equipped with parity bytes frame interleaved ( interleave ) are. The first byte of each frame are not delayed, delayed the each second byte of the frame to frame 4, the third byte to 8 frames, etc., the 28th byte is delayed by 108 frames. Since this is done in the current data stream to occur - apart from the first 108 frames, which remain incomplete - again full frame of 24 bytes plus 4 parity bytes. These new frameworks, which are composed now for completely different bytes ( only adjusted to now 28 fehlerzusichernde bytes ) again with the same matrix algebra with 4 parity bytes are inserted at byte position 29 to 32 in the frame.

After each frame, a so-called Subcodewort is then inserted (98 Subcodewörter always add a control and display information (including the address) for a so-called subcode ). The data is then passed serially back EFM modulated Eight -to- Fourteen modulation and before any already -modulated frame equipped with a synchronization information ( 1000000000010000000000101 ) so that the player will return to the beginning of the frame. The processed data are recorded in NRZ-I notation in the form of pits and lands in a track on the disc ( as in the CD-R) and recorded on a master. From the master, an injection mold is made, with which the individual discs are manufactured as copies. Here, a bit has a length of about 1/3 micron. On a millimeter of the track, the bits of about 150 bytes are recorded. A scratch on the disc can thus easily damage the bits 20, 50, or 100 bytes, ie the bytes of a half or full frame.

The scratched disc can still read with a CD player and play error-free. The read signal is converted into bits, these are EFM demodulates the synchronization information and the Subcodewort be removed from the data stream and the bytes again performed in parallel. Where the player could not read anything, dummy bits are clocked into the data stream.

It the error correction frame from a total of 32 bytes ( 24 information bytes and 2 x 4 parity bytes ) are formed again. After an assessment of the four most recently supplied parity bytes if all data has been read correctly or if somewhere a bit or a whole byte or even more bytes in error correction block are identified as incorrect. Minor errors can immediately correct the decoder. For larger error amounts ( such as scratches so-called burst error ) is not possible, but the erroneous byte may be identified and provided with an error message.

The data is then returned to its original position sorted ( de-interleaving ) and the original error correction frame from formed 24 bytes plus 4 parity bytes. At this point shows the correction effect of the " interleaving ": The damaged by the scratch 20 or 50 on the track adjacent bytes originally all came from different error correction frame and are then spread back to this frame. This are now in this frame in the rarest of cases, more than two bytes in error. So dive Although many error correction frame on isolated erroneous bytes, but this can all be corrected with the aid of the four parity bytes. At the end is again before the error- free serial data stream.

The calculation of the error correction bytes can be greatly simplified demonstrate the following example: The two bytes

01001010 and

10010010

To be equipped with parity bytes. As a rule for the calculation of the binary operation " Exclusive NOR " is ( XNOR ) is used: "If two identical digits are to each other, a 1 is taken as a parity bit, if two unequal numbers are under each other, a 0". This produces the following picture:

01001010

10010010

00,100,111th

You can now, for example, delete the first byte and using the parity byte and the second byte is not erased reconstruct the deleted byte by applying the same rule. Where two identical digits are to each other, a 1 is used as a correction bit, where two unequal numbers are under each other, a 0 following this happen already for the first two bits, the reader can complete the correction itself:

01

10010010

00,100,111th

Just can proceed if the second byte is cleared and the first is still present.

In this example, error correction data has to work with 50%. The CD 8 error correction bytes are inserted per 24 bytes, thus must be stored here 33 % additional (redundant ) information.

ADSL

In a regular ADSL connection interleaving is turned on by default for error correction. The data bits of multiple data blocks ( " frames" ) are mixed to form the error correction works more effectively against impulse noise on the line.

Interleaving drives the latency ( ping time ) in height, but a faultless data transfer is possible even without interleaving (although depending on the line quality between the exchange and subscriber line ).

Switching off the interleaving is offered in most DSL providers in Germany as fast-path function, although it does not represent an additional service, but a shutdown. Such compounds are useful for online players and for services with high user interactivity ( VoIP), where low latency is more important than the data error rate. As an example, a minimal volume loss or a slight noise, each <1 second, with a voice call using VoIP more easily acceptable as a faltering transmission.