JPH11186918A - Viterbi decoder - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a Viterbi decoder the circuit scale of which is made comparatively small, even if a binding length is extended by solving a problem of an exponential increase in the circuit scale due to prolonged binding length caused in a conventional structure and integrated serial processing of pluralities of parallel processing in each state at an add, compare and select(ACS) circuit and a maximum likelihood path discrimination section. SOLUTION: In a Viterbi decoder, branch metrics from a branch metric calculation section 1' and path metrics from a path metric memory section are divided into plural groups and converted into a serial series. An ACS section 2' applies addition, comparison, selection in time division for each group and a maximum likelihood path discrimination section also divides path metrics in plural states into plural groups and converts them into serial series, and then comparison and selection is applied to each group in time division.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a Viterbi decoder for maximum likelihood decoding of a convolutional code, which is one of error correction codes used in information transmission, and more particularly to a survivor path selection and a maximum likelihood path determination process. And a Viterbi decoder capable of reducing the circuit scale by serially performing time-division multiplexing.

[0002]

2. Description of the Related Art In the following description, for the sake of convenience, a coding rate 1 / R where a constraint length k, the number of input bits (information blocks) of a convolutional encoder is 1, and the number of output bits (code blocks) is R. A Viterbi decoder that decodes the convolutional code of will be described. However, a similar configuration is possible for extension to a convolutional code (for example, a coding rate of 3/4) using puncturing.

First, an example of a convolutional code having a constraint length k to be decoded by a Viterbi decoder will be described with reference to FIG. FIG. 6 is a state transition diagram (trellis diagram) expressing an example of a convolutional code having a constraint length k. In addition, FIG.
It shows the state transition in the time slot, and in the figure,
Each state at time t-1 represents a state before data is input to the convolutional encoder, and a state at time t represents a state after data is input to the convolutional encoder.

[0004] The state in the trellis diagram (circle in the figure)
When the coding rate is 1 / R, the number of branches and the number of lines (lines connecting the circles in the figure) is determined by the constraint length k, and is as follows. Number of states = ^2k-1 Number of branches = ^2k

[0005] Here, the two branches branched from an arbitrary state indicate to which state the code to be coded next has a value "0" and a state to which the code changes to "1". Is shown.

In the trellis diagram shown in FIG. 6,
Any state n (n = 0 to 2 ^k−1 −) at time t−1
The two branches branching from 1) merge into the two states at time t under the following conditions. If n <2 ^k−1 / 2 → State 2n and State 2n +
In the case of ln ≧ 2 ^k−1 / 2 → state 2n−2 ^k−1 and state 2n−2 ^k−1 +1

Therefore, the two states at time t include time t
Two of the two branches each derived from the two states at -1 will be joined together. As an example, state 0 and state 1 at time t in FIG.
In the following description, a total of four branches (Ba0, Ba1, and B2) from the state 0 and the state 2 ^k-1 / 2 at the time t-1 are described.
b0, Bb1) form a butterfly structure in which two lines are merged.

Here, state m at time t (m is 0 to 2 ^{k -1)}
The branch metric of the two branches merging into (even number including −1 and 0) and the branch metric of the two branches merging into the state m + 1 have the following relationship.

The branch metric of the branch joining state m from above and the branch metric of the branch joining state m + 1 from below are the same. The branch metric of the branch joining state m from below and the state metric above m + 1. That is, the branch metrics of the branches Ba0 and Bb1 and the branch metrics of the branch Ba1 and the branch Bb0 are the same.

Next, a general configuration of a conventional Viterbi decoder for decoding a convolutional code having a constraint length k represented by the trellis diagram described in FIG. 6 will be described with reference to FIG. FIG. 7 is a block diagram showing a general configuration example of a conventional Viterbi decoder.

The conventional Viterbi decoder comprises a branch metric calculation unit 1, an ACS unit 2, a path metric memory unit 3, a normalization operation unit 4, a maximum likelihood path determination unit 5, and a path memory unit 6. It is configured.

Each part of the conventional Viterbi decoder will be described. The branch metric calculation unit 1 stores in advance the data of the codeword of the trellis diagram used at the time of encoding in the corresponding convolutional encoder, and inputs and stores the demodulated data in codeblock units. From the codeword of the trellis diagram and the input demodulated data, a branch metric at time t corresponding to each branch constituting the trellis is calculated, and path information of each branch (path of value “0” or value of “1”) In the same timing).

Here, the branch metric uses a Hamming distance at the time of hard decision, and a metric such as shown in Table 1 is used at the time of soft decision.

[0014]

[Table 1]

Here, [Table 1] shows a symbol metric when demodulated data is subjected to 3-bit soft-decision quantization as an example, and the branch metric is the sum of the symbol metrics.

The types of branch metrics obtained by the branch metric calculation unit 1 vary depending on the coding rate. For example, when the coding rate is 1/3, 8 types (= 2
^Three), the branch metric of the four in the case of 1/2 (= 2 ^two) is generated.

As a specific example, the branch metric when the coding rate is 1/2 is as follows. (1) (symbol metric for "0") + (symbol metric for "0") (2) (symbol metric for "0") + (symbol metric for "1") (3) (symbol metric for "1" ) + (Symbol metric for “0”) (4) (symbol metric for “1”) + (symbol metric for “1”) As a result, the value of the branch metric changes depending on the input decoded data. There are four types of branch metrics at t.

The ACS unit 2 calculates a path metric (cumulative branch metric) of each state at the current time t, and performs an Add Compare and Select (ACS) operation for selecting a surviving path in each state. It is.

Specifically, the ACS unit 2 first converts the path metrics of the 2 ^{k -1} surviving paths at time t-1 output from the path metric memory unit 3 described later from the branch metric calculation unit 1 Output time t
Add the same branch metric and merge into the same state 2
By comparing the path metrics of the book paths and selecting a path with a high likelihood, the selected path is added 2
The updated surviving paths in the ^k-1 states are obtained, and path information (whether a path having a value “0” or a path having a value “1”) of the surviving path is output to the path memory unit 6, and the surviving path is further obtained. The path metric of the path is sent to the maximum likelihood path determination unit 5 and the normalization operation unit 4.

Here, the internal configuration of the conventional ACS unit 2 will be described with reference to FIG. FIG. 8 shows a conventional ACS unit 2
3 is a block diagram showing an example of the internal configuration of FIG. The conventional ACS unit 2 includes a plurality of ACS circuits 20, as shown in FIG. Here, when the coding rate is 1 / R, the number of ACS circuits used is determined by the constraint length k, and the number is equal to the number of trellis states and is 2 ^{k -1} .

In each ACS circuit 20, according to the trellis diagram shown in FIG. 6, two branches at time t-1 having two branches merging into an arbitrary state at time t.
The path metric of the two states and the branch metric of the two branches are input, and the branch metric is added to each path metric to obtain a path metric based on two types of path routes that merge in the state at the time t. By comparing the two paths, a path path having a high likelihood, that is, a path metric having a small value is selected, the selected path path is set as an updated surviving path in the state, path information of the surviving path and the surviving path And output the path metric.

Explaining in a concrete example, the ACS circuit (0) 20-1 of FIG. 8 has two branches (Ba0 and Bb0 in FIG. 6) that join the state (0) at time t. State (state (0) and state (2)
^k-1 / 2)) and the branch metrics of the above two branches (branch metrics 0 and 1 in FIG. 8) are input, and the path metric of state (0) +
The branch metric 1 of Ba0 and the path metric of state (2 ^k−1 / 2) + the branch metric 0 of Bb0 are calculated, a path path having a small calculation result is selected, and the surviving path in the state (0) at time t is selected. Is output as the path information of the surviving path.

