ES2206452T3 - Metodo y aparato para realizar la transformacion discreta de coseno y su inversa. - Google Patents
Metodo y aparato para realizar la transformacion discreta de coseno y su inversa.Info
- Publication number
- ES2206452T3 ES2206452T3 ES93310487T ES93310487T ES2206452T3 ES 2206452 T3 ES2206452 T3 ES 2206452T3 ES 93310487 T ES93310487 T ES 93310487T ES 93310487 T ES93310487 T ES 93310487T ES 2206452 T3 ES2206452 T3 ES 2206452T3
- Authority
- ES
- Spain
- Prior art keywords
- unit
- data
- stage
- butterfly
- multiplication
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/10—Complex mathematical operations
- G06F17/14—Fourier, Walsh or analogous domain transformations, e.g. Laplace, Hilbert, Karhunen-Loeve, transforms
- G06F17/147—Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Mathematical Physics (AREA)
- Data Mining & Analysis (AREA)
- Mathematical Optimization (AREA)
- Mathematical Analysis (AREA)
- Pure & Applied Mathematics (AREA)
- Computational Mathematics (AREA)
- Theoretical Computer Science (AREA)
- General Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Software Systems (AREA)
- Discrete Mathematics (AREA)
- Algebra (AREA)
- Complex Calculations (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Superconductors And Manufacturing Methods Therefor (AREA)
- Magnetic Resonance Imaging Apparatus (AREA)
- Auxiliary Devices For Music (AREA)
Abstract
UN APARATO DE TRANSFORMACION DISCRETA DE COSENO (DCT), CAPAZ DE GENERAR DCT UNI-DIMENSIONAL Y BI-DIMENSIONAL Y RESULTADOS DE DCT INVERTIDOS, USA ALGORITMOS RAPIDOS DCT/IDCT DE SEIS ETAPAS PARA PROCESAR UNA SECUENCIA DE DATOS DE ENTRADA (DIN) DE UN BLOQUE DE DATOS DE 8X8. CADA UNA DE LAS ETAPAS DIFERENTES DE LOS ALGORITMOS RAPIDOS DCT/IDCT DE SEIS ETAPAS INCLUYE UN NUMERO DE OPERACIONES FLOTANTES, QUE PUEDEN SER DESARROLLADAS POR UNA UNIDAD (2) DE OPERACION FLOTANTE DEL APARATO DCT, O UN NUMERO DE MULTIPLICACIONES INTRINSECAS, UN NUMERO DE OPERACIONES DE MULTIPLICACION POST-SUMA, O UN NUMERO DE OPERACIONES DE SUSTRACCION POST-MULTIPLICACION, LA TOTALIDAD DE LAS CUALES PUEDEN SER REALIZADAS POR UNA UNIDAD (3) DE OPERACION DE MULTIPLICACION. UNA UNIDAD (6) DE CONTROL DEL APARATO DCT PERMITE EL USO DE UNA UNIDAD (2) UNICA DE OPERACION FLOTANTE Y UNA UNIDAD (3) UNICA DE OPERACION DE MULTIPLICACION PARA DESARROLLAR LAS DIFERENTES ETAPAS DE LOS ALGORITMOS RAPIDOS DCT/IDCT. LOS RESULTADOS DE CADA ETAPA DE LOS ALGORITMOS RAPIDOS DCT/IDCT SON ALMACENADOS EN UNA UNIDAD (4) DE REGISTRO DE DATOS DEL APARATO DCT PARA SERVIR COMO ENTRADAS PARA LAS ETAPAS SUCESIVAS DE LOS ALGORITMOS RAPIDOS DCT/IDCT.
Description
Método y aparato para realizar la transformada
discreta de coseno y su inversa.
La invención se refiere a un método y aparato
para realizar la transformada discreta de coseno y su inversa, más
particularmente a un aparato DCT/IDCT que es capaz de procesamiento
en tiempo real y que tiene una construcción hardware relativamente
pequeña y sencilla.
Las transformadas discretas de coseno directa e
inversa (DCT/IDCT) se realizan durante la compresión y descompresión
de datos de imagen digital. En una operación de compresión de
imagen digital convencional, una señal de imagen original
normalmente se divide en bloques de 8 x 8 píxeles, cada uno de los
cuales sufre una operación DCT de forma que se generan los datos de
transformada DCT. En una operación de descompresión de imagen
digital, se realiza una IDCT con los datos de la transformada DCT
que resultan de una DCT de un bloque de píxeles con el fin de
recuperar la señal de imagen original.
Si se va ejecutar una operación DCT/IDCT
bidimensional, cada fila (o columna) de bloque de datos sufre una
DCT/IDCT unidimensional. Cada columna (o fila) de datos de la
transformada DCT/IDCT sufre luego una segunda DCT/IDCT
unidimensional, completando así la operación DCT/IDCT. La DCT
unidimensional de un bloque de píxel 8 x 8 se puede obtener de la
ecuación siguiente:
F(k) = 1/2 C(k)
\sum_{m=0}S(m) Cos[(2m+1)k\pi /16], k=
0, 1,
...7
donde:
C(k) es igual a 2^{-1/2} cuando k = 0 y
es igual a 1 cuando k = 1, 2, ...7;
S(m) es el dato de píxel en el dominio
espacial; y
F(k) es el dato de transformada DCT
resultante.
Un algoritmo rápido DCT que se puede derivar de
la ecuación de arriba implica trece operaciones de multiplicación y
veintinueve operaciones de adición / sustracción. La Fig. 1 es un
diagrama de flujo ilustrando el algoritmo rápido DCT. El algoritmo
rápido DCT emplea tres clases de operaciones aritméticas: mariposa,
multiplicación y adición seguida de multiplicación, como se muestra
en las Figs. 2A a 2C. En referencia a la Fig. 2D, se emplea una
cuarta clase de operación aritmética, la multiplicación seguida de
sustracción, en un algoritmo rápido DCT correspondiente.
En referencia una vez más a la Fig. 1, el
algoritmo rápido DCT emplea doce operaciones mariposa, cinco
operaciones de adición seguida de multiplicación y ocho operaciones
de multiplicación intrínsecas. Un aparato para realizar el diagrama
de flujo de la Fig. 1 se puede dividir en seis unidades operativas:
una primera unidad capaz de realizar cuatro operaciones mariposa;
una segunda unidad capaz de realizar dos operaciones de adición
seguidas de multiplicación; una tercera unidad capaz de realizar
tres operaciones de adición seguida de multiplicación; una cuarta
unidad capaz de realizar tres operaciones de adición seguida de
multiplicación; una quinta unidad capaz de realizar otras cuatro
operaciones mariposa; y una sexta unidad capaz de realizar ocho
operaciones de multiplicación intrínseca.
El algoritmo rápido IDCT se puede obtener
mediante la realización del algoritmo rápido DCT en secuencia
invertida. La Fig. 3 ilustra el diagrama de flujo del algoritmo
rápido IDCT. Nótese que un aparato para realizar el diagrama de
flujo IDCT se puede dividir también en seis unidades operativas:
una primera unidad capaz de realizar ocho operaciones de
multiplicación; una segunda unidad capaz de realizar cuatro
operaciones mariposa; una tercera unidad capaz de realizar tres
operaciones de multiplicación seguida de sustracción; una cuarta
unidad capaz de realizar cuatro operaciones mariposa más; una
quinta unidad capaz de realizar dos operaciones más de
multiplicación seguida de sustracción; y una sexta unidad capaz de
realizar otras cuatro operaciones mariposa.
Si se desea procesar un bloque de datos 8 x 8 con
el uso de DCT/IDCT bidimensional, se provee un primer aparato para
realizar los antes descritos algoritmos DCT/IDCT para ejecutar una
primera operación unidimensional DCT/IDCT. Los datos transformados
resultante del primer aparato se proporcionan luego a un segundo
aparato que es similar al primer aparato con el fin de realizar una
segunda operación unidimensional DCT/IDCT.
El aparato DCT/IDCT convencional es relativamente
caro porque implica el uso de circuitos lógicos con un cableado
relativamente complejo, que se diseñan con el fin de conseguir el
procesamiento en serie a muy elevada velocidad de proceso. Sin
embargo, en la práctica actual, la mayoría de las aplicaciones no
necesitan un procesamiento de datos a una velocidad de proceso muy
elevada con el fin de conseguir una transformación en tiempo
real.
Las minutas del Simposio Internacional sobre
Circuitos y Sistemas de 1990, Vo. 1/4, de 1 de Mayo de 1990, Nueva
Orleans USA, páginas 77-80, P. Duhamel et al: "Un
circuito integrado DCT basado en un algoritmo de nueva estructura y
eficiente computacionalmente" describe un aparato DCT con un
núcleo recursivo que comprende una vía de datos y una memoria de
circuito integrado. Los datos intermedios generados en una etapa
previa se pueden realimentar como datos de entrada para una etapa
siguiente.
La FR-A-2,581,463
se refiere a un aparato para realizar operaciones DCT/IDCT. El flujo
DCT/IDCT se divide en dos tipos de operaciones elementales, a saber
tipo-A y tipo-PM. Se emplea una
pluralidad de dispositivos de computación tipo-A y
tipo- PM, dispuestos en serie, para realizar las diferentes
operaciones elementales.
Es deseable proporcionar un aparato DCT/IDCT que
tenga una construcción relativamente simple y pequeña y que sea
relativamente barato.
También es deseable proporcionar un aparato
DCT/IDCT que sea capaz de procesar datos en tiempo real.
La presente invención proporciona un método de
transformada discreta de coseno tal como se establece en la
reivindicación 1.
La invención proporciona también un aparato de
transformada discreta de coseno unidimensional tal como se establece
en la reivindicación 3.
La invención proporciona además un método de
transformada discreta inversa de coseno tal como se establece en la
reivindicación 7, y un aparato de transformada discreta inversa de
coseno tal como se establece en la reivindicación 9.
Otras características y ventajas de la presente
invención se volverán evidentes en la siguiente descripción
detallada de las realizaciones preferidas, con referencia a los
dibujos anexos, de los que:
La Fig. 1 es un diagrama de flujo de un algoritmo
rápido DCT que se va a ejecutar por el aparato DCT/IDCT;
La Fig. 2A ilustra una operación mariposa
empleada en el diagrama de flujo mostrado en la Fig. 1;
La Fig. 2B ilustra una operación de
multiplicación empleada en el diagrama de flujo de la Fig. 1;
La Fig. 2C ilustra una operación de adición
seguida de multiplicación usada en el diagrama de flujo mostrado en
la Fig. 1;
La Fig. 2D ilustra una operación de
multiplicación seguida de sustracción que es empleada por un
algoritmo rápido DCT;
La Fig. 3 es un diagrama de flujo de un algoritmo
rápido IDCT que se va a ejecutar mediante el aparato DCT/IDCT;
La Fig. 4 es un esquemático del diagrama de
bloques del circuito de la primera realización preferida de un
aparato DCT/IDCT según la presente invención;
La Fig. 5 es un diagrama de tiempos ilustrando el
funcionamiento de la primera realización preferida durante una
operación DCT;
La Fig. 6 es un diagrama de tiempos ilustrando el
funcionamiento de la primera realización preferida durante una
operación IDCT;
La Fig. 7 es un esquemático del diagrama de
bloques del circuito de la segunda realización preferida de un
aparato DCT/IDCT según la presente invención; y
La Fig. 8 es un diagrama de tiempos ilustrando el
funcionamiento de la segunda realización preferida.
En referencia a la Fig. 4, se muestra la primera
realización preferida de un aparato DCT/IDCT según la presente
invención que comprende una unidad de entrada 1, una unidad de
operación mariposa 2, una unidad de operación de adición y
multiplicación 3, una unidad de registro de datos 4, una unidad de
salida 5 y una unidad de control 6.
La unidad de entrada 1 es un demultiplexor que
recibe una secuencia de datos de entrada en serie (Din) de un bloque
de datos 8 x 8 desde un dispositivo externo (no mostrado) y envía
los datos de entrada (Din) a la unidad de operación mariposa 2 ó a
la unidad de operación de multiplicación 3 según la operación de
transformación proyectada.
La unidad de operación mariposa 2 incluye un
multiplexor 21 y un circuito mariposa 22. El circuito mariposa 22
genera la suma y la diferencia de dos datos de entrada al mismo. El
multiplexor 21 tiene una entrada de selección que está conectada a
la unidad de control 6 y entradas de datos que están conectadas a la
unidad de entrada 1 y a la unidad de registro de datos 4. La unidad
de control 6 controla al multiplexor 21 para seleccionar los datos
de entrada (Din) de la unidad de entrada 1 o los datos de la unidad
de registro 4, y proporciona los datos seleccionados al circuito
mariposa 22 para permitir a este último realizar una operación de
mariposa. La salida del circuito mariposa 22 se almacena en la
unidad de registro de datos 4 o se envía a la unidad de salida
5.
La unidad de operación de adición y
multiplicación 3 incluye un multiplexor selector de entrada 31, un
circuito de adición sustracción 32, un circuito multiplicador 33,
una memoria de solo lectura (ROM) de coeficientes 34, y un
multiplexor selector de salida 35. La ROM de coeficientes 34
contiene una pluralidad de coeficientes de ponderación que sirven
como una de las entradas de operandos al circuito multiplicador 33.
La unidad de operación de multiplicación 3 es capaz de realizar
multiplicación, adición seguida de multiplicación y multiplicación
seguida de sustracción. Los datos de entrada (Din) desde la unidad
de entrada 1 o los datos desde la unidad de registro de datos 4 se
envían al circuito de adición / sustracción 32 o al multiplexor de
selección de entrada 31 con el fin de permitir a la unidad de
operación de adición y multiplicación 3 la operación aritmética
pretendida. Las salidas del circuito de adición / sustracción 32 al
multiplexor selector de salida 35 para ser almacenados en la unidad
de registro de datos 4. La salida del circuito multiplicador 33
también se puede enviar directamente a la unidad de salida 5.
Cuando la unidad de operación de adición y
multiplicación 3 ejecuta una operación de multiplicación, el dato
seleccionado del multiplexor selector de entrada 31 se envía al
circuito multiplicador 33. Al mismo tiempo la ROM de coeficientes 34
es controlada por la unidad de control 6 para proporcionar uno
predeterminado de los coeficientes de ponderación al circuito
multiplicador 33, permitiendo por eso que este último realice la
operación de multiplicación.
Cuando la unidad de operación de multiplicación 3
ejecuta una operación de adición seguida de multiplicación, el
circuito de adición / sustracción 32 recibe dos datos sucesivos de
entrada desde la unidad de registro de datos 4. La suma de los
datos de entrada se envía luego al circuito multiplicador 33. Al
mismo tiempo la ROM de coeficientes 34 es controlada por la unidad
de control 6 para que proporcione uno predeterminado de los
coeficientes de ponderación al circuito multiplicador 33,
permitiendo así a este último completar la operación de adición
seguida de multiplicación.
Cuando la unidad de operación de adición y
multiplicación 3 ejecuta una operación de multiplicación seguida de
sustracción, se reciben dos datos sucesivos desde la unidad de
registro de datos 4 por el circuito de adición / sustracción 32 y el
circuito multiplicador 33. Al mismo tiempo la ROM de coeficientes
34 es controlada por la unidad de control 6 para que proporcione
uno predeterminado de los coeficientes de ponderación al circuito
multiplicador 33. El producto de salida del circuito multiplicador
33 se utiliza como la otra entrada al circuito de adición /
sustracción 32. El circuito de adición / sustracción 32 resta el
dato procedente de la unidad de registros de datos 4 del producto de
salida del circuito multiplicador 33, completando así la operación
de multiplicación y adición sustracción.
La unidad de registro de datos 4 es un fichero de
registros de cuatro puertos, como una memoria de acceso aleatorio
(RAM) con dos puertos de escritura (WP1, WP2) y dos puertos de
lectura (RP1, RP2). El primer conjunto de puertos de lectura y
escritura (RP1, WP1) de la unidad de registro de datos 4 está
conectado a la unidad de operación mariposa 2, mientras que el
segundo conjunto de puertos de lectura y escritura (RP2, WP2) de la
misma está conectado la unidad de operación de adición y
multiplicación 3. La unidad de registro de datos 4 sirve para
almacenar datos procedentes de la unidad de operación mariposa 2 y
de la unidad de operación de adición y multiplicación 3, y sirve
para proporcionar datos a las mismas.
La unidad de salida 5 es un multiplexor que
selecciona la salida del circuito mariposa 22 o del circuito
multiplicador 33, dependiendo de si se está realizando DCT o
IDCT.
Finalmente, la unidad de control 6 es responsable
de controlar las operaciones de lectura / escritura de la ROM de
coeficientes 34 y de la unidad de registro de datos 4, y es también
responsable de controlar los distintos multiplexores 21, 31, 35. La
unidad de control es responsable además de controlar la
temporización de las operaciones de los restantes componentes del
aparato DCT/IDCT.
Las Figs. 5 y 6 son diagramas de temporización
que ilustran el funcionamiento de la primera realización preferida.
Para un bloque de datos (N) que se somete a DCT/IDCT bidimensional,
se obtiene un primer bloque de datos de transformada tras una
primera operación DCT/IDCT unidimensional (1-D). El
primer bloque de datos de transformada sufre después una segunda
DCT/IDCT 1-D con el fin de realizar una DCT/IDCT
bidimensional. Cada operación DCT/IDCT 1-D se puede
realizar en seis etapas operativas que implican el uso de la unidad
de operación mariposa 2 o de la unidad de operación de adición y
multiplicación 3. En referencia a la Fig. 5, las etapas primera,
tercera y quinta del algoritmo rápido DCT mostrado en la Fig. 1
requiere el uso de la unidad de operación mariposa 2, mientras que
las etapas segunda, cuarta y sexta del algoritmo rápido DCT
requieren el uso de la unidad de operación de multiplicación 3. Las
etapas segunda y cuarta del algoritmo rápido DCT implican
operaciones de adición seguidas de multiplicación, mientras que la
sexta etapa del algoritmo rápido DCT implica operaciones de
multiplicación. En referencia ahora a la Fig. 6, las etapas
primera, tercera y quinta del algoritmo rápido IDCT mostrado en la
Fig. 3 requieren el uso de la unidad de operación de adición y
multiplicación 3, mientras que las etapas segunda, cuarta y sexta
del algoritmo rápido IDCT requieren el uso de la unidad de operación
mariposa 2. La primera etapa del algoritmo rápido IDCT implica
operaciones de multiplicación intrínseca, mientras que las etapas
tercera y quinta del algoritmo rápido IDCT implica operaciones de
multiplicación seguida de sustracción. En la presente invención la
primera etapa de la primera DCT/IDCT 1-D se realiza
inmediatamente tras la recepción del bloque de datos de entrada
(N). Los resultados de la DCT/IDCT bidimensional se pueden obtener
de la salida de la sexta etapa de la segunda DCT/IDCT
1-D.
Nótese que los resultados de las etapas primera a
quinta de una operación DCT/IDCT 1-D se almacenan en
la unidad de registro de datos 4 de manera que las entradas de datos
a las etapas segunda a sexta de la operación DCT/IDCT
1-D se pueden obtener de la última. Cuando se emplea
la primera realización preferida para realizar una operación
DCT/IDCT bidimensional, los resultados de la sexta etapa de la
primera operación DCT/IDCT de un bloque de datos (N) son almacenados
en la unidad de registro de datos 4. Esto es necesario porque el
bloque de datos de transformada obtenido de la primera operación
DCT/IDCT 1-D tiene que procesarse en columnas si el
bloque de datos originales se introdujo en filas. El bloque de datos
de transformada que se genera durante la primera operación DCT/IDCT
1-D sobreescribe el bloque de datos de transformada
obtenido de la segunda operación DCT/IDCT 1-D de un
bloque de datos precedente. Nótese que la construcción de la unidad
de registro de datos 4 permite a la unidad de operación mariposa 2
y a la unidad de adición y multiplicación 3 leer y escribir datos
allí al mismo tiempo, permitiendo así a estas dos últimas conseguir
un procesamiento secuencial paralelo. La unidad de registro de datos
4 permite además a cada una de las unidades de operación mariposa 2
y de operación de multiplicación 3 realizar tres etapas operativas
de algoritmo rápido en sucesión cuando están procesando datos.
Lo que sigue es una descripción detallada del
funcionamiento de la primera realización preferida.
En referencia de nuevo a las Figs. 4 y 5, cuando
la primera realización preferida se emplea para realizar DCT
1-D, los datos de sesenta y cuatro píxeles de un
bloque de píxeles 8 x 8 son suministrados secuencialmente a la
unidad de entrada 1 en filas (o columnas). La unidad de control 6
controla a la unidad de entrada 1 para enviar los datos de píxel de
entrada (Din) a la unidad de operación mariposa 2 con el fin de
permitir a esta última realizar la primera etapa del algoritmo
rápido DCT que implica cuatro operaciones mariposa para cada fila
(o columna). La unidad de control 6 controla luego a la unidad de
registro de datos 4 de manera que los datos de salida de la primera
etapa de la unidad de operación mariposa 2 son allí almacenados vía
el puerto de escritura (WP1). Cuando unos datos predeterminados de
salida de primera etapa han sido almacenados en la unidad de
registro de datos 4, la unidad de control controla a la unidad de
registro de datos 4 para que suministre los datos predeterminados de
salida de primera etapa a la unidad de operación de adición y
multiplicación 3 vía el puerto de lectura (RP2) con el fin de
permitir a la última realizar la segunda etapa del algoritmo rápido
DCT que implica dos operaciones de adición seguida de
multiplicación para cada fila (o columna). La unidad de control 6
controla a la unidad de operación de registro de datos 4 para
almacenar allí los datos de salida de segunda etapa procedentes de
la unidad de operación de adición y multiplicación 3 vía el puerto
de escritura (WP2). Después de que la unidad de operación mariposa 2
ha terminado la primera etapa del algoritmo rápido DCT, la unidad
de control 6 controla a la unidad de registro de datos 4 para
suministrar los datos de salida de primera y segunda etapa en una
secuencia predeterminada a la unidad de operación mariposa 2 vía el
puerto de lectura (RP1) con el fin de permitir a esta última
realizar la tercera etapa del algoritmo rápido DCT que implica
cuatro o más operaciones mariposa por cada fila (o columna). La
unidad de control 6 controla de nuevo a la unidad de registro de
datos 4 para almacenar allí los datos de salida de tercera etapa
procedentes de la unidad de operación mariposa 2 vía el puerto de
escritura (WP1). Cuando unos datos predeterminados de salida de
tercera etapa se han almacenado en la unidad de registro de datos
4, la unidad de control 6 controla a la unidad de registro de datos
4 para suministrar los datos predeterminados de salida de la tercera
etapa a la unidad de operación de adición y multiplicación 3 vía el
puerto de lectura (RP2) con el fin de permitir a la última realizar
la cuarta etapa del algoritmo rápido DCT que implica tres
operaciones de adición seguida de multiplicación por cada fila (o
columna). La unidad de control 6 controla de nuevo a la unidad de
registro de datos 4 para almacenar allí los datos de salida de
cuarta etapa procedentes de la unidad de operación de adición
seguida de multiplicación 3 vía el puerto de escritura (WP2).
Después de que la unidad de operación mariposa 2 ha terminado de
realizar la tercera etapa del algoritmo rápido DCT, la unidad de
control 6 controla a la unidad de registro de datos 4 para
suministrar los datos de salida de tercera y cuarta etapa en una
secuencia predeterminada a la unidad de operación mariposa 2 vía el
puerto de lectura (RP1) con el fin de permitir a esta última
realizar la quinta etapa del algoritmo rápido DCT que implica otras
cuatro operaciones mariposa por cada fila (o columna). Nuevamente la
unidad de control 6 controla a la unidad de registro de datos 4
para almacenar allí los datos de salida de quinta etapa procedentes
de la unidad de operación mariposa 2 vía el puerto de escritura
(WP1). La unidad de control 6 controla entonces a la unidad de
registro de datos 4 para suministrar los datos de salida de quinta
etapa a la unidad de operación de adición y multiplicación 3 vía el
puerto de lectura (RP2) con el fin de permitir a esta última
realizar la sexta etapa del algoritmo rápido DCT que implica ocho
operaciones de multiplicación por cada fila (o columna). Nótese que
la unidad de control 6 puede controlar a la unidad de salida 5 para
recibir datos de salida de sexta etapa procedentes de la unidad de
adición y multiplicación 3 si se realiza DCT 1-D. En
otro caso la unidad de control 6 controla a la unidad de registro
de datos 4 para que almacene allí los datos de salida de sexta
etapa.
Si se realiza DCT bidimensional, la unidad de
control 6 controla a la unidad de registro de datos 4 para sacar
secuencialmente los datos de salida de sexta etapa de la primera
DCT 1-D hacia la unidad de operación mariposa 2 en
columnas (o filas) vía el puerto de lectura (RP1) de la misma,
comenzando por tanto la segunda operación DCT 1-D.
El funcionamiento de la segunda operación DCT 1-D es
sustancialmente similar a la primera operación DCT
1-D, residiendo la principal diferencia en que en
vez de escribir los datos de salida de sexta etapa en la unidad de
registro de datos 4, los datos de salida de sexta etapa de la
segunda operación DCT 1-D se reciben por la unidad
de salida 5 procedentes del circuito multiplicador 33. Los datos de
salida de sexta etapa sirven como datos transformados finales y son
suministrados por la unidad de salida 5 a un dispositivo
externo.
En referencia de nuevo a las Figs. 4 y 6, cuando
se emplea la primera realización preferida para realizar DCT
1-D, los sesenta y cuatro datos de transformada de
un bloque de datos de transformada 8 x 8 son suministrados
secuencialmente a la unidad de entrada 1 en filas (o columnas). La
unidad de control 6 controla a la unidad de entrada 1 para enviar
los datos de transformada de entrada (Din) a la unidad de operación
de adición y multiplicación 3 con el fin de permitir a esta última
realizar la primera etapa del algoritmo rápido IDCT que implica
ocho operaciones de multiplicación por cada fila (o columna). La
unidad de control 6 controla luego a la unidad de registro de datos
4 de manera que los datos de salida de la primera etapa de la unidad
de operación de adición y multiplicación 3 son almacenados en la
unidad de registro de datos 4 vía el puerto de escritura (WP2) de
la misma. Cuando unos datos predeterminados de salida de primera
etapa han sido almacenados en la unidad de registro de datos 4, la
unidad de control 6 controla a la unidad de registro de datos 4
para que suministre los datos disponibles de salida de primera
etapa a la unidad de operación mariposa 2 vía el puerto de lectura
(RP1) con el fin de permitir a la última realizar la segunda etapa
del algoritmo rápido IDCT que implica cuatro operaciones mariposa
para cada fila (o columna). La unidad de control 6 controla de
nuevo a la unidad de operación de registro de datos 4 para
almacenar allí los datos de salida de segunda etapa procedentes de
la unidad de operación mariposa 2 vía el puerto de escritura (WP1)
de la misma. Cuando unos predeterminados datos de salida de segunda
etapa se han almacenado en la unidad de registro de datos 4, la
unidad de control 6 controla a la unidad de registro de datos 4 para
suministrar los datos predeterminados de salida de segunda etapa a
la unidad de operación de adición y multiplicación 3 vía el puerto
de lectura (RP2) con el fin de permitir a esta última realizar la
tercera etapa del algoritmo rápido IDCT que implica tres operaciones
de multiplicación seguida de sustracción por cada fila (o columna).
La unidad de control 6 controla de nuevo a la unidad de registro de
datos 4 para almacenar allí los datos de salida de tercera etapa
procedentes de la unidad de operación de adición y multiplicación 3
vía el puerto de escritura (WP2) de la misma. Después de que la
unidad de operación mariposa 2 ha terminado de realizar la segunda
etapa del algoritmo rápido IDCT, la unidad de control 6 controla a
la unidad de registro de datos 4 para suministrar los datos de
salida de segunda y tercera etapa en una secuencia predeterminada a
la unidad de operación mariposa 2 vía el puerto de lectura (RP1) con
el fin de permitir a esta última realizar la cuarta etapa del
algoritmo rápido IDCT que implica cuatro operaciones mariposa más
por cada fila (o columna). Nuevamente la unidad de control 6
controla a la unidad de registro de datos 4 para almacenar allí los
datos de salida de cuarta etapa procedentes de la unidad de
operación mariposa 2 vía el puerto de escritura (WP1) de la misma.
Cuando unos datos predeterminados de salida de cuarta etapa se han
almacenado en la unidad de registro de datos 4, la unidad de
control 6 controla a la unidad de registro de datos 4 para
suministrar los datos predeterminados de salida de cuarta etapa a
la unidad de operación de adición y multiplicación 3 vía el puerto
de lectura (RP2) con el fin de permitir a la última realizar la
quinta etapa del algoritmo rápido IDCT que implica dos operaciones
de multiplicación seguida de sustracción por cada fila (o columna).
La unidad de control 6 controla nuevamente a la unidad de registro
de datos 4 para almacenar los datos de salida de quinta etapa a la
unidad de operación de adición y multiplicación 3 vía el puerto de
escritura (WP2). Después de que la unidad de operación mariposa 2 ha
terminado de realizar la cuarta etapa del algoritmo rápido IDCT, la
unidad de control 6 controla a la unidad de registro de datos 4
para suministrar los datos de salida de cuarta y quinta etapa en
una secuencia predeterminada a la unidad de operación mariposa 2 vía
el puerto de lectura (RP1) con el fin de permitir a esta última
realizar la sexta etapa del algoritmo rápido IDCT que implica
otras cuatro operaciones mariposa por cada fila (o columna). La
unidad de control 6 puede controlar a la unidad de salida 5 para
recibir datos de salida de sexta etapa procedentes de la unidad de
operación mariposa 2 si se realiza IDCT 1-D. En
otro caso la unidad de control 6 controla a la unidad de registro
de datos 4 para que almacene allí los datos de salida de sexta
etapa.
Si se realiza IDCT bidimensional, la unidad de
control 6 controla a la unidad de registro de datos 4 para sacar
secuencialmente los datos de salida de sexta etapa de la primera
IDCT 1-D hacia la unidad de operación de adición y
multiplicación 3 en columnas (o filas) vía el puerto de lectura
(RP2) de la misma, comenzando por tanto la segunda operación DCT
1-D. El funcionamiento de la segunda operación DCT
1-D es sustancialmente similar a la primera
operación DCT 1-D, residiendo la principal
diferencia en que, en vez de escribir los datos de salida de sexta
etapa en la unidad de registro de datos 4, los datos de salida de
sexta etapa de la segunda operación DCT 1-D se
reciben por la unidad de salida 5 procedentes del circuito mariposa
22. Los datos de salida de sexta etapa son datos de píxel
recuperados y son suministrados por la unidad de salida 5 a un
dispositivo externo.
En referencia a la Fig. 7, la segunda realización
preferida de un aparato DCT/IDCT según la presente invención es
capaz de realizar procesamiento secuencial DCT/IDCT bidimensional
de un bloque de datos 8 x 8 y se muestra comprendiendo dos aparatos
DCT/IDCT 1-D 7, 8 y una unidad de control 9. Cada
uno de los aparatos DCT/IDCT 1-D es capaz de
realizar los algoritmos rápidos DCT/IDCT 1-D de seis
etapas mostrados en las Figs. 1 y 3. El primer aparato DCT/IDCT
1-D 7 comprende: una unidad de entrada 71, tal como
un demultiplexor; una unidad de operación mariposa 72 incluyendo un
multiplexor 721 y un circuito mariposa 722; una unidad de operación
de adición y multiplicación 73 incluyendo un multiplexor selector de
entrada 731, un circuito de adición / sustracción 732, un circuito
multiplicador 733, una ROM de coeficientes 734 y un multiplexor
selector de salida 735; y una primera unidad de registro de datos 74
para almacenar los resultados de las seis etapas de la primera
operación DCT/IDCT 1-D y que sirve también como
memoria de transposición para suministrar datos de entrada al
segundo aparato DCT/IDCT 1-D 8.
El segundo aparato DCT/IDCT 1-D
8 comprende: una unidad de operación mariposa 81 incluyendo un
multiplexor 811 y un circuito mariposa 812; una unidad de operación
de adición y multiplicación 82 incluyendo un multiplexor selector de
entrada 821, un circuito de adición / sustracción 822, un circuito
multiplicador 823 y un multiplexor selector de salida 824; una
segunda unidad de registro de datos 83; y una unidad de salida 84,
tal como un multiplexor. Los circuitos multiplicadores 733, 823
comparten una ROM común de coeficientes 734. La unidad de control 9
es para controlar las operaciones de lectura / escritura de la ROM
de coeficientes 734 y las unidades de registro de datos 74, 83, y
es también para controlar a los diferentes multiplexores721, 731,
735, 811, 821, 824. La unidad de control 9 es además para controlar
la temporización de las operaciones de los restantes componentes de
los aparatos DCT/IDCT 1-D primero y segundo 7,
8.
En referencia a las Figs. 7 y 8, durante el
funcionamiento de la segunda realización preferida, cuando el primer
aparato DCT/IDCT 1-D recibe filas de datos de
entrada (Din) correspondientes a un bloque de datos (N), el segundo
aparato DCT/IDCT 1-D 8 recibe columnas de datos de
transformada DCT/IDCT correspondientes a un bloque de datos previo
(N-1) procedentes del puerto de lectura (RP1A) de la
unidad de registro de datos 74 si se está realizando una operación
DCT bidimensional, o procedentes del puerto de lectura (RP2A) de
esta última si se está realizando una operación IDCT bidimensional.
Como ambos aparatos DCT/IDCT 1-D 7, 8 realizan la
sexta etapa del algoritmo rápido DCT/IDCT, los datos finales de
transformada correspondientes al bloque de datos
(N-1) se reciben por la unidad de salida 84 para su
transmisión a un dispositivo externo. Entretanto, los datos de
transformada DCT/IDCT correspondientes al bloque de datos (N) son
almacenados en la unidad de registro de datos 74 con el fin de
permitir al segundo aparato DCT/IDCT 1-D 8 realizar
la misma operación en columnas.
La segunda realización preferida tiene una
velocidad de proceso que es dos veces la de la primera realización
preferida, permitiendo así una mayor velocidad de salida de
bits.
Claims (11)
1. Un método para calcular una transformada
discreta de coseno (DCT) en seis etapas mediante proceso de una
secuencia de datos de entrada (Din) de un bloque de datos 8 x 8
para generar una secuencia de datos transformados, donde las etapas
primera, tercera y quinta de dicho método implican una pluralidad de
operaciones mariposa, las etapas segunda y cuarta de dicho método
implican una pluralidad de operaciones de adición seguida de
multiplicación, y la sexta etapa de dicho método implica una
pluralidad de operaciones de multiplicación, comprendiendo dicho
método los pasos de:
(a) suministrar dicha secuencia de datos de
entrada (Din) a una unidad de entrada (1);
(b) dicha unidad de entrada (1) suministrando
dichos datos de entrada (Din) a una unidad de operación mariposa
(2) con el fin de realizar operaciones mariposa de dicha primera
etapa;
(c) almacenar en la unidad de registro de datos
(4) los datos de salida de primera etapa procedentes de dicha
unidad de operación mariposa (2);
(d) suministrar unos predeterminados de dichos
datos de salida de primera etapa almacenados en dicha unidad de
registro de datos (4) a una unidad de operación de adición y
multiplicación (3) con el fin de realizar dichas operaciones de
adición seguida de multiplicación de dicha segunda etapa y donde
dicha unidad de adición y multiplicación comienza a realizar dichas
operaciones de adición seguida de multiplicación de dicha segunda
etapa cuando dichos unos predeterminados de dichos datos de salida
de primera etapa han sido almacenados en dicha unidad de registro de
datos (4), mientras dicha unidad de operación mariposa continua
para realizar operaciones mariposa de dicha primera etapa;
(e) almacenar en dicha unidad de registro de
datos (4) datos de salida de segunda etapa procedentes de dicha
unidad de operación de adición y multiplicación (3);
(f) sacar de dicha unidad de registro de datos
(4) dichos datos de salida de primera y segunda etapa en una
secuencia predeterminada hacia dicha unidad de operación mariposa
(2) donde dicha unidad de operación mariposa (2) realiza operaciones
mariposa de dicha tercera etapa después de que dicha unidad de
operación mariposa (2) ha terminado de realizar operaciones mariposa
de dicha primera etapa;
(g) almacenar en dicha unidad de registro de
datos (4) datos de salida de tercera etapa procedentes de dicha
unidad de operación mariposa (2);
(h) dicha unidad de registro de datos (4)
suministrando unos predeterminados de dichos datos de salida de
tercera etapa a dicha unidad de operación de adición y
multiplicación con el fin de realizar dichas operaciones de adición
seguida de multiplicación de dicha cuarta etapa, donde dicha unidad
de adición y multiplicación comienza a realizar dichas operaciones
de adición seguida de multiplicación de dicha cuarta etapa cuando
dichos unos predeterminados de dichos datos de salida de tercera
etapa se han almacenado en dicha unidad de registro de datos (4),
mientras dicha unidad de operación mariposa continua para realizar
dicha tercera etapa;
(i) almacenar en dicha unidad de registro de
datos (4) datos de salida de cuarta etapa procedentes de dicha
unidad de operación de adición y multiplicación (3);
(j) dicha unidad de registro de datos (4)
proporcionando dichos datos de salida de tercera y cuarta etapa en
una secuencia predeterminada a dicha unidad de operación mariposa
(2) y donde dicha unidad de operación mariposa (2) realiza
operaciones mariposa de dicha quinta etapa después de que dicha
unidad de operación mariposa (2) ha terminado de realizar dichas
operaciones mariposa de dicha tercera etapa;
(k) almacenar en dicha unidad de registro de
datos (4) datos de salida de quinta etapa procedentes de dicha
unidad de operación mariposa (2);
(l) dicha unidad de registro de datos (4)
suministrando dichos datos de salida de quinta etapa a dicha unidad
de operación de adición y multiplicación (3) y donde dicha unidad
de operación de adición y multiplicación (3) realiza operaciones de
multiplicación de dicha sexta etapa; y
(m) enviar a una unidad de salida (5) dichos
datos de salida de sexta etapa desde dicha unidad de operación de
adición y multiplicación (3).
2. El método como se reivindica en la
reivindicación 1, comprendiendo además, entre los pasos (l) y (m),
los pasos de:
almacenar en dicha unidad de registro de datos
(4) dichos datos de salida de sexta etapa;
\newpage
dicha unidad de registro de datos (4)
proporcionando dichos datos de salida de sexta etapa a dicha unidad
de operación mariposa (2) y donde dicha unidad de operación
mariposa (2) realiza dicha primera etapa; y repetir los pasos (c) a
(l).
3. Aparato para calcular una transformada
discreta de coseno unidimensional (DCT) en seis etapas mediante el
procesamiento de una secuencia de datos de entrada (Din) de un
bloque de datos de 8 x 8 para generar una secuencia de datos de
transformada, donde las etapas primera, tercera y quinta implican
una pluralidad de operaciones mariposa, las etapas segunda y cuarta
implican una pluralidad de operaciones de adición seguida de
multiplicación, y una sexta etapa implica una pluralidad de
operaciones de multiplicación, comprendiendo dicho aparato DCT:
una unidad de entrada (1) adaptada para recibir
dichos datos de entrada (Din);
una unidad de operación mariposa (2) adaptada
para realizar dichas etapas primera, tercera y quinta y
comprendiendo medios adaptados para generar datos de salida de las
etapas primera, tercera y quinta, respectivamente;
una unidad de operación de adición y
multiplicación (3) adaptada para realizar dichas etapas segunda,
cuarta y sexta y comprendiendo medios adaptados para generar datos
de salidas de las etapas segunda, cuarta y sexta,
respectivamente;
una unidad de registro de datos (4) conectada a
dicha unidad de operación mariposa (2) y a dicha unidad de operación
de adición y multiplicación (3) y comprendiendo medios adaptados
para almacenar allí dichos datos de salida de las etapas primera,
segunda, tercera, cuarta y quinta;
una unidad de control (6) conectada a dicha
unidad de entrada (1), a dicha unidad de operación mariposa (2), a
dicha unidad de registro de datos (4) y a dicha unidad de operación
de multiplicación (3) y a una unidad de salida donde dicha unidad de
control comprende medios adaptados para controlar a dicha unidad de
operación mariposa, a dicha unidad de registro de datos, a dicha
unidad de adición y multiplicación, a dicha unidad de entrada y a
dicha unidad de salida;
dicha unidad de entrada comprendiendo medios
adaptados para proveer dichos datos de entrada (Din) a dicha unidad
de operación mariposa (2);
dicha unidad de registro de datos (4)
comprendiendo medios adaptados para almacenar dichos datos de salida
de primera etapa procedentes de dicha unidad de operación mariposa
(2);
dicha unidad de registro de datos (4)
comprendiendo además medios adaptados para proporcionar unos
predeterminados de dichos datos de salida de primera etapa a dicha
unidad de operación de adición y multiplicación donde dicha unidad
de operación de adición y multiplicación comprende medios adaptados
para comenzar la realización y para realizar dicha segunda etapa de
dicho algoritmo rápido DCT cuando dichos unos predeterminados de
dichos datos de salida de primera etapa han sido almacenados en
dicha unidad de registro de datos (4), y mientras dicha operación
mariposa continúa para realizar dicha primera etapa de dicho
algoritmo rápido DCT;
dicha unidad de registro de datos (4)
comprendiendo además medios adaptados para almacenar dichos datos
de salida de segunda etapa procedentes de dicha unidad de operación
de adición y multiplicación (3);
dicha unidad de registro de datos (4)
comprendiendo además medios adaptados para proporcionar dichos datos
de salida de primera y segunda etapa en una secuencia
predeterminada a dicha unidad de operación mariposa (2)
comprendiendo dicha unidad de operación mariposa medios adaptados
para realizar dicha tercera etapa después de que dicha unidad de
operación mariposa (2) ha finalizado de realizar dicha primera
etapa;
dicha unidad de registro de datos (4)
comprendiendo además medios adaptados para almacenar dichos datos de
salida de tercera etapa procedentes de dicha unidad de operación
mariposa (2);
dicha unidad de registro de datos (4)
comprendiendo además medios adaptados para proporcionar unos
predeterminados de dichos datos de salida de tercera etapa a dicha
unidad de operación de adición y multiplicación (3) y donde dicha
unidad de operación de adición y multiplicación comprende medios
adaptados para comenzar la realización y para realizar dicha cuarta
etapa cuando dichos unos predeterminados de dichos datos de salida
de tercera etapa han sido almacenados en dicha unidad de registro de
datos (4), y mientras dicha unidad de operación mariposa continúa
para realizar dicha primera etapa de dicho algoritmo rápido DCT;
dicha unidad de registro de datos (4)
comprendiendo además medios adaptados para almacenar dichos datos
de salida de cuarta etapa procedentes de dicha unidad de operación
de adición y multiplicación (3);
dicha unidad de registro de datos (4)
comprendiendo además medios adaptados para proporcionar dichos datos
de salida de tercera y cuarta etapa en una secuencia predeterminada
a dicha unidad de operación mariposa (2) y donde dicha unidad de
operación mariposa comprende medios adaptados para realizar dicha
quinta etapa de dicho algoritmo rápido DCT después de que dicha
unidad de operación mariposa (2) ha finalizado de realizar dicha
tercera etapa de dicho algoritmo rápido DCT;
dicha unidad de registro de datos (4)
comprendiendo además medios adaptados para almacenar dichos datos de
salida de quinta etapa, procedentes de dicha unidad de operación
mariposa (2);
dicha unidad de registro de datos (4)
comprendiendo además medios adaptados para proporcionar datos de
salida de quinta etapa a dicha unidad de operación de adición y
multiplicación (3) y donde dicha unidad de operación de adición y
multiplicación (3) comprende medios adaptados para realizar dicha
sexta etapa de dicho algoritmo rápido DCT; y
una unidad de salida (5) conectada a dicha unidad
de operación de multiplicación (3) y a dicha unidad de control (6)
adaptada para recibir dichos datos de salida de sexta etapa de
dicha unidad de operación de adición y multiplicación (3).
4. El aparato como el reivindicado en la
reivindicación 3, donde dicha unidad de operación mariposa (2)
comprende:
un multiplexor (21) que tiene una entrada de
selección conectada a dicha unidad de control (6) y entradas de
datos conectadas a dicha unidad de entrada (1) y a dicha unidad de
registro de datos (4), y donde dicha unidad de control comprende
medios para controlar a dicha unidad multiplexora (21), dicho
multiplexor (21) comprendiendo medios adaptados para generar datos
de salida correspondientes a uno seleccionado de dicha unidad de
entrada (1) y de dicha unidad de registro de datos (4); y
unos medios mariposa (22) conectados a dicho
multiplexor (21) comprendiendo medios adaptados para recibir dichos
datos de salida del mismo.
5. El aparato como el reivindicado en la
reivindicación 3, donde dicha unidad de operación de adición y
multiplicación (3) comprende:
un circuito de adición / sustracción (32) que
está conectado a dicha unidad de control (6) y a dicha unidad de
registro de datos (4) y que comprende medios adaptados para recibir
dichos unos predeterminados datos de salida de dicha primera etapa
y de dicha tercera etapa de dicha unidad de registro de datos (4) y
medios adaptados para generar sumas de aquellos;
un circuito multiplicador (33) que está conectado
a dicha unidad de control (6), a dicha unidad de registro de datos
(4) y a dicha unidad de adición / sustracción (32); y
una ROM de coeficientes (34) que está conectada a
dicho circuito multiplicador (33) y a dicha unidad de control (6) y
que contiene allí dentro una pluralidad de coeficientes de
ponderación;
medios adaptados para sacar unos predeterminados
de dichos coeficientes de ponderación de dicha ROM de coeficientes
(34);
dicho circuito multiplicador comprendiendo medios
adaptados para recibir dichas sumas de dicho circuito de adición /
sustracción (32) y dichos unos predeterminados de dichos
coeficientes de ponderación y medios adaptados para generar
productos de los mismos que sirven como dichos datos de salida de
segunda y cuarta etapa cuando dicha unidad de operación de adición
y multiplicación (3) realiza dichas segunda y cuarta etapas;
dicho circuito multiplicador (33) comprendiendo
medios adaptados para recibir dichos datos de salida de quinta etapa
desde dicha unidad de registro de datos (4) y dichos unos
predeterminados de dichos coeficientes de ponderación y medios
adaptados para generar productos de los mismos que sirven como
dichos datos de salida de sexta etapa cuando dicha unidad de
operación de adición y multiplicación (3) realiza dicha sexta etapa
y donde dicha unidad de control comprende medios para controlar a
dicha unidad de adición / sustracción, a dicho circuito
multiplicador, a dicha ROM de coeficientes, a dichos medios para
sacar unos predeterminados de dichos coeficientes de ponderación de
dicha ROM de coeficientes.
6. El aparato como el reivindicado en la
reivindicación 3, donde dicha unidad de registro de datos (4) es una
memoria de acceso aleatorio de cuatro puertos con un primer
conjunto de puertos de lectura y escritura (RP1, WP1) conectados a
dicha unidad de operación mariposa (2) y un segundo conjunto de
puertos de lectura y escritura (RP2, WP2) conectados a dicha unidad
de operación de adición y multiplicación (3).
7. Un método de cálculo de una transformada
discreta de coseno inversa (IDCT) en seis etapas mediante proceso de
una secuencia de datos de entrada (Din) de un bloque de datos 8 x 8
para generar una secuencia de datos transformados, implicando la
primera etapa de dicho método una pluralidad de operaciones
mariposa, implicando las etapas segunda, cuarta y sexta de dicho
método una pluralidad de operaciones mariposa, e implicando la
tercera y quinta etapas de dicho método una pluralidad de
operaciones de multiplicación seguidas de sustracción, comprendiendo
dicho método los pasos de:
(a) suministrar dicha secuencia de datos de
entrada (Din) a una unidad de entrada (1);
(b) dicha unidad de entrada (1) suministrando
dichos datos de entrada (Din) a una unidad de operación de adición
y multiplicación (3) donde dicha unidad de adición y multiplicación
(3) realiza dicha primera etapa;
(c) almacenar en una unidad de registro de datos
(4) los datos de salida de primera etapa procedentes de dicha unidad
de operación de adición y multiplicación (3);
(d) suministrando dicha unidad de registro de
datos (4) dichos datos de salida de primera etapa a una unidad de
operación mariposa (2) y realizando dicha unidad de operación
mariposa (2) dicha segunda etapa;
(e) almacenar en dicha unidad de registro de
datos (4) datos de salida de segunda etapa procedentes de dicha
unidad de operación mariposa (2);
(f) dicha unidad de registro de datos (4)
suministrando unos predeterminados de dichos datos de salida de
segunda etapa a una unidad de operación de adición y multiplicación
(3), dicha unidad de operación de adición y multiplicación (3)
comenzando a realizar y realizando dicha tercera etapa de dicho
algoritmo rápido DCT cuando dichos unos predeterminados de dichos
datos de salida de segunda etapa han sido almacenados en dicha
unidad de registro de datos (4), mientras la unidad de operación
mariposa continúa para realizar dicha segunda etapa;
(g) dicha unidad de registro de datos (4)
almacenando datos de salida de tercera etapa procedentes de dicha
unidad de operación de adición y multiplicación (3);
(h) dicha unidad de registro de datos (4)
suministrando dichos datos de salida de segunda y tercera etapa en
una secuencia predeterminada a dicha unidad de operación mariposa
(2) y dicha unidad de operación mariposa (2) realizando dicha cuarta
etapa después de que dicha unidad de operación mariposa (2) ha
terminado de realizar dicha segunda etapa;
(i) en dicha unidad de registro de datos (4)
almacenando datos de salida de cuarta etapa procedentes de dicha
unidad de operación mariposa (2);
(j) dicha unidad de registro de datos (4)
proporcionando unos predeterminados de dichos datos de salida de
cuarta etapa a dicha unidad de operación de adición y multiplicación
(3), dicha unidad de operación de adición y multiplicación (3)
comenzando realizar y realizando dicha quinta etapa cuando dichos
unos predeterminados datos de salida de dicha cuarta etapa han sido
almacenados en dicha unidad de registro de datos (4), mientras que
dicha unidad de operación mariposa continúa para realizar dicha
cuarta etapa;
(k) dicha unidad de registro de datos (4)
almacenando datos de salida de quinta etapa procedentes de dicha
unidad de operación de adición y multiplicación (3);(l) dicha
unidad de registro de datos (4) suministrando dichos datos de salida
de cuarta y quinta etapa en una secuencia predeterminada a dicha
unidad de operación mariposa (2), dicha unidad de operación
mariposa (2) realizando dicha sexta etapa después de que dicha
unidad de operación mariposa (2) ha terminado de realizar dicha
cuarta etapa; y
(m) enviar a una unidad de salida (5) dichos
datos de salida de sexta etapa desde dicha unidad de operación
mariposa (2).
8. El método como se reivindica en la
reivindicación 7, comprendiendo además, entre los pasos (l) y (m),
los pasos de:
dicha unidad de registro de datos (4) almacenando
dichos datos de salida de sexta etapa;
dicha unidad de registro de datos (4)
proporcionando dichos datos de salida de sexta etapa a dicha unidad
de operación de adición y multiplicación (3), dicha unidad de
operación de adición y multiplicación (3) realizando dicha primera
etapa; y
repitiendo los pasos (c) a (l).
9. Aparato para calcular una transformada
discreta de coseno inversa unidimensional (IDCT) en seis etapas
mediante el procesamiento de una secuencia de datos de entrada
(Din) de un bloque de datos de 8 x 8 para generar una secuencia de
datos de transformada,
donde la primera etapa implica una pluralidad de
operaciones de multiplicación, las etapas segunda, cuarta y sexta
implican una pluralidad de operaciones mariposa, y la tercera y
quinta etapas implican una pluralidad de operaciones de
multiplicación seguida de sustracción, comprendiendo dicho aparato:
una unidad de entrada (1) adaptada para recibir dichos datos de
entrada (Din);
una unidad de operación de adición y
multiplicación (3) adaptada para realizar dichas etapas primera,
tercera y quinta y comprendiendo medios adaptados para generar
datos de salida de las etapas primera, tercera y quinta,
respectivamente;
una unidad de operación mariposa (2) adaptada
para realizar dichas etapas segunda, cuarta y sexta y comprendiendo
medios adaptados para generar datos de salida de las etapas segunda,
cuarta y sexta, respectivamente, cuando realiza dichas segunda,
cuarta y sexta etapas;
una unidad de registro de datos (4) conectada a
dicha unidad de operación mariposa (2) y a dicha unidad de operación
de adición y multiplicación (3) y adaptada para almacenar dichos
datos de salida de las etapas primera, segunda, tercera, cuarta y
quinta;
una unidad de control (6) conectada a dicha
unidad de entrada (1), a dicha unidad de operación mariposa (2), a
dicha unidad de registro de datos (4) y a dicha unidad de operación
de multiplicación (3) donde dicha unidad de control comprende medios
para controlar a dicha unidad de entrada, a dicha unidad de
operación mariposa, a dicha unidad de registro de datos, a dicha
unidad de adición y multiplicación, y a dicha unidad de salida;
dicha unidad de entrada comprendiendo medios
adaptados para proveer dichos datos de entrada (Din) a dicha unidad
de operación de adición y multiplicación (3), dicha unidad de
operación de adición y multiplicación (3) comprendiendo medios
adaptados para realizar dicha primera etapa;
dicha unidad de registro de datos (4)
comprendiendo medios adaptados para almacenar dichos datos de salida
de primera etapa procedentes de dicha unidad de operación de adición
y multiplicación (3);
dicha unidad de registro de datos (4)
comprendiendo además medios adaptados para proporcionar dichos datos
de salida de primera etapa a dicha unidad de operación mariposa
(2), dicha unidad de operación mariposa comprendiendo medios
adaptados para realizar dicha segunda etapa;
dicha unidad de registro de datos (4)
comprendiendo además medios adaptados para almacenar dichos datos
de salida de segunda etapa procedentes de dicha unidad de operación
mariposa (2);
dicha unidad de registro de datos (4)
comprendiendo además medios adaptados para proporcionar unos
predeterminados de dichos datos de salida de segunda etapa a dicha
unidad de operación de adición y multiplicación (3) comprendiendo
dicha unidad de operación de adición y multiplicación (3) medios
adaptados para comenzar a realizar y realizar dicha tercera etapa
cuando dichos unos predeterminados datos de salida de dicha segunda
etapa han sido almacenados en dicha unidad de registro de datos
(4), mientras dicha unidad de operación mariposa continúa para
realizar dicha segunda etapa de dicho algoritmo rápido IDCT;
dicha unidad de registro de datos (4)
comprendiendo además medios adaptados para almacenar dichos datos de
salida de tercera etapa procedentes de dicha unidad de operación de
adición y multiplicación (3);
dicha unidad de registro de datos (4)
comprendiendo además medios adaptados para proporcionar dichos datos
de salida de segunda y tercera etapa a dicha unidad de operación
mariposa (2), dicha unidad de operación mariposa (2) comprendiendo
medios adaptados para realizar dicha cuarta etapa después de que
dicha unidad de operación mariposa (2) ha terminado de realizar
dicha segunda etapa;
dicha unidad de registro de datos (4)
comprendiendo además medios adaptados para almacenar dichos datos
de salida de cuarta etapa procedentes de dicha unidad de operación
mariposa (2);
dicha unidad de registro de datos (4)
comprendiendo además medios adaptados para proporcionar unos
predeterminados de dichos datos de salida de cuarta etapa a dicha
unidad de operación de adición y multiplicación (3), dicha unidad de
operación de multiplicación (3) comprendiendo medios adaptados para
comenzar a realizar y para realizar dicha quinta etapa cuando
dichos unos predeterminados datos de salida de dicha cuarta etapa
han sido almacenados en dicha unidad de registro de datos (4),
mientras dicha unidad de operación mariposa continúa para realizar
dicha cuarta etapa de dicho algoritmo rápido IDCT;
dicha unidad de registro de datos (4)
comprendiendo además medios adaptados para almacenar dichos datos de
salida de quinta etapa procedentes de dicha unidad de operación de
adición y multiplicación (3);
dicha unidad de registro de datos (4)
comprendiendo además medios adaptados para proporcionar dichos datos
de salida de cuarta y quinta etapa en una secuencia predeterminada
a dicha unidad de operación mariposa (2), dicha unidad de
operación mariposa (2) comprendiendo medios adaptados para realizar
dicha sexta etapa después de que dicha unidad de operación mariposa
(2) ha terminado de realizar dicha cuarta etapa; y
dicha unidad de salida (5) conectada a dicha
unidad de operación mariposa (2) y a dicha unidad de control (6) y
comprendiendo medios adaptados para recibir dichos datos de salida
de sexta etapa de dicha unidad de operación mariposa (2).
10. El aparato unidimensional como el
reivindicado en la reivindicación 9, donde dicha unidad de operación
de adición y multiplicación (3) comprende:
\newpage
un primer multiplexor (31) teniendo una entrada
de selección conectada a dicha unidad de control (6) y entradas de
datos conectadas a dicha unidad de entrada (1) y a dicha unidad de
registro de datos (4), dicho primer multiplexor (31) comprendiendo
medios adaptados para generar datos de salida correspondientes a uno
seleccionado de dicha unidad de entrada (1) y de dicha unidad de
registro de datos (4);
una ROM de coeficientes (34) que está conectada a
dicha unidad de control (6) y que contiene allí dentro una
pluralidad de coeficientes de ponderación;
medios de salida para sacar unos predeterminados
de dichos coeficientes de ponderación de dicha ROM de
coeficientes;
un circuito multiplicador (33) que está conectado
a dicha unidad de control (6), a dicho primer multiplexor (31) y a
dicha ROM de coeficientes (34), dicho circuito multiplicador (33)
comprendiendo medios adaptados para recibir dichos datos de entrada
(Din) de dicha unidad de entrada (1) vía dicho primer multiplexor
(31) y dichos unos predeterminados de dichos coeficientes de
ponderación y comprendiendo medios adaptados para generar productos
de los mismos que sirven como dichos datos de salida de primera
etapa cuando dicha unidad de operación de adición y multiplicación
(3) realiza dicha primera etapa de dicho algoritmo rápido IDCT,
dicho circuito multiplicador (33) comprendiendo además medios
adaptados para recibir dichos datos de salida de dicho primer
multiplexor (31) y dichos unos predeterminados de dichos
coeficientes de ponderación y adaptados para generar productos de
los mismos cuando dicha unidad de operación de adición y
multiplicación (3) realiza dichas tercera y quinta etapas;
un circuito de adición / sustracción (32)
conectado a dicha unidad de control (6), a dicha unidad de
registro de datos (4) y a dicho circuito multiplicador (33), dicho
circuito de adición / sustracción (32) comprendiendo medios
adaptados para recibir dichos productos de dicho circuito
multiplicador (33) y dichos unos predeterminados de dichos datos de
salida de segunda y cuarta etapa desde dicha unidad de registro de
datos (4) y adaptado para generar diferencias de ellos cuando dicha
unidad de operación de multiplicación (3) realiza dichas etapas
tercera y quinta, sirviendo dichas diferencias como dichos datos de
salida de tercera y quinta etapa; y
un segundo multiplexor (35) teniendo una entrada
de selección conectada a dicha unidad de control (6), entradas de
datos conectadas a dicho circuito multiplicador (33) y a dicho
circuito de adición / sustracción (32), y una salida conectada a
dicha unidad de registro de datos (4), dicho segundo multiplexor
(35) comprendiendo medios adaptados para generar datos de salida
correspondientes a uno seleccionado de dicho circuito multiplicador
(33) y a dicho circuito de adición / sustracción (32) y donde dicha
unidad de control (6) comprende medios para controlar a dicho primer
multiplexor, a dicha ROM de coeficientes, a dichos medios de
salida, a dicho circuito multiplicador, a dicho circuito de adición
/ sustracción, a dicho segundo multiplexor.
11. El aparato unidimensional como el
reivindicado en la reivindicación 9, donde dicha unidad de registro
de datos (4) es una memoria de acceso aleatorio de cuatro puertos
con un primer conjunto de puertos de lectura y escritura (RP1, WP1)
conectados a dicha unidad de operación mariposa (2) y un segundo
conjunto de puertos de lectura y escritura (RP2, WP2) conectados a
dicha unidad de operación de adición y multiplicación (3).
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/143,837 US5471412A (en) | 1993-10-27 | 1993-10-27 | Recycling and parallel processing method and apparatus for performing discrete cosine transform and its inverse |
| EP93310487A EP0660247B1 (en) | 1993-10-27 | 1993-12-23 | Method and apparatus for performing discrete cosine transform and its inverse |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| ES2206452T3 true ES2206452T3 (es) | 2004-05-16 |
Family
ID=26134616
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| ES93310487T Expired - Lifetime ES2206452T3 (es) | 1993-10-27 | 1993-12-23 | Metodo y aparato para realizar la transformacion discreta de coseno y su inversa. |
Country Status (7)
| Country | Link |
|---|---|
| US (1) | US5471412A (es) |
| EP (1) | EP0660247B1 (es) |
| AT (1) | ATE245838T1 (es) |
| DE (1) | DE69333113T2 (es) |
| DK (1) | DK0660247T3 (es) |
| ES (1) | ES2206452T3 (es) |
| PT (1) | PT660247E (es) |
Families Citing this family (29)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6336180B1 (en) | 1997-04-30 | 2002-01-01 | Canon Kabushiki Kaisha | Method, apparatus and system for managing virtual memory with virtual-physical mapping |
| US5574661A (en) * | 1994-07-29 | 1996-11-12 | Compcore Multimedia, Inc. | System and method for inverse discrete cosine transform implementation |
| US5636152A (en) * | 1995-04-28 | 1997-06-03 | United Microelectronics Corporation | Two-dimensional inverse discrete cosine transform processor |
| US6421695B1 (en) | 1995-10-28 | 2002-07-16 | Lg Electronics Inc. | Apparatus for implementing inverse discrete cosine transform in digital image processing system |
| JP3547567B2 (ja) * | 1996-08-08 | 2004-07-28 | シャープ株式会社 | 離散コサイン変換器 |
| AUPO648397A0 (en) | 1997-04-30 | 1997-05-22 | Canon Information Systems Research Australia Pty Ltd | Improvements in multiprocessor architecture operation |
| US6507898B1 (en) | 1997-04-30 | 2003-01-14 | Canon Kabushiki Kaisha | Reconfigurable data cache controller |
| US6061749A (en) | 1997-04-30 | 2000-05-09 | Canon Kabushiki Kaisha | Transformation of a first dataword received from a FIFO into an input register and subsequent dataword from the FIFO into a normalized output dataword |
| US6707463B1 (en) | 1997-04-30 | 2004-03-16 | Canon Kabushiki Kaisha | Data normalization technique |
| AUPO647997A0 (en) | 1997-04-30 | 1997-05-22 | Canon Information Systems Research Australia Pty Ltd | Memory controller architecture |
| US6414687B1 (en) | 1997-04-30 | 2002-07-02 | Canon Kabushiki Kaisha | Register setting-micro programming system |
| US6141456A (en) * | 1997-12-31 | 2000-10-31 | Hitachi America, Ltd. | Methods and apparatus for combining downsampling and inverse discrete cosine transform operations |
| JP3547971B2 (ja) * | 1998-01-30 | 2004-07-28 | 三洋電機株式会社 | 離散コサイン変換回路及びその動作方法 |
| JP3547972B2 (ja) * | 1998-01-30 | 2004-07-28 | 三洋電機株式会社 | 離散コサイン変換回路 |
| KR100270799B1 (ko) * | 1998-01-30 | 2000-11-01 | 김영환 | 이산코사인변환/역이산코사인변환 프로세서 |
| JP3524747B2 (ja) * | 1998-01-30 | 2004-05-10 | 三洋電機株式会社 | 離散コサイン変換回路 |
| US6401189B1 (en) | 1998-08-05 | 2002-06-04 | Michael J. Corinthios | General base state assignment for optimal massive parallelism |
| US6445829B1 (en) | 1998-09-15 | 2002-09-03 | Winbond Electronics Corp. | Joint cosine transforming and quantizing device and joint inverse quantizing and inverse cosine transforming device |
| US6160920A (en) * | 1998-09-15 | 2000-12-12 | Winbond Electronics Corp. | Cosine transforming and quantizing device, method of reducing multiplication operations in a video compressing apparatus |
| TW398146B (en) | 1998-09-15 | 2000-07-11 | Winbond Electronics Corp | Cosine transformation and quantification device, method for reducing multiplication operations of an image compressing device, inverse quantification and inverse cosine transformation device, and method for reducing multiplication operations of an image |
| US6243730B1 (en) | 1999-05-04 | 2001-06-05 | Sony Electronics, Inc. | Methods and systems for performing short integer chen IDCT algorithm with fused multiply/add |
| JP3934290B2 (ja) * | 1999-09-30 | 2007-06-20 | 株式会社東芝 | 離散コサイン変換処理装置、逆離散コサイン変換処理装置及び離散コサイン変換処理装置・逆離散コサイン変換処理装置 |
| US7292730B1 (en) * | 1999-12-09 | 2007-11-06 | Intel Corporation | Two-dimensional inverse discrete cosine transforming |
| US7123655B2 (en) | 2001-08-09 | 2006-10-17 | Sharp Laboratories Of America, Inc. | Method for reduced bit-depth quantization |
| US7792891B2 (en) * | 2002-12-11 | 2010-09-07 | Nvidia Corporation | Forward discrete cosine transform engine |
| US8423597B1 (en) | 2003-08-29 | 2013-04-16 | Nvidia Corporation | Method and system for adaptive matrix trimming in an inverse discrete cosine transform (IDCT) operation |
| JP4704333B2 (ja) * | 2004-06-08 | 2011-06-15 | パナソニック株式会社 | 画像符号化装置および画像復号化装置、ならびにそれらで用いられる集積回路 |
| US7539916B2 (en) | 2005-06-28 | 2009-05-26 | Intel Corporation | BIST to provide phase interpolator data and associated methods of operation |
| US9798698B2 (en) | 2012-08-13 | 2017-10-24 | Nvidia Corporation | System and method for multi-color dilu preconditioner |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| FR2581463B1 (fr) * | 1985-05-03 | 1989-09-08 | Thomson Csf | Dispositifs de calcul de transformees cosinus, dispositif de codage et dispositif de decodage d'images comportant de tels dispositifs de calcul |
| FR2608808B1 (fr) * | 1986-12-22 | 1989-04-28 | Efcis | Circuit integre de traitement numerique de signaux |
| US5029122A (en) * | 1988-12-27 | 1991-07-02 | Kabushiki Kaisha Toshiba | Discrete cosine transforming apparatus |
| EP0500048B1 (en) * | 1991-02-19 | 1998-05-27 | Matsushita Electric Industrial Co., Ltd. | Orthogonal transform apparatus for video signal processing |
| US5257213A (en) * | 1991-02-20 | 1993-10-26 | Samsung Electronics Co., Ltd. | Method and circuit for two-dimensional discrete cosine transform |
| US5818742A (en) * | 1991-06-24 | 1998-10-06 | Atmel Corporation | Apparatus to transform time to frequency and frequency to time of data signals |
| US5329318A (en) * | 1993-05-13 | 1994-07-12 | Intel Corporation | Method for optimizing image motion estimation |
-
1993
- 1993-10-27 US US08/143,837 patent/US5471412A/en not_active Expired - Lifetime
- 1993-12-23 ES ES93310487T patent/ES2206452T3/es not_active Expired - Lifetime
- 1993-12-23 DE DE69333113T patent/DE69333113T2/de not_active Expired - Lifetime
- 1993-12-23 EP EP93310487A patent/EP0660247B1/en not_active Expired - Lifetime
- 1993-12-23 AT AT93310487T patent/ATE245838T1/de active
- 1993-12-23 PT PT93310487T patent/PT660247E/pt unknown
- 1993-12-23 DK DK93310487T patent/DK0660247T3/da active
Also Published As
| Publication number | Publication date |
|---|---|
| DE69333113D1 (de) | 2003-08-28 |
| EP0660247B1 (en) | 2003-07-23 |
| EP0660247A1 (en) | 1995-06-28 |
| PT660247E (pt) | 2003-10-31 |
| DK0660247T3 (da) | 2003-11-17 |
| ATE245838T1 (de) | 2003-08-15 |
| US5471412A (en) | 1995-11-28 |
| DE69333113T2 (de) | 2004-01-29 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| ES2206452T3 (es) | Metodo y aparato para realizar la transformacion discreta de coseno y su inversa. | |
| US4821224A (en) | Method and apparatus for processing multi-dimensional data to obtain a Fourier transform | |
| Madisetti et al. | A 100 MHz 2-D 8/spl times/8 DCT/IDCT processor for HDTV applications | |
| US6073154A (en) | Computing multidimensional DFTs in FPGA | |
| US5181183A (en) | Discrete cosine transform circuit suitable for integrated circuit implementation | |
| US5226171A (en) | Parallel vector processing system for individual and broadcast distribution of operands and control information | |
| US5081573A (en) | Parallel processing system | |
| JP2744526B2 (ja) | 準１６基数プロセッサおよび方法 | |
| US4601006A (en) | Architecture for two dimensional fast fourier transform | |
| US6189021B1 (en) | Method for forming two-dimensional discrete cosine transform and its inverse involving a reduced number of multiplication operations | |
| US5297070A (en) | Transform processing circuit | |
| US7461114B2 (en) | Fourier transform apparatus | |
| JPH08235159A (ja) | 逆コサイン変換装置 | |
| KR100708270B1 (ko) | 계산효율적인 수학 엔진 | |
| JPS63167967A (ja) | ディジタル信号処理集積回路 | |
| EP0710915A1 (en) | Fast fourier transform dedicated processor | |
| US4764974A (en) | Apparatus and method for processing an image | |
| JPH08137832A (ja) | バタフライ演算回路および同回路を用いた高速フーリエ変換装置 | |
| US6460061B1 (en) | 2-dimensional discrete cosine transform using a polynomial transform | |
| EP0913778A1 (en) | A commutator circuit | |
| US6438568B1 (en) | Method and apparatus for optimizing conversion of input data to output data | |
| Hsu | LINC: The link and interconnection chip | |
| JP4248027B2 (ja) | データ要素の系列を変換する装置 | |
| KR100189195B1 (ko) | 단일화된 시스톨릭어레이 구조에 의한 2차원 dct/dst/dht의 수행장치 | |
| US6944640B2 (en) | Progressive two-dimensional (2D) pyramid filter |