KR100302032B1 - Error correction decoder and error correction decoding method - Google Patents

Abstract

An error correction decoder for performing a Viterbi decoding on an input digital signal using a Viterbi algorithm, comprising: a flag signal at a first position where a difference between path metrics in the Viterbi algorithm is lower than a threshold; Flag signal adding means for continuously adding a flag signal and continuously adding a flag signal to positions preceding the first position determined by trace back; An error correction decoder having a block code decoder for block code decoding the Viterbi decoded signal is disclosed by considering the positions added with the flag signal by the flag signal adding means as the lost positions.

Description

Error correction decoder and error correction decoding method

The present invention relates to a decoder for correcting errors occurring in digital wireless communication and the like.

FIG. 20 is a block diagram of a conventional concatenated code error correction decoder described in Japanese Patent Laid-Open No. 5-235784, where 101 is an RS for adding a check symbol of a RS (Reed Solomon) code to information. An encoder, 102 is a first deinterleaver for deinterleaving RS encoded data transmission order, 103 is a convolutional encoder for convolutional encoding of output data of the first deinterleaver 102, 104 is a transmission path for transmitting data, 105 Is a convolutional decoder that convolutionally decodes the output and outputs data reliability information, 106 is a second deinterleaver which deinterleaves the output data output from the convolutional decoder 105, and 107 is a convolutional decoder 105 A comparator for comparing the reliability information output from the threshold and the threshold value, 108 is a third deinterleaver to deinterleave the output signal of the comparator 107, 109 is the output signal of the third deinterleaver 108 A flow generating position information and a RS decoder for outputting the decoded data to the output data of said second deinterleaver (106) RS.

Next, the operation will be described. In the following operation, the operation of the signal received through the transmission path 104 will be described. First, a path is selected by the convolution decoder 105 to output a convolutionally decoded bit sequence. At this time, a value of a path metric accompanying the final output data is output as reliability information, and the value and a predetermined threshold are compared by the comparator 107. When the reliability information is smaller than the threshold, the corresponding output code is considered lost. Then, the second deinterleaver 106 operates the deinterleave of the decoded data output from the convolutional decoder 105, deinterleaves the loss information in the third deinterleaver 108, and removes the loss in the RS decoder 109. The error correction operation is used to output the result.

Since the conventional error correction decoder of the concatenated code is configured as described above, as a result of convolutional decoding, all of the convolutional decoding results in loss, even if the reliability is high. There was a problem of not being able to correct the loss efficiently.

SUMMARY OF THE INVENTION The present invention has been made to solve the above problems, and in the decoding operation of an outer code, by adding a flag only to a result that assumes that the Viterbi decoded result is likely to be wrong, the ratio of the missing symbols can be reduced. It is an object to obtain an error correction decoder with improved error correction capability.

An error correcting decoder of a concatenated code according to the present invention includes Viterbi decoding means for decoding an input digital signal by including reliability information in a Viterbi algorithm, and block code decoding means for obtaining a decoding result by decoding operation of a block code. In the error correction decoder, a flag is added to a corresponding position when the difference between path metrics by the Viterbi algorithm is lower than a set value, and a flag is added to a predetermined continuous position before the flag position after the traceback is determined. The signal portion is provided with means, and in the block code decoding means, the position where the flag is successively added is assumed to be the information loss position so as to perform block decoding.

In addition, the input digital signal is a code having a plurality of bits as one symbol, and the decoding of the block code is a Reed Solomon (RS) code decoding means in units of symbols. If any one of the symbols has a flag, the symbol is lost. RS code decoding is performed at the position.

