JPH06284018A - Viterbi decoding method and error correcting and decoding device - Google Patents

Abstract

(57) [Summary] [Purpose] By saving multiple survivor paths with high likelihood for each state and performing traceback multiple times,
Increase the chance of being decoded correctly. In an error correction coding apparatus on the transmission side, an error detection coding circuit 3 adds an error detection code, and an error correction coding circuit 4 performs convolutional coding and transmits. In the error correction decoding device on the receiving side, the metric (likelihood) of the path is calculated by the metric calculation circuit 5, and the path having the highest likelihood and the likelihood difference with the path are equal to or less than a preset threshold value. The path is stored in the path storage circuit 6, is decoded by the traceback circuit 7, and the decoding candidate is stored in the candidate storage circuit 9 except for the candidate in which the error is detected by the error detection circuit 8.
The decoded data determination circuit 10 determines the most powerful candidate and determines the decoded data.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a Viterbi decoding method which is a kind of error correction code decoding used for data transmission in digital automobiles, mobile phones and the like, and an error correction decoding apparatus using the method.

[0002]

2. Description of the Related Art Viterbi decoding is one of decoding methods for convolutional codes. Hereinafter, this Viterbi decoding is performed with the constraint length K generated by the conventional convolutional encoder as shown in FIG.
= 3 and the coding rate R = 1/2, the convolutional code C will be described as an example.

According to the states of the shift registers F ₀ and F ₁ shown in FIG. 3, the state S of the encoder is the following four states: S ₀ = (0,0), S ₁ = (1,0), S ₂ = (0,
1), S ₃ = (1, 1) ... (1).

The trellis diagram is a representation of the state in which the encoder that was initially in S ₀ changes every moment, that is, every time an information signal is input, the state transits. The trellis diagram of the code C is shown in FIG. It is assumed here that the input information signal sequence length is J−K + 1 and K−1 0s follow.

The branch-like portion of the trellis diagram is a branch, 2
A chain of more than one branch is called a partial path. In the trellis diagram shown in FIG. 4, the dotted line branch indicates that the input signal is 0, and the solid line indicates that the input signal is 1. Furthermore, the outputs a, b, c, d of the encoder are shown in the branch part. However, a = (0,0), b = (1,0), c = (0,1), d
= (1,1) ... (2), the left component is C _i ⁽¹⁾ , and the right component is C _i
^{(2) It} shall be represented.

[0006] The time t = state at t ₀ S ₀ (t =
t ₀₎ from t = state at _{t j S 0 (t = t} j) a series of branches that path to the. This path is for the codeword of the convolutional code C. When it is necessary to avoid confusion with a partial path, it will be called a codeword path.

FIG. 5 is a part of the trellis diagram of the code C.
Indicates a path. The subset of codewords that correspond to this partial path
For convenience,_S ¹= (00 00 11), C_S ²= (11 10
 00) (3). Pass C for Viterbi decoding_S ¹And pass C_S ²Likelihood of
And compare, for example, C_S ¹The likelihood of is path C_S ²Likelihood of
C if not lower than_S ²Reject. This allows
Path C_S ²All codeword paths that include as a partial path
This means that the transmission codeword candidate was rejected. C_S ¹of
The partial path that remains without being rejected is called the surviving path.
U

It can be seen from the trellis diagram of FIG. 4 that each state has two partial paths having the same branch state as shown in FIG. Also, in the steady state excluding the states at both ends of the codeword, it is always 2 ^{K-1 at} each time.
It can be seen that there are individual survival paths. Time t
_{After J-K + 2,} the surviving paths decrease by 1/2 at time t
_{At j} , there is only one survivor pass. Then, this surviving path is decoded as a transmission codeword by traceback.

[0009]

However, in the above-mentioned conventional method, only one partial path is set as the surviving path and the other is rejected even when there is no difference in likelihood.
There is a problem that the surviving codeword path may not be the correct decoded word. For example, in the case of the codeword C, since there are only two partial paths that rejoin each state at each time, there is a high probability that there is a difference in likelihood, but in the case of a code in which there are more partial paths that rejoin, The probability that there is no difference in likelihood also increases.

SUMMARY OF THE INVENTION The present invention is intended to solve such conventional problems, and an object thereof is to provide a Viterbi decoding method and an error correction decoding apparatus having high error correction decoding capability.

[0011]

In order to achieve the above object, the present invention uses an ACS (Add Compare Select) operation to select a path having the highest likelihood when selecting a surviving path at each state at each time. Rather than selecting and storing only one, the path with the highest likelihood and the path whose likelihood difference with that path is less than or equal to a preset threshold value are also stored and traceback is performed multiple times. , The influential candidate is selected from a plurality of decoding candidates obtained as a result and is used as the decoded data.

[0012]

Therefore, according to the present invention, when there is no difference in likelihood or there is a small difference, it is possible to perform more excellent error correction code decoding by leaving the path that was conventionally rejected.

[0013]

1 shows an error correction coding / decoding apparatus according to an embodiment of the present invention. In FIG. 1, 1 is an error correction coding apparatus and 2 is an error correction decoding apparatus. 3 is an error detection coding circuit, 4 is an error correction coding circuit, 5 is a metric calculation circuit, 6 is a path storage circuit, 7 is a traceback circuit, 8 is an error detection circuit, 9 is a decoding candidate storage circuit, and 10 is decoding. It is a data decision circuit.

First, in the error correction coding apparatus 1, in the error detection coding circuit 3, a CRC (Cycli) is added to the information data.
c) An error detection code such as a Redundancy Check code is added. Next, the error correction coding circuit 4 performs convolutional coding and transmits.

