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

摘要

In this paper, an effective column(row)-wise algorithm forncomputing the two-dimensional discrete Hadamard transform (2-D DHAT) ofnsize 2r×2r, r>1, by using the pairednalgorithm of the one-dimensional DHAT, is considered. A new class ofnso-called discrete paired transforms, which split then2r-point DHAT, r>1, into a set of smallern2r-i-point transforms, i=1: n, is introduced. Based on suchnsplitting, the algorithm for computing the 2-D DHAT requires on averagenno more than 12 operations of additions per sample