Block code decoding method and device thereof

Block code decoding method and device

The present invention relates to a block code decoding method and device, in particular to a low-complexity block code decoding method and device.

In various transmission and communication systems, it is often necessary to correctly transmit and receive a large amount of data. Especially in long-distance channels or wireless communication systems, reliable and error-free reception of digital information is a very important topic. However, when transmitting data or messages, it usually arrives at the receiver through a certain transmission channel, but it is often due to poor hardware equipment, external interference, power dissipation, noise or multipath attenuation, or sensitivity of electronic equipment. Errors occur, and the digital data cannot be transmitted correctly or received reliably. Therefore, reliable data transmission is often difficult.

To improve the reliability of channel data transmission, many methods have been developed. For example, forward error correction (FEC) codes and other devices are used to locate, offset, correct and/or eliminate these errors, according to specific encoding (encoding) The type of coding manual establishes many predetermined codewords and uses them to encode the data to be transmitted. Once the coding is completed, errors introduced in the transmission process have the opportunity to use the known codes in the decoding process. The mathematical processing method, locate and correct it.

In the process of message transmission, the message encoder converts the original message into a sequence of binary numbers (bits), called a message sequence (information sequence) u. Broad "coding" includes analog to digital conversion (A/D conversion, ADC), message source coding (source coding), and channel coding (channel coding) and so on. Among them, channel coding is a technology to improve the reliability of digital communication. By performing error control on digital signals, the quality and quantity of transmission can be improved. The channel encoder converts the information sequence into a discrete encoded sequence v, which is called a codeword.

Generally, the code word v is still a sequence of binary digits, but non-binary ones are also useful in some applications. Any n-bit codeword (codeword) can be regarded as a vector in n-dimensional space, and each coordinate component of this vector is each bit in the codeword. For example, we can write codeword 101 as a vector One-dimensional encoding vector<u style="single">x</u>=(101). The number of different components in the vector of any two codewords is defined as the Hamming distance d_H, Such as an encoding vector<u style="single">x</u> (101) and<u style="single">y</u> (110) Hamming distance d_H (<u style="single">x</u>，<u style="single">y</u>) Is 2 because the second and third components are different. For a designed coding system, the minimum Hamming distance between the effective code words is called the minimum Hamming distance d_min, This is the number of bits allowed to be errored during decoding, when the number of transmission errors in a codeword is less than d_minWhen the time, the occurrence of the error can be detected.

A commonly used decoding and correction method is to obtain the closest codeword of the received message as a decision code through a correlation operation. The correlation operation of two vectors can be defined as the product of the corresponding components, for example,<u style="single">x</u>(x_1,x_2,x₃...X_n)and<u style="single">y</u>(y₁,y₂,y₃,...Y_nThe associative operation of) can be expressed as follows:<u style="single">x</u>(x₁,x₂,x₃...X_n)⊕<u style="single">y</u>(y₁,y₂,y₃,...Y_n)=x₁*y₁+x₂*y₂+x₃*y₃...X_n*y_n

In a binary system, the larger the value obtained by the correlation operation between the received message and a codeword, the closer the received message is to the codeword, that is, the closer the codeword is to the possible correct solution.

If the transmitted block code itself has some characteristics, such as linear or cyclic, the decoding complexity can be greatly reduced. However, when the block code itself has no special characteristics that can reduce the decoding complexity, we have to Correlation operations are performed on the received information block and all codewords, and the codeword with the highest correlation is found as the decision code.

When the length of the block code becomes longer and the capacity becomes larger, the number of associative operations also increases sharply, which in turn affects the performance of channel transmission. In order to reduce the number of associative operations, in order to reduce the number of associative operations For a coding system with a minimum Hamming distance, only the codewords within the minimum Hamming distance of the received information need to be considered for correlation operations. This is the so-called bounded distance decoding. However, as the amount of information increases Improved, faster and more accurate transmission requirements, the existing decoding methods still have insufficient efficiency. Therefore, it is urgent to find a simpler and more efficient decoding method without affecting the reliability of channel transmission. Yes, because of the job, the applicant conceived the "block code decoding method and device" of this case. The following is a brief description of this case.

