CN103973318A

CN103973318A - Linear programming coding method of 73 square residue code

Info

Publication number: CN103973318A
Application number: CN201410177335.0A
Authority: CN
Inventors: 黎勇; 刘宏清; 李鹏华
Original assignee: Chongqing University of Post and Telecommunications
Current assignee: Chongqing University of Post and Telecommunications
Priority date: 2014-04-29
Filing date: 2014-04-29
Publication date: 2014-08-06

Abstract

The invention discloses a linear programming decoding method for (73, 37, 13) square residual codes. It first expresses (73, 37, 13) square residual codes in matrix form instead of polynomial form, and then decodes the linear programming Code thinking is applied to it. Compared with the existing (73, 37, 13) square residual code algebraic soft-decision decoding algorithm, the new decoding method proposed by the present invention significantly improves the decoding performance under the condition of comparable complexity. It has a good application prospect in business.

Description

A Linear Programming Decoding Method for 73 Square Residual Codes

技术领域technical field

本发明属于数字通信技术领域，具体涉及一种(73，37，13)平方剩余码(后文简称为73码)的代数译码方法。The invention belongs to the technical field of digital communication, and in particular relates to an algebraic decoding method of a (73, 37, 13) square residual code (hereinafter referred to as 73 code for short).

背景技术Background technique

1958年，Prange首次提出了二进制平方剩余码的概念。它是BCH码的一个子类，其码率略大于或等于1/2，有着较大的最小距离因而性能优异。比如，(24,12,8)扩展平方剩余码(也称格雷码)就被广泛用于大量的通信链路中，包括NASA的Voyager成像系统和高频无线电通信。In 1958, Prange first proposed the concept of binary square residual codes. It is a subclass of BCH code, its code rate is slightly greater than or equal to 1/2, and it has a large minimum distance and thus excellent performance. For example, (24,12,8) extended square residual codes (also known as Gray codes) are widely used in a large number of communication links, including NASA's Voyager imaging system and high-frequency radio communications.

过去几十年，平方剩余码常用的译码算法是利用Sylvester结子和Grobner基来解牛顿恒等式，从而得到错误位置多项式。然而，当发生错误个数很大时，牛顿恒等式中的变量多，且变量的幂次高，这些都使得解牛顿恒等式变得非常困难。另外，不同的平方剩余码需要采用不同的条件集合来计算错误位置，而枚举所有不同的条件从软件实现角度而言并不太实际。针对5个错误和6个错误的情况，传统的73码的代数译码算法采用许多复杂的运算以获得错误位置多项式的系数，并且需要4096字节的内存空间存储中间数据。近来，研究者提出一种有效的查找表译码算法，它比传统的代数译码算法更快，且只需85.4k字节内存来存储中间数据。然而，查找表译码算法的弊端在于当码长较长时，所需的内存空间会变得很大，这将使得译码代价显著升高。最近，文献[1]提出了一种新的算法求解未知校正子，然后基于IFBM算法求解错误位置多项式，从而实现了算法复杂度和占用存储空间之间较好的折中。In the past few decades, the commonly used decoding algorithm for square residual codes is to use Sylvester knots and Grobner basis to solve Newton's identity, so as to obtain the error location polynomial. However, when the number of errors is large, there are many variables in Newton's identity, and the power of the variable is high, which makes it very difficult to solve Newton's identity. In addition, different square residual codes require different sets of conditions to calculate the error location, and it is not practical to enumerate all the different conditions from the perspective of software implementation. For the cases of 5 errors and 6 errors, the traditional 73-code algebraic decoding algorithm uses many complex operations to obtain the coefficients of the error position polynomial, and requires 4096 bytes of memory space to store intermediate data. Recently, researchers proposed an efficient look-up table decoding algorithm, which is faster than traditional algebraic decoding algorithms and only needs 85.4k bytes of memory to store intermediate data. However, the disadvantage of the lookup table decoding algorithm is that when the code length is longer, the required memory space will become larger, which will significantly increase the cost of decoding. Recently, literature [1] proposed a new algorithm to solve the unknown syndrome, and then solve the error position polynomial based on the IFBM algorithm, so as to achieve a good compromise between the algorithm complexity and the occupied storage space.

一个平方剩余码的码长n是一个形如n＝8l±1的素数，其中l是一个正整数。则模n的平方剩余集合Q_n可写为The code length n of a square residual code is a prime number in the form of n=8l±1, where l is a positive integer. Then the set of square residues Q _n modulo n can be written as

Q_n＝{i|i≡j²mod n for1≤j≤n-1}.Q _n ＝{i|i≡j ² mod n for1≤j≤n-1}.

令m为满足2^m≡1(mod n)的最小正整数。对于73码而言，m＝9。令α是GF(2⁹)上本原多项式x⁹+x⁴+1的根，则β＝α⁷是GF(2⁹)上单位圆的本原73阶根。(73，37，13)平方剩余码的生成多项式为Let m be the smallest positive integer satisfying 2 ^m ≡ 1(mod n). For yard 73, m=9. Let α be the root of the primitive polynomial x ⁹ +x ⁴ +1 on GF(2 ⁹ ), then β=α ⁷ is the primitive 73rd order root of the unit circle on GF(2 ⁹ ). The generator polynomial of the (73, 37, 13) square residual code is

$\begin{matrix} g g ((x x)) = = \underset{i i &Element; &Element; {Q Q}_{7373}}{Π Π} ((x x - - {β β}^{i i})) = = {g g}_{11} ((x x)) {g g}_{33} ((x x)) {g g}_{99} ((x x)) {g g}_{2525} ((x x)) \\ = = {x x}^{3636} + + {x x}^{3535} + + {x x}^{3131} + + {x x}^{3030} + + {x x}^{2929} + + {x x}^{2828} + + {x x}^{2525} + + {x x}^{21 twenty one} + + {x x}^{1919} + + {x x}^{1818} + + \\ {x x}^{1717} + + {x x}^{1515} + + {x x}^{1111} + + {x x}^{88} + + {x x}^{77} + + {x x}^{66} + + {x x}^{55} + + x x + + 11 \end{matrix}$

其中g₁(x),g₃(x),g₉(x)和g₂₅(x)称为元素β,β³,β⁹,β²⁵对应的最小多项式，即0≤i≤8是g_r(x)的根，r＝1,3,9,25。因此73码能够纠正6个错误。Among them, g ₁ (x), g ₃ (x), g ₉ (x) and g ₂₅ (x) are called the minimum polynomials corresponding to elements β, β ³ , β ⁹ , β ²⁵ , namely 0≤i≤8 is the root of g _r (x), r=1,3,9,25. So 73 yards can correct 6 errors.

