CN107302372B - Fast path searching method for Viterbi decoding - Google Patents

Abstract

The invention discloses a fast path searching method for Viterbi decoding, which comprises a slave state S₀Starting, extending a branch to the right each time, firstly directly selecting a branch with the same output subgroup and the receiving sequence of the current time node as a path of the current segment, if the branch with the same receiving sequence can not be found, retaining all branches from the current state to the secondary state, then continuously searching the branch with the same output subgroup and the corresponding receiving sequence from the branches extending to the right of all the secondary states, finding the branch with the same output subgroup and the corresponding receiving sequence in the selection as a path of the secondary segment, then deleting other paths retained before, and retaining the branch reaching the secondary state connected with the decoding path of the secondary segment as a decoding path of the front segment, and searching the path in such a way until the fence diagram returns to the all 0 state, wherein the obtained path is the optimal path of the algorithm.

Description

A Fast Search Path Method for Viterbi Decoding

technical field

The invention relates to the technical field of digital information transmission, in particular to a fast search path method for Viterbi decoding.

Background technique

Channel coding is an important research field in digital information transmission technology. Among them, convolutional codes have been widely studied and applied due to their excellent anti-noise properties, flexible coding and decoding methods, and small delays. There are also many decoding methods for convolutional codes, and the more common method is the Viterbi decoding method.

The Viterbi decoding method can be used for both hard-decision decoding and soft-decision decoding. Viterbi hard-decision decoding is an algorithm to find a coded bit sequence with the smallest accumulated Hamming distance on the fence graph of the code according to the received hard-decision bit sequence. Let (n ₀ , k ₀ , m) the number of convolutional code information sequence segments be L, where m is the encoding storage of the convolutional code, then the convolutional code encoder has 2^(k ₀ m) states, L+m+ 1 time unit node, numbered from 0 to L+m. Therefore, all possible paths in the fence graph also have 2^(k ₀ L), but the Viterbi decoding method does not compare all possible paths, but receives a segment, calculates and compares a segment, and selects the most probable branch, so as to achieve The entire codeword sequence is a sequence of maximum likelihood functions. The decoder starts from a certain state, for example, from state S ₀ , extends one branch to the right at a time, and compares it with the corresponding branch of the received sequence, calculates the distance between them, and then adds the calculated distance to the extended path. in the cumulative distance value. Compare the cumulative distance values of each path (there are 2^k ₀ ) to each state, and keep the path with the smallest distance value, which is called the surviving path. When there are more than two, the minimum value can be taken one of them. Finally, the fence graph is returned to the state of all 0s, so that a surviving path is left, which is the desired path, and the information bits corresponding to the path backtracking are the decoding output sequence.

Although the Viterbi decoding algorithm is a high-performance algorithm, the complexity in the path search process is relatively large. For (n ₀ , k ₀ , m) convolutional codes, 2^(k ₀ m) “add-ratio-storage” operations are performed at each moment, and each operation includes 2^k ₀ additions and 2^ k ₀ -1 comparisons while keeping 2^(k ₀ m) surviving paths. It can be seen that the complexity of the algorithm has nothing to do with the channel quality, and the amount of calculation and storage increases exponentially with the encoding and storage m and the information element grouping k ₀ , so if m and k ₀ are large, Viterbi decoding is not applicable. Under the premise of good channel conditions, in order to further reduce the computational complexity and storage capacity of the Viterbi decoding algorithm, we will fully channel information and seek a path search method in the improved Viterbi decoding algorithm.

SUMMARY OF THE INVENTION

In order to overcome the shortcomings and deficiencies of the prior art, the present invention provides a fast search path method for Viterbi decoding.

Aiming at the path selection problem in the Viterbi decoding process of convolutional codes, this method adds a high deterministic path selection scheme under the premise of a good channel, which greatly reduces the computational complexity and storage capacity of path search, and has high practicality. significance.

The path searching method of Viterbi decoding proposed by the present invention starts from the state S ₀ , extends one branch to the right at a time, and first directly selects the branch whose output subgroup is the same as the current time node receiving sequence, that is, the Hamming distance is 0 as In this section of the path, if the same branch as the receiving sequence cannot be found, all branches from this state to the sub-state are retained, and then the search continues from the branches extending to the right from all the sub-states, and the output subgroup is the same as the corresponding receiving sequence. Branch, in the channel with only random errors and good conditions, generally there will not be two consecutive errors, so in this branch selection, the branch with the same output subgroup and the corresponding received sequence can be found as the secondary path, Then delete other paths reserved before, and search the path in this way until the fence graph returns to the state of all 0s, and the obtained path is the optimal path of the algorithm. If there are more than two consecutive errors, the path search of the consecutive error parts is performed according to the traditional method, and the intermediate path with the smallest Hamming distance between the encoded output sequence and the received sequence is found.

