An Improved GF(2) Matrix Inverter with Linear Time Complexity

This paper presents a new hardware implementation for boolean matrix inverters. A circuit capable of inverting a nonsingular N×N matrix in exactly N clock cycles is introduced, described, and tested in FPGA devices. This is an improvement over the fastest implementation reported to date, which computes the inverted matrix in 2N clock cycles on average or (N²+N)/2 clock cycles in the worst case. The time complexity of the proposed circuit is fixed (N clock cycles), which is important when the circuit must be used as part of a high performance or real-time system. The overall circuit operation is based on the Gauss-Jordan (GJ) elimination method, with the addition of several modifications in order to make the algorithm more hardware-oriented. The resulting hardware is still compact compared to a direct implementation of the traditional GJ algorithm, however less compact than the variable-time implementation referred to above.