CN102142848A - Decoding method and decoder of tail-biting convolutional code - Google Patents

Abstract

The present invention relates to a decoding method and a decoder of a tail-biting convolutional code. The above method performs a Viterbi (VA) algorithm on a sequence to be decoded, finds a preset number of cumulative metrics from the obtained cumulative metrics, and Backtrack its end state, and determine the reference state from the obtained start state; by comparing whether the end state corresponding to the above reference state is the same as the above reference state, decide whether to directly obtain the decoding sequence, or execute the above sequence to be decoded again VA algorithm, and then obtain the decoding sequence by backtracking; the decoder includes a VA algorithm module, a search module, a backtracking module, a state selection module and a comparison module. The invention not only simplifies the decoding complexity, reduces the decoding cost, but also has stronger decoding performance.

Description

A decoding method and decoder for tail-biting convolutional codes

technical field

The invention relates to the field of communication technology, in particular to a decoding method and a decoder of a tail-biting convolutional code.

Background technique

In digital communication systems, it is a very important task to correct the errors caused by channel interference and noise between the transmitter and receiver. The channel coder makes the system have the ability of error detection and error correction by artificially adding redundant information. During the evolution of Global System for Mobile Communications (GSM) Enhanced Data Rate for GSMEvolution (EDGE) Radio Access Network (GSM EDGE Radio Access Network, GERAN), we have always paid attention to this issue, one of which is One technique for error correction is to encode the transmitted data using a convolutional code.

Convolutional codes use registers to increase the correlation between symbols, resulting in higher coding gain. Convolutional codes can be represented by a ternary ordered group (n, k, m). Among them, n is the number of bits encoded by a unit time; k is the number of information symbol bits, which represents the number of information bits input to the convolutional code encoder per unit time; m represents the coded storage length of the convolutional code, It is equal to the maximum shift register length of the convolutional code encoder. Encoding constraint length N=m+1. As shown in Figure 1, it is a (2, 1, 2) encoder block diagram. In the figure, D is a shift register, ⊕ is an adder, and the encoding inputs 1 bit and outputs 2 bits. Its grid diagram is shown in Figure 2. The contents of two registers 0/1 are combined to form 4 states (ie: 00, 01, 10, 11). In the figure, the solid line represents the state transition when the code input is 0, and the dotted line represents Encodes the state transition on input 1.

The decoding technique of convolutional code, Viterbi algorithm (Viterbi Algorithm, VA) is based on trellis graph, and its decoding process is to find the best decoding sequence along the trellis graph according to the maximum likelihood criterion. When -1 represents a binary "1" and +1 represents a binary "0", that is to find the sequence with the largest correlation function (cumulative measure) with the received sequence. The calculation of the cumulative measure adopts the method of adding and comparing, as shown in Figure 3, which is a schematic diagram of the process of adding and comparing in the Viterbi algorithm. (k) old cumulative metric plus the current branch metric) for comparison, if the metric is larger, it will be used as a surviving path, and the corresponding branch decision value will be recorded. The VA algorithm is to accumulate metrics from a certain (or all) state, and at the end of the calculation, the cumulative metrics of all states are obtained and the corresponding survival path is recorded. From a specific end state, the decoding output can be obtained according to the survival path backtracking sequence.

There are two strategies for the final state of convolutional codes: zero termination and tailbiting. The zero-tail method adds fixed tail bits (usually all 0s) to the end of the information bits to ensure that the encoder ends in a specific state (usually state 0). Therefore, backtracking must start from this state, which can be decoded relatively easily and reliably. But the additional tail reduces the bit rate, so in GERAN, the zero tail method is generally used for data packets with more information bits. As for the header containing important information and less information bits in the message, tail-biting convolutional codes are used for encoding in the protocol specification. The tail-biting method ensures that the start state of the encoder is consistent with the end state by pre-inputting the bits that are the same as the end state before the code output 0 time. Therefore the end state to which a tail-biting convolutional code decoder is based before backtracking is unknown to the decoder.