One of the objectives of the present invention is to solve the problems of the prior art.

Another object of the present invention is to provide a block code decoding method and device with less computation.

According to an embodiment of the present invention, a method for decoding block codes is provided, in which a first message code is systematically coded (systematic encoding) to generate a first block code, the first block code is composed of the first message code and a first parity check code, the first block code is received as a first receiving code after transmission, The first receiving code includes a first receiving message code corresponding to the first message code part, and the method includes: (A) creating a set according to a dimension k and a selected distance p of the first receiving message code Exclusive-or (XOR) mask vector, where the dimension of the group of XOR mask vectors is k and its components are composed of two-bit values i or j, and the group of XOR mask vectors has 0~ The combination of all XOR mask vectors in which p components are i and the remaining components are j, represents all the possible error patterns of the message code after transmission, where i represents the bit position of the message code transmission error, and j represents the message code. The bit position where the message code is transmitted without error; (B) Perform an XOR operation on the first received message code and the set of XOR mask vectors, that is, perform an XOR operation on the first received message code corresponding to a component of the value i in the XOR mask In the first received message code, a component corresponding to the value j in the XOR mask remains unchanged, and a second received code is obtained; (C) the second received code is systematically coded again, And generate a set of second block codes; and (D) perform a correlation operation on the first received code and the set of second block codes, and take the second area of the set with the largest value obtained by the correlation operation One of the block codes is the most probable solution.

The most probable solution is to get a deeper understanding of the present invention through the following examples and illustrations.

The present invention will be fully understood by the following embodiments, so that those who are familiar with the art can complete it accordingly, but the embodiments of the present invention are not intended to limit the implementation possibilities of the present invention.

Before describing the embodiment of the present invention, the block code will be further described first. For a block code used for channel transmission, it can usually be represented by a function (n, k, t), where n represents the total length of the code word, and k represents the original code (message code) before encoding The bit length of, and t is the number of bits that can be corrected after the block code is transmitted and received, and its minimum Hamming distance d_minThe relationship can be expressed as:<img file="TW201014199A_D0001.tif" />, Where the symbol"<img file="TW201014199A_D0002.tif" />"Represents a floor function. In addition, the block code can be a systematic code, which means that the coded block code is composed of a message code and a check code. For example, in the block Code v(x₀,...X_k-1,z_K,...z_n-1), (x₀,...X_k-1) Is the message code and (z_k,...z_n-1) Is the check code. Please note that in the following embodiments of the present invention, the check code is a parity check, but this is not a limitation of the present invention.

In the prior art, when a block code is transmitted through the channel, the receiving end will receive a reception message corresponding to the block code<u style="single">y</u>(y₀,...Y_k-1y_k,...Y_n-1), and associate it with all possible codewords for the block code to find the maximum value:<img file="TW201014199A_D0003.tif" />,in{<i>c</i>_<i>i</i>,₀…<i>c</i>_<i>i</i>,_<i>k-</i>1<i>c</i>_<i>i</i>,_<i>k</i>…<i>c</i>_<i>i</i>,_<i>n-</i>1} Represents the i-th codeword, if the codeword has q bits, then 0i&lt;q^k. Therefore, as the number of bits of the codeword increases, the number of associated operations that need to be performed increases, that is, q^kSecond-rate. In order to reduce the number of correlation operations in the prior art (ie limiting the distance decoding), for the coding system with the minimum Hamming distance p, only the information received is considered<u style="single">y</u>(y₀,...Y_k-1,y_k,...Y_k-1The Hamming distance of) is within p for associative operations. In this way, the number of associative operations can be reduced to (1+<img file="TW201014199A_D0004.tif" />+<img file="TW201014199A_D0005.tif" />+…+<img file="TW201014199A_D0006.tif" />) Times, of which, 1 time (ie<img file="TW201014199A_D0007.tif" />Second) In order to consider the condition that no error occurs during channel transmission under the condition of the Hamming distance p,<img file="TW201014199A_D0008.tif" />In order to consider that under the condition of the Hamming distance p, a bit error occurs in the block code during channel transmission,<img file="TW201014199A_D0009.tif" />Considering the condition of p-bit errors in the block code during channel transmission under the condition of the Hamming distance p.

