JPS60176333A - Viterbi decoding circuit - Google Patents

Abstract

PURPOSE:To reduce a variation range of a path metric, and to make a hardware small in size by utilizing maximum likelihood path metric in that time for both determining a decoding output in a viterbi decoding method, and normalizing the path metric. CONSTITUTION:A branch metric (b) is obtained by the first means 10 from a receiving signal (a), the branch metric (b) and a normalized path metric (c) are inputted to the second means 20, a path metric (d), a surviving path (e) and a maximum likelihood path metric (f) are derived and stored by an ACS circuit 26, a surviving path circuit 28, a maximum likelihood estimating circuit 29, and a path metric storing circuit 27, and a decoding output signal (g) whose error has been corrected is obtained. Subsequently, by the path metric (d) and the maximum likelihood path metric (f) inputted by the third means 30, the normalized path metric (c) is obtained and sent out to the means 20.

Description

[Detailed Description of the Invention] [Technical Field of the Invention] The present invention relates to a Viterbi decoding circuit that can perform strong error correction for random errors, and particularly relates to a Viterbi decoding circuit that can perform strong error correction for random errors, and in particular,
The present invention relates to a Viterbi decoding circuit that uses an IJ book to determine a decoded output.

[Technical background of the invention and its problems]

The Viterbi decoding method is known as a powerful error correction decoding method for convolutional codes, and its application to satellite communication systems is being considered. However, there are some problems when implementing this algorithm in hardware, one of which is the increase in path metrics stored in the decoder over time. Therefore, in order to put this into practical use, processing that suppresses the increase in path metrics is necessary.

(i.e. pasta) There is a problem with IJ book normalization.

In the past, this problem had to be solved.

Before elucidating these problems in detail, some key points about the Viterbi decoding method will be described for the sake of understanding. This decoding method is described, for example, in "Coding Theory J" by Miyayo et al. (published by Shokodo in 1972), p. 368 et seq.

The code targeted by the Viterbi decoding method is called a convolutional code, and when the coding rate, constraint length, and code generation polynomial are specified, the code structure is uniquely determined, and there are several methods to represent the structure. Although it is possible, in order to visualize the algorithm, a grid diagram in which the internal state is drawn out at each time as shown in FIG. 1 is optimal. Figure 1 shows a coding rate of 1/2. An example with a constraint length of 3 is shown, but as can be seen from the figure, when a new information bit is input at time fk+, two code symbols (this pair of two bits is called a branch) are The output is 2 times (
k+1).

What is surrounded by a circle indicates an internal state, but when we focus on one state at a certain time, as can be seen from the grid diagram, we start from a known initial state,
Although there are generally many paths leading to the state of interest, only one path is determined that has the minimum distance from the actual received signal sequence (this is called the IJ book).

This is called the survival path for the state of interest.

At this time, the Viterbi algorithm sequentially determines one surviving path and its associated path metric for each time and each internal state of the encoder at that time.

