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

• US 20010004391A1
• Filed: 12/13/2000
• Published: 06/21/2001
• Est. Priority Date: 12/20/1999
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Naitou, Takahiro
• Granted Patent: US 6,810,095 B2
• Time in Patent Office: Days
• 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;

selecting and outputting “

0”

when they match or selecting and outputting said metric 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.

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, 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.

3. The Viterbi decoder according to

claim 2

, 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 k−

1 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.