定义码字多项式为c(x)＝c₇₂x⁷²+c₇₁x⁷¹+…+c₁x+c₀，错误多项式为e(x)＝e₇₂x⁷²+e₇₁x⁷¹+…+e₁x+e₀，接收码字为r(x)＝c(x)+e(x)。假定接收码字中发生了v个错误，v≤t＝6，即0≤l₁<l₁…<l_v≤n-1。相应的校验子为其中1≤j≤v称为错误位置。如果i包含在Q_n中，则校验子就称为已知校验子。由文献[2]可知，73码的生成多项式在GF(2)上既约，其所有的已知校验子(未知校验子)均可由S₁，S₃，S₉和S₂₅(S₅，S₁₁，S₁₃和S₁₇)的幂次表示。Define the codeword polynomial as c(x)=c ₇₂ x ⁷² +c ₇₁ x ⁷¹ +…+c ₁ x+c ₀ , and the error polynomial as e(x)=e ₇₂ x ⁷² +e ₇₁ x ⁷¹ +…+e ₁ x+e ₀ , the received codeword is r(x)=c(x)+e(x). Suppose there are v errors in the received codeword, v≤t=6, that is 0≤l ₁ <l ₁ ...<l _v ≤n-1. The corresponding syndrome is in 1≤j≤v is called the error position. If i is included in Q _n , the syndrome is called a known syndrome. It can be known from literature [2] that the generator polynomial of the 73 code is reduced on GF(2), and all its known syndromes (unknown syndromes) can be obtained by S ₁ , S ₃ , S ₉ and S ₂₅ (S ₅ , S ₁₁ , S ₁₃ and S ₁₇ ).

平方剩余码的硬判决译码算法包括三步：求解校验子；计算错误位置多项式；利用钱搜索求得错误位置。Inverse-free BM算法是最有效的求错误位置多项式的方法之一。对于73码而言，采用该算法共需要使用连续12个校验子，即S₁,S₂,…,S₁₂。然而，仅有S₁,S₂,S₃,S₄,S₆,S₈,S₉和S₁₂可以直接从r(x)中计算而得，另外4个校验子是S₅,S₇,S₁₀和S₁₁未知校验子。由文献[2]可知，S₇和S₁₀可分别由S₅的幂次表示，因此我们只需求解S₅和S₁₁。近来，文献[1]提出了一种较快速的硬判决译码算法。以该算法为内核，利用Chase算法可以获得73码的代数软判决译码性能。The hard-decision decoding algorithm for square residual codes includes three steps: solving the syndrome; calculating the error location polynomial; and finding the error location by money search. The Inverse-free BM algorithm is one of the most effective methods to find the error position polynomial. For code 73, the algorithm needs to use 12 consecutive syndromes, that is, S ₁ , S ₂ ,...,S ₁₂ . However, only S ₁ , S ₂ , S ₃ , S ₄ , S ₆ , S ₈ , S ₉ and S ₁₂ can be directly calculated from r(x), and the other four syndromes are S ₅ , S ₇ , S ₁₀ and S ₁₁ are unknown syndromes. According to literature [2], S ₇ and S ₁₀ can be expressed by the power of S ₅ respectively, so we only need to solve S ₅ and S ₁₁ . Recently, literature [1] proposed a faster hard-decision decoding algorithm. With this algorithm as the kernel, the algebraic soft-decision decoding performance of code 73 can be obtained by using Chase algorithm.

发明内容Contents of the invention

针对以上现有技术中的不足，本发明的目的在于提供一种减少译码复杂度、提高译码性能的73平方剩余码的线性规划译码方法，本发明的技术方案如下：For above deficiencies in the prior art, the object of the present invention is to provide a kind of linear programming decoding method of 73 square residual codes that reduces decoding complexity, improves decoding performance, technical scheme of the present invention is as follows:

一种73平方剩余码的线性规划译码方法，其包括以下步骤：A linear programming decoding method of 73 square residual codes, comprising the following steps:

101、将73平方剩余码的码字u经过AWGN信道后传输给接收端，其中u＝[u₁,...,u_n]^T，n表示码长73，接收端接收到的矢量为y，对73平方剩余码初始化，采用矩阵H形式表示73平方剩余码，满足H·u＝0；101. Transmit the codeword u of the 73-square residual code to the receiving end after passing through the AWGN channel, where u=[u ₁ ,...,u _n ] ^T , n represents the code length 73, and the vector received by the receiving end is y , initialize the 73-square residual code, and use matrix H to represent the 73-square residual code, satisfying H·u=0;

102、根据步骤101中得到的矩阵H中每一行，采用自适应添加约束法得出如下线性约束：102. According to each row in the matrix H obtained in step 101, adopt the adaptive addition constraint method to obtain the following linear constraints:

其中N_i表示H矩阵中第i行非零元素下标的集合，并且|V|是奇数.u_j表示第j个码字比特；；N_i\V表示N_i-V这一差集； Where N _i represents the set of subscripts of the i-th row of non-zero elements in the H matrix, And |V| is an odd number. u _j represents the jth codeword bit;; N _i \V represents the difference set of N _i -V;

103、对步骤102中的第j个码字比特u_j采用盒子约束0≤u_j≤1来构造出一个线性规划译码表达式：103. For the j-th codeword bit u _j in step 102, use the box constraint 0≤u _j ≤1 to construct a linear programming decoding expression:

min y^T·umin y ^T u

s.t. 0≤u_j≤1 (1)st 0 ≤ u _j ≤ 1 (1)

$\underset{j j &Element; &Element; V V}{Σ Σ} {u u}_{j j} - - \underset{j j &Element; &Element; {N N}_{i i} \ \ V V}{Σ Σ} {u u}_{j j} \leq \leq | | V V | | - - 11,, &ForAll; &ForAll; V V &SubsetEqual; &SubsetEqual; {N N}_{i i},, | | V V | | isodd isodd$

其中，y＝[y₁,…,y_n]^T表示AWGN信道输出给接收端的矢量；Among them, y=[y ₁ ,...,y _n ] ^T represents the vector output by the AWGN channel to the receiving end;

104、对步骤101中的H矩阵求取冗余行矩阵H^r，并重复步骤102和步骤103得到冗余行矩阵H^r对应的线性规划译码表达式，104. Calculate the redundant row matrix H ^r for the H matrix in step 101, and repeat steps 102 and 103 to obtain the linear programming decoding expression corresponding to the redundant row matrix H ^r ,

min y^T·umin y ^T u

s.t. 0≤u_j≤1 (2)，st 0 ≤ u _j ≤ 1 (2),

