Semisystolic architecture for fast Hartley transform: decimation in frequency and radix 2

A parallel architecture is presented for the calculation of the fast Hartley transform (FHT) radix 2 which is adequate for its implementation in VLSI technology. As a first step, a constant geometry (decimation in frequency) algorithm for computing the FHT has been developed. The circuit proposed is characterised by its modular design and its interconnection regularity. It can be considered as semi-systolic. It is highly efficient and flexible. It permits the computation of arbitrarily sized FHTs as a consequence of data recirculation over the processing units in all the stages of the transform. The number of communications is the least possible due to the use of a constant geometry algorithm. Each calculation stage requires N/4Q cycles where N and Q are the length of the input real sequence and the number of processors (N =2², Q=2^q), respectively. The system proposed calculates the FHT in n stages, therefore, the total calculation time is (N log₂ N)/4Q cycles