Data Communications and
Networks
Layer 2: Channel coding
Pham Quang Thai – [Link]@[Link]
1
Data link layer tasks
Error and Error
Binary data Framing
flow control detection
Transmitted Impaired Received
Error Error and
Synchronize Binary data
detection Flow control
2
Concept of channel coding
• Reminding of Shannon’s theory
– Source entropy:
– Channel capacity:
• The source and channel are not related (source -
channel separation theorem)
– Source can be compress (source coding) to lower limit
entropy disregarding channel characteristics
– Channel capacity depending on W and SNR and
independent of source characteristics
Concept of channel coding
• A source can be transmitted with no error if H<C
• Example: repetition code
– For bit 0, send [0|00000….0]
– What happen if bit rate H<C?
– What happen if bit rate H>C?
• Any error can be detect/correct by sending
codeword=[data bit|check bit] at rate H<C
• The method of converting between data and
codeword is called channel coding
Concept of Hamming distance
• The number of bit positions in which the
corresponding bits of two codewords of the same
length are different
Concept of Hamming distance
• Assuming d is the minimum Hamming distance
between codewords:
– Can detect all patterns of ≤(d-1) bit errors
– Can correct all patterns of ≤(d-1)/2 bit errors
Type of channel coding
• Error detection
– Block code (linear block code, cyclic code etc.)
• Error correction (or Forward Error Control – FEC)
– Block code (Hamming, BCH, Reed Solomon etc.) for 1st
generation FEC
– Concatenate code, convolution code for 2nd generation FEC
– Turbo code and Low-Density Parity-Check code (LDPC) for
3rd generation FEC
• 3rd generation FEC has reached the Shannon limit in
2001, the year Shannon pasted away
Error detection
• Block code
– Data is broken up into blocks of equal length
– Each block is “mapped” onto a larger block Example:
(6,4) code, codeword length n = 6, data bit k = 4,
check bit r = n-k = 2, code rate R = k/n = 2/3
• Linear block code
– Combination of any two codewords is a codeword
• Cyclic code
– Any shifted value of a codeword is a codeword
Linear block code – Parity code
• Linear transformation: D.G=C
– C is an n-element row vector containing the codeword
– D is a k-element row vector containing the message
– G is the k x n generator matrix
Syndrome Decoding
• What is the Hamming distance?
• Indicate error using syndrome value: S = D1+D2+D3+P
• Calculating syndrome S
Gk n I k k Ak ( n k )
H AT I ( n k )( n k )
S H (C E )T
Rectangular Parity Codes
• Linear transformation: D.G=C
• What is the Hamming distance?
•
Rectangular Parity Codes
Cyclic code – Cyclic redundant check (CRC)
• Linear transformation: D.G=C
• The generation matrix
• Is created using a generator polynomial
Cyclic code – Cyclic redundant check (CRC)
• Codeword generation
– Choose a generator G of length r+1 bits
– Choose R such that T is a multiple of G (T = A*G, for some
A)
– Now when T is divided by G there will be no remainder =>
no errors
– All done using mod 2 arithmetic
T = M 2r + R = A*G => M 2r = A*G + R (mod 2 arithmetic)
Let R = remainder of M 2r /G and T will be a multiple of G
Cyclic code – Cyclic redundant check (CRC)
• Error detection
T’=T+E=A*G+E
R’=T’/G
– If R’=0, no error or undetectable error
– If R’≠0, error
• Hamming distance depending on the generator
polynomial G and data length k
Some notes on CRC
• If the generator has more than one term and the
coefficient of x0 is 1, all single errors can be caught.
• If a generator cannot divide xt + 1
(t between 0 and n – 1), then all isolated double errors
can be detected.
• A generator that contains a factor of x + 1 can detect all
odd-numbered errors.
• All burst errors with L ≤ r will be detected.
• All burst errors with L = r + 1 will be detected with
probability 1 – (1/2)r–1.
• All burst errors with L > r + 1 will be detected with
probability 1 – (1/2)r.