Method of fast 1-D paired transforms for computing the 2-D discrete Hadamard transform

In this paper, an effective column(row)-wise algorithm for computing the tw o-dimensional discrete Hadamard transform (2-D DHAT) of size 2(r) X 2(r), r > 1, by using the paired algorithm of the one-dimensional DHAT, is conside red, A new class of so-called discrete paired transforms, which split the 2 (r)-point DHAT, r > 1, into a set of smaller 2(r-i)-point transforms, i = 1 : n, is introduced. Based on such splitting, the algorithm for computing th e 2-D DHAT requires on average no more than 12 operations of additions per sample.