Similarly, the ACS circuit (1) 20-2 shown in FIG. 8 has two branches (Ba1 and Bb1 in FIG. 6) that join the state (1) at time t. The path metric of the state (state (0) and state (2 ^k−1 / 2)) and the branch metric of the two branches are input.

As described with reference to FIG. 6, since the characteristics of the branch metric in the trellis diagram are the same, the branch metrics of the branch Ba0 and the branch Bb1 and the branch Ba1 and the branch Bb0 are the same.
Then, branch metric of branch Ba1 = branch B
As the branch metric of b0 = branch metric 0 and the branch metric of branch Bb1 = branch metric of branch Ba0 = branch metric 1, the same branch metric as the ACS circuit 20-1 is input.

Then, in the ACS circuit (1) 20-2, the path metric of the state (0) + the branch metric of Ba1 and the path metric of the state (2 ^k−1 / 2) + Bb1 are calculated. A path route having a small value is selected, and is output as the path information of the surviving path in the state (1) at time t and the path metric of the surviving path.

Next, the ACS circuit 2 constituting the ACS unit 2
0 will be described in detail with reference to FIG. FIG.
FIG. 1 is a block diagram showing an example of a configuration of an ACS circuit 20 constituting a conventional ACS unit 2.

The ACS circuit 20 is composed of two adders 21, an adder 22, and one comparison selector 23.

The adder 21 calculates the path metric of one state (state A in FIG. 9) at time t-1 at which the branch joins an arbitrary state (state C in FIG. 9) at time t, and A branch metric from state A (in FIG. 9, branch metric A) is input, and the two input values are added and output.

Similarly, the adder 22 calculates the path metric of the other state (state B in FIG. 9) at time t-1 at which the branch joins an arbitrary state (state C in FIG. 9) at time t, A branch metric from state B at time t (branch metric B in FIG. 9) is input, and the two input values are added and output.

The comparison selector 23 receives the addition result from the adder 21 and the addition result from the adder 22, compares the two, and selects the smaller value as the path with higher likelihood. Then, a signal (FIG. 9) indicating which one of the path metric (the path metric of the state C in FIG. 9) and the two branches (the branch of the value “0” or the branch of the value “1”) is selected. Then, the surviving path information) is output to the outside. If the addition results are the same, either one may be selected, and either one is selected and output.

The maximum likelihood path determination section 5 selects the maximum likelihood path from surviving paths for the number of states.
The path metrics of the 2 ^k-1 types of surviving paths output from the S unit 2 are input, and the maximum likelihood path having the highest likelihood, that is, the value of the path metric is selected from among them, and the selected maximum likelihood is selected. The path number (the maximum likelihood path number) is stored in the path memory unit 2
06, and at the same time, the path metric of the maximum likelihood path is output to the normalization calculation unit 204.

Here, a specific configuration example of the conventional maximum likelihood path determination unit 5 will be described with reference to FIG. FIG.
FIG. 11 is a block diagram illustrating a specific configuration example of a conventional maximum likelihood path determination unit 5. As one configuration example of a conventional maximum likelihood path determination unit 5, as shown in FIG.
A path with high likelihood is selected by the tournament method from the path metrics of 2 ^{k -1} types of surviving paths output from 0, and a comparison selector is arranged so as to finally obtain the maximum likelihood path. There is a way.

[0033] For example, if the constraint length is k, the number of states of the trellis becomes a 2 ^k-1 one, because the path metrics outputted from the ACS unit 2 becomes 2 ^k-1 species, 2 ^k in the first stage ^-2 comparison selectors 51 are arranged, 2 ^k-3 comparison selectors 52 are arranged in the second stage, and one comparison selector 53 is finally arranged in the (k-1) stage. Therefore, (2 ^k−1 −1) comparison selectors are required. For example, when the constraint length is 7, 63 comparison selectors are required, and when the constraint length is 9, 255 comparison selectors are required.

Then, in the first stage comparison selector 51,
Two A's in each ACS circuit 20 constituting the ACS unit 2
The path metric of the surviving path output from the CS circuit 20 is input, and the path metric of the higher likelihood, that is, the smaller path metric is selected, and the path metric of the selected path and the 2 ^{k -1} surviving path are selected. Information (path number) indicating the order of the path is output to the next stage. Note that the number of bits of the pass number is also determined by the constraint length k.

Similarly, the second-stage comparison selector 52 inputs the path metric and the path number of the surviving path selected by the first-stage comparison selector 51, and obtains a high likelihood, that is, the path metric of the path metric. The smaller one is selected, and the path metric and path number of the selected path are output to the next stage.

Finally, the path with the highest likelihood is selected as the maximum likelihood path from the 2 ^k-1 types of surviving paths by the (k-1) th stage comparison / selector 53, and the number of the maximum likelihood path is selected. Is output to the path memory unit 6, and at the same time, the path metric of the maximum likelihood path is output to the normalization operation unit 4.
In the case where the path metrics are the same in the comparison selectors 51, 52 and 53, either one may be selected, and either one is selected and output.

The normalization operation unit 4 normalizes the path metric of the surviving path. Specifically, the normalization operation unit 4 receives the path metric of the surviving path output from the ACS unit 2 and inputs the values of all the path metrics. By subtracting the path metric of the maximum likelihood path output from the maximum likelihood path determination unit 5 from, the value of the path metric is lowered so that the path metric of the maximum likelihood path always becomes 0, and normalization is performed. The result is output to the path metric memory unit 3.

This is because the path metric of the surviving path is added and accumulated by the ACS unit 2 each time, so that the path metric is prevented from overflowing the range of the memory prepared in advance. It is.

The path metric memory unit 3 stores the normalized path metric, and stores the stored path metric in synchronization with the timing at which the branch metric from the branch metric calculation unit 1 is input to the ACS unit 2. The metric is output to the ACS unit 2.

The path memory section 6 stores path information according to the path information of the surviving path output from the ACS section 2 and outputs the path information of the path selected as the maximum likelihood path as decoded data. . It should be noted that the information on the path route to be stored is only the length called the truncation length for each surviving path.

More specifically, the path memory unit 6 has memories corresponding to 2 ^{k -1} states, and stores path information (“0” or “1”) of the surviving path output from the ACS unit 2. The information is sequentially stored, and this is information representing a path route that joins each state until time t. Then, the oldest path information from the memory corresponding to the state at time t at which the path selected as the maximum likelihood path by the maximum likelihood path determination unit 5 is output to the outside as decoded data of the Viterbi decoder.

Next, the operation of the conventional Viterbi decoder will be described with reference to FIG. In the conventional Viterbi decoder, demodulated data is input to the branch metric calculation unit 1 in code block units, and 2 ^R types (1 / R: coding rate) of branch metrics at time t corresponding to each branch forming the trellis Is calculated and output to the ACS unit 2 at the same timing.

Then, the ACS unit 2 calculates the path metrics of the surviving paths in 2 ^k−1 states at time t−1 output from the path metric memory unit 3 and the time output from the branch metric calculation unit 1. and 2 ^k-number of branch metric t are added, and the path metric of the two paths merging in the same state are compared, higher likelihood path is selected, which is the 2 ^k-1 pieces of state update A surviving path is obtained, path information of the surviving path is output to the path memory unit 6, and at the same time, a path metric of the surviving path is output to the normalization operation unit 4 and the maximum likelihood path determining unit 5.

The path information of the surviving path is stored in the path memory unit 6.

The path metric of the surviving path is
The path with the highest likelihood is sequentially selected by the tournament method in the maximum likelihood path determination unit 5, the maximum likelihood path with the highest likelihood is finally selected, and the number of the maximum likelihood path obtained as a result is stored in the path memory unit 6. And the path metric of the maximum likelihood path is output to the normalization operation unit 4 at the same time.

