This paper presents a matrix permuting approach to the construction of Low-Density Parity-Check (LDPC) code. It investigates the structure of the sparse parity-check matrix defined by Gallager. It is discovered that t...This paper presents a matrix permuting approach to the construction of Low-Density Parity-Check (LDPC) code. It investigates the structure of the sparse parity-check matrix defined by Gallager. It is discovered that the problem of constructing the sparse parity-check matrix requires an algorithm that is efficient in search environments and also is able to work with constraint satisfaction problem. The definition of Q-matrix is given, and it is found that the queen algorithm enables to search the Q-matrix. With properly permuting Q-matrix as sub-matrix, the sparse parity-check matrix which satisfied constraint condition is created, and the good regular-LDPC code that is called the Q-matrix LDPC code is generated. The result of this paper is significant not only for designing low complexity encoder, improving performance and reducing complexity of iterative decoding arithmetic, but also for building practical system of encodable and decodable LDPC code.展开更多
A generalization of the well-known n-queen problem is to put N×k‘queens’on an k×nchessboard in such a way that each row and each column contains exactly k‘queens’and eachdiagonal with length from 1 to n ...A generalization of the well-known n-queen problem is to put N×k‘queens’on an k×nchessboard in such a way that each row and each column contains exactly k‘queens’and eachdiagonal with length from 1 to n and slope either 1 or -1 contains at most k‘queens’.Aconstruction is given to show that this is always possible whenever n≥4 and n≥k≥1.展开更多
Let Z_n be the set of residue classes modulo n and let r, s,…be its elements.If the set S={(R_i, S_i)|i=1, 2,…, m}Z_nxZ_n(0【m≤n) satisfies the conditions that R_i≠R_j, S_i≠S_j, S_i+R_i≠S_j+R_j and S_i-R_i≠S_j-...Let Z_n be the set of residue classes modulo n and let r, s,…be its elements.If the set S={(R_i, S_i)|i=1, 2,…, m}Z_nxZ_n(0【m≤n) satisfies the conditions that R_i≠R_j, S_i≠S_j, S_i+R_i≠S_j+R_j and S_i-R_i≠S_j-R_j when i≠j, then we say that S is a partial n-solution with m elements.展开更多
基金Supported by the National Natural Science Foundation of China (No.60572050)by the National Science Foundation of Hubei Province (No.2004ABA049)
文摘This paper presents a matrix permuting approach to the construction of Low-Density Parity-Check (LDPC) code. It investigates the structure of the sparse parity-check matrix defined by Gallager. It is discovered that the problem of constructing the sparse parity-check matrix requires an algorithm that is efficient in search environments and also is able to work with constraint satisfaction problem. The definition of Q-matrix is given, and it is found that the queen algorithm enables to search the Q-matrix. With properly permuting Q-matrix as sub-matrix, the sparse parity-check matrix which satisfied constraint condition is created, and the good regular-LDPC code that is called the Q-matrix LDPC code is generated. The result of this paper is significant not only for designing low complexity encoder, improving performance and reducing complexity of iterative decoding arithmetic, but also for building practical system of encodable and decodable LDPC code.
文摘A generalization of the well-known n-queen problem is to put N×k‘queens’on an k×nchessboard in such a way that each row and each column contains exactly k‘queens’and eachdiagonal with length from 1 to n and slope either 1 or -1 contains at most k‘queens’.Aconstruction is given to show that this is always possible whenever n≥4 and n≥k≥1.
文摘Let Z_n be the set of residue classes modulo n and let r, s,…be its elements.If the set S={(R_i, S_i)|i=1, 2,…, m}Z_nxZ_n(0【m≤n) satisfies the conditions that R_i≠R_j, S_i≠S_j, S_i+R_i≠S_j+R_j and S_i-R_i≠S_j-R_j when i≠j, then we say that S is a partial n-solution with m elements.