However, with this received information<u style="single">y</u>(y₀,...Y_k-1,y_k,...Y_n-1There may still be many codewords with Hamming distance p of ), that is, when the total bit length n of the codeword is longer and/or the Hamming distance p is larger, the number of associated operations (1+<img file="TW201014199A_D0010.tif" />+<img file="TW201014199A_D0011.tif" />+…+<img file="TW201014199A_D0012.tif" />) Will be more. In view of this, the present invention proposes a method and device to solve this problem, as detailed in the following embodiments of this case.

This embodiment is aimed at the situation when the block code is most likely to be resolved into a systematic code. Please refer to the first figure, which is a flowchart of this embodiment. The first block code transmitted by the transmitting end (not shown) of this embodiment<u style="single">v</u>(x₀,...X_k-1,z_k,...z_n-1)=<u style="single">v</u>(<u style="single">u</u>,<u style="single">z</u>) Is a systematic code, where the first message code<u style="single">u</u>(x₀,...X_k-1) Is the message code to be sent, added by the code<u style="single">z</u>(z_k,...z_n-1) Is the parity check code. After transmitting through a channel, the receiving end receives a message (step 101), which is a first received code<u style="single">r</u>(y₀,y₁,...,Y_k-1,y_k,...Y_n-1)=<u style="single">r</u>₁(y₀,y₁,...,Y_k-1)+<u style="single">r</u>₂(y_k,y_k+1,...,Y_n-1),in<u style="single">r</u>₁(y₀,y₁,...,Y_k-1) Is the first received message code, which is the part corresponding to the original message code.

due to<u style="single">v</u>It is a systematic coding. Therefore, we only need to consider the case where the Hamming distance of the message code part (k-dimension) is p (step 102). For a one-k-dimensional message code, consider all possible transmission patterns within the Hamming distance p, including all error-free situations and possible error patterns, and create a set of mutual exclusion or mask (XOR mask) )M, this group of mutual exclusion or mask is composed of a set of transmission modes representing errors of 0~p bits respectively {M₀, M₁, M₂,..., M_p}, each mutex or mask can also be expressed as a k-dimensional vector, where the number "0" represents that the corresponding bit is correct for transmission, and the number "1" represents that the corresponding bit is expected to be wrong.

Therefore, when considering the error of 0 bits, only one XOR mask is M₀{(0,0,0,0,‥‥,0)_kx1}, all its components are 0; when considering 1 bit error, it is M₁{0,0,0,0‥‥,1)_kx1, (0,0,0,0,‥‥,1,0)_kx1, (0,0,0,0,…1,0,0)_kx1,……(1,0,0,,…0,0,0)_kx1}common<img file="TW201014199A_D0013.tif" />= k XOR masks; M when considering 2 wrong bits₂{(0,0,0,‥‥0,1,1)_kx1, (0,0,0,…,1,0,1)_kx1, (0,0,0,…1,0,0,1)_kx1,…(0,0,0,…0,1,1,0)_kx1, (0,0,…,1,0,1,0)_kx1,……, (1,0,0,…0,0,0)_kx1}common<img file="TW201014199A_D0014.tif" />XOR masks, similarly, when considering the wrong p bits, there are a total of<img file="TW201014199A_D0015.tif" />XOR masks, all XOR masks represent all possible transmission results when 0~p bits are wrong.

