JPH05347564A - Error correction coding/decoding method and device and error correction decoding device - Google Patents

Abstract

PURPOSE:To improve the system adaptability by turning a block code into a punctured code and to attain the use of the punctured code in a coding factor higher than the original block code. CONSTITUTION:An error correction coding device 11 adds an error detection code to the input data and divides this data into plural pieces to turn them into the block codes. Then a bit selection/erasing circuit 15 appropriately erases the coded bits and transmits them. An error correction decoding circuit 12 inserts all combinable bit patterns to the erased bits through a bit inserting circuit 17 and performs the error correction decoding. Then the candidates estimated as the block coding data obtained before erasure of bits are selected and stored by a coding result storage circuit 19. These selected candidates are combined together by a block coding data candidate selection circuit 20 and the error detection code is decoded. Thus it is possible to select the correct decoding data among those candidates.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION The present invention relates to a digital car telephone,
The present invention relates to an error correction code decoding method used for mobile phones and the like.

[0002]

2. Description of the Related Art Generally, a punctured code is a convolutional code which is one of error correction codes, and a code having a low coding rate which is relatively easy to decode is used as an original code and a part of coded bits is cycled. Practical application has been advanced as a code having a higher coding rate, which can be obtained by erasing the code. FIG. 6 is a schematic block diagram of a conventional punctured code error correction code decoding apparatus configured by convolutional code + Viterbi decoding.

First, on the encoding device 1 side, input data is convolutionally encoded by an original code encoding circuit 2, and a part of the encoded data is periodically erased by a bit selection erasing circuit 3 in accordance with an erasing pattern and punctured. It is transmitted as Chad encoded data. Next, when decoding the punctured code on the decoding device 4 side, the dummy bit insertion circuit 5 inserts dummy data into the reception data according to the bit position erased on the transmission side, and After reproducing the data sequence before bit erasing, it is decoded using the Viterbi decoding circuit 6 for original code. In an error correction code decoding device using a punctured code based on such a convolutional code,
Since the coding rate can be freely selected and a high coding rate code can be realized by a relatively easy decoder, it has been used in various communication systems.

[0004]

However, in the above conventional error correction code decoding apparatus, all punctured codes used as error correction codes are convolutional codes,
The Viterbi decoder was used as the decoder. The convolutional code + Viterbi decoder is known as a strong error correction method when performing soft-decision decoding, but in hard-decision decoding, it is always superior in error correction capability to block codes with similar coding rates. It cannot be said that there is. Depending on the condition and the code, the block code is rather superior in performance. Furthermore, the hardware scale of a Viterbi decoder is generally much larger than that of a block code decoder.

However, the punctured code based on the convolutional code allows the coding rate to be freely selected and is well suited to the system, whereas an error correction device using the punctured code based on the block code has been used up to now. There is a problem that the block code is difficult to be used as the error correction code because it is not present.

The present invention solves such a problem, and by performing punctured coding on a block code like a convolutional code, an excellent error correction code that can be used even at a higher coding rate. It is intended to provide a decoding device.

[0007]

In order to achieve the above object, the present invention provides an error correction coding apparatus in which an error detection code is added to input data and then divided into a plurality of blocks for block coding. Further, a part of the coded bits is deleted and transmitted. Also, receiving the above transmitted data,
In the error correction decoding device, a plurality of bit patterns are inserted into the erased bits to decode the error correction code, and among these, candidate data estimated to be block coded data before bit erasure Is selected and the candidate data of each block code is combined to decode the error detection code.

[0008]

According to the present invention, therefore, even an error correction code decoding device using a block code can be used at a higher coding rate than the original code by performing punctured coding, and has high system compatibility. Can have sex.

[0009]

Example 1 First, an outline of the present invention will be described. The punctured block code is a code having a higher coding rate, in which coded bits of the block code are appropriately deleted. On the encoding side, the algorithm of the error correction code decoding method of the present invention is: 1. Add an error detection code to the input data.

2. Divide into a plurality of blocks and perform error correction coding using block codes. 3. Delete any part of the encoded bits and transmit. On the decoding side, 4, all the bit patterns that can be combined with the erased bits of each coded bit are inserted to perform error correction decoding of received data.

5. From the error correction number information or error detection information in each inserted bit pattern at the time of decoding, and the decoding result such as the decoded data, it is estimated that the block coded data is a block coded data before bit erasure. In some cases) may be selected and stored.

6. The error detection code is decoded by combining each block code candidate. 7. Detect correct decoded data from the above candidates.

