Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-02-01
2003-07-29
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06601215
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates, in general, to a method and apparatus for decoding convolutionally-encoded signals. More specifically, the invention relates to a traceback method and apparatus for Viterbi decoding.
2. Description of the Relevant Art
Digital signal processing algorithms are characterized by repetitive accesses to data, especially at the input end of a processing chain. Decoding of convolutionally-encoded signals is a typical example of such repeating address patterns. The need for speed and compactness imposed by real-time signal processing applications often requires the use of special structures that exploit this regularity to accelerate the generation of addresses. In software, this may involve placing coefficients in memory in order of use, so that simple address increment operations can access them. Alternatively, simple hardware logic can be developed to implement address generation.
One way of achieving regular, repetitive addressing is through the use of a circular buffer. The circular buffer is used for cases in which limited amounts of data are accessed in sequence over and over. For example, filter coefficients are accessed in sequence to multiply a consecutive set of samples, and then the samples are shifted by one and the same set of filter coefficients are again accessed. The address cycle may proceed in increments of one and reset to zero after reaching a maximum value of N−1, thereby implementing a modulo N counter. Alternatively, the address cycle may increment by a number m>1, implementing a striding memory that accesses every mth location until exceeding N−1, then resetting either back to zero or to the remainder of the quotient N/m. If N is an integer power of two, N=2
i
, a simple hardware solution can pick the least significant i bits of a counter to provide modulo N cycling. In software, simple bit masking by means of a logical AND can be used for modulo address generation.
In the Viterbi algorithm, an important set of operations is the sequence of choosing a minimum from N numbers, identifying the argmin, or index of the minimum number, adding the minimum to an accumulating distance score, and passing back the argmin and updated distance score. Typically N numbers that correspond to distance values are received and the minimum values s′ and the index of that minimum value, t′, are calculated. Alternatively, the distance measure, which is small for similar patterns, could be replaced by a similarity measure, which increases as two patterns become identical, and the min function would be replaced by a max function. The minimum distance s′ is added to a global distance that is the accumulation of many such operations in the past from the scoring of other recognition subunits and the global distance is thus updated. The argmin is sent to a linked list structure.
Viterbi decoders are used heavily in communications applications for Forward Error Correction (FEC). They undo the encoding of convolutional encoders and correct bit errors. An essential part of the Viterbi decoder is a traceback memory (TM). It stores information about decisions made by an Add-Compare-Select Unit (ACSU). For each state of the Viterbi trellis, the TM contains a circular buffer. The ACSU writes the decision information into the TM, and a Traceback Unit reads that information from the TM and decodes the bit stream.
Heretofore, the TM required separate circular buffers for each state of the Viterbi trellis. For each buffer, a start and an end address needed to be stored. Accesses to these buffers require an address generation unit that checks for overflow and maintains the circular structure. This address generation is costly both in terms of silicon area as well as cycle count.
SUMMARY OF THE INVENTION
Accordingly, the present invention is directed to a Viterbi decoding method and apparatus that substantially obviates one or more of the problems due to limitations and disadvantages of the related art. Additional features and advantages of the invention will be set forth in the description which follows, and in part will be apparent from the description, or may be learned by practice of the invention. The objectives and other advantages of the invention will be realized and attained by the method and apparatus particularly pointed out in the written description and claims hereof, as well as the appended drawings.
To achieve these and other advantages, and in accordance with the purpose of the invention as embodied and broadly described, there is provided apparatus for Viterbi decoding of an encoded signal represented as a time-sequence of coded symbols. The apparatus includes a processor receiving the encoded signal and generating therefrom a time-sequence of trellis-state decision records; a buffer receiving and storing in an array the time-sequence of trellis-state decision records, the buffer time-sequence shifting in the array a plurality of the time-sequence of trellis-state decision records; and a traceback unit operatively connected to the buffer tracing back a path in the array representing a most-likely survivor path and generating therefrom a decoded signal.
In another aspect of the apparatus, the buffer comprises a plurality of indexed-buffer registers each storing a predetermined one of the plurality of trellis-state decision records, each such indexed-buffer register responsive to a first (GSP) and a second (WRITEP) write pointer signal; the first write pointer signal pointing to one of the plurality of indexed-buffer registers as the shifted starting point of the time-sequence array and the second write pointer signal pointing to the index within each of the buffer registers for storage of the trellis-state decision records.
In yet another aspect of the apparatus, the first write pointer is incremented by a fixed predetermined value. Also in another aspect of the apparatus, the second write pointer is incremented by a fixed predetermined value after each trellis-state decision is generated by the processor.
In another aspect of the apparatus, the buffer is further responsive to a read pointer signal (READP) generated by the traceback unit pointing to the trellis-state decision being read; the READP being formed from a state number of the trellis-state and a read base signal (RBASE).
Also in another aspect of the invention, the read base signal is decremented by a fixed predetermined value.
In another aspect of the apparatus, the memory length of indexed-buffer registers, M, is a power of 2 and wherein said second write pointer predetermined fixed incrementing value is register size N. Also in another aspect of the apparatus, the total memory length, M, is not a power of 2, and wherein said second write pointer is set to the remainder after subtracting M, if a subtraction therefrom by M produces a positive or zero result. Also in another aspect of the apparatus, the subtraction is performed by modulo (2
N+1
) addition of the value −N.
In yet another aspect of the apparatus, the buffer is a random access memory (RAM).
Also, in accordance with the invention, there is provided a method of Viterbi decoding of an encoded signal represented as a time-sequence of coded symbols, having, the steps of generating from the encoded signals a time-sequence of trellis-state decision records, storing the records in an array, generating a decoded symbol from traceback paths in the array, and shifting pointers for the records in the array.
In another aspect of the method, the array comprises a plurality of indexed-buffer registers each storing a predetermined one of the trellis-state decision records, each such indexed-buffer register responsive to a first write pointer (GSP) signal and a second write pointer (WRITEP) signal; the first write pointer signal pointing to one of the plurality of indexed-buffer registers as the shifted starting point of the time-sequence array and the second write pointer signal pointing to the index within each of the buffer registers for storage of
Agere Systems Inc.
Baker Stephen M.
Mendelsohn Steve
LandOfFree
Traceback buffer management for VLSI Viterbi decoders does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Traceback buffer management for VLSI Viterbi decoders, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Traceback buffer management for VLSI Viterbi decoders will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3105189