A novel fft pruning algorithm: improving efficiency for a nc-ofdm cognitive radio

Abstract

Cognitive Radio (CR) is a promising candidate to deploy future wireless networks because CR can enable an efficient use of the resources involved in wireless communications networks, specifically the Electromagnetic (EM) spectrum. Recent research shows that there is an overuse of some spectrum bands such as cell phone or IEEE 802.11 bands; meanwhile, other bands such as the regional analog television are abandoned. This current allocation of the EM spectrum yields an underutilization of this resource. Furthermore, this misallocation has generated a false notion of a spectrum scarcity. Thus, trying to solve the current underutilization of the channel, an interdisciplinary research is addressing all aspects related to this problem, namely, technical, scientific, and regulatory. Specifically, from a technical-scientific point of view, a transmission model where a secondary non-licensed user could use the bands assigned to incumbent (licensed) users without causing any interference has been proposed. This approach is known as opportunistic use of the spectrum and offers great challenges in terms of implementation. In the physical layer, many modulation schemes have been proposed, but Non-Contiguous OFDM appears to be a suitable candidate to build practical CR systems (NC-OFDMCR). According to the availability of the spectrum, the cognitive engine of a NC-OFDMCR selects the transmission pattern activating or deactivating specific bands of sub-carriers. In this work, the main goal is to contribute to the implementation of NC-OFDMCR in the physical layer performing a research on the implementation issues. Among these is- sues, the most important one is the computation of the Discrete Fourier Transform (DFT) for sparse signals. This work shows the mathematical and computational (implementation) aspects related to the DFT. Then, the work proposes an algorithm based on Cooley-Tukey Radix-2 Fast Fourier Transform (FFT) to calculate the DFT using a hybrid dynamic structure to represent sparse signals. When the dynamic structure is traversed, irrelevant computations can be pruned. The algorithm is evaluated for signal lengths greater than 216, and it shows efficient results. These lengths are important in the sense that they allow to perform NC-OFDM wide-transmissions. Besides, the proposed data structure enables the representation of sparse signals in other algorithms that compute the DFT such as those based on Polynomial Algebras. In addition, the algorithm is coded in C-language allowing its implementation in other platforms.

La radio cognitiva (CR por sus siglas en inglés) es un candidato prometedor para construir las redes en el futuro debido a que CR puede hacer posible un uso eficiente de los recursos envueltos en las redes de comunicación inalámbricas. Dentro de estos recursos está el Espectro Electromagnético (EM). Investigaciones recientes, muestran que existe un sobreuso de algunas bandas del espectro tales como la usada por celulares o IEEE802.11, mientras otras bandas como la usada para la television análoga regional están prácticamente abandonadas. Esta asignación del espectro EM conlleva a una subutilización de este recurso. Además, está asignación deficiente ha generado una falsa noción de escases del espectro. Tratando de resolver la actual subutilización del espectro de manera general, una investigación interdisciplinaria está evaluando todos los aspectos relacionados a este problema, a saber, problemas técnicos, científicos y de regulación (legislación). Desde un punto de vista técnico-científico, se ha propuesto un modelo donde usuarios secundarios ”sin licencia” pueden usar las bandas asignadas a usuarios propietarios (licenciados) sin causar ninguna interferencia. Este modelo es conocido como uso oportunista del espectro, ofreciendo grandes retos en términos de implementación. Ya en la capa física, han sido propuestos muchos esquemas de modulación, pero OFDM no contiguo, aparece como un candidato oportuno para construir sistemas prácticos de CR (NC-OFDMCR por sus siglas en ingles). De acuerdo a la disponibilidad del espectro, el modulo de cognición del NC-OFDMCR selecciona el patrón de transmisión activando o desactivando bandas especificas de sub-portadoras. En este trabajo, el objetivo principal es contribuir a la implementación de NC-OFDMCR en la capa física, llevando a cabo una investigación en los problemas de implementación. Entre estos problemas, el que más se destaca es el cómputo de la Transformada Discreta de Fourier (TDF) para señales esparcidas. Este trabajo muestra los aspectos matemáticos y computacionales (implementación) de la TDF. Entonces, el trabajo propone un algoritmo basado en el algortimo Cooley-Tukey Radix-2 para calcular la Transformada Rápida de Fourier (FFT por sus siglas en ingles) para calcular la DFT usando una estructura dinámica híbrida para representar las señales esparcidas. Cuando la estructura dinamica es recorrida, las computaciones irrelevantes pueden ser descartadas (podadas). El algoritmo es evaluado para largos de señales mayores de 216 mostrando resultados eficientes. Esto permite llevar acabo transmisiones NC-OFDMCR de banda ancha. Asimismo, la estructura de datos propuesta permite la representación de señales esparcidas en otros algoritmos para computar la TDF, tales como aquellos basados en Algebras Polinomiales. Igualmente, el algoritmo esta codificado en lenguaje C permitiendo así su implementación en otras plataformas.