[HGI-News] HGI-Seminar, Montag 22.05.06: SMITH - A Parallel Hardware Architecture for fast Gaussian Elimination over GF(2)

[Newsletter des Horst Görtz Instituts]

                      Marius Mertens, COSY-Group, RUB

                Montag 22. Mai 2006, 13:15 Uhr IC 4 / 39-41

                 SMITH - A Parallel Hardware Architecture
                 for fast Gaussian Elimination over GF(2)

This talk presents a hardware-optimized variant of the well-known Gaussian
elimination over GF(2) and its highly efficient implementation. The proposed
hardware architecture can solve any regular and (uniquely solvable) over-
determined linear system of equations (LSE) and is not limited to matrices
of a certain structure. Besides solving LSEs, the architecture at hand can
also accomplish the related problem of matrix inversion extremely fast.

As proof-of-concept the architecture has been realized on a contemporary
low-cost FPGA. The implementation for a 50 × 50 LSE can be clocked with a
frequency of up to 300 MHz and computes the solution in 0.33us on average.

In addition, the physical requirements for larger implementations are
discussed with special focus on the limitations imposed by current CMOS
technology and how they could possibly be overcome using optical components.

_____________________________________________________________________________
Die Webseite des HGI-Seminars mit allen Informationen zu vergangenen und
zukünftigen Vorträgen: http://www.hgi.rub.de/deutsch/lehrangebot/seminar.html