Prime-composition approach to Ramanujan-Fourier transform computation

Abstract

Ramanujan sums (RS) and their Fourier transforms have attracted more and more attention in signal processing in recent years. Due to their non-periodic and non-uniform spectrum, RS are widely used in low-frequency noise processing, Doppler spectrum estimation and time-frequency analysis. However, the traditional method for calculating RS values is rather complex since it requires two numbers’ factorization in two arithmetic functions. For a length-n vector, its Ramanujan-Fourier transform usually involves a series of RS values which will occupy O(n ²) memory units. Thus, in this paper an approach based on prime-composition is proposed to reduce the complexity of RS calculation to O(n ²). Meanwhile, the complexity of Ramanujan-Fourier transform can be further reduced from O(n ²) to O(nln(ln(n))).

Keywords

Ramanujan sums / Ramanujan-Fourier transform / prime-composition

References

[1] Ramanujan S. On certain trigonometric sums and their applications in the theory of numbers[J]. Trans. Camb. Phil Soc., 1918, 22, 259-276.

[2] Carmichael R D. Expansions of arithmetical functions in infinite series[J]. Proceedings of the London Mathematical Society, 1932, s2–34(1): 1-26.

[3] Gadiyar H G, Padma R. Linking the circle and the sieve: Ramanujan-Fourier series [EB/OL]. 2006

[4] Planat M, Rosu H, Perrine S. Ramanujan sums for signal processing of low-frequency noise[C]. IEEE International Frequency Control Symposium and PDA Exhibition. Louisiana, USA, 2002 715-720.

[5] Lagha M, Bensebti M. Doppler spectrum estimation by Ramanujan-Fourier transform(rft)[J]. Digital Signal Processing, 2009, 19(5): 843-851.

[6] Mainardi L T, Bertinelli M, Sassi R. Analysis of T-wave alternans using the Ramanujan transform[C]. Computer in Cardiology. Bologna, Italy, 2008 605-608.

[7] Sugavaneswaren L, Xie S, Umapathy K, et al. Timefrequency analysis via Ramanujan sums[J]. Signal Processing Letters, IEEE, 2012, 19(6): 352-355.

[8] Samadi S, Ahmad M O, Swamy M N. Ramanujan sums and discrete Fourier transforms[J]. Signal Processing Letters, IEEE, 2005, 12(4): 293-296.

[9] Pei S C, Chang K W. Odd Ramanujan sums of complex roots of unity[J]. Signal Processing Letters, IEEE, 2007, 14(1): 20-23.

[10] Planat M, Minarovjech M, Saniga M. Ramanujan sums analysis of long-period sequences and 1/f noise[J]. Europhysics Letters(EPL), 2009, 85(4): 1-5.

[11] Hardy G H, Ramanujan S. The normal number of prime factors of a number[J]. Quarterly Journal of Mathematics, 1917, 48, 76-92.

[12] Eric B, Jeffrey S. Algorithmic Number Theory[M]. 1996, Cambridge: MIT Press.

[13] Noblom M A. Counting the perfect powers[J]. Applied Probability Trust, 2008, 41(1): 27-31.