After that, the first received message code<u style="single">r</u>₁(y₀,y₁,...,Y_k-1) And all k-dimensional XOR masks to perform XOR operation (step 103). The operation method of XOR operation is to shift and not carry, that is, the first received message code<u style="single">r</u>₁The component corresponding to the component of the k-dimensional XOR mask is "1", which means that the component that will generate errors during channel transmission is estimated. Then the component is changed, and "0" is changed to "1" or " 1" is changed to "0", and the first received message code received<u style="single">r</u>₁The component corresponding to the "0" part of the component of the k-dimensional XOR mask indicates that no error occurred during the transmission of the estimated channel, so its value is not changed. The first received message code<u style="single">r</u>₁After performing the XOR operation with all k-dimensional XOR masks, the same number of XOR masks (1+<img file="TW201014199A_D0016.tif" />+<img file="TW201014199A_D0017.tif" />+…+<img file="TW201014199A_D0018.tif" />)<u style="single">r</u>₁' (<i>x</i>₀',<i>x</i>₁',…<i>x</i>_k-1'), hereafter called the second message code, all the second message codes<u style="single">r</u>₁'Is the solution of all possible message codes based on the first received message code and the Hamming distance p.

All the second message codes<u style="single">r</u>' (<i>x</i>₀',<i>x</i>₁',…<i>x</i>_<i>k</i>-1') After encoding again (step 104), a set of comparison codes can be obtained, that is, the second block code<u style="single">v</u>' (<i>x</i>₀',<i>x</i>₁',…<i>x</i>_<i>k</i>-1',<i>z</i>₀',<i>z</i>₁',…<i>z</i>_<i>k</i>-1') (step 105), the second block code<u style="single">v</u>'Is all possible solutions, a total of 1+<img file="TW201014199A_D0019.tif" />+<img file="TW201014199A_D0020.tif" />+…+<img file="TW201014199A_D0021.tif" />Group, the 1+<img file="TW201014199A_D0022.tif" />+<img file="TW201014199A_D0023.tif" />+…+<img file="TW201014199A_D0024.tif" />Group second block code<u style="single">v</u>'Respectively and the first receiving code<u style="single">r</u>(y₀,y1,...,y_k-1,y_k,...Y_n-1) Perform correlation operation (step 108), and take the second block code when the maximum value occurs<u style="single">v</u>'Is the first receiving code<u style="single">r</u>The most probable solution (109).

In the above process, the XOR mask of k-dimensional (k&lt;n) is only established for the message code part of the systematic code (n-dimensional), and only 1+<img file="TW201014199A_D0025.tif" />+<img file="TW201014199A_D0026.tif" />+…+<img file="TW201014199A_D0027.tif" />Times of associative operations, compared to the previous technology, which requires 1+<img file="TW201014199A_D0028.tif" />+<img file="TW201014199A_D0029.tif" />+…+<img file="TW201014199A_D0030.tif" />The number of associated operations, so it is obvious that all the required operations are further reduced.

If we assume the first received message code in the decoding process {<i>y</i>₀…<i>y</i>_<i>k</i>-1The number of errors p of} is not greater than k (0pk). In this case, when p is smaller, the number of associated operations that need to be performed is less. A systematic binary code with (16, 8, 2) characteristics is used For example, if you do all the associative operations, you need to do 2⁸Times, that is, 256 associated operations. When the Hamming distance of the coding system is set to 2, that is, when only two bit errors are considered, only 37 (1+<img file="TW201014199A_D0031.tif" />+<img file="TW201014199A_D0032.tif" />) Times of associative operations, when the Hamming distance is 3, then 93(1+<img file="TW201014199A_D0033.tif" />+<img file="TW201014199A_D0034.tif" />+<img file="TW201014199A_D0035.tif" />) Times of associative operations. When the Hamming distance is 4, then 163 (1+<img file="TW201014199A_D0036.tif" />+<img file="TW201014199A_D0037.tif" />+<img file="TW201014199A_D0038.tif" />+<img file="TW201014199A_D0039.tif" />) Times of associative operations.

