6

P. A. HUMBLET

The sequence of N binary digits is usually parsed in groups of n (with values 1,2, • • • 2"). If

the kth group has value mik) — i then the waveform slit**kT) is transmitted (this is just the

waveform sl it) delayed by kT). The received waveform is the sum of the waveforms

corresponding to each group plus the noise thus it has the form

r

(

r

) -

^smik)it-kT)+nit)

.

To generate the most likely sequence the demodulator must find the values m(0), m(l), • • • ,

mi ) minimizing (1). This operation can be rewritten as maximizing

N-n

S irit)Jm(kHt-kT) - ±Mm(k)it~kT)\\2- 2 sm(k,)it-k'T),smik)it-kT)» (2)

k-0

2

k'k

N

The only quantities depending on rit) in this formula are the — 2 n innerproducts rit)t

n

slit—kT). For k fixed the demodulator can either evaluate them directly, or first compute the

components of rit) in the space spanned by the slit—kT).

Maximizing (2) would be easy if slit—£T), sHt) were 0 for all ij and £ ^ 0, i.e. if

there were no "intersymbol interference". In that case each mik) can be decoded independently of

the others.

As observed by Nyquist, this condition is met if, for all ij,

£ S'(f + h&\f + UlK{f + •£)

/«_«, 1 1 1

is equal to afj for some atj and for / .

Waveforms are usually designed to (approximately) satisfy this condition, as the task of the

demodulator is then simplified. However it becomes increasingly hard to meet when the passband

of the channel is close to —-, as is the case in high performance modems, or when the channel

response Hif) is not known a priori.

If slit—klT), sjit) is negligible for |fc| L then an elegant algorithm is available to

maximize (2). It is a form of dynamic programming known to communication engineers as

Viterbi's algorithm.