N-POINT COMPLEX FOURIER TRANSFORM STRUCTURE HAVING ONLY 2N REAL MULTIPLIES, AND OTHER MATRIX MULTIPLY OPERATIONS
An integrated circuit chip implementing multiplication of an MxN element matrix with an N-element vector to obtain an M-element product by combining the vector with rows of bits of the same significance selected from the matrix one bit-row at a time to form partial products, exploiting the fact that the same potential combinations are needed for all bit-rows and all matrix rows to precompute all of the combinations once and for all, and combining selected partial products for different bit place-significance with a shift-and-add operation only once for each of the M product elements, thereby effectively using only M multiply-equivalent structures. An N-point Complex Fourier Transform can therefore be claimed which only needs 2N real multiplies and the product of an NxN matrix with another NxN matrix requires only N2 multiplies.