CN102655415B - A kind of Viterbi decoding device and method - Google Patents

Abstract

A kind of Viterbi decoding device, comprise input-buffer and selected cell, branch metric unit, Jia-ratio-menu unit, path metric memory unit, path survivable memory unil, trace unit, described device also comprises: signal reliability test cell, for outputing signal reliability data to signal testing; Code element expanding element, for according to described signal reliability data, calculates the Baud Length needing expansion, and described Baud Length is outputted to described input-buffer and selected cell and described trace unit, expands for code element.After adopting technical scheme of the present invention, effectively can improve the error correcting capability to burst error code; The method is by force pointed, adjusts in real time, simple to operate, the advantage easily realized.

Description

A Viterbi decoding device and method

technical field

The invention relates to a Viterbi decoding device and method, in particular to a device and method for improving the error correction capability of Viterbi truncated decoding.

Background technique

Channel coding is an effective method for the reliability of digital communication systems. Viterbi decoding is mainly a decoding technology for channel coding such as convolutional codes. Its basic idea is to compare the received sequence with all possible transmitted sequences, and choose The transmitted sequence with the minimum Hamming distance from the received sequence is output as the decoded sequence. This kind of decoding has a good error correction ability for discrete random error codes, and has limited error correction ability for continuous burst error codes. The best Viterbi decoding performance is after the entire frame, that is, after all information has been received. Then find the best path as the decoding result, but when the sending sequence is long, the required storage capacity is large, and the decoding delay is too long, which cannot meet the requirements of real-time communication. Therefore, the actual implementation of Viterbi decoding usually adopts the method of truncated decoding, that is, when the length of the path stored in the decoder reaches a specified decoding depth L, the path with the smallest measure is selected as the survival path, and Output the corresponding information symbols according to the encoding rules, and then calculate the surviving path of the next level of L depth, the convolution form of (n, k, N) (k is the number of input binary information symbols in each group, and n is In terms of the number of encoded output group symbols, N is the constraint length), usually L>5KN-1 (L is an integer multiple of k). The basic method is shown in Fig. 1, each functional unit cooperates to realize Viterbi truncated decoding, wherein the backtracking length is the decoding depth L.

The truncated decoding method divides a long series of input sequences into several segments, which increases the error probability for the decoding of adjacent segment sequences. In practical applications, it is found that when there is a sudden error code that can be corrected for the whole frame decoding at the connection point, the truncation decoding method cannot guarantee the accuracy of the result at this point. In the form of (2,1,7) convolutional code, the frame length is 550, and the decoding depth is 35. The end positions of the paragraphs into which the long input sequence in the Viterbi decoder is divided are 70 and 140 respectively. , 210, 280..., when a burst error code occurs near these end positions (the burst error code is within the tolerance range of the Viterbi full-frame decoding in the (2,1,7) convolution form), it will be in the final Error decoding occurs around 35, 70, 105, 140... of the resulting sequence. Although the probability of burst error codes at the junction is not very high, when the number of separated sequences increases, the probability of decoding errors will increase accordingly, which is not conducive to the large-scale and high-efficiency of Viterbi truncation decoding. application.

The application number is 02121004.7, and the publication number is CN1159933C. The general-purpose Viterbi decoder designed in the Chinese invention patent "Universal Convolutional Encoder and Viterbi Decoder" is to add a control unit on the basis of accompanying drawing 1, Parameters can be configured for frame length, code rate, constraint length, generator polynomial, and channel type to truly achieve versatility. It is mentioned that "a threshold comparison circuit is set at the decoder interface circuit. When the frame length is lower than a certain When a threshold is reached, the end decoding algorithm is used, and when the frame length exceeds a certain threshold, the truncated decoding algorithm is used", but the shortcomings and solutions of the truncated decoding algorithm at the connection are not proposed.

Contents of the invention

The purpose of the present invention is to provide a method for eliminating burst interference at the junction in the Viterbi truncated decoding mode, through the form of the decoded convolutional code (n, k, N) and the reliability of the input signal, adaptive Determine the length of the extended symbol, and then adjust the processing methods of the input buffer and selection unit, the path metric storage unit, and the backtracking unit according to the length of the extended symbol, so as to avoid the error decoding caused by the burst error code at the connection point and improve the Viterbi interception rate. The short decoding performance achieves a decoding effect equivalent to Viterbi whole frame decoding.

