Path memory control method in Viterbi decoder

Details Path memory control method in Viterbi decoder Path memory control method in Viterbi decoder

1987-12-01

1990-02-27

Shoop, Jr., William M.

Coded data generation or conversion

Digital code to digital code converters

Adaptive coding

341 81, 371 43, H03M 1322

Patent

active

049053175

DESCRIPTION:

BRIEF SUMMARY
TECHNICAL FIELD

The present invention relates to a path memory control method in a Viterbi decoder in which the method of accessing a path memory used for trace back is novel.


BACKGROUND ART

In order to perform decoding operation in a Viterbi decoder, paths of finite lengths each to serve as a candidate for a most probable path as a transmission path are called survivor paths and stored in a path memory with respect to states on a code trellis of interest.
A bit which is common to previous surviving paths of a length about 4 to 5 times a code constraint length, in which the above survivor paths are assumed to effectively converge into one path, is output as decoded data.
In this case, the survivor paths are stored as follows:
In consideration of a unit cell structure of a trellis diagram as shown in FIG. 2A, state transition information between adjacent times (i.e., 1-bit information representing that which is more probable that state X.sub.k+1 at a time (k+1) is reached from state X.sub.k or from state X.sub.k ' at a time immediately before time (k+1)) is stored in a corresponding memory circuit.
Such 1-bit state transition information is called trellis connection data and is stored, with respect to each state, for each decoding step.
Therefore, in order to execute decoding on the basis of surviving paths thus stored, it becomes necessary to trace backward on the basis of preceding state transition information from the most probable state at time k (in which the probability of the surviving path stored with respect to this state is larger than that of any surviving path stored with respect to any other state), and decoded data is determined in accordance with state X.sub.k-v (where v is a surviving path length) which is finally reached. That is, so-called "trace back" must be performed.
In this case, basically, if trace back from time k to time k-v is not completed during one decoding step, decoded data cannot be output. In order to explain this more clearly, assume that a surviving path memory circuit is realized by a random-access memory as shown in FIG. 3, and that an ordinate direction corresponds to a trellis state and an abscissa direction corresponds to a time axis. Especially, assume that a decoding operation at time k is completed and a decoding operation of time (k+1) is started.
State transition information determined by an operation unit on the basis of a Viterbi algorithm are sequentially written in a memory in the vertical direction. In this case, in order to perform decoding, trace back must be executed in the horizontal direction before writing is completed and must reach, for example, the left end of the memory shown in FIG. 3.
In this case, trace back means repetition of a cycle such as accessing of an address .fwdarw. reading of state transition information .fwdarw. determination of an address to be accessed (at an immediately preceding time). Therefore, normally, writing of state transition information in the memory and track back operation are alternately performed.
However, as is apparent from FIG. 3, if the number of trellis states is different from the surviving path length (e.g., if the memory of FIG. 3 is a rectangle elongated in the horizontal direction), trace back does not reach the left end, even when writing of state transition information is completed with respect to all the states at time (k+1).
Moreover, assume that the numbers of trellis states and the surviving path length are the same with each other, and that the circuit configuration of a decoder is such that state transition information with respect to a plurality of states can be obtained at the same time. In this case, if these state transition information are written in a memory at a time, when the writing operation is completed with respect to all the states, trace back can be executed by only a portion of the path length. That is, the surviving paths can be traced back to only an intermediate stage. As a result, conventionally, it is difficult to conveniently control the memory, unless proper matching is ac

REFERENCES:
patent: 4545054 (1985-10-01), Davis
patent: 4583078 (1986-04-01), Shenoy et al.
patent: 4614933 (1986-09-01), Yamashita et al.
patent: 4677624 (1987-06-01), Betts et al.
patent: 4677625 (1987-06-01), Betts et al.
patent: 4677626 (1987-06-01), Betts et al.
patent: 4709377 (1987-11-01), Martinez et al.
COMSAT Technical Review, vol. 13, No. 2, pp. 315-329; A. Shenoy and P. Johnson; 1983.
IEEE Transactions on Communications, vol. Com. 29, No. 9, Sep. 1981, Charles M. Rader, "Memory Management in a Vitervi Decoder", pp. 1399-1401.

Affiliated with

Also associated with

Rating

Path memory control method in 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 Path memory control method in Viterbi decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Path memory control method in Viterbi decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-180016