$\underset{j j &Element; &Element; V V}{Σ Σ} {u u}_{j j} - - \underset{j j &Element; &Element; {N N}_{i i}^{r r} \ \ V V}{Σ Σ} {u u}_{j j} \leq \leq | | V V | | - - 11,, &ForAll; &ForAll; V V &SubsetEqual; &SubsetEqual; {N N}_{i i}^{r r},, | | V V | | isodd isodd$

将所得到的冗余行矩阵线性规划译码表达式(2)加入步骤103中得到的线性规划译码表达式(1)中，则得到的线性规划译码表达式为：The resulting redundant row matrix linear programming decoding expression (2) is added in the linear programming decoding expression (1) obtained in step 103, then the linear programming decoding expression obtained is:

min y^T·umin y ^T u

s.t. 0≤u_j≤1st 0 ≤ u _j ≤ 1

$\underset{j j &Element; &Element; V V}{Σ Σ} {u u}_{j j} - - \underset{j j &Element; &Element; {N N}_{i i} \ \ V V}{Σ Σ} {u u}_{j j} \leq \leq | | V V | | - - 11,, &ForAll; &ForAll; V V &SubsetEqual; &SubsetEqual; {N N}_{i i},, | | V V | | isodd isodd - - - - - - ((33))$

其中，表示由H矩阵的冗余行组成的新矩阵H^r的第i行非零元素下标的集合，求解表达式(3)，若解出来的码字都满足约束条件，则译码过程结束，否则返回步骤104；如果所有码字比特u_j均为整数，则译码成功，解出来的码字是最大似然码字，若不均为整数则译码失败，并进行分数码字比特进行四舍五入取整。in, Indicates the set of subscripts of non-zero elements in the i-th row of the new matrix H ^r composed of redundant rows of the H matrix, and solves the expression (3). If the codewords solved satisfy the constraints, the decoding process ends, otherwise Return to step 104; if all codeword bits u _j are integers, the decoding is successful, and the codeword obtained is a maximum likelihood codeword, if they are not all integers, the decoding fails, and the fractional codeword bits are rounded Rounding.

进一步的，所述73平方剩余码的码长为73，信息位长度为37，最小汉明距离为13。Further, the code length of the 73 square residual code is 73, the information bit length is 37, and the minimum Hamming distance is 13.

本发明的优点及有益效果如下：Advantage of the present invention and beneficial effect are as follows:

本发明中由于73平方剩余码的H矩阵均是稠密矩阵，采用当同时使用H矩阵和冗余矩阵Hr对应的约束时，性能获得了非常显著的提升。In the present invention, since the H matrix of the 73-square residual code is a dense matrix, when the constraints corresponding to the H matrix and the redundant matrix Hr are used at the same time, the performance is significantly improved.

附图说明Description of drawings

图1为本发明提出的新译码算法与其他译码算法在AWGN信道下的性能对比；Fig. 1 is the performance contrast of new decoding algorithm proposed by the present invention and other decoding algorithms under AWGN channel;

图2为本发明73平方剩余码的线性规划译码方法流程图。Fig. 2 is a flow chart of the linear programming decoding method of the 73 square residual code of the present invention.

具体实施方式Detailed ways

下面结合附图给出一个非限定性的实施例对本发明作进一步的阐述。A non-limiting embodiment is given below in conjunction with the accompanying drawings to further illustrate the present invention.

参照图1-2所示，平方剩余码是分组码的一种，因此也能用奇偶校验矩阵的方式来表示。为简便起见，我们只列出奇偶校验矩阵中每行非零元素的下标。73码的奇偶校验矩阵为：As shown in Figure 1-2, the square residual code is a kind of block code, so it can also be expressed in the form of a parity check matrix. For brevity, we only list the subscripts of the non-zero elements of each row in the parity check matrix. The parity check matrix of the 73 code is:

1 37 38 39 40 41 44 45 46 48 50 51 60 61 63 65 66 67 70 71 72 731 37 38 39 40 41 44 45 46 48 50 51 60 61 63 65 66 67 70 71 72 73

2 37 42 44 47 48 49 50 52 60 62 63 64 65 68 702 37 42 44 47 48 49 50 52 60 62 63 64 65 68 70

3 38 43 45 48 49 50 51 53 61 63 64 65 66 69 713 38 43 45 48 49 50 51 53 61 63 64 65 66 69 71

4 39 44 46 49 50 51 52 54 62 64 65 66 67 70 724 39 44 46 49 50 51 52 54 62 64 65 66 67 70 72

5 40 45 47 50 51 52 53 55 63 65 66 67 68 71 735 40 45 47 50 51 52 53 55 63 65 66 67 68 71 73

6 37 38 39 40 44 45 50 52 53 54 56 60 61 63 64 65 68 69 70 71 736 37 38 39 40 44 45 50 52 53 54 56 60 61 63 64 65 68 69 70 71 73

7 37 44 48 50 53 54 55 57 60 62 63 64 67 69 737 37 44 48 50 53 54 55 57 60 62 63 64 67 69 73

8 37 39 40 41 44 46 48 49 50 54 55 56 58 60 64 66 67 68 71 72 738 37 39 40 41 44 46 48 49 50 54 55 56 58 60 64 66 67 68 71 72 73

9 37 39 42 44 46 47 48 49 55 56 57 59 60 63 66 68 69 70 719 37 39 42 44 46 47 48 49 55 56 57 59 60 63 66 68 69 70 71

10 38 40 43 45 47 48 49 50 56 57 58 60 61 64 67 69 70 71 7210 38 40 43 45 47 48 49 50 56 57 58 60 61 64 67 69 70 71 72

11 39 41 44 46 48 49 50 51 57 58 59 61 62 65 68 70 71 72 7311 39 41 44 46 48 49 50 51 57 58 59 61 62 65 68 70 71 72 73

12 37 38 39 41 42 44 46 47 48 49 52 58 59 61 62 65 67 69 7012 37 38 39 41 42 44 46 47 48 49 52 58 59 61 62 65 67 69 70

13 38 39 40 42 43 45 47 48 49 50 53 59 60 62 63 66 68 70 7113 38 39 40 42 43 45 47 48 49 50 53 59 60 62 63 66 68 70 71

14 39 40 41 43 44 46 48 49 50 51 54 60 61 63 64 67 69 71 7214 39 40 41 43 44 46 48 49 50 51 54 60 61 63 64 67 69 71 72

15 40 41 42 44 45 47 49 50 51 52 55 61 62 64 65 68 70 72 7315 40 41 42 44 45 47 49 50 51 52 55 61 62 64 65 68 70 72 73

16 37 38 39 40 42 43 44 52 53 56 60 61 62 67 69 70 7216 37 38 39 40 42 43 44 52 53 56 60 61 62 67 69 70 72