Therefore, at each time, as many surviving paths as the number of internal states and the same number of path metrics corresponding to each path are stored, but among these, the surviving path with the minimum path metric ( That is,
The received data sequence I (the closest path in a probabilistic sense) is called the maximum likelihood path at that time in the sense that it is the most likely transmission data, and is used to determine the decoding output.

However, the way the path metric is determined is arbitrary, and it is possible to associate a path closer to the received data with a larger path metric.

In such a case, the surviving path with the largest path metric becomes the most likely path at that time.

Therefore, in order to unify the two, the maximum likelihood path determined regardless of the definition of the path metric will be considered as the standard, and will be referred to here as the IJ Cook maximum likelihood path metric.

Now, it is known that the above-mentioned Viterbi decoding method can dramatically improve bit error burden especially when used in combination with soft-decision demodulation, and is actually used in this manner.

In this case, the distance between the soft decision data and the transmitted signal is defined as the symbol metric, and the symbol metric calculated for the soft decision data at each time is defined as the branch metric (the sum of the symbol metrics for the branch is the branch metric). The path metric is the sum of all calls up to that time.

Therefore, if we choose the symbolic metric to be non-negative,
Path metrics are time,! :(!: Both increase monotonically and gradually become excessive. Therefore, when implementing the Viterbi algorithm in hardware, some kind of normalization is required to prevent each path metric from exceeding a finite capacity. It was necessary to do it.

As a conventional solution to such a problem, a method is known in which a predetermined constant is periodically subtracted from each pasta l-IJ cook. However, since this is a correction using a predetermined constant, it is necessary to perform fine-grained normalization and to set the pasta l-IJ cook variation range to be considerably large. That is, there is a drawback that the hardware becomes enormous in order to allocate sufficiently long bits for storing and calculating path metrics.

Additionally, it may be possible to incorporate a protection device in case the increase in path metrics exceeds one memory capacity, but such considerations are cumbersome and the installation of a protection device also has the disadvantage of increasing the size of the device. was there.

[Purpose of the invention]

This invention is intended to eliminate the above-mentioned drawbacks, and allows fine-grained normalization to be performed according to the situation of a single communication line without installing any special protection equipment, thereby reducing the range of changes in path metrics. It is an object of the present invention to provide a Viterbi decoding circuit that can reduce the number of hardware required and downsize the hardware.

[Summary of the invention]

The present invention uses a Viterbi decoding circuit as a first means for obtaining a branch metric by inputting a received signal.

Using this branch metric and normalized path metric as input, creating a path metric, a surviving path, and a maximum likelihood path metric and storing them, outputting the IJ cook and the maximum likelihood path metric, and outputting the maximum likelihood path metric, and outputting the maximum likelihood path metric. a second means for obtaining an error-corrected decoded output signal using an operation that calculates the maximum likelihood; and a normalizer for normalizing the path metric based on the maximum likelihood path metric and supplying the normalized signal to the second means. and a third means for obtaining an IJ cook.

In particular, this invention uses the maximum likelihood pulse measurement at that time) I
J. Cook, Viterbi decoding method is characterized by its use in both determining the decoding output and normalizing the path metric.

〔Effect of the invention〕

In normalizing the path metric, this invention utilizes the maximum likelihood path metric originally obtained for determining the decoding output.

To normalize the path metric, if we take the trouble to calculate the maximum likelihood path metric, the circuit configuration for path metric normalization, and therefore the overall circuit configuration, would become complicated and large.However, in this invention, the decoded output Since the maximum likelihood path metric obtained for determination is used, it has the advantage of minimizing the increase in circuit scale required for normalization.

Further? In this normalization method for FiAl.

Since detailed normalization is performed according to the communication line situation, the maximum value of IJ sock after normalization will never exceed a certain limit value, regardless of the value of S of the received signal. Therefore, not only the memory capacity can be reduced, but also the number of bits required for path metric calculation can be reduced, making it possible to significantly reduce the amount of hardware compared to the conventional case.

[Embodiments of the invention]

An embodiment of the present invention will be described below with reference to one drawing.

In FIG. 2, 1 is the input terminal for the received signal, and 10
is the first means for obtaining a branch I-IJ socket using this received signal as an input signal. 20 is the second means,
A branch metric is input from the first means 10 via a terminal 21, and the normalization path 7 is input via a terminal 22.
l-IJ sock is input, these branch metrics and the normalized path metric are input, the path metric, the surviving path, and the maximum likelihood path metric are stored together, and the path metric is output from the terminal 23. terminal 24
The maximum likelihood path metric is output from the terminal 2, and a decoded output signal subjected to error correction is output from the terminal 2. 30 is a path metric inputted from the second means 20 via the terminal 23 and a maximum likelihood path inputted via the terminal 24) IJ Sock et al. normalized path 7l-IJ
This is a third means for supplying the second means 20 via the terminal 22.

For reference, the received signal in the figure is a, the branch metric is C, the normalized path metric is C, the path metric is d, the surviving path is e, the maximum likelihood path metric is f, and the decoded output signal after error correction is applied. are respectively indicated by the symbol g.