An error correcting decoder of a concatenated code according to the present invention includes Viterbi decoding means for decoding an input digital signal by including reliability information in a Viterbi algorithm, and block code decoding means for obtaining a decoding result by decoding operation of a block code. In the error correction decoder, reliability generation means for obtaining and determining reliability information based on a difference of a pass metric after determining with traceback by decoding by a Viterbi algorithm, and having reliability at bits with low reliability obtained by the reliability generation means The block-code decoding of the outputs of the plurality of bit inverting means for selecting and inverting bits by lowering a predetermined number of different numbers and the number of bit inverting means for inverting different numbers of bits is performed. Decoding output to select as decoding output And it has a select means.

1 (a) and 1 (b) are diagrams showing the operation flow and configuration of the error correction decoder of the concatenated code according to the first embodiment.

2 (a) to 2 (d) show trellis diagrams, bit strings, and flag strings for explaining the operation of the apparatus having the configurations of FIGS. 1 (a) and 1 (b).

3 (a) and 3 (b) show the operation flow and configuration of the error correction decoder of the concatenated code in the second embodiment.

4 (a) to 4 (e) show a flag string for explaining the operation of the apparatus having the configurations of FIGS. 3 (a) and 3 (b).

5 (a) and 5 (b) show the operation flow and configuration of the error correction decoder of the concatenated code in the third embodiment.

6 (a) and 6 (b) show the operation flow and configuration of the error correction decoder of another concatenated code according to the third embodiment.

7 (a) and 7 (b) show the operation flow and configuration of the error correction decoder of the concatenated code in the fourth embodiment.

8 (a) to 8 (d) are diagrams for explaining the operation of the reliability generating means of FIGS. 7 (a) and 7 (b).

9 (a) and 9 (b) show the operation flow and configuration of the error correction decoder of another concatenated code according to the fourth embodiment.

10 (a) and 10 (b) show the operation flow and configuration of the error correction decoder of the concatenated code of the fifth embodiment.

11 (a) and 11 (b) show the operation flow and configuration of the error correction decoder of another concatenated code according to the fifth embodiment.

12 is an operation flowchart of an error correction decoder of a concatenated code according to the sixth embodiment;

Fig. 13 is a configuration diagram of an error correction decoder of concatenated codes according to the sixth embodiment.

14 is a flowchart of operation of the error correction decoder of the concatenated code according to the seventh embodiment.

Fig. 15 is a flowchart of operation of the error correction decoder of the concatenated code of the eighth embodiment.

Fig. 16 is a flowchart of operation of the error correction decoder of the concatenated code according to the ninth embodiment.

17 is an operational flowchart of an error correction decoder of another concatenated code according to the ninth embodiment;

18 (a) and 18 (b) show the operation flow and configuration of the error correction decoder of the concatenated code of the tenth embodiment;

19 (a) and 19 (b) show the operation flow and configuration of an error correction decoder of another concatenated code of the tenth embodiment;

20 is a block diagram of a conventional error correction decoder of a concatenated code.

* Explanation of symbols for main parts of the drawings

1: demodulation means 2: Viterbi decoding means

3: flag signal adding means 4: deinterleaver

5: block decoding means 6: symbol segmentation means

7: RS code decoding means 8: CRC checking means

9: flag signal adding means 10: reliability generating means

11: flag signal adding means 12a, 12b, 12c: bit inverting means

13 decoding means selection means 14 symbol reliability generating means

15: symbol flag adding means 16: flag checking means

17 cell generation means 18 cell reception discard inspection means

19: flag signal adding means

Embodiment 1

A concatenation code error correction decoder in Embodiment 1 of the present invention will be described.

The main gist of the present invention is based on the result of analyzing the fact that the degradation of the reliability in Viterbi decoding. In other words, the occurrence of a low-reliability part in the trellis diagram of Viterbi decoding is not only caused by the path at the point of occurrence, but also by the next several passes, so all of these low-reliability paths are flagged. It is thought that it is better to decode and decode them as being lost positions in the decoding of the outer code to obtain a good decoding result.

FIG. 1 (a) shows the operation flow and device configuration of the error correction decoder of this embodiment. In FIG. 1 (b), 1 is demodulation means, 2 is Viterbi decoding means as an inner decoder, 3 is flag element adding means which is a new element, 4 is a deinterleaver to deinterleave the output of Viterbi decoding, 5 is an outer Block code decoding means as a decoder.

