Look-ahead maximum likelihood sequence estimation decoder

Details Look-ahead maximum likelihood sequence estimation decoder Look-ahead maximum likelihood sequence estimation decoder

1999-04-21

2002-07-09

Chin, Stephen (Department: 2734)

Pulse or digital communications

Systems using alternating or pulsating current

Plural channels for transmission of a single pulse train

C375S265000, C375S341000, C714S794000, C714S795000

Reexamination Certificate

active

06418172

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to digital communications and, more particularly, to decoding data using a Near Maximum Likelihood Sequence Estimation.
BACKGROUND OF THE INVENTION
The dramatic increase in desktop computing power driven by intranet-based operations coupled with increased demand for time-sensitive data delivery among users has spurred development of high speed Ethernet local area networks (LANs). 100BASE-TX Ethernet (see IEEE Std. 802.3u-1995 CSMA/CD Access Method, Type 100 Base-T) using existing category 5 (CAT-5) copper wire, and the newly developing 1000BASE-T Ethernet (see IEEE Draft P802.3ab/D4.0 Physical Layer Specification for 1000 Mb/s Operation on Four Pairs of Category 5 or Better Twisted Pair Cable (1000 Base-T)) for Gigabit/s transfer of data over category 5 data grade copper wire, require new techniques in high speed symbol processing.
Conventionally, a single category 5, unshielded, twisted wire pair, with a length varying from 0 meter to 100 meters, is used to transmit data, in accordance with the 100BASE-TX data transmission protocol. Prior to transmission, the data is encoded at the transmitting end and is subsequently decoded at the receiving end. A well known encoding scheme, called MLT-3, is typically used to encode the data (See American National Standard Information system, Fiber Distributed Data Interface (FDDI)—Part: Token Ring Twisted Pair Physical Layer Medium Dependent (TP-PMD), ANSI X3.263:199X). In the MLT-3 encoding scheme, a logic 1 is transmitted as either a −1 or +1 and a logic 0 is transmitted as a 0.
A data signal appearing at time k at the receiving end of a category 5 wire (hereinbelow referred to as the channel) depends not only on the data transmitted at time k, but also on the previously transmitted data and the noise generated in the channel, creating difficulties in decoding the transmitted data.
One method for decoding the MLT-3 encoded, transmitted data is the so-called Delayed Decision Feedback Sequence Estimation(DDFSE) which, in turn, uses the well-known Viterbi algorithm. One disadvantage of the Viterbi algorithm is that it assumes the noise generated in a transmission channel is an additive white Gaussian noise. It is well known, however, that the noise generated in a category 5 100BASE-TX transmission channel is a cross-talk noise which has a different characteristic than the additive white Gaussian noise.
Another disadvantage of the DDFSE algorithm is that it requires additional signal processing steps. Moreover, to obtain acceptable bit error rate (BER)—which is the probability that a bit is decoded erroneously (the IEEE 802.3 specification calls for a BER of less than or equal to 1e-6)—using the Viterbi algorithm, large values of trace-back depth are typically needed, resulting in undesirable increases in the latency, which, in turn, requires more hardware to ensure that the processing of the current data is completed before the arrival of the next data. Furthermore, the DDFSE algorithm requires feedback, precluding the use of pipelining for the processing of the signals.
Moreover, because the Viterbi algorithm uses the well-known trace-back technique, a decoder implementing the Viterbi algorithm requires a relatively large amount of memory, read-write pointers and dual port random access memories, adding to the complexity and the manufacturing cost of the decoder.
Therefore, a need continues to exist for an algorithm for decoding transmitted data that is simple, computationally efficient and inexpensive.
SUMMARY OF THE INVENTION
A Nearest Neighbor Look-Ahead Maximum Likelihood Estimation Sequence (LA-MLSE) algorithm, in accordance with one embodiment of the present invention, decodes the MLT-3 encoded signal at time k—where k denotes the time index—which signal is transmitted via a category 5 transmission channel, by evaluating the signals received at the receiving end at times k, k+1, k+2, etc. The number of the received signals that the algorithm uses to decode is called the “depth” of the LA-MLSE. The algorithm assumes that the transmission channel has a z-transform defined by the expression (1+&agr;×z
−1
), where &agr; is a number greater than 0 and smaller or equal to 1.
In some embodiments of the present invention, the algorithm uses a depth of 3, in which case, to make the estimation, the algorithm forms the following three vectors: (1) a vector of the encoder input bit signals A=A{k, k+1, k+2}, with A(k), A(k+1) and A(k+2) respectively representing the encoder input bit signals at times k, k+1 and k+2; (2) a vector of the noise-free encoder channel output symbol signals Y=Y{A(k), A(k+1), A(k+2)}, with Y(A(k)), Y(A(k+1)) and Y(A(k+2)) respectively representing the noise-free channel output symbol signals for the corresponding encoder input signals A(k), A(k+1) and A(k+2); and (3) a vector of the received signals R=R(A(k), A(k+1), A(k+2)), with R(A(k)), R(A(k+1)) and R(A(k+2)) respectively representing the received signals for the corresponding encoder input signals A(k), A(k+1) and A(k+2). The algorithm determines the Nearest Neighbor distance for each channel output vector which is of the form Y{1, A(k+1), A(k+2)}, where the Nearest Neighbor distance for each such channel output vector is defined as the shortest of all the distances between that channel output vector and all the other channel output vectors which are of the form Y{0, A(k+1), A(k+2)}, and where the distance between each two vectors is defined as the sum of the square of the differences between the corresponding signals of the two vectors for each of the times k, k+1, and k+2. If the distance between the received signal R and at least one of the channel output vectors which are of the form Y{1, A(k+1), A(k+2)} is shorter than the distance between the received signal R and the Nearest Neighbor of the signal Y{1, A(k+1), A(k+2)}, then A(k) is decoded as 1, otherwise A(k) is decoded as 0.
In an All Neighbors LA-MLSE algorithm, in accordance with another embodiment of the present invention, the algorithm decodes A(k) as 1, only if the distance between the received signal R and at least one of the channel output vectors which is of the form Y{1, A(k+1), A(k+2)} is shorter than all the distances between the signal R and each of the channel output vectors which is of the form Y{0, A(k+1), A(k+2)}, otherwise the algorithm decodes A(k) as 0.
In a Nearest Neighbor Adjusted Depth LA-MLSE algorithm, in accordance with another embodiment of the present invention, the depth parameter is varied to minimize the amount of computation. Therefore, if the distance obtained using the signals received during the first two time indices, i.e. k and k+1, is greater than a minimum distance, the signal received during the time index k+2 is omitted in decoding the encoded signal.