The present invention adopts following technical scheme:

A fast search path method for Viterbi decoding, comprising the steps:

S1 pairs (n ₀ , k ₀ , m) convolutional codes, starting from the unit time node j=0, that is, starting from the state S ₀ , extending a branch to the right, and finding the output subgroup and the reception of the current time node from the branch The branch with the same sequence is used as the decoding path of this segment. If the branch that satisfies the condition cannot be found, it will enter S2, otherwise j=j+1 will enter S4;

S2 retains all the branches from the previous state to the sub-state, and then extends a branch to the right for all the sub-states, then j=j+1, selects the output subgroup from the branches extending to the right and is the same as the receiving sequence of the current time node The branch of is used as the sub-section decoding path and enters S3;

S3 retains the branch that reaches the sub-state connected with the sub-stage decoding path as the previous-stage decoding path, and deletes other branches that reach the sub-state, and enters S4;

S4 If j<L+m, return to S1, otherwise stop, the decoder obtains the maximum likelihood path with preconditions, where L is the number of information sequence segments in the convolutional code, and m is the encoded storage of the convolutional code.

If there are more than two consecutive errors in the received sequence, the path search of the consecutive error part is performed according to the traditional method, and the intermediate path with the smallest Hamming distance between the encoded output sequence and the received sequence is found.

The (n ₀ , k ₀ , m) convolutional code has 2^(k ₀ m) states, in order to ensure that the fence graph returns to the all-zero state, it will have L+m+1 time unit nodes , numbered from 0 to L+m.

The fact that the output subgroup is the same as the receiving sequence of the current time node means that the Hamming distance between the output subgroup and the receiving sequence of the current time node is 0.

Beneficial effects of the present invention:

(1) The fast path searching method of Viterbi decoding is suitable for channels with better conditions that are widely used in practice, and has the same optimal effect as the traditional Viterbi decoding path searching method.

(2) Compared with the traditional decoding path searching method, the invention has lower computational complexity and less path storage capacity, and only needs to store an optimal path, thereby greatly improving the path searching speed.

Description of drawings

Fig. 1 is the working flow chart of the present invention;

2 is a fence diagram representation of (2, 1, 2) convolutional code G(D)=(1+D+D ² , 1+D ² ) in an embodiment of the present invention;

FIG. 3 is a schematic diagram of an execution process of a fast search path method for (2, 1, 2) convolutional code Viterbi decoding in an embodiment of the present invention.

Detailed ways

The present invention will be described in further detail below with reference to the embodiments and the accompanying drawings, but the embodiments of the present invention are not limited thereto.

Example

As shown in Fig. 1-Fig. 3, a fast search path method of Viterbi decoding is suitable for the received sequence without two consecutive errors. In the embodiment, we use a simple (2, 1, 2) convolutional code, namely The information element block length of the convolutional code is 1, the output sub-group symbol length is 2, and the code storage is 2. The generator polynomial of the convolutional code is G(D)=(1+D+D ² , 1+D ² ), as shown in FIG. 2 , which is a fence diagram of the convolutional code. In the fence diagram of Figure 2, each state has two input and two output branches. At a certain unit time node _j , the dashed branch that leaves each state, that is, the following branch represents the information subgroup mi in the input encoder. =1; and the solid line branch, that is, the upper branch, represents the information subgroup m _i = 0 input to the encoder at this moment; the 2 numbers on each branch represent the subgroup output by the encoder at the jth moment, so in the fence diagram, each A path all corresponds to different input sequences of information. We also assume that the encoded information sequence is m=(1011100), the received codeword is R=(10, 10, 01, 01, 10, 01, 11, 00....), the first sequence segment and the third The second bit of the sequence segment is all wrong, that is, the original correct codeword is C=(11, 10, 00, 01, 10, 01, 11, 00...).

Taking the simple convolutional code we selected as an example, FIG. 3 is a schematic diagram of the execution process of the fast search path method for Viterbi decoding of the convolutional code in this embodiment. The specific implementation of the fast search path method of Viterbi decoding is described below:

S1: For (2, 1, 2) convolutional codes, starting from the unit time node j=0, that is, starting from the state S ₀ , extending a branch to the right, and finding the received sequence of the output subgroup and the current time node from the branch (10) The same branch is used as the decoding path of this section, and it is found that the branch that satisfies the condition cannot be found, and enters step 2;

S2: Retain state S ₀ to reach all branches of sub-states, namely S ₀ and S ₁ , such as the two branches ① in Figure 3, then extend one branch to the right for all sub-states, increase j by 1, and select the output sub from the branch Group the same branch as the receiving sequence (10) of the current time node, such as branch ② in Figure 3, as the sub-section decoding path, and enter step 3;

