JPH04329027A - viterbi decoder - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed description of the invention]

0001

[Industrial Application Field] The present invention uses a Viterbi sequence to encode a code sequence in which an information sequence is encoded by a convolutional encoder that takes an arbitrary initial state at the time of data transmission and whose initial state and final state are the same. This invention relates to a Viterbi decoder that performs maximum likelihood decoding.

As is well known, convolutional encoders are characterized by the information rate R and constraint length K of the code. The information rate R of the code is given by k/n when k information bits of the information sequence are encoded into n code bits of the code sequence. For example, when one information bit of an information sequence is represented by two code bits of a code sequence, R=1/2. Restraint length K
indicates the range affected by the information bits of a certain block, and is given by K=(m+1)n, where m is the order of the code generation polynomial and n is the length of the partial block. Convolutional codes are codes in which encoding is performed block by block, but information on past blocks also affects the current block. Convolutional encoders can take on multiple internal states. That is, when the number of delay elements included in a convolutional encoder is d, each delay element takes a logic "0" or "1", so the convolutional encoder can take on 2d internal states. Every time k information bits of the information sequence are input, the internal state of the convolutional encoder changes. The transition of the internal states of a convolutional encoder over time is illustrated by a trellis diagram, which is well known in the art. Simply stated, a trellis diagram is a representation of internal state transitions and outputs with the time axis horizontal. Therefore, when transmitting data, that is, when encoding an information sequence into a code sequence,
A convolutional encoder undergoes a transition in its internal state from an initial state to a final state. The initial state is also called the starting point, and the final state is also called the ending point. A transition route between internal states is called a path. There are three types of methods for selecting the starting point of a convolutional encoder. That is, (2) all the delay elements included in the convolutional encoder are set to the logic "0" state at the starting point. ■Do not specify a starting point. ■ Select one of the possible internal states of the convolutional encoder as a starting point. Furthermore, among ■, some have the same starting point and ending point. The present invention receives a code sequence in which an information sequence is encoded by a convolutional encoder having the same starting point and ending point as a received sequence via a transmission path, and maximum likelihood decodes this received sequence using a Viterbi sequence. It concerns a Viterbi decoder.

0003

2. Description of the Related Art A conventional Viterbi decoder repeatedly adds and compares path metrics and selects a trellis as many times as the path memory length using a Viterbi sequence, and outputs decoded data. At this time, the path ends by taking advantage of the fact that the initial state and final state of the convolutional encoder are the same, using the decoded data to infer the starting point of the path, and forcing it to end at that location. .

0004

[Problems to be Solved by the Invention] Conventional Viterbi decoders estimate the end point from the decoded data for the first constraint length bits, so if there is an error during decoding during this time, the second half of the received data, especially the last There is a problem that the decoded data corresponding to the constraint length bits is erroneous.

[0005] Accordingly, an object of the present invention is to provide a Viterbi decoder that can more accurately terminate a path without propagating errors during decoding.

[0006]

[Means for Solving the Problems] The Viterbi decoder of the present invention provides a code sequence in which an information sequence is encoded by a convolutional encoder that takes an arbitrary initial state at the time of data transmission and whose initial state and final state are the same. A Viterbi decoder that receives the received sequence as a received sequence via a transmission path, and maximum likelihood decodes the received sequence using a Viterbi sequence, and calculates a metric for all states assuming that each is a starting point of a path. means for adding and comparing the calculated metrics and selecting a trellis for all the states; means for storing the selected trellis for all the states; and a starting point in the stored trellis. The present invention is characterized by comprising means for preferentially selecting a path whose end point is at the same position.

[0007]

Embodiments Next, embodiments of the present invention will be described with reference to the drawings. Referring to FIG. 1, a Viterbi decoder according to an embodiment of the present invention receives a convolutional code with a code information rate R=1/2 and a constraint length K=3 as a received sequence via a transmission path, and receives this received sequence. Maximum likelihood decoding is performed using the Viterbi sequence. A convolutional encoder that generates such a convolutional code includes two delay elements and can therefore take on 22 = 4 internal states. That is, the convolutional encoder is (0
It can take the following internal states: 0), (01), (10), and (11). Here, (00), (01), (10),
The internal states of and (11) will be referred to as first to fourth states, respectively. When transmitting data, the convolutional encoder to which this embodiment is applied takes one of the first to fourth states as the initial state (starting point), and the initial state (starting point) and final state (end point) are the same. It is.

The Viterbi decoder of this embodiment receives a code sequence in which an information sequence is encoded by the convolutional encoder as a reception sequence via a transmission path. As mentioned above,
Although the initial state of the convolutional encoder is one of the first to fourth states, it should be noted that the Viterbi decoder side does not know which state the convolutional encoder was in the initial state.