REFERENCES:
patent: 4456893 (1984-06-01), Otani
patent: 4701936 (1987-10-01), Clarke et al.
patent: 4888560 (1989-12-01), Ogura
patent: 4974185 (1990-11-01), Ohno et al.
patent: 5031194 (1991-07-01), Crespo et al.
patent: 5119196 (1992-06-01), Ayanoglu et al.
patent: 5245291 (1993-09-01), Fujimura
patent: 5291499 (1994-05-01), Behrens et al.
patent: 5465272 (1995-11-01), Smith
patent: 5481564 (1996-01-01), Kakuishi et al.
patent: 5502735 (1996-03-01), Cooper
patent: 5602507 (1997-02-01), Suzuki
patent: 5617450 (1997-04-01), Kakuishi
patent: 5638065 (1997-06-01), Hassner et al.
patent: 5654667 (1997-08-01), Adachi
patent: 5809079 (1998-09-01), Hayashi
patent: 5818378 (1998-10-01), Cheng et al.
patent: 5841478 (1998-11-01), Hu
patent: 5841484 (1998-11-01), Hulyalkar et al.
patent: 5859861 (1999-01-01), Oh
patent: 5872668 (1999-02-01), Muto
patent: 5895479 (1999-04-01), Suganuma
patent: 5909384 (1999-06-01), Tal et al.
patent: 5940442 (1999-08-01), Wong et al.
pate

Affiliated with

Also associated with

Rating

Look-ahead maximum likelihood sequence estimation decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Look-ahead maximum likelihood sequence estimation decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Look-ahead maximum likelihood sequence estimation decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2869471