Solving linear systems of determinant frequently zero over finite field GF(2) (Q1262699)

The paper deals with the solution of linear systems of the form \(Ax=b\) over the finite field GF(2). The best known computational methods consider only systems with nonzero determinant. The purpose of the paper is to solve systems with \(\det (A)=0.\) The authors first compute the probability of \(\det (A)=0\) over GF(2), a question of interest in application to the decoding of algebraic linear codes over GF(2). Then an algorithm is proposed and tree data structure is given to accomplish the computational tasks of the algorithm, which takes 2n-1 systolic cycles, yielding time complexity O(n). Advantages and disadvantages of this algorithm for VLSI implementations are discussed, based on consideration of speed, chip area, and regularity. Finally, some comments on the extension to systems over GF(p) are given.