In the path memory unit 6 to which the information of the maximum likelihood path is input, the data of the oldest path information of the path selected as the maximum likelihood path is output to the outside as decoded data of the Viterbi decoder.

The path metric of the surviving path output from the ACS unit 2 and input to the normalization operation unit 4 is the same as that of the maximum likelihood path obtained from the maximum likelihood path determination unit 5 in the normalization operation unit 4. The subtraction and normalization are performed, and the result is stored in the path metric memory unit 3 and output to the ACS unit 2 at the same timing as the next branch metric is input to the ACS unit 2, and the path metric at the next time is output. Is used for the calculation.

[0048]

However, in general, the number of states of a trellis is 2 ^k-1 when the constraint length is k, and the number of states increases exponentially as the constraint length increases. Since the number of the ACS circuits 20 constituting the ACS unit 2 and the number of the comparison selectors 51 to 53 in the maximum likelihood path determination unit 5 depend on the number of trellis states, the constraint length increases. As a result, the circuit scale increases exponentially, and there is a problem that mounting on an IC becomes difficult.

The present invention has been made in view of the above circumstances, and solves the problem of exponentially increasing the circuit scale when the constraint length generated in the conventional structure is increased.
A plurality of parallel processes for each state in the S circuit and the maximum likelihood path determination unit are collectively converted into a serial sequence and processed in a time-division manner, so that the circuit scale can be relatively small even if the constraint length becomes long. It is an object of the present invention to provide a Viterbi decoder capable of performing the following.

[0050]

According to a first aspect of the present invention, there is provided a Viterbi decoder for storing a codeword of a trellis diagram of convolutional coding in advance and decoding demodulated data. Is input in coding block units, a branch metric is calculated by calculating a distance between the input demodulated data and a codeword of the trellis diagram, and a branch metric associated with path information branched from each state is output. A branch metric calculation unit, a path metric memory unit that stores a path metric of a surviving path in each state at the time of the previous decoding, and outputs the path metric in synchronization with an output from the branch metric calculation unit; The branch metric output from the branch metric calculation unit is added to the path metric output from the metric memory unit. To obtain an updated path metric, compare the path metrics of two paths merging in an arbitrary state, select a path with a high likelihood as a surviving path, and select the path metric and path of the selected surviving path. An ACS unit for outputting information;
Among the path metrics of the surviving paths in each state output from the unit, the path with the highest likelihood is selected as the maximum likelihood path, and the maximum likelihood path determination unit that outputs the path number and the path metric of the maximum likelihood path. Subtracting the path metric of the maximum likelihood path output from the maximum likelihood path determination unit from the path metric of the surviving path in each state output from the ACS unit, performs normalization, and outputs the result to the path metric memory unit. A normalization operation unit and sequentially stores path information of surviving paths in each state output from the ACS unit, and replaces the oldest path information of the path number with the path number of the maximum likelihood path from the maximum likelihood path determination unit. A Viterbi decoder having a path memory unit that outputs decoded data, wherein the ACS unit outputs each state output from the path metric memory unit. The path metric and the branch metric of each branch output from the branch metric calculation unit are each divided into a plurality of specific groups, and the path metric and the branch metric are converted into a serial series for each of the groups, and the time division is performed. The path metric and the branch metric are added to two paths that merge in an arbitrary state to obtain updated path metrics, and the updated two path metrics are compared, and a path with a high likelihood is determined as a surviving path. An ACS unit that selects and converts the path metric and path information of the selected surviving path into a parallel sequence for each group and outputs the same at the same timing. The number of circuits in the portion to be selected can be reduced.

According to a second aspect of the present invention, a codeword of a trellis diagram of convolutional coding is previously stored in a Viterbi decoder, and demodulated data is stored in units of a coding block. A branch metric calculation unit that calculates a distance between the input demodulated data and the codeword of the trellis diagram to obtain a branch metric, and outputs a branch metric associated with path information branched from each state. A path metric memory unit that stores a path metric of a surviving path in each state at the time of previous decoding, and outputs the path metric in synchronization with an output from the branch metric calculation unit; and a path metric memory unit that outputs the path metric. Updated by adding the branch metric output from the branch metric calculation unit to the path metric The path metric of the two paths merging in an arbitrary state is compared, the path having a high likelihood is selected as a surviving path, and the path metric and path information of the selected surviving path are output. Among the path metrics of the surviving paths in each state output from the ACS unit and the ACS unit, the path with the highest likelihood is selected as the maximum likelihood path, and the path number and the path metric of the maximum likelihood path are output. A maximum likelihood path determination unit, subtracts the path metric of the maximum likelihood path output from the maximum likelihood path determination unit from the path metric of the surviving path in each state output from the ACS unit, and performs normalization. A normalization operation unit that outputs to the metric memory unit, and path information of a surviving path in each state that is output from the ACS unit is sequentially stored. A path memory unit for outputting the oldest path information of the path number as decoded data in accordance with the path number of the maximum likelihood path from the maximum likelihood path determination unit, wherein the branch metric calculation unit A branch metric calculation unit that divides a branch metric associated with path information branched from a plurality of groups into a plurality of specific groups, converts the branch metric into a serial sequence for each group, and outputs the serial series at time-divided timing; A metric memory unit, which divides a path metric into the plurality of specific groups, converts the path metric into a serial sequence for each group, and time-divides the path metric to output at a timing synchronized with the branch metric calculation unit; The ACS unit is the path metric memory unit The path metric of each state input at a time-divided timing from the branch metric and the branch metric of each branch input at a time-divided timing from the branch metric calculation unit are input. The path metric and the branch metric are added to the path to obtain updated path metrics, the two updated path metrics are compared, and a path having a high likelihood is selected as a surviving path, and the selected surviving path is selected. Characterized in that the ACS unit converts the path metric and the path information into a parallel sequence for each group and outputs the same at the same timing. The number of circuits in the ACS unit that perform addition / comparison / selection is reduced. Can be reduced.

According to a third aspect of the present invention, a codeword of a trellis diagram of convolutional coding is stored in advance in a Viterbi decoder, and demodulated data is stored in units of coding blocks. A branch metric calculation unit that calculates a distance between the input demodulated data and the codeword of the trellis diagram to obtain a branch metric, and outputs a branch metric associated with path information branched from each state. A path metric memory unit that stores a path metric of a surviving path in each state at the time of previous decoding, and outputs the path metric in synchronization with an output from the branch metric calculation unit; and a path metric memory unit that outputs the path metric. Updated by adding the branch metric output from the branch metric calculation unit to the path metric The path metric of the two paths merging in an arbitrary state is compared, the path having a high likelihood is selected as a surviving path, and the path metric and path information of the selected surviving path are output. Among the path metrics of the surviving paths in each state output from the ACS unit and the ACS unit, the path with the highest likelihood is selected as the maximum likelihood path, and the path number and the path metric of the maximum likelihood path are output. A maximum likelihood path determination unit, subtracts the path metric of the maximum likelihood path output from the maximum likelihood path determination unit from the path metric of the surviving path in each state output from the ACS unit, and performs normalization. A normalization operation unit that outputs to the metric memory unit, and path information of a surviving path in each state that is output from the ACS unit is sequentially stored. A Viterbi decoder having a path memory unit that outputs the oldest path information of the path number as decoded data according to the path number of the maximum likelihood path from the maximum likelihood path determination unit, wherein the maximum likelihood path determination unit is The path metric of the surviving path output from the ACS unit is divided into a plurality of specific groups, the path metric is converted into a serial sequence for each of the groups, and compared at time-division timing to perform an alternative comparison selection. It is a maximum likelihood path determination unit that selects a path with the highest likelihood as the maximum likelihood path, and outputs a path number and a path metric of the maximum likelihood path. It is possible to reduce the number of circuits in a portion for performing comparison and selection in the path determination unit.

