Viterbi decoder with reduced number of bits in branch metric calculation processing

• US 6,810,095 B2
• Filed: 12/13/2000
• Issued: 10/26/2004
• Est. Priority Date: 12/20/1999
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Naitou, Takahiro
• Primary Examiner(s): Chin, Stephen
• Assistant Examiner(s): Perilla, Jason M.
• Application Number:
  US09/734,892
• Publication Number:
  US 20010004391A1
• Time in Patent Office: 1,413 Days
• Field of Search: 375/341, 375/262, 375/265, 375/267, 375/340, 375/347, 375/349, 375/316, 371/43.4, 371/43.7, 371/43.8, 714/795
• US Class Current: 375/341
• CPC Class Codes: H03M 13/3961 Arrangements of methods for branch or transition metric calculation
• CPC Class Codes: H03M 13/4107 implementing add, compare, select [ACS] operations
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing

Abstract

A Viterbi decoder with a reduced number of bits in branch metric calculation processing is disclosed. In a branch metric calculator, word split circuits divide metric data 1 to 3 from respective latch circuits into the signs of the least 1 bit and metrics of k−1 bits, respectively. EX-OR gates determine whether or not the divided signs (1 bit) match codewords (1 bit) for each state produced from a convolutional code generated by a convolutional code generator and a counter. Each time-division switch for 1 bit selects the output of the match or mismatch with switched timing. Adders add outputs when the signs match to the divided metrics output from selectors when the signs do not match based on the selection to calculate a branch metric.

Claims

1. A method of calculating a branch metric in Viterbi decoding for deriving a branch metric by comparing a codeword produced from a convolutional code with a sign of determination data obtained from conversion of received data for branch metric calculation, said method comprising the steps of:

dividing said determination data into a sign and a metric and outputting them;

determining whether said divided sign matches said codeword or not and outputting a determination signal and an inverted determination signal as a result thereof;

outputting, on a time-division basis, either the determination signal or the inverted determination signal based on timing pulses;

selecting and outputting, based on an output of the outputting step, “

0”

when said divided sign matches said codeword or selecting and outputting said metric when said divided sign does not match said codeword; and

adding outputs selected when the signs match to outputs selected when the signs do not match to calculate a branch metric.

12. The Viterbi decoder according to claim 1, wherein said determination data is divided into the sign and the metric prior to the outputting of the determination signal or the inverted determination signal on a time-division basis.

2. A Viterbi decoder for deriving a branch metric by comparing a codeword produced from a convolutional code with a sign of determination data obtained from conversion of received data for branch metric calculation, comprising:

metric data conversion means for outputting a plurality of metric data which are soft decision symbols converted from a received data sequence;

code generation means for generating and outputting said codeword;

branch metric calculation means for dividing the plurality of metric data from said metric data conversion means into signs and metrics, respectively, outputting them, determining whether the divided signs match the codewords from said code generation means and outputting a determination signal and an inverted determination signal based on the determination, outputting one of the determination signal and the inverted determination signal on a time-division basis, selecting and outputting, under control of the outputted one of the determination signal and the inverted determination signal, “

0”

when the divided signs match the codewords or selecting and outputting said metrics when the divided signs do not match the codewords, and adding outputs selected when the signs match to outputs selected when the signs do not match to calculate a branch metric;

add/compare/select operation means for adding the branch metric calculated by said branch metric calculation means to a survivor path metric, and making a comparison of two joining metrics paths to obtain a new path metric and a survivor path;

path metric memory means for storing the new path metric and the survivor path metric from said add/compare/select means and for supplying said add/compare/select operation means with a survivor path metric;

path information memory means for storing survivor paths with a plurality of states from said add/compare/select operation means; and

trace back processing means for decoding a state with the smallest path metric at final truncation of bits from said path metric memory means and the survivor paths with the plurality of states from said path information memory means.

3. A Viterbi decoder for deriving a branch metric by comparing a codeword produced from a convolutional code with a sign of determination data obtained from conversion of received data for branch metric calculation, comprising:

metric data conversion means for outputting a plurality of metric data which are soft decision symbols converted from a received data sequence;

code generation means for generating and outputting said codeword;

branch metric calculation means for dividing the plurality of metric data from said metric data conversion means into signs and metrics, respectively, outputting them, determining whether the divided signs match the codewords from said code generation means, selecting and outputting “

0”

when they match or selecting and outputting said metrics when they do not match based on the determination result of the match or mismatch, and adding outputs selected when the signs match to outputs selected when the signs do not match to calculate a branch metric;

add/compare/select operation means for adding the branch metric calculated by said branch metric calculation means to a survivor path metric, and making a comparison of two joining metrics paths to obtain a new path metric and a survivor path;

path metric memory means for storing the new path metric and the survivor path metric from said add/compare/select means and for supplying said add/compare/select operation means with a survivor path metric;

path information memory means for storing survivor paths with a plurality of states from said add/compare/select operation means; and

trace back processing means for decoding a state with the smallest path metric at final truncation of bits from said path metric memory means and the survivor paths with the plurality of states from said path information memory means, wherein said branch metric calculation means includes;

a plurality of division means for dividing each of the plurality of input metric data into signs and metrics and outputting them;

a plurality of determination means for determining whether or not the respective signs divided by each of said plurality of division means match the codewords input thereto;

a plurality of time-division selection means for selecting either outputs obtained by not inverting the results of the match or outputs obtained by inverting the results of the mismatch determined by each of said plurality of determination means; and

addition means for adding outputs from said pluralities of time-division selection means when the signs match to the metrics divided and output by said plurality of division means selected when the signs do not match to obtain a branch metric.

4. The Viterbi decoder according to claim 3, wherein each of said plurality of division means is a word split circuit for dividing each of the plurality of input metric data into a sign and a metric and outputting them.

5. The Viterbi decoder according to claim 3, wherein each of said plurality of determination means is an exclusive OR gate for determining whether or not each of the signs divided by said plurality of division means matches each of the codewords input to each of said exclusive OR gates.

6. The Viterbi decoder according to claim 3, wherein said addition means includes two adders for adding outputs when the signs match to outputs when the signs do not match based on the selection at said plurality of time-division selection means to obtain a branch metric.

7. The Viterbi decoder according to claim 3, wherein the inversion of the output result of the mismatch determined by each of said plurality of determination means is performed using an inverter.

8. The Viterbi decoder according to claim 4, further comprising a plurality of latch circuits on the sides of respective inputs to said plurality of word split circuits for holding the input metric data until latch pulses are input.

9. The Viterbi decoder according to claim 4, wherein each of said word split circuits divides each of the plurality of input metric data into the most significant bit for sign determination and a metric of k1 bits.

10. The Viterbi decoder according to claim 5, wherein each of the signs and the codewords input to each of said plurality of exclusive OR gates comprises one bit.

11. The Viterbi decoder according to claim 3, wherein each of said plurality of time-division selection means is a multiplexer.