Error-Control Coding

Hesham M. Al-Salman

In This Presentation

Definition and importance of coding.

Types of codes: block and convolutional.

Linear block codes.

Convolutional codes.

Turbo Codes.

Conclusion

Coding: Pros and Cons

Channel or error-control coding is adding redundant bits to detect only or detect and correct errors.

Goal: Increase the operational range, reduce error probability or reduce power transmission requirements.

Typical gains are in the range of 4-5 dB in SNR for BER and much better FER gains. Much higher gains are now possible with relatively little cost than other methods.

Sacrifice: Bit rate and/or complexity.

Types of Codes

In general there are two types of codes:

Block codes:

Hamming

Cyclic

BCH and Reed Solomon Codes

Convolutional codes

Trellis-coded modulation (TCM)

Space-time

The Distance

Hamming Distance is the number of differences between code words.

e.g. d (1101, 0101) = 1

d (0000, 0111) = 3

Minimum distance (d_min): the min no of differences between any two code words

Adding redundant bits limits the number of code words used. Hence, increasing the minimum distance between them

Example: (7,4) Block Code

Linear Block Codes

Check the previous code to see that it consists of block of code words. Your message will be changed to this format.

Add any two code words to get a third one.

A code with d_min is ‘guaranteed’ to correct (d_min – 1) / 2 errors or detect d_min – 1 errors.

