JPH0815270B2 - Error correction block code decoding method - Google Patents

Description

The present invention relates to a decoding method of a code transmitted by adding redundant bits to data and transmitted as an error correction block code,
For example, it is applied to a decoding method for an error correction block code used in a data transmission system in land mobile radio.

"Prior art" As is well known, in data transmission in mobile communication, a code error occurs due to the high speed and wide fluctuation fading that occurs in the transmission line, and some kind of error control is essential. . In this case, in a mobile communication environment in which the error pattern changes variously depending on the fading pitch fluctuation, it is considered that a random error correction block code whose error correction capability depends only on the number of errors in a frame is suitable. To be

As a decoding method for this block error correction code, a minimum distance decoding method has been conventionally used in which decoding is performed using only the algebraic redundancy of the code. However, this minimum distance decoding method focuses on the algebraic property of the code to find the code word closest to the received word, and the error rate of each digit of the received word has no effect on the decoding. In other words, the error rates of the digits are all considered to be equal, and if an error occurs in a number of bits that exceeds the error correction capability determined by the inter-code distance, it results in erroneous reception.

On the other hand, in the maximum likelihood decoding method, the error rate of each bit is used to calculate which codeword is most likely to be considered to have been sent, and the codeword with the highest probability is used as the decoding result.
This maximum-likelihood decoding method can correct an error with a bit number exceeding the error correction capability of the minimum distance decoding method, but has the drawback that the decoding process becomes enormous if the number of codewords increases.

The minimum distance decoding method is equivalent to the maximum likelihood decoding method when the error rates of all the digits of the received word are all the same, but it is not the maximum likelihood decoding when the error rates of the digits are different, as in mobile communication. . Conversely, in mobile communication, it is possible that the word error rate characteristic can be improved by performing maximum likelihood decoding using the error rate of each digit. Rather, it is more natural to perform maximum likelihood decoding in mobile communications where the reception level fluctuates greatly.

Incidentally, in mobile communication, normally, the reception electric field level detection circuit provided in the receiver on the reception side can measure the reception electric field level at the identification point of each bit. Therefore, it is possible to estimate the error rate of each bit from the sample value of the received electric field level for each bit. Nevertheless, the minimum distance decoding method has been used for conventional decoding of error correction block codes in mobile communication, and the error rate of individual bits has never been used for decoding. Therefore, the word error rate cannot be reduced sufficiently.

IEEE Transaction on Information Theory,
Vol.IT-18, No.1.Jan.1972, pp. 170-181, digit Y _i (i = 1, ..., N) of received decoded word Y and jth code word X in the total set of code words. _{About j} 's Digit X _ji It is shown that X _j that minimizes is found and used as the decoded word. This reliability information α _i is given to each digit corresponding part of each reception demodulation output baseband signal assuming that the magnitude of the ray-ray phasing is known together with the phase of the reception signal.
It is calculated by giving the corresponding weight of the ray ray phasing characteristic.

Since the detection output (demodulation output) is used in this way, a linear detector is required and cannot be applied to reception / decoding of a non-linear modulation signal such as FSK or DPSK. Furthermore, the process of correctly estimating fading is complicated, and it is difficult to correctly estimate fading in an environment where fast fading occurs such as mobile communication.

"Means for Solving Problems" The present invention is a decoding method for a code transmitted by adding a redundant bit to data and transmitted as an error correction block code. The received word of the frame is made, the received electric field level for each digit of the received word is detected, and each possible code word and the received word are compared for each corresponding digit. On the other hand, the sum corresponding to the received electric field level is weighted to obtain the sum for each code word, and the code word having the smallest sum is used as the decoding result. When obtaining the sum of the values corresponding to the received electric field level, it may be obtained by multiplying an appropriate weight defined by a monotonically increasing function of the received electric field level.

"Embodiment" FIG. 1 shows an embodiment of the present invention. Receiving antenna 11
Is connected to a receiver 12, and the receiver 12 outputs a reception demodulation output 13 and a reception electric field level output 14. These outputs 13,1
4 is supplied to the bit-by-bit decoder 15, and at the same time identification is performed in bit units, the reception electric field level at the identification timing is sampled, and the reception word of one frame and the sample value of the reception electric field level at each bit are output. 16
Is supplied to the block code decoder 17. The block code decoder 17 is a sample value of the received electric field level in all bits of the code word, or a part of the code and the received word at different bits,
Alternatively, a process for obtaining a codeword that minimizes the sum of the received CNR (carrier noise ratio) values obtained from the value is executed, and the result is output as the decoding output 18.