The time and space complexity occupied by the VA algorithm is the main cost of the tail-biting convolutional code decoder. However, since the first and last states are unknown, the prior art either executes the VA algorithm multiple times (generally greater than twice), or uses multiple repetitions of the input sequence length to perform longer VA, which greatly increases the computational complexity and memory usage.

In the prior art, the consistency of the start state and the end state is usually used as the judging sign of successful decoding according to the characteristic that the first and last states of the tail-biting convolutional code are consistent. However, if the end state of the maximum cumulative metric obtained after a certain VA algorithm is not the real end state, but the wrong start state obtained after backtracking may still be the same as the end state, obviously, the output obtained in this way sequence is not the correct decoding result.

Contents of the invention

One of the objectives of the present invention is to provide a tail-biting convolutional code decoding method and decoder to reduce decoding cost and complexity; the present invention is simple to implement.

The present invention proposes a decoding method of a tail-biting convolutional code,

Starting from all states, execute the VA algorithm on the sequence to be decoded to obtain the cumulative metrics and survival paths of all states;

Find a preset number of larger cumulative metrics from the cumulative metrics, and record the end status of the cumulative metrics;

According to the surviving path, according to the order of cumulative metrics from large to small, respectively trace back the end states of the records to obtain the corresponding start states and output sequences;

selecting a reference state from said derived starting states;

Comparing whether the end state corresponding to the reference state is the same as the reference state, if so, the decoding sequence is equal to the output sequence obtained by backtracking the end state; otherwise, starting from the reference state, the to-be-decoded The code sequence executes the VA algorithm to obtain new cumulative metrics and survival paths of all states; according to the survival path, the reference state is used as the end state for backtracking, and the obtained output sequence is the decoding sequence.

Preferably, starting from all states above, before performing the VA algorithm on the sequence to be decoded, the cumulative metrics of all states above are first initialized to the same value.

Preferably, the aforementioned preset number is greater than or equal to three.

Preferably, the above-mentioned step of selecting a reference state from the obtained starting state specifically includes:

Judging whether there is a repeated start state in the above-mentioned start state, if so, the above-mentioned reference state is the start state with the largest number of repeated occurrences, and if the start state with the largest number of repeated occurrences is more than one, then the reference state is the repeated start state. The start state backtracked earlier among the start states with the most occurrences; otherwise, the above reference state is the start state backtracked from the end state with the largest cumulative metric.

Preferably, before performing the VA algorithm on the above-mentioned sequence to be decoded again, the following steps are also performed:

Initialize the cumulative metrics of the above reference state to 0, and initialize the cumulative metrics of the remaining states to the negative minimum value represented by the data format of the corresponding cumulative metrics.

The present invention also proposes a decoder for realizing the above method, including a VA algorithm module, a search module, a backtracking module, a state selection module and a comparison module,

The above VA algorithm module is used to execute the VA algorithm on the sequence to be decoded;

The above-mentioned search module is used to find a preset number of larger cumulative metrics from the cumulative metrics of all states, and record the end state of the above-mentioned cumulative metrics;

The above-mentioned backtracking module is used to backtrack the end state to obtain the output sequence;

The above state selection module is used to determine the reference state;

The comparison module is configured to compare whether the end state corresponding to the reference state is the same as the reference state, and determine a decoding sequence according to the comparison result.

Preferably, the above-mentioned VA algorithm module is also used to initialize the cumulative metrics of each state.

Preferably, the above search module includes a selection submodule and a recording submodule,

The above selection sub-module is used to find a preset number of larger cumulative metrics from all the above cumulative metrics;

The recording sub-module is configured to record the end status of the accumulated metrics found above.

Preferably, the above state selection module includes a judgment submodule and a reference state determination submodule,

The above judging sub-module is used to judge whether there are repeated starting states in all starting states;

The reference state determination submodule is configured to determine the reference state according to the judgment result of the judgment submodule.

Preferably, the comparison module includes a state comparison submodule, a decoding sequence determination submodule,

The above-mentioned state comparison sub-module is used to compare whether the end state corresponding to the above-mentioned reference state is the same as the above-mentioned reference state;