17 38 39 40 41 43 44 45 53 54 57 61 62 63 68 70 71 7317 38 39 40 41 43 44 45 53 54 57 61 62 63 68 70 71 73

18 37 38 42 48 50 51 54 55 58 60 61 62 64 65 66 67 69 70 7318 37 38 42 48 50 51 54 55 58 60 61 62 64 65 66 67 69 70 73

19 37 40 41 43 44 45 46 48 49 50 52 55 56 59 60 62 68 72 7319 37 40 41 43 44 45 46 48 49 50 52 55 56 59 60 62 68 72 73

20 37 39 40 42 47 48 49 53 56 57 65 66 67 69 70 71 7220 37 39 40 42 47 48 49 53 56 57 65 66 67 69 70 71 72

21 38 40 41 43 48 49 50 54 57 58 66 67 68 70 71 72 7321 38 40 41 43 48 49 50 54 57 58 66 67 68 70 71 72 73

22 37 38 40 42 45 46 48 49 55 58 59 60 61 63 65 66 68 69 7022 37 38 40 42 45 46 48 49 55 58 59 60 61 63 65 66 68 69 70

23 38 39 41 43 46 47 49 50 56 59 60 61 62 64 66 67 69 70 7123 38 39 41 43 46 47 49 50 56 59 60 61 62 64 66 67 69 70 71

24 39 40 42 44 47 48 50 51 57 60 61 62 63 65 67 68 70 71 7224 39 40 42 44 47 48 50 51 57 60 61 62 63 65 67 68 70 71 72

25 40 41 43 45 48 49 51 52 58 61 62 63 64 66 68 69 71 72 7325 40 41 43 45 48 49 51 52 58 61 62 63 64 66 68 69 71 72 73

26 37 38 39 40 42 45 48 49 51 52 53 59 60 61 62 64 66 69 7126 37 38 39 40 42 45 48 49 51 52 53 59 60 61 62 64 66 69 71

27 38 39 40 41 43 46 49 50 52 53 54 60 61 62 63 65 67 70 7227 38 39 40 41 43 46 49 50 52 53 54 60 61 62 63 65 67 70 72

28 39 40 41 42 44 47 50 51 53 54 55 61 62 63 64 66 68 71 7328 39 40 41 42 44 47 50 51 53 54 55 61 62 63 64 66 68 71 73

29 37 38 39 42 43 44 46 50 52 54 55 56 60 61 62 64 66 69 70 71 7329 37 38 39 42 43 44 46 50 52 54 55 56 60 61 62 64 66 69 70 71 73

30 37 41 43 46 47 48 50 53 55 56 57 60 62 66 7330 37 41 43 46 47 48 50 53 55 56 57 60 62 66 73

31 37 39 40 41 42 45 46 47 49 50 54 56 57 58 60 65 66 70 71 72 7331 37 39 40 41 42 45 46 47 49 50 54 56 57 58 60 65 66 70 71 72 73

32 37 39 42 43 44 45 47 55 57 58 59 60 63 65 7032 37 39 42 43 44 45 47 55 57 58 59 60 63 65 70

33 38 40 43 44 45 46 48 56 58 59 60 61 64 66 7133 38 40 43 44 45 46 48 56 58 59 60 61 64 66 71

34 39 41 44 45 46 47 49 57 59 60 61 62 65 67 7234 39 41 44 45 46 47 49 57 59 60 61 62 65 67 72

35 40 42 45 46 47 48 50 58 60 61 62 63 66 68 7335 40 42 45 46 47 48 50 58 60 61 62 63 66 68 73

36 37 38 39 40 43 44 45 47 49 50 59 60 62 64 65 66 69 70 71 72 7336 37 38 39 40 43 44 45 47 49 50 59 60 62 64 65 66 69 70 71 72 73

假设一个码字经过AWGN信道后接收的矢量为y，则相应的最大似然译码可写作如下的整数规划问题Assuming that the vector received by a codeword after passing through the AWGN channel is y, the corresponding maximum likelihood decoding can be written as the following integer programming problem

min y^T·umin y ^T u

s.t. u∈conv(C)s.t.u∈conv(C)

其中u是一个码字，C是相应的码字集合。conv(C)表示C的凸壳，其数学表达式为where u is a codeword and C is the corresponding set of codewords. conv(C) represents the convex hull of C, and its mathematical expression is

$conv conv ((C C)) = = {{\underset{c c &Element; &Element; C C}{Σ Σ} {λ λ}_{c c} c c : : {λ λ}_{c c} &GreaterEqual; &Greater Equal; 00,, \underset{c c &Element; &Element; C C}{Σ Σ} {λ λ}_{c c} = = 11}}$

conv(C)也被称作码字多面体，所有合法码字均是该多面体的顶点，并且多面体上的每个点均对应一个矢量f＝(f₁,…,f_n)。其中，每个分量f_i被定义为一个求和式f_i＝∑_cλ_cc_j。于是，conv(C)可以用有限数量的线性约束来表示。然而，这个数目与码长n呈指数关系。为了降低复杂度，文献[3]将conv(C)放松成一个所谓的基本多面体，该多面体可以通过将H矩阵的每一行所对应的本地码字的凸壳相交而成。conv(C) is also called a codeword polyhedron, all legal codewords are vertices of the polyhedron, and each point on the polyhedron corresponds to a vector f=(f ₁ ,...,f _n ). Wherein, each component f _i is defined as a summation formula f _i =∑ _c λ _c c _j . Thus, conv(C) can be expressed with a finite number of linear constraints. However, this number is exponentially related to the code length n. In order to reduce the complexity, the literature [3] relaxes conv(C) into a so-called basic polyhedron, which can be formed by intersecting the convex hulls of the local codewords corresponding to each row of the H matrix.

众所周知，整数规划问题是个NP-hard问题。如果u中的每个分量改为在[0,1]区间上取值而不是仅仅取值为0或者1，则上述整数规划问题就转化成容易求解的线性规划问题。文献[3]中已经证明，当得到的u是整数解时，则u一定是最大似然码字，这就是线性规划译码所特有的“最大似然验证属性”。As we all know, the integer programming problem is an NP-hard problem. If each component in u is changed to take a value on the [0,1] interval instead of just taking a value of 0 or 1, the above integer programming problem can be transformed into an easy-to-solve linear programming problem. It has been proved in literature [3] that when the obtained u is an integer solution, then u must be a maximum likelihood codeword, which is the unique "maximum likelihood verification property" of linear programming decoding.

详细的73码线性规划译码算法步骤如下：The detailed 73-code linear programming decoding algorithm steps are as follows:

1)初始化1) Initialization