Next, the configuration of the second means 20 shown within the dashed line frame will be explained in detail. 25 is Pasta) IJ Cook path, AC8 circuit 26 and path metric storage circuit 27
It is made up of. The AC8 circuit 26 receives the branch metric from the terminal 21 and the normalized path metric from the terminal 22.

Pasta) It is obtained by adding, comparing, and selecting the IJ sock and survival path designation signals (in addition,
A indicates addition, C indicates attendance, and S indicates selection. ). Further, the path metric storage circuit 27 is for storing the path metric output from the AC8 circuit 26. This path metric is read out and supplied to the third means 30 from the terminal 23 as described above.

Further, from the AC8 circuit 26 of the path metric circuit 25, the surviving path designation signal (indicated by h in the figure for reference), which is the other output, is input to the surviving path circuit 28, and this circuit 28 selects the surviving path. As well as updating and storing, the surviving path is output to the lζ maximum likelihood estimation circuit 29.

The maximum likelihood estimation circuit 29 obtains a maximum likelihood path metric and a maximum likelihood path designation signal from the path metric input from the bus metric calculation circuit 25, and further calculates the maximum likelihood path designation signal No. 49 I.
Based on this, an error-corrected decoded output is obtained from the surviving path input from the surviving path circuit $28. maximum likelihood pasta) via the IJ sock terminal 24 to the third means 3
0, while the decoded output signal is output via terminal 2, respectively.

Now, as mentioned above, the Viterbi algorithm sequentially determines one surviving path and the path metric associated with that path for each time and each internal state of the encoder at that time. + to time (kl
It is sufficient to pay attention to how operations including normalization are executed in the process of moving to t).

Therefore, it is assumed that all calculations up to the current time (kl) have been completed. That is, the path metric storage circuit 27 and the maximum likelihood estimation circuit 291 in the second means 20 are It is assumed that each path metric at time (k) and its maximum likelihood value, the maximum likelihood path metric, are stored.

Note that in this state, Pasta) IJ sock has not yet been normalized. Here, the procedure for calculating the updated bus metric and updated surviving paths for one state (Xk+1) at one time (kl1) will be explained assuming that a new received signal is input from terminal l.

The path metric of time (kl) related to the focused state CXk+]) is called from the path metric storage circuit 27, and at the same time, the maximum likelihood path metric of time (10) is output from the maximum likelihood estimation circuit 29, and both are read from the third means 30. be led to.

In the third means, the maximum likelihood path 7) IJ sock normalization is executed and the normalized path metric at time 1 (k) is input to the AC8 circuit 26.

For example, at a certain time (kl
The path metrics corresponding to the four states in 's, 2. a, 4, the maximum likelihood path metric is 2 if the minimum value is considered optimal.

Therefore, this value 2 is subtracted from each path metric, and the normalized path metric becomes 3, 0, 1, 2 c:. In this way, by using the maximum likelihood path metric, fine-grained normalization is performed according to the situation of the 0 communication line.

On the other hand, when the received signal is input to the first means 10 from the terminal 1, the branch code corresponding to the transition from time fk) to time (kl1) [this is the state of interest (Xk-H
). A branch metric is output corresponding to the above-mentioned normalized path metric, and is input to the AC8 circuit 26 in a form corresponding to the normalized path metric described above.

The AC8 circuit 26 uses these two values to perform additive comparison and selection operations, and the updated path metrics for state (Xk+1) are led to the path metric storage circuit 27 and stored. On the other hand, the updated surviving path is stored in the surviving path circuit 28 in accordance with the surviving path designation signal output from the AC8 circuit 26.

This basic operation is repeated for the number of states, thereby updating the update buster for all states at time (kl1)
IJ socket and update survival path are respectively busters)
It is stored in the IJ hook storage circuit 27 and the surviving path circuit 28.

On the other hand, in the process of repeating this algorithm, the updated path metric output from the AC8 circuit 26 is also input to the maximum likelihood estimation circuit 29, and when the calculation of path metrics for all states at one time (kl1) is completed - The maximum likelihood value is saved.

This maximum likelihood path metric is used for past (IJ) sock normalization in the next decoding step.

