Pulse or digital communications – Receivers – Particular pulse demodulator or detector
Reexamination Certificate
2000-09-22
2004-09-07
Chin, Stephen (Department: 2634)
Pulse or digital communications
Receivers
Particular pulse demodulator or detector
C375S262000, C714S795000
Reexamination Certificate
active
06788750
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to digital data communications, and specifically to trellis-based methods for decoding digital signals.
BACKGROUND OF THE INVENTION
Trellis-based coding and decoding are well known in the art of signal processing. For example, in trellis-coded modulation (TCM), convolutional encoding and constellation mapping is applied to a sequence of input bits, to create encoded symbols to be transmitted over a noisy channel. The encoding introduces “memory” into the encoded symbols, so that each one depends on the preceding symbols. Practically speaking, trellis-based decoding can be applied to substantially any system that can be represented by a trellis diagram. A trellis-based decoder at the receiving end decodes the received symbols by hypothesizing different possible sequences of input symbols and finding the one that gives a maximum likelihood of being the correct one. Trellis-based decoding can be used in conjunction with a wide range of different coding schemes, as well as for resolving intersymbol interference in communication channels and in other signal processing applications.
In trellis-based decoding, at each point in time, the trellis has a number of vertices corresponding to the number of possible states of the encoding state machine at the corresponding time instant. Transitions between the vertices from one point in time to the next, are henceforth referred to as branches of the trellis, and are associated with the respective symbols that could have caused the transitions. A metric is computed for each branch, indicating the likelihood that the signal actually received at the given point in time resulted from the transmission of the symbol associated with the branch. Typically, the metric of a given branch provides a measure of distance between the received signal and the transmitted branch symbol. In particular, in a Gaussian channel, the logarithm of the likelihood that the received signal corresponds to the transmitted branch symbol reduces to the Euclidean distance between signals. An important property of the distance metric is that the smaller the distance, the greater the likelihood of belonging to the trellis path of the transmitted symbols in the sequence. A path through the trellis is composed of a series of interconnected branches. Each such path thus corresponds to a possible sequence of transmitted symbols and has a path metric equal to the sum of the metrics of its branches. The path with the best metric corresponds to the sequence of symbols with maximum likelihood.
The Viterbi algorithm is a mathematically-optimal maximum likelihood solution to the trellis-based decoding problem. It is described, for example, by Forney in “The Viterbi Algorithm,” published in
Proceedings of the IEEE
61(3), pages 268-278 (1973), which is incorporated herein by reference. To streamline the decoding procedure, the Viterbi algorithm retains for each vertex only the one path with the best metric, terminating at the vertex. Other branches, and their corresponding paths, are discarded. The remaining paths at any point in time are referred to as “survivors.” Thus, at each section of the trellis, it is necessary to maintain only as many surviving paths as there are possible states. Nevertheless, when a system has a large number of possible states (as occurs for example in high-performance TCM schemes), the computational burden of tracking all of the survivors is still substantial.
At each step of the decoding procedure, another symbol in the sequence is decoded, by tracing back the most likely path over a certain number of symbols, known as the “decision delay.” Increasing the decision delay generally increases the likelihood of correctly decoding the sequence, but at the same time incurs a greater delay in outputting the decoded symbols.
Conventional implementations of the Viterbi algorithm use two data structures: one to hold the state metrics, and the other for path history (traceback). The data structure of the state metrics holds two sets of old and new state metrics. Each set contains a plurality of state metrics according to the number of states of the encoding system, organized so that the place of the state metric in the structure corresponds to the index of the related state. The traceback data structure is arranged as a table whose dimensions are the number of states of the encoding system and the chosen decision delay. As in the state metrics data structure, the traceback data are stored so that their location in the table corresponds to the index of the related state. Each entry in the table contains a pointer indicating which preceding state was on the surviving path that led to this state.
Each step of a Viterbi decoder corresponds to an input sample to the decoder. In each step, the decoder calculates branch metrics, based on the input sample. Then, based on the old state metrics stored in the data structure and on the calculated branch metrics, a set of new state metrics is calculated. The new state metrics are calculated for each and every state in the trellis. Each new state metric is calculated by an Add/Compare/Select operation, which retains for each state only one path. The Add/Compare/Select operation for a given new state is composed of calculating the metrics for all the paths that terminate in this state, by adding the corresponding old state metrics to the connecting branch metrics, comparing the different path metrics that terminate in this state and selecting only the one path with the best metric.
As noted above, the trellis is processed by tracing back from the current symbol to the decision delay, in order to decode the symbol or bits that were received at a delay corresponding to the decision delay. The traceback starts from the state that has the highest likelihood among all states at the current symbol. The trellis path terminating at this state is declared as the winner path, and the traceback table is used to track the winner path, ending at the state to be decided upon. This path is tracked by reading the entry of the most likely state at the current symbol from the traceback table, and finding the state at the previous symbol that is connected to it on the winner path. This operation steps back one branch on the winner path. From the state found at the previous symbol, the operation is repeated, reading from the traceback table iteratively, until it reaches the earliest symbol in the table. The path thus tracked through the traceback table is the most likely path up to the current symbol. The decoder then returns the symbol or bits corresponding to the earliest transition in the most likely path that was tracked.
Alternative sub-optimal decoding approaches have been proposed, such as the M- and T-algorithms, in order to reduce the number of paths retained. Methods of this type are described, for example, by Simmons, in “Breadth-First Trellis Decoding with Adaptive Effort,” published in
IEEE Transactions on Communications
38(1), pages 3-12 (1990), by Anderson et al., in “Sequential Coding Algorithms: A Survey and Cost Analysis,” published in
IEEE Transactions on Communications
32(2), pages 169-176 (1984), and by Chennakeshu et al., in U.S. Pat. No. 5,905,742. These publications are incorporated herein by reference. In these methods, the number of survivors at each section of the trellis is restricted to a certain number of paths whose metrics are smaller than a given limit. In the T-algorithm, all paths whose metrics are above a given threshold (T) are discarded. In the M-algorithm, a certain number of states (M) are retained. Simmons and Chennakeshu both describe methods for adaptively varying M or T. As a result, the computational effort required at each decoding stage will tend to vary, leading also to a variable delay between symbols output by the decoder. This effect is very meaningful in T-algorithm, where the number of surviving paths can change significantly from one symbol to another, even for a fixed threshold. Simmons considers but rejects the idea of purging all
Ayalon Gilad
Frenkel Liron
Reuven Ilan
Shahar-Doron Ayelet
Chin Stephen
Darby & Darby
Tioga Technologies Inc.
Wang Ted
LandOfFree
Trellis-based decoder with state and path purging 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-based decoder with state and path purging, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Trellis-based decoder with state and path purging will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3272157