Tree structures for orthogonal transform and application to the Hadamard transform

Tree structures for computing orthogonal transforms are introduced. Two cases, delay trees and decimation trees, are investigated. A simple condition, namely the orthogonality of branches with a common root, is shown to be necessary and sufficient for the overall transform to be orthogonal. Main advantages are structural simplicity and a number of operations proportional to N Log2N. Application of the tree structures to the Walsh-Hadamard Transform (in natural, sequency and dyadic order) is presented. A single module can be multiplexed or used in parallel in order to perform all operations. Such a system is shown to be well suited for hardware implementation.