先用矩阵形式表示73码。给定一个合法码字u＝[u₁,K,u_n]^T，其中n表示码长73，它必然满足Express 73 codes in matrix form first. Given a legal codeword u=[u ₁ ,K,u _n ] ^T , where n represents a code length of 73, it must satisfy

H·u＝0H·u=0

2)对于H矩阵的每一行，可以推出如下的一系列线性约束：2) For each row of the H matrix, the following series of linear constraints can be derived:

$\underset{j &Element; V}{Σ} u_{j} - \underset{j &Element; N_{i} \ V}{Σ} u_{j} \leq | V | - 1, &ForAll; V &SubsetEqual; N_{i}$ 并且|V|是奇数. $\underset{j &Element; V}{Σ} u_{j} - \underset{j &Element; N_{i} \ V}{Σ} u_{j} \leq | V | - 1, &ForAll; V &SubsetEqual; N_{i}$ And |V| is odd.

其中N_i表示H矩阵中第i行非零元素下标的集合。Among them, N _i represents the set of subscripts of non-zero elements in the i-th row in the H matrix.

3)采用盒子约束0≤u_j≤1来替换每个码字比特的二元值约束u_j∈{0,1}，则可构造出一个线性规划译码问题：3) Using the box constraint 0≤u _j ≤1 to replace the binary value constraint u _j ∈{0,1} of each codeword bit, a linear programming decoding problem can be constructed:

min y^T·umin y ^T u

s.t. 0≤u_j≤1st 0 ≤ u _j ≤ 1

其中，y＝[y₁,…,y_n]^T表示信道输出矢量。Wherein, y=[y ₁ ,...,y _n ] ^T represents the channel output vector.

4)H矩阵不同行的线性组合称为冗余行，通过将冗余行对应的线性约束加入3)中的线性规划问题可以显著改善译码性能。则最后的线性规划译码问题为：4) The linear combination of different rows of the H matrix is called a redundant row, and the decoding performance can be significantly improved by adding the linear constraints corresponding to the redundant row to the linear programming problem in 3). Then the final linear programming decoding problem is:

min y^T·umin y ^T u

s.t. 0≤u_j≤1st 0 ≤ u _j ≤ 1

其中，表示由H矩阵的冗余行组成的新矩阵H^r的第i行非零元素下标的集合。这里需要说明的是：上述算法的前3步也构成了一种线性规划译码，即只采用H矩阵对应的约束。但是对于73码这种奇偶校验矩阵是稠密矩阵的码型而言，这种译码方法性能并不太好(参见图1)。HD decoding:代数硬判决译码in, Indicates the set of subscripts of the i-th row of non-zero elements of the new matrix H ^r composed of redundant rows of the H matrix. What needs to be explained here is that the first three steps of the above algorithm also constitute a kind of linear programming decoding, that is, only the constraints corresponding to the H matrix are used. But for 73 codes, the parity-check matrix is a dense matrix, the performance of this decoding method is not very good (see Figure 1). HD decoding: algebraic hard decision decoding

SD decoding：基于Chase算法的代数软判决译码SD decoding: algebraic soft decision decoding based on Chase algorithm

LP-I decoding：只采用H矩阵对应的约束的线性规划译码LP-I decoding: linear programming decoding using only the constraints corresponding to the H matrix

LP-II decoding：同时采用H和Hr矩阵对应的约束的线性规划译码LP-II decoding: Linear programming decoding using constraints corresponding to H and Hr matrices at the same time

为简便起见，我们以(7,4,3)汉明码为例来说明上述线性规划译码算法的具体实施方式。该码的H矩阵为：For the sake of simplicity, we take (7,4,3) Hamming code as an example to illustrate the specific implementation of the above-mentioned linear programming decoding algorithm. The H matrix of the code is:

$H h = = [\begin{matrix} 11 & 11 & 11 & 00 & 11 & 00 & 00 \\ 00 & 11 & 11 & 11 & 00 & 11 & 00 \\ 11 & 11 & 00 & 11 & 00 & 00 & 11 \end{matrix}]$

相应的冗余行组成的矩阵H^r是The corresponding redundant row matrix H ^r is

${H h}^{r r} = = [\begin{matrix} 11 & 00 & 00 & 11 & 11 & 11 & 00 \\ 11 & 00 & 11 & 00 & 00 & 11 & 11 \\ 00 & 00 & 11 & 11 & 11 & 00 & 11 \\ 00 & 11 & 00 & 00 & 11 & 11 & 11 \end{matrix}]$

由线性规划译码算法的详细步骤中可知：H和H^r的每一行均对应着2^w-1个约束，其中w代表每行所对应的行重。于是，(7,4,3)汉明码的线性规划译码问题就共有7个变量，63个约束。具体的线性规划译码表达式为：From the detailed steps of the linear programming decoding algorithm, it can be seen that each row of H and H ^r corresponds to 2 ^w-1 constraints, where w represents the row weight corresponding to each row. Therefore, the linear programming decoding problem of (7,4,3) Hamming code has 7 variables and 63 constraints in total. The specific linear programming decoding expression is:

LP0:目标函数：min y^T·uLP0: Objective function: min y ^T u

约束：constraint:

0≤u₁≤1 (1)0≤u ₁ ≤1 (1)

0≤u₂≤1 (2)0≤u ₂ ≤1 (2)

0≤u₃≤1 (3)0≤u ₃ ≤1 (3)

0≤u₄≤1 (4)0≤u4≤1 ( ₄ )

0≤u₅≤1 (5) _0≤u5≤1 (5)

0≤u₆≤1 (6) _0≤u6≤1 (6)

0≤u₇≤1 (7)0≤u7≤1 ( ₇ )

H矩阵对应的约束：Constraints corresponding to the H matrix:

u₁-(u₂+u₃+u₅)≤0 (8)u ₁ -(u ₂ +u ₃ +u ₅ )≤0 (8)

u₂-(u₁+u₃+u₅)≤0 (9)u ₂ -(u ₁ +u ₃ +u ₅ )≤0 (9)

u₃-(u₁+u₂+u₅)≤0 (10)u ₃ -(u ₁ +u ₂ +u ₅ )≤0 (10)

u₅-(u₁+u₂+u₃)≤0 (11)u ₅ -(u ₁ +u ₂ +u ₃ )≤0 (11)

(u₁+u₂+u₃)-u₅≤2 (12)(u ₁ +u ₂ +u ₃ )-u ₅ ≤2 (12)

(u₁+u₂+u₅)-u₃≤2 (13)(u ₁ +u ₂ +u ₅ )-u ₃ ≤2 (13)

(u₁+u₃+u₅)-u₂≤2 (14)(u ₁ +u ₃ +u ₅ )-u ₂ ≤2 (14)

(u₂+u₃+u₅)-u₁≤2 (15)(u ₂ +u ₃ +u ₅ )-u ₁ ≤2 (15)

