Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Unified Table Based Subset Decoder for the Viterbi Algorithm

IP.com Disclosure Number: IPCOM000113720D
Original Publication Date: 1994-Sep-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 8 page(s) / 284K

Publishing Venue

IBM

Related People

Nobakht, RA: AUTHOR

Abstract

A table based subset decoder for the Viterbi algorighm is disclosed which is capable of decoding any constellation size for any data rate scheme with constant number of computations. In addition, no error is introduced as the result of this subset decoding.

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

Unified Table Based Subset Decoder for the Viterbi Algorithm

      A table based subset decoder for the Viterbi algorighm is
disclosed which is capable of decoding any constellation size for any
data rate scheme with constant number of computations.  In addition,
no error is introduced as the result of this subset decoding.

      The number of cycles necessary to perform such a task an
example Signal Processor is about 100 cycles for any given
constellation size (different data rates) of the CCITT V32bis and IBM
proprietary V32ter full duplex modems.  This results in improvements
of up to a factor of 16 times over existing methods.  The memory
consumption of this algorithm is small and increases proportionally
with the data rate.

      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 Viterbi algorithm 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 (t0) 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 (t0) 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 Euclidean distance.  In other words, the Viterbi
algorithm minimizes the distance described by equation (1), where ri
and vi 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-distance subset path
through the past N-1 time periods of the trellis.  The
minimum-distance
subset paths to the next state are then calculated b...