JPH07288478A - Viterbi decoding method and Viterbi decoding device - Google Patents

Abstract

(57) [Abstract] [Purpose] To increase the number of decoded data (decoding candidates) within a certain processing time when performing traceback multiple times in Viterbi decoding. [Structure] A plurality of decoding candidates are searched by the recursive method, and in each state traced back by traceback, the allowable metric difference and the likelihood difference in that state are compared (step 1
3) If the likelihood difference is less than or equal to the allowable metric difference, the time, state, branch flag, and four parameters of the remaining metric value are stored as one information in the stack memory (step 14). When decoding by the recursive method, in the next traceback, the decoding result of the common part of the paths passed by the previous traceback is used by being copied, and the different partial paths are the times stored in the stack memory. And so on, and only the path select signal at the branch point is inverted to perform traceback to obtain the decoded data of the remaining partial paths.

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 and apparatus for error correcting codes used for data transmission in digital automobile telephones, mobile telephones and the like.

[0002]

2. Description of the Related Art Viterbi decoding is one of decoding methods for convolutional codes. The conventional Viterbi decoding will be described below. A convolutional code C having a high speed length K = 3 and a coding rate R = 1/2 generated by a convolutional encoder as shown in FIG.
Will be described as a specific example.

With the shift registers F ₁ and F ₂ shown in FIG. 7, the encoder state S has 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 the state S ₀ changes every second, that is, each time an information signal is input. A trellis diagram of the code C is shown in FIG. Note that here, the input information signal sequence length is J−K + 1, and K−1 0s are added.
Shall continue.

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. 8, 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), d = (1,1) (2), the left component is C _i ⁽¹⁾ , and the right component is C _i ^{(2 )}
Shall be represented.

State S ₀ (t = t ₀ ) at time t = t ₀
The series of branches that the path to the state in t = t ₁ from _{S 0 (t = t 1)} . This path is the convolutional code C
Is the path for the codeword of. When it is necessary to avoid confusion with the partial path, we call it the codeword path.

FIG. 9 shows a partial path in the trellis diagram of the code C. For the sake of convenience, the subset of codewords corresponding to this partial path is set to C _s ¹ = (00 00 11) and C _s ² = (11 1000) (3). In Viterbi decoding by comparing the likelihood of the path C _s ¹ and C _s ^2, for example, towards the likelihood of C _s ¹ to reject the C _s ² is greater than the likelihood of C _s ^2. At this time, all codeword paths including the path C _s ² as a partial path are rejected from the transmission codeword candidates. A partial path that remains without being rejected, such as C _s ¹ , is called a surviving path.

It can be seen from the trellis diagram of FIG. 8 that each state has two partial paths having the same branch state as shown in FIG. Therefore, in normal Viterbi decoding, it can be seen that there are always 2 ^{K- 1} surviving paths at each time in the steady state excluding the states at both ends of the codeword. After time t _{J-K + 2} , the number of surviving paths decreases by ½, and at time t _j , there is only one surviving path. Then, this survivor path is decoded by traceback to obtain maximum likelihood decoded data.

On the other hand, in the Viterbi decoding method described in the specification of Japanese Patent Application No. 5-67061 previously proposed by the applicant of the present application, only one partial path is set as the surviving path even if there is no difference in likelihood. , The other is rejected. Therefore, in order to solve the problem that there is a high possibility that the surviving codeword path will not be a correct decoded word when data is transmitted through a transmission path with many errors, ACS ( Add Compare Selec
t) When selecting the surviving path in each state in the operation, not only select and store only the path with the highest likelihood (metric) (memorize the path select signal), but also select the path with the highest likelihood. The likelihood difference between the path and other paths is also stored together, and when the decoded data is obtained by traceback, not only the maximum likelihood decoding path but also the likelihood (traceback in the traceback section of the maximum likelihood path And the likelihood of the data decoding section), traceback is performed for each of a plurality of paths having a likelihood equal to or less than a preset threshold (allowable metric difference).
Multi-traceback is performed to obtain multiple decoding candidates from multiple tracebacks.