The decoding sequence determination sub-module is used to determine the decoding sequence according to the comparison result of the state comparison sub-module.

Compared with the traditional method, the present invention only needs to execute the VA algorithm twice at most, and does not need to extend the input sequence and perform longer VA, which not only simplifies the decoding complexity and reduces the decoding cost, but also has strong for even stronger decoding performance. The present invention is suitable for decoding tail-biting convolutional codes in communication systems, such as being applied in GERAN systems.

Description of drawings

Fig. 1 is a schematic structural diagram of a convolutional code encoder;

Fig. 2 is a convolutional code encoding lattice diagram;

Fig. 3 is a schematic diagram of the process of adding, comparing and selecting in the VA algorithm;

Fig. 4 is a flow chart of a preferred embodiment of the method of the present invention;

Figure 5 is a comparison chart of decoding frame error rate (Frame Error Rate, FER) performance curve;

Fig. 6 is a functional block diagram of the first embodiment of the decoder of the present invention;

Fig. 7 is a functional block diagram of the second embodiment of the decoder of the present invention.

The realization of the purpose of the present invention, functional characteristics and advantages will be further described in conjunction with the embodiments and with reference to the accompanying drawings.

Detailed ways

The tail-biting convolutional code decoding method and decoder proposed by the present invention will be further described in detail below in conjunction with the accompanying drawings and preferred embodiments.

As shown in Figure 4, it is a flow chart of a preferred embodiment of the method of the present invention, including:

S401: Initialize the cumulative metrics of all states to the same value, that is, initialize the cumulative metrics of all states;

The same value above is generally 0;

S402: Starting from all states, execute the VA algorithm on the sequence to be decoded to obtain the cumulative metrics and survival paths of all states;

At the beginning of decoding, since the starting state is unknown, it is necessary to start from all states.

S403: Find a larger preset number of accumulated metrics from the accumulated metrics obtained above, and record the end status of the accumulated metrics found above;

The above preset number is generally greater than or equal to 3;

S404: According to the surviving path, according to the order of the accumulated metrics from large to small, respectively trace back the above-mentioned end states to obtain their respective start states and output sequences;

Since there are M end states, this step obtains M start states;

S405: Select a reference state from the above obtained start states;

This step is achieved by the following methods:

S4051: Determine whether there are repeated start states in the start states obtained above, if yes, execute S4052; otherwise, execute S4053;

S4052: Let the reference state be the start state with the largest number of repetitions; if the above-mentioned start state with the largest number of repetitions is more than one, set the reference state to be the start state obtained earlier from the start state with the largest number of repetitions;

S4053: Let the reference state be the start state obtained by backtracking the end state of the largest cumulative metric.

S406: Compare whether the end state corresponding to the above reference state is the same as the above reference state, if yes, execute S407; otherwise, execute S408;

S407: Make the decoding sequence equal to the output sequence obtained by backtracking the above-mentioned end state, and the decoding ends;

S408: Initialize the cumulative metric of the above reference state to 0, and initialize the cumulative metric of the remaining states (ie all states except the above reference state) to the negative minimum value represented by the data format of the corresponding cumulative metric;

S409: Starting from the above reference state, execute the VA algorithm again on the sequence to be decoded to obtain new cumulative metrics and survival paths of all states;

S410: According to the surviving path, perform backtracking with the above reference state as the end state, and obtain the output sequence;

S411: Make the decoding sequence equal to the output sequence obtained by backtracking the above reference state, and the decoding ends.

As shown in Figure 5, it is a comparison diagram of the decoding FER performance curve obtained by using the method of the present invention and the decoding FER curve obtained by using the prior art; After the SCHM) head is encoded with a (3, 1, 6) tail-biting convolutional code, the decoding FER performance curve of the sequence to be decoded after transmission in a channel with a Signal to Noise Ratio (SNR) of SNR As an example, the method of the present invention and two methods of the prior art are compared and illustrated, among the figures,