Take the systematic binary code with (16, 8, 2) characteristics when the minimum Hamming distance is 2 as an example. Among them, a first message code<u style="single">u</u>(<i>x</i>₀,<i>x</i>₁,…<i>x</i>₇) Is the information to be transmitted through the channel, which becomes a first block code after a systematic encoding<u style="single">v</u>(<u style="single">u</u>,<u style="single">z</u>)=<u style="single">v</u>(<i>x</i>₀,<i>x</i>₁,…<i>x</i>₇,<i>z</i>₀,<i>z</i>₁,…<i>z</i>₇), which is added by code<u style="single">z</u>(<i>z</i>₀,<i>z</i>₁,…<i>z</i>₇) Is a parity check code, after a channel is transmitted, a received code is a first received code<u style="single">r</u>(<i>y</i>₀,<i>y</i>₁,…<i>y</i>₁₅). After that, the first receiving code<u style="single">r</u>(<i>y</i>₀,<i>y</i>₁,…<i>y</i>₁₅)=[<u style="single">r</u>₁,<u style="single">r</u>₂] The part corresponding to the original message code<u style="single">r</u>₁(<i>y</i>₀,<i>y</i>₁…<i>y</i>₇) (Called the first received message code) and 37 pre-established mutexes or masks (XOR masks) M_jPerform exclusive-or operations. These 37 masks represent the set of error patterns with errors of 0~2 bits respectively {M₀, M₁, M₂}, where the number "0" represents correct, and the number "1" represents error: when it is wrong by 0 bits, M₀for<u style="single">m</u>₀,₁(0,0,0,0,0,0,0,0); when one bit is wrong, M₁for<u style="single">m</u>₁,₁(0,0,0,0,0,0,0,1)，<u style="single">m</u>₁,₂(0,0,0,0,0,0,1,0), <u style="single">m</u>₁,₃(0,0,0,0,0,1,0,0)，<u style="single">m</u>₁,₄(0,0,0,0,1,0,0,0)，<u style="single">m</u>₁,₅(0,0,0,1,0,0,0,0)，<u style="single">m</u>₁,₆(0,0,1,0,0,0,0,0), <u style="single">m</u>₁,₇(0,1,0,0,0,0,0,0)，<u style="single">m</u>₁,₈(1,0,0,0,0,0,0,0) 8 in total; the same is true, when 2 bits are wrong, M₂for<u style="single">m</u>₂,₁(0,0,0,0,0,0,1,1)，<u style="single">m</u>₂,₂(0,0,0,0,0,1,0,1), <u style="single">m</u>₂,₃(0,0,0,0,1,0,0,1)，<u style="single">m</u>₂,₄(0,0,0,1,0,0,0,1)，<u style="single">m</u>₂,₅(0,0,1,0,0,0,0,1)，<u style="single">m</u>₂,₆(0,1,0,0,0,0,0,1)，<u style="single">m</u>₂,₇(1,0,0,0,0,0,0,1)，<u style="single">m</u>₂,₈(0,0,0,0,0,1,1,0)，<u style="single">m</u>₂,₉(0,0,0,0,1,0,1,0)，<u style="single">m</u>₂,₁₀(0,0,0,1,0,0,1,0)，<u style="single">m</u>₂,₁₁(0,0,1,0,0,0,1,0)，<u style="single">m</u>₂,₁₂(0,1,0,0,0,0,1,0), m₂,₁₃(1,0,0,0,0,0,1,0)，<u style="single">m</u>₂,₁₄(0,0,0,0,1,1,0,0)，<u style="single">m</u>₂,₁₅(0,0,0,1,0,1,0,0)，<u style="single">m</u>₂,₁₆(0,0,1,0,0,1,0,0)，<u style="single">m</u>₂,₁₇(0,1,0,0,0,1,0,0)，<u style="single">m</u>₂,₁₈(1,0,0,0,0,1,0,0)，<u style="single">m</u>₂,₁₉(0,0,0,1,1,0,0,0)，<u style="single">m</u>₂,₂₀(0,0,1,0,1,0,0,0)，<u style="single">m</u>₂,₂₁(0,1,0,0,1,0,0,0)，<u style="single">m</u>₂,₂₂(1,0,0,0,1,0,0,0)，<u style="single">m</u>₂.₂₃(0,0,1,1,0,0,0,0)，<u style="single">m</u>₂,₂₄(0,1,0,1,0,0,0,0)，<u style="single">m</u>₂,₅(1,0,0,1,0,0,0,0)，<u style="single">m</u>₂,₂₆(0,1,1,0,0,0,0,0)，<u style="single">m</u>₂,₂₇(1,0,1,0,0,0,0,0)，<u style="single">m</u>₂,₂₈(1,1,0,0,0,0,0,0), there are 28 error modes in total.