When the maximum likelihood path metric is calculated in the maximum likelihood estimation circuit 29-, a maximum likelihood path designation signal is output, and based on this maximum likelihood path designation signal, one of the surviving paths input from the survival path circuit 28 is selected. The most likely path is selected, and the oldest information on that path is output from terminal 2 as decoded data, as will be detailed later.

The above one-cycle calculation is repeatedly executed every time a new received signal is input from terminal 1.

The present invention is characterized in that the maximum likelihood path metric at that time is used for both determining the decoding output and normalizing the IJ Sock. By using it for normalization, the increase in circuit scale for that purpose is suppressed.

It will be explained as follows that the normalization means is extremely suitable for the Viterbi decoding algorithm itself.

A notable feature of the Viterbi algorithm is that as the algorithm progresses, the sufficiently past portions of the surviving paths stored for each internal state gradually converge into one common path.

Therefore, in actual hardware, it is not necessary to store surviving paths for an infinite length; it is usually only necessary to store them for a limited length.

In this case, the oldest bit common to each surviving path can be directly used as the decoded output.

However, due to the memory length of the surviving paths, it is assumed that the oldest bits of these paths may not be common, and in such cases, a new most likely path is determined from among the surviving paths at that time. The oldest bit of the maximum likelihood path can be selected as the decoding output. This invention is based on the algorithm itself in the sense that it effectively utilizes the calculated maximum likelihood path metric in determining the decoding output. This makes it possible to reduce the unnecessary increase in hardware required for normalization.

Furthermore, the use of P-sintering in this invention not only reduces the memory capacity for storing path metrics, but also reduces the number of bits required for path metric calculations, which requires less hardware than conventional methods. This enables a significant reduction in wear.

FIG. 3 shows an example of the distribution state of the maximum value of the path metric after normalization when normalization is performed according to the present invention.
This is shown as the S/N relationship of the received signal. In the same figure, the curve ■ indicates the average value of the maximum values of the normalized path metrics, and the curve ■ indicates the standard deviation σ of the maximum values of the normalized path metrics.

According to the curve ■, the maximum IJ hook value (normalized pasta) is independent of the S/N value of the received signal.

It can be known that the value does not exceed a certain value (8 in this case). Is this upper limit unique depending on the structure of the target convolutional code? This means that when designing a decoder, it is possible to specify in advance the memory capacity for storing path metrics and the number of operation bits. Moreover, normalized pasta)
Due to the fact that the IJ hook maximum value does not exceed a certain limit value in any case, there is no need to consider installing a protection device in advance in case the path metric exceeds the memory capacity.

Therefore, by performing normalization according to this invention,
It becomes possible to suppress the dynamic range of the path metric to a necessary and sufficient minimum value, and it is possible to simplify the hardware.

By the way, in Figure 3, the maximum value of the normalized path metric is small where the S/H is poor, that is, on the left end, and the maximum value of the normalized path metric is large and large where the S/N is good, that is, on the right end. A phenomenon is occurring. When there is a lot of noise, this increases as it approaches the pasta l-IJ hook pressure of the surviving path corresponding to each state,
Therefore, by normalization, each path metric becomes smaller as a whole, and on the other hand, when the noise is small, the path metric of the maximum likelihood path and other surviving paths (IJ hooks) becomes distinctly separated, and the simultaneous maximum likelihood path This is because the maximum path metric after normalization becomes larger as the metric becomes smaller.

Next, FIG. 4 shows another embodiment of the present invention.

This embodiment, like the embodiment shown in Figure @2, includes a first means 10 for outputting branch metrics, and an AC8 circuit 26.
and pasta) A path metric circuit 25 consisting of an IJ hook storage circuit 27. Survival path circuit 28. The second means 20 includes a maximum likelihood estimation circuit 29, and the third means 30 further performs normalization.

However, compared to the embodiment shown in FIG. 2, the position where normalization is performed and the input signal to the maximum likelihood estimation circuit 29 are different. In other words, in the configuration shown in FIG. 4, the output of the AC8 circuit 26 is supplied to the third means 3o and to the return line 29 of the means 1n of the third means 3o. When this happens, both b and b are input to the path metric storage circuit 27, and the other connections are the same as in the case of FIG.

