Circuito electrónico digital para el cálculo de senos y cosenos de múltiplos de un ángulo
Objeto de la invención
La presente invención tiene por objeto un circuito electrónico digital que calcula los coeficientes de twiddle de la transformada de Fourier empleando un subcircuito que calcula los senos y cosenos de múltiplos enteros de un ángulo concreto que comprende memorias semiconductoras cuyo número total de entradas es del orden del logaritmo de la longitud de la transformada. Esto implica un ahorro considerable en área (componentes) y consumo de memoria en aplicaciones en las que la secuencia de datos es larga.
Tiene su aplicación en el área de la tecnología electrónica, concretamente, en el tratamiento digital de señales.
Estado de la técnica
Entre los principales objetivos de los diseñadores de circuitos electrónicos digitales se encuentran la reducción del área ocupada por los mismos así como la reducción de su consumo de energía y el aumento de su velocidad. La reducción de área permite reducir los costes de producción de los chips y generalmente acarrea una reducción de consumo. Esto último es especialmente importante en equipos portables alimentados por baterías de cara a aumentar su autonomía. Muchos de estos equipos Integran circuitos que calculan senos y/o cosenos de múltiplos de un ángulo. Un ejemplo notable son los circuitos que implementan la transformada rápida de Fourier. En ellos se requieren una serie de coeficientes complejos (denominados de twiddle o de pivote) cuyos valores se obtienen de los correspondientes pares seno/coseno de determinados múltiplos de un mismo ángulo. Dado que el cálculo de funciones trigonométricas resulta costoso en tiempo, en implementaciones hardware de la transformada donde la velocidad es critica estos valores se encuentran precalculados en memorias de acceso directo (normalmente de tipo ROM). Estas memorias pueden tener gran número de posiciones pues se requieren tantos coeficientes como muestras tenga la serie. Esto supone una grave penalización en área y consumo en el hardware
de cálculo de transformadas de secuencias largas siendo el tamaño de las memorias muy grande en comparación con el resto de componentes (1).
Por ello se han propuesto varias formas de reducir el número de posiciones requeridas:
- D. Cohén mostró que era suficiente un número de posiciones igual a la mitad del número de muestras (2).
- Y. Ma, L. Wanhammar, Y. Chang y K. K. Parhi redujeron el número de posiciones a la cuarta parte al almacenar únicamente los coeficientes de ángulos en un intervalo de un cuarto de circunferencia El resto se obtiene de forma fácil y rápida mediante relaciones trigonométricas simples que sólo requieren permutar y cambiar el signo de los componentes de los valores almacenados (3) y (4).
- M. Hasan y T. Arslan redujeron el número de posiciones a poco más de un octavo del número de muestras almacenando únicamente los coeficientes en un intervalo de un octavo de circunferencia. De nuevo los coeficientes restantes pueden calcularse rápidamente a partir de ellos aplicando relaciones trigonométricas (5).
- T Sansaloni, A. Pérez-Pascual, V. Torres y J. Valls redujeron el número de posiciones a exactamente un octavo del número de muestras usando hardware específico para detectar y tratar los coeficientes cuyas parte real/imaginaria tiene una
magnitud igual a I ^. Esto permite evitar los problemas derivados de ¡mplementar una memoria semiconductora cuyo tamaño no es una potencia de 2 (6).
Sin embargo, todas estas mejoras requieren una memoria de un número de posiciones que crece linealmente con el número de muestras. Esto supone un inconveniente en aplicaciones en las que la secuencia de datos es larga tales como PLC (7) o DVB-T2
(8) (con longitudes del orden de 2A13 y 2A15 respectivamente) o muy larga como es el caso de las aplicaciones basadas en conteo de fotones (9) o en el uso de radiotelescopios (10) (con longitudes del orden de 2A27 y 2A30 respectivamente).
Referencias
(1) O. Gustafsson, "Analysis of Twiddle Factor Memor y Complexity of Radix-21 Pipelined FFTs", Conference Record of the Forty-Third Asilomar Conference on Signáis, Systems and Computers, 2009, páginas 217-220
(2) "Simplified control of FFT hardware", IEEE Trans. Acoust. Speech Signal Process, páginas 577-579, 1976
(3) "Efficient FFT implementation using digit-serial arithmetic", IEEE Workshop on Signal Processing Systems, páginas 645-653, 1999
(4) "Hardware efficient control of memor y addressing for high performance FFT processors" IEEE Trans. Signal Process, páginas 917-921, 2000
(5) "Scheme for reducing size of coefficient memor y in FFT processor", Electronics Letters, páginas 907-911, 14 Febrero 2002
(6) "Scheme for Reducing the Storage Requirements of FFT Twiddle Factors on FPGAs", Journal of VLSI Signal Processing, páginas 183-187, 2006
(7) IEEE 1901, "IEEE Standard for Broadband over Power Line Networks: Médium Access Control and Physical Layer Specifications", IEEE Communications Society, 2010.
(8) "Digital Video Broadcasting (DVB) ; Frame structure channel coding and modulation for a second generation digital terrestrial televisión broadcasting system (DVB-T2) ", Ref. REN/JTC-DVB-308, ETSI EN 302 755 v1.3.1, 2012.
(9) Stanton, R. H., "PhotonCounting - One More Time", The Society for Astronómica! Sciences, 31st Annual Symposium on Telescope Science, May 22-24, 2012, Big Bear Lake, CA. Society for Astronomical Sciences, 2012, pp.177-184.
(10) Nakahara, H., Nakanishi, H., Sasao, T., "On a Wideband Fast Fourier Trasform for a Radio Telescope", ACM SIGARCH Computer Architecture News, Vol. 40, No. 5, pp. 46-51, December 2012.
Descripción de las figuras
Figura 1. Se ilustra un subcircuito que calcula los senos y cosenos de los múltiplos de 0=2n/L=77/213 en el intervalo [Q, ttI4) , es decir, las potencias del complejo e®'. El subcircuito está estructurado en dos fases y comprende cuatro memorias pequeñas (F=2, D=2f=4) , denominadas M0, Mu M2 y M? (1). Cada memoria de índice K mantiene los coeficientes (pares seno/coseno) de los ángulos múltiplos de 2k0 , M3 posee sólo dos líneas de dirección (q = 2) y las otras tres memorias (r = 3) tienen una línea más. En total estas ROM suman solamente 28 posiciones de memoria. Sea d la entrada del subcircuito (de 11 bits) , este calcula el complejo en01 siendo n el número codificado en d. Los bits de d se reparten entre las líneas de dirección de las memorias de forma que cada una de ellas proporciona el par seno/coseno de un subángulo ak siendo n0=ao+cti +a2+a3.El complejo en0` se obtiene multiplicando las salidas de las memorias usando dos niveles de multiplicadores complejos (2) de forma que el retraso total del subcircuito es de dos multiplicadores complejos.
Figura 2- Se ilustra un circuito que calcula los coeficientes de twiddle de la transformada de Fourier para muestras de longitud L=2f siguiendo el esquema de T.
Sansaloni. En el caso del ejemplo /=14. El índice del coeficiente a calcular se codifica en la entrada B=B,.1Bf.2..B0. El circuito comprende un subcircuito como el ¡lustrado en la figura 2 (3). Un multiplexor (4a) y un sumador (5) se emplean para que el subcircuito que devuelve los senos y cosenos reciba como entrada Bi_4Bf_5..B0 cuando S, _3=0, o su complemento a dos cuando Bf_3= 1 Una puerta lógica (6a) comprueba si el bit vale 1 y el resto de bits menos significativos de B valen 0, en cuyo caso la magnitud
devuelta para el seno y el coseno es gracias a un par de multiplexores (4b). En la última etapa otra puerta lógica (6b) calcula la operación lógica EXOR de B, _3 y Bf.2. Si el valor de la operación lógica EXOR es 0 un par de multiplexores (4c) harán la magnitud de la parte imaginaria y de la parte real igual a la del seno y el coseno calculada por el subcircuito (3) respectivamente En caso contrario las magnitudes imaginaria y real serán las del coseno y el seno respectivamente. El signo de la parte real y la imaginaria se calculan fácilmente con puertas lógicas simples (6c) en función de B, _2 y B,.h
Descripción de la invención
La invención trata de un circuito electrónico digital que calcula los coeficientes de twiddle de la transformada de Fourier. Los coeficientes de twiddle son los pares seno/coseno de los ángulos múltiplos de -2tt/L siendo L la longitud de la secuencia sobre la que se aplica la transformada. Esto es, los coeficientes de twiddle son las potencias del complejo e2ni/L. Para llevarlo a cabo se ha ideado un subcircuito que calcula el complejo en<t>\ es decir, el seno y el coseno de n<t> siendo 0 un ángulo constante y n un número codificado en base 2 que se suministra como entrada. Hay que hacer notar que el subcircuito puede emplearse para cálculo trigonométrico en general y no solo para el cálculo de los coeficientes de twiddle. El subclrcuito consta de los siguientes componentes:
memorias semiconductoras (normalmente de tipo ROM)
multiplicadores complejos
lineas que los interconectan en forma de árbol Sea b la entrada del subcircuito y E el número de bits de b, pueden codificarse N = 2E ángulos distintos. El subcircuito se estructura en un número F de fases siendo F no mayor que el logaritmo en base 2 de E. En total el subcircuito comprende d = 2F memorias de acceso directo que denominaremos M0, Mh , Sea q el cociente
de dividir E entre d y sea r el resto, de entre las d memorias r tendrán q + 1 líneas de dirección. El resto tendrá sólo q líneas de dirección. Sea líneas (Mk) el número de líneas de dirección de cada memoria k, se tiene
j- i
£ líneas (MK) ~ E
k= O
Cada posición de memoria p de la memoria Mm contendrá el seno y el coseno del ángulo
£ Uneas (Mt)
0p 2M
Dicho de otra forma, dicha posición de memoria contendrá el complejo definido por
e A (0p 2
J lineas
¡)
Sea b = bE. 1 bE. 2 b1 b0, la entrada del subcircuito que codifica el número n, para obtener el seno y el coseno de n0, es decir, el complejo en<t\ se divide b en d subcadenasSo, Sf,... Sd.? de longitudes líneas{M0) , líneasiMi) ,.... //neas (/Wd., ). Nótese que
2°+n 2"reas (M0>+n 2llneas^M0^*llneas^M1^+ +n 2lneas^M0^+llneas^M1^+ *nneas (Md-i)
donde nk denota el número representado por la subcadenaS*. Por tanto tenemos que n®=a0+a1+..+ad_1 siendo cada ángulo ak definido por
T
«* (1>nk2'
lineas ^ ^
De modo que el valor buscado puede calcularse mediante el producto
n0i___ o0# a, i aA_.i
e - e e..e
Las lineas de dirección de cada memoria Mm se conectan a la subentrada Sm de forma que su salida proporciona el complejo eAfam/j. El valor e^nOi) es calculado por los multiplicadores a partir de las salidas de las memorias Los multiplicadores se disponen en paralelo de forma que cada fase introduce un retraso igual al de un multiplicador complejo. En el caso de tomar para F el valor de la parte entera por defecto de log2 (E) , como máximo se tendrían E memorias de no más de dos líneas de dirección, con lo que el número de posiciones de memoria totales estará acotado superiormente por 22E=Alog2 (N) Esta cota crece logarítmicamente con el número de ángulos N.
El subcircuito presentado puede emplearse para calcular directamente los coeficientes de twiddle de una transformada de longitud L tomando 0=-2tt/L. El número de bits de la entrada E sería la parte entera por exceso de log2 (L) de modo que E<2log2 (L). Si se toma como número de fases F el valor de la parte entera por defecto de log2 (E) se tendrían no más de E memorias de no más de dos líneas de dirección, con lo que el número de posiciones de memoria totales estará acotado superiormente por
22E<dlog2 (L). Aunque esto por sí solo permite ahorrar gran cantidad de recursos respecto al estado de la técnica, si L es potencia de 2 se puede emplear un circuito aún más optimizado. El circuito optimizado está compuesto por los siguientes elementos:
Un subcircuito como el descrito en el apartado anterior
Cinco multiplexores 2:1
Un sumador
Un conjunto de puertas lógicas
Este circuito emplea un esquema similar al presentado por T. Sansaloni de forma que los casos en los que el múltiplo de 0 corresponde a los ángulos ttIA, 3tt/4, 5tt/4 y 7jt/4 se detectan con una simple puerta lógica y se tratan de forma separada La puerta se limita a comprobar si el bit Bf.3 vale 1 y el resto de bits menos significativos de B valen 0, en cuyo caso la magnitud devuelta para el seno (parte imaginaria) y el coseno (parte
real) es gracias a un par de multiplexores. A diferencia del esquema de T. Sansaloni, este circuito no usa una ROM para obtener los senos y cosenos de los múltiplos de 0=-2tt/L en el intervalo (-rr/4, 0]. En lugar de eso se emplea un subcircuito como el descrito anteriormente para calcular los pares seno/coseno de los múltiplos de 0=2tt/L en el intervalo [0, m/4). Esto hace posible reducir enormemente la memoria necesaria para implementar el sistema. Además, al ser positivos los senos y cosenos de todos los ángulos en el intervalo [0, rr/4). los multiplicadores complejos pueden implementarse usando multiplicadores de magnitud sin signo. Sea la longitud de la transformada L=2! y sea B=BM Bf.2..B0 la entrada del circuito optimizado que codifica el índice del coeficiente de twiddle a calcular, cuando Bf.3=0 la entrada al subclrcuito que devuelve los senos y cosenos se hace igual a la subcadena Bi.4B^5..B0. En caso contrario se hace igual al complemento a dos de dicha subcadena. Para ello se emplean un multiplexor y un sumador. Una puerta lógica comprueba si el bit vale 1 y el resto de bits menos significativos de B valen 0, en cuyo caso la magnitud devuelta
para el seno y el coseno es gracias a un par de multiplexores conectados a la salida del subcircuito. En la última etapa una puerta calcula la operación lógica EXOR de Bf.3 y B, _2. Si vale 0 un par de multiplexores harán la magnitud de la parte imaginaria y de la parte real igual a la del seno y el coseno calculada por el subcircuito respectivamente. En caso contrario las magnitudes imaginaria y real serán las del coseno y el seno respectivamente. El signo de la parte real y la imaginaria se calcula con puertas lógicas simples en función de Bf.2 y 6f.,.
Modo de realización de la invención
A modo de ejemplo se ha realizado sobre FPGA (Field Programable Gate Array) un circuito que calcula los coeficientes de twiddle de la transformada de Fourier para secuencias de longitud L = 214. Esto requiere conocer los senos y cosenos de los 5 múltiplos enteros del ángulo ®=-2tt/L=-tt/2'3. En el esquema presentado por T. Sansaloni se mantendrían almacenados en una memoria ROM los coeficientes correspondientes a los ángulos en el intervalo (-7t/4, 0] (una octava parte de circunferencia, esto es, N = U8 = 211 = 2048). La ROM tendría 11 líneas de dirección (E = 11) y 2048 posiciones de memoria. En lugar de dicha ROM se ha empleado el 10 subcircuito de la figura 1 que calcula los senos (parte imaginaria) y cosenos (parte real) de los múltiplos de ®=2tt/L=tt/2^ en el intervalo [0, rr/4) usando tan solo un total de 28 posiciones de memoria Dicho subcircuito se emplea en el circuito de la figura 2 para el cálculo de los coeficientes de twiddle