Among them, the operation mode of the exclusive OR (XOR) operation is shifting instead of carrying, for example, if the first received code is received<u style="single">r</u>(<i>y</i>₀,<i>y</i>₁,…<i>y</i>₁₅)=(0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1), which corresponds to the first received message code of the original message code part<u style="single">r</u>₁(<i>y</i>₀,<i>y</i>₁…<i>y</i>₇)=(0,0,1,1,0,0,1,1), if you choose the error mode when 2 bits are wrong<u style="single">m</u>₂,₂(0,0,0,0,0,1,0,1) When performing exclusive OR operations (XOR),<u style="single">r</u>₁The component corresponds to<u style="single">m</u>₂,₂The "1" part of the component indicates the component that caused the error in the estimation of the channel transmission process, then the component is changed, "0" is changed to "1" or "1" is changed to "0", and<u style="single">r</u>₁The component corresponds to<u style="single">m</u>₂,₂The "0" part of the component indicates the component that did not generate an error during the estimated channel transmission process, and its value is not changed. Therefore, if the first received message code is (0,0,1,1,0,0,1 ,1), and<u style="single">m</u>₂,₂(0,0,0,0,0,1,0,1) mutually exclusive OR operation is: (0,0,1,1,0,0,1,1)XOR (0,0,0, 0,0,1,0,1)=(0,0,1,1,0,<b><i>1</i></b>,1,<b><i>0</i></b>)

Use the result of the exclusive OR operation (the second message code) as the message code<u style="single">x</u>'(<i>x</i>₀',<i>x</i>₁,'…<i>x</i>₇') After encoding again, a second block code can be obtained<u style="single">v</u>' (<i>x</i>₀,<i>x</i>₁',…<i>x</i>₇',<i>z</i>₀',<i>z</i>₁'…<i>z</i>₇'), a total of 37 sets of the second block code are all possible correct codes, and the 37 sets of second block codes are respectively the first received code<u style="single">r</u>(<i>y</i>₀,<i>y</i>₁,…<i>y</i>₁₅) For correlation operation, the second block code that takes the maximum value is the first received code<u style="single">r</u>(<i>y</i>₀,<i>y</i>₁,…<i>y</i>₁₅) Is the most likely solution.

However, if the conventional bounded distance decoding (bounded distance decoding) is used, the received first received code<u style="single">r</u>(<i>y</i>₀,<i>y</i>₁,…<i>y</i>₁₅) Must be separated from the first block code v(<u style="single">u</u>,<u style="single">z</u>)=v(<i>x</i>₀,<i>x</i>₁,…<i>x</i>₇,<i>z</i>₀,<i>z</i>₁,…<i>z</i>₇) In all cases where there may be 0~2 error bits, do the correlation operation to find the closest solution, so a total of<img file="TW201014199A_D0040.tif" />+<img file="TW201014199A_D0041.tif" />+<img file="TW201014199A_D0042.tif" />=1+16+120=137 times of associative operations, and only 37 times of associative operations are required through the method listed in this embodiment, so the benefits achieved by this embodiment are significant and clear.

In summary, the present invention uses a set of mutually exclusive or (XOR) masks predetermined according to the minimum Hamming distance, which can effectively simplify the procedures and calculations for judging all possible solutions during decoding. , With the use of XOR masks, by cleverly arranging the minimum Hamming distance that only needs to process the message code, it greatly reduces the number of correlation operations and the amount of calculations, and improves the efficiency of channel transmission. It is a difficult innovative design. , Has deep industrial value, and Yan filed an application in accordance with the law.

This creation can be modified in many ways by those who are familiar with the craftsmanship, but all of them are not deviated from the protection of the scope of application.

<p>101Receive a message</p><p>102Retrieve the message code part</p><p>103XOR mask operation</p><p>104Code</p><p>105Generate comparison code</p><p>108associative operations</p><p>109The most likely solution is the comparison code where the maximum value occurs</p>

The first figure is a flowchart of a preferred embodiment of the block code decoding method of the present invention.