In the error correction decoding device 2, the metric (likelihood) of each partial path is calculated from the received data string in the metric calculation circuit 5. Next, in the path storage circuit 6, the metrics of a plurality of paths transiting to each state at each time are compared, and the difference between the metric having the highest metric and the metric is higher than a preset threshold value. Select and store a small path.

As a result, according to the present invention, the number of surviving paths is not limited to one as in the conventional Viterbi decoding method, and generally a plurality of paths survive as shown in FIG. In this case, S ₀ - (A) -S ₁ - (i) -S ₀ - (d) -S ₀ - (mosquito) -S ₁ - (Ke) -S ₀ S ₀ - (A) -S ₁ - (b) -S ₀ - (d) -S ₀ - (key) -S ₁ - (Ke) -S ₀ S ₀ - (A) -S ₁ - (i) -S ₀ - (O) -S ₁ - (viii) -S ₁ - (Ke) -S ₀ S ₀ - (A) -S ₁ - (c) -S ₀ - (d) -S ₀ - (mosquito) -S ₁ - (Ke) -S ₀ S _0- (A) -S _1- (C) -S _0- (D) -S _0- (K) -S _1- (K) -S ₀ S _0- (A) -S _1- (C ) -S _0- (e) -S _1- (h) -S _1- (ke) -S ₀ ... (4) 6 paths survive.

Then, in the traceback circuit 7,
These multiple paths are traced back to obtain multiple decoding candidates. Next, the error detection circuit 8 detects the error of the decoding candidate based on the error correction code added by the error detection coding circuit 3, and stores the candidate in which no error is detected in the decoding candidate storage circuit 9. Then, the decoded data determination circuit 10 selects the most powerful candidate and sets it as the decoded data.

FIG. 2 shows the configuration of the decoded data determination circuit 10. (A) is a likelihood comparison type, and (b) is a re-encoded signal comparison type.

In FIG. 2A, in the decoded data determination circuit 10A, the candidate comparison / selection circuit 11 selects the candidate with the highest likelihood from the decoding candidates stored in the decoding candidate storage circuit 9 in FIG. To be decrypted data.

In FIG. 2B, in the decoded data decision circuit 10B, the decoding candidates stored in the decoding candidate storage circuit 9 of FIG. 1 are re-encoded by the re-encoding circuit 12. Formula (5)
Introducing a value M represented by, the reliability calculation circuit 13 compares the re-encoded signal with the received signal (binarized value) and obtains the sum of the reliability of the received signals when they are different. The candidate having the smallest value M is selected by the candidate comparison / selection circuit 14 to be the decoded data.