According to a fourth aspect of the present invention, there is provided a Viterbi decoder according to the first or second aspect, wherein the maximum likelihood path determination unit is configured to perform the maximum likelihood path determination according to the third aspect. It is characterized in that it is a path determination unit, so that the number of circuits in the ACS unit that perform addition, comparison, and selection can be reduced, and the number of circuits in the maximum likelihood path determination unit that performs comparison and selection can be further reduced. .

According to a fifth aspect of the present invention, there is provided a Viterbi decoder according to the fourth aspect, wherein the ACS units join in an arbitrary state at a time-divided timing for each group. The path metric and the branch metric are added for the two paths to obtain updated path metrics, the two updated path metrics are compared, and a path with a high likelihood is selected as a surviving path. The ACS unit outputs the path metric of the surviving path for each group while maintaining the time-divided timing, and converts the path information of the selected surviving path into a parallel sequence for each group and outputs the same at the same timing. The maximum likelihood path determination unit determines the path metrics of the surviving paths output for each group from the ACS unit. Are input at time-divided timings, compare and select in a tournament manner with an alternative comparison selection, select the path with the highest likelihood as the maximum likelihood path, and select the path number of the maximum likelihood path and ACS is characterized by being a maximum likelihood path determination unit that outputs a path metric.
The circuit for converting the path metric selected in the unit into a parallel sequence and the circuit for converting the path metric in the maximum likelihood path determination unit into a serial sequence can be reduced.

According to a sixth aspect of the present invention, there is provided a Viterbi decoder according to the third aspect, wherein the maximum likelihood path determining unit is configured to determine a path metric of a surviving path in each input state. The number of P / S converters for converting a path metric of an arbitrary group from a parallel sequence to a serial sequence obtained by dividing a plurality of groups into a plurality of groups, and a counter for counting the number of paths in the P / S converter And the path metrics of the serial sequence from the two P / S converters are input and compared, and a path metric having a high likelihood is selected, and an output from the counter is output for the path of the selected path metric. A first comparison / selector for outputting the path metric and the path number, and a path metric from the first comparison / selector Two path numbers are input and compared, and a path metric having a high likelihood is selected as an alternative, and the selected path metric and the path number are output. A second comparison and selector for outputting a path metric and a path number, a memory for storing a path metric and a path number having a high likelihood, a path metric and a path number from the second comparison and selector, and the memory Enter the path metric and the path number stored in
A third comparison selector that compares the two path metrics and selects a path metric having a high likelihood and outputs the selected path metric and the path number; and an output from the third comparison selector. It is characterized by a maximum likelihood path determination unit having a switch for switching between the memory and the outside, so that it is easy to manage path numbers in accordance with the reduction in the number of circuits in the comparison / selection part in the maximum likelihood path determination unit. It can be realized with a simple configuration.

According to a seventh aspect of the present invention, there is provided a Viterbi decoder according to the fifth aspect, wherein the maximum likelihood path determination unit corresponds to a path metric input from the ACS unit. A counter for counting the number of paths and two path metrics input for each group from the ACS unit are input and compared, and a path metric having a high likelihood is selected. A first comparison / selection unit that allocates a path number according to the output from the counter and outputs the path metric and the path number, and inputs and compares two path metrics and the path number from the first comparison / selection unit Then, a path metric having a high likelihood is selected as an alternative, the selected path metric and a path number are output, and finally the path metric having the highest likelihood is output. A memory for storing a path metric and a path number having a high likelihood; a path metric and a path number from the second comparison and selector; Inputting the stored path metric and the path number, comparing the two path metrics and selecting a path metric having a high likelihood,
A maximum likelihood path determination unit having a third comparison / selector that outputs the selected path metric and the path number, and a switch that switches the output from the third comparison / selector between the memory and the outside. It is characterized by the fact that the management of the path number accompanying the reduction of the number of circuits in the comparison / selection part in the maximum likelihood path determination unit can be realized with a simple configuration.

[0057]

Embodiments of the present invention will be described with reference to the drawings. The Viterbi decoder according to the embodiment of the present invention divides a branch metric from a branch metric calculation unit and a path metric from a path metric memory unit into a plurality of groups and converts them into a serial sequence. Since addition comparison selection is performed in a time-division manner, the maximum likelihood path determination unit also divides the path metrics in a plurality of states into a plurality of groups, converts them into a serial sequence, and performs comparison selection processing in a time-division manner for each group. The circuit scale of the section and the maximum likelihood path determination section can be reduced, and the circuit scale of the entire Viterbi decoder can be kept relatively small even if the constraint length becomes long.

The Viterbi decoder of the present invention basically has the configuration shown in FIG.
, A branch metric calculation unit 1, an ACS unit 2, a path metric memory unit 3, a normalization operation unit 4, a maximum likelihood path determination unit 5, and a path memory unit 6 as in the conventional Viterbi decoder shown in FIG. However, the contents of the branch metric calculation unit 1, the ACS unit 2, the path metric memory unit 3, and the maximum likelihood path determination unit 5 are different.

Each part of the Viterbi decoder according to the present invention will be described focusing on the parts different from the conventional one. To make the description easy to understand, the present invention uses a convolutional code with constraint length k = 7 and coding rate 1 / R. Description will be made by taking as an example a case where the present invention is applied to a Viterbi decoder for decoding, and decoding processing in the Viterbi decoder is performed by 16 multiplexing time division. Also, the decoding processing time required to obtain one piece of decoded data in the Viterbi decoder is represented by T
It will be described as.

First, the branch metric calculator 1 'of the Viterbi decoder according to the present invention will be described. The branch metric calculation unit 1 'according to the present invention stores codeword data of a trellis diagram used in encoding in advance, inputs demodulated data in units of code blocks, and stores the data. 2 to calculate the ^R type of branch metrics from the demodulation data input codeword of the trellis diagram are.

Then, the branch metrics of a total of 128 branches derived from the 2 ^{k -1} states at time t-1 by two branches are divided into groups of 16 branches each.
The 16 branch metrics are converted into a serial sequence and output for each group.

At this time, as described in the prior art with reference to FIG. 6, the state 2n and the state 2n + 1 (n = 0 to 31)
The branch metric of a total of four branches that join
Since there are only the types, the number of outputs of the branch metric calculation unit 1 'which should be present in parallel can be 128 / (16 × 2) = 4.

The output timing of the branch metric in the branch metric calculation unit 1 'is synchronized with the output timing of the path metric memory unit 3'.
ACS unit 2 'at the same cycle (T / 16 interval in this example)
Is output to.

Next, the ACS unit 2 'of the present invention will be described with reference to FIG.
I will explain using. FIG. 1 is a configuration block diagram of a branch metric calculation unit 1 'and an ACS unit 2' of a Viterbi decoder according to the present invention.

The ACS unit 2 ′ of the present invention comprises:
It comprises four ACS circuits 20-1 to 20-4 and four S / P converters 25-1 to 25-4.

The ACS circuits 20-1 to 20-4 calculate the path metric (cumulative branch metric) of each state in the same manner as in the related art, and select the surviving path in each state (Add Compare and Select: ACS) operation.

However, in the ACS circuit 20 of the present invention, the path metric at time t-1 output from the path metric memory block of the path metric memory unit 3 'described later and the time output from the branch metric calculation unit 1' t is the time metric T / 16
The information is input serially every time, and the information of the surviving path selected and added and compared and the path metric are output at each time interval T / 16.

The S / P converters 25-1 to 25-4 convert the path metric and the surviving path information of the surviving path serially input from the ACS circuits 20-1 to 20-4 for each T / 16 into a parallel sequence. And outputs it at the same timing every time T.