Next, a first embodiment of the present invention will be described with reference to the drawings. 1A and 1B are diagrams showing an error correction coding / decoding device according to the present embodiment. FIG. 1A shows an error correction coding device and FIG. 1B shows an error correction decoding device. FIG. 2 is a diagram showing a code composed of six Golay codes which are one of block codes and a 7-bit CRC code, as an example of the transmitted code, and FIG. 3 is a flowchart showing the operation of the error correction decoding apparatus in this embodiment. Is.

First, in the error correction coding device 11, in the error detection coding circuit 13, CRC (Cy
clic Redundancy Check) error detection code (Fig. 2)
CRC bit 23) in. Next, after being divided into a plurality of information bits 21 in the error correction coding circuit 14, check bits 22 are added and block coding is performed. Further, the bit selection / erasure circuit 15 erases a part of the coded bits of each block code and transmits it. At this time, the number of bits (P bits) of each block coded bit to be erased in the bit selection erasure circuit 15 is equal to the maximum number of error-correctable bits (C bits) of the block code.
Erase so that the relationship of P ≦ C is established. In this embodiment, both P and C have 2 bits. That is, of the codes having the configuration shown in FIG. 2, the rightmost 2 bits are erased before transmission. In the example shown in FIG. 2, 2 bits are erased from each check code 22 for each Golay code, but information bits 21 may be erased.

Next, in the error correction decoding device 12, for each punctured code obtained from the received data, the erased bit position storage circuit 16 for storing the position of the bit erased by the bit selection circuit 15 and the erased bit position. The bit insertion circuit 17 for inserting bits inserts all bit patterns that can be combined with the erased bits, and then the error correction decoding circuit 18 performs error correction decoding. From the decoding results of the error correction number information, the error detection information, and the decoded data in each inserted bit pattern at this time, candidates that are estimated to be block coded data before bit erasure (that is, the error correction coding circuit 14 , Which is estimated to be the output of the above, and there may be a plurality of candidates) are selected and stored in the decoding result storage circuit 19.

At this time, six block codes B _i (1 ≦
The number of error corrections of i ≦ 6) is C _i (= 2). Here, assuming that the number of erased bits is P _i (= 2), there are 2 ² = 4 dummy bits to be inserted into B _i at the time of decoding, which are (0,0), (0,1). ), (1,0),
It is (1,1).

That is, a bit insertion circuit 17 inserts a bit into 2 erased bits (step 33), the inserted code is Golay-decoded by an error correction decoding circuit 18 (step 34), and this decoding result is decoded. Result memory circuit 1
The data is once stored in step 9 (step 35). This operation is repeated 2 ² = 4 times for each block code. Next, a candidate presumed to be the block coded data before bit erasing in the coding apparatus 11 is selected from the decoding results of the error correction number information, the error detection information, the decoded data, etc. in each inserted bit pattern, and the decoding result It is stored in the storage circuit 19 (step 38). The operation up to this point is repeated by the number of block codes, that is, six times in this embodiment.

Here, the block code before the bit erasure is performed.
The number of candidates presumed to be digitized data is K _iThen each block
K code candidate K_iDecoding error detection code by combining
The total number M of combinations when performing

[0019]

[Equation 1]

[0020] Here, the total number M of combinations is compared with an appropriately set allowable value L (for example, L = 16) (step 41), and when the total number M of combinations exceeds the allowable value L, the error detection code is detected. Stop the operation of selecting the correct decrypted data by decrypting. As a result, it is possible to limit the number of decoding processes and reduce the amount of calculation.
Further, it is possible to limit the occurrence probability of false establishment of the error detection code caused by excessively combining incorrect candidates.

Next, when the total number M of combinations is smaller than the allowable value L, one for each block code from the candidates presumed to be the block coded data before bit erasure stored in the decoding result storage circuit 19. These are taken out and combined (step 43), and CRC error detection is performed in the block coded data candidate selection circuit 20 (step 44). This operation is repeated until correct data appears as a result of the CRC error detection or the total number of combinations is M times, and the correct data is output from the block encoded data candidate selection circuit 20 as decoded data (step 4).
6).

If correct data is not detected despite the above operation for all combinations, the error detection flag is set to 0 for the block code having only a single candidate, and the candidate data is decoded. For a block code having a plurality of candidates, one of these candidate data is appropriately selected, the error detection flag is set to 1, and then output.