In FIG. 4, when a received signal is input through terminal 1, a branch metric is generated by first means 10, which becomes one input signal of AC8 circuit 26 through terminal 21. In addition, the path metric at the previous time output from the path metric storage circuit 27 is sent to the S circuit 26.
and the new path metric becomes the other input signal of AC
The data is calculated and updated by the eight circuit 26 and supplied to the third means 30 via the terminal 23.

The maximum likelihood path metric at the previous time stored in the maximum likelihood estimation circuit 29 is input to the third means 30 via the terminal 24, and the path metric normalized in the third means 30 is input to the terminal 22. The data is stored in the path metric storage circuit 27 via the path metric storage circuit 27. At the same time.

This normalized path metric is input to the maximum likelihood estimation circuit 291, which generates a maximum likelihood path designation signal corresponding to the first time t. is memorized.

A surviving path designation signal, which is another output, is input from the AC8 circuit 26 to the surviving path circuit 28#, and the surviving paths are sequentially designated and updated. On the other hand, this surviving path is input to the maximum likelihood estimation circuit 29, and the maximum likelihood path is selected based on the maximum likelihood path designation signal generated within this circuit 29 as described above. Output from terminal 2. In this case as well, various effects similar to those of the embodiment shown in FIG. 2 (1) can be obtained.

In the circuit configuration as shown in FIG. 2 or 4, the maximum likelihood path metric and the maximum likelihood survival path can be determined extremely efficiently by operating the maximum likelihood estimation circuit 29 as follows. Explain what you can do at each station using Figure 5.

That is, first, focusing on the fact that the path metric for each internal state is calculated in a time-sharing manner in the AC8 circuit 26, the maximum likelihood estimation circuit 29 is operated in synchronization with the path metric circuit 25 and the surviving path circuit 28, and each internal In synchronization with the input of the path metric for a state from the path metric circuit 25 to the maximum likelihood estimation circuit 29, the surviving paths for the same state are input from the surviving path circuit 28 to the maximum likelihood estimation circuit 29.

Next, in the maximum likelihood estimation circuit 29, the path metric input from the path metric circuit 25 and the contents of the maximum likelihood value buffer 103 are sequentially compared and determined in the comparison circuit 101, and when a path metric with a more maximum likelihood is input. only,]! S
The path metrics are exchanged via the selection circuit 102.

Also, at this time, based on the maximum likelihood path designation signal generated by the comparator circuit 101, between the surviving path similarly input from the surviving path circuit 28 and the maximum likelihood surviving path stored in the maximum likelihood path buffer 106. 1 selection circuit 1
When the surviving paths are replaced through 05 and the path metric calculation for all states at the second time point is completed, the maximum likelihood path metric and the maximum likelihood surviving path are stored in the maximum likelihood value memory 104 and the maximum likelihood path memory, respectively. 107.

This invention is not limited to the above embodiments, and can be implemented with various modifications without changing the gist.

For example, the internal configuration of the second means can be variously changed depending on the bit rate and parameters in Tobi decoding, that is, the coding rate, constraint length, or number of soft decision bits of the target convolutional code.

Also, in the embodiments of FIGS. 2 and 4.

Although the AC8 circuit 26 is constructed of one circuit and operates serially and time-divisionally, it is also possible to configure the present invention by providing a plurality of circuits. for example,
It is also possible to separately install the AC8 circuits corresponding to the number of states, and also separately incorporate the IJ cook storage circuit 27 (the same number of buses corresponding to the number of AC8 circuits corresponds to the number of states). It can be adapted to the case. in this case.

It is also appropriate that a plurality of third means 30 for normalization be separated and installed in a distributed manner corresponding to the above configuration.

The present invention is capable of taking various modified configurations in addition to the above, within the scope of the main idea of performing normalization using the maximum likelihood path metric calculated when specifying the maximum likelihood path used to determine the decoding output. I can do it.

