Split manageable efficient algorithm for Fourier and Hadamard transforms

In this paper, a general, efficient, manageable split algorithm to compute one-dimensional (1-D) unitary transforms, by using the special partitioning in the frequency domain, is introduced, The partitions determine fast tran sformations that split the N-point unitary transform into a set of N-i-poin t transforms i = 1: n (N-1 + ... + N-n = N). Here, we introduce a class of splitting transformations: the so-called paired transforms. Based on these transforms, the decompositions of the Fourier transforms of arbitrary order s are given, and the corresponding algorithms are considered, Comparative e stimates revealing the efficiency of the proposed algorithms with respect t o the known ones are given. In particular, a proposed method of calculating the 2(r)-point Fourier transform requires 2(r-1) (r - 3) + 2 multiplicatio ns and 2(r-1) (r + 9) - r(2) - 3r - 6 additions. In terms of the paired tra nsforms, the splitting of the 2(r)-point Hadamard transform is described. A s a result, the proposed algorithm for computing this transform uses on the average no more than six operations of additions per sample.