JPS638652B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a Viterbi decoder, and particularly to an optimal path determination circuit for a Viterbi decoder that selects a plurality of candidate patterns by time-division processing.

Conventionally, the Viterbi decoder has been known as the decoder with the best performance for decoding convolutional codes, but on the other hand, it has the disadvantage of increasing the scale of the hardware. For example, if the constraint length of the encoder is K in a commonly used convolutional code with a coding rate of 1/2, the Viterbi decoder always considers ^2K - ¹ candidate patterns and performs path metric analysis by comparing the candidate patterns with the received sequence. Since a new candidate pattern is selected by calculating ^correlation values ^called It becomes necessary. In order to make this circuit smaller, the above
^2K - A method is being considered to reduce the circuit size by replacing parts of ^one circuit that perform the same processing with a single circuit and performing time-sharing processing. In the Viterbi decoder that performs this time-division processing, the determination output is obtained by the optimal path determination circuit. After completing the processing for all candidate patterns, the optimal path determination circuit selects the pattern with the largest corresponding path metric, and outputs the final bit of that pattern as the determination output. However, this method has the disadvantage that the number of operations to be processed within a certain period of time increases because an operation for obtaining a determination output is added in addition to selecting a candidate pattern, or in other words, the signal processing speed is delayed.

An object of the present invention is to eliminate the drawbacks of the optimal path determination circuit of the conventional Viterbi decoder described above, and to obtain an optimal path determination circuit that can obtain a determination output at the same time as processing for all candidate patterns is completed.

According to the present invention, a correlation circuit calculates the correlation between a received signal and a plurality of reception candidate signals, and a plurality of path metric values corresponding to a plurality of reception patterns are updated by time-division processing using the output of the correlation circuit. In the Viterbi decoder, the Viterbi decoder is composed of a metric update circuit that outputs path selection information along with the path selection information, and a path memory that selects a plurality of decoding candidate patterns by time-sharing processing based on the path selection information. A maximum metric memory that stores the maximum value of new metric values obtained at each point in time is compared with the maximum metric memory and the newly obtained metric value, and the newly obtained metric value is larger. A comparison circuit that sends out a maximum value update pulse that updates the contents of the maximum metric when the maximum value update pulse arrives, and a judgment output storage circuit that stores the final bit of the path memory that is sequentially selected when the maximum value update pulse arrives. To provide an optimal path determination circuit for a Viterbi decoder, characterized in that the content of the determination output storage circuit at the time when the pulse memory is updated for all paths is output as a decoding result by the optimal path. Can be done.

For convenience of explanation, the Viterbi decoding method will first be explained in detail, and then the differences between the present invention and conventional circuits will be explained.

FIG. 1 is a block diagram showing an embodiment of a convolutional encoder. The convolutional encoder shown in FIG. 1 constitutes an encoder with a constraint length of 3 and a coding rate of 1/2. Signals of 1 or 0 input from input terminal 100 are stored in registers 1 and 2 sequentially. Addition of the input signal, the contents of register 1, and the contents of register 2 modulo 2 is obtained by exclusive OR 3, and output terminal 1
Output from 01. Also input signal and register 2
The addition modulo 2 of 2 is obtained by exclusive OR 4 and output from the output terminal 102. In this way 1
A bit input signal is converted to 2 bits and transmitted. Since the two output bits are determined by the contents of registers 1 and 2 and the input signal, the state transition diagram of this encoder is as shown in FIG. In Figure 2, the four states (00), (10), (01), and (11) correspond to the internal states of registers 1 and 2, respectively, and the line connecting each state to the next state is the input signal. This means that it will move to a different state depending on the value. Also, the expressions (00), (11), (10), and (01) on the wiring are terminal 10.
1 and the value output from the terminal 102. For example, the initial values of registers 1 and 2 are (0,
0) and a signal "1" is input, the output becomes (1, 1) and the states of registers 1 and 2 change to (1, 0).

In FIG. 2, the change in state when the signals 1, 0, 1 are inputted subsequently is shown by a thick line. In this way, broken lines on the state transition diagram are formed in one-to-one correspondence to each data series. This broken line is called a normal path. The Viterbi decoder calculates the correlation between the transmitted sequence and the received sequence corresponding to each path, determines the path with the maximum correlation, and performs decoding. The correlation between the received sequence and each path is usually called a path metric. The Viterbi decoder stores path metrics corresponding to the four states shown in FIG. 2, and updates the path metrics every time two symbols corresponding to one bit of information are received.