This multi-trace back processing is performed as follows. In each traceback, the following processes (i) to (iv) are performed at each time (t _n ).

(I) Find the tolerance at time t _n . t
The tolerance in _n is the difference between the reversed paths when the path from the start of this traceback to t _{n + 1} includes the selected path reversed by the process (vi) before this traceback. The metric difference (or the sum of those if multiple are included) is calculated by subtracting the given allowable path metric difference.

[0012] (ii) if the path at time t _n to pass through the state S _i, obtained in ACS [time t _n, the state S _i] metric difference in the If it is within the tolerance, the state at that time And the metric difference. However, if the selection path of [time t _n , state S _i ] is reversed due to (vi), it is not stored.

(Iii) [time t _n , state S obtained by ACS]
_i ] to trace back the selected path and determine the state where the path passes at time t _n-1 (normal traceback processing).

(Iv) Obtain decoded data at time t _n (normal traceback processing). The following processing is performed at the end of each traceback.

(V) Decoded data is output (normal traceback processing). (Vi) If the one stored earliest (closest to t ₀ ) among the items stored in (ii) is [time t _m , state S _j ], the following two processes are performed.

Invert the path select signal at [time t _m , state S _j ] obtained by ACS.

By the previous processing, if there are reverse paths in any of the times t _{0 to} t _m-1 , they are all restored. The above is repeated, and when there is no pass to be reversed in (vi), the process ends.

[0018]

However, in the multi-traceback processing algorithm of the above-mentioned prior invention, in each traceback, the decoded data is calculated every time from the final time to the first time t _0. It is necessary, and the conditions for storing the time and the state are complicated, so that it takes a lot of processing time.
When performing multi-trace back within a limited processing time in hardware, even if there are many decoding candidates within the given allowable metric difference, processing is performed according to the number of times of trace back (decoded data number). There is a problem that the time is limited and the traceback cannot be performed a sufficient number of times, so that only some decoding candidates can be obtained.

The present invention solves the above problems of the prior invention, and an object of the present invention is to provide a more efficient and excellent Viterbi decoding method and its apparatus.

[0020]

In order to achieve the above object, the present invention searches a plurality of decoding candidates by a recursive method,
At this time, in each state traced back by traceback,
The allowable metric difference is compared with the likelihood difference stored in that state, and if the likelihood difference is less than or equal to the allowable metric difference,
Assuming that the state is a state in which multiple branches can be selected, the time and state, the branch flag indicating which branch is selected and performing traceback, and the likelihood difference is subtracted from the allowable metric difference. Value (remaining metric value) is stored in the stack memory as one piece of information, and when decoding by the recursive method, in the next traceback, among the paths that have been passed by the previous traceback, , Copy the common partial path decoding result (memory transfer), and use different partial paths with a new branch at the time and state stored in the stack memory and invert only the path select signal at that branch point to trace By performing back, the decoded data of the remaining partial paths is obtained.

In addition, when performing multi-trace back within a limited processing time, instead of the conventional method of limiting the processing time by the number of trace backs (the number of decoded data), a new branch is made to trace. Obtain the number of branches (path length) of the partial path to be backed from the time stored in the stack memory, and if the cumulative value is less than or equal to the preset limit value, perform traceback to obtain the decoded data. If the output exceeds the limit value,
The processing time is limited by ending the decoding process without performing the traceback.

[0022]

Therefore, according to the present invention, more decoded data candidates can be obtained within a limited processing time,
More efficient and excellent error correction decoding can be performed.

[0023]

1 is a block diagram showing the arrangement of a Viterbi decoding apparatus according to an embodiment of the present invention. In FIG. 1, 1 is a Viterbi decoding device, 2 is a metric calculation circuit, and 3 is ACS.
A circuit, 4 is a path select storage circuit, 5 is a path metric storage circuit, 6 is a multi-trace back circuit, and 7 is a stack memory.