[Brief explanation of the drawing]

Fig. 1 is a specific example of a grid diagram representing the structure of a convolutional code, Fig. 2 is a circuit configuration diagram of an embodiment of the present invention, and Fig. 3 is a diagram showing the maximum value of the path metric after normalization in the present invention. A characteristic diagram showing the distribution state as a function of S of the received signal, FIG. 4 is a circuit configuration diagram showing another embodiment of the present invention,
FIG. 5 is a circuit configuration diagram embodying a maximum likelihood estimation circuit that can efficiently determine the maximum likelihood path (IJ Cook) and the maximum likelihood survival path. 1... Input terminal 2... Output terminal 10... First means 2 for outputting branch metrics
0--Second means 21-24 for outputting path metric, maximum likelihood path metric, and decoded output signal...Terminal 25...Nox Flick circuit 26...AC8 circuit 27...Path metric Memory circuit 28... Survival path circuit 29... Maximum likelihood estimation circuit 30... Third means for normalizing pasta and tricks 101... Comparison circuit 102... Selection circuit 103.
...Maximum likelihood value buffer 104...Maximum likelihood value memo 1-10
5...Selection circuit 106...Maximum likelihood number/'e,
) Fa 107... Maximum likelihood path memory Figure 1 t (mouth 4 亥9>, 0 1 ? 3 4 5 Figure 2 0 Figure 3 Physiological Rinpot Dayo'N (dB) Key 4 Joy 1 5th 1; Ku1

Claims (6)

[Claims] (1) A first means for obtaining a branch metric by receiving a received signal as an input, and storing the branch metric and a normalized path metric by inputting a path metric, a survival path, and a maximum likelihood path metric, and storing the above-mentioned path metric. and the maximum likelihood pasta)-I
A second method that outputs a J-hook and obtains an error-corrected decoded output signal using the calculation of the maximum likelihood path metric.
means for normalizing the path metric based on the maximum likelihood path metric and supplying it to the second means; and third means for obtaining an IJ hook. Viterbi decoding circuit. (2) The second means inputs the branch metric right and the normalized path metric and outputs the path metric and the surviving path designation signal. A surviving path circuit that stores and outputs a maximum likelihood path metric and a maximum likelihood path designation signal from the path metric or the normalized path metric, and performs error correction based on the survival path and the maximum likelihood path designation signal. 2. The Viterbi decoding circuit according to claim 1, further comprising: a maximum likelihood estimation circuit for obtaining a decoded output signal subjected to (3) The maximum likelihood estimation circuit in the second means operates in synchronization with the path metric circuit and the surviving path circuit, and the path metric for each internal state is input from the path metric circuit to the maximum likelihood estimation circuit. In synchronization with this, the surviving paths for the same internal state are input from the remaining path circuit to the maximum likelihood estimation circuit, and at this time, the maximum likelihood estimation circuit replaces the path metrics only when a path metric with a higher maximum likelihood is input. Do this. Also, based on the maximum likelihood path designation signal generated earlier, the surviving paths input from the surviving path circuit are sequentially selected and the surviving paths are replaced, and the path metric calculation for all states at the first time point has been completed. 3. The Viterbi decoding circuit of claim 2, wherein the Viterbi decoding circuit is configured to determine a maximum likelihood path metric and a maximum likelihood survival path. (4) The path metric circuit adds the branch metric and normalized path metric as input. The AC8 circuit outputs a path metric and a surviving path designation signal by a comparison 2 selection operation, and a path metric storage circuit for storing the path metric output from the 〇S circuit. A Viterbi decoding circuit according to claim 2. (5) The path metric circuit stores the normalized path metric, and the normalized path metric and branch metric output from this storage circuit. Claim 2, characterized in that it is equipped with an AC8 circuit that outputs a survival path designation signal.
The Viterbi decoding circuit described in section. (6) Claim 4, characterized in that a plurality of A(9 circuits, a path metric storage circuit, and a plurality of third means are provided, each corresponding to the number of internal states of the encoder) Or the Viterbi decoding circuit according to item 1.