As is clear from FIG. 2, each of the four states produces two branches corresponding to the transmitted signal and returns to one of the four states. From the perspective of the new state, the new state is the result of transmitting different codes from two of the previous states. For example, the state (1,0) is created by adding "1" to the state (0,0), outputting (1,1), and reaching (1,0), and the state (0,1) is "1". 1" may be added to output (0,0) and reach (1,0). The Viterbi decoder corresponding to the k-th data now adds the correlation between the received signal and the reception candidate signal corresponding to each branch to the previous path metric value for these two cases,
The path metric is updated by using the larger one as the new path metric. This path metric update operation will be explained in more detail.

Adjust the path metric corresponding to the k-th data to the current state and write _k M ₀ 0, _k M ₁₀ , _k M ₀₁ , _k
M ₁₁ , and the correlation between the k+1st 2-bit received signal and the 2-bit reception candidate signal corresponding to each branch is _k+1 when the reception candidate signals are i ₁ and i ₂ .
If expressed as R _i1,i2, then the k+1st path metric _k+1 M ₁₀ is _k M ₀₀ + _k+1 R ₁₁ and _k M ₀₁ + _k+1
It will be the larger of R ₀₀ . Therefore _k+1 M ₀₀ , _k+1
Expressing M ₁₀ , _k+1 M ₀₁ , _k+1 M ₁₁ in the formula, _k+1 M ₀₀ = Max( _k M ₀₀ + _k+1 R ₀₀ , _k M ₀₁ + _k+1 R
₁₁ ) _k+1 M ₁₀ = Max ( _k M ₀₀ + _k+1 R ₁₁ , _k M ₀₁ + _k+1 R ₀₀ ) _k+1 M ₀₁ = Max ( _k M ₁₀ + _k+1 R ₁₀ , _k M ₁₁ + _k+1 R ₀₁ ) _k+1 M ₀₁ = Max ( _k M ₁₀ + _k+1 R ₁₀ , _k M ₁₁ + _k+1 R ₀₁ ) _k+1 M ₁₁ = Max ( _k M ₁₀ + _{k+ 1} R ₀₁ , _k M ₁₁ + _k+1 R ₁₀ )
(1) becomes. Since the path taken can be determined by which of the two branches is selected, the Viterbi decoder always stores four paths based on the selection signal. The circuit that stores this path is usually called a path memory.

FIG. 3 is a diagram showing an example of paths stored in the path memory. Only the selected path is shown in FIG. In FIG. 3, if all the paths stored in the path memory at time A are traced backwards, it can be seen that all the portions before time B result in the same path. Therefore, no matter what kind of signal is received in the future, it is impossible for the signal to deviate from the path before time B (thick line portion). This phenomenon is called merging, and when merging occurs, previously received sequences are uniquely determined, so a decision output can be obtained from them. Generally, the length of the path until the margin is achieved varies depending on the transmission path error pattern, and depending on the error pattern, there may be cases where the margin is not infinite. In an actual circuit, it is impossible to store a path of infinite length, so the length of the path must be truncated at some point. In this case 4
There are cases where it is necessary to make a judgment before the book path reaches the margin. In order to reduce judgment errors when the path does not have a margin, a method is used in which the most probable path at the current (judgment time) is determined to be the correct path. Therefore, a normal Viterbi decoder uses a path memory of a fixed length, and outputs the value corresponding to the earliest symbol of the path having the maximum path metric at each determination time.

FIG. 4 is a block diagram showing an example of the configuration of a conventional Viterbi decoder. The Viterbi decoder in Figure 4 is expressed by formula (1)
The path metrics are updated in four ways using time-sharing processing.