Step 3: Retain the branch that reaches the sub-state connected to the sub-stage decoding path as the previous-stage decoding path, such as the branch ① connected to the branch ② in Figure 3, delete other branches that reach the sub-state, as shown in Figure 3 Another branch ① connected to branch ②, go to step 4;

Step 4: If j<7, return to step 1, otherwise stop, the decoder obtains the maximum likelihood path with the preconditions, as shown in the path ①→②→③→④→⑤→⑥→⑦ in Figure 3 . The information sequence obtained by backtracking according to this path is consistent with the encoder information sequence m=(1011100), indicating that the decoding is successful.

The number of information sequence segments in the (2, 1, 2) convolutional code is 5, and the encoding of the convolutional code is stored as 2.

The (2, 1, 2) convolutional code has 4 states, namely S ₀ , S ₁ , S ₂ , and S ₃ . In order to ensure that the fence graph returns to the state of all 0s, there will be 8 states. Time unit nodes, numbered from 0 to 7.

In a channel with only random errors and good conditions, two errors generally do not occur in a row. Under the premise of this channel, the search path of Viterbi decoding is carried out according to the above method, that is, the output sub-channel is directly searched in the process of searching the path. The branch with the same group as the received sequence, that is, the branch where the Hamming distance between the output subgroup and the received sequence is 0 is directly searched, and the obtained path is a maximum likelihood path, which is an optimal decoding path under preconditions.

If there are more than two consecutive errors, the path search of the consecutive error parts is performed according to the traditional method, and the intermediate path with the smallest Hamming distance between the encoded output sequence and the received sequence is found.

For (n ₀ , k ₀ , m) convolutional codes, n ₀ represents the length of the symbol, and k ₀ represents the length of the information element. When using the traditional decoding path search method, 2^(k ₀ m is required for each moment. ) times "add-compare-save" operations, each operation includes 2^k ₀ additions and 2^k ₀ -1 comparisons, while 2^(k ₀ m) survival paths are reserved. We can see from the embodiment that this method has lower computational complexity and less path storage than the traditional decoding path search method, and generally only needs to do 2^k ₀ times at each moment. A match comparison operation does not require storing a temporary path. In the worst case, only 2^k ₀ temporary paths need to be stored, and 2^(2k ₀ ) matching and comparison operations are required. In general, only one optimal path needs to be stored, so the path search speed is also greatly improved. At the same time, this method has the same optimal effect as the traditional Viterbi decoding path searching method.

The above-mentioned embodiments are preferred embodiments of the present invention, but the embodiments of the present invention are not limited by the described embodiments, and any other changes, modifications, substitutions, and combinations made without departing from the spirit and principle of the present invention , simplification, all should be equivalent replacement modes, and are all included in the protection scope of the present invention.

Claims (4)

1. A fast path search method for Viterbi decoding, comprising the steps of:

s1 pairs (n)₀，k₀M) convolutional codes, starting from the unit time node j equal to 0, i.e. from the state S₀Starting from the branch, extending a branch to the right, finding out the branch with the output subgroup same as the receiving sequence of the current time node from the branch as the decoding path of the segment, if no branch meeting the condition can be found, entering S2, otherwise, entering S4 when j is j +1, and n₀Denotes the length of the symbol, k₀Indicating an information element length;

s2 retains all branches from the previous state to the next state, then extends a branch to the right for all the next states, then j equals j +1, selects a branch with the same output subgroup as the received sequence of the current time node from the branches extending to the right as the next segment decoding path, and proceeds to S3;

s3 reserving the branch of the arrival secondary state connected with the secondary decoding path as the front-stage decoding path, deleting other branches of the arrival secondary state, and entering S4;

and S4, if j is less than L + m, returning to S1, otherwise, stopping, and obtaining the maximum likelihood path with the precondition by the decoder, wherein L is the number of information sequence segments in the convolutional code, and m is the coding storage of the convolutional code.

2. The method as claimed in claim 1, wherein if more than two consecutive errors occur in the received sequence, the path search of consecutive error portions finds the intermediate path with the minimum hamming distance between the coded output sequence and the received sequence according to the conventional method.

3. The method of claim 1, wherein (n) is equal to₀，k₀M) convolutional codes have 2^ (k)₀m) states, which will have L + m +1 time unit nodes, numbered 0 to L + m, where n is the number of time unit nodes, to ensure that the trellis diagram eventually returns to the all 0 state₀Denotes the length of the symbol, k₀Indicating the information element length.

4. The method of claim 1, wherein the output subset being identical to the received sequence of the current time node means that the hamming distance between the output subset and the received sequence of the current time node is 0.

Images