In the Viterbi decoding apparatus 1, the metric calculation circuit 2 calculates the likelihood (metric) of each partial path (branch) from the received data string. Next, the ACS circuit 3 compares the metrics of a plurality of paths that transit to each state at each time, selects the path with the highest metric, and stores the path select signal in the path select storage circuit 4. However, the metric difference with other paths is also stored at the same time. Also, as with normal Viterbi decoding,
The path metric memory circuit 5 also stores and updates the path metric. Then, based on the information in the path select storage circuit 4, the multi-trace back circuit 6
And the traceback is performed by the stack memory 7. In this case, depending on the given allowable metric difference, the number of surviving paths does not always become one, and as shown in FIG.
Multiple paths survive.

In the case of FIG.

[0026]

[Equation 1]

In the multi-trace back circuit 6, these six paths are traced back and a plurality of decoded data are obtained, with the six paths as surviving paths.

3 and 4 show an example of the processing algorithm of the multi-trace back circuit 6 in this embodiment. In this example, as shown in the trellis diagram of FIG. 8, there are two paths from the 1 state.

First, in the initialization process of step 10, the stack memory, the stack memory address, the allowable metric difference, the traceback (TB) branch number counter, the TB counter, and the state are initialized. Then, the time tn is initialized (step 11), and the traceback process is performed thereafter. The path select signal and the metric difference in that state are read from the path select storage circuit 4 (step 12) and compared with the allowable select difference (step 13). If the metric difference is less than the allowable metric difference, it is stored in the stack memory 7. (Step 1
4) The address is updated (step 15). FIG. 5 shows an example of 1 information (4 parameters) stored in the stack memory 7 at this time.

Then, after calculating the state one hour before (step 16) and calculating / storing the decoded data (step 17), the time is changed (step 18) and it is judged whether or not to go back further ( Perform step 19). If it is determined that one traceback has been completed, it is checked whether or not the information is stored in the stack memory 7 (step 20), and if there is no information, the process is completed (step 29).
If there is, the highest address (last stored address)
The branch flag of 1 information is determined (step 21),
If it is "1", 1 information of the highest address is erased, the address is decremented by 1 (step 30), and the process returns to step 20 again. On the other hand, when the branch flag is "0", the other parameters of the 1 information are read, the remaining metric value is set as the allowable metric difference (step 22), and the branch flag is converted from 0 to 1 and then updated. The other information is stored in the stack memory 7 again (step 23).

Then, the cumulative value of the number of branches to be traced back (TB) is calculated (step 24), and if it is less than the limit number, the TB counter is increased (step 26).
The decoded data up to the branch point is copied from the immediately preceding decoded data (step 27), the path select signal in the state of the branch point is inverted (step 28), and the process returns to step 16 to trace back. To do. On the other hand, if the number exceeds the limit, it is determined that the process is insufficient, and the decoding process ends (step 29).

In the above processing algorithm example, TB
Although the processing time is limited by the number of branches, if it is desired to limit the number of decoded data instead of the processing time, the number of decoded data is monitored in step 26. Therefore, the processing is performed when the preset number of decoded data is reached. By terminating
Obviously, it can be easily restricted.

FIG. 6 shows an example of changes in the stack memory 7 when multi-trace back is performed by the processing algorithms of FIGS. 3 and 4. This figure shows changes in the stack memory 7 when the path for traceback moves from (a) to (e). Here, the allowable metric difference is set to 5, and in the state of black dots, it is assumed that the total of the metric differences (displayed as + x in the figure, the likelihood that a path with a number has a lower likelihood) is less than or equal to the allowable metric difference.
It is stored in the stack memory 7.

For example, in the path of (a), since the lower likelihood is selected only at time N-2, time N-
The branch flag of stack memory 2 is set to 1. When the traceback branches to the path of (b) at time N-7, the path with a low likelihood is selected at time N-7, so the selection flag at that time becomes 1.
When branching to (c), the information at time N-7 is once erased, the selection flag at time N-6 becomes 1, and the time N-7
It is newly stored at -7. It is clear from the above algorithm that the branch flag becomes 1 when the TB of (d) performs this information.

[0035]