2 (a) to 2 (d) show a trellis diagram showing a state of state transition for explaining the operation by the constituent devices of FIGS. 1 (a) and 1 (b). It is explanatory drawing. In FIG. 2 (a), the thick line is the path determined by the trellis back, and the black circle indicates the position where the flag is added because the difference of the path metric (cumulative metric-cumulative metering) is smaller than the set value. In addition, this trellis diagram shows that four states can be taken at each position.

Next, the operation will be described with reference to the first (a), the first (b) and the second (a) to the second (d).

When the constituent device of FIG. 1 (b) receives the signal in step S1 (described later in step 1) of FIG. 1 (a), in S2, the soft decision information of each bit is generated by the demodulation means. do. S3 is a step of selecting an input path having high reliability in line correspondence of the input side at each position of FIG. 2 (a) by the pass metric by Viterbi decoding. In the example of FIG. (b) outputs a bit string. Similarly, S4 is a step of adding a flag of low reliability to the position when it is lower than the set value with the difference of the path metric, and is added to five black circles in FIG. 2 (a). S5 is a step of tracing back to Viterbi decoding. The hard decision information is determined by this step processing, that is, the most likely path is selected and determined as one. In this way, the thick line path of FIG. 2 (a) is determined. As a result, the flag output corresponding to the position with low reliability becomes as shown in FIG. 2 (c).

In Viterbi decoding, the small difference in the path metric is low, not only because of the previous pass, but also because of the accumulated result from the previous state. That is, S6 is a step of continuously adding a flag from each position with a flag to a predetermined retroactive position in the flag signal adding means 3 which is a new element. Where it is retroactively varies from case to case, in Figs. 2 (a) to 2 (b), a flag is added to the two-path correspondence to the flag "A", for example, for the "A" position. A total of three flags are added for the position preceding in "A". In other words, because the judgment is staggered at the previous branch, the confidence level is already low at the branch point “I”. In this way, the output of FIG. 2 (d) is obtained.

S7 is a step of changing the order in the deinterleaver 4, and S8 is a step of block decoding the input of the second (d) degrees consecutively in the block decoding means 5 with the flag position as the lost position. The decoding result is obtained (S9).

This adds a flag only to bits that are likely to be wrong, thereby increasing the effect of outer code decoding.

Embodiment 2

3 (a) and 3 (b) show the operation flow and device configuration of the error correction decoder in this embodiment. In FIG. 3 (b), 6 is symbol dividing means for dividing information into symbols consisting of a plurality of bits, and 7 is decoding means in a Reed Solomon (RS) code. The other elements, the demodulation means 1, the Viterbi decoding means 2, the flag signal adding means 3, and the deinterleave 4 are the same as those in the first embodiment. 4 (a) to 4 (e), the third (a) and the fourth (a) of FIG. It is a figure which illustrates the process by the apparatus of FIG. a) and (b).

The operation of the configuration device will be described.

Up to the deinterleaver 4 operates as in the first embodiment. That is, from S1 to S7, soft decision information is generated, the path is selected by the path metric, and the flag is positioned at the position where the difference of the path metric is less than the set value, the trace back is selected by one pass, and the predetermined number of flags are added to the preceding position. do. In this way, the output is divided in symbol units in R18. In the examples of Figs. 4 (a) to 4 (e), the symbols of (d) are obtained in comparison with the flag states of Fig. 4 (c). Next, in the RS code decoding means 7, if there is a flag even in one bit among the symbols separated by every three bits as S19, the flag is added because the symbol is low in reliability, and thus the lost position is set. In this way, even if the symbol including several preceding flags is continuously lost, the symbol to which the flag of FIG. 4 (e) is added is externally decoded by the RS code to obtain a decoding result (S20).