The present invention provides a Viterbi decoding device, comprising an input buffer and selection unit for receiving data input and a signal clock; a branch measurement unit for dividing the output data of the input buffer and selection unit into different branches and calculating Path metric value; add-comparison-selection unit, for accumulating the path metric value output by the branch metric unit, to select a surviving path; path metric storage unit, for storing the path metric output by the add-comparison-selection unit value, and return to the addition-comparison-selection unit to do the initial value of accumulation; the survival path storage unit is used to store the survival path selected by the addition-comparison-selection unit; the backtracking unit is used to Among the surviving paths output by the surviving path storage unit, select the best path, and perform backtracking processing, and output the decoding result; the device also includes: a signal reliability testing unit, which is used to test the signal and output the signal reliability degree data; a symbol extension unit, used to calculate the symbol length that needs to be extended according to the signal reliability data and the convolutional code form, and output the symbol length to the input buffer and selection unit and the The backtracking unit is used for code element expansion.

Furthermore, the signal reliability testing unit detects the input signal in real time, and outputs the signal reliability data.

Furthermore, the signal reliability testing unit detects the decoding result of the traceback unit in real time, and outputs the signal reliability data.

Furthermore, the input buffer and selection unit divides the input whole frame data into lengths according to the convolution form of Viterbi decoding (n, k, N), the symbol length M, and the traceback length L sequence of paragraphs.

Furthermore, the input data frame length is less than , the end decoding algorithm is directly adopted.

Furthermore, the last extension of P symbols in each of the paragraph sequences, , and the extended P symbols of the previous sequence are simultaneously used as the P symbols at the beginning of the next sequence.

Furthermore, the number of states of the add-comparison-selection unit and the number of branch units of the add-comparison-selection are both 2 ^K(N-1) , and the add-comparison-selection unit performs a possible path metric at each state Accumulate, and select the path at the minimum metric as the surviving path of this state.

Furthermore, the path metric storage unit records the path metric value at the moment when the stored path length is equal to the backtracking length, and sends it back to the add-compare-select unit as an initial value when the next sequence starts.

Furthermore, according to the symbol length of the symbol extension unit, when the path storage length reaches L+M, the backtracking unit marks that the decoding of this paragraph sequence is completed, and starts to select in the survivor path storage unit The path with the smallest metric value is regarded as the best path, and the first L-length sequence of the best path is selected as the decoding result of this paragraph and output.

Furthermore, the device also includes a parameter configuration and control unit, configured to receive configuration parameter information, the parameters include frame length, convolutional code format and backtracking length, and for the input buffer and selection unit, the branch metric unit, the add-compare-select unit, the symbol extension unit and the traceback unit perform initialization operations.

The present invention also provides a Viterbi decoding method, the method comprising:

Step 1, performing signal reliability detection;

Step 2, determine the extension symbol length M;

Step 3, performing truncation processing on the input data according to the convolutional code form (n, k, N), the symbol length M and the backtracking length L;

Step 4, determine whether the input data frame length is greater than , yes, then proceed to step five, if not, then jump to step nine after the end decoding is performed on the data;

Step 5, perform branch metric calculation;

Step 6: Carry out add-comparison-select operation in a loop, and store the result until the storage length of the path is L+M, then go to step 7;

Step 7, judging the best matching path among all storage paths, and backtracking the sequence of length L before the best matching path as the decoding result;

Step 8, judge whether the entire frame of data is completed, if yes, then jump to step 9, if not, then jump to step 1, and the addition-comparison-selection unit described in step 6 takes the last round of path storage length as L The stored value of is used as the initial value;

Step 9, the decoding is completed, and the result is output.

Furthermore, the signal reliability detection in the first step is to perform real-time detection on the input data, and output signal reliability data.

Furthermore, the signal reliability detection in the first step is to perform real-time detection on the decoding result, and output signal reliability data.

In a further step, before the first step, a parameter configuration step is added, and corresponding parameters are configured according to control requirements.

Further, the parameters include frame length, convolutional code form (n, k, N) and traceback length L.

After adopting the technical scheme of the invention, the error correction capability for burst error codes can be effectively improved; the method has the advantages of strong pertinence, real-time adjustment, simple operation and easy realization.

Description of drawings

Fig. 1 is a functional unit block diagram of a traditional Viterbi decoder;

Fig. 2 is a kind of Viterbi decoder functional unit block diagram of the embodiment of the present invention;

Fig. 3 is a schematic diagram of data segmentation according to an embodiment of the present invention;

Fig. 4 is a flow chart of data processing according to an embodiment of the present invention;

Fig. 5 is a kind of Viterbi decoder functional unit block diagram of the embodiment of the present invention;

Fig. 6 is a kind of Viterbi decoder functional unit block diagram of the embodiment of the present invention;

Fig. 7 is a flow chart of data processing in an embodiment of the present invention;