The Viterbi decoder includes a data input terminal 1 receiving a received sequence, a branch metric calculation circuit 2, first to fourth processing units 10, 20, 30, and 40, a comparison judgment control circuit 3, Data selector 4 and data output terminal 5
and has. The branch metric calculation circuit 2 calculates the branch metric (inter-symbol distance) for each received code (two code bits) of the received sequence input from the data input terminal 1. The branch metric calculation circuit 2 applies the calculated branch metric to the first to fourth processing units 10 to 40.
Send to. The first to fourth processing units 10 to 40 execute the Viterbi sequence assuming the first to fourth states as the first to fourth starting points, respectively. Since the first to fourth processing units 10 to 40 have similar configurations, the first processing unit 10 will be described in detail below.

The first processing unit 10 includes a first ACS calculation circuit 11, a first path metric memory 12, a first path memory 13, a first end point data latch 14, and a first starting point. It has an end point comparison circuit 15 and a first decoded data buffer 16. The first path metric memory 12 stores the past first path metric calculated by the first ACS calculation circuit 11. 1st AC
The S calculation circuit 11 adds the branch metric calculated by the branch metric calculation circuit 2 and the past first path metric stored in the first path metric memory 12, and calculates the path metric obtained by this addition. Compare and select the smaller path metric and its corresponding path. The selected path metric and path (trellis) are stored in the first path metric memory 12 and the first path memory 13 as a new first path metric and first trellis, respectively. That is, the first ACS calculation circuit 11 assumes that the first state is the first starting point, and adds the first path metric;
Compare and select the first trellis. The first path memory 13 outputs first decoded data corresponding to the first trellis. The first output from the first path memory 13
The decoded data is stored in the first decoded data buffer 16. Further, the first decoded data of the end point is latched into the first end point data latch 14 as the first end point data. The first start point/end point comparison circuit 15 compares the first start point data representing the first start point with the first end point data latched in the first end point data latch 14, and generates a first comparison determination result signal. Output. In this way, the first processing unit 10
outputs the first decoded data and the first comparison determination result signal.

Similarly, the second processing unit 20 outputs the second decoded data and the second comparison determination result signal, and the third processing unit 30 outputs the third decoded data and the third comparison determination result signal. The fourth processing unit 40 outputs the fourth decoded data and the fourth
A comparison judgment result signal is output.

The first to fourth decoded data are supplied to the data selector 4, and the first to fourth comparison determination result signals are supplied to the comparison determination control circuit 3. The comparison/determination control circuit 3 determines in which processing unit the starting point and the ending point match from the first to fourth comparison/judgment result signals, and instructs the processing unit in which the starting point and the ending point match. A selection signal is sent to the data selector 4. The data selector 4 has first to fourth
The decoded data from the processing unit designated by this selection signal is selected from among the decoded data of , and the selected decoded data is output from the data output terminal 5. Furthermore, these first to fourth
If the start point and end point do not match in any of the processing units 10 to 40, the comparison determination control circuit 3 transmits the selection signal to the data selector based on the likelihood of the path metric memory of each processing unit. Send to 4. Therefore, the data selector 4 and the comparison/judgment control circuit 3 preferentially select paths whose starting point and ending point are at the same position among the trellises stored in the path memories 13, 23, 33, and 43.

In the above embodiment, the code information rate R=1/2
An example of maximum likelihood decoding of a convolutional code with a constraint length of K=3 was described in , but the present invention is not limited to this. It can be applied to convolutional codes encoded by a certain convolutional encoder.

[0014]

As explained above, the present invention starts an ACS calculation by assuming the starting point of each path for all states, stores the trellis of all the states, and calculates a path whose starting point and ending point are at the same position. By selecting and terminating the path,
It is possible to eliminate the spread of errors during decoding and suppress the increase in error rate due to path termination.

[Brief explanation of drawings]

FIG. 1 is a block diagram illustrating a Viterbi decoder according to an embodiment of the invention.

[Explanation of symbols]

1 Data input terminal 2 Branch metric calculation circuit 3 Comparison judgment control circuit 4 Data selector 5 Data output terminal 10, 20, 30, 40 processing section

Claims (1)

[Claims] 1. A code sequence in which an information sequence is encoded by a convolutional encoder that takes an arbitrary initial state at the time of data transmission and whose initial state and final state are the same, is received as a received sequence via a transmission path, A Viterbi decoder for maximum likelihood decoding of the received sequence using a Viterbi sequence includes means for calculating a metric for all states assuming each as a starting point of a path; means for adding, comparing, and selecting a trellis;
Viterbi characterized by comprising: means for storing the selected trellis in all the states; and means for preferentially selecting a path whose start point and end point are at the same position among the stored trellises. decoder.