JP3530451B2 - Viterbi decoding device - Google Patents

Description

Description: BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a Viterbi decoding device, and more particularly, to an improvement in a Viterbi decoding device for decoding a convolutional code by a maximum likelihood decoding method. 2. Description of the Related Art Viterbi decoding is a method for efficiently realizing the maximum likelihood decoding of convolutional codes, and has a strong error correction capability, so that error correction of digital signals in a satellite communication system or a mobile communication system can be performed. Widely used as a method. Viterbi decoding is one of the maximum likelihood decoding schemes for estimating a transmission sequence closest to a transmitted reception sequence and decoding the original information sequence. The outline of the decoding principle of the Viterbi decoding device will be described below using a simple example. FIG. 5 is a block diagram showing an example of a configuration of an encoder for generating a convolutional code, which has a relatively simple configuration with a constraint length of four. This encoder includes three delay lines 1 to 3 and two exclusive OR circuits 4 and 5. The generator polynomial of this encoder is G0 (X) = X ³ +
1 is ^{G1 (X) = X 3 +} X 2 + X 1 +1. The input signal of 0 or 1 is the delay line 1
3 are sequentially shifted, and each time the exclusive OR circuits 4 and 5 output 0 or 1 signals G0 and G1. That is, while the original input signal X to the convolutional encoder is one, the output convolutional code is two. In other words, since two codes must be actually transmitted for one signal to be transmitted, the coding rate of this encoder is r = １ ／. The signals affecting the outputs G0 and G1 are a total of four signals including the input X and the respective signals of the delay lines 1 to 3, so that the constraint length is K = 4.
It is. Each of the delay lines 1 to 3 is 0 or 1
Are latched, there are two states. Therefore, the delay lines 1 to 3 as a whole are 8 (= 2 ³ ).
It has the following states: Hereinafter, these eight states are described as S000 to S111. For example, a state in which delay line 1 latches 0, delay line 2 latches 0, and delay line 3 latches 1 is expressed as S100. FIG. 6 is a state transition diagram of the encoder shown in FIG. In FIG. 6, two digits before “/” indicate outputs G0 and G1, and one digit after “/” indicates input X. For example, when 0 is input in the state S000, the state transits to the same state S000 again and 00 is output. On the other hand, when 1 is input in the state S000, the state transits to the state S001 and 11 is output. Alternatively, when 0 is input in the state S110, the state transits to the state S100 and 10 is output. On the other hand, when 1 is input in the state S110, the state transits to the state S101 and 01 is output. FIG. 7 is a trellis diagram of the encoder shown in FIG. Here, the initial state at time T = 0 is S000
And The transition path when the input is 0 is shown by a solid line, and the transition path when the input is 1 is shown by a dotted line. When 0 is input in the state S000 at the time T = 0, 00 is output and the state S00 at the time T = 1 is output.
When a transition is made to 0, while 1 is input, 11 is output and the state transits to the state S001 at time T = 1. When 0 is input in state S001 at time T = 1, 11 is output and state S01 at time T = 2 is output.
When a transition is made to 0, while 1 is input, 00 is output and the state transits to a state S011 at time T = 2. When 0 is input in state S011 at time T = 2, 10 is output and state S11 at time T = 3 is output.
When the state transits to 0, while 1 is input, 01 is output and the state transits to the state S111 at time T = 3. When 0 is input in state S111 at time T = 3, 01 is output, and state S11 at time T = 4 is output.
When the state transits to 0, while 1 is input, 10 is output and the state transits to the state S111 at time T = 4. As described above, the encoder shown in FIG.
Or, it generates 00, 01, 10 or 11 output signals G0 and G1 according to one input signal X. The output signals G0,
G1 is usually subjected to parallel-serial conversion and transmitted as a convolutional code to a Viterbi decoding device. FIG. 8 is a schematic block diagram showing a general configuration of a Viterbi decoding apparatus for decoding the transmitted convolutional code into the original input code sequence by the maximum likelihood decoding method. Referring to FIG. 8, branch metric calculation circuit 1
01 is a difference between the received convolutional code and the expected reception code in each of the eight possible states (S000 to S111) of the convolutional encoder each time the convolutional code is received. The metric is calculated and given to the ACS circuit 102 described later. The calculation of the branch metric will be described later. As shown in FIG. 7, after time T = 4, each state has two paths that transition to that state. ACS (Add Compare Select) circuit 1
02 is read from the cumulative metric storage circuit 105;
The cumulative metrics associated with the two paths at the previous reception, that is, at the time T = 3, are added to the two metrics at the time T = 4 calculated by the branch metric calculation circuit 101.
Add the branch metrics for each of the paths. The ACS circuit 102 compares the addition results of the two paths transitioning to the state with each other, and leaves the path with the smaller addition result, that is, the path with the higher likelihood, and the other path. Throw away the path. This remaining path is generally called a “surviving path”. The path memory 103 stores and outputs information for specifying the surviving path. Further, the result of addition of the surviving paths calculated in this state is stored in the cumulative metric storage circuit 105 as a cumulative metric. The ACS circuit 102 has eight possible encoders.
The above operations are sequentially performed for each of the following states. As described above, when the surviving path is determined for each state, as shown in FIG.
The surviving paths converge to one. In the example of FIG. 9, at time T = 9, the surviving paths from time T = 0 to T = 4 have converged to one. In this state, the maximum likelihood sequence determining circuit 10 shown in FIG.
6 shows eight states at time T = 9 (S000 to S1).
11) The magnitude of all finally calculated cumulative metrics is determined. That is, the state having the smallest cumulative metric among the eight states is determined to have the highest likelihood (most likely). The path selection circuit 104 selects and outputs the maximum likelihood surviving path information from the surviving path information output from the path memory 103 according to the decision output of the maximum likelihood sequence decision circuit 106. That is, surviving path information that traces the surviving path corresponding to the state determined to be the maximum likelihood and goes back to state S000 at time T = 0 is successively read. The read survival path information is decoded into a code sequence received by the path selection circuit 104. The above is an outline of the Viterbi decoding described using a relatively simple example of the constraint length K = 4. Viterbi decoding itself is a well-known technique in the art, and its details are described in, for example, "Introduction to Coding Theory" by Yoshihiro Iwatari (published by Shokodo Co., Ltd., December 20, 1992).
Pp. 135-159. In reality, a satellite communication system or a mobile communication system usually uses a convolutional code having a larger constraint length. For example, in these applications, the constraint length K =
A convolution with 9 encoders is used. FIG.
Is a block diagram illustrating an example of such a convolutional encoder with a constraint length K = 9. This encoder includes eight delay lines 1 to 8 and two exclusive OR circuits 9 and 10. The generator polynomial for this encoder is: [0025] G0 (X) = 1 + X 2 + X 3 + X 4 + X 8 G0 = 561 8 G1 (X) = 1 + X + X 2 + X 3 + X 5 + X 7 + X 8 G1 = 753 8 ( It should be noted that 8 of the subscript is the octal An input signal of 0 or 1 sequentially shifts the delay lines 1 to 8, and each time the exclusive OR circuits 9, 10
Output signals G0 and G1 of 0 or 1. Since each of the delay lines 1 to 8 latches a signal of 0 or 1, it has two states. Therefore, the delay lines 1 to 8 as a whole have 256 (= 2 ⁸ ) states.
Thus, when the constraint length is K = 9, the aforementioned K = 4
Since the number of states increases exponentially as compared with the case of (1), it is difficult to show a state transition diagram as in FIG. 6 or a trellis diagram as in FIG. 7, and illustration thereof is omitted here. In the encoder shown in FIG. 10, the signal input side is defined as the MSB, and the initial value of the encoder state is S000.
00000, and this state is referred to as state number 0 among the 256 states. Here, when 1 is input, the state of the encoder becomes S10000000, and the decimal number 128 is set as the state number of this state. Subsequently, when 0 is input, the state of the encoder becomes S01000000, and 64 which is a decimal representation thereof is set as the state number of this state. Therefore, 256 states that the encoder can take are represented by state numbers J = 0 to 255. Next, a method of calculating a branch metric will be described. In Viterbi decoding, when transiting from a certain state to the next state, a cross-type change is made as shown in FIG. This is apparent from the shape of the transition in the trellis diagram when the constraint length is K = 4 in FIG. From the shape of the state change shown in FIG. 11, such a state transition is usually called a butterfly operation. More specifically, the state of the encoder will be described in detail using a state number J that is displayed in decimal. For the state assumed as the next state to transit from a certain state number 2J, “1” is input to the convolutional encoder. "J + (the number of all states /
2) ", or" J "which transits when" 0 "is input. On the other hand, the state assumed as the next state which transits from a certain state number 2J + 1 is the state of "J + (all number of states / 2)" which transits when "1" is input to the convolutional encoder. , Or “J” that transits when “0” is input. In the example of FIG. 11, for example, there are two paths that transition to the state number J. Then, the expected 2-bit received code sequence (00,
01, 10, 11).
The difference (distance) between the 2-bit expected value for each path and the actually received 2-bit convolutional code is calculated for each path as a branch metric. In more detail,
The branch metric for each received code is calculated as the sum of the Euclidean distance (inner product) between the expected 2-bit input value and the actual 2-bit input value. In FIG. 12, when the received convolutional code has two bits A and B, the branch metric which is the distance from the expected reception value 00 is represented by S + P, and the distance from the expected reception value 01 is The distance from the expected reception value 10 is represented by S + Q, and the distance from the expected reception value 10 is represented by T + P.
Is represented by T + Q. As shown in FIG. 12, when determining received data, each bit is set to "1" at a certain threshold,
There are a further decision that is divided into "0" and a soft decision which is treated as a value having a range from "0" to "15", for example, and the above branch metric calculation method relies on a soft decision method. The closer the distance between the expected received code and the actually received code is, the more likely it is that the received code is a more likely code. Therefore, as described above, the final accumulated value of this distance (branch metric) Is determined as the most likely code sequence (most likely code sequence). In Viterbi decoding, it is necessary to store a code sequence having such a minimum cumulative metric.
In the Viterbi decoding device having the general configuration shown in FIG. 8, such code sequence information is stored in the path memory 103 as described above. Various examples of the specific configuration of the path memory 103 are conceivable. For example, as shown in FIG. 13, a shift register configured by connecting a large number of flip-flop circuits 11 in a plurality of stages is used. What can be considered. Each of the flip-flop circuits 11 shown in FIG. 13 basically has the configuration shown in FIG. The configuration of the path memory 103 shown in FIG. 13 shows an example of a configuration in which the constraint length is 3, and states 00, 01, and 1 that a convolutional encoder (not shown) can take.
A plurality of flip-flop circuits 11 are arranged on lines corresponding to 0 and 11, respectively. Although it is considered that the number of stages of such a shift register is originally appropriate to be approximately 5 to 6 times the constraint length, in FIG. 13, only four stages are provided for simplification of illustration. It is shown as a shift register. The path memory (shift register) 1 shown in FIG.
In each of the flip-flop circuits 11 of the second and subsequent stages of 03, the path memory 103 is configured such that the path from the two flip-flop circuits 11 of the preceding stage transitions. Each flip-flop circuit 11 has the configuration shown in FIG. 14, and each of the two inputs of the selector 12 has a corresponding flip-flop circuit 11
, Information that specifies the surviving state, respectively, is input. On the other hand, the selector 12
Is supplied from the ACS circuit 102 (FIG. 8) to the control input of which signal which specifies the path with the higher likelihood of the two inputs, and the information which specifies which state is surviving in the previous stage is selected by the selector. 12 stores the data in the flip-flop element 13. In the shift register (FIG. 13) constituting the path memory 103, every time the convolutional code is received, the data is shifted to the flip-flop circuit 11 of the next stage. 01, 10, 1
For each of the information items 1, information for specifying a code sequence is output. Then, information specifying the code sequence corresponding to the state with the highest likelihood determined by the maximum likelihood sequence determination circuit 106 is selected by the path selection circuit 104 and output. [0043] As shown in FIG. 13,
The path memory 103 has a configuration of a shift register, and after a plurality of stages of shift processing, data specifying a surviving path is output. Therefore, the path memory 103
In the output data of the path memory 103, a delay occurs with respect to the received code sequence by a processing time corresponding to the number of stages of the shift register. More specifically, even if all of the received code sequence consisting of the convolutional code has been received, the data being processed remains in the path memory 103. Therefore, such residual data is also stored in the path memory 103. 103 must be extracted. Therefore, after the reception of the received code sequence,
For example, a method of extracting data remaining in the path memory 103 by giving data including a plurality of 0s as a dummy input is conceivable. However, if dummy data consisting of 0 is input immediately after the received data, there is a possibility that an error occurs in the output data of the path memory 103 due to the data of the dummy input 0. In order to avoid the influence of such a dummy input, it has been necessary to add a tail bit consisting of a plurality of 0s at the end of the input data sequence itself. Such addition of the tail bit is an undesirable constraint on the amount of data that can be transmitted. An object of the present invention is to provide a Viterbi decoding device capable of performing error-free Viterbi decoding without including a special tail bit in transmission data. According to the first aspect of the present invention, there is provided a Viterbi decoding apparatus for decoding a reception code sequence including a convolutional code generated by a convolutional encoder by a maximum likelihood decoding method. It includes a branch metric calculation unit, an operation comparison unit, a cumulative metric storage unit, a path information storage unit, a maximum likelihood sequence determination unit, a path selection unit, and an input selection unit. Each time a convolutional code is received, the branch metric calculation means calculates a branch metric for each path that transits to each of a plurality of states that the convolutional encoder can take. The operation comparing means adds the branch metric of each of the two paths calculated by the branch metric calculating means to the accumulated metric at the previous reception of the convolutional code, which is associated with the two paths transitioning to each of the plurality of states. Are added to each other, and the addition results of the two paths are compared with each other, and the path with the higher likelihood of the two paths is determined as the surviving path. The cumulative metric storage means stores the addition result of the operation comparing means as a cumulative metric. The path information storage means includes a plurality of flip-flop circuits, and stores and outputs information for specifying the determined surviving path. The maximum likelihood sequence determining means determines a surviving path with the highest likelihood by comparing all final accumulated metrics in a plurality of states. The path selecting means determines a received code sequence having the highest likelihood based on the information specifying the surviving path output from the path information storage means, according to the determined output of the maximum likelihood sequence determining means. The input selecting unit is configured to output the maximum possible data of each of the received code sequences during a period from when the final data of the received code sequence is received to when the final data of the information specifying the surviving path is output from the path information storage unit. A value corresponding to an intermediate value between the value and the minimum value is provided to the branch metric calculation means. As described above, according to the first aspect of the present invention, during the period corresponding to the processing delay period in the path information storage means, the value corresponding to the intermediate value between the maximum value and the minimum value of the received code data is changed. Since it is input, it is possible to extract the information specifying the surviving path without error without adding a tail bit in the transmission data in advance. Embodiments of the present invention will be described below in detail with reference to the drawings. In the drawings, the same or corresponding portions have the same reference characters allotted, and description thereof will not be repeated. FIG. 1 is a schematic block diagram showing a configuration of a Viterbi decoding device according to an embodiment of the present invention. The Viterbi decoding device shown in FIG. 1 is the same as the general Viterbi decoding device shown in FIG. 8 except for the following points. That is, in the general Viterbi decoder of FIG. 8, the received signal is directly input to the branch metric calculation circuit 101, whereas in the Viterbi decoder of the embodiment of FIG. An input selection circuit 100 is provided at a stage preceding 101, and a received signal is input to the input selection circuit 100. FIG. 2 is a block diagram showing a configuration of the input selection circuit 100. The two inputs of the two-input selector 20 receive the data of the received code sequence and a fixed value supplied from the signal source 21 and corresponding to an intermediate value between the maximum value and the minimum value of the received data, which are selected. Input as a signal. The input data control circuit 22 selects the received data from the start of the Viterbi decoding to the end of the reception of the received code sequence, and thereafter, the processing time corresponding to the number of stages of the shift register (FIG. 13) constituting the path memory 103 A selection signal is given to the control input of the selector 20 so that the fixed value from the signal source 21 is selected only during the period corresponding to. Here, the intermediate value of the received data is from 7 or 8 or from “−8” when it is handled as a value having a range from “0” to “15” based on the above soft decision. When it is handled as a value having a width up to “7”, it is a value such as 0 or 1. The reason why there are two values as intermediate values is that there is no integer corresponding to the intermediate value between the maximum value and the minimum value in the above case. FIG. 3 is a timing chart showing the relationship between the input data (received code sequence) of the Viterbi decoding device and the output data of the path memory 103. As shown in FIG. 3, even when a data sequence composed of a convolutional code starts to be input, no data is output because the output data of the path memory 103 still remains in the path memory 103. When an input data sequence is input by the number of shift register stages of the path memory 103, output data relating to the input data is output from the path memory 103 for the first time. Thereafter, as the processing proceeds, for each set of convolutional codes (consisting of two codes) constituting the input data, as a result, the data becomes 1
Are output. The output data of the path memory 103 at that time is data delayed by the number of shift register stages of the path memory 103. After the last input data is input, an intermediate value is input by the switching operation of the selector 20, and the Viterbi decoding process proceeds similarly. The intermediate values are input for the number of shift register stages of the path memory. In this way, the result for the last input data remaining in the path memory 103 is extracted. Next, by making the input value an intermediate value,
The reason why output data remaining in the path memory 103 can be extracted without error will be described. In the Viterbi decoding, as described above, the difference or distance (expressed by a metric value) between the code sequence assumed by the receiving side and the actually received code sequence is calculated.
This is a decoding method for obtaining an assumed code sequence having the smallest calculated distance as a maximum likelihood sequence. FIG. 4 is a diagram schematically showing the relationship between the code sequence received up to the present time and the code sequence assumed on the receiving side. Note that the state shown in FIG. 4 corresponds to the point in time when the input of the received data has been completed. Further, the code sequences assumed on the receiving side are represented by A, B, C, D, and the differences or distances between these code sequences and the actually received code sequences are represented by a, b, c, d (a < b <c
<D). Until the time point shown in FIG. 4, the received sequence can be considered to be the assumed code sequence A having the smallest difference a. However, after this, if a random value or the like is input, and as a result, the difference between the received sequence and the assumed code sequence has a relationship of a> b, the Viterbi decoding device converts the received sequence into ,
It is determined that the code sequence B is assumed. As a result, the decoding operation will be erroneous (what the magnitude relationship of the difference between the codes will be is determined by the input data sequence). Even if the input signal is not a random value as described above, a similar situation occurs when, for example, a fixed value corresponding to 0 or 1 is input. However, if an intermediate value between the maximum value and the minimum value that can be taken by the input data is input instead of the random value as described above, A to D
Since the difference (distance) of each of the code sequences is the same from any of the code sequences, a <<
It does not affect the magnitude relation of b <c <d. Therefore, the original code sequence A can be correctly output without being mistaken for another code sequence. As described above, in the Viterbi decoding apparatus according to the embodiment of the present invention, special data such as tail bits are not added to the transmission data, and the data remains in the path memory even after the end of the reception of the input data. Data can be extracted without error. The embodiments disclosed this time are to be considered in all respects as illustrative and not restrictive. The scope of the present invention is defined by the terms of the claims, rather than the description above, and is intended to include any modifications within the scope and meaning equivalent to the terms of the claims. According to the present invention, during the period required for the shift register processing of the path memory after the reception of the input data,
By inputting a fixed value corresponding to an intermediate value between the maximum value and the minimum value that can be taken by the input data and continuing the Viterbi decoding, the pass data can be transmitted without adding special data such as tail bits in advance in the transmission data. Data remaining in the memory can be extracted without error.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a block diagram illustrating an overall configuration of a Viterbi decoding device according to an embodiment of the present invention. FIG. 2 is a block diagram illustrating a configuration of an input selection circuit of FIG. 1; FIG. 3 is a timing chart showing a relationship between input data and output data. FIG. 4 is a diagram schematically showing the principle of the present invention. FIG. 5 is a schematic block diagram showing a simple example of a convolutional encoder. 6 is a state transition diagram of the encoder shown in FIG. 7 is a trellis diagram of the encoder shown in FIG. FIG. 8 is a block diagram illustrating a configuration of a general Viterbi decoding device. 9 is a trellis diagram for explaining the operation of the Viterbi decoding device shown in FIG. FIG. 10 is a block diagram illustrating another example of a convolutional encoder. FIG. 11 is a diagram schematically illustrating a butterfly operation in Viterbi decoding. FIG. 12 is a diagram illustrating a method of calculating a branch metric in Viterbi decoding. FIG. 13 is a block diagram showing a configuration of the path memory shown in FIG. 14 is a block diagram illustrating a configuration of the flip-flop circuit illustrated in FIG. [Description of Signs] 20 selector, 21 signal source, 22 input data control circuit, 100 input selection circuit, 101 branch metric calculation circuit, 102 ACS circuit, 103 path memory, 1
04 path selection circuit, 105 cumulative metric storage circuit, 106 maximum likelihood sequence determination circuit.