The SCHM-Max1 curve is in the prior art, selects one of the largest cumulative metrics from the cumulative metrics obtained by executing the VA algorithm, backtracks the end state of the largest cumulative metric to obtain an output sequence, and uses this output sequence as the final translation The decoding FER performance curve under the code sequence situation;

The SCHM-Max3 curve is in the prior art, selects 3 larger cumulative metrics from the cumulative metrics obtained by executing the VA algorithm, and then backtracks the end states of the above cumulative metrics in turn to obtain the start state and output sequence of the current end state, Compare whether the above start state and end state are the same, if they are the same, the output sequence obtained by backtracking from the current end state is the final decoding sequence; if they are different, the decoding FER in the case of backtracking the start state of the next cumulative metric performance curve;

The SCHM-TrcE curve is the decoding FER performance curve obtained using the method of the present invention;

As can be seen from the figure, the FER using the method of the present invention is lower than the FER using the prior art method.

As shown in FIG. 6 , it is a functional block diagram of the first embodiment of the decoder of the present invention, including a VA algorithm module 100, a search module 200, a backtracking module 300, a state selection module 400 and a comparison module 500,

The VA algorithm module 100 is used to initialize the cumulative metrics of each state; it is used to execute the VA algorithm for the sequence to be decoded to obtain the cumulative metrics and survival paths of all states; in the present invention, the VA algorithm module 100 will execute the VA algorithm once or twice , the first time starts from all states, and the second time starts from the above reference state.

The search module 200 is used to find out the preset number M larger cumulative metrics from the cumulative metrics obtained by the above-mentioned VA algorithm module 100, and record the end status of the found cumulative metrics;

The backtracking module 300 is used for backtracking the end state (including the end state recorded by the above-mentioned search module 200 and the end state when the reference state is used as the end state) according to the survival path obtained by the above-mentioned VA algorithm module 100, to obtain the corresponding end state start state and output sequence;

A state selection module 400, configured to select a reference state from the starting states obtained by the above-mentioned backtracking module 300;

The comparison module 500 is configured to compare whether the end state corresponding to the above reference state is the same as the above reference state, and determine a decoding sequence according to the comparison result.

As shown in FIG. 7 , it is a functional block diagram of the second embodiment of the decoder of the present invention. This embodiment is the same as the first embodiment in that they both include a VA algorithm module 100, a search module 200, a backtracking module 300, State selection module 400 and comparison module 500; the difference is:

The search module 200 includes a selection submodule 201 and a recording submodule 202; the state selection module 400 includes a judgment submodule 401 and a reference state determination submodule 402; the comparison module 500 includes a state comparison submodule 501 and a decoding sequence determination submodule 502, wherein ,

Selecting a submodule 201 for finding a preset number M larger cumulative metrics from all the cumulative metrics obtained by the above-mentioned VA algorithm module 100;

A record submodule 202, configured to record the end status of the accumulated metrics found by the selection submodule 201;

Judgment sub-module 401, for judging whether there is a repeated start state among all the start states obtained by the above-mentioned backtracking module 300;

The reference state determination submodule 402 is used to determine the reference state according to the judgment result of the judgment submodule 401, that is, when there is a repeated start state in the start state obtained by the above-mentioned backtracking module 300, the reference state is the most repeated occurrence The start state; when the start state obtained by the above-mentioned backtracking module 300 is different from each other, let the reference state be the start state obtained by backtracking the end state of the largest cumulative metric;

The state comparison sub-module 501 is used to compare whether the end state corresponding to the above-mentioned reference state is the same as the above-mentioned reference state;

The decoding sequence determination sub-module 502 is used to generate a decoding sequence according to the comparison result of the state comparison sub-module 501, that is, when the end state corresponding to the reference state is the same as the above-mentioned reference state, make the decoding sequence equal to the above-mentioned end state backtracking The obtained output sequence; when the end state corresponding to the reference state is different from the above reference state, make the decoding sequence equal to start from the above reference state, execute the VA algorithm again on the sequence to be decoded, and proceed with the above reference state as the end state The output sequence obtained by backtracking.