Next, the path metric memory unit 3 'of the present invention will be described with reference to FIG. FIG. 2 is a block diagram showing a configuration example of the path metric memory unit 3 'of the present invention. The path metric memory unit 3 'of the present invention
Four path metric memory blocks 30 per group
-1 to 30-4.

The configurations in the four path metric memory blocks 30 are all common, and the 16 memories 3
1 (memory 0 to 15 in FIG. 2) and one P / S converter 32.

In each path metric memory block 30, 16 path metrics at time t-1 in the trellis state are stored in order. In this example, block 0 has states 0 to 15, block 1 has states 32 to 47,
State 16 to 31 for block 2, state 4 for block 3
The path metrics at time t-1 from 8 to 63 are stored.

Then, the 16 memory contents in each path metric memory block 30 are read at the same timing, and are serially output to the ACS unit 2 by the P / S converter 32 at intervals of T / 16. Further, the contents of the sixteen memories in the path metric memory block 30 are updated at time T periods.

Next, the maximum likelihood path determination section 5 'of the present invention will be described with reference to FIG. FIG. 3 is a block diagram showing a configuration example of the maximum likelihood path determination unit 5 'of the present invention. The maximum likelihood path determination unit 5 'of the present invention, as shown in FIG.
S converters 54-1 to 54-4, hexadecimal counter 55, 4
It comprises three comparison selectors 56-1, 56-2, 57, 58, a switch 59, and a memory 60.

The P / S converter 54 outputs the T / T
The path metrics of the 64 surviving paths in states 0 to 63, which are output every time, are divided into four groups, each of which is input, converted into a serial sequence, and output for each T / 16.

The hexadecimal counter 55 outputs the last four digits (0000 to 1111) of each pass number represented by a binary number for each T / 16 in perfect synchronization with the output of the ACS unit 2. Things. Specifically, for example, the P / S converter 54-1
When the path metric 0 is output from the
When the hexadecimal counter 55 outputs “0000” and the path metric 1 is output, the hexadecimal counter 55 outputs “0001”. When the path metric 2 is output, the hexadecimal counter 55 outputs “0000”. 0
At the timing when the path metric 15 is output, the hexadecimal counter 55 outputs “111”.
1 "is output.

The first-stage comparison selectors 56-1 and 56-2 are:
The path metric serial sequence of the surviving path output from the P / S converters 54-1 and 54-2 is input, and the likelihood is high each time the input is made (for each T / 16). The smaller metric is selected, and the path metric of the selected path and the path number are output to the next stage.

Here, in order to manage the path number, the comparison selector 56 inputs the last four digits of the path number from the hexadecimal counter 55 and the path number of the path number uniquely held by the comparison selector 56. It has the function of performing an OR operation with the first two digits.

More specifically, in the comparison / selector 56-1, the path metric input from the P / S converter 54-1 is
"00000" assuming that the first two digits of the pass number are "00"
Using 0 ', a pass number is determined by performing an OR operation with the last four digits (0000 to 1111) output from the hexadecimal counter 55.

Similarly, the comparison selector 56-1 determines that the first two digits of the path number are "01" for the path metric input from the P / S converter 54-2 to "01000".
0 'and the P / S converter 54-3 in the comparison selector 56-2.
For the path metric input from, "100000" is used assuming that the first two digits of the path number are "10", and input from the P / S converter 54-4 by the comparison selector 56-2. For the path metric, the first two digits of the path number are "11", and the path number is determined using "110000".

The comparison selector 57 outputs the selected path metric output from the comparison selector 56-1 and its path number, the selected path metric output from the comparison selector 56-2 and its path number, And selects the path metric with the higher likelihood, that is, the path metric with the smaller path metric, and outputs it to the comparison selector 58 together with the path number. The output from the comparison selector 57 is selected and output with the highest likelihood from the path metrics output from the four P / S converters 54 for each T / 16. .

The comparison selector 58 compares the selected path metric output from the comparison selector 57 with the path metric stored in the memory 60, and determines the higher likelihood, that is, the smaller path metric. And outputs the path metric and the path number. In the case where the path metrics are the same in the comparison selectors 56, 57, 58, either one may be selected, and either one is selected and output.

The memory 60 stores the path metric and the path number output from the comparison / selector 58, and the contents are cleared every T. In practice, by setting a value having a sufficiently lower likelihood than the value of the path metric of the maximum likelihood path, a value in the memory 60 is not selected at the time of comparison selection immediately after clearing.

The switch 59 switches between outputting the output from the comparison selector 58 to the memory 60 and outputting to the outside. The switch 59 is initially connected to the B side, and the time T / 16
The path metric output from the comparison selector 58 and its path number are output and stored in the memory 60 for each time (1
5 * T / 16) is switched to the A side at the time
The path metric and the path number of the maximum likelihood path output from the comparison selector 58 are output to the outside.

The control of the timing in each part constituting the Viterbi decoder of the present invention described above,
The switching control of No. 9 is performed by a timing control unit (not shown) that totally controls the timing of each unit in the apparatus.

Next, the operation of the Viterbi decoder of the present invention will be described with reference to FIGS. Note that, similarly to the configuration, a Viterbi decoder that decodes a convolutional code with a constraint length k = 7 and a coding rate of 1 / R performs decoding processing in a 16-multiplex time-division manner to obtain one piece of decoded data. The processing time is described as T.

In the Viterbi decoder of the present invention, demodulated data is input to the branch metric calculation unit 1 'in code block units, and 2 ^R types (1 / R: encoding at time t corresponding to each branch constituting the trellis) Rate), the branch metric of the 128 branches is divided into eight by sixteen, and the sixteen are converted into a serial sequence.
The branch metric of the sequence is output to the ACS unit 2 'at the timing of T / 16.

On the other hand, from the path metric memory unit 3 ', the path metrics of the surviving paths in the 2 ^{k -1} (64) states at the time t-1 are converted into 16 serial sequences, and the branch metric is calculated. The data is output to the ACS unit 2 'at the timing of T / 16 in synchronization with the unit 1'.

In the ACS section 2 ', four ACS circuits 20
At time t-
1 and the branch metric at time t from the branch metric calculation unit 1 'are added for each T / 16, and a path with high likelihood in the same state is selected, and the S / P converter 25 Is used to convert the 16 surviving paths from serial to parallel.
At each time T, information on the surviving path is output to the path memory unit 6, and at the same time, the path metric of the surviving path is output to the normalization operation unit 4 and the maximum likelihood path determination unit 5 '.

The operation of the ACS unit 2 'will be described with a specific example with reference to FIG. FIG. 4 shows a branch metric calculation unit 1 ', a path metric memory unit 3', A
FIG. 9 is a timing chart illustrating a data output state in a CS unit 2 ′.

However, here, the ACS circuits 20-1 and 20-2
The description is limited to the following. In FIG. 4, the path metric output from the path metric memory block (0) 30-1 of the path metric memory unit 3 'is (a) the path metric memory block 0, and the path metric memory block (1) 30-2. Are described as (c) path metric memory block 1.

Then, Pn (n = 0 to 15, 32) in FIG.
To 47) indicate the path metric in state n at time t-1. Of the four signals output from the branch metric calculation unit 1 ', those input to the ACS circuit (0) 20-1 and the ACS circuit (1) 20-2 are represented by (b) branch metric 0, (d) Let Bn (n
= 0 to 31) is a branch metric of each branch at time t.

First, the ACS circuit (0) 20-1 has a ΔT
The path metric memory block 0 and the branch metric 0 are input every (= T / 16), and the result of adding these is compared with the result of adding the path metric memory block 1 and the branch metric 1 similarly.

