Prime-length real-valued polynomial residue division algorithms

One class of efficient algorithms for computing a discrete Fourier transform (DFT) is based on a recursive polynomial factorization of the polynomial 1 - z(-N). The Bruno algorithm is a typical example of such algorithms. Recently, the Bruun algorithm, which is applicable only when system lengths are powers of two in its original form, is generalized and modified to be applicable to the case when the length is other than a power of two. This generalized algorithm consists of transforms T-d,T-f with prime d and real f in the range 0 less than or equal to f < 0.5. T-d,T-0 computes residues X(z)mod(1-z(-2)) and X(z)mod(1-2 cos(pik/d)z(-1)+z(-2)), k = 1,2,...,d - 1, and T-d,T-f(f not equal 0) computes residues X(z)mod(1 - 2cos(2pi(f + k)/d)z(-1) + z(-2)), k = 0, 1,..., d - 1 for a given real signal X (z) of length 2d. The purpose of this paper is to find efficient algorithms for T-d,T-f. First, polynomial factorization algorithms are derived for T-d,T-0 and T-d,T-1/4. When f is neither 0 nor 1/4, it is not feasible to derive a polynomial factorization algorithm. Two different implementations of T-d,T-f for such f are derived. One implementation realizes T-d,T-f via a d-point DFT, for which a variety of fast algorithms exist. The other implementation realizes T-d,T-f via T-d,T-1/4, for which the polynomial factorization algorithm exists. Comparisons show that for d greater than or equal to 5, these implementations achieve better performance than computing each output of T-d,T-f separately.