d_min = w_min (the smallest weight of the nonzero code word.

Any linear block code can be systematic:

Hamming Codes

Definition:

(n,k) = (2^m – 1, 2^m – 1 – m)

For Hamming codes d_min = 3. Therefore, they are capable of correcting any single error or detecting any double error.

Encoding Hamming Codes

Encoding can be done using the generator matrix:

c = u × G

For the (7, 4) code mentioned earlier:

Decoding Hamming Codes:

The direct way is to measure the Hamming distance between the transmitted code word and all possible code words (16 in the past example). The minimum distance gives the correct transmitted code word.

In practice, syndrome decoding is used.

In syndrome decoding the received code word is multiplied by a matrix called the parity check matrix or the H matrix (G×H = 0)

The result indicates the error pattern (if any).

Cyclic Codes

An (n, k) linear block code C is cyclic if every shift of any code word in C is also a code word in C.

The (7,4) Hamming code discussed before is a cyclic code.

For every cyclic code there is a single minimum degree r generating polynomial g(x)

All code words are generated from g(x)

Encoding Cyclic Codes

Encoding can be done by multiplying the message polynomial by the generating polynomial g(x)

e.g. for the mentioned (7, 4) code g(X) = 1+X+X³. The message 1001 in polynomial format is 1 + X³. The resulting code word is (1+X+X³) × (1 + X³) = 1 + X + X⁴ + X⁶ (1100101)

(7,4) Code Generated by 1+X+X³

Infor. Code Code polynomials

0000 0000000 0 = 0 . g(X)

1000 1101000 1 + X + X³ = 1 . g(X)

0100 0110100 X + X² + X⁴ = X . g(X)

1100 1011100 1 + X² + X³ + X⁴ = (1 + X) . g(X)

0010 0011010 X² + X³ + X⁵ = X² . g(X)

1010 1110010 1 + X+ X² + X⁵ = (1 + X²) . g(X)

0110 0101110 X+ X³ + X⁴ + X⁵ = (X+ X²) . g(X)

1110 1000110 1 + X⁴ + X⁵ = (1 + X + X²) . g(X)

0001 0001101 X³ + X⁴ + X⁶ = X³ . g(X)

(7,4) Code Generated by 1+X+X³

Infor. Code Code polynomials

1001 1100101 1 + X + X⁴ + X⁶ = (1 + X³) . g(X)

0101 0111001 X+ X² + X³ + X⁶ = (X+ X³) . g(X)

1101 1010001 1 + X² + X⁶ = (1 + X + X³) . g(X)

0011 0010111 X² + X⁴ + X⁵ + X⁶ = (X² + X³). g(X)

1011 1111111 1 + X + X² + X³ + X⁴ + X⁵ + X⁶
= (1 + X² + X³) . g(X)

0111 0100011 X + X⁵ + X⁶ = (X + X² + X³). g(X)

1111 1001011 1 + X³ + X⁵ + X⁶
= (1 + X + X² + X³) . g(X)

Decoding Cyclic Codes

Syndrome decoding is again used to find the error pattern and correct it.

The difference here (from Hamming codes) is that the cyclic property can be used to simplify the Encoder/Decoder circuit very much.

BCH Codes

Bose-Chaudhuri-Hocquenghem (BCH) codes are a class of cyclic codes constructed using finite fields.

Their generator polynomials are factors of p^2m-1 + 1 (where p is a prime number).

Tables of BCH generator polynomials are found in most digital communications text books.

Reed Solomon Codes

These are a sub-class of BCH codes with non-binary alphabets.

Non-binary codes consist of n symbols rather than n bits.

This ‘grouping’ of bits enables the construction of long codes with very strong error correcting capabilities.

The added complexity is almost negligible.

Convolutional Codes

Described by (n,k) and K (constraint length).

Main difference: no block, only a bit stream.

Unlike block codes minimum distance and performance properties are not well-established mathematically.

Main performance criterion is the minimum free distance d_free.

Convolutional Code Example

Rate 1/2 (2,1) code with g₁(D) = 1 + D + D² , g₂(D) = 1 + D²

State Diagram Representation

Trellis Diagram Representation

Decoding

Decoding is done by maximum likelihood.

One method of decoding is the Viteribi algorithm.

It measures the path metric of all possible paths and eliminates the ones with higher pm until there is only one survivor.

This can be done in hard decision or soft decision (better performance)

Viterbi Algorithm

Performance

The longer the constraint length the better.

The longer the depth of the encoder the better.

About 2.5 dB increase in performance between HD and SD decoding.

Reaches near asymptotic value at relatively high bit error rates.

Puncturing can be introduced to improve bit rate with some loss of performance.

Trellis Coded Modulation

Combined coding and modulation.

Error correcting capabilities without the sacrifice of information bit rate.

e.g. if a BPSK modulation technique is used for transmission, one can add a rate 1/2 convolutional encoder and use QPSK modulation.

Set partitioning is used to ensure performance enhancement.

The distance here is no longer Hamming but rather Euclidean distance.

Encoding and decoding is as convolutional codes, except that one deals with symbols rather than bits.

General TCM Block Diagram

Space-Time Codes

Combines TCM with multiple transmit antennas.

Output of one transmit antenna is a sequence of coded symbols different than any other transmit antenna.

All transmit antennas work on the same frequency, time slot, power…etc (i.e. overlapping signals).

Very strong error-correcting capabilities in fading channels.

A Space-Time Encoder

Turbo Codes

New: introduced in 1993

In addition to the encoder there is an interleaver to shuffle bits.

De-interleaving is done at the decoder.

Promises a lot: Shannon limit.

For AWGN channel Eb/N0=0.7 dB for BER=10^-5.

Problems: delay, complexity.

Turbo Encoder

Performance Simulations

In the coming slides we have simulation for various coding schemes:

Block AND BCH codes.

1/2 and 1/3 convolutional codes.

Concatenation of 1/2 conv and RS.

TCM and space-time.

Slide 32

Slide 33

Slide 34

Slide 35

The Dilemma:
Block or Convolutional?

Many debates are out there in the literature on which coding technique is better.

It really depends on the application.

For an AWGN channel convolutional codes are preferable. They approach asymptotic gains at relatively high BER (10^-5 to 10^-7) (e.g sat TV).

For low BER requirements RS codes are better because they achieve higher asymptotic gains at lower BER (10^-10).

Concatenation of RS and convolutional codes produce very strong error correcting capabilities.

Continued…

Near Shannon-limit performance is possible with turbo codes, making them suitable for non-real time applications.

Space-time codes gave strong error correcting capabilities for fading channels.

NASA Voyager mission transmission of 2 Mbps data rates at E_b/N₀=2.53 dB uses a concatenation of a rate 1/2 K=7 convolutional encoder inner code and a (255, 233) RS outer code with BER=10^-6.

A 48 Mbps satellite TDMA system with BER around 10^-11 using a (204, 192) RS code was described by Berlekamp et al.


	Definition and importance of coding.
	Types of codes: block and convolutional.
	Linear block codes.
	Convolutional codes.
	Turbo Codes.
	Conclusion


	Channel or error-control coding is adding redundant bits to detect only or detect and correct errors.
	Goal: Increase the operational range, reduce error probability or reduce power transmission requirements.
	Typical gains are in the range of 4-5 dB in SNR for BER and much better FER gains. Much higher gains are now possible with relatively little cost than other methods.
	Sacrifice: Bit rate and/or complexity.


In general there are two types of codes:
	Block codes:
		Hamming
		Cyclic
		BCH and Reed Solomon Codes
	Convolutional codes
		Trellis-coded modulation (TCM)
		Space-time


	Hamming Distance is the number of differences between code words.
	e.g. d (1101, 0101) = 1
	d (0000, 0111) = 3
	Minimum distance (d_min): the min no of differences between any two code words
	Adding redundant bits limits the number of code words used. Hence, increasing the minimum distance between them


	Check the previous code to see that it consists of block of code words. Your message will be changed to this format.
	Add any two code words to get a third one.
	A code with d_min is ‘guaranteed’ to correct (d_min – 1) / 2 errors or detect d_min – 1 errors.
	d_min = w_min (the smallest weight of the nonzero code word.
	Any linear block code can be systematic:


	Definition:
	(n,k) = (2^m – 1, 2^m – 1 – m)
	For Hamming codes d_min = 3. Therefore, they are capable of correcting any single error or detecting any double error.


	Encoding can be done using the generator matrix:
	c = u × G
	For the (7, 4) code mentioned earlier:


	The direct way is to measure the Hamming distance between the transmitted code word and all possible code words (16 in the past example). The minimum distance gives the correct transmitted code word.
	In practice, syndrome decoding is used.
	In syndrome decoding the received code word is multiplied by a matrix called the parity check matrix or the H matrix (G×H = 0)
	The result indicates the error pattern (if any).


	An (n, k) linear block code C is cyclic if every shift of any code word in C is also a code word in C.
	The (7,4) Hamming code discussed before is a cyclic code.
	For every cyclic code there is a single minimum degree r generating polynomial g(x)
	All code words are generated from g(x)


	Encoding can be done by multiplying the message polynomial by the generating polynomial g(x)
	e.g. for the mentioned (7, 4) code g(X) = 1+X+X³. The message 1001 in polynomial format is 1 + X³. The resulting code word is (1+X+X³) × (1 + X³) = 1 + X + X⁴ + X⁶ (1100101)


	Infor. Code Code polynomials
	0000 0000000 0 = 0 . g(X)
	1000 1101000 1 + X + X³ = 1 . g(X)
	0100 0110100 X + X² + X⁴ = X . g(X)
	1100 1011100 1 + X² + X³ + X⁴ = (1 + X) . g(X)
	0010 0011010 X² + X³ + X⁵ = X² . g(X)
	1010 1110010 1 + X+ X² + X⁵ = (1 + X²) . g(X)
	0110 0101110 X+ X³ + X⁴ + X⁵ = (X+ X²) . g(X)
	1110 1000110 1 + X⁴ + X⁵ = (1 + X + X²) . g(X)
	0001 0001101 X³ + X⁴ + X⁶ = X³ . g(X)


	Infor. Code Code polynomials
	1001 1100101 1 + X + X⁴ + X⁶ = (1 + X³) . g(X)
	0101 0111001 X+ X² + X³ + X⁶ = (X+ X³) . g(X)
	1101 1010001 1 + X² + X⁶ = (1 + X + X³) . g(X)
	0011 0010111 X² + X⁴ + X⁵ + X⁶ = (X² + X³). g(X)
	1011 1111111 1 + X + X² + X³ + X⁴ + X⁵ + X⁶ = (1 + X² + X³) . g(X)
	0111 0100011 X + X⁵ + X⁶ = (X + X² + X³). g(X)
	1111 1001011 1 + X³ + X⁵ + X⁶ = (1 + X + X² + X³) . g(X)


	Syndrome decoding is again used to find the error pattern and correct it.
	The difference here (from Hamming codes) is that the cyclic property can be used to simplify the Encoder/Decoder circuit very much.


	Bose-Chaudhuri-Hocquenghem (BCH) codes are a class of cyclic codes constructed using finite fields.
	Their generator polynomials are factors of p^2m-1 + 1 (where p is a prime number).
	Tables of BCH generator polynomials are found in most digital communications text books.


	These are a sub-class of BCH codes with non-binary alphabets.
	Non-binary codes consist of n symbols rather than n bits.
	This ‘grouping’ of bits enables the construction of long codes with very strong error correcting capabilities.
	The added complexity is almost negligible.


	Described by (n,k) and K (constraint length).
	Main difference: no block, only a bit stream.
	Unlike block codes minimum distance and performance properties are not well-established mathematically.
	Main performance criterion is the minimum free distance d_free.


	Rate 1/2 (2,1) code with g₁(D) = 1 + D + D² , g₂(D) = 1 + D²


	Decoding is done by maximum likelihood.
	One method of decoding is the Viteribi algorithm.
	It measures the path metric of all possible paths and eliminates the ones with higher pm until there is only one survivor.
	This can be done in hard decision or soft decision (better performance)


	The longer the constraint length the better.
	The longer the depth of the encoder the better.
	About 2.5 dB increase in performance between HD and SD decoding.
	Reaches near asymptotic value at relatively high bit error rates.
	Puncturing can be introduced to improve bit rate with some loss of performance.


	Combined coding and modulation.
	Error correcting capabilities without the sacrifice of information bit rate.
	e.g. if a BPSK modulation technique is used for transmission, one can add a rate 1/2 convolutional encoder and use QPSK modulation.
	Set partitioning is used to ensure performance enhancement.
	The distance here is no longer Hamming but rather Euclidean distance.
	Encoding and decoding is as convolutional codes, except that one deals with symbols rather than bits.


	Combines TCM with multiple transmit antennas.
	Output of one transmit antenna is a sequence of coded symbols different than any other transmit antenna.
	All transmit antennas work on the same frequency, time slot, power…etc (i.e. overlapping signals).
	Very strong error-correcting capabilities in fading channels.


	New: introduced in 1993
	In addition to the encoder there is an interleaver to shuffle bits.
	De-interleaving is done at the decoder.
	Promises a lot: Shannon limit.
	For AWGN channel Eb/N0=0.7 dB for BER=10^-5.
	Problems: delay, complexity.


	In the coming slides we have simulation for various coding schemes:
		Block AND BCH codes.
		1/2 and 1/3 convolutional codes.
		Concatenation of 1/2 conv and RS.
		TCM and space-time.


	Many debates are out there in the literature on which coding technique is better.
	It really depends on the application.
	For an AWGN channel convolutional codes are preferable. They approach asymptotic gains at relatively high BER (10^-5 to 10^-7) (e.g sat TV).
	For low BER requirements RS codes are better because they achieve higher asymptotic gains at lower BER (10^-10).
	Concatenation of RS and convolutional codes produce very strong error correcting capabilities.


	Near Shannon-limit performance is possible with turbo codes, making them suitable for non-real time applications.
	Space-time codes gave strong error correcting capabilities for fading channels.
	NASA Voyager mission transmission of 2 Mbps data rates at E_b/N₀=2.53 dB uses a concatenation of a rate 1/2 K=7 convolutional encoder inner code and a (255, 233) RS outer code with BER=10^-6.
	A 48 Mbps satellite TDMA system with BER around 10^-11 using a (204, 192) RS code was described by Berlekamp et al.