That is, Pn + Bn and P (n + 32) + B
The results of (n + 16) (n = 0 to 15) are compared, and the one with the higher likelihood is selected. This becomes the path metric Sn (n = 0 to 15) at the time t, and the S /
The signal is output to the P converter 25-1 and converted into a parallel series by the S / P converter 25-1, and Sn in (e) (n = 0 to 15)
Are output at the same timing for each T, and are output to the maximum likelihood path determination unit 5 ′ and the normalization operation unit 4.

Similarly, in the ACS circuit (1) 20-2,
(A) Path metric memory block 0 and (d) branch metric 1 are input, and the result of adding them is:
The (b) path metric memory block 1 and (c) the result obtained by adding the branch metric 0 are compared. In the figure, Pn + B (n + 16) and P (n + 32) + Bn (n = 0
To 15), and as a result, a path metric S (n + 16) (n = 0 to 15) at time t is obtained.
The data is output to the S / P converter 25-2 every 16 and is converted into a parallel series by the S / P converter 25-2 to obtain (f) S (n + 1
6) (n = 0 to 15) are output at the same timing every T and output to the maximum likelihood path determination unit 5 'and the normalization operation unit 4.

As a result, the path metric and path information of the surviving path in each state are output in a parallel sequence from the ACS unit 2 'as in the conventional case.

The path information of the surviving path output from the ACS unit 2 'is stored in the path memory unit 6 as in the conventional case.

The path metric of the surviving path is
The P / S converter 54 of the maximum likelihood path determination unit 5 'converts the serial sequence into four serial sequences of 16 each, and 2 for each T / 16.
In the tour, the paths having the highest likelihood among the four paths are sequentially selected in a tournament manner using three comparison selectors 56 and 57, and the highest likelihood among the 16 paths is selected using the comparison selector 58 and the memory 60. The maximum likelihood path is finally selected, and the number of the maximum likelihood path obtained as a result is output to the path memory unit 6. At the same time, the path metric of the maximum likelihood path is output to the normalization operation unit 4.

In the path memory unit 6 to which the information of the maximum likelihood path has been input, the oldest data of the path selected as the maximum likelihood path is output to the outside as decoded data of the Viterbi decoder as in the related art.

The path metric of the surviving path output from the ACS unit 2 'and input to the normalization operation unit 4 is:
In the normalization operation unit 4, the path metric of the maximum likelihood path obtained from the maximum likelihood path determination unit 5 'is subtracted and normalized, and is stored in each memory 31 of the path metric memory unit 3'. ing.

In the above description of the Viterbi decoder of the present invention, the branch metric calculation unit 1 'and the path metric memory unit 3' have a P / S conversion function, and the ACS unit 2 '
, The branch metric and the path metric are input in a serial sequence. However, the branch metric calculation unit 1 ′ and the path metric memory unit 3 ′ are output in a parallel sequence with the same configuration as the conventional one. After performing P / S conversion inside the ACS unit 2 ',
It may be input to the S circuit 20.

In the above description, both the ACS unit 2 'and the maximum likelihood path determination unit 5' are described as being processed in a serial sequence. However, only the ACS unit 2 'or only the maximum likelihood path determination unit 5' is processed. May be processed in a serial sequence.

In the above-described configuration of the ACS unit 2 'in FIG. 1 and the maximum likelihood path determination unit 5' in FIG. 3, the ACS unit 2 '
Since the path metric is once subjected to S / P conversion and output as a parallel series once, and inside the maximum likelihood path determination unit 5 ', P / S conversion is performed again and the comparison and selection processing is performed with a serial series.
S / P conversion and maximum likelihood path determination unit 5 'inside ACS unit 2'
It is also possible to omit the internal P / S conversion.

Here, a configuration in which the S / P conversion and the P / S conversion of the path metric are omitted will be described as a second embodiment with reference to FIG. FIG. 5 is a configuration block diagram of the ACS unit and the maximum likelihood path determination unit according to the second embodiment in which the S / P conversion and the P / S conversion of the path metric are omitted.

The ACS unit 2 ″ according to the second embodiment of the present invention
Is that the path metric in the output of the ACS circuits 20-1 to 20-4 is output as a serial sequence without passing through the S / P converters 25-1 to 25-4, and the maximum likelihood path determination unit 5 Are directly input to the comparison selectors 56-1 and 56-2.

The path information in the outputs of the ACS circuits 20-1 to 20-4 is converted into a parallel sequence through S / P converters 25-1 to 25-4 and then output to the path memory unit 6. However, in FIG. 5, the S / P converters 25-1 to 25-4 are omitted.

The operation after input to the comparison selector 56 of the maximum likelihood path determination unit 5 ″ is the same as that described with reference to FIG.
In the case of the configuration of FIG. 5, the P / S conversion unit of the maximum likelihood path determination unit becomes unnecessary, so that the circuit scale can be further reduced.

The path metric output from the ACS unit 2 ″ is output as a serial sequence without passing through the S / P converters 25-1 to 25-4. It is necessary to perform normalization by inputting in a serial sequence, convert it to a parallel sequence, and output it to the path metric memory unit 3 '.

In the above, the case where the constraint length = 7 has been described as an example. When the constraint length (k) = 7, in the conventional configuration, 64 ACS circuits 20 of the ACS unit 2 and 64 While 63 comparison selectors 51 to 53 are used, in the example to which the present invention is applied, only four comparison selectors are required.

Hexadecimal counter 55, S / P converter 25,
Although a circuit such as the P / S converter 54 is added, the circuit scale is much smaller than the conventional one. Further, when the present invention is applied to both the ACS unit 2 and the maximum likelihood path determination unit 5, it is possible to further reduce the circuit scale more synergistically.

According to the Viterbi decoder of the present invention, the path metric and the branch metric input to the ACS unit 2 'are converted into a serial sequence and input, and the addition / comparison / selection processing is multiplexed and time-division multiplexed. Is converted into a parallel sequence again and output, so that the number of ACS circuits 20 that perform the addition / comparison / selection processing can be greatly reduced, and the circuit scale can be reduced even if the constraint length is increased.

Further, according to the Viterbi decoder of the present invention, the path metric of the surviving path input to the maximum likelihood path determination unit 5 'is converted into a serial sequence, and the comparison and selection processing is multiplexed and performed in a time-division manner. Therefore, the number of the comparison selectors 56 to 58 for performing the comparison selection processing can be greatly reduced, and the circuit scale can be reduced even if the constraint length is increased.

According to the Viterbi decoder of the present invention, A
If both the CS unit 2 'and the maximum likelihood path determination unit 5' are configured to process in a serial sequence, there is an effect that the circuit scale can be significantly reduced.

Furthermore, if the path metric of the surviving path from the ACS unit 2 'is output as a serial sequence and input to the maximum likelihood path determination unit 5', the P / The S converter 54 can be omitted, and the circuit scale can be further reduced.

[0114]

According to the first aspect of the present invention, the path metric of each state output from the path metric memory unit in the ACS unit and the branch metric of each branch output from the branch metric calculation unit are respectively stored in the ACS unit. The path metric and the branch metric are divided into a specific plurality of groups, the path metric and the branch metric are converted into a serial sequence for each of the groups, and the path metric and the branch metric are added to the two paths that merge in an arbitrary state at the time-divided timing. An updated path metric is obtained, the two updated path metrics are compared, a path having a high likelihood is selected as a surviving path, and the path metric and path information of the surviving path are converted into a parallel sequence for each group. Since the Viterbi decoder outputs at the same timing, the ACS unit By reducing the number of circuit parts for performing addition, comparison and selection of, there is an effect of reducing the circuit scale increases exponentially with increasing constraint length.

