JPH05211447A - Viterbi decoder and its method - Google Patents

Abstract

PURPOSE:To decode a convolution code having an information quantity of 30Mbps or more used for, e.g. an HDTV broadcast or the like. CONSTITUTION:The decoder is provided with a swap inverter circuit 1, a punctured processing circuit 2, a branchmetric calculation circuit 3, an ACS.SM normalizing circuit 4, a normalizing command circuit 5, a state metric storage circuit 6, a path memory circuit 7, a majority decision decoding decision circuit 8, a transmission decoding circuit 9 and a synchronization discrimination control circuit 10, makes the calculation of selecting a path minimizing the distance with a reception code among paths confluent to each state node for 2 time slots and sets the selection processing time of each path to be once per 2-time slots thereby nearly halving the processing time of two time slots in comparison with a conventional method. Thus, a series closest to a code series received among code series able to be generated from a sender encoder as to input data is selected and decoding data are generated based on the selected content.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a Viterbi decoding apparatus and method used in satellite broadcasting and the like.

[0002]

2. Description of the Related Art Convolutional coding is a method of coding information of a time slot in which a past information sequence is divided into a certain number of bits while affecting a current block, and a short time slot. It is widely used in the field of communication because it has a high error correction capability even if it is long. The Viterbi decoding system is known as one of the systems for decoding the convolutional code. This Viterbi decoding method is a maximum likelihood decoding method for a convolutional code, and selects a sequence (which is called a maximum likelihood path) that is the closest to the received code sequence from the code sequences that can be generated from the encoder on the transmission side. Perform error correction with.

This method of selecting the maximum likelihood path does not check by comparing all the paths, but obtains the Hamming distances between all the code strings that can be generated on the transmission side and the received code strings, and finds the smallest one (that is, Choose the one with the highest likelihood),
After that, the basic method is to check only the path (survival path) required for decoding, and if the path length is set sufficiently long, the surviving path ends (root) will merge and become the same value. , Whichever survivor path, if traced back, the same value will be decoded. Therefore, the path length that does not increase the decoding error rate is examined, and the data traced back by the length can be used as the decoded data.

FIG. 5 is a block diagram showing an example of a Viterbi decoding apparatus using such a Viterbi decoding method. The Viterbi decoding device shown in this figure is a branch metric calculation circuit 1
01 and ACS (Add Compare Selec
t) The circuit 102, the normalization circuit 103, the state metric storage circuit 104, the path memory circuit 105, and the maximum likelihood decoding determination circuit 106 are provided, and the data (input data) output from the transmission side is input. At this time, a sequence closest to the received code sequence is selected from the code sequences that can be generated by the encoder on the transmission side, and the decoded data is generated based on the selection content.

When the input data is input, the branch metric calculation circuit 101 calculates the branch metric (Hamming distance between the reception code and the path) of this input data and outputs the calculation result (branch metric) to the ACS circuit 1.
Supply to 02.

Two ACS circuits 102 join into a certain state based on the branch metric supplied from the branch metric calculation circuit 101 and the state metric (cumulative sum) supplied from the state metric storage circuit 104. For each path, the branch metric of this path and the cumulative sum (state metric) of the branch metrics up to that point are added.

Further, the ACS circuit 102 compares these addition results, selects one with a high likelihood based on this comparison result, supplies this selection content to the path memory circuit 105, and determines the likelihood. The higher addition result is supplied to the normalization circuit 103 as a newly obtained cumulative sum (state metric).

In this case, the constraint length is (7) and the number of states (6
In the case of 4), as shown in the transition diagram of FIG. 6 for each time slot, the Hamming distance (branch metric) between the received code and the path is calculated for each of the two paths that join in a certain state. The cumulative sum (state metric) of the branch metrics is added, the addition results are compared, and the one with a high likelihood is selected based on the comparison result.

Here, the constraint length refers to the number of time slots after the time slot which is influenced by the information of a certain time slot.

The normalization circuit 103 includes the ACS circuit 10
The state metric output from 2 is normalized to a value within a preset range, and this is supplied to the state metric storage circuit 104.

The state metric storage circuit 104 stores the normalized state metric supplied from the normalization circuit 103 and feeds back the stored state metrics to the ACS circuit 102.

Further, the path memory circuit 105 uses the ACS
The selection content output from the circuit 102 is stored and the selection content is supplied to the maximum likelihood decoding determination circuit 106.

The maximum likelihood decoding determination circuit 106 determines the maximum likelihood path based on the selection contents stored in the path memory circuit 105, generates decoded data, and outputs this.

[0014]

By the way, in the Viterbi decoding apparatus as shown in the prior art, the state metric memory circuit 104 to the ACS circuit is added in order to add the value of the state metric in the pre-decoding process in the current decoding process. Up to an adder (not shown) provided in 102 are connected in a loop. Since the calculation in the loop needs to be performed within the information speed, it is necessary to reduce the upper limit of the time required in the loop portion in order to increase the information speed.