Fig. 8 is a comparison diagram of simulation test performance of the present invention.

detailed description

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention.

Based on the traditional Viterbi decoding operation, the present invention adds signal reliability testing and symbol extension functional units. The specific implementation includes Viterbi decoding for a specific (n, k, N) convolution form. The code can be arbitrarily configured (n, k, N) general-purpose Viterbi decoding; the implementation mode with the reliability detection of the preamble signal, the implementation mode with the reliability detection of the feedback signal, etc. Those skilled in the art will recognize that many alternative embodiments can be accomplished using the aspects of the present invention and that the invention is not limited to the embodiments illustrated for explanatory purposed.

First embodiment of the present invention:

Accompanying drawing 2 is the improved Viterbi decoding functional block diagram for a specific (n, k, N) convolution form, and the backtracking length is set as L, and 201 is a signal reliability testing unit; 202 is a symbol extension unit, 203 204 is a branch metric unit, 205 is an add-compare-select unit, 206 is a path metric storage unit, 207 is a survivor path storage unit, and 208 is a backtracking unit. It is assumed here that the specific convolutional code is in the form of (2,1,7), and the traceback length L is set to 35.

The specific working principle and technical points are:

The signal reliability testing unit 201 will detect the signal in real time during the whole frame data input process, mainly for continuous burst error codes, to obtain the signal reliability index;

The symbol extension unit 202, according to the convolutional code form (n, k, N) and the received signal reliability index (mainly the number of symbols X of continuous burst error codes), can adaptively adjust the required extension The symbol length M, the adjustment process follows the formula (1):

(1)

In formula (1), Xmax is the maximum number of burst errors that can be tolerated when the Viterbi full-frame decoding method is adopted for convolutional codes of the form (n, k, N). Once the signal reliability is relatively poor, the burst error When the number of codes exceeds Xmax, the error code cannot be corrected even if the whole frame is decoded, which is the limit of the error correction capability of Viterbi decoding. Therefore, the extended code length method mentioned in the present invention also has the same upper limit. When X>Xmax, how the value of M changes can no longer realize the correction of burst error codes, so M=0. For the convolutional code form (2,1,7) in this example, there is an adjustment rule of M, as shown in formula (2):

(2)

Input buffering and selection unit 203 divides the whole frame data of input into paragraph units with a length of 2 (35+M) according to the extended symbol length M, and can realize the data transmission mode shown in Fig. 3 , the extended in each segment sequence The last 2M code elements will not be lost, but will be decoded again as the first 2M code elements in a subsequent sequence, as shown in FIG. 3 .

The branch metric unit 204 forms different branches according to different convolution forms, and calculates each possible metric value (ie code distance) according to the corresponding branch metric calculation formula;

Add-comparison-selection unit 205, for a convolutional code with a constraint length of N, its number of states is 2N-1, and the number of states of a convolutional code in the form of (2,1,7) is 64, and this unit has a pair of sums of states The addition-comparison-selection branch unit can read the path metric result of the last corresponding branch from the path storage unit 206 as an initial value, accumulate the possible path metrics at each state, and compare and select the minimum path metric, and keep this path as the surviving path for that state;

The path metric storage unit 206, in addition to storing the path metric values corresponding to each state at each time obtained in the traditional method, and sending back to the addition-comparison-selection unit to do the initial value of the next accumulation, in order to cooperate with the present invention For the mentioned scheme, the unit also needs to add a fixed-point recording function. The specific method is to open up a separate area when the length of the storage path reaches the original backtracking length L=35, and record the path metric value at the moment. This record value When the next truncated sequence starts to decode, send it back to the add-comparison-select unit as the initial value;

The surviving path storage unit 207 stores the surviving paths corresponding to each state, and the upper limit of the record length should be consistent with the extended backtracking length 35+M;

Backtracking unit 208 increases the originally specified backtracking length L=35 to 35+M according to the symbol extension length M, and when the path storage length reaches 35+M, it indicates that the 2 (35+M) paragraph sequence decoding is completed , start to select the path with the smallest path metric value as the best path among the surviving 2N-1=64 paths, and perform backtracking processing, but the difference is that the length of the backtracking is not carried out according to the extended 35+M, but Take the first 35 length sequences of the best path as the decoding result of this paragraph and output it.

The data processing flow is shown in Fig. 4, and it should be pointed out that the end decoding method can be used when performing forward sequence decoding.

Second embodiment of the present invention:

The method of the present invention is not limited to the Viterbi decoding of a specific convolutional code form, and corresponding functional units can be added to make the method applicable to a general Viterbi decoder. Accompanying drawing 5 provides an improvement The block diagram of the functional units of the general Viterbi decoder.