In this embodiment, the punctured code of the Golay code is considered. Golay as an example
The (23,12) code is a perfect code with a minimum inter-code distance of 7. For this reason, the decoding side can correct up to 3 bit errors (3C-Golay), but suppress up to 2 bit correction to detect 3 and 4 bit errors (2
C4D-Golay) is also possible. (Table 1)
2 is a table showing the relationship between the erased bits and the decoding result when the Golay code in which 2 bits of the check bits 22 shown in FIG. 2 are erased is corrected by 2 bits, m = 6, P =
2, when C = 2.

[0024]

[Table 1]

Further, (Table 1) shows the error correction for the entire code word when error correction decoding is performed by inserting dummy bits in the erasure bits (P ₁ , P ₀ ) in a state where an error is added to the punctured code. Number, the number of residual error bits, and the decoded output pattern after error correction, where A is the correct answer and B, C, D, and E are the different patterns. However, at the time of input to the block coded data candidate selection circuit 20, these A to E are merely recognized as different patterns, and the respective patterns have not been specified.

In Table 1, the number of error bits is from the error correction coding device 11 to the error correction decoding device 1.
2 means the number of error bits that occurred during transmission. In addition, 0 in the dummy bit inserted in the erased part,
1 indicates that 0 ... Inserted erased transmission data itself (same data as transmission data) 1 ... Inserted erased transmission data itself and inverted data. In addition, 0, 1,
2. Detection means 0 ... no error bit to be corrected 1 ... 1 bit error correction 2 ... 2 bit error correction detected ... 3 bit or 4 bit error detected ..

In Table 1, the number of error bits that occurred during transmission when the block encoded data candidate selection circuit 20 selects transmission data candidates before bit erasing from 2 ² = 4 decoding results Is 0 to 2 bits, the correct answer is uniquely determined from the number of error corrections and the output pattern.
Therefore, in these cases, there is only one transmission data candidate before bit erasure. Therefore, in the case of 2-bit correction, since there is one candidate for any error bit number, the number of combinations M is always 1, and it is not necessary to set the allowable value L.

However, as is clear from (Table 1), although a correct answer is uniquely determined by a 2-bit error, 3
It cannot be distinguished from bit errors. Therefore, in the decoding algorithm shown in FIG.
5) (only once because M = 1 in this case) 2 when NG
B _i (G
When the error detection flag of the olay code) is set to 0, it is expected that the residual bit error rate (BER) will be high as a result because the probability of 3-bit error is high. Therefore, in the decoding algorithm shown in FIG. 3, when the error detection (steps 44 and 45) is NG, the error detection flag of the single candidate B _i selected for 2-bit error correction is set to 1 instead of 0.

Further, (Table 2) is a check bit 2 shown in FIG.
6 is a table showing a relationship between erased bits and a decoding result when correcting a Golay code in which bits are erased by 3 bits,
This is the case when m = 6, P = 2, and C = 3.

[0030]

[Table 2]

In the example shown in (Table 2), when the number of error bits occurring during transmission is 0 or 1 bit, the correct answer is uniquely determined from the number of error corrections and the output pattern. On the other hand, the 2-bit error is indistinguishable from the case of the 3-bit error, and therefore is indicated by A and B. Two output patterns are candidates. Then, in the case where all four output patterns are different and all three bits are corrected, all four patterns are stored as candidates in the decoding result storage circuit 19, and all of them are output to the block encoded data candidate selection circuit 20. .. Further, the maximum combination upper limit L is set appropriately (for example, L = 16).

When the erasure bit position storage circuit 16 and the bit insertion circuit 17 insert all bit patterns that can be combined with the erasure bits, the error correction decoding circuit 18 performs error correction decoding. If the block code is a linear code, in the process of inserting the first bit pattern and calculating the value of the syndrome, the value being calculated is held in the memory or register. Here, the syndrome is an m-dimensional vector defined by s = Hy ^T from the parity check matrix H for the received word y in the code theory. For more details, see "Points of error correction coding technology, published by Japan Industrial Technology Center Co., Ltd., published March 20, 1986, page 22".
It is described in. The Golay code is a linear code, and in the Golay decoding (step 34) shown in FIG. 3, the syndrome s = p ₂₂ α ²² + p ₂₁ α for the received word y = (p ₂₂ p ₂₁ ... P ₁ p ₀ ). ²¹ + ... + p ₀ Calculate α ⁰ . This is a column vector α _^22, ···, p ²² to α ^0, ···, obtained by multiplying the p _0. The column vectors α ²² , ..., α ⁰ are determined by the linear code used. Now, assuming that the erased bits are 2 bits of p ₁ p ₀ , the value s ′ = p ₂₂ α ²² + p ₂₁ α ²¹ + ... + p ₂ α ² during calculation of the syndrome for the received words other than these 2 bits is 4 Inserted bit patterns (p ₁ , p ₀ ) = (0,0), (0,1), (1,0),
It has the same value regardless of (1, 1). Therefore, in the process of inserting the first bit pattern and calculating the value of the syndrome, it is necessary to hold the value s ′ in the middle of calculation in the memory or the register and calculate s ′ again in the other three calculation processes. Therefore, the amount of calculation can be reduced.