In this case, among the loops, the one having the greatest influence on the operation speed is the one that joins a certain state.
For each path of the book, the Hamming distance (branch metric) between the received code and the path and the cumulative sum (branch metric) of branch metrics up to that point are added and compared, and the ACS with a high likelihood is selected. The circuit 102.

However, as shown in FIG. 7, the conventional ACS circuit 102 used in such a Viterbi decoding apparatus has path selection signals S _(t) and S _{(t + 1)} corresponding to path transition information for each time slot. , Are output, the time T _T shown in the following equation is required as the calculation time.

[Equation 1]

Further, at this time, the accuracy of clock synchronization is strictly required due to the increase in information rate. Therefore, if the information speed is increased with the conventional circuit configuration,
In terms of circuit operation, a problem such as a shift in transition time is likely to occur, and control of a clock becomes difficult.

In the above loop, the ACS circuit 10
Similar to 2, the operation speed of the normalization circuit 103 that normalizes the state metric output from the ACS circuit 102 also has the greatest influence.

Since the normalization circuit 103 has to perform various kinds of processing such as normalization determination processing, normalization timing processing, and normalization processing, it requires a certain amount of processing time for normalization.

Therefore, unless the processing time is shortened, the speed of the loop portion cannot be shortened and the information speed cannot be increased.

Further, in a conventional Viterbi decoding apparatus, particularly a Viterbi decoding apparatus which handles a punctured code having a long constraint length, which has a large circuit scale, the number of bits of the state metric should be reduced as much as possible to reduce the circuit scale. is necessary.

However, in such a Viterbi decoding device, since the value of the state metric selected by the ACS circuit 102 is the sum of the branch metrics of the surviving paths, it constantly increases with time, and thus the ACS
A normalization circuit 103 provided after the circuit 102 normalizes the value of the state metric selected by the ACS circuit 102 under a preset condition.

At this time, the best normalization method is to subtract the minimum value from all the state metrics, but the value of the state metric output from the ACS circuit 102 by such a method. If is normalized, the processing speed of the entire loop is reduced.

Therefore, in the conventional configuration, the upper limit of the operating speed is determined by the operation speed of the loop in one time slot, and the coding rate (7 /
8), the current technology level is 25 Mb
ps becomes the limit. Therefore, there is a problem in that the amount of information of 30 Mbps or more cannot be processed as when decoding a convolutional code used in HDTV broadcasting or the like.

The present invention has been made in view of the above-mentioned problems of the prior art. For example, Viterbi capable of decoding a convolutional code having an information amount of 30 Mbps or more used in HDTV broadcasting and the like. It is intended to provide a decoding device.

[0026]

In order to achieve the above object, a Viterbi decoding apparatus and method according to the present invention calculates a branch metric for a plurality of paths for data of a plurality of time slots. Means, for each of the plurality of time slots, add branch metrics for the plurality of time slots and state metrics corresponding to these branch metrics, compare the addition results with each other, and based on the comparison result, Addition / comparison / selection means for collectively performing the process of obtaining the path having the highest likelihood, and decoding of input data based on the path contents obtained by the addition / comparison / selection means for each of the plurality of time slots And a maximum likelihood decoding determination means.

Further, for data of a plurality of time slots, branch metric calculating means for calculating branch metrics for a plurality of paths, state metric calculating and storing means for calculating and storing state metrics, and the plurality of time slots. For each time, the branch metrics for the plurality of time slots and the state metrics corresponding to these branch metrics are added, the addition results are compared with each other, and the path with the highest likelihood is obtained based on the comparison result. It has addition / comparison / selection means for collectively performing the processing, and maximum likelihood decoding determination means for decoding the input data based on the path contents obtained by the addition / comparison / selection means for each of the plurality of time slots. ..

Further, the addition / comparison / selection means, for each of the plurality of time slots, the branch metrics for the plurality of time slots at the current processing stage with each of the plurality of paths, and the state metric calculation storage means. A plurality of addition means for respectively adding the state metrics corresponding to these branch metrics up to the preprocessing stage stored in, and a plurality of comparison means for mutually comparing the addition results of these plurality of addition means, It is characterized by comprising selection means for selecting the path with the highest likelihood from the comparison results of a plurality of comparison means.

With respect to the data of 2 time slots, a branch metric calculating means for calculating branch metrics for each of a plurality of paths, a state metric calculating and storing means for calculating and storing a state metric, and for each of the 2 time slots. , The branch metrics for the two time slots at the current processing stage and the state metrics corresponding to these branch metrics are added to each of the four paths that join one state node, and the addition results are compared with each other. Then, the addition / comparison / selection means for collectively performing the process for obtaining the path having the highest likelihood based on the comparison result and the path contents obtained by the addition / comparison / selection means for each of the two time slots. And maximum likelihood decoding determination means for decoding the input data based on the input data.