Next, the decoding operation will be described. As is well known, in mobile communication, the received electric field level fluctuates greatly, but the received electric field level at the time of identification in bit-by-bit decoding is output from the receiver 12 as a received electric field level output 14. . The bit error rate P _E (γ) when the received electric field level is R is γ = R ² / (2N): Received CNR N: Noise power of receiver α: Expressed as a constant. Therefore, for the i-th digit of the received word Y, P _e (γi) is used as the error rate estimation value of this bit, and this value is used to calculate the posterior probability when Y is received for all code words. If the calculation is performed, the most probable transmission word is obtained and maximum likelihood decoding is possible.

Furthermore, since the bit error rate in equation (1) decreases sharply as γ increases, the maximum value of the posterior probabilities is the bit error in the error bit found in the decoding result by the algebraic decoding method, that is, the minimum distance decoding method. It is almost equal to the product of rates. However, since the bit error rate in equation (1) is expressed in the form of an exponential function, it is necessary to find the code word that maximizes the posterior probability by not matching each digit of the code word with the corresponding digit of the received word. Equivalent to finding the codeword that minimizes the sum of the received CNR for that codeword at Further, since the reception electric field level R is R ≧ 0, this is equivalent to finding a code word that minimizes the sum of the reception electric field levels of the digits that do not match. Further, the sum may be obtained by adding an arbitrary weight W (R) defined by a monotonically increasing function of the received electric field level.

The block code decoder 17 executes the above decoding algorithm. When formulated and expressed, Y = (Y ₁ , ..., Y _N ): received word Ω ₀ : entire set of code words X _j = (X _j1 , ..., X _jN ): j-th in Ω ₀ For the received CNR at the time of identifying the codeword γ _i : Y _i , Then we find X _j (X _j ∈ Ω).

From the above, it has been shown that the decoding method of the present invention can perform an operation close to maximum likelihood decoding and can improve the word error rate characteristic. However, in the above decoding method, in order to obtain a codeword satisfying the expression (2) from the set Ω ₀ of all the codewords, the left side of the expression (2) is calculated for all the codewords, When selecting the smallest one among them, the number of code words is large and the amount of calculation becomes enormous. That is, in the above description, it is assumed that all codewords may be the decoding result, but the calculation amount of codewords having such a possibility can be reduced by the following algorithm, for example.

Of each digit of the received word Y, K bits are selected in order from the smallest received CNRγ _i . However, the code distance 2d + 1
With respect to 0 <K ≦ 2d. It should be noted that K = 0 is equivalent to the minimum distance signal, and K = N is equivalent to the case of processing all the codewords described above.

Assuming that K bits have been lost and received, 2 ^K kinds of patterns are applied to this portion, and C-bit error correction decoding is performed by the algebraic decoding method (minimum distance decoding method). However,
0 ≦ C ≦ d.

Set of decoding results Ω for each pattern of
For Then, X _j is obtained from Ω and used as the transmission word X _j .

With this algorithm, algebraic decoding up to 2 ^K times and the left side of equation (2) should be calculated for the resulting codeword (less than 2 ^K ).

Next, this decoding principle will be specifically described with reference to FIG.

As an example, assume that a code having a code length N = 23 and an inter-code distance of 2d + 1 = 7 (Golay code) is used and that all the digits are "0". When the receiving side receives this frame (1 word), the received CNR changes as shown by the curve 21 in FIG. 2, and the received word Y is Y = [Y ₁ Y ₂ ...... Y ₂₃ ] = [ 00000000011010000011000] is obtained. The received word Y, so 5 bit errors _{Y 10 Y 11 Y 13 Y 19} Y 20 has occurred, it is erroneous reception in the conventional algebraic decoding (this code, the algebraic decoding correctly to 3 bit erroneous Mari It is decodable), which is decoded as a 2-bit error from the codeword adjacent to the transmitted word.
The position of these two bits is, for example, the first and seventh digits Y ₁ , Y ₇
Is identified as (Indicated by Δ in FIG. 2). That is, the adjacent codewords in this case are Y ″ =
[10000010011010000011000]. The received CNR in these two bits is γ ₁ = 20, γ _{7 as} shown in FIG.
= 24 [dB].