As in the first embodiment, since a flag is added to a symbol that is likely to be wrong, the decoding effect of an outer code is increased.

Embodiment 3

FIG. 5 (a) shows the operation flow and device configuration of the error correction decoder in this embodiment. This configuration aims at improving the reliability. In FIG. 5 (b), 8 is CRC checking means and 9 is flag signal adding means. The other elements are the same as the corresponding elements of the first embodiment.

The operation of the apparatus of this embodiment is different from the apparatus of the previous embodiment from S1 to S5, but CRC check is performed on the hard decision information generated as indicated by S21 of FIG. 5 (a) after Viterbi decoding. If an error is detected, the flag signal adding means 9 adds a flag to the bit targeted for CRC. Such Viterbi decoding, CRC check, and flag signal addition operations are repeated for the data to be sequentially received, and the deinterleaver 4 changes the order of hard decision information and added flags (S7). With respect to the deinterleaved information, the block code decoding means 5 decodes the outer side by missing the bits to which the flag is added (S9) and outputs the final decoded data (S30).

6 (a) shows the operation flow and device configuration of another error correction decoder of this embodiment. The configuration device of FIG. 6 (b) uses the configuration device of FIG. 5 (b) as error correction for symbol objects.

In this configuration apparatus and its operation, the same elements as in the second embodiment and the fifth embodiment are denoted by the same reference numerals, and the description for each step of the operation flow is also the same as that of the embodiment described so far, and thus the description thereof is omitted. .

This makes it possible to add a flag only to the bit sequence in which an error has occurred reliably, thereby increasing the efficiency of outer code decoding.

Embodiment 4

Fig. 7 shows the operation flow and device configuration of the error correction decoder in this embodiment. In Fig. 7 (b), 10 is reliability generating means and 11 is flag signal adding means. The other elements are the same as the corresponding elements of the first embodiment. 8 (a) to 8 (d) are explanatory diagrams for explaining the operation of the reliability generating means 10, illustrating output bits at respective positions of Viterbi decoding and corresponding information thereafter.

Next, the operation will be described.

The apparatus of this embodiment performs the same operation as the apparatus of the previous embodiment with respect to S1 to S5.

Further, the reliability information shown in S31 of Fig. 7A is generated for the Viterbi decoding result. This means that, for example, the path metric difference of FIG. 8 (b) is obtained compared to the output bit string of FIG. 8 (a). With reliability information p and path metric difference s, in this example, the i-bit reliability information p (i)

p (i) = 0.7s (i) + 0.2s (i-1) + 0.1s (i-2)

When p is obtained, reliability information of FIG. 8 (c) is obtained.

The threshold value of the reliability information, i.e., the value of the following value or less, may vary depending on the situation. In the case of this embodiment, a flag is added to the position information of a predetermined value in S32 of FIG. Thus, the flag string of FIG. 8 (d) is obtained.

9 (a) shows the operation flow and device configuration of another error correction decoder of this embodiment. The configuration device in FIG. 9 (a) is used for error correction of the symbol object.

The operation of the device in this configuration is clear from the description of the device of the embodiment described so far, and thus description is omitted here.

[Embodiment 5]

10 (a) shows the operation flow and device configuration of the error correction decoder in this embodiment. In Fig. 10 (b), 16 is flag checking means. The other elements are the same as the corresponding elements in the above embodiments.

The operation will be described according to FIG. 10 (a). This embodiment combines the apparatus of the first embodiment and the third embodiment. In other words, the first flag is added by the path metric difference in S44, and if it is not a few bits, the first flag is added to the preceding bit by the position determined in S46. If an error is detected by the CRC check in S21, a second flag is added to the bit that is the error target in the CRC check in S47.

The above operation is repeated for the data sequentially received, and the deinterleaver 4 changes the order of the hard decision information and the first and second flags on the result. In the flag check means 16, the bits with both of these flags in S48 are regarded as lost positions because of low reliability. Thus, the block code decoding means 5 decodes the final result.

