Pulse or digital communications – Systems using alternating or pulsating current – Plural channels for transmission of a single pulse train
Reexamination Certificate
2000-01-31
2003-10-14
Chin, Stephen (Department: 2734)
Pulse or digital communications
Systems using alternating or pulsating current
Plural channels for transmission of a single pulse train
C375S259000, C375S260000, C375S261000, C375S262000, C375S341000, C714S752000, C714S755000, C714S760000, C714S796000
Reexamination Certificate
active
06633615
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to decoding of a data stream in a communications system, and, more particularly, to a threshold normalization of state transition probabilities in a data detector employing a state transition trellis.
2. Description of the Related Art
Communication systems commonly employ encoding of data prior to transmission through, or recording on, a medium. Such systems commonly use convolutional or block codes to encode the data as a sequence of symbols. The transmitted or recorded signal with the encoded data is then demodulated and sampled by a receiver to produce a sequence of channel samples. The transmission or storage medium and the subsequent reception, demodulation, and sampling (including equalization of received samples by the receiver) defines a partial response channel through which the encoded data signal passes. The receiver generally includes maximum likelihood (ML) detector, e.g., either a Viterbi or a maximum aposteriori (MAP) detector, to detect and reconstruct the symbols prior to decoding of the detected, encoded data, or to decode detected and reconstructed symbols. For example, wireless communication systems operating in accordance with the CDMA 2000 standard include a MAP detector for decoding in the turbo-decoder of a receiver.
The ML detector provides a maximum a posteriori estimate of a state sequence of a finite-state, discrete-time Markov process observed in noise. Given a received sequence of channel samples of a signal corrupted with additive noise, the algorithm finds a sequence of symbol bits which is “closest” in a state trellis to the received sequence of channel samples. The trellis corresponds to possible states (portion of received symbol bits in the sequence) for each received channel symbol per unit increment in time (e.g., one clock cycle). For the algorithm used by the detector, the term “closest” is mathematically defined relative to a predefined metric incorporating the probabilities associated with certain state transitions as well as the cumulative probabilities associated with following each path through the trellis. For the trellis diagram, the number of bits (corresponding to output channel samples and detected symbol bits) for a state is usually equivalent to the memory of the partial response channel. Transitions are “weighted” according to the predefined metric, and Euclidean distance may be used as a metric for the trellis structure.
FIG. 1
shows an 8-state trellis employed for a partial response channel having a memory length of three. The left stage
101
of 3-bit states d(n−3), d(n−2), d(n−1) represents state symbol bits for the channel samples in the ML detector during a previous clock cycle, while the right stage
102
of 3-bit states d(n−2), d(n−1), d(n) represents state symbol bits for the channel samples during the current clock cycle. The right stage
102
includes the state symbol bit d(n) that corresponds to the currently received output channel sample at time n.
Each line, termed a branch, connecting the states in the left and right stages
101
and
102
represents a transition between states of the trellis (i.e., a state of the previous trellis phase to a state of a current trellis phase). The branch is a portion of a possible path through the trellis, and may be included in more than one path. For example, a branch connects the state #0 (“000”) in the left stage
101
(the originating state) to state #0 (“000”) in the right stage
102
. This branch represents a potential decision of the detector that not only identifies the current channel sample d(n) as being a “0” symbol, but also for the path representing the sequence of symbol bits received by the ML detector up to time n. A branch also connects the state #
4
(“100”) to state #0 (“000”) and represents a potential decision for channel sample d(n) being a “0” symbol except that now the originating state is “100”. Therefore, two branches from the previous state may pass through the present state “000”.
Similarly, two branches pass through each of the other states in the current trellis phase. Any destination state ending in a “0” represents d(n) being the “0” symbol for the path going through the state, while any destination state ending in a “1” represents d(n) equivalent to the “1” symbol for the path going through the state. In general, the different possible paths may be represented by a P-state trellis where P=2
Q
, where is Q an integer equivalent to the state length (i.e., memory length of the partial response channel).
The algorithm of the ML detector recursively performs three steps to detect a path through a trellis corresponding to the received sequence of symbol bits in the forward direction (i.e., states from left to right in FIG.
1
). First, branch metrics for the trellis are calculated for the current states; second, updates for each state metric are calculated for all states; and, third, survivor paths are determined. In addition, some algorithms perform similar steps to detect a path through a trellis corresponding to the received sequence of symbol bits in the reverse direction (i.e., states from right to left in FIG.
1
). The survivor path represents the sequence of symbol bits as transitions between states in the trellis which is closest, according to the Euclidean distance, to the received sequence of symbol bits in noise.
The branch metric for a state transition is defined as the Euclidean distance between the received channel sample (yr[n]) and the ideal channel output sample (y
i
[n]) corresponding to the transition. The path metric is simply the accumulated branch metrics of different branches encountered by the path through phases of the trellis as different possible paths are considered. The state metric of a given state is the path metric at some particular time if the path includes the given state at that particular time. To compute the entire, or global, sequence most likely received, the algorithm recursively calculates and updates state metrics of all states to provide a minimum path metric over several state transitions. The maximum likelihood sequence of the trellis is found by determining the sequence of symbol bits, or path, through the trellis that provides a minimum path metric in either the forward, reverse, or forward and reverse directions.
For a turbo decoder operating in accordance with a CDMA 2000 standard, the turbo decoder processor (TDP) calculates branch metrics from extrinsic in formation, systematic data, and parity, an then calculates the forward (&agr;) transition probabilities in the forward direction of the trellis and reverse (&bgr;) transition probabilities in the reverse direction of the trellis. Transition probabilities are quantities that are either substantially equal or directly related to branch and state metric values. In addition, as the path metrics are updated, the forward or reverse transition probabilites are accumulated. Since processors have storage with finite resolution (i.e., they have M bits available to store path metric values), a technique known as threshold normalization is employed to prevent data overflow. Prior art ML detectors employ a magnitude compare and subtract operation for threshold normalization. The accumulated transition probability (&agr; or &bgr;) of a state is compared with a threshold value. If the accumulated transition probability for each state in the stage of the trellis is greater than the threshold value, the threshold value is subtracted from the accumulated transition probability. Threshold normalization may be employed several times in a trellis, but tracking when each normalization operation takes place is not necessary. Such threshold normalization, however, requires a magnitude compare circuit and a subtraction circuit which increase the complexity and integrated circuit area of the TDP implementing an ML detector.
SUMMARY OF THE INVENTION
In accordance with exemplary embodiments of the present invention,
Pekarich Steven P.
Wang Xiao-An
Agere Systems Inc.
Hughes Ian M.
Mendelsohn Steve
LandOfFree
Trellis transition-probability calculation with threshold... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Trellis transition-probability calculation with threshold..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Trellis transition-probability calculation with threshold... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3171088