u₂-(u₃+u₄+u₆)≤0 (16)u ₂ -(u ₃ +u ₄ +u ₆ )≤0 (16)

u₃-(u₂+u₄+u₆)≤0 (17)u ₃ -(u ₂ +u ₄ +u ₆ )≤0 (17)

u₄-(u₂+u₃+u₆)≤0 (18)u ₄ -(u ₂ +u ₃ +u ₆ )≤0 (18)

u₆-(u₂+u₃+u₄)≤0 (19)u ₆ -(u ₂ +u ₃ +u ₄ )≤0 (19)

(u₂+u₃+u₄)-u₆≤2 (20)(u ₂ +u ₃ +u ₄ )-u ₆ ≤2 (20)

(u₂+u₃+u₆)-u₄≤2 (21)(u ₂ +u ₃ +u ₆ )-u ₄ ≤2 (21)

(u₂+u₄+u₆)-u₃≤2 (22)(u ₂ +u ₄ +u ₆ )-u ₃ ≤2 (22)

(u₃+u₄+u₆)-u₂≤2 (23)(u ₃ +u ₄ +u ₆ )-u ₂ ≤2 (23)

u₁-(u₂+u₄+u₇)≤0 (24)u ₁ -(u ₂ +u ₄ +u ₇ )≤0 (24)

u₂-(u₁+u₄+u₇)≤0 (25)u ₂ -(u ₁ +u ₄ +u ₇ )≤0 (25)

u₄-(u₁+u₂+u₇)≤0 (26)u ₄ -(u ₁ +u ₂ +u ₇ )≤0 (26)

u₇-(u₁+u₂+u₄)≤0 (27)u ₇ -(u ₁ +u ₂ +u ₄ )≤0 (27)

(u₁+u₂+u₄)-u₇≤2 (28)(u ₁ +u ₂ +u ₄ )-u ₇ ≤2 (28)

(u₁+u₂+u₇)-u₄≤2 (29)(u ₁ +u ₂ +u ₇ )-u ₄ ≤2 (29)

(u₁+u₄+u₇)-u₂≤2 (30)(u ₁ +u ₄ +u ₇ )-u ₂ ≤2 (30)

(u₂+u₄+u₇)-u₁≤2 (31)(u ₂ +u ₄ +u ₇ )-u ₁ ≤2 (31)

H^r矩阵对应的约束：Constraints corresponding to the H ^r matrix:

u₁-(u₄+u₅+u₆)≤0 (32)u ₁ -(u ₄ +u ₅ +u ₆ )≤0 (32)

u₄-(u₁+u₅+u₆)≤0 (33)u ₄ -(u ₁ +u ₅ +u ₆ )≤0 (33)

u₅-(u₁+u₄+u₆)≤0 (34)u ₅ -(u ₁ +u ₄ +u ₆ )≤0 (34)

u₆-(u₁+u₄+u₅)≤0 (35)u ₆ -(u ₁ +u ₄ +u ₅ )≤0 (35)

(u₁+u₄+u₅)-u₆≤2 (36)(u ₁ +u ₄ +u ₅ )-u ₆ ≤2 (36)

(u₁+u₄+u₆)-u₅≤2 (37)(u ₁ +u ₄ +u ₆ )-u ₅ ≤2 (37)

(u₁+u₅+u₆)-u₄≤2 (38)(u ₁ +u ₅ +u ₆ )-u ₄ ≤2 (38)

(u₄+u₅+u₆)-u₁≤2 (39)(u ₄ +u ₅ +u ₆ )-u ₁ ≤2 (39)

u₁-(u₃+u₆+u₇)≤0 (40)u ₁ -(u ₃ +u ₆ +u ₇ )≤0 (40)

u₃-(u₁+u₆+u₇)≤0 (41)u ₃ -(u ₁ +u ₆ +u ₇ )≤0 (41)

u₆-(u₁+u₃+u₇)≤0 (42)u ₆ -(u ₁ +u ₃ +u ₇ )≤0 (42)

u₇-(u₁+u₃+u₆)≤0 (43)u ₇ -(u ₁ +u ₃ +u ₆ )≤0 (43)

(u₁+u₃+u₆)-u₇≤2 (44)(u ₁ +u ₃ +u ₆ )-u ₇ ≤2 (44)

(u₁+u₃+u₇)-u₆≤2 (45)(u ₁ +u ₃ +u ₇ )-u ₆ ≤2 (45)

(u₁+u₆+u₇)-u₃≤2 (46)(u ₁ +u ₆ +u ₇ )-u ₃ ≤2 (46)

(u₃+u₆+u₇)-u₁≤2 (47)(u ₃ +u ₆ +u ₇ )-u ₁ ≤2 (47)

u₃-(u₄+u₅+u₇)≤0 (48)u ₃ -(u ₄ +u ₅ +u ₇ )≤0 (48)

u₄-(u₃+u₅+u₇)≤0 (49)u ₄ -(u ₃ +u ₅ +u ₇ )≤0 (49)

u₅-(u₃+u₄+u₇)≤0 (50)u ₅ -(u ₃ +u ₄ +u ₇ )≤0 (50)

u₇-(u₃+u₄+u₅)≤0 (51)u ₇ -(u ₃ +u ₄ +u ₅ )≤0 (51)

(u₃+u₄+u₅)-u₇≤2 (52)(u ₃ +u ₄ +u ₅ )-u ₇ ≤2 (52)

(u₃+u₄+u₇)-u₅≤2 (53)(u ₃ +u ₄ +u ₇ )-u ₅ ≤2 (53)

(u₃+u₅+u₇)-u₄≤2 (54)(u ₃ +u ₅ +u ₇ )-u ₄ ≤2 (54)

(u₄+u₅+u₇)-u₃≤2 (55)(u ₄ +u ₅ +u ₇ )-u ₃ ≤2 (55)

u₂-(u₅+u₆+u₇)≤0 (56)u ₂ -(u ₅ +u ₆ +u ₇ )≤0 (56)

u₅-(u₂+u₆+u₇)≤0 (57)u ₅ -(u ₂ +u ₆ +u ₇ )≤0 (57)

u₆-(u₂+u₅+u₇)≤0 (58)u ₆ -(u ₂ +u ₅ +u ₇ )≤0 (58)

u₇-(u₂+u₅+u₆)≤0 (59)u ₇ -(u ₂ +u ₅ +u ₆ )≤0 (59)

(u₂+u₅+u₆)-u₇≤2 (60)(u ₂ +u ₅ +u ₆ )-u ₇ ≤2 (60)

(u₂+u₅+u₇)-u₆≤2 (61)(u ₂ +u ₅ +u ₇ )-u ₆ ≤2 (61)