Two symbols of received signals are input from input terminals 103 and 104 and input to correlation circuit 5 . On the other hand, the reception candidate signal is read out from the read-only memory ROM 6 based on the address signal generated by the address generation circuit 9, which is generated based on the high-speed clock inputted from the terminal 106. The output of the address/generating circuit 9 corresponds to one of the four states shown in FIG. When the state is determined, a candidate signal corresponding to the state is determined, and the reception candidate signal is output from the ROM 6. Correlation circuit 5 compares the received symbol and the received candidate signal bit by bit, and adds "1" if they match, and subtracts "1" if they do not match. Therefore, the output of the correlation circuit is +2,
It will be either 0 or -2. This corresponds to R _i1,i2 . The metric update circuit uses random access
Consists of memory (RAM), M ₀₀ , M ₁₀ ,
Metric memory 8 that stores M ₀₁ and M ₁₁ and the formula
It is composed of an arithmetic circuit 7 that performs addition and comparison (1). In the metric memory, _k M _j1,j2 are read out from the metric memory 8 based on the address signal generated by the address generation circuit 9, and the correlation circuit 5
Arithmetic circuit 7 performs addition and comparison with _k+1 R _i1,i2 from
It will be held in From equation (1), the write address must be different from the read address. The write address is the write address generator 10
is generated. The read address and write address are different, so if you execute the four expressions in Expression 1 in order from the top, by the time you execute the lower expression, the contents of the metric memory will have already been rewritten. There may be cases where To avoid this, two sets of metric memories are used, at one time reading from the first metric memory and writing to the second metric memory, and then reading from the second metric memory when decoding the next symbol. write to the first metric memory,
Reading and writing are repeated alternately. This memory switching signal is at terminal 10.
It is input from 5. The arithmetic circuit 7 updates the path metrics and at the same time outputs a path selection signal indicating which path is selected. Since the path memory must store as many paths as the number of states, it is composed of RAM whose number of words corresponds to the number of states and whose word length corresponds to the length of the path. Each word of the RAM stores the decoding result corresponding to the path that reaches the state corresponding to that address. The path memory also has two memories that are switched by a memory switch signal. As an example, the contents of the path at time C in FIG. 3 are shown. Now, assume that the path memory length is 4. A path to reach state (0,0) always passes through state (0,0). Therefore, the word corresponding to this path is (0, 0, 0, 0). The path that reaches state (1,0) (the left side corresponds to the old state) changes from state (0,0) to state (1,0) at the end. As a signal, this corresponds to a series of 0's followed by a 1. Therefore, this path is expressed as (0, 0, 0, 1). state (0,
The path to reach 1) is from state (0,0) to state (1,0) and then to state (0,1).
This path becomes (0, 0, 1, 0). Finally, state (1, 1) changes from state (0, 0) to state (1, 1).
0) and reaches the state (1, 1). Therefore, this path becomes (0, 0, 1, 1).

Here, a description will be given of how the path memory is updated based on changes in the path when moving from time C to time A. First, the address generation circuit 9 generates the state (0,0), the address (0,0) corresponding to the state (0,1), and the addresses (0,0) and (0,1) corresponding to the state (0,1). Based on this address, the ROM 6 outputs the reception candidate signals (0, 0) and (1, 1) to the correlation circuit 5, and the correlation circuit 5 calculates _k+1 R ₀₀ and _k+1 R ₁₁ . . On the other hand, in the metric memory 8, addresses (0, 0) and (0,
Based on 1), read _k M ₀₀ and _k M ₀₁ . In the arithmetic circuit, the output of the correlation circuit 5 and the metric memory 8
Calculate the first line of equation (1) from the output of . In Figure 3, _k M ₀₀ + _k+1 R ₀₀ was large, so _k+1 M ₀₀ =
kM ₀₀ + _k+1 R ₀₀ , and "0" indicating that (0,0) has been selected is output as the path selection signal.
In the path memory, addresses (0,0) and (0,1) are stored in an address register 11, and address (0,0) is selected based on a path selection signal. Based on this address, the path (0, 0, 0, 0) corresponding to the state (0, 0) is read out from the RAM 12, shifted one bit to the left in the shift register 13, and a new bit is generated at the far right. circuit 14
A new bit generated by is input.
Since _k+1 M ₀₀ has been found, _k+1 M ₀₀ is written to the write address (0,0) determined by the write address generator 10, and the RAM 1 of the path memory
2 also to address (0,0) (0,0,0,0)
is written. If we execute equation (1) in order from the top, the write addresses will be (0,0), (1,0),
It changes sequentially to (0, 1) and (1, 1). in the same way
_k M ₀₀ + _k+1 R ₁₁ is written to _k +1 M ₁₀ and RAM1
Address (1,0) of 2 is address (0,0)
The contents (0, 0, 0, 0) are shifted to the left by 1 bit and "1" is inserted to the right end, resulting in (0, 0, 0, 1). Also, _k M ₁₀ + _k+1 R ₁₀ is written to _k+1 M ₀₁ ,
Address (0, 1) of RAM12 is obtained by shifting the contents (0, 0, 0, 1) of address (1, 0) to the left by 1 bit and inserting "0" to the right end (0, 0,
0,1). Finally _k+1 M ₁₁ has _k M ₁₁ + _k+1
R ₁₀ is written, RAM12 address (1,1)
is the content (0,0,1,1,) of address (1,1)
Shift 1 bit to the left and insert "1" to the right end, resulting in (0, 1, 1, 1). In this embodiment, the latest bit to be entered at the right end is the left bit of the write address.

