yawiki.org entry for Decoding methods

	Navigation Home Recent Most Active Popular Blog Credits RSS
	Interaction Register Statistics
	Help Suggestions Contact Us How to Edit Help

[Edit]

This article discusses common methods in communication theory for decoding codewords sent over a noisy channel (such as a binary symmetric channel).

    Decoding methods
        Notation
        Ideal observer decoding
        Maximum likelihood decoding
        Minimum distance decoding
        Syndrome decoding

top

Notation
Henceforth

C subset mathbb_2^n

shall be a (not necessarily linear) code of length

n

;

x,y

shall be elements of

mathbb_2^n

; and

d(x,y)

shall represent the Hamming distance between

x,y

top

Ideal observer decoding

Given a received codeword

x in mathbb_2^n

, ideal observer decoding picks a codeword

y in C

to maximise:

$mathbb(y mbox mid x mbox)$

-the codeword (or a codeword)

y in C

that is most likely to be received as

x

.

Where this decoding result is non-unique a convention must be agreed. Popular such conventions are:

Request that the codeword be resent;

Choose any one of the possible decodings at random.

top

Maximum likelihood decoding

Given a received codeword

x in mathbb_2^n

maximum likelihood decoding picks a codeword

y in C

to maximise:

$mathbb(x mbox mid y mbox)$

-the codeword that was most likely to have been sent given that

x

was received. Note that if all codewords are equally likely to be sent during ordinary use, then this scheme is equivalent to ideal observer decoding:

egin mathbb(x mbox mid y mbox) & = & rac \ && \ & = & rac rac \ && \ & = & rac \ && \ & = & mathbb(y mbox mid x mbox) \ end

As for ideal observer decoding, a convention must be agreed for non-unique decoding. Again, popular such conventions are:

Request that the codeword be resent;

Choose any one of the possible decodings at random.

top

Minimum distance decoding

Given a received codeword

x in mathbb_2^n

, minimum distance decoding picks a codeword

y in C

to minimise the Hamming distance

$d(x,y) =$

-the codeword (or a codeword)

y in C

that is as close as possible to

x in mathbb_2^n

.

Notice that if the probability of error on a discrete memoryless channel

p

is strictly less than one half, then minimum distance decoding is equivalent to maximum likelhood decoding since if

$d(x,y) = d$

then:

egin mathbb(y mbox mid x mbox) & = & (1-p)^p^d \ && \ & = & (1-p)^n left( rac ight)^d \ end

which (since

p

is less than one half) is maximised by minimising

d

.

As for other decoding methods, a convention is agreed for non-unique decoding. Popular such conventions are:

Request that the codeword be resent;

Choose any one of the possible decodings at random.

top

Syndrome decoding
Syndrome decoding is a highly efficient method of decoding a linear code over a noisy channel - ie one on which errors are made. In essence, syndrome decoding is minimum distance decoding using a reduced lookup table. It is the linearity of the code which allows for the lookup table to be reduced in size.

Suppose that

Csubset mathbb_2^n

is a linear code of length

n

and minimum distance

d

with parity check matrix

H

. Then clearly

C

is capable of correcting upto

$t=lfloorrac$

floor

errors made by the channel (since if no more than

t

errors are made then minimum distance decoding will still correctly decode the incorrectly transmitted codeword).

Now suppose that a codeword

x in mathbb_2^n

is sent over the channel and the error pattern

e in mathbb_2^n

occurs. Then

z=x+e

is received. Ordinary minimum distance decoding would lookup the vector

z

in a table of size

|C|

for the nearest match - ie an element (not necessarily unique)

c in C

with

$d(c,z) leq d(y,z)$

for all

y in C

. Syndrome decoding takes advantage of the property of the parity matrix that:

$Hx = 0$

for all

x in C

. The syndrome of the received

z=x+e

is defined to be:

$Hz = H(x+e) =Hx + He = 0 + He = He$

Under the assumption that no more than

t

errors were made during transmission the receiver looks up the value

He

in a table of size

egin sum_^t inom < |C| \ end

(for a binary code) against pre-computed values of

He

for all possible error patterns

e in mathbb_2^n

. Knowing what

e

is, it is then trivial to decode

x

as:

$x = z - e$

Notice that this will always give a unique (but not necessarily accurate) decoding result since

Hx = Hy

if and only if

x=y

. This is because the parity check matrix

H

is a generator matrix for the dual code

C^perp

and hence is of full rank.

	Source Privacy License Download Contact Us Atlas Scientus.org Dictionary (Yet Another Wiki) RC : 1.39 This article is licensed under the GNU Free Documentation License [copyleft]. It uses material from the Wikipedia article "Decoding methods". link