According to the second aspect of the present invention, the branch metric calculation unit divides the branch metric associated with the path information branched from each state into a plurality of specific groups, and divides the branch metric for each group into a serial sequence. The path metric memory section divides the path metric into a plurality of specific groups, converts the path metric into a serial series for each group, time-divides and synchronizes with the branch metric calculation section. And the ACS unit outputs the path metric of each state input at time-division timing from the path metric memory unit and the branch metric of each branch input at time-division timing from the branch metric calculation unit. And the path of the two paths that merge in any state The updated path metric is obtained by adding the metric and the branch metric, the two updated path metrics are compared, a path having a high likelihood is selected as a surviving path, and the path metric and path of the selected surviving path are selected. Since the information and the Viterbi decoder are converted into parallel sequences for each group and output at the same timing, the number of circuits in the ACS section for performing addition / comparison / selection is reduced, thereby increasing the constraint length. Therefore, there is an effect that the circuit scale which increases exponentially can be reduced.

According to the third aspect of the present invention, the maximum likelihood path determination unit divides the path metric of the surviving path output from the ACS unit into a plurality of specific groups, and converts the path metric into a serial sequence for each group. Convert, compare at the time-divided timing, select the tournament by alternative comparison selection, select the path with the highest likelihood as the maximum likelihood path, and select the path number and path metric of the maximum likelihood path , The number of circuits in the maximum likelihood path determination unit that performs comparison / selection can be reduced, so that the circuit scale that increases exponentially with the increase in the constraint length can be reduced. effective.

According to the fourth aspect of the present invention, the maximum likelihood path determining section is the maximum likelihood path determining section of the third aspect of the present invention.
The CS unit is the ACS unit according to claim 1, or the branch metric calculation unit, the ACS unit, and the path metric memory unit are the branch metric calculation unit and the ACS.
And the Viterbi decoder, which is a path metric memory unit, reduces the number of circuits in the ACS unit that perform addition, comparison and selection, and further reduces the number of circuits in the maximum likelihood path determination unit that performs comparison and selection. Has the effect of reducing the circuit scale that increases exponentially with the increase in the constraint length.

According to the fifth aspect of the present invention, the ACS unit outputs the path metric of the selected surviving path as it is at the time-divided timing, and the maximum likelihood path determination unit outputs the path metric from the ACS unit for each group. Enter the output path metric of the surviving path at time-divided timing,
By comparing and selecting in a tournament with an alternative comparison selection, selecting the path with the highest likelihood as the maximum likelihood path,
The Viterbi decoder according to claim 4, which outputs a path number and a path metric of the maximum likelihood path, so that a circuit for converting a path metric selected in an ACS unit into a parallel sequence and a path metric in a maximum likelihood path determination unit are used. There is an effect that the circuit scale can be further reduced by reducing the number of circuits for converting the serial series.

According to the sixth aspect of the present invention, the maximum likelihood path determining unit according to the third aspect of the present invention divides a path metric of a surviving path in each input state into a plurality of specified groups by selecting a path metric of an arbitrary group. A specific number of P / S converters for converting metrics from a parallel sequence to a serial sequence;
A counter that counts the number of paths in the P / S converter and path metrics of serial sequences from the two P / S converters are input and compared, and a path metric having a high likelihood is selected. A path number is assigned to a path metric path according to the output from the counter, and a first comparison / selection unit that outputs a path metric and a path number, and two path metrics and path numbers from the first comparison / selection unit A second comparison / selector for inputting and comparing, selecting a path metric having a high likelihood as an alternative, and finally outputting a path metric and a path number having the highest likelihood, and a path having a high likelihood. A memory for storing the metric and the path number, a path metric and a path number from the second comparison / selector,
Third comparison and selection of inputting the path metric and the path number stored in the memory, comparing the two path metrics, selecting a path metric having a high likelihood, and outputting the selected path metric and the path number. It is preferable that the switch comprises a switch and a switch for switching an output from the third comparison selector between a memory and an external device.

According to the seventh aspect of the present invention, the maximum likelihood path determination unit according to the fifth aspect includes a counter for counting the number of a path corresponding to the path metric input from the ACS unit, and a group for each group from the ACS unit. The input two path metrics are input and compared, a path metric having a high likelihood is selected, a path number is assigned to the selected path metric path according to the output from the counter, and the path metric and the path number are assigned. A first comparison selector that outputs
The path metric and the path number from the first comparison / selector are set to 2
Input and compare them, select a path metric with a high likelihood as an alternative, output the selected path metric and the path number, and finally, the path metric and the path number with the highest likelihood , A memory for storing a path metric having a high likelihood and a path number,
, The path metric and the path number from the selector and the path metric and the path number stored in the memory are input, and the two path metrics are compared to select a path metric having a high likelihood. It is preferable to use a third comparison / selection unit that outputs a metric and a path number, and a switch that switches the output from the third comparison / selection unit between the memory and the outside.

[Brief description of the drawings]

FIG. 1 is a configuration block diagram of a branch metric calculation unit and an ACS unit of a Viterbi decoder according to the present invention.

FIG. 2 is a block diagram illustrating a configuration example of a path metric memory unit according to the present invention.

FIG. 3 is a block diagram illustrating a configuration example of a maximum likelihood path determination unit according to the present invention.

FIG. 4 is a timing chart illustrating a data output state in a branch metric calculation unit, a path metric memory unit, and an ACS unit according to the present invention.

FIG. 5 is a block diagram illustrating a configuration of an ACS unit and a maximum likelihood path determination unit according to a second embodiment in which S / P conversion and P / S conversion of a path metric are omitted.

FIG. 6 is a state transition diagram (trellis diagram) expressing an example of a convolutional code having a constraint length k.

FIG. 7 is a block diagram showing a general configuration example of a conventional Viterbi decoder.

FIG. 8 is a block diagram showing an example of the internal configuration of a conventional ACS unit.

FIG. 9 is a block diagram showing a configuration example of an ACS circuit constituting a conventional ACS unit.

FIG. 10 is a block diagram illustrating a specific configuration example of a conventional maximum likelihood path determination unit.

[Explanation of symbols]

1, 1 '... branch metric calculation unit, 2, 2',
2 "... ACS unit, 3, 3 '... Path metric memory unit, 4 ... Normalization operation unit, 5, 5', 5" ... Maximum likelihood path determination unit, 6 ... Path memory unit, 20 ... ACS circuit,
21, 22 ... adder, 23 ... comparison selector, 25 ... S /
P converter, 30 ... path metric memory block,
31: memory, 32: P / S converter, 51, 52,
53, 56, 57, 58: comparison selector, 54: P / S
Converter, 55 ... hex counter, 59 ... switch,
60 ... Memory

Claims (7)

