Memory reduction techniques in a viterbi decoder

Details Memory reduction techniques in a viterbi decoder Memory reduction techniques in a viterbi decoder

2000-06-18

2003-07-08

DeCady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C375S341000, C714S794000, C714S796000, C714S792000

Reexamination Certificate

active

06591395

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a Viterbi decoder, and more particularly to the memory reduction techniques for a Viterbi decoder of Trellis-coded modulation.
BACKGROUND OF THE INVENTION
Trellis-coded modulation/demodulation has been widely used in many communication systems to improve system performance. It has been shown that the trellis-coded modulation scheme using two-dimensional (2-D) constellations can improve the error performance of synchronous data links without sacrificing data rate or requiring more bandwidth.
Trellis-coded modulation schemes using 4-D constellations have also been reported in recent years. In a paper titled “Trellis-Coded Modulation with Multidimensional Constellations” published in IEEE Transactions on Information Theory, Vol. IT-33, No. 4, July 1987, a number of modulation schemes have been presented and evaluated by Lee-Fan Wei. How to select multi-dimensional constellations, partition them into subsets and construct trellis codes using these subsets as well as how to map bits to constellation points have been discussed in the paper.
Wei's 16-state 4 dimensional (4-D) trellis code has been adopted by ADSL standards such as TIE1.4 and G.DMT as an option.
FIG. 1
shows a trellis diagram of 16-state codes with 4-D constellation. There are 16 states and four branches enter each state. As a result, a total of 64 transitions exist.
A Viterbi decoder may be used as a decoder of Wei's 16 state 4-D trellis-code. The basic operation of the Viterbi decoder is to select the most likely symbol from the 4-D cosets in Wei's construction based on a long sequence of received data. Whenever a newly received data is available, several candidates (surviving paths or survivors) are extended and compared with the received data sequence., and the data associated with the best survivor is chosen as the most likely one.
FIG. 2
illustrates the block diagram of a typical Viterbi decoder using a trace-back method. As shown in the block diagram, for each received 4-D signal a branch metric unit
101
computes the branch metrics associated with the 64 transitions. The branch metric associated with each transition is measured in terms of Euclidean distance between the received signal and a symbol in the 4-D cosets that is closet to the received signal. An add-and-compare selector (ACS)
102
determines the survival path for each of the 16 states. A memory unit
103
stores the 4-D symbols as well as the trace-back information for all branches in all the surviving paths that reach the 16 states. A trace-back unit
104
is used to implement the trace-back operation.
As can be seen from
FIG. 2
, significant memories are required in the decoding process to store the trace-back information as well as the 4-D symbols associated with all the state transitions in each survival path. Assuming a track-back length of 20, the size of the required memory that saves the survival 4-D symbols of each state is 16×20×8×4 bits. In the conventional implementation, redundant information is stored if the 4-D symbols associated with all state transitions that are selected from the cosets are stored in their original format.
The most commonly used implementation for the trace-back unit
104
is a ROM device which saves the trace-back information as shown in
FIG. 3
for a 16-state Wei's code. As can be seen from
FIG. 3
, a ROM of size 16×16×2 bits is required because 2 bits are needed to represent the trace-back information {
0
,
1
,
2
,
3
} that denotes four possible survivors leading to a specific state.
From the forgoing discussion, it is understandable that there is strong need in improving the conventional implementation of a Viterbi decoder of trellis-coded modulation so as to provide more efficient as well as lower cost decoders.
SUMMARY OF THE INVENTION
The present invention has been made to improve the above-mentioned drawbacks of a conventional Viterbi decoder of trellis-coded modulation. The primary object of the invention is to provide mechanisms for reducing memory requirement in the conventional Viterbi decoder. Accordingly, the invention proposes a simple combinational logic circuit to replace the implementation using ROM and an information storage mechanism that helps to reduce the required memory used for storing all the 4-D symbols associated with each state transitions in all survivors for trace-back procedure.
It is also an object of the invention to provide a combinational logic circuit for processing trace-back operation of a Vierbi decoder instead of using a ROM. According to the present invention, the combinational circuit comprises a four-input and one-output multiplexer, a shifter and an adder. The multiplexer provides a trace-back value according to the trace-back information of a state and the shifter shifts the state value towards right by two bits. The trace-back value and shifted value are added together to get the state value of the prior state.
Another object of the invention is to provide a mechanism for reducing the size of the memory storing 4-D symbols of the trace-back information. A 4-D coset is rewritten as a union of two Cartesian product of two 2-D cosets. All the symbols in the eight 4-D cosets closest to a received signal can be represented by symbols from two 2-D cosets along with differences between their coordinates.


REFERENCES:
patent: 4583078 (1986-04-01), Shenoy et al.
patent: 4709377 (1987-11-01), Martinez et al.
patent: 4713817 (1987-12-01), Wei
patent: 5418798 (1995-05-01), Wei
patent: 5465275 (1995-11-01), Blaker et al.
patent: 5490178 (1996-02-01), Blaker et al.
patent: 5550870 (1996-08-01), Blaker et al.
patent: 5937015 (1999-08-01), Dent et al.
patent: 5970097 (1999-10-01), Ishikawa et al.
patent: 6088404 (2000-07-01), Jekal
patent: 6345073 (2002-02-01), Curry et al.
patent: 6460161 (2002-10-01), Crozier et al.
T.K Truong, “VLSI Design for A Trace-back Viterbi Decoder”, Mar. 1992, IEEE Transactions on Communications, vol. 40, No. 3, pp. 616-624.*
Charles H. Roth, “Fundamentals of Logic Design”, West Publishing Company, 4th Edition, p. 223-226.*
M. Boo et al., “Mapping of The Viterbi Algoritm Onto Area-Efficient Vlsi Architecture”, 1997, NEC Research Index.*
Samir Palnitkar, “Verilog HDL”, 1996, Prentice Hall, pp. 3-9, 275-317.*
Trellis-Coded Modulation with Multidimensional Constellations, Jul., 1987, Lee-Fang Wei, Member, IEEE.
A VLSI Design for a Trace-Back Viterbi Decoder, Mar., 1992, T.K. Truong, Senior Member, IEEE.

Affiliated with

Also associated with

Rating

Memory reduction techniques in a viterbi 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 Memory reduction techniques in a viterbi decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory reduction techniques in a viterbi decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3102541