The above are only preferred embodiments of the present invention, and are not intended to limit the patent scope of the present invention. Any equivalent structure or equivalent process conversion made by using the description of the present invention and the contents of the accompanying drawings, or directly or indirectly used in other related technical fields , are included in the patent protection scope of the present invention.

Claims (10)

1. the interpretation method of a tail-biting convolutional code is characterized in that, described method is:

From all states, sequence to be decoded is carried out Viterbi (VA) algorithm, obtain the cumulative metric and the survivor path of all states;

From described cumulative metric, find out default several bigger cumulative metrics, and write down the done state of described cumulative metric;

According to described survivor path, according to cumulative metric order from big to small, respectively the done state of described record is recalled, obtain corresponding initial state and output sequence;

From the described initial state that obtains, select reference state;

Relatively whether more identical with described reference state with the corresponding done state of described reference state, if then decipher sequence and equal described done state and recall the output sequence that obtains; Otherwise, from described reference state, once more described sequence to be decoded is carried out the VA algorithm, obtain the cumulative metric and the survivor path of all new states; According to described survivor path, to recall as done state with described reference state, the output sequence that obtains is the decoding sequence.

2. the interpretation method of tail-biting convolutional code as claimed in claim 1 is characterized in that, and is described from all states, and before sequence execution VA algorithm to be decoded, at first the cumulative metric with described all states is initialized as identical value.

3. the interpretation method of tail-biting convolutional code as claimed in claim 1 is characterized in that, described default number is more than or equal to 3.

4. the interpretation method of tail-biting convolutional code as claimed in claim 1 is characterized in that, the described reference state step of selecting from the initial state that obtains specifically comprises:

Judge in the described initial state that obtains whether the initial state that repeats is arranged, if, then described reference state is the maximum initial state of frequency of occurrence, if the maximum initial state of described frequency of occurrence is greater than one, then described reference state is early to recall the initial state that obtains in the maximum initial state of described frequency of occurrence; Otherwise described reference state is recalled the initial state that obtains for the done state of maximum cumulative metric.

5. the interpretation method of tail-biting convolutional code as claimed in claim 1 is characterized in that, and is described from reference state, to before the described sequence execution VA algorithm to be decoded, also carries out following steps once more:

The cumulative metric of described reference state is initialized as 0, the cumulative metric of all the other states is initialized as the negative minimum value that the data format of corresponding cumulative metric is represented.

6. a decoder is characterized in that, comprise the VA algoritic module, search module, recall module, state selects module and comparison module,

Described VA algoritic module is used for sequence to be decoded is carried out the VA algorithm;

The described module of searching is used for finding out default several bigger cumulative metrics from the cumulative metric of all states, and writes down the done state of described cumulative metric;

Describedly recall module, be used for done state is recalled;

Described state is selected module, is used for determining reference state;

Described comparison module, whether with described reference state identical, and determine the decoding sequence according to comparative result if being used for the corresponding done state of comparison and described reference state.

7. decoder as claimed in claim 6 is characterized in that, described VA algoritic module also is used for the cumulative metric of each state of initialization.

8. decoder as claimed in claim 6 is characterized in that, the described module of searching comprises and choose submodule and record sub module,

The described submodule of choosing is used for finding out default several bigger cumulative metrics from described all cumulative metrics;

Described record sub module is used to write down the done state of the described cumulative metric of finding out.

9. decoder as claimed in claim 6 is characterized in that, described state selects module to comprise to judge submodule and reference state to determine submodule,

Described judgement submodule is used for judging whether all initial states have the initial state that repeats;

Described reference state is determined submodule, is used for the judged result according to described judgement submodule, determines reference state.

10. as claim 6,8 or 9 described decoders, it is characterized in that described comparison module comprises that state contrasts submodule, the decoding sequence is determined submodule,

Described state contrast submodule, whether be used for the corresponding done state of comparison and described reference state identical with described reference state;

The decoding sequence is determined submodule, is used for the comparative result according to described state contrast submodule, determines the decoding sequence.

Images