(u₂+u₆+u₇)-u₅≤2 (62)(u ₂ +u ₆ +u ₇ )-u ₅ ≤2 (62)

(u₅+u₆+u₇)-u₂≤2 (63)(u ₅ +u ₆ +u ₇ )-u ₂ ≤2 (63)

73码的H矩阵是一个稠密矩阵，因此不能直接按上述汉明码的方式写出H和Hr对应的所有约束然后直接求解。文献[4]针对LDPC码提出了一种自适应添加约束的方式，将一个大的线性规划译码问题分解成若干个小的线性规划译码子问题进行求解。我们将该思想应用于73码的线性规划译码问题中，将H矩阵每行对应的约束通过一种自适应的方式加入，即只把那些有用的约束加入线性规划问题中。所谓有用的约束是指不被当前获得的分数解所满足的约束，将其加入原线性规划问题中重新求解即可切除该分数解，使得最终的解尽可能为一整数解(即最大似然码字)。The H matrix of code 73 is a dense matrix, so it is not possible to directly write out all the constraints corresponding to H and Hr in the manner of the above-mentioned Hamming code and then solve them directly. Literature [4] proposes a method of adaptively adding constraints for LDPC codes, which decomposes a large linear programming decoding problem into several small linear programming decoding sub-problems for solution. We apply this idea to the linear programming decoding problem of code 73, and add the constraints corresponding to each row of the H matrix in an adaptive way, that is, only add those useful constraints to the linear programming problem. The so-called useful constraints refer to the constraints that are not satisfied by the currently obtained fractional solution. Adding it to the original linear programming problem and resolving it can cut off the fractional solution, so that the final solution is an integer solution as much as possible (that is, the maximum likelihood Codeword).

事实上，H^r中每行对应的约束也有很多是无用的约束，我们也可以选择性的加入。为了更容易地找到那些有用的约束，我们借用文献[5]中的思想，在加入冗余行所对应的约束时先对得到的中间解u’中的小数分量按可靠性高低进行排序，从而更快捷的找到有用的约束。详情请参见文献[5]。下面仍以(7,4,3)汉明码为例说明其译码过程，假定发送的码字为：1,0,0,1,1,1,0，采用BPSK调制：0--->+1，1--->-1，经过AWGN信道后的输出为y＝[-0.8,-0.1,-0.3,0.1,-0.2,-0.9,0.6]。In fact, the constraints corresponding to each row in H ^r also have many useless constraints, and we can also selectively add them. In order to find those useful constraints more easily, we borrow the ideas in [5], and when adding the constraints corresponding to the redundant rows, we first sort the fractional components in the obtained intermediate solution u' according to the reliability, so that Find useful constraints faster and faster. Please refer to the literature [5] for details. The following is still taking (7,4,3) Hamming code as an example to illustrate its decoding process, assuming that the code word sent is: 1,0,0,1,1,1,0, using BPSK modulation: 0---> +1, 1--->-1, the output after passing through the AWGN channel is y=[-0.8,-0.1,-0.3,0.1,-0.2,-0.9,0.6].

1.先求解下面的线性规划问题：1. First solve the following linear programming problem:

LP1:目标函数：min y^T·uLP1: Objective function: min y ^T u

约束:0≤u_j≤1,1≤j≤7.Constraints: _{0≤uj≤1,1≤j≤7} .