FIG. 11 (a) shows the operation flow and device configuration of another error correction decoder of the present embodiment. The structural apparatus of FIG. 11 (b) combines the apparatus of Embodiment 2 and Embodiment 3. As shown in FIG.

Therefore, since the operation of the configuration device is apparent from the above operation description and the description of the device of the embodiment described so far, the description is omitted here.

Accordingly, the flag is added only to the ones that are likely to be wrong among the flags added in the third embodiment, and the decoding effect of the outer code is increased.

Embodiment 6

FIG. 12 is a diagram showing the operation flow of the error correction decoder in the present embodiment, and FIG. 13 is a diagram showing the configuration of the apparatus. In Fig. 13, 17 is a cell generation means, 18 is a cell reception discard check means for receiving a cell and checks cell discard on the way, and 19 is a flag signal adding means. The other elements are the same as the corresponding elements in the above embodiments.

The operation of the apparatus of this embodiment will be described with reference to FIG.

In this embodiment, the case where transmission by a cell is performed after the error correction of an internal call is demonstrated. The symbol dividing means 6 in FIG. 13 divides the output bit for each symbol in S49 in FIG. 12, and generates first and second flags for each symbol. Next, the cell generating means 17 collects a plurality of symbols as data in S51 of FIG. 12 to generate and transmit a cell.

The cell reception discard inspection means 18 of FIG. 13 adds a third flag when detecting cell discard in S52 of FIG. In this embodiment, the RS decoding operation is performed at S53 with only the symbol including the third flag of the cell discard as the loss position first, and if it is impossible to correct, the RS decoding is performed at S54 with the symbol flagged at S44 and S47 as the loss position. To operate.

By detecting the cell discard, the error correction effect of the outer code is increased.

[Embodiment 7]

14 shows the operation flow of the error correction decoder of this embodiment.

The configuration of the apparatus of FIG. 14 is the same as that of FIG. 1, but means for calculating a set threshold of reliability information is provided in the flag signal adding means, for example.

The operation of the device will be described including an operation description of the threshold calculation means.

In FIG. 14 showing the operation of the apparatus, in S61, an average value of reliability of a specific bit (e.g., the first n bit) as shown in FIG. 8 (c) is calculated. Similarly, in S62, it is calculated how much the threshold value should be set by the difference of the pass metrics. That is, the value used as a reference | standard of whether to add a flag is determined.

Once the threshold is determined, subsequent operations are the same as in the first embodiment.

Accordingly, it is possible to adjust the number of bits to add a flag according to the communication channel situation and obtain the decoding effect of the outer code.

Embodiment 8

FIG. 15 shows the operation flow of the error correction decoder in this embodiment. The configuration of the apparatus for performing the operation of FIG. 15 is the same as that in FIG.

In Fig. 15 showing the operation of the apparatus, the average value of the reliability of a specific bit (e.g., the first n bits) is calculated, and in S63, for example, when the reliability is low, the length of the position where the preceding flag is added is increased. Set it.

In S63, once the bit length for adding the flag is determined, the subsequent operation is the same as in the first embodiment.

Accordingly, by adding a flag according to the communication path situation, the number of bits can be adjusted and the decoding effect of the outer code can be efficiently obtained.

Embodiment 9

16 shows the operation flow of the error correction decoder of this embodiment.

In Fig. 16, the output bits are divided for each symbol in S64, flags are generated for each symbol, cells are generated for each of a plurality of symbols in S65, and reliability is determined for each cell from, for example, the number of flags in S66.

The RS decoding is operated in S67 in that all of the cells with a certain number or more of flags below the set reliability and the symbols included in the cell discarding generation cells are lost positions for each cell. FIG. 17 is an exemplary diagram of operations performed by another correction decoder in the present embodiment, and is an operational flow in the case of combining the CRC check according to the third embodiment with the present embodiment. If an error is detected in S68, an error detection flag is added.