[Equation 1] Here, x _i : i-th bit of the signal obtained by re-encoding the decoded candidate y _i : i-th bit of the signal obtained by binary judgment of the actual reception point γ _i : reliability of the reception signal (envelope information of the reception signal, etc. )

In the above embodiment, instead of the preset threshold value, a threshold value that varies depending on the reception state or the decoding result up to immediately before may be used.

Further, instead of storing all the paths equal to or less than the threshold value, a preset number may be stored.

Further, instead of tracing back all paths below a preset threshold value,
It is also possible to set the threshold to be set in multiple stages and limit the path to be traced back according to the magnitude of the likelihood difference.

[0024]

As is apparent from the above-described embodiment, the present invention can improve the error correction decoding capability by surviving a plurality of paths in Viterbi decoding and determining decoded data by error detection or the like. Has the effect.

[Brief description of drawings]

FIG. 1 is a block diagram of an error correction coding / decoding device according to an embodiment of the present invention.

FIG. 2A is a block diagram showing an example of a likelihood comparison type decoded data determination circuit in one embodiment of the present invention. FIG. 2B is a re-encoded signal comparison type decoded data determination circuit in one embodiment of the present invention. Block diagram showing an example

FIG. 3 is a block diagram showing an example of an error correction coding circuit in a conventional example.

FIG. 4 is a trellis diagram showing an example of encoder state transition in a conventional example.

FIG. 5 is a partial trellis diagram showing an example of two rejoining partial paths in a conventional example.

FIG. 6 is a schematic diagram showing an example of a plurality of survivor paths in the present embodiment.

[Explanation of symbols]

 1 Error Correction Encoding Device 2 Error Correction Decoding Device 3 Error Detection Encoding Circuit 4 Error Correction Encoding Circuit 5 Metric Calculation Circuit 6 Path Storage Circuit 7 Traceback Circuit 8 Error Detection Circuit 9 Decoding Candidate Storage Circuit 10, 10A, 10B Decoded data determination circuit 11 Candidate comparison / selection circuit 12 Re-encoding circuit 13 Reliability calculation circuit 14 Candidate comparison / selection circuit

Claims (5)

[Claims] 1. In Viterbi decoding of a convolutional code, only one path having the highest likelihood is selected and stored, and the path having the highest likelihood and the difference between the path and the likelihood are preset. The paths below the threshold value are also stored together, and when the decoded data is obtained by the traceback, the traceback is performed for each of these multiple paths and the error detection code is performed for the obtained multiple decoding candidates. , A Viterbi decoding method characterized in that a candidate having the highest likelihood among candidates in which no error is detected is used as decoded data. 2. Instead of using the candidate having the highest likelihood among the candidates in which no error has been detected as decoded data, a signal obtained by re-encoding the decoded candidate and a received signal are selected for these candidates in which no error has been detected. 2. The Viterbi decoding method according to claim 1, wherein the sum of envelopes of received signals corresponding to bits different from each other is calculated by comparing the binary-determined signal, and a candidate having the smallest value is used as decoded data. . 3. The Viterbi decoding method according to claim 1, wherein instead of the preset threshold value, a threshold value that varies depending on a reception state or a decoding result up to immediately before is used. 4. The method is characterized in that instead of tracing back all paths that are less than or equal to a preset threshold value, the threshold value to be set is set in multiple steps and the traceback path is controlled according to the magnitude of the likelihood difference. Claim 1
Alternatively, the Viterbi decoding method according to claim 2. 5. The maximum likelihood is calculated by comparing the likelihood of a partial path in the trellis diagram from the received data string with a likelihood of a plurality of paths transiting to each state at each time. Path storage means for selecting and storing a path having a likelihood difference between the path and a path smaller than a preset threshold, and tracing for tracing back the selected paths to obtain a plurality of decoding candidates Back means, error detection means for performing error detection of decoding candidates based on the error correction code added by the error detection coding circuit on the transmission side, and decoding candidate storage means for storing decoding candidates in which no error is detected. An error correction decoding apparatus comprising: a decoding data determining unit that selects the most powerful candidate from the stored decoding candidates and sets it as decoded data.