$\{\begin{matrix} 00 \leq \leq {u u}_{j j},, & if if {y the y}_{j j} &GreaterEqual; &Greater Equal; 00 \\ {u u}_{j j} \leq \leq 11,, & if if {y the y}_{j j} < < 00 \end{matrix}$

解出的矢量为：1,1,1,0,1,1,0，此结果不满足LP0中的约束(21)，于是将该约束加入LP1，重新求解。The solved vector is: 1,1,1,0,1,1,0, this result does not satisfy the constraint (21) in LP0, so add this constraint to LP1 and solve again.

2.第二次解出的矢量为：1,0,1,0,1,1,0，此结果不满足LP0中的约束(14)和(24)，于是将这两个约束加入LP1，再次求解。2. The vector solved for the second time is: 1,0,1,0,1,1,0, this result does not satisfy the constraints (14) and (24) in LP0, so these two constraints are added to LP1, Solve again.

3.第三次解出的矢量为：1,1,1,1,1,1,0，此结果不满足LP0中的约束(28)，于是将这个约束继续加入LP1，重新求解。3. The vector obtained for the third solution is: 1,1,1,1,1,1,0. This result does not satisfy the constraint (28) in LP0, so add this constraint to LP1 and solve again.

4.第四次解出的矢量为：1,0.666667,0.666667,0.333333,1,1,0,此时H对应的所有约束都被满足，但LP0中的约束(38),(44)和(60)不被满足，注意到这3个约束是Hr对应的约束。于是将其加入LP1，再次求解。4. The vectors solved for the fourth time are: 1, 0.666667, 0.666667, 0.333333, 1, 1, 0. At this time, all the constraints corresponding to H are satisfied, but the constraints (38), (44) and ( 60) is not satisfied, notice that these three constraints are constraints corresponding to Hr. So add it to LP1 and solve again.

5.第五次解出的矢量为：1,0,0,1,1,1,0,此时所有的约束都被满足，译码过程结束。根据线性规划译码的特性，解出来的码字一定是最大似然码字，而且也刚好是我们发送的码字。5. The vector obtained for the fifth solution is: 1,0,0,1,1,1,0. At this time, all constraints are satisfied, and the decoding process ends. According to the characteristics of linear programming decoding, the decoded codeword must be the maximum likelihood codeword, and it happens to be the codeword we sent.

需要特别强调的是，由于不能以较短的篇幅列举出73码的所有约束，因此以(7,4,3)汉明码为例说明本发明中的线性规划译码方法的具体过程。对于73码，其译码过程与(7,4,3)汉明码完全一样。此外，本发明中的线性规划译码方法虽然针对的是73码，但是对于其他的平方剩余码也适用。与LDPC码等有着稀疏的奇偶校验矩阵的分组码不同，平方剩余码的H矩阵均是稠密矩阵，因此如果只使用H矩阵对应的约束性能将会很差，这从图1中即可看出。然而，当同时使用H矩阵和冗余矩阵Hr对应的约束时，性能获得了非常显著的提升。由图1可知：在AWGN信道下，当bit error rate(BER)＝3×10^-6时，采用线性规划译码方法，相比基于Chase算法的代数软判决译码方法，可以获得约0.9dB的增益。It should be emphasized that since all the constraints of code 73 cannot be listed in a short space, the (7,4,3) Hamming code is taken as an example to illustrate the specific process of the linear programming decoding method in the present invention. For 73 yards, its decoding process is exactly the same as that of (7,4,3) Hamming code. In addition, although the linear programming decoding method in the present invention is aimed at 73 codes, it is also applicable to other square residual codes. Unlike block codes with sparse parity check matrixes such as LDPC codes, the H matrix of the square residual code is a dense matrix, so if only the H matrix is used, the constraint performance corresponding to it will be poor, as can be seen from Figure 1 out. However, when using constraints corresponding to both the H matrix and the redundancy matrix Hr, the performance is significantly improved. It can be seen from Figure 1 that: under the AWGN channel, when the bit error rate (BER) = 3 × 10 ^-6 , using the linear programming decoding method, compared with the algebraic soft-decision decoding method based on the Chase algorithm, can obtain about 0.9dB gain.

以上这些实施例应理解为仅用于说明本发明而不用于限制本发明的保护范围。在阅读了本发明的记载的内容之后，技术人员可以对本发明作各种改动或修改，这些等效变化和修饰同样落入本发明方法权利要求所限定的范围。The above embodiments should be understood as only for illustrating the present invention but not for limiting the protection scope of the present invention. After reading the content of the present invention, the skilled person can make various changes or modifications to the present invention, and these equivalent changes and modifications also fall within the scope defined by the method claims of the present invention.

Claims

1. A linear programming decoding method of 73 square residue codes is characterized by comprising the following steps:

101. transmitting a code word u of the 73 square residue code to a receiving end after passing through an AWGN channel, wherein u is [ u ═ u₁,...,u_n]^TN represents the code length 73, the vector received by the receiving end is y, the 73 square residue code is initialized, the 73 square residue code is represented in a matrix H form, and H.u is equal to 0;

102. according to each row in the matrix H obtained in the step 101, a self-adaptive constraint adding method is adopted to obtain the following linear constraints:

wherein N is_iRepresents the set of the i-th row non-zero element subscripts in the H matrix,N_iand | V | is an odd number_jRepresents the jth codeword bit; (ii) a N is a radical of_iV represents N_i-V this difference set;

103. for the j code word bit u in step 102_jRestraining u to be more than or equal to 0 by adopting box_jAnd ≦ 1 to construct a linear programming decoding expression:

min y^T·u

s.t. 0≤u_j≤1 (1)

<math> <mrow> <munder> <mi>Σ</mi> <mrow> <mi>j</mi> <mo>&Element;</mo> <mi>V</mi> </mrow> </munder> <msub> <mi>u</mi> <mi>j</mi> </msub> <mo>-</mo> <munder> <mi>Σ</mi> <mrow> <mi>j</mi> <mo>&Element;</mo> <msub> <mi>N</mi> <mi>i</mi> </msub> <mo>\</mo> <mi>V</mi> </mrow> </munder> <msub> <mi>u</mi> <mi>j</mi> </msub> <mo>≤</mo> <mo>|</mo> <mi>V</mi> <mo>|</mo> <mo>-</mo> <mn>1</mn> <mo>,</mo> <mo>&ForAll;</mo> <mi>V</mi> <mo>&SubsetEqual;</mo> <msub> <mi>N</mi> <mi>i</mi> </msub> <mo>,</mo> <mo>|</mo> <mi>V</mi> <mo>|</mo> <mi>isodd</mi> </mrow> </math>

wherein y ═ y₁,…,y_n]^TA vector representing the output of the AWGN channel to the receiving end;

104. solving the H matrix in step 101Redundant row matrix H is taken^rAnd repeating the steps 102 and 103 to obtain a redundant row matrix H^rCorresponding linear programming decoding expression, min y^T·u

s.t. 0≤u_j≤1 (2)，

<math> <mrow> <munder> <mi>Σ</mi> <mrow> <mi>j</mi> <mo>&Element;</mo> <mi>V</mi> </mrow> </munder> <msub> <mi>u</mi> <mi>j</mi> </msub> <mo>-</mo> <munder> <mi>Σ</mi> <mrow> <mi>j</mi> <mo>&Element;</mo> <msubsup> <mi>N</mi> <mi>i</mi> <mi>r</mi> </msubsup> <mo>\</mo> <mi>V</mi> </mrow> </munder> <msub> <mi>u</mi> <mi>j</mi> </msub> <mo>≤</mo> <mo>|</mo> <mi>V</mi> <mo>|</mo> <mo>-</mo> <mn>1</mn> <mo>,</mo> <mo>&ForAll;</mo> <mi>V</mi> <mo>&SubsetEqual;</mo> <msubsup> <mi>N</mi> <mi>i</mi> <mi>r</mi> </msubsup> <mo>,</mo> <mo>|</mo> <mi>V</mi> <mo>|</mo> <mi>isodd</mi> </mrow> </math>

Adding the obtained redundant row matrix linear programming decoding expression (2) into the linear programming decoding expression (1) obtained in the step 103, wherein the obtained linear programming decoding expression is as follows:

min y^T·u

s.t. 0≤u_j≤1

<math> <mrow> <munder> <mi>Σ</mi> <mrow> <mi>j</mi> <mo>&Element;</mo> <mi>V</mi> </mrow> </munder> <msub> <mi>u</mi> <mi>j</mi> </msub> <mo>-</mo> <munder> <mi>Σ</mi> <mrow> <mi>j</mi> <mo>&Element;</mo> <msub> <mi>N</mi> <mi>i</mi> </msub> <mo>\</mo> <mi>V</mi> </mrow> </munder> <msub> <mi>u</mi> <mi>j</mi> </msub> <mo>≤</mo> <mo>|</mo> <mi>V</mi> <mo>|</mo> <mo>-</mo> <mn>1</mn> <mo>,</mo> <mo>&ForAll;</mo> <mi>V</mi> <mo>&SubsetEqual;</mo> <msub> <mi>N</mi> <mi>i</mi> </msub> <mo>,</mo> <mo>|</mo> <mi>V</mi> <mo>|</mo> <mi>isodd</mi> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>3</mn> <mo>)</mo> </mrow> </mrow> </math>

wherein,representing a new matrix H consisting of redundant rows of the H matrix^rSolving the expression (3) of the set of the i-th row nonzero element subscripts, and if the solved code words all meet the constraint condition, thenEnding the decoding process, otherwise returning to the step 104; if all codeword bits u_jIf the number of the codes is all integer, decoding is successful, the decoded code words are maximum likelihood code words, if the number of the codes is not all integer, decoding is failed, and rounding up is carried out on fraction code word bits.

2. The linear programming decoding method of 73 square residue code as claimed in claim 1, wherein: the code length of the 73 square residue code is 73, the information bit length is 37, and the minimum Hamming distance is 13.