EEL 6509 Wireless Communications- Block Codes

Dr. John M. Shea

Dr. John M. Shea

- Binary Block Codes
- Error Correcting Codes - cont.
- Binary BCH Codes
- Error Probabilities

- Error Detecting Codes
- Cyclic Redundancy Check (CRC) Codes

- Error Correcting Codes - cont.
- Nonbinary Block Codes
- Reed-Solomon Codes

- powerful class of cyclic codes
- provide large selection of block lengths, code rates,

and error-correcting capabilities - also available in non-binary alphabets
- (
*n*,*k*) BCH codes exist for any integers*m*>3 and*t*< 2^{m-1}such that:

*n*=2^{m}-1

- such a code is called a
*t*-error-correcting BCH code

- Prob. of codeword error is

where*p*= prob. of code symbol error - Prob. of bit error=
*P*_{b}

- See Fig. 5.22, [1], p. 299 (in the PDF file)
- For fixed channel-symbol error prob.,
shorter Hamming codes do better than longer Hamming
codes.
- This is because the prob. of codeword error is greater for the longer code since there are more code symbols that can be in error.

- The performance difference can also be understood by
considering the rates of the codes.
- For example, the (7,4) code is rate 0.57,

while the (31,26) code is rate 0.84. - Thus the redundancy is greater for the (7,4) code.

- For example, the (7,4) code is rate 0.57,
- Note that as the error correcting capability of a code goes
up, the probability of bit error goes down, as expected.

- For fixed channel-symbol error prob.,
shorter Hamming codes do better than longer Hamming
codes.
- For BPSK transmission,

where*E*_{c}= energy per code symbol - To maintain constant energy per information bit regardless
of coding, we set

- See Fig. 5.23, [1], p. 300, (in the PDF file)
- Note that now the Hamming codes performance improves as the
block length increases.
- The effect of the difference in code rate is compensated for by the amount of energy transmitted per code symbol.
- In general, longer codes outperform shorter codes.

- The
*t*=15 code actually performs worse than the*t*=10 code.- At very low rates, the loss in information rate is not compensated for by the increase in coding gain for BCH codes.

- Note that at low SNRs, less-powerful codes or even no code
can outperform complicated coding schemes, such as the (127, 36)
*t*=15 BCH code.

- Note that now the Hamming codes performance improves as the
block length increases.

- Class of cyclic or polynomial codes commonly used for error detection
- strong error detection capability, typically:
- All single bit errors
- All double bit errors
- All odd numbers of errors
- All burst errors of length <
*r*, where*r*= the redundancy - of all other error bursts

- high rate

**Example**Ethernet, CRC-32 code

32 bits used to protect 1500 bytes = 12000 bits in a packet

**Example**IS-54 US Digital Cellular System, CRC-7 code

7 bits used to protect 77 bits

- simple encoding and decoding using shift registers or bit operations
- standard CRC code polynomials are available for many
redundancy sizes

- typically defined over Galois extension fields
- binary math is defined as math over the Galois field with 2
elements, GF(2)
- an extension field of GF(2) is denoted GF(2
^{m}) and consists of elements

- the representation of elements in GF(2
^{m}) shown above is known as the*power representation* - each element in GF(2
^{m}) can also be represented as a polynomial of degree*m*-1 or less

where - the representation above is known as the
*polynomial representation* - the mapping between the power representation and the
power representation and the polynomial representation is
determined by an
*irreducible polynomial*that defines the Galois extension field - any element in GF(2
^{m}) can be represented by an*m*-bit binary sequence corresponding to the coefficients of its polynomial representation. **Example**See GF(2^{4}) generated by*p*(*X*)=1+*X*+*X*^{4}in Table 2.8 from [2], p. 33

- An (
*n*,*k*) Reed-Solomon (RS) block code over GF(2^{m}) has- block length
*n*=2^{m}-1 - number of parity symbols
- minimum distance
*d*_{min}=2*t*+1 - error correcting capability
*t*bits

- block length

**Example** *t*=2 code over GF(2^{3})

(7,3) code

Message symbols: 3 symbols from GF(2^{3}) = 3 (3 bit symbols) = 9 bits

Coded symbols: 7 (3 bit symbols) = 21 bits

2^{9} = 512 code words

2^{21} = 2 million possible received words

(In comparison, the (7,3) binary code has 8 codewords and 128 possible received words.)

For the (7,3) RS code,

For the (7,3) binary code,

- Reed-Solomon codes can have a huge no. of codewords:
- the NASA Voyager satellite used a (255, 223) RS code from GF(2
^{8}) - the number of codewords for this code is
(Physicists estimate that the number
of molecules in the universe is 10
^{90})

- the NASA Voyager satellite used a (255, 223) RS code from GF(2
- RS codes can be decoded with algebraic decoders
- RS codes are particularly useful for correcting bursts of
errors or for systems that employ M-ary orthogonal modulation
- used in wireless communications and in CD and DVD players

System |
Error Correcting Code | Error Detecting Code | |

AMPS - US Analog Cellular System |
|||

forward blank & burst | (40,28) BCH | ||

reverse blank & burst | (48,36) BCH | ||

IS-54 - US Digital Cellular System |
|||

voice channel | (convolutional) | 7-bit CRC | |

digital verification color code | (12,8) Hamming | ||

GSM |
|||

voice | (conv.) | 3-bit CRC on most- | |

important bits | |||

control | (conv.) | 40-bit CRC | |

IS-95 - CDMA Cellular System |
|||

various | (conv.) | 16, 12, 10, 8, 6-bit CRC codes | |

Digital European Cordless Telephone (DECT) |
(none) | 16-bit CRC | |

SINCGARS Military Frequency Hop Radio |
Reed-Solomon | ||

IEEE 802.11 Wireless LAN |
?? | 16-bit CRC | |

Bluetooth |
|||

Header | rate-1/3 repetition | 8-bit CRC | |

Data | (15,10) shortened Hamming code | 16-bit CRC | |

NASA Voyager Satellite |
(255,223) Reed-Solomon code | ||

(with conv. code) |

Information for this table collected from
[3]-[5].

**1**-
B. Sklar,
*Digital Communications: Fundamentals and Applications*.

Englewood Cliffs, New Jersey: Prentice Hall, 1988. **2**-
S. Lin and D. J. Costello,
*Error Control Coding: Fundamentals and Applications*.

New Jersey: Prentice-Hall, 1983. **3**-
T. S. Rappaport,
*Wireless Communications: Principles and Practice*.

New Jersey: Prentice Hall, 1996. **4**-
V. K. Garg,
*IS-95 CDMA and cdma2000: Cellular/PCS Systems Implementation*.

Upper Saddle River, New Jersey: Prentice Hall, 2000. **5**-
S. B. Wicker and V. K. Bhargava, eds.,
*Reed-Solomon Codes and Their Applications*.

Piscataway, New Jersey: IEEE Press, 1994.

This document was generated using the
**LaTeX**2`HTML` translator Version 98.1p1 release (March 2nd, 1998)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:

**latex2html** `-no_navigation -split 2 -white blockcodes`.

The translation was initiated by John Shea on 2001-04-04