Pulse or digital communications – Receivers – Particular pulse demodulator or detector
Reexamination Certificate
1999-02-13
2003-09-09
Phu, Phuong (Department: 2631)
Pulse or digital communications
Receivers
Particular pulse demodulator or detector
C375S229000
Reexamination Certificate
active
06618451
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to data communications and in particular to an efficient reduced state maximum likelihood sequence estimator for use in data communication systems.
2. Description of the Related Art
The received signal in a digital communication system includes noise and distortion caused at least in part by intersysmbol interference (ISI). One such digital communication system employs modems, which use digital modulation techniques to modulate and demodulate binary data over analog band-limited communications channels, e.g., telephone lines.
Modems typically conform to international standards to ensure interoperability with modems from other manufacturers. One such standard is the V.34 specification described in ITU-T Recommendation V.34, A Modem Operating at Data Signalling Rates of up to 28 800 bits/s for Use on the General Switched Telephone Network and on Leased Point-to-Point 2-Wire Telephone-Type Circuits, dated September, 1994 (previously CCITT Recommendation V.34), which is hereby incorporated herein, in its entirety, by reference. Another such standard is the V.90 specification described in ITU-T Recommendation V.90, A Digital Modem and Analogue Modem Pair For Use on the Public Switched Telephone Network (PSTN) At Data Signalling Rates of Up To 56 000 bits/s Downstream and Up To 33 600 bits/s Upstream, dated September, 1998, which is hereby incorporated herein, in its entirety, by reference.
Maximum Likelihood Sequence Estimators (MLSE) are widely used in data communications such as modem communications for decoding data passed through the channels with intersymbol interference (ISI) and for decoding convolutionally encoded data. The Viterbi algorithm (VA) is quite often used to implement MLSE. A brief description of the Viterbi algorithm, which is well known in the art, is provided to facilitate an understanding of the present invention.
Assume that a sequence of symbols x={x
i
}, i &egr;]−∝;∝[, x
i
&egr;A={a
1
, a
2
, . . . a
L
} is transmitted through a channel with impulse response h={h
i
}, such that h
i
≠0 only when 0<h
i
<=M, where M−1 is the number of h
i
story terms contained in the channel. The signal received at the other end of the channel in the absence of noise is defined as y=x*h, where “*” denotes a convolution. If the noise &eegr; is added to the signal in the channel, then the signal at the other end of the channel contains that noise and is defined as z=y+&eegr;. The receiver must reconstruct the transmitted sequence of symbols x, based on the received sequence z. At the time nT the following can be used to reconstruct the most recently sent symbol x
n
:
x
n
=(
y
n
−(
x
n−1
h
1
+. . . +x
n−M+1
h
M−1
))/
h
o
(1)
From the equation (1) it can be seen that besides the received signal y
n
, value x
n
depends on the vector {x
n−1
, . . . x
n−M+1
} of M−1 previously decoded symbols. That vector will be further referred to herein as a state. With each new decoded symbol, the state of the decoder changes to reflect the new value of the vector {x
n−1
, . . . x
n−M+1
}. That is, if at a time nT the state was {x
n−1
, . . . x
n−M+1
} then at a time (n+1)T the new state will be {x
n
, . . . x
n−M+2
} and so forth. That change will be further referred herein as a state transition. The h
i
story of state transitions represents a state trajectory. Since each symbol x
n
belongs to a finite alphabet A of size L, there can only be K=L
M−1
unique states. All states comprise a state set S={s
1
, s
2
, . . . s
k
}, where each element S
k
is a vector of M−1 elements that belong to alphabet A such that s
k
≠s
m
for k≠m.
Since the noiseless channel output y
n
is not available to the receiver, the value of x
n
cannot be determined with absolute certainty, and instead an estimate is used:
x
n
=(
z
n
−(
x
n−1
h
1
+. . . +x
n−M+1
h
M−1
))/
h
o
(2)
The Euclidean distance, t
n1
, from the alphabet element a
1
to the estimate x
n
, is defined as t
n1
−(x
n
−a
1
)
2
, which provides the measure of likelihood that the transmitted symbol x
n
equals a
1
at the time nT.
In a simple receiver, the alphabet element with the minimum Euclidean distance is selected and x
n
is assumed to be equal to that alphabet element. However if x
n
is not determined correctly (e.g. due to noise), that incorrect value will cause incorrect state transition causing future symbols to be decoded incorrectly affecting in turn future state transitions and so on. That condition is called “error propagation.”
To avoid the “error propagation” problem, all possible decoder states and all possible state transitions must be examined. A state metric D
n
={d
n1
, d
n2
, . . . , d
nK
} defines the measure of likelihood, such that each element d
nk
defines the measure of likelihood of state s
k
at a time nT which is directly related to the Euclidean distance of the elements of the symbol vector corresponding to state s
k
. The relationship of the state metric D and state set S is shown in
FIG. 1
in which set S is shown to consist of four states s
1
through s
4
. In the example shown in
FIG. 1
A&egr;(0,1) and L=2 and M=3. Each state s
1
through s
4
has an associated state metric d
1
through d
4
in D.
1. For each state s
k
of a set S calculate a symbol estimate x
nk
, based on received symbol z
n
according to equation (2) above.
2. For each state s
k
of a set S consider L transitions from that state, and for each transition combination (k, 1) calculate a combined metric d
k1
=d
k
+t
k1
, where t
k1
is an Euclidean distance of the alphabet element a
1
from the symbol estimate x
nk
, t
k1
=(x
nk
−a
1
)
2
.
3. For each state s
k
of a set S consider L transitions to that state, selecting the one with the minimum combined metric d calculated during step 2 and assign its value to the state metric d
k
.
4. Find the state with the minimum metric d
k
storing a transition that led to that state as a candidate optimal trajectory.
5. The first four steps are repeated for each value of n, i.e., for each received symbol.
The optimal trajectory for the state with the smallest metric is considered the optimal path (most likely sequence) at a given time. As it can be seen from the above description, the computational complexity of the Viterbi algorithm is proportional to L
M
. For high speed communication systems over band limited channels the value of L is large, thus making the Viterbi algorithm complexity potentially prohibitive even for channels with relatively short impulse response.
One use of the Viterbi algorithm, as stated above, is in modem data transmission. Such transmission is always affected by linear intersymbol interference (ISI) and by noise. These two impairments are typically countered by equalization, a technique which minimizes ISI and noise at periodic instances at which decisions are taken. The ultimate goal of the equalizer is to minimize a combined effect of ISI and noise and thus reduce the probability of incorrect decisions. Traditionally, dial up modem designers used Linear Equalizers (LE) to do the job. The performance of LE is quite satisfactory when the combination of the channel impulse response and the equalizer can form a Nyquist-1 pulse to satisfy the distortionless (zero ISI) criterion. To achieve that goal, the bandwidth of the channel has to be wider than the symbol rate employed by the modem.
The new generation of modems conforming to the V.90 recommendation no longer satisfy this criterion. The impulse response of a PCM codec is designed to achieve satisfactory transmission of voice signals, and its bandwidth is always more narrow than the 8000 Hz symbol rate
Phu Phuong
Zagorin O'Brien & Graham LLP
LandOfFree
Efficient reduced state maximum likelihood sequence estimator does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient reduced state maximum likelihood sequence estimator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient reduced state maximum likelihood sequence estimator will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3044297