Further, the addition / comparison / selection means, for every two time slots, the branch metric for the two time slots at the current processing stage with each of the four paths joining one state node, and the state. Four addition means for adding the state metrics corresponding to these branch metrics up to the preprocessing stage stored in the metric calculation storage means, and six addition means for mutually comparing the addition results of these four addition means And a selecting means for selecting the path with the highest likelihood from the comparison results of these six comparing means.

Further, a branch metric calculating means for calculating a branch metric, a state metric calculating and storing means for calculating and storing a state metric, a branch metric at the current processing stage, and the state metric calculating and storing means are stored. Based on the state metrics corresponding to these branch metrics up to the preprocessing stage, the state metric calculating means for calculating the next state metric and at least one of the MSBs of the words storing the next state metric are Normalizing timing is determined by predicting the maximum time interval from the time it is asserted to the point just before the word storing the state metric overflows,
The normalization command means for outputting a normalization command signal based on this determination, and the next state metric obtained by the calculation means in the period in which the normalization command signal is asserted from the normalization command means. The state metric is shifted to the LSB side and normalized, and this state metric is stored as a new state metric in the state metric calculation storage means, and during the period in which the normalization instruction signal from the normalization instruction means is negated, Selection / normalization means for storing the state metric of the above state metric as a new state metric in the state metric calculation storage means without normalization, and maximum likelihood decoding for decoding input data based on the new state metric And a determination means.

Further, the present invention is characterized by further comprising a swap inverter means for performing a swap inverter process for input data.

Further, branch metrics with respect to a plurality of paths are respectively calculated for data of a plurality of time slots, and branch metrics corresponding to the plurality of time slots and the branch metrics corresponding to the plurality of time slots are calculated for each of the plurality of time slots. State metric is added, the addition results are compared with each other, and the process of obtaining the path with the highest likelihood based on this comparison result is performed collectively.
The input data is decoded based on the path contents obtained by the above processing.

[0034]

In the above structure, the branch metrics for a plurality of time slots are collectively calculated by the branch metric calculating means. At the same time, the ACS calculation is performed for each of the plurality of time slots based on the branch metrics for the plurality of time slots obtained by the branch metric calculation circuit and the state metric up to that point obtained by the addition / comparison / selection (ACS calculation) means. And
The maximum likelihood decoding determination circuit decodes the input data from the path contents obtained by the ACS calculation.

In the above structure, the state metric calculation means calculates a new state metric based on the branch metric for the input data and the state metric up to that point. At the same time, among the state metrics obtained by the state metric calculating means, when at least one of the MSBs of words storing the state metric has a logical value 1 (asserted), the normalization command means When this is detected, the length of time during which the word storing each state metric does not overflow is predicted and calculated, the normalization timing is determined, and the normalization command signal is output based on this determination.

Further, in parallel with this operation, the next state metric obtained by the state metric calculating means by the selecting / normalizing means is shifted to the LSB side and normalized with the next state metric. The next state metric before conversion is generated. Along with this, when the normalization command signal from the normalization command means is output (asserted), the next normalized state metric is selected, and this is used as a new state metric for state metric calculation storage. Stored in the means. When the normalization command from the normalization command circuit is not output (negated), the next state metric before normalization is selected and stored in the state metric calculation storage means as a new state metric. Meanwhile, the maximum likelihood decoding determination circuit decodes the input data from the path contents obtained by the state metric calculation processing of the calculation circuit.

[0037]

EXAMPLE A first example will be described below. Prior to a detailed description of the first embodiment, the basic principle of the Viterbi decoding apparatus and method of the present invention will be described with reference to FIG. Now, assume that the constraint length of the input data is (7) and the number of states is (64). In the conventional method, as shown in FIG. 6, for each time slot, a calculation is performed to select a path that has the shortest distance from the received code with respect to a path that joins each state node.

On the other hand, in the Viterbi decoding apparatus and method according to the present invention, as shown in FIG. 8, the path having the shortest distance from the received code is selected from the paths that join each state node every two time slots. To perform the operation. Thus, in the conventional method, the addition processing time of the state metric (path metric) and the branch metric, the comparison processing time of each addition result, and the selection processing time of each path, which are required for each time slot, are 2 hours. The processing time for two time slots is set to the value of the following expression by setting the rate of once per slot.

[Equation 2]

Even with the method of the Viterbi decoding apparatus and method of the present invention shown in FIG. 8, the state is required regardless of the transition from four states to four states, and even when the central state in FIG. 6 is lost. The information is only the decoded word of the selected path and its transition information. Therefore, even if ACS (addition / comparison / selection) calculation is performed every two time slots, if the decoded word of the path memory circuit is transitioned in 2-bit units according to the transition diagram for two time slots, the conventional one time slot is used. You can get exactly the same result as each calculation.