The number of lost bits K may be within 2d = 6, but for example K = 3
3 bits from the lowest received CNR are erasure bits. In the case of FIG. 2, these three bits are the ₁₀ , ₁₁ , and 12 digits Y ₁₀ , Y ₁₁ , and Y ₁₂ , which are shown as E in FIG. (In this, the error bits Y ₁₀ and Y ₁₁
It is included. ) Next, when 2 ³ patterns 22 are applied to these 3 bits, specifically, 2 ³ patterns are generated, and an exclusive OR operation is performed for each pattern, this portion and each bit. And, as a result of this operation, when the 3 bits are (000), that is, the pattern to be generated is (110)
At this time, the received word becomes Y ′ = [00000000000010000011000], and the number of error bits for the transmitted word is Y ₁₃ , Y ₁₉ , Y
_{Since it is 20} 3 bits, it is decoded into a pattern of all digits "0" which is a transmission word.

However, at the receiving side, it is not known at this stage whether the pattern of all digits "0" is the transmission word. When the transmitted word is all digits "0", the actual error bit is the one of the bits of the received word Y that has been corrected to "1", so the 10th, 11th, 13th, 19th, 20th digit is used. Yes, the received CNR for each digit is γ ₁₀ = 16, γ ₁₁ = 7, γ ₁₂ =
12, γ ₁₉ = 16, γ ₂₀ = 3 [dB].

Next, the sum of the received CNR of the erroneous bits (mismatched digits), assuming that they have been decoded into adjacent codes, and
Receiving erroneous bits when decoded to all digits "0"
Compare with the sum of CNR. If the result is adjacent code: γ
₁ + γ ₇ = 351 [True value] When all digits are "0": γ ₁₀
+ Γ ₁₁ + γ ₁₂ + γ ₁₉ + γ ₂₀ = 121 [true value] (this calculation is performed by converting to the true value of the received CNR in decibel representation). Therefore, all digits "0" are
Since the sum of the received CNRs in the error bits is small, the transmitted word is determined to be a pattern of all digits "0" and is correctly decoded. That is, the sum of the CNRs corresponding to the erroneous bits of the received word Y and all the transmitted words in which the lost bits may be replaced is obtained, and it is determined that the transmitted word having the smallest CNR is a legitimate one.

The decoding algorithm described above is executed by the block code decoder 17 shown in FIG. 3, for example. In FIG. 3, the bit-by-bit decoder output 16 consists of a received word 24 for one frame for each received signal frame and a sampled value 25 of the received electric field level at each digit of the received word. In the received electric field level sample value 25, the erasure bits (erasure digits) are selected by a predetermined number of bits (K bits) in ascending order of the reception level in one frame supplied to the erasure bit generation circuit 26. Data 27 indicating the position of the lost bit of lost bit generating circuit 26 from one frame is supplied to the pattern generating circuit 28, the pattern generating circuit 28, (which as 2 ^K) entire pattern position of the lost bit in one frame
Is applied, the bit is set to "1", and all patterns are output while being shifted in time, and when the output of all patterns is completed, the pattern end pulse 29 is output. The pattern output 31 from the pattern generation circuit 28 is stored in the first-in first-out (FIFO) register 32, and the FIFO register 32
The corresponding bits of the output loss bit 33 of FIG. 1 and each bit in the received word 24 are subjected to exclusive OR operation by the exclusive OR circuit 34. The output 35 of the exclusive OR circuit 34 is minimum distance decoded by the minimum distance decoding circuit 36 of the block code, and at the end of the decoding operation, the read pulse 37 is output to the FIFO register 32.

The minimum distance decoding result 38 from the minimum distance decoding circuit 36 is subjected to an exclusive OR operation with each corresponding bit (digit) of the received word 24 in the exclusive OR circuit 39, and the bits (bits) different from each other ( The pattern 41 whose digit) is "1" is output. The pattern 41 is input to the calculator 42, and the sum or square sum of the sampled values 25 of the received electric field level corresponding to the digit "1" in one frame of the pattern 41 is calculated. The calculation result 43 is input to the minimum value detection circuit 44, and the calculation result until the pattern end pulse 29 is input.
At the same time that the value of 43 and the minimum distance decoding result 38 are stored, the pattern of the minimum distance decoding result 38 corresponding to the smallest one of the stored operation results 43 is stored at the time when the pattern end pulse 29 is input. Output as a decrypted transmission word.

