Browse Prior Art Database

Trellis Subset Decoder Algorithm Based on a Pattern Recognition Scheme

IP.com Disclosure Number: IPCOM000114028D
Original Publication Date: 1994-Oct-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 6 page(s) / 208K

Publishing Venue

IBM

Related People

Nobakht, RA: AUTHOR

Abstract

Disclosed is a design for a subset decoder for the Viterbi algorithm which is capable of subset decoding any shell mapped, four way partitioned trellis coded super constellation size for any data rate scheme. The maximum number of computations necessary for subset decoding remains constant for all data rates. In addition, no error is introduced as the result of this subset decoding. However, the amount of computation can be reduced based on the level of accuracy desired. The memory consumption of this algorithm is small and will not change with the data rate. This results in computational and performance improvements over the existing methods. This algorithm can be directly implemented for trellis decoding in the V.fast (TSS V.34) full duplex modem standard and subsequently in the similar half duplex standard for fax.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 32% of the total text.

Trellis Subset Decoder Algorithm Based on a Pattern Recognition Scheme

      Disclosed is a design for a subset decoder for the Viterbi
algorithm which is capable of subset decoding any shell mapped, four
way partitioned trellis coded super constellation size for any data
rate scheme.  The maximum number of computations necessary for subset
decoding remains constant for all data rates.  In addition, no error
is introduced as the result of this subset decoding.  However, the
amount of computation can be reduced based on the level of accuracy
desired.  The memory consumption of this algorithm is small and will
not change with the data rate.  This results in computational and
performance improvements over the existing methods.  This algorithm
can be directly implemented for trellis decoding in the V.fast (TSS
V.34) full duplex modem standard and subsequently in the similar half
duplex standard for fax.

      The Viterbi Algorithm (VA) is a recursive optimal solution to
the problem of estimating the state sequence of a discrete time
finite-state Markov process observed in memoryless noise.  Many
problems in areas such as digital communications can be cast in this
form.  The VA was proposed in 1967 as a method of decoding
convolutional codes.  Since that time, it has been recognized as an
attractive solution to a variety of digital estimation problems,
somewhat as the Kalman filter has been adapted to a variety of analog
estimation problems.  Like the Kalman filter, the VA tracks the state
of a stochastic process with a recursive method and that is optimum
in a certain sense, and that lends itself readily to implementation
and analysis.  However, the underlying process is assumed to be
finite-state Markov rather than Gaussian, which leads to marked
differences in structure.

      The VA for decoding can use the structure of the trellis and
the input data to determine the most likely path through the trellis.
The output for time (t_0) reflects a decision made by the decoder on
data received up to N time periods in the future.  This means that
the output for time (t_0) is necessarily delayed by N time periods or
that the latency of the decoder is N time periods.  N is determined
by the constraint length of the code and, for near optimum decoding,
is four or five times the constraint length.  The most likely path
through the trellis is one that is a minimum-distance path for the
input data or the path closest to the received data in in Euclidean
distance.  In other words, the Viterbi algorithm minimizes the
distance described by equation (1), where r_i and v_i are the
received and the decoded signal sequences, respectively.  At each
time period, every state in the trellis can have several paths
(defined by each trellis subset) going into it, but only one will be
the minimum distance for that state.  Thus, the state with the
smallest accumulated distance is the beginning point, at that time
period, to trace the minimum-...