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 two-dimensional discrete Hadamard transform (2-D DHAT) of size 2^r×2^r, r>1, by using the paired algorithm of the one-dimensional DHAT, is considered. 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 the 2-D DHAT requires on average no more than 12 operations of additions per sample