The lost bit generation circuit 26 is the step of the above-mentioned algorithm, the pattern generation circuit 28, the FIFO register 38, the exclusive OR circuit 34, the minimum distance decoding circuit 36 is the step, the exclusive OR circuit 39, and the arithmetic unit 42 are the expressions ( The calculation of the value on the left side of 2) 'and the minimum value detection circuit 44 perform the operation of finding the minimum value of the equation (2)'.

"Effect of Invention" Next, the improvement effect of the present invention will be described. Fourth
As shown in the figure, the decoding area is divided as follows according to the values of the erasure bit number K and the error correction bit number C.

(I) Error correction bit number C for inter-code distance 2d + 1
However, when C ≦ [(2d−K) / 2] (3) [·]: Gauss symbol, it can be decoded into a unique codeword by erasure bit correction. Therefore, this code word satisfies the minimization of equation (2) '.

(Ii) When C> [(2d-K) / 2], Ω is composed of a plurality of code words. Therefore, for these, the code word to be minimized cannot be found unless the left side of the equation (2) is calculated.

In the following, in the cases of (i) and (ii), the improvement effect is quantitatively shown.

In the case of (i) The probability density of the received CNR of KK bits that is not lost is Given in. In Fig. 5, N = 23 (assuming Golay code)
P _c (γ) for As is clear from FIG.
It can be seen that as the number of lost bits K increases, the peak of the probability density function shifts to the right, and the diversity effect is obtained. This average bit error rate in NK bits is
It is obtained by averaging the bit error rate of equation (1) with the probability density function of equation (4). The results are shown in FIG. As is clear from the figure, the larger K is,
The average error rate performance is improved.

On the other hand, the larger K is, the shorter the equivalent inter-code distance is. Therefore, the error correction capability is reduced, and the overall word error rate is not always improved.

Next, the word error rate is calculated. NK not treated as lost
If the number of errors in a bit is C or less, it is correctly decoded, and if the number of errors is C + 1 or more, it is an error. Assuming random error, the word error rate is Given in. However, P _b1 is the average bit error rate in FIG.

FIG. 7 shows the relationship between the average CNR obtained from equation (5) and the word error rate P _W1 . As is clear from the figure, when the number of lost bits K = 2 and the number of error correction bits C = 2, the reception CNR that has the greatest improvement effect and obtains the word error rate = 10 ⁻³
In comparison, when K = 0 and C = 3 (3-bit error correction is performed without erasure treatment, P _{W0 in the} figure), the required reception CNR is reduced by about 2 dB.

In case of (ii) The word error rate P _{W2 in} this case is P _W2 = P _W ′ + P _W ″ (6) P _W ′ = P _rob {C + in N−K bits not treated as erasure
One or more errors occur} P _W ″ = P _rob {The number of errors in N−K bits that are not treated as erasure is C or less, but as a result of equation (2) ′, it is decoded into an erroneous codeword. }, Where P _W ′ is the same as the calculation of P _{W1 in} the previous section, and in the case of a random error, Required by. Further, P _W ″ is given by the following equation in the case of a random error.

However, S = K−k, t = e−K + k, e = 2d + 1−k−1 And P _c (γ) is given by equation (4), and P _e
(Γ) is Is. Also, Is. FIG. 8 shows the relationship between the word error rate P _W2 and the average received CNR when N = 23,2d + 1 = 7 (Golay code). When the number of lost bits K = 3 and the number of error correction bits C = 3, 2 is each calculation result in the case of K = 3 and C = 2, and in this figure, the word error rate P _W0 by only error correction is shown. (K =
0, C = 3), and P _W ′ (probability that the number of errors in N−K bits not treated as erasure is C + 1 or more) in Expression (7) are also shown. From this figure, the following can be said.

When K = 3 and C = 3, P _W2 deteriorates more than P _W ′,
When K = 3 and C = 2, P _W2 is almost the same as P _W ′.

P _W2 in the case of K = 3 and C = 3 shows better characteristics in the case of K = 3 and C = 2, but the difference is slight. These are improved by about 4 dB in the average received CNR to obtain a word error rate of 10 ⁻³ , as compared with the case of performing only 3-bit error correction.

