Error Detection What is Automatic Repeat reQuest (ARQ) Error Correction Methods What is Cyclic Redundancy Check (CRC) What is Header Error Control (HEC) What is Forward Error Correction (FEC) What is Reed Solomon (RS) Coding What is Trellis Coded Modulation (TCM)

~ Error Detection and Correction

Error Detection and Correction can have several different states

• No errors detected
• Error detected which requires retransmission. (eg CRC)
• Decoder detects and corrects bit errors. (eg FEC)
• Decoder detects an error but is unable to correct it.
• Decoder detects no errors even though an error may be present.

~ Automatic Repeat reQuest (ARQ)

A function that allows your modem to detect flawed data and request that it be retransmitted.
ARQ is a networking protocol responsible for error detection and relies on each data packet being acknowledged by the receiver. If an error is found, ARQ will automatically request that the data packet is resent.

~ Error Correction Methods

ADSL utilises error correction at different levels

• Convolutional Coding. - Performed on each symbol in the data stream of non-fixed length, by adding redundant bits to the code. A highly efficient form of encoding data and used in telecoms (mobile phones, satellite, voice modems), digital radio and bluetooth to aid performance.
• Block Coding - Performed on blocks of data packets of fixed sizes. An algorithm is used to produce a code word from the original data. Commonly used for storage devices such as CDs, DVDs but also used in many digital communication methods such as WiFi, satellite, DSL

Convolutional coding is efficient at correcting random or white noise errors with little overhead, but doesn't fair well if a longer noise burst disrupts the sequence making the path impossible to recreate.
(See Trellis Coded Modulation)

Block coding is better suited for burst errors as it utilises more parity bits, but the downside of block coding is the redundancy increases bandwidth and delay. (See Reed Solomon encoding)

Both of these methods work independently but can be combined so that any burst errors resulting from convolutional coding may be caught by the block coding.
Concatenating these two different coding methods gives a high degree of correction. It's usual for the convolutional code such as TCM to be the "Inner code" whilst a block code such as RS is classed as the "Outer Code".

Also applying Interleaving to the block code, in order to scatter the errors from noise bursts, gives near optimum performance.

~ Cyclic Redundancy Check (CRC)

CRC is a block code used for error detection only. CRC is when a special checksum code is attached to each packet of data that is transmitted.

A very simplified example of a checksum would be:

At the receiving end a decoder then performs the same calculation on the data in the packet and then compares it to the transmitted CRC code.
The decoder produces the output data only if the codes match indicating that there are no errors. If an error occurs then the decoder signals an erasure (loss of data), and a higher level ARQ then re-requests the data.

More sophisticated codes can correct some number of errors only if the number of errors exceeds the codes correction ability will it signal an erasure (eg HEC)

~ Header Error Control (HEC)

A CRC algorithm used for checking and correcting an error in an ATM cell header. HEC has single bit error correction and multiple bit error detection capabilities. ATM equipment checks for an error and if possible will correct it.

A simplified example would be

Multiple bit errors are discarded and re-requested.

~ Forward Error Correction (FEC)

FEC sends additional redundant data which can be used by the decoder to check for errors and correct data without the need for retransmission. Reed Solomon (RS) coding is commonly used in Forward Error Correction.

~ Reed Solomon (RS) Coding

Reed Solomon encoding is a form of block (or algebraic) coding. Depending on the algorithm used the encoder at the sending end inserts "x" number of parity bits into the payload data.
This new output is called a codeword, and its length is the the original data plus the check symbols after it has encoded.

Different levels of redundancy can be applied. Obviously the more check bits that are used gives higher chance of data recovery, but will cause a higher increase in latency. Some routers will show the level applied by the DLM. eg

R (number of check bytes in RS code word) 16 16
R (number of check bytes in RS code word) 12 8

When data is received at the other end the decoder then converts back to the original data, and if necessary using the additional redundancy to recover any data that may have been corrupted.

~ Trellis Coded Modulation (TCM)

TCM is a type of convolutional code which utilises parity bits on each symbol within a continuous data stream. Its also a highly efficient form of modulation for data which is to be transferred over such mediums as the telephone line.

So called because of the "trellis" like structure in which the data is encoded, data can only follow one of 2 paths in a branch like (or garden trellis type) structure. If one bit is corrupted then using this technique its possible to recalculate the missing bit of data based on the data either side of the corrupted data.

If the data received had an error then the path through the trellis would be broken, but could be recalculated from the preceding and following data.
For example if data sent was 1,3,5,7,9 and the far end received 1,3,?,7,9 then the far end would be able to calculate the missing number based on a parity check of the numbers on either side of the missing number.

Below is a simple diagram showing Trellis Coded Modulation

Blue arrows show possible paths through the "trellis" from any one point to the next. Each point can only go 1 of 2 ways which will be encoded as 0 or 1. Red lines show a sample path through the trellis. Incoming data symbols are shown at the top and underneath the converted code for transmission. Its important to note that the converted transmit data (with the double bits) record a distinct path through the trellis. This bit stream does NOT directly relate to the original data bits ***** which is later decoded back into the original format,

In reality the code is much more complicated and can be multi-dimensional which allows more data to be remapped.

~ Glossary

ATM - Asynchronous Transfer Mode - Protocol used to transport data - See ATM
BER - Bit Error Rate - Ratio of Errored bits to Transmitted bits. BERT = Bit Error Rate Test
Code Rate - Ratio of data bits to the total bits transmitted in the code word.
Code Redundancy - Ratio of the redundant bits to data bits.
Coding Gain - Measurement of efficiency of the coded signal over an un-encoded signal.

Further reading

EE4253 Digital Communications - Convolutional Coding
Coding and decoding with Convolutional Codes
TAPR Error Control Coding Seminar
How the CRC algorithm works
Error Control Coding
Block Coding
ARQ HEC