Extended Bit-Flipping Algorithm for Solving Sparse Linear Systems of Equations Modulo p

被引：0

作者：

Abolpour, Asie ^{[1
]}

Sadeghi, Mohammad-Reza ^{[1
]}

Panario, Daniel ^{[2
]}

机构：

[1] Amirkabir Unvers Technol, Fac Math & Comp Sci, Hafez Ave, Tehran, Iran

[2] Carleton Univ, Sch Math & Stat, Ottawa, ON K1S 5B6, Canada

来源：

2011 IEEE INFORMATION THEORY WORKSHOP (ITW) | 2011年

关键词：

GF(2);

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let p be a prime number. We propose a new method for solving sparse linear systems of equations modulo p when the coefficient matrix has column degree at most 2. This algorithm is based on a well-known decoding algorithm for Low-Density Parity-Check (LDPC) codes called bit-flipping (BF) algorithm. We modify and extend this hard-decision decoding algorithm. The complexity of this algorithm is linear in terms of the number of columns n and the number of nonzero coefficients w of the matrix. We give a detailed small example, and report on computational results for larger systems.

引用

页数：5

共 12 条

[1] [Anonymous], P IEEE CPMT S AUG
[2] [Anonymous], 1963, Low-Density Parity-Check Codes
[3] [Anonymous], 2009, PUBLIC KEY CRYPTOGRA
[4] SOLVING LINEAR-EQUATIONS OVER GF(2) - BLOCK LANCZOS-ALGORITHM
COPPERSMITH, D
[J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 1993, 192 : 33 - 60
[5] SOLVING HOMOGENEOUS LINEAR-EQUATIONS OVER GF(2) VIA BLOCK WIEDEMANN ALGORITHM
COPPERSMITH, D
[J]. MATHEMATICS OF COMPUTATION, 1994, 62 (205) : 333 - 350
[6] Discrete Logarithms in GF(p)
Coppersmith, Don
Odlzyko, Andrew M.
Schroeppel, Richard
[J]. ALGORITHMICA, 1986, 1 (1-4) : 1 - 15
[7] Reduced complexity iterative decoding of low-density parity check codes based on belief propagation
Fossorier, MPC
Mihaljevic, M
Imai, H
[J]. IEEE TRANSACTIONS ON COMMUNICATIONS, 1999, 47 (05) : 673 - 680
[8] LAMACCHIA BA, 1991, LECT NOTES COMPUT SC, V537, P109
[9] Near Shannon limit performance of low density parity check codes
MacKay, DJC
Neal, RM
[J]. ELECTRONICS LETTERS, 1996, 32 (18) : 1645 - 1646
[10] A RECURSIVE APPROACH TO LOW COMPLEXITY CODES
TANNER, RM
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 1981, 27 (05) : 533 - 547

← 1 2 →