Confirmation by computer simulation The above theoretical values are obtained by assuming a random error, but when γ _i is correlated, the joint probability density of the received CNR in the bits of the erasure part and the part that is not erasure is calculated. Is difficult. Therefore, the word error rate characteristics in the cases of (i) and (ii) were obtained by computer simulation. The simulation method is as follows.

Amplitude variation corresponding to Rayleigh fading is generated.

Received CNRγ from the amplitude value of the i-th digit (bit)
calculate _i The bit error rate is calculated by

A random number in the interval (0,1) is generated, and the i-th value X _i is X
_{When i} <P _bi , the i-th digit is regarded as an error.

Repeat ~. f _D T (f _D : fading pitch,
The amplitude value is sampled at a normalized sampling period corresponding to T = 1 / fb, fb: bit rate).

The result of the simulation is shown in FIG. Fig. 9A
Is the simulation result for P _{W1 in} the case of (i), and the parameters are K = 2, C = 2, FIG. 9B, and FIG. 9C,
In the case of (ii), P _W ′ (C in N-K bits that are not lost)
In the simulation result for the probability of occurrence of +1 or more errors), the parameters are K = 3, C = 2 in FIG. 9B and K = 3, C = 3 in FIG. From these, the following can be said.

When it can be regarded as a random error (when f _D T = 1), both simulation results agree.

In both cases (i) and (ii), the word error rate characteristic deteriorates as f _D T increases, but the deterioration rate is f _D T = 0.5,0.2 in the case of (ii). The feature is that it is not so large and then deteriorates rapidly.

Figure 10 shows the average received CNR of 10 dB obtained from the results in Figure 9.
F _D T and word error rate improvement amount P _W1 / P _W0 , P _W ′ / P _W0
When f _D T = 0.01, there is almost no improvement in case of (i), whereas in case of (ii), the improvement is about 1/2 (K = 3, C = 3), and 3/4 (K
It can be seen that = 3, C = 2).

As described above, according to the present invention, even when the received electric field level greatly changes as in mobile communication,
Maximum likelihood decoding becomes possible, and the improvement effect is that the code length N = 23,
For a code having an inter-code distance of 2d + 1 = 7, in the case of (i), the maximum is 2 dB in the reception CNR that obtains the word error rate of 10 ^−3, and in the case of (ii), the similar evaluation has an improvement effect of a maximum of 4 dB.

In the above description, a binary code capable of bit error correction has been described, but the result can be applied to a decoding method of a byte error correction code such as Reed Solomon code as it is.

In the present invention, the received electric field level is used as the reliability information and is not obtained from the demodulation output. Therefore, the received electric field level can be easily and accurately detected regardless of the modulation format, that is, even when decoding the nonlinear modulation signal, and therefore the nonlinear It can also be applied to the decoding of modulated signals, does not require complex processing such as fading estimation, and operates effectively even in a fast fading environment. Since the mobile communication receiver originally has a function of detecting a received electric field level, its output can be used as reliability information.

[Brief description of drawings]

FIG. 1 is a block diagram showing an example of the configuration of a receiving apparatus to which the decoding method according to the present invention is applied, FIG. 2 is a diagram specifically showing the principle of decoding according to the present invention, and FIG. FIG. 4 is a block diagram showing a detailed configuration example of the block code decoder 17, FIG. 4 is a diagram showing the relationship between the number of lost bits and the number of error correction bits, and the decoding area. FIG. FIG. 6 is a diagram showing a probability density function of K-bit received CNR, FIG. 6 is an average bit error rate characteristic diagram of NK bits that are not lost, and FIG. 7 is a theoretical value of the word error rate characteristic in the case of (i). Figure showing,
FIG. 8 is a diagram showing the theoretical value of the word error rate characteristic in the case of (ii), FIG. 9 is a diagram showing the simulation result of the word error rate characteristic of (i) and (ii), and FIG. 10 is a simulation. It is a figure which shows the relationship between _fD T calculated | required by and the improvement amount by this invention.

Claims (1)

[Claims] 1. A decoding method for a code transmitted by adding a redundant bit to data as an error correction block code, wherein a received code is subjected to bit-by-bit identification decoding to create a received word, and each digit of the received word. The received electric field level for each is calculated, each possible code word and the received word are compared for each corresponding digit, and the code word for which the sum of the weights calculated from the received electric field level in the disagreement digit is the minimum An error correction block code decoding method characterized in that