Pulse or digital communications – Receivers – Particular pulse demodulator or detector
Reexamination Certificate
1999-03-08
2004-10-26
Ghebretinsae, Temesghen (Department: 2631)
Pulse or digital communications
Receivers
Particular pulse demodulator or detector
C375S262000, C375S265000
Reexamination Certificate
active
06810094
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to Viterbi decoding.
BACKGROUND TO THE INVENTION
Viterbi decoders find many applications. One such application is in baseband decoders for European digital audio broadcast (DAB) receivers. DAB services are transmitted using a frame structure in which individual services use one or more of six subframes of a frame. A problem arises because decoders suitable for consumer equipment cannot decode all six subframes thereby limiting the available equipment to the reception of one service at a time and preventing the use of a whole frame for one high bandwidth service.
DAB services are transmitted using a convolution code, having a 7-bit constraint length, to form four polynomial codes. The decoding process is computationally intensive, typically requiring 328 DSP (digital signal processor) instructions for a one bit decoder. This is because, in order to decode the 7-bit constraint length convolution code used for DAB, processing is required for 64 states. The processing of each state requires the following stages: adding two new branch metrics to an existing path metric; identify best of the two new branch metrics; selecting the best new branch metric as the surviving path; and tracing back the surviving path.
A full-rate DAB decoder, i.e. one for decoding all of the subframes in real time, must operate at a speed of 1.9 Mbits/s, requiring operation at 623 MIPs by the DSP.
The use of Viterbi decoding of convolution coded data is described in general in Halsall, F., “Data Communications, Computer Network and Open Systems”, ISBN 0-201-42293-X.
Viterbi decoding comprises processing of path metrics and processing of path history data. This data is typically stored in RAM.
SUMMARY OF THE INVENTION
It is an object of the present invention to provided an improved Viterbi decoder.
It is a further object of the present invention to provide a Viterbi decoder having an increased data throughput.
It is yet a further object of the present invention to provide a Viterbi decoder which makes efficient use of silicon possible.
According to the present invention, there is provided a Viterbi decoder including memory means for storing Viterbi decoder data, comprising path metrics and/or path history data, clocked processing means for producing new Viterbi decoder data from Viterbi decoder data read from the memory means and a signal being decoded, and addressing means for addressing the memory means, wherein the memory means comprises two-port RAM means and the addressing means is configured such that Viterbi decoder data is always read from the memory means in the same state order and the addressing of the memory means for writing Viterbi data follows the same sequence as the read addressing but lags by the maximum number of control clock cycles taken between reading Viterbi data and storing of the resultant new Viterbi data. The use of the same addresses for reading and then, a predetermined period later, writing data means that the address sequence used cycles through a series of permutations, changing with each frame, so that the data is always read in a constant state order.
The particular addressing arrangement of the present invention means that two-port RAMs can be employed, resulting in a significant reduction in the amount of memory required. When the present invention is embodied in an integrated circuit, there is also a significant reduction in the area of silicon required.
Preferably, the memory means comprised first and second two-port RAM means and the addressing means is arranged for reading two path metrics or history data for two paths concurrently from respectively the first and second RAM means. More preferably, an address signal applied to the first RAM means is concurrently applied to the second RAM means. The first and second two-port RAM means may be embodied in a single RAM structure. Since the same address signals are applied concurrently to both RAM means, one RAM means can be embodied in the cells for the most significant bits and the other RAM means can be embodied in the cells for the least significant bits. For example, if each RAM means must store an 11-bit word, a single RAM that stores 22-bit words can be used. In this case, the first RAM means may comprise the cells for the 11 most significant bits and the second RAM means may comprise the cells for the 11 least significant bits.
In a preferred embodiment, the memory means comprises four two-port RAM means, two of which store path metric data and two of which store path history data. The four two-port RAM means may be embodied in a single two-port RAM structure.
According to the present invention, there is also provided a method of Viterbi decoding comprising the steps of: (a) obtaining two path metrics, the path metrics being associated with states that can be followed by the same set of states; (b) modifying said path metrics with branch metrics to produce a first pair of new path metrics for a first member of said set and a second pair of path metrics for a second member of said set, the members of each pair being derived respectively from said two path metrics; and (c) selecting the lower cost path metric of each pair.
Preferably, step (a) is performed while step (b) is being performed in respect of two path metrics obtained by an earlier performance of step (a). In other words, the processing of path metrics is pipelined.
Preferably, step (b) comprises adding a branch metric to each of said two path metrics and subtracting the same branch metric from each of said two path metrics. This may be applied cases where there is a degree of symmetry inherent in the convolution code being decoded.
Preferably, the selected path metrics are stored in a memory means from which at least one of said two path metrics was read. More preferably, selected path metrics are written to respective RAM means in dependence on the most significant bits of the binary representations of the states to which the selected path metrics relate.
Preferably, the reading of path metrics is arranged such that a first performance of step (a) and a second immediately following performance of step (a) leads to a pair of selected path metrics to be stored in one of said RAM means and a pair of selected path metrics to be stored in the other of said RAM means, and each member of one of the pairs of selected path metrics is stored concurrently with a member of the other pair of selected path metrics.
According to the present invention, there is also provided Viterbi decoder comprising first processing means for concurrently modifying two path metrics using at least one branch metric to produce a pair of new path metrics for each of two branched to states, and second processing means for concurrently processing pairs of new path metrics, produced by the first processing means, to select from each pair a path metric for a surviving path.
Preferably, there is provided memory means for storing path metrics and addressing means for reading two path metrics from the memory means, the path metrics being associated with states that can be followed by the same set of states, wherein the first processing means is arranged to process path metrics read from the memory means by means of the addressing means.
Preferably, the first processing means comprises an first adder for adding a branch metric to a first path metric read from the memory means, a second adder for adding a branch metric to a second path metric read from the memory means, a first subtracter for subtracting a branch metric from said first path metric and a second subtracter for subtracting a branch metric from said second path metric.
More preferably, the same branch metric is applied to the first and second adders and the first and second subtracters.
Preferably, the second processing means is arranged to output said selected path metrics to the memory means.
Preferably, the memory means comprises first and second RAM means and the second processing means is arranged such that said selected path metrics are output to one or other of the RAM means
Ghebretinsae Temesghen
Hitachi , Ltd.
Kenyon & Kenyon
Kumar Pankaj
LandOfFree
Viterbi decoder with pipelined parallel architecture does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Viterbi decoder with pipelined parallel architecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Viterbi decoder with pipelined parallel architecture will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3301388