In the embodiment shown in FIG. 4, the leftmost bit shifted by the shift register 13 is taken as the decoding result. This is good if there is a margin within the length of the path memory, as in the example of FIG. 3, but if there is no margin, the determination result will not be determined and correct decoding will not be possible. In order to reduce this error, there is a method of storing the write address of the largest metric among the newly written metrics and using the leftmost bit of the address of this largest metric as the judgment output. However, when this method is used, the address must be set and read again after the four calculations corresponding to equation (1) are completed, which increases the number of operations to be executed within a symbol period and increases the speed of the circuit. required. In other words, the maximum bit rate that can be applied to the same circuit becomes smaller. The present invention avoids this and implements a circuit that reads from the path of the address with the maximum metric.

Next, the present invention will be explained in detail with reference to the drawings.

FIG. 5 is a block diagram showing one embodiment of the present invention. The updated metric value obtained as the output of the metric update circuit shown in FIG. When the calculation based on equation (1) begins, the maximum metric memory 21 is first initialized by a mode switching signal from the input terminal 105. When a new metric value is input from the input terminal 110, the comparator 20 compares the value in the maximum metric memory with the new metric value, and the comparator 20 returns the maximum value only if the new metric value is larger. A write pulse, which is an update pulse, is output to the maximum metric memory 21, and the input from the terminal 110 is written to the maximum metric memory. In this way, the maximum value of the metric memory is stored in the maximum metric when the metric update circuit completes the calculation of equation (1). The maximum value update pulse of the output of the comparator 20 is simultaneously supplied to the judgment output storage circuit 22 as a latch signal. Input terminal 111 is connected to terminal 107 in FIG. 4, and receives the final output of shift register 13 in FIG. The judgment output storage circuit 22 is realized by a latch circuit, and stores the value from the terminal 111 when the maximum value update pulse arrives. In this way, the contents of the judgment output storage circuit when all the calculations in equation (1) are completed will be the last bit of the path memory when the maximum value update pulse was last output, that is, the path path when the metric is maximum. Since the last bit of the memory is stored, a determination result with a small error rate can be obtained even when paths are not merged.

In this way, the judgment output can be obtained at the same time as the calculation of equation (1) is completed, and there is no need to particularly increase the operating speed of the circuit.

As described above, according to the present invention, there is provided a correlation circuit that calculates the correlation between a received signal and a plurality of reception candidate signals, and a plurality of path metrics corresponding to a plurality of reception patterns by time-division processing using the output of the correlation circuit. A Viterbi decoder consists of a metric update circuit that updates values and outputs path selection information, and a path memory that selects multiple decoding candidate patterns by time-sharing processing based on the path selection information. Even when merging is not performed, it is possible to obtain an optimal path determination circuit that has a small error rate and has a margin for operating speed.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing an example of a convolutional encoder, FIG. 2 is a state transition diagram showing the structure of a convolutional code, and FIG. 3 is a diagram showing the internal state of a Viterbi decoder.
FIG. 4 is a block diagram showing an embodiment of a conventional Viterbi decoder. FIG. 5 is a block diagram showing one embodiment of the present invention, in which reference numerals 20, 21, and 22 indicate a comparison circuit, a maximum metric memory, and a judgment output storage circuit, respectively.

Claims (1)

[Claims] 1 A correlation circuit that calculates the correlation between a received signal and a plurality of reception candidate signals, and a correlation circuit that uses the output of the correlation circuit to update a plurality of path metric values corresponding to a plurality of reception patterns through time-division processing, and also to update path selection information. In the Viterbi decoder, which is composed of a metric update circuit that outputs a metric update circuit, and a path memory that selects a plurality of decoding candidate patterns by time-sharing processing based on the path selection information, the metric update circuit sequentially obtains A maximum metric memory that stores the maximum value of new metric values at each point in time, and compares the maximum metric memory with the newly obtained metric value, and if the newly obtained metric value is larger, the maximum metric memory is stored. It consists of a comparison circuit that sends out a maximum value update pulse that updates the content of the metric, and a judgment output storage circuit that stores the final bit of the path memory that is sequentially selected when the maximum value update pulse arrives, and An optimal path determination circuit for a Viterbi decoder, characterized in that the contents of the determination output storage circuit at the time when the memory is updated for all paths are output as a decoding result by the optimal path.