Fast computation of the discrete Walsh and Hadamard transforms

The discreteWalsh and Hadamard transforms are often used in image processing tasks such as image coding, pattern recognition, and sequency filtering. In this correspondence, a new discrete Walsh transform (DWT) algorithm is derived in which a modified form of the DWT relation is decomposed into smaller-sized transforms using vectorized quantities. A new sequency-ordered discrete Hadamard transform (DHAT) algorithm is also presented. The proposed approach results in more regular algorithms requiring no independent data swapping and fewer array-index updating and bit-reversal operations. An analysis of the computational complexity and the execution time performance are provided. The results are compared with those of the existing algorithms.