(Embodiment 2) FIG. 4 is a block diagram showing a second embodiment of the present invention, in which 50 is an error correction coding apparatus and 51 is an error correction decoding apparatus. Since these configurations are basically the same as the configurations shown in FIG. 1, only different points will be described. That is, the error detection coding circuit 52 and the error correction coding circuit 5 in the error correction coding device 50.
3, the bit selection / erasure circuit 54 corresponds to the error detection coding circuit 13, the error correction coding circuit 14, and the bit selection / erasure circuit 15 in FIG. 1, respectively. Further, the erased bit position storage circuit 56, the bit insertion circuit 57, the error correction decoding circuit 58, the decoding result storage circuit 59, and the block coded data candidate selection circuit 60 in the error correction decoding device 51,
Erase bit position storage circuit 16, bit insertion circuit 17, error correction decoding circuit 18, decoding result storage circuit 19,
This corresponds to the block coded data candidate selection circuit 20.

In this embodiment, according to the error state of the line,
On the encoding side, the error correction encoding control circuit 55 controls the error detection encoding circuit 52, the error correction encoding circuit 53, and the bit selection erasure circuit 54 to erase the erased bit position and erase from the block encoded data. By changing the number of bits, the number of error correction codes used,
It changes the configuration method. For example, when used as a transceiver, when the received data from the transmission side is decoded by the error correction decoding device 51, the line error state is estimated based on the decoding result of the error correction decoding circuit 58. In this case, the decoding result stored in the decoding result storage circuit 59 is sent to the error correction coding device 50 as line error state data. In the error correction coding device 50, the error correction coding control circuit 55 controls the error detection coding circuit 52, the error correction coding circuit 53, and the bit selection erasing circuit 54 based on the line error state data, Error correction coding is performed by any one of a plurality of error correction methods. Further, the information indicating which error correction method has been used is sent to the error correction decoding device 51 together with the transmission data as an error correction method selection signal.

Receiving side, that is, error correction decoding device 51
Then, according to the error correction method selection signal received together with the received data, the error correction decoding control circuit 61 causes the erase bit position storage circuit 56, the bit insertion circuit 57, the error correction decoding circuit 58, the decoding result storage circuit 59, and the block. The encoded data candidate selection circuit 60 is controlled to perform decoding by the decoding method according to the error correction method selected by the error correction coding apparatus 50. The procedure itself of each error correction method is the same as that shown in the first embodiment.

In the above case, the decoding method is changed based on the error correction method selection signal transmitted together with the transmission data, but the selection signal is not transmitted and the optimum decoding method is selected only from the reception data. You may. In other words, it is an error correction method in which the decoding is performed by a plurality of decoding methods corresponding to all the error correction methods that can be selected on the transmission side, and the method that was correctly decoded among the plurality of decoding results is used on the transmission side. Therefore, it may be output as optimum decoded data.

FIG. 5 shows an example of the transmitted code when the error correction method is changed in two ways according to the line state in this embodiment. Here, Golay with 12 information bits and 11 check bits
The (23, 12) code is used. When there are few line errors when transmitting voice data or the like, as in the line error state 1 of FIG. 5A, 65 bits of the information bits 65 of the data to be transmitted are protected by error correction. A CRC bit 67 of 7 bits is added as input data to the error correction coding apparatus, and error correction coding is performed using six Golay codes, four of which are check bits 6
2 bits out of 6 and 2 bits out of 6 are erased (erased bit 68) and transmitted.

On the other hand, when the line state is worse than the line error state 1 and there are many errors, the line error state 2 is set as shown in FIG. To 77 bits, 7
After adding CRC bit 71 of the bit, this time Go
Error correction coding is performed using seven lay codes. Then, for these 7 bits, 3 bits of the check bits 70 are erased and transmitted.

As described above, on the transmission side, an error is caused by changing the number of error correction codes to be used, the erasure bit position and the number of erasure bits from the block-encoded data according to the error state of the transmission line. Change the correction method and send. At this time, the error correction codes used need not all be the same block code, and a plurality of types of codes may be combined.

