# UMD ENEE 739C - ENEE 739C Lecture 3 (7 pages)

Previewing pages*1, 2*of 7 page document

**View the full content.**## ENEE 739C Lecture 3

Previewing pages *1, 2*
of
actual document.

**View the full content.**View Full Document

## ENEE 739C Lecture 3

0 0 21 views

Lecture Notes

- Pages:
- 7
- School:
- University of Maryland, College Park
- Course:
- Enee 739c - Advanced Topics In Signal Processing: Coding Theory

**Unformatted text preview: **

ENEE 739C Advanced Topics in Signal Processing Coding Theory Instructor Alexander Barg Lecture 3 draft 9 1 03 Decoding of codes Our task of code construction is not complete if we cannot decode the codes we are studying Decoding another major task in coding theory studied in a variety of scenarios Definition 1 Given a code C Hqn and a point y Hqn maximum likelihood or complete decoding takes y to one of the closest code vectors by the Hamming distance This procedure may be actually called minimum distance decoding the name maximum likelihood is justified in a short while Intuitively is seems natural to assume that this decoding is the best we can hope for in terms of minimizing the error rate Note if a vector x C say a binary code is sent over a binary symmetric channel W the probability that a vector y is received on its output P y x W n yx pw 1 p n w where w d x y If c is the decoding result the probability of a decoding error equals 1 P c y Therefore the mapping that minimizes the probability of error for the codeword ci is given by y ci Letting P y P c C P ci y P cj y j 6 i n W y c we have W n y c P c y P y P c If we assume that P c 1 M for every c C then maximum likelihood decoding is defined equivalently as y ci W n y ci W n y cj j 6 i Finally note that maximizing W n y c is equivalent to minimizing the distance d y c so minimum distance decoding is indeed max likelihood or ML decoding We know from ENEE722 that max likelihood decoding of a linear binary n k d code C can be implemented by the standard array or the syndrome trellis or by other equivalent means The problem is that all these methods for codes of large length and rate not very close to 0 or 1 are very computationally involved Therefore coding theory is also concerned with restricted decoding procedures One of the most commonly used is bounded distance decoding This name is used loosely for all procedures that find the closest codeword to the received vector in a sphere of some fixed radius t if

View Full Document