Compared with the first embodiment, a parameter configuration control unit 501 is added to receive the configured parameter information to make the entire Viterbi decoder complete the initialization operation.

The specific working principle is:

In this scheme, the frame length, convolutional code form (n, k, N), and the original backtracking length L are configured. The parameter configuration and control unit 501 receives the configuration information of these parameters and sends it to the corresponding unit. And participate in the control of its completion initialization operation: the symbol extension unit 503 determines the extension length M, which needs to be based on the reliability of the signal and the convolutional code form (n, k, N) of the configuration; the truncation of the entire frame by the input buffer and selection unit 504 The operation needs to be based on the configured convolutional code form (n, k, N), the original backtracking length L and the extended symbol length M; the branch measurement unit 505 and the addition-comparison-selection unit 506 are based on different convolutional code forms (n, k, N) will have a corresponding set of branch and path metric calculation methods; the backtracking length of the backtracking unit 509 is determined by the configured original backtracking length L and extended length M. In this way, each unit has completed the initialization operation relative to the convolutional code form (n, k, N) in the configuration information, and becomes Viterbi decoding for the convolutional code (n, k, N) form device.

The data processing flow is the same as that of Fig. 4 in the first embodiment.

The third embodiment of the present invention:

In addition to the implementation with preamble reliability detection in the above embodiments, the implementation with feedback signal reliability detection can also be used, as shown in FIG. 6 .

The specific working principle is:

In Viterbi truncated decoding, when the decoding of a certain segment is completed and the L-length result is output, the signal reliability test analysis is performed according to the decoding result of the segment, and the test result is fed back to the symbol expansion unit 608, and then combined with the convolution Code form (n.k, N), adaptively adjust the extension length M, so that the input buffer and selection unit 601 adjusts the truncated paragraph length according to the new M value, and the backtracking unit 606 sets a new backtracking control length L+M, and then starts The decoding operation of the next paragraph.

The data processing flow is shown in Fig. 7, and it should be pointed out that the end decoding method can be used when performing forward sequence decoding.

Accompanying drawing 8 shows that under the (2,1,7) convolutional code form, the traditional Viterbi truncated decoding method and the improved truncated decoding method of the present invention become more and more Simulation results of decoding accuracy under strong (signal reliability is getting worse) conditions, and the comparison with the whole frame decoding method.

In the simulation, the length of one frame of data is set to 550 bits, and the backtracking length L of truncated decoding is set to 35, respectively simulating the input signals under different sudden interference (especially interference at the junction) scenarios, and its reliability gradually decreases , count the accuracy rate of the final 275bit decoding result, and take the average after several statistics, and draw the graph in Figure 8. It can be seen that the traditional Viterbi decoding method simply truncates a frame sequence into 70-bit paragraphs for decoding, and outputs 35-bit results each time. When the sudden interference at the junction becomes stronger and the signal reliability decreases, the decoding is accurate. degree is obviously decreased, which is far inferior to the performance of whole frame decoding; and the truncated decoding method proposed by the present invention, for different signal reliability, the extension code length M changes accordingly, and each input paragraph becomes 2(35+M )bit, only the first 35 bits in the decoding result are taken. After this operation, the accuracy of the final 275-bit decoding result is basically the same as the whole frame decoding method, which shows the superiority of this scheme in dealing with burst error codes. In addition, when the reliability of the signal drops below the tolerable limit of the entire frame decoding, the accuracy of several decoding methods is relatively low and tends to be consistent.

This method can eliminate the impact of sudden interference at the connection point during Viterbi truncated decoding, improve the decoding accuracy, and make up for the defects of the truncated decoding method when correcting burst error codes; and can according to the quality of the signal, Adaptive adjustment, more convenient and efficient.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention should be included in the protection of the present invention. within range.

Claims (15)

1. A Viterbi decoding device comprises an input buffer and a selection unit, which is used for receiving data input and a signal clock; the branch measurement unit is used for dividing the output data of the input buffer and selection unit into different branches and calculating a path measurement value; the adding-comparing-selecting unit is used for accumulating the path metric values output by the branch metric unit and selecting a survivor path; a path metric storage unit for storing the path metric value output by the add-compare-select unit and returning the path metric value to the initial value accumulated by the add-compare-select unit; a survivor path storage unit, configured to store the survivor path selected by the add-compare-select unit; the backtracking unit is used for selecting an optimal path from the survivor paths output by the survivor path storage unit, performing backtracking processing and outputting a decoding result; characterized in that the device further comprises: the signal reliability testing unit is used for testing signals and outputting signal reliability data; the code element expansion unit is used for calculating the code element length to be expanded according to the signal reliability data and the convolutional code form, and outputting the code element length to the input buffer and selection unit and the backtracking unit for code element expansion; the convolutional code is in the form of (N, k, N); the calculation of the symbol length follows the following formula:

wherein,Xthe number of symbols of the continuous burst error code;X _max the maximum burst error code number which can be tolerated when the convolutional code of the (N, k, N) form adopts a Viterbi whole frame decoding mode is adopted.

2. The viterbi decoding apparatus according to claim 1, wherein the signal reliability test unit detects an input signal in real time and outputs the signal reliability data.

3. The viterbi decoding apparatus according to claim 1, wherein the signal reliability testing unit detects the decoding result of the trace-back unit in real time, and outputs the signal reliability data.

4. The viterbi decoding apparatus according to claim 1, wherein the input buffer and selection unit divides the input entire frame data into data having a length of M according to a convolution form of viterbi decoding (N, k, N), the symbol length M, and a trace-back length Ln/K*(L+M)A sequence of paragraphs of (a).

5. Viterbi decoding apparatus according to claim 4, wherein the input data frame length is smaller thann/K*(L+M)Then the trailing decode algorithm is directly employed.

6. Viterbi decoding apparatus according to claim 4 wherein the last P symbols of the last extension of each of the sequence of segments,P=n/K*Mand P code elements of the spread sequence of the previous section are simultaneously used as P code elements of the beginning of the sequence of the next section.

7. Viterbi decoding apparatus as claimed in claim 1 or 4, wherein the number of states of the add-to-list unit and the number of the add-to-list unit are both 2^K(N-1)The add-compare-select unit accumulates the possible path metrics at each state and selects the path at the minimum metric as the survivor path for that state.

8. Viterbi decoding apparatus as claimed in claim 1 or 4, wherein the path metric storage unit records the path metric value at the moment when the stored path length is equal to the trace-back length, and returns the value to the plus-minus-one unit as an initial value at the start of the next segment sequence.

9. The viterbi decoding apparatus according to claim 4, wherein the trace-back unit marks that decoding of the sequence of the current segment is completed when the path storage length reaches L + M according to the symbol length of the symbol extension unit, and starts to select the sequence of the first L length of the best path as the best path in the survivor path storage unit, and selects the sequence of the first L length of the best path as the decoding result of the segment to be output.

10. The viterbi decoding apparatus according to any one of claims 1 to 5, further comprising a parameter configuration and control unit configured to receive configuration parameter information, where the parameters include a frame length, a convolutional code form, and a trace-back length, and perform initialization operations on the input buffer and selection unit, the branch metric unit, the add-compare-select unit, the symbol extension unit, and the trace-back unit.

11. A viterbi decoding method, characterized in that the method comprises:

step one, detecting signal reliability;

step two, determining the length M of the extended code element;

truncating input data according to a convolutional code form (N, k, N), a code element length M and a backtracking length L;

step four, judging whether the frame length of the input data is larger than that of the input data framen/K*(L+M)If yes, performing the fifth step, if not, performing ending decoding on the data, and then jumping to the ninth step;

step five, branch measurement calculation is carried out;

step six, circularly performing the adding-comparing-selecting operation, storing the result, and turning to the step seven until the path storage length is L + M;

step seven, judging the best matching path in all the storage paths, and backtracking the sequence of the front L length of the best matching path as a decoding result;

step eight, judging whether the whole frame data is finished, if so, jumping to the step nine, if not, jumping to the step one, and if so, taking a stored value with the path storage length L in the previous round as an initial value in the adding-comparing-selecting operation in the step six;

step nine, decoding is finished, and a result is output;

wherein the calculation of the symbol length M follows the following equation:

wherein,Xthe number of symbols of the continuous burst error code;X _max the maximum burst error code number which can be tolerated when the convolutional code of the (N, k, N) form adopts a Viterbi whole frame decoding mode is adopted.

12. The viterbi decoding method according to claim 11, wherein the signal reliability detection in the first step is a real-time detection of the input data and outputs signal reliability data.

13. The viterbi decoding method according to claim 11, wherein the signal reliability detection in the first step is a real-time detection of the decoding result, and outputs signal reliability data.

14. The viterbi decoding method according to any one of claims 11 through 13, wherein a parameter configuration step is added before the step one, and corresponding parameters are configured according to a control requirement.

15. The viterbi decoding method according to claim 14, wherein the parameters include a frame length, a convolutional code form (N, k, N), and a trace-back length L.