In S69, the reliability of the cell is generated using the number of flags and the error detection flag for each symbol. Accordingly, it is possible to efficiently decode the outer code simply by transmitting a small amount of additional information.

Embodiment 10

FIG. 18A shows the operation flow and configuration of the error correction decoder in this embodiment. In Fig. 18 (b), 12 is bit inversion means, and 13 is decoding output means for selecting the most likely result from the result decoded by the block code decoding means 5. The other elements are the same as the corresponding elements in the above embodiments.

The operation of the present embodiment and the apparatus will be described using FIGS. 18A and 18B.

From the reception of the input signal to the inner decoding by the Viterbi decoding means 2, that is, from S1 to S5, the operation is similar to that of the device of the other embodiment. Next, in S31, as described in the fourth embodiment, the reliability generating means 10 obtains a reliability calculation result as shown in, for example, the eighth (a) to eighth (d) figures. In this embodiment after rearrangement by the deinterleaver 4, j is the number of bits in which j is selected in order of low reliability information (where 0 ≦ j ≦ minimum distance d). In the step S72 of Fig. 2, bits having low reliability are forcibly bit inverted. At this time, the plural bit inverting means 12a, 12b, and 12c invert the K-1 bit, the K bit, and the K + l bit, respectively, with low reliability. As a result of the decoding by the block code decoding means 5, the decoding output selection means 13 selects the smallest sum of the reliability information of the error-corrected bits as in S74 to make the final decoding result (S80).

19 (a) shows the operation flow and configuration of another error correction decoder of the present embodiment. In Fig. 19 (b), 14 is symbol reliability generating means and 15 is symbol flag adding means. The other elements are the same as the corresponding elements in the above embodiments.

Since the structural apparatus of FIG. 19 (a) combines Embodiment 2 and this Embodiment, description of detailed operation | movement is abbreviate | omitted. In S76, reliability information is generated for each symbol. In S77, a flag is added to the K symbol having low reliability to manipulate decoding of the RS code to generate a decoding candidate.

As a result, since the highest reliability is selected as the codeword from among the decoding candidates of the plurality of outer codes, the decoding effect of the outer code is increased.

As described above, according to the present invention, in Viterbi decoding of an inner code, a flag is added to a position having low reliability, and in decoding of an outer code, the information of these flag positions is manipulated as missing, so that the decoding effect is improved.

In addition, since the CRC is used in combination with another check mechanism, the decoding effect is further improved.

In addition, by selecting a different number of bits with low reliability and forcibly inverting each other to select a result that may be decoded outside, there is an effect of improving reliability.

Claims (3)

An error correction decoder for performing a Viterbi decoding on an input digital signal using a Viterbi algorithm, comprising: a flag signal at a first position where a difference between path metrics in the Viterbi algorithm is lower than a threshold; Flag signal adding means for adding a flag signal and continuously adding a flag signal to positions preceding the first position determined by trace back; And a block code decoder which decodes the Viterbi decoded signal by considering the positions added with the flag signal by the flag signal adding means as the lost positions. The method of claim 1, wherein the input digital signal has a plurality of bits constituting a symbol, the block code decoder performs Reed-Solomon (RS) decoding using the symbol, and at least one of the flag signal Error correction decoder in which the containing symbol is considered a missing symbol. An error correction decoding method for error correcting an input digital signal, comprising: viterbi decoding an input digital signal using a Viterbi algorithm; Selecting a path having a high reliability based on a path metric in the Viterbi decoding step; Adding a flag signal indicating low reliability to a first position where the difference between the pass metrics is below a threshold; Specifying a most reliable path by tracing back using the Viterbi algorithm in the Viterbi decoding step; Continuously adding a flag signal indicating a low reliability to positions ahead of the first position; And performing block code decoding by considering the first position with the flag signal and the positions earlier than the first position with the flag signal as missing positions.

Images