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

摘要

In this brief, two different approaches to compute the 2-Dndiscrete Hadamard transform (DHAT) of sizes 2r×2rn, r>1 are presented. Both are based on the so-called 1-Dndiscrete paired transforms, which split the 2r-point DHATninto a set of smaller 2r-1-point transforms, i=1:r. The firstnapproach is a column (row)-wise algorithm which requires, on average, nonmore than 12 operations of additions per sample. The second approach isna splitting algorithm, in which then2r×2r-point DHAT is reduced to thencomputation of 2r-13 1-D DHATs instead of 2r+1 1-DnDHAT's in the column (row)-wise algorithm, but requires more operationsnof additions. Examples and comparison of the proposed algorithms withnthe known algorithms are provided