This tutorial looks at how adsl broadband errors are detected and the methods used to correct corrupted data.
~ Error Detection and Correction
Our modems are responsible for Error Detection and Correction, which 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.
If no errors are detected then data can be processed and passed on to our computers, elsewise the modem decides which action to take depending on whether or not the data can be recovered.
~ Automatic Repeat reQuest (ARQ)
A function that enables devices connected to the Internet 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
DSL Broadband 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.
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 - 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
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 type errors not corrected by convolutional coding may be caught by the block coding method.
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)
Cyclic Redundancy Check (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:
| Data Transmitted :
||1, 3, 5, 7, 9
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 outcome will be one of the following options:
- Checksum match - indicating no errors - Decoder produces the output data for transmission.
- Checksum mis-match - indicating error - Decoder signals an erasure (loss of data) and a higher level ARQ then re-requests the data. Modem records a CRC Error.
More sophisticated CRC codes (eg HEC) can correct some number of errors. Only if the number of errors exceeds the codes correction ability will it signal a CRC erasure.
~ Header Error Control (HEC)
A CRC type of 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
||1, 3, 5, 7
| Checksum code :
||1, ?, 5, 7
| Checksum code:
Using the code, the missing item can be calculated.
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 and typically incurs an overhead of circa 8%.
Forward Error Correction is often used in conjunction with interleaving to help stabilise adsl lines, but the redundant data will obviously carry an overhead. There are two ways of dealing with the overhead:-
1. Reducing payload capacity. (Less useful data per transmission).
2. Transmission of the redundant data in specially assigned channels. (Out of Band)
ADSL uses out-of-band signals to carry redundant data for FEC whereby certain sub-channels are specifically assigned to carry the overhead data. These sub-channels are not available for transmission of normal data and used purely for FEC overheads. Assigning sub-channels as out-of-band has the effect of reducing the maximum sync speed available for normal data transmission.
~ 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 been 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.
Trellis encoding works well for general background type noise. It has negligible data overheads for redundancy and instead uses complex constellations for mapping of the data path. The advantage is a higher data rate than with block encoding but it relies on the modem chipset to undertake more complex calculations and therefore a faster processor is required to avoid latency.
Whilst Trellis encoding may cause a tiny amount of buffering during the encoding and decoding stage it should be negligible on most decent modems and not cause any noticeable latency. The end result should be low error rates for environments experiencing low level repetitive noise as it detects patterns from noise sources and is able to correct these.
The net coding gain for TCM is said to be circa 3dB in most environments, although it must also be said it does not offer any advantage if the line is completely noise free. It should work best on longer lines which are more likely to pick up background noise from the environment.
~ How does Trellis Coding work?
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 constellations which allows more data to be remapped.
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.
EE4253 Digital Communications - Convolutional Coding
Coding and decoding with Convolutional Codes
TAPR Error Control Coding Seminar
How the CRC algorithm works
Error Control Coding
last updated Dec 2014