[Claims] 1. A codeword of a trellis diagram of convolutional coding is stored in advance, demodulated data is input in units of coding blocks, and a distance between the input demodulated data and a codeword of the trellis diagram is calculated. A branch metric calculating unit that obtains a branch metric and outputs a branch metric associated with path information branched from each state; and stores a path metric of a surviving path in each state at the time of the previous decoding. A path metric memory unit that outputs the path metric in synchronization with an output from the unit; a path updated by adding a branch metric output from a branch metric calculation unit to a path metric output from the path metric memory unit Find the metric and measure the path of the two paths that meet in any state. And an ACS unit that selects a path having a high likelihood as a surviving path and outputs a path metric and path information of the selected surviving path; and a path of a surviving path in each state output from the ACS unit. Among the metrics, a path with the highest likelihood is selected as the maximum likelihood path, a maximum likelihood path determination unit that outputs the path number of the maximum likelihood path and a path metric, and a survivor in each state output from the ACS unit A normalization operation unit that subtracts the path metric of the maximum likelihood path output from the maximum likelihood path determination unit from the path metric of the path and performs normalization, and outputs the result to the path metric memory unit; The path information of the surviving path in each state is sequentially stored, and the oldest path number is stored in accordance with the path number of the maximum likelihood path from the maximum likelihood path determination unit. In a Viterbi decoder having a path memory unit that outputs path information as decoded data, the ACS unit includes a path metric in each state output from the path metric memory unit and a path metric output from the branch metric calculation unit. The branch metric of the branch is divided into a plurality of specific groups, the path metric and the branch metric are converted into a serial sequence for each of the groups, and the path metric and the path metric are merged in an arbitrary state at a time-divided timing. The updated path metrics are obtained by adding the branch metrics and the updated path metrics, and the two updated path metrics are compared to select a path with a high likelihood as a surviving path,
A Viterbi decoder, characterized in that the Viterbi decoder is an ACS unit that converts a path metric and path information of the selected surviving path into a parallel sequence for each group and outputs the parallel sequence at the same timing. 2. A codeword of a trellis diagram of convolutional coding is previously stored, demodulated data is input in units of coding blocks, and a distance between the input demodulated data and a codeword of the trellis diagram is calculated. A branch metric calculating unit that obtains a branch metric and outputs a branch metric associated with path information branched from each state; and stores a path metric of a surviving path in each state at the time of the previous decoding. A path metric memory unit that outputs the path metric in synchronization with an output from the unit; a path updated by adding a branch metric output from a branch metric calculation unit to a path metric output from the path metric memory unit Find the metric and measure the path of the two paths that meet in any state. And an ACS unit that selects a path having a high likelihood as a surviving path and outputs a path metric and path information of the selected surviving path; and a path of a surviving path in each state output from the ACS unit. Among the metrics, a path with the highest likelihood is selected as the maximum likelihood path, a maximum likelihood path determination unit that outputs the path number of the maximum likelihood path and a path metric, and a survivor in each state output from the ACS unit A normalization operation unit that subtracts the path metric of the maximum likelihood path output from the maximum likelihood path determination unit from the path metric of the path and performs normalization, and outputs the result to the path metric memory unit; The path information of the surviving path in each state is sequentially stored, and the oldest path number is stored in accordance with the path number of the maximum likelihood path from the maximum likelihood path determination unit. A Viterbi decoder having a path memory unit that outputs path information as decoded data, wherein the branch metric calculation unit divides a branch metric associated with the path information branching from each state into a specific plurality of groups, A branch metric calculation unit that converts a branch metric into a serial sequence for each group and outputs the serial metric at a time-divided timing, wherein the path metric memory unit divides the path metric into the plurality of specific groups, and sets a path for each of the groups. A path metric memory unit for converting a metric into a serial sequence, time-dividing the metric, and outputting the metric at a timing synchronized with the branch metric calculation unit, wherein the ACS unit is input from the path metric memory unit at a time-divided timing The path metric for each state and the The path metric and the branch metric of each branch input at time-division timing from the chimetric calculation unit are input, and the path metric and the branch metric are added to the two paths merging in an arbitrary state. Then, the two updated path metrics are compared, a path having a high likelihood is selected as a surviving path, and the path metric and path information of the selected surviving path are converted into a parallel sequence for each group. ACS output at the same timing
A Viterbi decoder, which is a unit. 3. A codeword of a trellis diagram of convolutional coding is stored in advance, demodulated data is input in units of coding blocks, and a distance between the input demodulated data and a codeword of the trellis diagram is calculated. A branch metric calculating unit that obtains a branch metric and outputs a branch metric associated with path information branched from each state; and stores a path metric of a surviving path in each state at the time of the previous decoding. A path metric memory unit that outputs the path metric in synchronization with an output from the unit; a path updated by adding a branch metric output from a branch metric calculation unit to a path metric output from the path metric memory unit Find the metric and measure the path of the two paths that meet in any state. And an ACS unit that selects a path having a high likelihood as a surviving path and outputs a path metric and path information of the selected surviving path; and a path of a surviving path in each state output from the ACS unit. A path with the highest likelihood among the metrics is selected as the maximum likelihood path, and a maximum likelihood path determination unit that outputs the path number of the maximum likelihood path and a path metric; and a survivor in each state output from the ACS unit. A normalization operation unit that subtracts the path metric of the maximum likelihood path output from the maximum likelihood path determination unit from the path metric of the path and performs normalization, and outputs the result to the path metric memory unit; The path information of the surviving path in each state is sequentially stored, and the oldest path number is stored in accordance with the path number of the maximum likelihood path from the maximum likelihood path determination unit. A Viterbi decoder having a path memory unit that outputs path information as decoded data, wherein the maximum likelihood path determination unit divides a path metric of a surviving path output from the ACS unit into a specific plurality of groups, The path metric is converted into a serial sequence for each group, and the time-division timing is compared and tournament-selection is performed with a binary comparison selection.The path with the highest likelihood is selected as the maximum likelihood path, A Viterbi decoder, which is a maximum likelihood path determination unit that outputs a path number and a path metric of the maximum likelihood path. 4. The Viterbi decoder according to claim 1, wherein the maximum likelihood path determination unit is the maximum likelihood path determination unit according to claim 3. 5. The ACS unit obtains updated path metrics by adding a path metric and a branch metric for two paths that merge in an arbitrary state at a time-divided timing for each group, and obtains updated path metrics. By comparing the path metrics, a path having a high likelihood is selected as a surviving path, and the path metric of the selected surviving path is output for each group with time division timing, and the selected surviving path is selected. The path information is an ACS unit that converts each group into a parallel sequence and outputs the same at the same timing. The maximum likelihood path determination unit divides the path metric of the surviving path output from the ACS unit for each group by time division. Enter at the timing you chose, compare and make a tournament selection with an alternative comparison selection Most high likelihood path is selected as the maximum likelihood path, the Viterbi decoder according to claim 4, wherein the a maximum likelihood path determination unit for outputting a path number and the path metric of the maximum likelihood path. 6. The specific number, wherein the maximum likelihood path determination unit divides a path metric of a surviving path in each input state into a plurality of specific groups, and converts a path metric of an arbitrary group from a parallel sequence to a serial sequence. A P / S converter, a counter for counting the number of paths in the P / S converter, and serial path metrics from the two P / S converters that are input and compared. Selecting a high path metric and assigning a path number to the path of the selected path metric according to the output from the counter;
A first comparison / selection unit that outputs the path metric and the path number; and a path metric and a path number from the first comparison / selection unit that are input and compared. A second comparison selector for selecting a path metric, outputting the selected path metric and the path number, and finally outputting the path metric and the path number having the highest likelihood, A memory for storing a path metric and a path number; a path metric and a path number from the second comparison / selection unit; and a path metric and a path number stored in the memory. Comparing a path metric having a high likelihood with the selected path metric and outputting the selected path metric and the path number; and outputting the output from the third comparison and selector to the memory 4. The Viterbi decoder according to claim 3, wherein the Viterbi decoder is a maximum likelihood path determination unit having a switch that switches between the units. 7. A maximum likelihood path judgment unit inputs and compares a counter for counting the number of a path corresponding to the path metric input from the ACS unit and two path metrics input for each group from the ACS unit. A first comparison / selector that selects a path metric having a high likelihood, assigns a path number to the path of the selected path metric according to the output from the counter, and outputs the path metric and the path number And inputting two path metrics and path numbers from the first comparison / selector and comparing them, selecting a path metric having a high likelihood as an alternative, and selecting the selected path metric and path number. And a second comparison / selector that finally outputs the path metric and the path number with the highest likelihood, and stores the path metric and the path number with the highest likelihood. A memory, a path metric and a path number from the second comparison / selection unit, and a path metric and a path number stored in the memory; and comparing the two path metrics, a path metric having a high likelihood. And a third comparator / selector that outputs the selected path metric and the path number, and a switch that switches the output from the third comparator / selector between the memory and the outside. The Viterbi decoder according to claim 5, wherein the Viterbi decoder is a path determination unit.