DISPOSITIVO ELECTRÓNICO CALCULADOR DE FUNCIONES TRIGONOMÉTRICAS Y
USOS DEL MISMO
OBJETO DE LA INVENCIÓN
La presente invención, según lo expresa el enunciado de esta memoria descriptiva, se refiere a un método y dispositivo electrónico digital para cálculo de funciones trigonométricas y tratamiento digital de señales e imágenes. Más concretamente, el objeto de la invención es un dispositivo, basado en un circuito electrónico digital, que permite calcular el seno y el coseno. Al contrario de los desarrollos conocidos, el objeto de la invención no almacena en tablas valores de cosenos ni los calcula de forma intermedia. En lugar de ello almacena y/o calcula el complemento de cosenos, entendiendo como el complemento del coseno de un ángulo el resultado de restar a la unidad el coseno de dicho ángulo. Esta novedad permite reducir los recursos requeridos y aumentar la velocidad de operación.
Esta invención tiene su aplicación dentro de la industria dedicada a la fabricación de dispositivos electrónicos y/o informáticos que requieran el cálculo de funciones trigonométricas, incluyendo de forma no exhaustiva a aquellos dedicados al tratamiento digital de señales e imágenes.
ANTECEDENTES DE LA INVENCIÓN
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 portátiles alimentados por baterías de cara a aumentar su autonomía. En los sistemas dedicados al tratamiento digital de señales e imágenes resulta esencial el computo de funciones trigonométricas. En particular, muchos de estos sistemas integran dispositivos que calculan senos y/o cosenos de múltiplos de un ángulo onstante $, es decir, calculan sen (n$) y/o cos (n$) , siendo n un número entero que se proporciona como entrada al dispositivo. A continuación, se describen algunas de las aplicaciones de estos dispositivos:
• Calcular la transformada de Fourier. El cómputo de esta transformada emplea una serie de coeficientes complejos denominados factores de pivote (twiddle factors) cuyos valores se obtienen de los correspondientes pares seno/coseno de determinados múltiplos de un mismo ángulo $. Para una transformada de longitud L dicho ángulo es $ = - 2 n/L. Expresado formalmente, los factores de pivote son las potencias del número complejo e (-2n/L) i. Así, el factor de pivote de índice n será (e (-2n/L^n _ en (-2n/L) i _ sen[n (-2 n / L) ]i + cos[n (_-2n/L) ], es decir, el par seno/coseno de n<p siendo $ = - 2 n/L.
• Implementar sistemas digitales cuya función sea proporcionar el seno y/o coseno de un ángulo expresado en una determinada unidad. Para ilustrarlo, supongamos uno de estos sistemas cuya entrada denominaremos I. Es evidente que I tiene un número finito de bits, por lo que el conjunto de ángulos que puede representar es también finito. Sea C el conjunto de los valores absolutos de los ángulos representables distintos de cero y sea $ el elemento más pequeño de C, todos los ángulos representables son múltiplos positivos o negativos de $, independientemente de si la entrada del dispositivo se representa en punto fijo, punto flotante o alguna notación entera. Por tanto, la funcionalidad del sistema equivale a proporcionar el seno y/o coseno de siendo n un entero.
En adelante consideraremos que el entero n se representa en notación base 2 sin signo. No obstante, dadas las propiedades de periodicidad y simetría de las funciones seno y coseno es irrelevante si la notación empleada permite valores de n positivos y negativos. Para ilustrarlo con un ejemplo, veamos la funcionalidad del circuito descrito por F. de Dinechin en su artículo "Fixed-Point Trigonometric Functions on FPGAs" de la publicación ACM SIGARCH Computer Architecture News Vol. 41, No. 5 de diciembre de 2013. Dicho circuito calcula el seno y el coseno de nx siendo x un número en el intervalo [-1, 1) representado en complemento a 2. Si llamamos I a la entrada del circuito, w al número de bits de I y S al valor representado por I en complemento a 2 tenemos que x = S/2W~1 ^ nx = Sn/2W~1. Por tanto, el circuito calcula el seno y el coseno de SQ siendo $ = n/2w~1. Si n es el valor representado por I en notación base 2 sin signo, es fácil ver que el seno/coseno de SQ coincide con el de n<p, por lo que la funcionalidad de este circuito equivale a calcular el seno y el coseno de n<p. Esto se ilustra a continuación para w = 3.
Volviendo al ejemplo de cálculo de la transformada de Fourier, dado que el cálculo de funciones trigonométricas resulta costoso en tiempo, en implementaciones hardware de la transformada donde la velocidad es crítica los factores de pivote 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 tal y como señala O. Gustafsson en su trabajo "Analysis of Twiddle Factor Memor y Complexity of Radix-2i Pipelined FFTs" (Conference Record of the Forty-Third Asilomar Conference on Signals, Systems and Computers, 2009, páginas 217-220) . Por ello se han propuesto varias formas de reducir el número de posiciones requeridas cuando la longitud de la transformada es potencia de 2:
• En 1976, D. Cohen mostró que sólo era necesario un número de posiciones igual a la mitad del número de muestras en su artículo "Simplified control of FFT hardware" de la revista IEEE Trans. Acoust. Speech Signal Process (páginas 577-579) .
• Entre 1999 y 2000, 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 complementar los valores almacenados. Véase su artículo "Efficient FFT implementation using digit-serial rithmetic" del IEEE Workshop on Signal Processing Systems de 1999 (páginas 645-653) así como "Hardware efficient control of memor y addressing for high performance FFT processors" de la revista IEEE Trans. Signal Process (páginas 917-921) del 2000.
• En 2002 M. Hasan y T. Arslan redujeron el número de posiciones a aproximadamente 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. Esto se hace patente en su artículo "Scheme for reducing size of coefficient memor y in FFT processor" del ejemplar del 14 de febrero de la revista Electronics Letters (páginas 907-911) .
• En 2006 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 1/V2. Esto permite evitar los problemas derivados de implementar una memoria semiconductora cuyo tamaño no es una potencia de 2. Su esquema es presentado en su artículo "Scheme for Reducing the Storage Requirements of FFT Twiddle Factors on FPGAs" publicado en 2007 en la revista Journal of VLSI Signal Processing (páginas 183 187) .
Estas optimizaciones se basan en propiedades de simetría y periodicidad de las funciones seno y coseno que también son aprovechadas por F. de Dinechin para simplificar su circuito de cálculo de seno y coseno de nx en una optimización que denomina reducción de argumentos. Desgraciadamente, aun aplicando todas estas mejoras la implementación de la transformada sigue requiriendo 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 o DVB-T2 (con longitudes del orden de 213 y 215 respectivamente) o muy larga como es el caso de las aplicaciones basadas en conteo de fotones o en el uso de radiotelescopios (con longitudes del orden de 227 y 230 respectivamente) . Esto se solucionó en la patente P201600865 presentada en octubre de 2016. La patente requiere memorias cuyo número total de posiciones crece de forma logarítmica con el número de muestras en lugar de crecer de forma lineal. La patente empleaba un dispositivo que calcula el complejo en , es decir, el seno y el coseno de n<p siendo n un número codificado en base 2 que se suministra como entrada y $ un ángulo constante que puede elegirse de forma arbitraria dependiendo de la aplicación. El dispositivo comprendía los siguientes componentes:
• memorias semiconductoras (normalmente de tipo ROM)
• multiplicadores complejos
Para describir el dispositivo de la patente P201600865, en adelante usaremos la siguiente notación:
w: número de bits de entrada del dispositivo
I = IW- 1IW- 2.../i/0: entrada del dispositivo
n = Xr=_o1^t2t: valor representado por la entrada
m: número de memorias empleadas
M0, M1, ^, M m_1: las m memorias empleadas
Mk[d]: contenido de la posición de la memoria Mk cuya dirección es d
L (k) : número de líneas de dirección de la memoria Mk
A (_k) = A (k) l k^-) _1...A (k) 0: líneas de dirección de la memoria Mk
nk = Y, LSo ~1A (k) t2t : dirección representada por A (k)
las memorias de índice inferior a k
<pk: ángulo definido por (2Si (A>) $
Las memorias se eligen de forma que el número total de líneas de dirección coincide con el número de bits de entrada del dispositivo, de modo que
m - 1
w = SL (m) = y L{k)
El valor precalculado que contienen las posiciones de memoria se define de la forma siguiente:
Mk[d] = ed$kl = sen (d (pk) i + cos (d$k)
Una memoria de acceso directo pone en su salida el contenido de la posición cuya dirección coincida con el número indicado por sus líneas de dirección. Por lo tanto, cada memoria Mk pondrá en su salida el seno y el coseno del ángulo nk<pk. Por otro lado, las líneas de dirección de cada memoria Mk se conectan a las líneas de entrada del dispositivo que van de
a ISL (k+i) -i, es decir, cada línea de dirección A (k) t está conectada a la línea de entrada It+sL (k) de modo que
Debido a esto, el valor n representado por la entrada podemos escribirlo de la forma siguiente:
de modo que el múltiplo del ángulo cuyo seno y coseno se desea calcular puede escribirse así:
Así que el ángulo es la suma de los subángulos nkQk. Como los senos y cosenos de estos subángulos se encuentran a las salidas de las memorias, el seno y el coseno de
puede obtenerse a partir de los mismos aplicando las siguientes fórmulas trigonométricas:
Una forma alternativa de decirlo es que la salida de cada memoria Mk proporciona el complejo 
y que el valor de en puede calcularse mediante el producto
En efecto, el cálculo del producto de dos complejos de módulo unidad
equivale al cálculo del seno y el coseno de la suma de dos ángulos a partir de los senos y cosenos de dichos ángulos e implica cuatro productos simples, una suma y una resta. Teniendo esto en cuenta, el grafo del dispositivo descrito en la patente tiene forma de árbol binario dirigido con m hojas en el que cada nodo intermedio tiene exactamente dos hijos. Cada nodo se corresponde con un componente que tiene como salida un complejo de módulo unidad. Las hojas se corresponden con las m memorias y proporcionan los complejos enk^ki. El resto de los nodos se corresponden con multiplicadores complejos que calculan el producto de las salidas de los componentes correspondientes a sus nodos hijos. La salida del dispositivo corresponde a la del nodo raíz. En adelante denominaremos H a la altura de dicho árbol. A continuación, se omentan recomendaciones que, aunque no son necesarias para que el dispositivo funcione, mejoran la eficiencia del diseño:
• Para reducir la latencia del dispositivo conviene minimizar la altura del árbo1H. Esto se consigue usando un árbol binario completo o semicompleto. Este tipo de árboles se caracteriza porque el nivel de cualquier par de hojas difiere en no más de la unidad.
• El número total de posiciones de memoria se minimiza cuando el número de líneas de dirección de cada par de memorias difiere como mucho en la unidad. Para conseguir esto, sea q el cociente de dividir el número de líneas de entrada w entre m y sea r el resto de dicha división, de entre las m memorias, r deberán tener q + 1 líneas de dirección y las demás deberán tener q líneas de dirección.
• Si se sigue la recomendación anterior, el número total de posiciones de memoria disminuye a medida que aumenta el número de memorias m . Para una altura de árbol fija H, el valor máximo de m es 2H, por lo que el número total de posiciones de memoria se minimiza para dicho valor de m .
Una aplicación obvia de este dispositivo es el cálculo de los factores de pivote de la transformada de Fourier. Para ello bastaría tomar $ = 2n/L, siendo L la longitud de la transformada. El número de bits de la entrada w sería la parte entera por exceso de log2 ( i) de modo que w < 21ºg2 (L) . Si se toma como altura del árbol H la parte entera por defecto de log2 (w) se tendrían no más de w memorias de no más de dos líneas de dirección cada una, con lo que el número de posiciones de memoria totales estará acotado superiormente por 22w < Qlog2 (L) . Esta cota crece de forma logarítmica con L. Aunque esto por si solo permite ahorrar gran cantidad de recursos, si L es potencia de 2 se puede emplear un circuito de cálculo de factores de pivote aún más optimizado. El circuito optimizado para L = 2? se muestra en la figura 1. Su entrada se ha denominado B = Bf _1Bf _2...B1B0. Comprende los siguientes componentes:
• un dispositivo como el descrito anteriormente para calcular el seno y el coseno de múltiplos de 2n/L (1)
• cinco multiplexores 2:1 (2)
• un sumador (3)
• un conjunto de puertas lógicas (4)
Este circuito emplea un esquema similar al presentado por T. Sansaloni de forma que los casos en los que el múltiplo de - 2 n/L corresponde a los ángulos n ¡4, 3^/4, 5^/4 y 7^/4 se detectan con una simple puerta lógica (4a) 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 y el coseno es 1/V2 gracias a un par de multiplexores (2b) . A diferencia del esquema de T. Sansaloni, este circuito no usa una ROM para obtener los senos y cosenos de los múltiplos de $ = -2 n /L en el intervalo {-n /4, 0]. En lugar de eso se emplea un dispositivo como el descrito anteriormente para calcular los pares seno/coseno de los múltiplos de $ = 2n/L en el intervalo [0, n ¡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, n ¡4) , los multiplicadores complejos pueden implementarse usando multiplicadores de magnitud sin signo. Cuando Bf _3 = 0 la entrada al dispositivo que devuelve los senos y cosenos se hace igual a la subcadena Bf _ABf _s ...B0. En caso contrario se hace igual al complemento a dos de dicha subcadena siguiendo el esquema de M. Hasan. Para ello se emplean el multiplexor (2a) y el sumador (3) . En la última etapa una puerta lógica (4b) calcula la operación or exclusiva de Bf _3 y Bf _2. Si el resultado vale 0, un par de multiplexores (2c) harán la magnitud de la parte imaginaria y de la parte real igual a las del seno y el coseno calculadas por el dispositivo 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 (4c) en función de Bf _2 y Bf _t .
En el dispositivo descrito en la patente P201600865, las memorias de menor índice codifican los pares seno/coseno de ángulos muy pequeños. Esto implica que sus senos serán muy próximos a cero y sus cosenos muy próximos a uno, lo que permite llevar a cabo ciertas optimizaciones. Para ilustrarlo, veamos cómo podría aplicarse la patente P201600865 en el cálculo de los factores de pivote de una transformada de longitud L = 211. En este ejemplo las componentes seno y coseno de cada coeficiente se proporcionan en notación de punto fijo con 8 bits de parte fraccionaria sin bit para la parte entera, por lo que el valor uno se aproxima por 1 - 2_8. Se usará el circuito optimizado de la figura 1 que incluirá un dispositivo de 1.- 3 = 8 líneas de entrada para calcular los pares seno/coseno de los múltiplos de $ = 27T/211 = n /210 en el intervalo [0, n ¡4) . Si el dispositivo está estructurado en forma de árbol de altura unidad tendrá la apariencia que se muestra en la figura 2. Nótese que, para compensar los errores de edondeo, las memorias (5) deben almacenar los valores con una precisión de 17 bits. La memoria M0 codificará los senos y cosenos de los ángulos múltiplos de $0 = 20$ = n /2w, mientras que la memoria M1 codificará los senos y cosenos de los ángulos múltiplos de 0 ! = 24$ = n /26. Los ángulos correspondientes a la memoria M0 son mucho más pequeños que los correspondientes a la memoria M1, y se encuentran en el intervalo [0, 15rc/210]. Dado que en [0, n ¡4) el seno es creciente, el seno más grande codificado en M0 es el de !Sn/210, la representación de ese seno tiene los cuatro bits más significativos a cero. Esto implica que todos los senos de la memoria M0 tienen dichos bits a cero, por lo que no es necesario almacenarlos. Por otro lado, dado que el coseno es decreciente en [0, n ¡4) , el coseno más pequeño codificado en M0 es el de !Sn/210. La representación de este coseno tiene los nueve bits más significativos a uno, lo que implica que todos los cosenos de la memoria M0 tienen dichos bits a uno y no es necesario almacenarlos. Las mismas observaciones podrían hacerse con la memoria M1 pero, al ser los ángulos correspondientes a ésta más grandes, en M1 solo es posible ahorrar un bit por pivote. Dicho bit es el más significativo de los cosenos ya que vale 1 en todos los cosenos codificados en M1. Nótese que los ceros comunes en los bits más significativos de los senos permiten reducir el tamaño de la circuitería aritmética. En este caso concreto, en lugar de cuatro multiplicadores de 17 x 17 bits han sido necesarios dos de 17 x 17 (6b) y dos de 13 x 17 (6a) . Una observación importante es que los unos comunes en los bits más significativos de los cosenos no permiten una optimización semejante en la circuitería aritmética. En las secciones siguientes se describe cómo la invención propuesta resuelve esta limitación.
DESCRIPCIÓN DE LA INVENCIÓN
El dispositivo objeto de la invención calcula funciones trigonométricas de n<p, siendo n un número que se suministra en base dos como entrada y $ un ángulo constante que puede elegirse de forma arbitraria dependiendo de la aplicación. En particular, las funciones trigonométricas que calcula el dispositivo son sen (n$) y com (n$) , siendo esta última función el complemento del coseno definido por com (x) = 1 - cos (_x) . El dispositivo comprende principalmente los siguientes componentes:
• De forma opcional, un conjunto de registros que almacenan los valores calculados de forma intermedia. Éstos solamente son necesarios si se desea realizar una implementación en pipeline o secuencial.
• Unos dispositivos que denominaremos sumadores trigonométricos y que representaremos con la letra T. La funcionalidad de un sumador trigonométrico consiste en calcular el seno y el complemento del coseno de la suma de dos ángulos a partir del seno y el complemento del coseno de dichos ángulos. Para implementarlo, partiendo de las siguientes fórmulas trigonométricas
sen (A + B) = sen (A) cos (B) + cos (A) sen (B)
cos{A + B) = cos (A) cos (B) sen (A) sen (B)
obtenemos las siguientes
sen (A + B) = sen (A) + sen (B) [sen (A) com (B) + com (A) sen (B) ] com{A + B) = com (A) + com (B) + [sen (_A) sen (B) com{A) com (B) ] Por tanto, un sumador trigonométrico puede construirse a partir de multiplicadores (6) , sumadores (3) y restadores (7) tal y como se muestra en la figura 3. Aunque no se muestra en dicha figura, tal y como se ha comentado, entre los distintos circuitos aritméticos pueden situarse registros si se desea una implementación en pipeline o secuencial.
• Un conjunto de m dispositivos con la funcionalidad de tablas de consulta (lookup tables) que denominaremos tablas trigonométricas y que representaremos por M0, Mt, ..., Mm_1.
Para describir la estructura del dispositivo de manera similar a la empleada en la sección de antecedentes con la patente P201600865, en adelante usaremos la siguiente notación:
0: ángulo constante elegido
w: número de bits de entrada del dispositivo
I = Iw- 1Iw- 2... l t l0: entrada del dispositivo
n = Xt'=_o1^t2t: valor representado por la entrada en base 2
m: número de tablas trigonométricas empleadas
M0, M1, ..., Mm_1: las m tablas trigonométricas empleadas
L (k) : número de líneas de entrada de la tabla trigonométrica Mk
A (_k) = 4 (k ) (k) _! ...A (k) 0: líneas de entrada de la tabla trigonométrica Mk
nk (k) t2t : valor representado por la entrada A{k) en base 2
las tablas trigonométricas de índice inferior a k
• ángulo definido por (2Si (k) ) 0
La funcionalidad de cada tabla trigonométrica Mk consiste en proporcionar el seno y el complemento del coseno de nk<pk. De forma no exhaustiva y no exclusiva, se proponen algunas formas de implementarlas:
• Mk puede ser una memoria de acceso directo de solo lectura en la que el contenido de cada posición de memoria de dirección d es el seno y el complemento del coseno de d<pk.
• Mk puede ser una memoria de acceso directo de lectura/escritura que se inicializa antes de que el dispositivo se ponga en funcionamiento de forma que cada posición de memoria de dirección d se escribe con el seno y el complemento del coseno de d<pk.
• Mk puede ser un circuito que proporcione el seno y el complemento del coseno de nk<pk realizando algún tipo de cálculo, como por ejemplo el cómputo de un polinomio de interpolación.
• Mk puede ser una combinación de circuitos de memoria y de cálculo que proporcionen el seno y el complemento del coseno de nk<pk. Por ejemplo, puede incluir un circuito que compute un polinomio de interpolación conectada a una memoria que le proporcione los coeficientes de dicho polinomio dependiendo del intervalo en el que se encuentre la entrada.
Las tablas trigonométricas se eligen de forma que su número total de líneas de entrada sea igual al número de líneas de entrada del dispositivo, de modo que
Las líneas de entrada de cada tabla trigonométrica Mk se conectan a las líneas de entrada del dispositivo que van de ISL^ a ISL (k+i) - i, es decir, cada línea A (_k) t está conectada a la línea h+sL (k) de modo que
A ( m 1 ) ¡ w - l h > L ( m - l ) + l h > L ( m - l )
Debido a esto, el valor n representado por la entrada I podemos escribirlo de la forma siguiente:
de modo que el múltiplo del ángulo cuyo seno y complemento del coseno se desea calcular puede escribirse así:
Así que el ángulo es la suma de los subángulos nkQk. Como los senos y complementos de los cosenos de estos subángulos se encuentran a las salidas de las tablas trigonométricas, el seno y el complemento del coseno de n<p puede obtenerse a partir de los mismos usando sumadores trigonométricos. Teniendo esto en cuenta, el grafo del dispositivo tiene forma de árbol binario dirigido con m hojas en el que cada nodo intermedio tiene exactamente dos hijos. Cada nodo se corresponde con un componente que proporciona en su salida el seno y el complemento del coseno de un ángulo. Las hojas se corresponden con las m tablas trigonométricas y proporcionan los senos y complementos de cosenos de los ángulos n0$0, n1^ 1...... El resto de los nodos se corresponden con sumadores trigonométricos que
reciben como entrada las salidas de sus nodos hijos. La salida del dispositivo corresponde a la del nodo raíz. La conexión entre las entradas de un sumador trigonométrico y las salidas correspondientes a sus nodos hijos puede ser directa o, si se desea una implementación en pipeline, a través de registros intermedios. Si se usan registros para almacenar los valores intermedios puede realizarse una implementación secuencial en la que el número de sumadores trigonométricos sea inferior al número de nodos intermedios del grafo del circuito, reutilizándose al menos uno de estos sumadores trigonométricos para realizar el cómputo correspondiente a dos o más nodos intermedios. En adelante denominaremos H a la altura del árbol. A continuación, se comentan recomendaciones que, aunque no son necesarias para que el dispositivo funcione, mejoran la eficiencia del diseño:
• Para reducir la latencia del dispositivo conviene minimizar la altura del árbol H. Esto se consigue usando un árbol binario completo o semicompleto. Este tipo de árboles se caracteriza porque el nivel de cualquier par de hojas difiere en no más de la unidad.
• Si se usan memorias de acceso directo para implementar las tablas trigonométricas, el número total de posiciones de memoria se minimiza si el número de líneas de dirección de cada par de memorias difiere como mucho en la unidad. Para conseguir esto, sea w el número total de líneas de dirección, m el número de memorias, q el cociente de dividir w entre m y sea r el resto de dicha división, de entre las m memorias, r deberán tener q + 1 líneas de dirección y las demás deberán tener q líneas de dirección.
• Si se sigue la recomendación anterior, el tamaño total de las memorias empleadas para implementar las tablas trigonométricas disminuye a medida que aumenta el número de las mismas. Para un árbol de altura H el número máximo de tablas trigonométricas es m = 2H.
Una utilidad obvia de este dispositivo es el cálculo del seno y el coseno de n<p, por lo que abarca todas las aplicaciones de la patente P201600865. A modo de ejemplo, la figura 4 muestra cómo usar el dispositivo para el cálculo del seno y el coseno de n<p usando 11 bits para codificar n (es decir, w = 11) . El dispositivo tiene estructura de árbol binario de altura 2 (H = 2) . Se ha maximizado el número de tablas trigonométricas haciendo m = 2H = 4. Las cuatro tablas trigonométricas, denominadas M0, Mt, M2 y M3 se han implementado usando memorias ROM (8) . Siguiendo la recomendación para minimizar el número total de posiciones de memoria, a M3 se la ha dotado de dos líneas de dirección (q = [w/m\ = 2) y las tres memorias restantes (r = w - mq = 3) tienen una línea de dirección más cada una, de modo que L (3) = 2 y L (2) = L ( l) = (0) = 3. Por tanto SL (0) = 0, 0 O = 2 >, SL (1) = 3, $ t = 230, SL (2) = 6, 02 = 260, SL (_3) = 9 y 03 = 290. Cada línea de entrada t de cada tabla trigonométrica Mk está conectada a la línea It+sL (k) , así que las entradas de M0, Mt, M2 y M3 se encuentran conectadas respectivamente a I2I1I0, /5/4/3, h h h e 710/g. Cada Mk contiene los senos y los complementos de los cosenos de los múltiplos de 0k, por lo que en su salida aparecen el seno y el complemento del coseno de nk<pk. El dispositivo contiene tres sumadores trigonométricos (9) .
Los dos directamente conectados a las tablas trigonométricas calculan el seno y el complemento del coseno del ángulo no0 o + n1$1 y el ángulo n202 + n 303 respectivamente. El correspondiente a la raíz calcula el seno y el complemento del coseno de n0 = no0 o + n1^ 1 + n2<p2 + n3<p3. A la salida del dispositivo se conecta un circuito trivial (10) que resta el complemento del coseno de n0 a la unidad para obtener el coseno de n0.
Al igual que en la patente P201600865, si en una aplicación concreta el múltiplo del ángulo se encuentra siempre entre 0 y n¡2 radianes entonces no se requieren circuitos aritméticos con signo. Además, el dispositivo propuesto tiene como ventaja respecto a dicha patente que los multiplicadores empleados no reciben como entrada cosenos de ángulos sino el complemento de los mismos. Esto permite reducir el tamaño de los multiplicadores. Para ilustrarlo volvamos al ejemplo de aplicación de la patente P201600865 presentado en la sección de antecedentes de la invención. En el ejemplo, para el cálculo de los factores de pivote de una transformada de longitud 211 se usaba un dispositivo con estructura de árbol de altura H = 1 que proporcionaba los pares seno/coseno de los múltiplos de $ = 27T/211 = n /210 en el intervalo [0, n ¡4) . Los cuatro bits más significativos de la representación de los senos codificados en la memoria M0 eran igual a cero, lo que permitía reducir el tamaño de dos de los multiplicadores a 13 x 17, pero los unos comunes en la representación de los cosenos no permitían una optimización semejante de modo que los otros dos multiplicadores debían seguir siendo de 17 x 17. En cambio, si se usase la invención propuesta ahora, las memorias no codificarían los cosenos sino el complemento de los mismos. Como vimos, los ángulos correspondientes a la memoria M0 se encuentran en el intervalo [0, 15n:/210]. Al ser el complemento del coseno creciente en [0, n ¡4) , el mayor de los codificados en M0 sería el de 15rc/210. Como la representación de dicho valor tiene los 9 bits más significativos a cero, todos los complementos de cosenos codificados en M0 tendrían dichos bits a cero. Lo mismo ocurriría con el bit más significativo de la representación del complemento de los cosenos de la memoria M1. Por tanto, con la invención propuesta sólo sería necesario un multiplicador de 13 x 17, uno de 13 x 16, uno de 8 x l 7 y otro de 8 x 16. Si se desea implementar la transformada de una muestra más larga la mejora será aún mayor ya que los ángulos correspondientes a las memorias de menor índice serán aún más pequeños.
DESCRIPCIÓN DE LOS DIBUJOS
Para complementar la descripción que se está realizando y con objeto de ayudar a una mejor comprensión de las características de la invención, de acuerdo con un ejemplo preferente de realización práctica de la misma, se acompaña como parte integrante de dicha descripción, un juego de dibujos en donde, con carácter ilustrativo y no limitativo, se ha representado lo siguiente:
Figura 1.- Muestra un diagrama donde se aprecia un circuito que calcula los factores de pivote de la transformada de Fourier para muestras de longitud L = 2 siguiendo el esquema de T. Sansaloni. El índice del coeficiente a calcular se codifica en la entrada ...B0. El circuito comprende un dispositivo que calcula el seno y coseno de un múltiplo de $ = 2n/2 f en el intervalo [0, n ¡4) (1) . Un multiplexor (2a) y un sumador (3) se emplean para que el dispositivo que devuelve los senos y cosenos reciba como entrada Bf_ABf _s ...B0 cuando B¡_3 = 0, o su complemento a dos cuando B¡_3 = 1. Una puerta lógica (4a) comprueba si el bit Bf _2 = 0 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 1/V2 gracias a un par de multiplexores (2b) . En la última etapa otra puerta lógica (4b) calcula la operación or exclusiva de B¡_3 y Bf _2. Si la salida de dicha puerta es 0, un par de multiplexores (2c) harán la magnitud de la parte imaginaria y de la parte real igual a las del seno y el coseno calculadas por el subcircuito (1) 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 (4c) en función de Bf _2 y Bf_1.
Figura 2.- Muestra un diagrama donde se aprecia un ejemplo de uso del dispositivo de la patente P201600865 que calcula los senos y los cosenos de los múltiplos de $ = 27T/211 = n /2w en el intervalo [0, n ¡4) . La entrada del circuito se denomina I y tiene 1.- 3 = 8 bits. El circuito pone en su salida el seno y el coseno de n<p siendo n el número representado por I en base 2. En este ejemplo las salidas se proporcionan en notación de punto fijo con 8 bits de parte fraccionaria sin bit para la parte entera, por lo que el valor 1 se aproxima por 1 - 2 -8. El dispositivo de este ejemplo está estructurado en forma de árbol de altura unidad (H = 1) y comprende dos memorias pequeñas (m = 2H = 2) , denominadas M0 y M1 (5) . La memoria M0 codifica los senos y cosenos de los ángulos múltiplos de $0 = 2°$ = n/2w, mientras que la memoria M1 codifica los senos y cosenos de los ángulos múltiplos de 0 ! = 24$ = n /26. Nótese que, para compensar los errores de redondeo, las memorias deben almacenar los valores con una precisión de 17 bits. Los ángulos correspondientes a la memoria M0 son mucho más pequeños que los correspondientes a la memoria M1, y se encuentran en el intervalo [0, 15n:/210] . Dado que en [0, n ¡4) el seno es creciente, el seno más grande codificado en M0 es el de 15n:/210, y la representación de ese seno tiene los uatro bits más significativos a cero. Esto implica que todas las representaciones de los senos de la memoria M0 tienen dichos bits a cero, por lo que no es necesario almacenar esos bits. Por otro lado, dado que el coseno es decreciente en [0, n ¡4) , el coseno más pequeño codificado en M0 es el de !Sn/210. La representación de este coseno tiene los nueve bits más significativos a uno, lo que implica que todas las representaciones de los cosenos de la memoria M0 tienen dichos bits a uno y no es necesario almacenar esos bits. Las mismas observaciones podrían hacerse con la memoria M1 pero, al ser los ángulos correspondientes a ésta más grandes, en M1 solo es posible ahorrar un bit por pivote. Dicho bit es el más significativo de los cosenos ya que vale 1 en todos los cosenos codificados en M1. Los cuatro bits menos significativos de I se conectan a las líneas de dirección de M0 y los restantes a las líneas de dirección de M1 de modo que n = n0 + n124 siendo n0 y n1 el valor representado por las líneas de dirección de M0 y M1 respectivamente, por tanto n<p = n0$ + n124<p = n0$ 0 + n1^ 1. El seno y el coseno de n<p se obtienen a partir de las salidas de las memorias usando cuatro multiplicadores (6) , un sumador (3) y un restador (7) . Como el seno y coseno de todos los ángulos en el intervalo [0, n ¡4) son positivos, estos circuitos aritméticos usan notación sin signo. Los ceros comunes en los bits más significativos de los senos permiten reducir el tamaño de la circuitería aritmética. En este caso concreto, en lugar de cuatro multiplicadores de 17 x 17 bits han sido necesarios dos de 17 x 17 (6b) y dos de 13 x 17 (6a) .
Figura 3.- Muestra un diagrama donde se aprecia un circuito, denominado sumador trigonométrico, que calcula el seno y el complemento del coseno de la suma de dos ángulos denominados A y B a partir de los senos y el complemento de los cosenos de dichos ángulos. El complemento del coseno de un ángulo se define como el resultado de restar a la unidad el coseno de dicho ángulo. El circuito emplea sumadores (3) , restadores (7) y multiplicadores (6) para obtener los resultados aplicando las fórmulas
sen (A + B) = sen (A) + sen (B) [sen (A) com (B) + com (A) sen (B) ]
com{A + B) = com (A) + com (B) + [sen (_A) sen (B) com{A) com (B) ]
En estas fórmulas com denota la función complemento del coseno, es decir, com (i) = 1 -cos (x) .
Figura 4.- Muestra un diagrama donde se aprecia un ejemplo de uso de la invención propuesta para calcular el seno y el coseno de n<p siendo $ un ángulo constante y n el alor representado por la entrada / en base 2. Para ello la invención calcula el seno y el complemento del coseno de n<p, entendiendo el complemento del coseno de un ángulo como el resultado de restar a la unidad el coseno de dicho ángulo. En la figura com denota la función complemento del coseno, es decir, com (i) = 1 - cos (x) . En el ejemplo de esta figura la entrada I es de 11 bits (w = 11) y la invención tiene estructura de árbol binario de altura 2 (H = 2) . Se ha maximizado el número de tablas trigonométricas (m) haciendo m = 2H = 4. Las cuatro tablas trigonométricas, denominadas M0, M1, M2 y M3 se han implementado usando memorias ROM (8) . Siguiendo la recomendación para minimizar el número total de posiciones de memoria, a M3 se le ha dotado de dos líneas de dirección (q = [w/m\ = 2) y las tres memorias restantes (r = w - mq = 3) tienen una línea de dirección más cada una, de modo que L (3) = 2 y L (2) = L ( l) = L (0) = 3. Por tanto SL (0) = 0, 0º = 2O0, SL (1) = 3, 0 ! = 230, SL (2) = 6, 02 = 260, SL (3) = 9 y 03 = 290. Cada memoria Mk contiene los senos y los complementos de los cosenos de los múltiplos de 0k = (2Si (k) ) 0, de modo que en su salida aparecen el seno y el complemento del coseno de nk<pk, siendo nk el valor de sus líneas de dirección. Cada línea de entrada t de cada tabla trigonométrica Mk está conectada a la línea It+SL (k) , de modo que las entradas de M0, Mt, M2 y M3 se encuentran conectadas respectivamente a /2/1/0, /5/4/3, /8/7/6e/10/g. Por tanto n = n02SL^ 0^ + n12SL^ 1>> + n22SL^2>> + n32SL (3^ ^ n<p = n02SL (°^ <p + n12Si 1^^ 0 + n22Si (2) 0 + n32Si (3) 0 = no0 o + n1^ 1 + n2<p2 + n303. En este ejemplo se usan tres sumadores trigonométricos (9) . Los dos directamente conectados a las tablas trigonométricas calculan el seno y el complemento del coseno del ángulo no0º + n1^ 1 y el ángulo n202 + n303 respectivamente. El correspondiente a la raíz calcula el seno y el complemento del coseno de n0 = no0 o + n1^ 1 + n2<p2 + n303. A la salida de la invención se conecta un circuito trivial (10) que resta el complemento del coseno de n0 a la unidad para obtener el coseno de n0.
REALIZACIÓN PREFERENTE DE LA INVENCIÓN
En una realización preferente del objeto de la invención se implementó sobre una FPGA (Field Programable Gate Array) modelo Virtex 7 XC7VX485T-2FFG1761 del fabricante Xilinx, un circuito que calcula los factores de pivote de la transformada de Fourier para muestras de longitud L = 215 en notación punto fijo de 16 bits para la parte fraccionaria y 0 bits para la parte ntera. La síntesis se ha realizado mediante la herramienta Vivado Design Suite de Xilinx. En dicha síntesis se usaron las unidades DSP integradas en la FPGA para implementar los multiplicadores. Siguiendo el esquema de T. Sansaloni, el circuito usa un dispositivo con una entrada de 1.- 3 = 12 bits que calcula el seno y coseno de los múltiplos de 0 = 2n/2is en el intervalo [0, n ¡4) . Dicho dispositivo se ha implementado usando la invención propuesta para calcular el seno y el complemento del coseno de los múltiplos de 0 = 2n/2is . Este ejemplo de la invención comprende dos tablas trigonométricas que se han implementado usando las LUT de la FPGA. Cada una de las ellas tiene 12/2 = 6 bits de entrada. Un circuito aritmético trivial resta a la unidad el complemento del coseno para obtener el coseno. La implementación requirió 7 unidades de DSP. Para realizar una comparación con el estado de la técnica, se ha implementado un circuito con idéntica funcionalidad pero que, en lugar de usar la invención propuesta, usa el dispositivo descrito en el documento anteriormente comentado P201600865 para calcular el seno y coseno de 0 = 2n/2is en el intervalo [0, n ¡4) . Usando la misma FPGA y la misma herramienta de síntesis que en el caso anterior, el diseño requirió 12 unidades de DSP. Por tanto, la invención propuesta proporciona un ahorro de casi un 42% en dichos recursos.
