Implementación VLSI del algoritmo CORDIC en modo vectorización utilizando Radix alto
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC
Algoritmo iterativo para la rotación de un vector en un sistema de coordenadas lineales, circulares o hiperbólicas.
Permite realizar transformaciones de coordenadas y el cálculo de una gran variedad de funciones trigonométricas e hiperbólicas, entre otras.
Utilizado en procesado digital de señales y gráficos 3D, álgebra matricial, radar y robótica, entre otras aplicaciones.
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC
Algoritmo iterativo para la rotación de un vector en un sistema de coordenadas lineales, circulares o hiperbólicas.
Permite realizar transformaciones de coordenadas y el cálculo de una gran variedad de funciones trigonométricas e hiperbólicas, entre otras.
Utilizado en procesado digital de señales y gráficos 3D, álgebra matricial, radar y robótica, entre otras aplicaciones.
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC
Algoritmo iterativo para la rotación de un vector en un sistema de coordenadas lineales, circulares o hiperbólicas.
Permite realizar transformaciones de coordenadas y el cálculo de una gran variedad de funciones trigonométricas e hiperbólicas, entre otras.
Utilizado en procesado digital de señales y gráficos 3D, álgebra matricial, radar y robótica, entre otras aplicaciones.
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC
Algoritmo iterativo para la rotación de un vector en un sistema de coordenadas lineales, circulares o hiperbólicas.
Permite realizar transformaciones de coordenadas y el cálculo de una gran variedad de funciones trigonométricas e hiperbólicas, entre otras.
Utilizado en procesado digital de señales y gráficos 3D, álgebra matricial, radar y robótica, entre otras aplicaciones.
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC
Formulación convencional: recurrencia radix 2 (se extrae 1 bit del resultado en cada iteración).
Iteraciones lentas.
Elevada latencia para un tamaño de palabra elevado.
Soluciones:
Uso de sumadores rápidos (CLA) y/o aritmética redundante (carry-save, signed-digit).
Empleo de recurrencias con un radix alto r = 2b (se extraen b bits del resultado en cada iteración).
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC
Formulación convencional: recurrencia radix 2 (se extrae 1 bit del resultado en cada iteración).
Iteraciones lentas.
Elevada latencia para un tamaño de palabra elevado.
Soluciones:
Uso de sumadores rápidos (CLA) y/o aritmética redundante (carry-save, signed-digit).
Empleo de recurrencias con un radix alto r = 2b (se extraen b bits del resultado en cada iteración).
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC
Formulación convencional: recurrencia radix 2 (se extrae 1 bit del resultado en cada iteración).
Iteraciones lentas.
Elevada latencia para un tamaño de palabra elevado.
Soluciones:
Uso de sumadores rápidos (CLA) y/o aritmética redundante (carry-save, signed-digit).
Empleo de recurrencias con un radix alto r = 2b (se extraen b bits del resultado en cada iteración).
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC
Formulación convencional: recurrencia radix 2 (se extrae 1 bit del resultado en cada iteración).
Iteraciones lentas.
Elevada latencia para un tamaño de palabra elevado.
Soluciones:
Uso de sumadores rápidos (CLA) y/o aritmética redundante (carry-save, signed-digit).
Empleo de recurrencias con un radix alto r = 2b (se extraen b bits del resultado en cada iteración).
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC
Formulación convencional: recurrencia radix 2 (se extrae 1 bit del resultado en cada iteración).
Iteraciones lentas.
Elevada latencia para un tamaño de palabra elevado.
Soluciones:
Uso de sumadores rápidos (CLA) y/o aritmética redundante (carry-save, signed-digit).
Empleo de recurrencias con un radix alto r = 2b (se extraen b bits del resultado en cada iteración).
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC
Formulación convencional: recurrencia radix 2 (se extrae 1 bit del resultado en cada iteración).
Iteraciones lentas.
Elevada latencia para un tamaño de palabra elevado.
Soluciones:
Uso de sumadores rápidos (CLA) y/o aritmética redundante (carry-save, signed-digit).
Empleo de recurrencias con un radix alto r = 2b (se extraen b bits del resultado en cada iteración).
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC CON RADIX ALTO EN MODO VECTORIZACIÓN
Modo vectorización.- Rotación del vector inicial hasta que se sitúa sobre el eje de coordenadas X. Resultados: xN+1=módulo y zN+1=argumento.
Fundamento: descomposición del ángulo de rotación q en una suma de ángulos elementales:
Los coeficientes si toman valores enteros en el intervalo {-(r -1), … , 0, … , (r -1)}, siendo el radix r = 2b.
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC CON RADIX ALTO EN MODO VECTORIZACIÓN
Modo vectorización.- Rotación del vector inicial hasta que se sitúa sobre el eje de coordenadas X. Resultados: xN+1=módulo y zN+1=argumento.
Fundamento: descomposición del ángulo de rotación q en una suma de ángulos elementales:
Los coeficientes si toman valores enteros en el intervalo {-(r -1), … , 0, … , (r -1)}, siendo el radix r = 2b.
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC CON RADIX ALTO EN MODO VECTORIZACIÓN
Y
X
(Gp:) a2
(Gp:) a3
(Gp:) a1
q = a1 + a2 + a3 + …
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC CON RADIX ALTO EN MODO VECTORIZACIÓN
Modo vectorización.- Rotación del vector inicial hasta que se sitúa sobre el eje de coordenadas X. Resultados: xN+1=módulo y zN+1=argumento.
Fundamento: descomposición del ángulo de rotación q en una suma de ángulos elementales:
Los coeficientes si toman valores enteros en el intervalo {-(r -1), … , 0, … , (r -1)}, siendo el radix r = 2b.
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
Expresión de las recurrencias:
d[i+1] = d[i] + sir -2iw[i]
w[i+1] = r(w[i] – sid[i])
z[i+1] = z[i] + tan-1(sir -i)
con d[1] = xin, w[1] = r yin, z[1] = 0.
Los coeficientes si se seleccionan mediante el redondeo de w[i] truncado a t bits fraccionales:
si = round (w[i]t )
ALGORITMO CORDIC CON RADIX ALTO EN MODO VECTORIZACIÓN
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
Expresión de las recurrencias:
d[i+1] = d[i] + sir -2iw[i]
w[i+1] = r(w[i] – sid[i])
z[i+1] = z[i] + tan-1(sir -i)
con d[1] = xin, w[1] = r yin, z[1] = 0.
Los coeficientes si se seleccionan mediante el redondeo de w[i] truncado a t bits fraccionales:
si = round (w[i]t )
ALGORITMO CORDIC CON RADIX ALTO EN MODO VECTORIZACIÓN
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
Expresión de las recurrencias:
d[i+1] = d[i] + sir -2iw[i]
w[i+1] = r(w[i] – sid[i])
z[i+1] = z[i] + tan-1(sir -i)
con d[1] = xin, w[1] = r yin, z[1] = 0.
Los coeficientes si se seleccionan mediante el redondeo de w[i] truncado a t bits fraccionales:
si = round (w[i]t )
ALGORITMO CORDIC CON RADIX ALTO EN MODO VECTORIZACIÓN
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC CON RADIX ALTO EN MODO VECTORIZACIÓN
Necesidad de dos escalados de la recurrencia (empleo de los factores M1 y M2) para asegurar convergencia.
Uno antes y otro después de la primera microrrotación.
Para simplificar el primer escalado, se utiliza un radix R inferior en la primera microrrotación, siendo:
R = 2B > 2ëb/2û+1, para t >2
Extensión del rango de convergencia.
Comparación de los F bits más significativos de xin e yin.
Si yin > xin+2-F, intercambio, z[1] = p/2 y se decrementa.
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC CON RADIX ALTO EN MODO VECTORIZACIÓN
Necesidad de dos escalados de la recurrencia (empleo de los factores M1 y M2) para asegurar convergencia.
Uno antes y otro después de la primera microrrotación.
Para simplificar el primer escalado, se utiliza un radix R inferior en la primera microrrotación, siendo:
R = 2B > 2ëb/2û+1, para t >2
Extensión del rango de convergencia.
Comparación de los F bits más significativos de xin e yin.
Si yin > xin+2-F, intercambio, z[1] = p/2 y se decrementa.
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC CON RADIX ALTO EN MODO VECTORIZACIÓN
Necesidad de dos escalados de la recurrencia (empleo de los factores M1 y M2) para asegurar convergencia.
Uno antes y otro después de la primera microrrotación.
Para simplificar el primer escalado, se utiliza un radix R inferior en la primera microrrotación, siendo:
R = 2B > 2ëb/2û+1, para t >2
Extensión del rango de convergencia.
Comparación de los F bits más significativos de xin e yin.
Si yin > xin+2-F, intercambio, z[1] = p/2 y se decrementa.
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC CON RADIX ALTO EN MODO VECTORIZACIÓN
Necesidad de dos escalados de la recurrencia (empleo de los factores M1 y M2) para asegurar convergencia.
Uno antes y otro después de la primera microrrotación.
Para simplificar el primer escalado, se utiliza un radix R inferior en la primera microrrotación, siendo:
R = 2B > 2ëb/2û+1, para t >2
Extensión del rango de convergencia.
Comparación de los F bits más significativos de xin e yin.
Si yin > xin+2-F, intercambio, z[1] = p/2 y se decrementa.
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC CON RADIX ALTO EN MODO VECTORIZACIÓN
Existencia de un factor de escala Ki en las variables d y w en cada microrrotación.
El factor de escala global viene dado por:
K depende del ángulo.
Cómputo de ln(K -1): g[i+1] = g[i] – (1/2)ln(1+si2r -2i).
Compensación evaluando la función exponencial:
xr = xC·exp(ln(K -1)) = xC·K -1
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC CON RADIX ALTO EN MODO VECTORIZACIÓN
Existencia de un factor de escala Ki en las variables d y w en cada microrrotación.
El factor de escala global viene dado por:
K depende del ángulo.
Cómputo de ln(K -1): g[i+1] = g[i] – (1/2)ln(1+si2r -2i).
Compensación evaluando la función exponencial:
xr = xC·exp(ln(K -1)) = xC·K -1
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC CON RADIX ALTO EN MODO VECTORIZACIÓN
Existencia de un factor de escala Ki en las variables d y w en cada microrrotación.
El factor de escala global viene dado por:
K depende del ángulo.
Cómputo de ln(K -1): g[i+1] = g[i] – (1/2)ln(1+si2r -2i).
Compensación evaluando la función exponencial:
xr = xC·exp(ln(K -1)) = xC·K -1
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC CON RADIX ALTO EN MODO VECTORIZACIÓN
Existencia de un factor de escala Ki en las variables d y w en cada microrrotación.
El factor de escala global viene dado por:
K depende del ángulo.
Cómputo de ln(K -1): g[i+1] = g[i] – (1/2)ln(1+si2r -2i).
Compensación evaluando la función exponencial:
xr = xC·exp(ln(K -1)) = xC·K -1
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ALGORITMO CORDIC CON RADIX ALTO EN MODO VECTORIZACIÓN
Existencia de un factor de escala Ki en las variables d y w en cada microrrotación.
El factor de escala global viene dado por:
K depende del ángulo.
Cómputo de ln(K -1): g[i+1] = g[i] – (1/2)ln(1+si2r -2i).
Compensación evaluando la función exponencial:
xr = xC·exp(ln(K -1)) = xC·K -1
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ARQUITECTURA
Arquitectura palabra-serie.
Formato de punto fijo.
Arquitectura para el cálculo del argumento del vector de entrada: función tan-1(yin/xin).
Arquitectura para el cálculo de módulo y argumento: (xin2+yin2)½ y tan-1(yin/xin).
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ARQUITECTURA
Arquitectura palabra-serie.
Formato de punto fijo.
Arquitectura para el cálculo del argumento del vector de entrada: función tan-1(yin/xin).
Arquitectura para el cálculo de módulo y argumento: (xin2+yin2)½ y tan-1(yin/xin).
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ARQUITECTURA
Arquitectura palabra-serie.
Formato de punto fijo.
Arquitectura para el cálculo del argumento del vector de entrada: función tan-1(yin/xin).
Arquitectura para el cálculo de módulo y argumento: (xin2+yin2)½ y tan-1(yin/xin).
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
ARQUITECTURA
Arquitectura palabra-serie.
Formato de punto fijo.
Arquitectura para el cálculo del argumento del vector de entrada: función tan-1(yin/xin).
Arquitectura para el cálculo de módulo y argumento: (xin2+yin2)½ y tan-1(yin/xin).
Arquitectura completa = Arquitectura argumento (modificada) + vía g.
(Gp:) z[i+1] = z[i] + tan-1(sir -i)
(Gp:) d[i+1] = d[i] + sir -2iw[i]
(Gp:) w[i+1] = r(w[i] – sid[i])
g[i+1] = g[i] – (1/2)ln(1+si2r -2i)
(Gp:) g[j+1] = r (g[j] – rj ln(1+ejr -j))
(Gp:) d[j+1] = d[j] + ejd[j]r -j
Vías d y w.- Realización de los escalados y las microrrotaciones.
Bloques de M1 y M2.- Obtención de los factores de escalado.
Bloques de si y ej.- Selección de los coeficientes mediante redondeo.
Vía z.- Determinación del ángulo elemental en cada microrrotación y cómputo del ángulo total.
Vía g.- Cómputo de ln(K -1) y, junto con la vía d, realización de las iteraciones de compensación.
Unidad de control (FSM).
g
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
Parámetros de diseño.
Precisión: n = 32 bits.
Radix r = 512, valor t = 3 bits .
Radix R = 32, valor F = 5 bits.
Tamaño de palabra interno: q = 38 bits fraccionales.
Es necesario realizar N = 4 microrrotaciones para alcanzar la precisión de n = 32 bits.
n ³ B + (N -1)·b
IMPLEMENTACIÓN
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
Parámetros de diseño.
Precisión: n = 32 bits.
Radix r = 512, valor t = 3 bits .
Radix R = 32, valor F = 5 bits.
Tamaño de palabra interno: q = 38 bits fraccionales.
Es necesario realizar N = 4 microrrotaciones para alcanzar la precisión de n = 32 bits.
n ³ B + (N -1)·b
IMPLEMENTACIÓN
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
Parámetros de diseño.
Precisión: n = 32 bits.
Radix r = 512, valor t = 3 bits .
Radix R = 32, valor F = 5 bits.
Tamaño de palabra interno: q = 38 bits fraccionales.
Es necesario realizar N = 4 microrrotaciones para alcanzar la precisión de n = 32 bits.
n ³ B + (N -1)·b
IMPLEMENTACIÓN
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
Parámetros de diseño.
Precisión: n = 32 bits.
Radix r = 512, valor t = 3 bits .
Radix R = 32, valor F = 5 bits.
Tamaño de palabra interno: q = 38 bits fraccionales.
Es necesario realizar N = 4 microrrotaciones para alcanzar la precisión de n = 32 bits.
n ³ B + (N -1)·b
IMPLEMENTACIÓN
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
Flujo de diseño basado en VHDL.
Herramientas CAD utilizadas en el diseño lógico:
HDLdesk, de Cadence (simulación funcional de los componentes).
Design Analyzer, de Synopsys (síntesis lógica y simulación pre-layout).
Librería de celdas estándar 0.7 mm CMOS doble metal de ES2.
IMPLEMENTACIÓN
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
Flujo de diseño basado en VHDL.
Herramientas CAD utilizadas en el diseño lógico:
HDLdesk, de Cadence (simulación funcional de los componentes).
Design Analyzer, de Synopsys (síntesis lógica y simulación pre-layout).
Librería de celdas estándar 0.7 mm CMOS doble metal de ES2.
IMPLEMENTACIÓN
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
Flujo de diseño basado en VHDL.
Herramientas CAD utilizadas en el diseño lógico:
HDLdesk, de Cadence (simulación funcional de los componentes).
Design Analyzer, de Synopsys (síntesis lógica y simulación pre-layout).
Librería de celdas estándar 0.7 mm CMOS doble metal de ES2.
IMPLEMENTACIÓN
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
Flujo de diseño basado en VHDL.
Herramientas CAD utilizadas en el diseño lógico:
HDLdesk, de Cadence (simulación funcional de los componentes).
Design Analyzer, de Synopsys (síntesis lógica y simulación pre-layout).
Librería de celdas estándar 0.7 mm CMOS doble metal de ES2.
IMPLEMENTACIÓN
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
Flujo de diseño basado en VHDL.
Herramientas CAD utilizadas en el diseño lógico:
HDLdesk, de Cadence (simulación funcional de los componentes).
Design Analyzer, de Synopsys (síntesis lógica y simulación pre-layout).
Librería de celdas estándar 0.7 mm CMOS doble metal de ES2.
IMPLEMENTACIÓN
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
IMPLEMENTACIÓN
Multiplicadores-Acumuladores (MAC):
Evaluación de la operación: h = a + b ·c.
Representación de los operandos:
Complemento a dos: sumando ( a ) y multiplicando ( c ).
SD-radix 4: multiplicador ( b ); reduce a la mitad el número de productos parciales a acumular.
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
IMPLEMENTACIÓN
Multiplicadores-Acumuladores (MAC):
Evaluación de la operación: h = a + b ·c.
Representación de los operandos:
Complemento a dos: sumando ( a ) y multiplicando ( c ).
SD-radix 4: multiplicador ( b ); reduce a la mitad el número de productos parciales a acumular.
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
IMPLEMENTACIÓN
Multiplicadores-Acumuladores (MAC):
Evaluación de la operación: h = a + b ·c.
Representación de los operandos:
Complemento a dos: sumando ( a ) y multiplicando ( c ).
SD-radix 4: multiplicador ( b ); reduce a la mitad el número de productos parciales a acumular.
1. Algoritmo
2. Arquitectura
3. Implementación
4. Conclusiones
IMPLEMENTACIÓN
Multiplicadores-Acumuladores (MAC):
Evaluación de la operación: h = a + b ·c.
Representación de los operandos:
Complemento a dos: sumando ( a ) y multiplicando ( c ).
SD-radix 4: multiplicador ( b ); reduce a la mitad el número de productos parciales a acumular.
ARCHITECTURE behave OF mac_d IS
— Declaración del componente CSA_TREE
— Declaración de señales y constantes
for U1 : csa_tree Use Entity work.csa_tree(crypt);
BEGIN
partial1:process(b)
begin
for i in 0 to 7 loop
b0(i)