As is apparent from the above-described embodiment, the present invention searches for a plurality of candidates by the recursive method when performing multi-traceback, and at this time, in each state traced back by traceback, the allowable metric difference is calculated. The likelihood difference stored in that state is compared, and if the likelihood difference is less than or equal to the allowable metric difference, it is considered that a plurality of branches can be selected, and the time and state of that state and which branch is selected. The branch flag indicating whether or not the selected traceback is being performed and the value obtained by subtracting the likelihood difference from the allowable metric difference are stored in the stack memory, and when decoding by the recursive method, in the next traceback, Of the decoded data of the paths that have passed through the trace back one before, the decoding result of the common partial path is copied and used, and the different partial paths are
Since a new branch is made from the time and state stored in the stack memory and only the path select signal at the branch point is inverted and the tray is backed, the decoded data of the remaining partial paths is obtained. In Viterbi decoding, there is an effect that the processing time can be shortened when a plurality of paths are made to survive and a plurality of decoded data candidates are obtained.

[Brief description of drawings]

FIG. 1 is a block diagram of a Viterbi decoding device according to an embodiment of the present invention.

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

FIG. 3 is a flowchart showing an example of a multi-traceback processing algorithm in this embodiment.

FIG. 4 is a flowchart showing the continuation of the processing algorithm.

FIG. 5 is a schematic diagram showing an example of storage in a stack memory in multi-trace back processing in this embodiment.

FIG. 6 is a schematic diagram showing an example of changes in the stack memory in the multi-trace back processing in this embodiment.

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

FIG. 8 is a schematic diagram showing an example of a trellis diagram in a conventional example.

FIG. 9 is a schematic diagram showing an example of two rejoining partial paths in a conventional example.

[Explanation of symbols]

 1 Viterbi Decoding Device 2 Metric Calculation Circuit 3 ACS Circuit 4 Path Select Storage Circuit 5 Path Metric Storage Circuit 6 Multi Trace Back Circuit 7 Stack Memory

Claims (3)

[Claims] 1. When selecting a surviving path in each state in an ACS (Add Compare Select) operation, not only one path with the highest likelihood is selected and its path select signal is stored, The likelihood difference between a path with a high likelihood and another path is also stored together, and when obtaining decoded data by traceback, not only the maximum likelihood decoding path but also the traceback section of the maximum likelihood path With respect to the likelihood, a multi-trace back is performed to obtain a plurality of decoding path candidates by performing a trace back for each path having a likelihood equal to or less than an allowable metric difference that is a preset threshold value. When performing back, multiple candidates are searched by the recursive method, and in each state traced back by traceback, the allowable metric difference and its The likelihood difference stored in the state is compared, and if the likelihood difference is less than or equal to the allowable metric difference, it is considered that multiple branches can be selected, and the time and state of that state and which branch is selected. Then, a branch flag indicating whether or not the traceback is being performed, and a value obtained by subtracting the likelihood difference from the allowable metric difference are stored in the stack memory, and when decoding by the recursive method, in the next traceback, Of the decoded data of the paths passed by the preceding traceback, the decoding result of the common partial path is copied and used, and the different partial paths are newly branched from the time and state stored in the stack memory, and A Viterbi decoding method characterized in that the decoded data of the remaining partial paths are obtained by performing traceback by inverting only the path select signal at the branch point. 2. Of the decoded data of the path that has passed by the preceding traceback, the decoding result of the common part is used by copying or memory transfer, and the different part inverts only the path select signal at the branch point. When performing traceback by performing traceback, obtain the number of branches or the length of the path to be traceback from the time stored in the stack memory.If the cumulative value of the number of branches is less than or equal to the preset limit value, traceback is performed. The Viterbi decoding method according to claim 1, wherein the decoding process is terminated without performing traceback when the limit value is exceeded. 3. A metric calculation means for calculating the likelihood of each partial path from the received data string, a means for comparing the metrics of a plurality of paths transiting to each state at each time, and a path with the highest metric is selected. Not only that signal but also the metric difference with other paths at the same time, the path metric storage means for storing and updating the path metric, and the information in the path select storage means. A Viterbi decoding device, comprising: a multi-trace back means for performing the multi-trace back according to claim 1 or 2; and a stack memory for storing information necessary for the multi-trace back.