The addition time T _A2 ′, the comparison time T _C2 ′, and the selection time T _S2 ′ shown in (Equation 2) are the addition time T _A required for each time slot in the conventional method shown in the following equation: The comparison time T _C and the selection time T _S have almost the same values.

[Equation 3]

In the conventional method, as shown in FIG. 7, it takes (2T _T ) time to process two time slots, whereas in the Viterbi decoding apparatus and method of the present invention, as shown in FIG. Almost half the time (T _r ')
(However, T _r '≈T _r ) can process two time slots.

FIG. 1 is a block diagram showing an embodiment of the Viterbi decoding apparatus of the present invention using the above-mentioned basic principle.
The Viterbi decoding device shown in this figure includes a swap inverter circuit 1, a punctured processing circuit 2, a branch metric calculation circuit 3, an ACS / SM normalization circuit 4, a normalization command circuit 5, and a state metric storage circuit. 6, a path memory circuit 7, a majority decoding determination circuit 8, a differential decoding circuit 9, and a synchronization determination control circuit 10. In this Viterbi decoding device, when data (input data) from the transmission side is input, a sequence closest to the received code sequence is selected from the code sequences that can be generated from the transmission side encoder, and this selection is performed. Decoded data is generated based on the content.

The swap / inverter circuit 1 takes in the input data based on the control command from the synchronization judgment control circuit 10, performs the swap / inverter process on the input data, and then punctures the processed input data. It is a circuit that supplies the circuit 2. Here, the swap inverter circuit 1 is used when performing communication via a wireless line, especially communication hygiene.
The inverter process is a process for removing the phase uncertainty of the signal sent from the satellite.

The punctured processing circuit 2 operates on the basis of the control command from the synchronization determination control circuit 10 to execute the swap
It is a circuit that takes in the input data output from the inverter circuit 1, performs punctured processing on these input data, and then supplies the processed input data to the branch metric calculation circuit 3. Here, the punctured process is a process of inserting a null signal into the erased bits decimated when transmitting the signal subjected to the convolutional coding process and performing interpolation.

The branch metric calculation circuit 3 takes in the input data output from the punctured processing circuit 2 and calculates the branch metric of this input data to obtain the result (branch metric) as ACS.SM.
This is a circuit that supplies the normalization circuit 4.

The branch metric of the input data means that a transmission sequence (y ₁ y ₂ ) obtained by convolutionally encoding the information sequence (x) is erroneous (error sequence (e ₁ e ₂ )) on a transmission path at a certain point of time. Input data received (z ₁ z ₂ )
(= (Y ₁ + e ₁ , y ₂ + e ₂ )) and the Hamming distance of each path (i). This Hamming distance (branch metric) BMX _j is defined by the following equation.

[Equation 4]

ACS / SM (Add Compare)
The Select / State Metric) normalization circuit 4 is a circuit for calculating and normalizing a state metric and selecting a path. The processing in the ACS / SM normalization circuit 4 is as described below. The ACS / SM normalization circuit 4 includes 64 unit processing circuits 11 _{1 to} 11 ₆₄ . In the unit processing circuits 11 _{1 to} 11 ₆₄ , based on the branch metric supplied from the branch metric calculation circuit 3 and the state metric (cumulative sum) supplied from the state metric storage circuit 6,
Hamming distance (branch metric) between the received code and the path for each of the four paths that join in a certain state
And the cumulative sum (state metric) of branch metrics up to that point are added to obtain an added value.

After that, these respective added values are compared, the one having a high likelihood (path having a small state metric value) is selected based on the comparison result, and the selected contents are supplied to the path memory circuit 7. At the same time, when the normalization command signal (the signal having the logical value 0) from the normalization command circuit 5 is not output, the normalization command circuit 5 is used as the added value as the newly obtained cumulative sum (state metric). And the state metric memory circuit 6.

When the normalization command signal is output from the normalization command circuit 5, the added value is normalized to a value within a preset range, and this is newly obtained as a cumulative sum. (State metric) is supplied to the normalization command circuit 5 and the state metric storage circuit 5.

As shown in FIG. 2, each of the unit processing circuits 11 _{1 to} 11 ₆₄ includes an adding section 12, a comparing section 13, an encoder section 14, and a selecting / normalizing section 15. Based on the branch metric supplied from the branch metric calculation circuit 3 and the state metric supplied from the state metric storage circuit 6, each of the unit processing circuits 11 _{1 to} 11 ₆₄ joins into a certain state. For each path, the Hamming distance (branch metric) between the received code and the path and the cumulative sum (branch metric) of branch metrics up to that point are added and compared.

Based on this comparison result, the one with a high likelihood is selected and the selected contents are supplied to the path memory circuit 7. At the same time, when the normalization command signal from the normalization command circuit 5 is not output, the newly obtained cumulative sum (state metric) is directly supplied to the normalization command circuit 5 and the state metric storage circuit 6.

When the normalization command signal is output from the normalization command circuit 5, the newly obtained state metric is normalized to a value within a preset range. Is supplied to the normalization command circuit 5 and the state metric storage circuit 6.

Here, in the state metric normalization processing, since the state metric is calculated by sequentially accumulating branch metrics, the value increases with the lapse of time. Therefore, there is a possibility that the bit length of the state metric cannot be stored (overflow).

On the other hand, the state metric does not mean that the absolute value is significant, but the magnitude relation between the values of the state metrics of each path is significant. Therefore, when the value of the state metric exceeds a certain value, for example, when the logical value 1 is set in the maximum bit (MSB) of the state metric, each state metric is minimized as in the first embodiment. This is a process of shifting the value to the bit (LSB) side by 1 bit and supplying the value within the preset range.

The adder 12 adds the branch metric for two time slots supplied from the branch metric calculation circuit 3 and the state metric supplied from the state metric storage circuit 6 to generate an added value. Four adders 16 _{1 to} 16 ₄ are provided, and four addition values AS ₁ obtained by this addition operation are provided.
~ AS ₄ is supplied to the comparison unit 13 and the selection / normalization unit 15.

In this case, the state node which is the calculation target of the unit processing circuits 11 _{1 to} 11 ₆₄ is the state metric S.
M ₀₀ , SM ₁₆ , SM ₃₂ , SM ₄₈ , and if the branch metrics are BMX ₁ , BMX ₂ , BMX ₃ , and BMX ₄ , the addition value of the value shown in the following equation from the addition unit 12 (new state Metrics AS ₁ , AS ₂ , AS ₃ , AS ₄ are generated and supplied to the comparison unit 13 and the selection / normalization unit 15.

[Equation 5]

The comparing section 13 includes the adders 16 _{1 to} 16 _1.
4 adders AS ₁ , AS ₂ , A output from 4
It is provided with _six comparators 17 _{1 to} 17 ₆ which select S 2 having a higher likelihood from each other by combining S ₃ and AS _4, and four additions output from the respective adders 16 _{1 to} 16 _4. Value A
A pair of S ₁ , AS ₂ , AS ₃ , and AS ₄ is paired and the values are compared to generate a signal indicating the higher likelihood, and the signal is supplied to the encoder unit 14.

The encoder unit 14 encodes the signals output from the comparators 17 _{1 to} 17 ₆ forming the comparison unit 13 and outputs the addition value AS output from the addition unit 12.
_{A first} encoder 18 that generates a 4-bit selection signal necessary for designating any one of ₁ , ₁ , AS ₂ , AS ₃ , and AS ₄ , and encodes a 4-bit selection signal output from the first encoder 18. And a second encoder 19 for generating a 2-bit selection signal.

This encoder section 14 is provided for each of the comparators 1
The addition values AS ₁ , AS ₂ , AS output from the adder 13 by encoding the signals output from 7 _{1 to} 17 _6
3 , a 4-bit selection signal designating either AS ₄ is generated, and the 4-bit selection signal is selected / normalized by the selection / normalization unit 15.
Supply to. At the same time, this selection signal is further encoded to generate a 2-bit selection signal and supply it to the path memory circuit 7.

As shown in FIG. 3, the selection / normalization unit 15 includes dividers 20 _{1 to} 20 ₄ and AND gates 21 ₁ to 2 4.
1 _4, the AND gate 22 ₁ to 22 _4, the inverter 2
3 and an OR gate 26. The AND gates 21 _{1 to} 21 ₄ are the first selection unit 24, and the AND gates 22 _{1 to} 22 ₄ and the inverter 23 are the second selection unit 2.
Make up 5.

Here, the four dividers 20 _{1 to} 20 ₄ are
The addition values AS ₁ , AS ₂ , AS ₃ , AS ₄ output from the addition unit 12 to the selection / normalization unit 15 are shifted to the LSB side to reduce the value to (1/2). The first selection unit 24 has four AND gates 21 _{1 to} 21 ₄ , and when the normalization command is not output from the normalization command circuit 5, the addition value AS ₁ output from the addition unit 12 AS ₂ , A
Of S ₃ and AS ₄ , the addition value designated by the 4-bit selection signal output from the encoder unit 14 is selected.

The second selection section 25 includes four AND gates 2
When the normalization command is output from the normalization command circuit 5, the normalized addition value AS output from each of the dividers 20 _{1 to} 20 ₄ has 2 _{1 to} 22 ₄ and an inverter 23. _{Of 1} , ₁ , AS ₂ , AS ₃ , and AS ₄ , the addition value designated by the 4-bit selection signal output from the encoder unit 14 is selected.

The OR gate 26 has the first selection section 24.
Also, the added value selected by one of the second selection units 25 is taken in and output as a new state metric.

Then, the selecting / normalizing unit 15 adds the added values AS ₁ , AS ₂ , AS ₃ , which are output from the adding unit 12,
Normalized the sum value AS ₄ normalized AS _1, A
S ₂ , AS ₃ , and AS ₄ and the unnormalized addition value AS ₁ ,
AS ₂ , AS ₃ , and AS ₄ are generated. With this,
At this time, if the normalization command is not output from the normalization command circuit 5, the first selection unit 24 outputs the addition value AS ₁ , AS ₂ , AS ₃ , AS ₄ , which is not normalized, from the encoder unit 14. The addition value designated by the 4-bit selection signal is selected and supplied to the normalization command circuit 5 and the state metric storage circuit 6.

If the normalization command is output from the normalization command circuit 5, of the addition values AS ₁ , AS ₂ , AS ₃ , AS ₄ that have been normalized by the second selection unit 25,
The addition value designated by the 4-bit selection signal output from the encoder unit 14 is selected and supplied to the normalization command circuit 5 and the state metric storage circuit 6.

The normalization command circuit 5, as shown in FIG.
OR gates 30 ₁ to 30 ₈ and D-type flip-flop 3
1 _{1-31 8} comprises an OR gate 32, and a normalization command generation circuit 33.

Here, eight OR gates 31 _{1 to} 31 ₈
Takes in the new state metric output from the ACS / SM normalization circuit 4 and takes the logical sum in units of eight. One OR gate 32 takes the logical sum of the logical sum data output from these D-type flip-flops 31 _{1 to} 31 ₈ . The normalization command generation circuit 33 has a shift register, delays the logical sum data output from the OR gate 32 by a preset time slot, and when the MSB has a logical value 1, normalization command ( Signal of logic 0) is generated.

The normalization command circuit 5 generates a normalization command after a predetermined time slot when any MSB of the new state metrics output from the ACS / SM normalization circuit 4 has a logical value of 1. This is ACS SM
It is supplied to the normalization circuit 4.

For example, when the maximum number of bits of the state metric is 7 and the input data is the 8-value soft decision input, the value of the state metric increases by the maximum value (14) that the branch metric can take for each time slot. Then, the time from when the MSB becomes the logical value 1 to the point before the overflow is (3.5) time slot.

Here, eight OR gates 30 ₁ to 30 ₈
And one OR gate 32 delays by 0.5 time slot, and eight D-type flip-flops 31 _{1 to} 31 ₈
1 time slot delayed by shift register 3
3 delayed by 2 time slots. As a result, a normalization command is generated after (3.5) time slots from the time when any MSB of the new state metric output from the ACS / SM normalization circuit 4 becomes the logical value 1, and this is generated. It is supplied to the ACS / SM normalization circuit 4.

The state metric storage circuit 6 stores the state metric supplied from the ACS / SM normalization circuit 4 and supplies each stored state metric to the ACS / SM normalization circuit 4.

Further, the path memory circuit 7 is the ACS / S
The selection content output from the M normalization circuit 4 is stored, and the selection content is supplied to the majority decoding determination circuit 8.

The majority decision decoding decision circuit 8 decides the maximum likelihood path based on the selection contents stored in the path memory circuit 7 to generate decoded data, which is generated by the differential decoding circuit 9 and the synchronization judgment control circuit. 10 and supply.

The differential decoding circuit 9 takes in the decoded data output from the majority decision decoding determining circuit 8 and performs differential decoding processing of this decoded data to generate decoded data, which is then output to the next-stage circuit (illustrated). Is omitted).

The synchronization determination control circuit 10 determines the synchronization based on the decoded data output from the majority decoding determination circuit 8 and determines the synchronization between the swap inverter circuit 1 and the punctured processing circuit 2 based on the content of this determination. Control synchronization.

As described above, in the first embodiment, 2
Since the ACS calculation is performed for each time slot, the time required for the ACS calculation for two time slots can be halved compared to the case where the ACS calculation is performed for each time slot.
It is possible to decode a convolutional code having an information amount of 30 Mbps or more used in broadcasting and the like.

In the first embodiment, ACS.
A normalization command circuit 5 is provided outside the loop formed by the SM normalization circuit 4 and the state metric storage circuit 6,
Outside the loop, the presence / absence of normalization processing, normalization timing processing, etc. are performed. Along with this, when it is determined that normalization is needed, before the ACS overflows at least one of the state metrics, the ACS
The state metric normalized by the SM normalization circuit 4 is selected and output as a new state metric. Therefore, A
The whole loop can be operated at a higher speed than a circuit in which an adder provided in the CS circuit, a normalization circuit, and a state metric storage circuit are connected on the loop.

In the first embodiment, ACS.
Six comparators 17 _{1 to} 17 ₆ are provided in the SM normalization circuit 4, and the four addition values AS ₁ , AS ₂ , AS ₃ , AS ₄ output from the adders 16 _{1 to} 16 ₄ are provided at once. It is possible to make a comparison and determination, which makes it possible to obtain the maximum likelihood sum with a minimum delay time.

Further, in the first embodiment, since the ACS operation is performed in units of two time slots, the ACS operation for two time slots is performed more than when the ACS operation is performed for each time slot. The time required can be reduced to about half, and thus the convolutional code having the information amount of 30 Mbps or more used in HDTV broadcasting can be decoded.

In the first embodiment, ACS.
Six comparators 17 _{1 to} 17 ₆ are provided in the SM normalization circuit 4, and four addition values AS ₁ , AS ₂ , AS ₃ , AS ₄ output from each of the adders 16 _{1 to} 16 ₄ are set two by two. The values are compared in pairs and the one with the higher likelihood is selected.
Therefore, these added values AS ₁ , AS ₂ , AS ₃ , AS
₄ can be compared and judged at once, and the maximum likelihood sum can be obtained with the minimum delay time.

The second embodiment will be described below. In the second embodiment, for paths that join each state node, which has been performed every two time slots in the second embodiment,
The operation to select the path that minimizes the distance from the received code is
It is performed every n time slots (n> 2, n is an integer), for example, every 3 time slots.

In the conventional method, as described in the first embodiment, the operation for selecting the path having the smallest distance from the received code is selected from the paths joining each state node for each time slot. To do.

On the other hand, in the Viterbi decoding apparatus of the second embodiment, in the first embodiment, the distance from the received code is the smallest for the paths that join each state node performed every two time slots. The calculation for selecting the path to be performed is performed every three time slots. Thus, in the conventional method, the addition processing time of the state metric and the branch metric required for each time slot, the comparison processing time of each addition result, and the selection processing time of each path are once every three time slots. The processing time for 3 time slots is set to the value of the following equation.

[Equation 6]

Even if ACS (addition / comparison / selection) calculation is performed every three time slots, the same result as the conventional calculation for each time slot can be obtained. The addition time T _A3 ′, the comparison time T _C3 ′, and the selection time T _S3 ′ shown in (Equation 6) are the addition time T _A and the comparison time T required for each time slot in the conventional method shown in the following equation. _The values of _C and the selection time T _S are almost the same.

[Equation 7] As described above, in the second embodiment, since the ACS calculation is performed in units of n time slots, compared to the case where the ACS calculation is performed for each time slot,
Approximately (1
/ N), and the decoding of the convolutional code can be realized at a higher speed than that of the Viterbi decoding apparatus of the first embodiment.

The third embodiment will be described below. In the first embodiment, the ACS / SM normalization circuit 4 collectively performs the ACS operation and the normalization processing of the state metric, but it is configured to perform them by another circuit. The configuration and operation of each part of the Viterbi decoding apparatus according to the third embodiment not described here are as described in the first embodiment.

FIG. 10 shows the configuration of the Viterbi decoding apparatus according to the third embodiment. State metric calculation circuit 40
Is a circuit that calculates a state metric based on the branch metric output by the branch metric calculation circuit 3. The ACS circuit 41 is a circuit that performs ACS calculation. Even with this configuration, it is possible to obtain the same effects as the Viterbi decoding apparatus and method 1 according to the first embodiment.

The fourth embodiment will be described below. The fourth embodiment is a modification of the ACS / SM normalization circuit 4. In the first embodiment, the ACS / SM normalization circuit 4 shifts the state metric to the LSB side by 1 bit when the MSB of the state metric has a logical value 1 as a state metric normalization method. Although the normalization has been performed, in this embodiment, the state metric is normalized by subtracting the smallest value of the state metric from the state metric itself and other state metrics.

According to the state metric normalization method of the fourth embodiment, it is possible to more accurately store the magnitude of the mutual values of the state metrics even after normalization.
Further, the normalization of the state metric described in the first embodiment and the ACS calculation in units of n time slots described in the first and third embodiments are not indivisible and may be used separately. It is possible.

In addition to the configuration described above, the Viterbi decoding apparatus and method of the present invention can have various configurations.
The embodiments described above are merely examples.

[0090]

As described above, according to the present invention, a convolutional code having a very high information rate can be decoded.

[Brief description of drawings]

FIG. 1 is a block diagram showing an embodiment of a Viterbi decoding device according to the present invention.

FIG. 2 is a block diagram showing a detailed configuration example of an ACS / SM normalization circuit shown in FIG.

3 is a circuit diagram showing a detailed configuration example of a selection / normalization unit shown in FIG.

FIG. 4 is a circuit diagram showing a detailed configuration example of a normalization command circuit shown in FIG.

FIG. 5 is a block diagram showing an example of a conventionally known Viterbi decoding device.

FIG. 6 is a transition diagram of two time slots showing an operation example of the ACS circuit shown in FIG.

FIG. 7 is a schematic diagram showing a time required for a calculation of the ACS circuit shown in FIG.

FIG. 8 is a transition diagram for two time slots showing the basic principle of the Viterbi decoding device according to the present invention.

FIG. 9 is a schematic diagram showing a time required for ACS calculation according to the present invention.

FIG. 10 shows ACS / S in the Viterbi decoding device of the present invention.
It is a figure which shows the modification of the M normalization circuit.

[Explanation of symbols]

 3 ... Branch metric calculation circuit 4 ... ACS / SM normalization circuit (ACS calculation circuit) 5 ... Normalization command circuit 6 ... State metric storage circuit 7 ... Bus memory circuit 8 ... Majority decision decoding decision circuit

Claims (8)

[Claims] 1. Data of a plurality of time slots,
Branch metric calculation means for respectively calculating branch metrics for a plurality of paths, and for each of the plurality of time slots, add branch metrics for the plurality of time slots and state metrics corresponding to these branch metrics, An addition / comparison / selection unit that collectively performs a process of comparing addition results with each other and obtaining a path having the highest likelihood based on the comparison result; and the addition / comparison / selection unit for each of the plurality of time slots. A Viterbi decoding device having maximum likelihood decoding determining means for decoding input data based on the path contents obtained by the above. 2. Data of a plurality of time slots,
Branch metric calculation means for respectively calculating branch metrics for a plurality of paths, state metric calculation storage means for calculating and storing state metrics, and branch metrics for the plurality of time slots for each of the plurality of time slots. Addition / comparison / selection means for collectively performing the processing of adding the state metrics corresponding to these branch metrics, comparing the addition results with each other, and obtaining the path with the highest likelihood based on the comparison results. A Viterbi decoding device having maximum likelihood decoding determination means for decoding input data based on the path contents obtained by the addition / comparison / selection means for each of the plurality of time slots. 3. The Viterbi decoding apparatus according to claim 2, wherein the addition / comparison / selection means for each of the plurality of timeslots corresponds to the plurality of timeslots in a current processing stage with each of the plurality of paths. A plurality of adding means for adding the branch metric and the state metrics corresponding to these branch metrics stored in the state metric calculating and storing means up to the pre-processing stage, and the addition results of the plurality of adding means are mutually calculated. A Viterbi decoding apparatus, comprising: a plurality of comparing means for comparing with each other and a selecting means for selecting a path having the highest likelihood from the comparison results of the plurality of comparing means. 4. A branch metric calculation means for calculating branch metrics of a plurality of paths for data of two time slots, a state metric calculation storage means for calculating and storing a state metric, and for each of the two time slots. , Each of the four paths that join one state node
The branch metrics for the time slots and the state metrics corresponding to these branch metrics are added, the addition results are compared with each other, and the process of obtaining the path with the highest likelihood based on the comparison result is collectively performed. A Viterbi decoding apparatus comprising: an addition / comparison / selection unit; and a maximum likelihood decoding determination unit that decodes input data based on the path contents obtained by the addition / comparison / selection unit every two time slots. 5. The Viterbi decoding apparatus according to claim 4, wherein the adding / comparing / selecting means performs the above-mentioned 2 in each time slot with the current processing stage of each of the 4 paths joining one state node. Four adding means for adding the branch metrics for the time slots and the state metrics corresponding to these branch metrics stored in the state metric calculating and storing means up to the pre-processing stage, and these four adding means. The Viterbi decoding device is characterized by comprising six comparison means for mutually comparing the addition results of the above, and selection means for selecting the path having the highest likelihood from the comparison results of these six comparison means. .. 6. A branch metric calculating means for calculating a branch metric, a state metric calculating and storing means for calculating and storing a state metric, a branch metric at a current processing stage, and a state metric stored in the state metric calculating and storing means. State metric calculation means for calculating the next state metric based on the state metric corresponding to these branch metrics up to the preprocessing stage, and at least one of the MSBs of the words storing the next state metric, Normalizing command means for predicting and calculating the maximum time interval from the time of being asserted to the time just before the word storing the state metric overflows to determine the normalization timing, and outputting a normalization command signal based on this determination. , The normalization While the normalization command signal is asserted from the command means, the next state metric obtained by the calculation means is shifted to the LSB side and normalized, and the state metric is used as a new state metric. In the period in which the normalization command signal from the normalization command means is stored in the calculation storage means and the normalization command signal from the normalization command means is negated, the normalization is not performed for the next state metric and the state metric is used as a new state metric. A Viterbi decoding device comprising: a selection / normalization unit to be stored in a calculation storage unit; and a maximum likelihood decoding determination unit to decode input data based on the new state metric. 7. The Viterbi decoding device according to claim 1, further comprising a swap inverter means for performing a swap inverter process for input data. 8. The data of a plurality of time slots,
The branch metrics for a plurality of paths are respectively calculated, the branch metrics for the plurality of time slots and the state metrics corresponding to these branch metrics are added for each of the plurality of time slots, and the addition results are mutually calculated. A Viterbi decoding method that performs a process of collectively comparing and obtaining a path having the highest likelihood based on a result of the comparison, and decoding input data based on the path contents obtained by the process.