Prime-composition approach to Ramanujan-Fourier transform computation |
| |
| Authors: | Lina Zhou Zulin Wang Lei Zhao |
| |
| Institution: | 1. School of Electronic and Information Engineering, Beihang University, Beijing, 100083, China
|
| |
| 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 2) memory units. Thus, in this paper an approach based on prime-composition is proposed to reduce the complexity of RS calculation to O(n 2). Meanwhile, the complexity of Ramanujan-Fourier transform can be further reduced from O(n 2) to O(nln(ln(n))). |
| |
| Keywords: | Ramanujan sums Ramanujan-Fourier transform prime-composition |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ |
|
