- Communication channels have a wide range of characteristics
- We must have a way to deal with errors
- error correction codes
- FEC(Forward Error Correction)
- error detection codes
- both must account for the types of erros that can occur, both have trade offs
- burst error
- single bit error
- sometimes location of an error will be known, erasure channel
Error - Correcting Codes
- four different codes
- Hamming Codes
- Hamming distance, the number of bits that are different between two sequences after exclusive or each bit together
- to reliably detect d errors you need a distance d+1 code
- total length of a block is n = m + r
- n bit code word
- code rate is the fraction of a codeword that carries non redundant information
- example
- 0000000000, 0000011111, 1111100000, 1111111111
- hamming distance of 5 so can correct double errors or quadruple errors
- useful for understanding block codes
- Binary Convolution Codes
- convolution code, no natural size, as incoming bits come in perform some operation
- each input bit produces two output bits on the right hand side that are XOR sums of the input and internal state
- each state is kept in 6 memory registers, each time another bit is inputted all values are shifted to the right, constraint length of this code is k = 7
- Viterbi algorithm
- soft decision decoding determine likeliness of 1, 0
- hard decision decode determine each bit is 0,1 before error correction
- Reed - Solomon Codes
- linear block codes, systematic
- operates on m bit symbols
- based on fact that every n degree polynomial is determined by n + 1 points so if 2 points are received in error, we can find the third point that will still lie on the line
- defined as polynomials that operate over finite fields, strong error correction properties makes them useful in DSL, CDs, DVDs and Blu-Ray
- Low - Density Parity Check Codes
- LDPC (Low - Density Parity Check Codes)
- each output bit is formed from only a fraction of the input bits
- matrix representation of code with low density of 1s, standard for video broadcasting, 10 Gbps Ethernet and 902.11
- these all add redundancy to the information that is sent
- systematic code, m data bits are sent along with check bits
- linear code check bits are computed as a function of the data bits
- usually using exclusive or
Error - Detecting Codes
- types of codes
- Parity
- parity bit appended to the end of data to make the number of 1s in the codeword even or odd
- 1011010 is sent in even parity it will be sent as 10110100 to signify that its already even by appending the 0
- can only reliably detect single bit error
- interleaving, can have multiple parity bits n x n matrix with parity bits at the end of each
- n+1 burst will still be undetected but now capable of correcting bits
- Checksums
- 16 bit internet checksum used as part of IP
- one's compliment arithmetic
- CRCs(Cyclic Redundancy Checks)
- polynomial code, treats bits as polynomial coefficients
- sender and receiver agree upon generator polynomial G(x) in advance
- algorithm
- let r be degree of G(x) append r zero bits to the low order end of the frame so its now m+r bits
- divide the bit string corresponding to G(x) into the bit string using modulo 2 division
- subtract the remainder using modulo 2 subtraction, the result is checksummed frame to be sent
- example as follows
- with single bit or 2 single bit errors the division will not be able to grant the same checksum if burst length is r+1 the remainder will be zero if and only if the burst is identical to G(x)
- IEE 802 standard is
- detects all bursts of length 32 or less and all bursts that are odd