Therefore, according to the second embodiment,
By selecting an appropriate error correction method according to the state of the transmission line, it is possible to perform transmission with fewer errors.

[0041]

As is apparent from the above embodiments, the present invention can be used even in an error correction code decoding apparatus using a block code at a higher coding rate than the original code by performing punctured coding. Moreover, high system compatibility can be provided.

[Brief description of drawings]

FIG. 1A is a block diagram of an error correction coding apparatus according to a first embodiment of the present invention, and FIG. 1B is a block diagram of an error correction decoding apparatus according to a first embodiment of the present invention.

FIG. 2 is a diagram showing an example of codes transmitted in the first embodiment.

FIG. 3 is a flowchart showing an error correction decoding algorithm in the first embodiment.

FIG. 4A is a block diagram of an error correction coding apparatus according to a second embodiment of the present invention, and FIG. 4B is a block diagram of an error correction decoding apparatus according to a second embodiment of the present invention.

5A is a diagram showing an example of a code transmitted in a line error state 1; FIG. 5B is a diagram showing an example of a code transmitted in a line error state 2;

FIG. 6 is a block diagram of a conventional error correction decoding device.

[Explanation of symbols]

 11, 50 Error correction coding device 12, 51 Error correction decoding device 13, 52 Error detection coding circuit 14, 53 Error correction coding circuit 15, 54 Bit selection erasure circuit 16, 56 Erase bit position storage circuit 17, 57 Bit insertion circuit 18,58 Error correction decoding circuit 19,59 Decoding result storage circuit 20,60 Block coded data candidate selection circuit 55 Error correction coding control circuit 61 Error correction decoding control circuit

Claims (11)

[Claims] 1. A transmission side performs error detection coding on input data, performs error correction coding on the data after error detection coding by a block code, and erases at least one coded bit from the data after error correction coding. Candidate is presumed to be block encoded data before bit erasure by inserting a plurality of bit patterns into the encoded bits erased in the transmitted data and performing error correction decoding on the receiving side. An error correction code decoding method characterized by selecting data and combining candidate data of each block code to decode an error detection code. 2. The number of bits less than or equal to the maximum error-correctable bit number of the block code is erased.
The error correction code decoding method described. 3. An error correction coding apparatus and an error correction decoding apparatus, wherein the error correction coding apparatus includes means for error detection coding input data, and the error detection coded data. The error correction decoding apparatus is provided with means for performing error correction coding by a block code and means for erasing at least one bit of the block coded data and transmitting the data. Means for inserting a plurality of bit patterns into the bit positions for error correction decoding of the received data, and block encoded data before bit erasing in the error correction encoding device among the data subjected to error correction decoding An error correction coding / decoding apparatus comprising means for selecting estimated candidate data and means for selecting correct decoded data from the candidate data. 4. The number of bits less than or equal to the maximum error-correctable bit number of the block code is erased.
The error correction code decoding device described. 5. The error correction code decoding apparatus according to claim 3, wherein correct decoded data is selected by combining a plurality of candidate data and performing error detection decoding. 6. The error correction code decoding apparatus according to claim 5, wherein when the combination of a plurality of candidate data exceeds a certain value, the operation of selecting correct decoded data is stopped. 7. Data which has been subjected to error detection coding and error correction coding using a block code and has at least one coded bit erased is received, and a plurality of bit patterns are inserted at the erased bit positions. And means for performing error correction decoding of the received data, and means for selecting candidate data presumed to be block coded data before bit erasure in the error correction coding process among the data subjected to error correction decoding. , An error correction decoding device comprising means for selecting correct decoded data from the candidate data. 8. When the block code used is a linear code, error correction decoding of block coded data in which a plurality of bit patterns are inserted at a plurality of erased bit positions and then the bit pattern is inserted 8. The error correction decoding apparatus according to claim 7, wherein a value in the middle of calculation of the value of the syndrome of the encoded data to be decoded first is stored when performing. 9. The transmitting side varies the erasing bit position and the number of erasing bits from the block-encoded data according to the error state of the transmission line to change the error correction coding method for transmission, and the receiving side , An error correction code decoding method characterized by performing decoding corresponding to the error correction method used on the transmitting side. 10. The transmission side transmits information indicating the error correction method used, and the reception side receives information indicating the error correction method,
10. The error correction coding / decoding method according to claim 9, wherein decoding corresponding to the error correction method is performed. 11. The error according to claim 9, wherein the receiving side performs decoding by a plurality of decoding methods corresponding to a plurality of error correcting methods used on the transmitting side to obtain a plurality of decoded data. Correction code decoding method.