Claims (1)

(57) Claims 1. A Viterbi decoding device for decoding a received code sequence formed of a convolutional code generated by a convolutional encoder by a maximum likelihood decoding method, wherein each time the convolutional code is received, Branch metric calculation means for calculating a branch metric for each path transitioning for each of a plurality of possible states of the convolutional encoder; Adding the branch metrics of each of the two paths calculated by the branch metric calculation means to the accumulated metric of the previous reception of the convolutional code, and comparing the addition results of the two paths with each other; An operation comparing means for determining a path having a higher likelihood among the two paths as a surviving path; and an addition result of the operation comparing means as a cumulative metric. Cumulative metric storage means, a plurality of stages of flip-flop circuits, and path information storage means for storing and outputting information specifying the determined surviving path; and all final cumulative metrics of the plurality of states. A maximum likelihood sequence determining unit that determines a surviving path with the highest likelihood by comparing the maximum likelihood sequence determining unit with information that specifies the surviving path output from the path information storage unit in accordance with the determination output of the maximum likelihood sequence determining unit Path selecting means for determining a received code sequence having the highest likelihood based on the last data of the received code sequence, and the final data of the information specifying the surviving path from the path information storage means after the final data of the received code sequence is received. During the period until output, the branch metric calculation means calculates a value corresponding to an intermediate value between the maximum value and the minimum value that can be taken by each data of the received code sequence. And an input selection means for providing, Viterbi decoder.