ES2566917T3

ES2566917T3 - Esquema de codificación y descodificación por entropía

Info

Publication number: ES2566917T3
Application number: ES14160511.3T
Authority: ES
Inventors: Detlev Marpe; Tung Nguyen; Heiko Schwarz; Thomas Wiegand
Original assignee: GE Video Compression LLC
Current assignee: GE Video Compression LLC
Priority date: 2011-01-14
Filing date: 2012-01-12
Publication date: 2016-04-18
Anticipated expiration: 2032-01-12
Also published as: HUE037749T2; EP3644516A1; US20130300591A1; JP2020099077A; PT3349360T; KR102393305B1; TWI640169B; US10826524B2; EP2768144A3; US20180019762A1; KR102095172B1; JP2021100266A; US20160308555A1; HK1202000A1; KR102438562B1; TW202315401A; CN107196662B; TW201624928A; TWI753434B; HUE027907T2

Abstract

Aparato de codificacion por entropia que comprende una unidad de descomposicion (136) que esta configurada para convertir una secuencia (138) de elementos de sintaxis que tienen un intervalo de valores el cual esta subdividido en una secuencia de N particiones (1401-3) en una secuencia (106) de simbolos de origen (106) mediante la descomposicion de forma individual de por lo menos un subgrupo de los elementos de sintaxis en un numero respectivo n de simbolos de origen si con i >= 1 ... n, el numero respectivo n de simbolos de origen dependiendo de en cual de la secuencia de N particiones (1401-3) cae un valor z de los elementos de sintaxis respectivos, de tal modo que una suma de valores del numero respectivo de simbolos de origen si da z, y, si n > 1, para todo i >= 1 ... n-1, el valor de si se corresponde con un intervalo de la i-esima particion; un subdivisor (100) que esta configurado para subdividir la secuencia (106) de simbolos de origen en una primera subsecuencia (108) de simbolos de origen y una segunda subsecuencia (110) de simbolos de origen de tal modo que todos los simbolos de origen sx con x siendo miembro de un primer subconjunto de {1 ... N} estan contenidos dentro de la primera subsecuencia (108) y todos los simbolos de origen sy con y siendo miembro de un segundo subconjunto de {1 ... N} que es disjunto con respecto al primer subconjunto, estan contenidos dentro de la segunda subsecuencia (110); un codificador de VLC (102) que esta configurado para codificar por simbolos los simbolos de origen de la primera subsecuencia (108); y un codificador aritmetico (104) que esta codificado para codificar la segunda subsecuencia (110) de simbolos de origen, caracterizado por que los valores z del subgrupo de los elementos de sintaxis son valores absolutos, y en el que la unidad de descomposicion esta configurada para adaptar uno o mas de los limites entre las particiones de acuerdo con unos simbolos de origen previamente codificados.

Description

5

10

15

20

25

30

35

40

45

50

55

60

Esquema de codificacion y descodificacion por entrc^a DESCRIPCION

La presente invencion se refiere a una codificacion y descodificacion por entropfa y se puede usar en aplicaciones tales como, por ejemplo, compresion de v^deo y de audio.

La codificacion por entropfa, en general, se puede considerar como la forma mas generica de compresion de datos sin perdida. La compresion sin perdida tiene por objeto representar unos datos discretos con menos bits de los necesarios para la representacion de datos original pero sin perdida alguna de informacion. Los datos discretos se pueden dar en forma de texto, graficos, imagenes, video, audio, habla, fax, datos medicos, datos meteorologicos, datos financieros, o cualquier otra forma de datos digitales.

En la codificacion por entropfa, se descuidan las caractensticas de alto nivel espedficas del origen de datos discretos subyacente a menudo. En consecuencia, se considera que cualquier origen de datos se da como una secuencia de sfmbolos de origen que adopta valores en un alfabeto m-ario dado y que se caracteriza por una distribucion de probabilidad (discreta) correspondiente {pi, ... , pm}. En estos escenarios abstractos, el lfmite inferior de cualquier metodo de codificacion por entropfa en terminos de la longitud de palabra de codigo esperada en bits por sfmbolos viene dado por la entropfa

m

^ = ~Y,pi\og2pi. (Al)

M

Los codigos de Huffman y los codigos aritmeticos son ejemplos bien conocidos de codigos practicos capaces de aproximarse al lfmite de entropfa (en un cierto sentido). Para una distribucion de probabilidad fija, los codigos de Huffman son relativamente sencillos de construir. La propiedad mas atractiva de los codigos de Huffman es que su implementacion puede ser realizada de forma eficiente mediante el uso de tablas de codigos de longitud variable (VLC, variable length code). No obstante, cuando se abordan unas estadfsticas de origen variables en el tiempo, es decir, unas probabilidades de sfmbolo cambiantes, la adaptacion del codigo de Huffman y sus tablas de VLC correspondientes es bastante exigente, tanto en terminos de la complejidad algontmica asf como en terminos de los costes de implementacion. Asimismo, en el caso de tener un valor de alfabeto dominante con pk > 0,5, la redundancia del codigo de Huffman correspondiente (sin usar ampliacion de alfabeto alguna tal como la codificacion de longitud de series) puede ser bastante sustancial. Otra deficiencia de los codigos de Huffman viene dada por el hecho de que en el caso de tratar con un modelado de probabilidad de orden superior, se pueden requerir multiples conjuntos de tablas de VLC. La codificacion aritmetica, por otro lado, a pesar de ser sustancialmente mas compleja que VLC, ofrece la ventaja de una manipulacion mas consistente y adecuada cuando se hace frente a un modelado de probabilidad adaptativo y de orden superior asf como con el caso de unas distribuciones de probabilidad muy sesgadas. En la practica, esta caractenstica basicamente resulta del hecho de que la codificacion aritmetica proporciona un mecanismo, por lo menos conceptualmente, para poner en correspondencia cualquier valor dado de estimada de probabilidad de una forma mas o menos directa con una porcion de la palabra de codigo resultante. Estando provista con una interconexion de este tipo, la codificacion aritmetica permite una separacion limpia entre las tareas de modelado de probabilidad y de estimacion de probabilidad, por un lado, y la codificacion por entropfa real, es decir, la puesta en correspondencia de unos sfmbolos con palabras de codigo, por otro lado.

Una alternativa a la codificacion aritmetica y la codificacion de VLC es la codificacion de PIPE. Para ser mas precisos, en la codificacion de PIPE, el intervalo unitario se subdivide en particiones para dar un pequeno conjunto de intervalos de probabilidad disjuntos para canalizar el procesamiento de codificacion a lo largo de las estimadas de probabilidad de variables de sfmbolo aleatorias. De acuerdo con esta subdivision en particiones, una secuencia de entrada de sfmbolos de origen discretos con tamanos de alfabeto arbitrarios se puede poner en correspondencia con una secuencia de sfmbolos alfabeticos y cada uno de los sfmbolos alfabeticos se asigna a un intervalo de probabilidad particular que es, a su vez, codificado por un proceso de codificacion por entropfa especialmente dedicado. Con cada uno de los intervalos estando representado por una probabilidad fija, el proceso de codificacion de entropfa de subdivision en particiones de intervalos de probabilidad (PIPE, probability interval partitioning entropy) se puede basar en el diseno y la aplicacion de codigos de longitud de variable a variable. El modelado de probabilidad puede o bien ser fijo o bien ser adaptativo. No obstante, a pesar de que la codificacion de PIPE es significativamente menos compleja que la codificacion aritmetica, esta sigue teniendo una complejidad mas alta que la codificacion de VLC.

Por lo tanto, sena favorable tener a mano un esquema de codificacion por entropfa el cual posibilite lograr una mejor compensacion redproca entre la complejidad de codificacion por un lado y la eficiencia de compresion por otro lado, incluso cuando se compara con la codificacion de PIPE la cual ya combina ventajas tanto de la codificacion aritmetica como de la codificacion de VLC.

5

10

15

20

25

30

35

40

45

50

55

60

Ademas, en general, sena favorable tener a mano un esquema de codificacion por entropfa el cual posibilite lograr una mejor eficiencia de compresion de por sf, con una complejidad de codificacion moderada.

El documento WO 2008/129021 A2 se refiere a la compresion escalonable de secuencias de estructura reticular en 3D temporalmente consistentes. En lo que respecta a la cuantificacion y la codificacion por entropfa, el documento describe que los errores de prediccion de los vectores de estructura reticular se comprimen componente a componente. En particular, las componentes se ponen en correspondencia con la cantidad de numeros enteros, es decir con signo, y un maximo para la cantidad, es decir imax, se usa para definir un intervalo dentro de la cantidad de numeros enteros para el cual las componentes que caen dentro de este intervalo se codifican por entropfa. La cantidad residual, es decir la distancia al extremo mas cercano del intervalo, se codifica mediante el uso de codigos de Golomb.

Un objeto de la presente invencion es la provision de un concepto de codificacion por entropfa el cual satisface la demanda que se ha identificado en lo que antecede, es decir permite conseguir una mejor compensacion redproca entre la complejidad de codificacion por un lado y la eficiencia de compresion por otro lado.

Este objeto se logra mediante la materia objeto de las reivindicaciones independientes.

La presente invencion se basa en la idea de que la descomposicion de un intervalo de valores de los elementos de sintaxis respectivos en una secuencia de n particiones con codificacion de las componentes de los valores de elemento de sintaxis z encontrandose dentro de las particiones respectivas por separado con por lo menos una mediante codificacion de VLC y con por lo menos una mediante codificacion aritmetica. Por consiguiente, de acuerdo con realizaciones de la presente invencion, elementos de sintaxis se descomponen en un numero respectivo n de sfmbolos de origen si con i = 1 ... n, el numero respectivo n de sfmbolos de origen dependiendo de en cual de una secuencia de n particiones (140i-3) en las cuales esta subdividido un intervalo de valores de los elementos de sintaxis respectivos, cae un valor z de los elementos de sintaxis respectivos, de tal modo que una suma de valores del numero respectivo de sfmbolos de origen si da z, y, si n > 1, para todo i = 1 ... n-1, el valor de si se corresponde con un intervalo de la i-esima particion.

Aspectos preferidos de la presente invencion son el objeto de las reivindicaciones dependientes incluidas.

Realizaciones preferidas de la presente invencion se describen en lo sucesivo con respecto a las figuras. Estas realizaciones representan ejemplos, en la medida en la que estas no usen codificacion aritmetica junto a la codificacion de VLC. Entre las figuras,

la figura la muestra un diagrama de bloques de un aparato de codificacion por entropfa;

la figura 1b muestra un diagrama esquematico que ilustra una posible descomposicion de elementos de sintaxis

en sfmbolos de origen;

la figura 1c muestra un diagrama de flujo que ilustra un posible modo de funcionamiento de la unidad de descomposicion de la figura la en la descomposicion de elementos de sintaxis en sfmbolos de origen;

la figura 2a muestra un diagrama de bloques de un aparato de descodificacion por entropfa;

la figura 2b

muestra un diagrama de flujo que ilustra un posible modo de funcionamiento de la unidad de composicion de la figura 2a en la composicion de elementos de sintaxis a partir de sfmbolos de origen;

la figura 3 muestra un diagrama de bloques de un codificador de PIPE de acuerdo con una realizacion de comparacion el cual se puede usar en la figura 1;

la figura 4 muestra un diagrama de bloques de un descodificador de PIPE adecuado para descodificar un tren de bits generado por el codificador de PIPE de la figura 3, de acuerdo con una realizacion de comparacion, el cual se puede usar en la figura 2;

la figura 5

muestra un diagrama esquematico que ilustra un paquete de datos con trenes de bits parciales multiplexados;

la figura 6 muestra un diagrama esquematico que ilustra un paquete de datos con una segmentacion alternativa que usa unos segmentos de tamano fijo;

la figura 7 muestra un diagrama de bloques de un codificador de PIPE usando una intercalacion de trenes de bits parciales;

la figura 8

muestra un diagrama esquematico que ilustra ejemplos para el estatus de una memoria intermedia de

5

10

15

20

25

30

35

40

45

50

55

60

la figura 9 la figura 10

la figura 11

la figura 12

la figura 13

la figura 14

la figura 15

la figura 16

la figura 17

la figura 18

palabras de codigo en el lado de codificador de la figura 7;

muestra un diagrama de bloques de un descodificador de PIPE que usa una intercalacion de trenes de bits parciales;

muestra un diagrama de bloques de un descodificador de PIPE usando una intercalacion de palabras de codigo que usa un unico conjunto de palabras de codigo;

muestra un diagrama de bloques de un codificador de PIPE usando una intercalacion de secuencias de bits de longitud fija;

muestra un diagrama esquematico que ilustra ejemplos para el estatus de una memoria intermedia de bits global en el lado de codificador de la figura 11;

muestra un diagrama de bloques de un descodificador de PIPE usando una intercalacion de secuencias de bits de longitud fija;

muestra una grafica para ilustrar una discretizacion de intervalo de probabilidad optima en K = 4 intervalos suponiendo una distribucion de probabilidad uniforme en (0, 0,5];

muestra un diagrama esquematico que ilustra un arbol de eventos binarios para una probabilidad de LPB de p = 0,38 y un codigo de longitud variable asociado obtenido mediante el algoritmo de Huffman;

muestra una grafica a partir de la cual se puede reunir el aumento relativo de tasa de bits p(p, C) para unos codigos optimos C dado un numero maximo de entradas de tabla Lm;

muestra una grafica que ilustra el aumento de tasa para la subdivision en particiones de intervalos de probabilidad teoricamente optima en K = 12 intervalos y un diseno real con codigos de V2V con un numero maximo de Lm = 65 entradas de tabla;

muestra un diagrama esquematico que ilustra un ejemplo para la conversion de un arbol de eleccion ternario en un arbol de eleccion binario completo;

la figura 19 muestra un diagrama de bloques de un sistema que comprende un codificador (parte izquierda) y un descodificador (parte derecha);

la figura 20 muestra un diagrama de bloques de un aparato de codificacion por entropfa;

la figura 21 muestra un diagrama de bloques de un aparato de descodificacion por entropfa;

la figura 22 muestra un diagrama de bloques de un aparato de codificacion por entropfa;

la figura 23 muestra un diagrama esquematico que ilustra ejemplos para el estatus de una memoria intermedia de

bits global en el lado de codificador de la figura 22;

la figura 24 muestra un diagrama de bloques de un aparato de descodificacion por entropfa.

Antes de que se describan varias realizaciones de la presente solicitud en lo sucesivo con respecto a las figuras, se hace notar que se usan signos de referencia iguales por la totalidad de las figuras con el fin de indicar unos elementos iguales o equivalentes en estas figuras, y la descripcion de estos elementos presentada con cualquiera de las figuras previas tambien sera de aplicacion a cualquiera de las siguientes figuras siempre que la descripcion anterior no entre en conflicto con la descripcion de las figuras actuales.

La figura 1a muestra un aparato de codificacion por entropfa. El aparato comprende un subdivisor 100, un codificador de VLC 102 y un codificador de PIPE 104.

El subdivisor 100 esta configurado para subdividir una secuencia de sfmbolos de origen 106 en una primera subsecuencia 108 de sfmbolos de origen y una segunda subsecuencia 110 de sfmbolos de origen. El codificador de VLC 102 tiene una entrada del mismo que esta conectada con una primera salida del subdivisor 100 y esta configurado para convertir por sfmbolos los sfmbolos de origen de la primera subsecuencia 108 en unas palabras de codigo formando un primer tren de bits 112. El codificador de VLC 102 puede comprender una tabla de consulta y usar, de forma individual, los sfmbolos de origen como un mdice con el fin de consulta, por sfmbolos de origen, una palabra de codigo respectiva en la tabla de consulta. El codificador de VLC emite esta ultima palabra de codigo, y prosigue con el siguiente sfmbolo de origen en la subsecuencia 110 con el fin de emitir una secuencia de palabras de codigo en la que cada palabra de codigo esta asociada con exactamente uno de los sfmbolos de origen dentro de

5

10

15

20

25

30

35

40

45

50

55

60

la subsecuencia 110. Las palabras de codigo pueden tener diferentes longitudes y se pueden definir de tal modo que ninguna palabra de codigo forma un prefijo con cualquiera de las otras palabras de codigo. Adicionalmente, la tabla de consulta puede ser estatica.

El codificador de PIPE 104 tiene una entrada del mismo que esta conectada con una segunda salida del subdivisor 100 y esta configurado para codificar la segunda subsecuencia 110 de sfmbolos de origen, que se representa en la forma de una secuencia de sfmbolos alfabeticos, y comprende una unidad de asignacion 114 que esta configurada para asignar una medida para una estimada de una distribucion de probabilidad entre los posibles valores que pueden asumir los sfmboios alfabeticos respectivos, a cada sfmbolo alfabetico de la secuencia de sfmbolos alfabeticos sobre la base de la informacion contenida dentro de sfmbolos alfabeticos previos de la secuencia de sfmbolos alfabeticos, una pluralidad de codificadores por entropfa 116 cada uno de los cuales esta configurado para convertir los sfmbolos alfabeticos reenviados al codificador por entropfa respectivo en un segundo tren de bits 118 respectivo, y un selector 120 que esta configurado para reenviar cada sfmbolo alfabetico de la segunda subsecuencia 110 a uno seleccionado de la pluralidad de codificadores por entropfa 116, dependiendo la seleccion de la medida que se ha mencionado en lo que antecede para la estimada de la distribucion de probabilidad asignada al sfmbolo alfabetico respectivo. La asociacion entre sfmbolos de origen y sfmbolos alfabeticos puede ser de tal modo que cada sfmbolo alfabetico se asocia de forma unica con exactamente un sfmbolo de origen de la subsecuencia 110 con el fin de representar, junto con sfmbolos alfabeticos posiblemente adicionales de la secuencia de sfmbolos alfabeticos los cuales pueden seguir inmediatamente unos a otros, este mismo sfmbolo de origen.

Tal como se describe con mas detalle en lo sucesivo, la secuencia 106 de sfmbolos de origen puede ser una secuencia de elementos de sintaxis de un tren de bits que se puede analizar sintacticamente. El tren de bits que se puede analizar sintacticamente puede representar, por ejemplo, contenido de video y / o de audio de una forma escalonable o no escalonable con los elementos de sintaxis representando, por ejemplo, niveles de coeficiente de transformada, vectores de movimiento, indices de referencia de imagenes de movimiento, factores de escala, valores de energfa de envolvente de audio o similares. Los elementos de sintaxis pueden, en particular, ser de diferente tipo o categona con elementos de sintaxis del mismo tipo, por ejemplo, teniendo el mismo significado dentro del tren de bits que se puede analizar sintacticamente pero con respecto a diferentes porciones del mismo, tal como diferentes imagenes, diferentes macrobloques, diferentes componentes espectrales o similares, mientras que elementos de sintaxis de diferente tipo pueden tener un significado diferente dentro del tren de bits, tal como un vector de movimiento tiene un significado diferente al de un elemento de sintaxis que representa un nivel de coeficiente de transformada que representa el residuo de prediccion de movimiento.

El subdivisor 100 se puede configurar para realizar la subdivision dependiendo del tipo de los elementos de sintaxis. Es decir, el subdivisor 100 puede reenviar elementos de sintaxis de un primer grupo de tipos a la primera subsecuencia 108 y reenviar elementos de sintaxis de un segundo grupo de tipos distinto del primer grupo, a la segunda subsecuencia 110. La subdivision que es realizada por el subdivisor 100 se puede disenar de tal modo que las estadfsticas de sfmbolos de los elementos de sintaxis dentro de la subsecuencia 108 son adecuadas para someterse a codificacion de VLC por el codificador de VLC 102, es decir da como resultado, de hecho, casi una minima entropfa posible a pesar del uso de la codificacion de VLC y su restriccion con respecto a su idoneidad para determinadas estadfsticas de sfmbolos tal como se bosqueja en la porcion introductoria de la memoria descriptiva de la presente solicitud. Por otro lado, el subdivisor 100 puede reenviar todos los otros elementos de sintaxis a la segunda subsecuencia 110 de tal modo que estos elementos de sintaxis que tienen unas estadfsticas de sfmbolos que no son adecuadas para la codificacion de VLC, son codificados por el codificador de PIPE mas complejo, pero mas eficiente - en terminos de la relacion de compresion - 104.

Tal como es tambien el caso con el mayor detalle con respecto a las siguientes figuras, el codificador de PIPE 104 puede comprender un simbolizador 122 que esta configurado para poner en correspondencia de forma individual cada elemento de sintaxis de la segunda subsecuencia 110 con una secuencia parcial respectiva de sfmbolos alfabeticos, formando en conjunto la secuencia 124 que se ha mencionado en lo que antecede de sfmbolos alfabeticos. Dicho de otra forma, el simbolizador 122 puede no estar presente si, por ejemplo, los sfmbolos de origen de la subsecuencia 110 ya estan representados como secuencias parciales respectivas de sfmbolos alfabeticos. El simbolizador 122 es, por ejemplo, ventajoso en el caso de que los sfmbolos de origen dentro de la subsecuencia 110 sean de diferentes alfabetos y, en especial, alfabetos que tienen diferentes numeros de sfmbolos alfabeticos posibles. En concreto, en este caso, el simbolizador 122 puede armonizar los alfabetos de los sfmbolos que llegan al interior del subtren 110. El simbolizador 122 se puede realizar, por ejemplo, como una unidad de binarizacion que esta configurada para binarizar los sfmbolos que llegan dentro de la subsecuencia 110.

Tal como se ha mencionado antes, los elementos de sintaxis pueden ser de diferente tipo. Esto tambien puede ser cierto para los elementos de sintaxis en el interior del subtren 110. Entonces, el simbolizador 122 se puede configurar para realizar la puesta en correspondencia individual de los elementos de sintaxis de la subsecuencia 110 usando un esquema de puesta en correspondencia de simbolizacion, tal como un esquema de binarizacion, diferente para elementos de sintaxis de diferente tipo. En la siguiente descripcion se presentan ejemplos para esquemas de binarizacion espedficos, tal como un esquema de binarizacion unaria, un esquema de binarizacion de

5

10

15

20

25

30

35

40

45

50

55

60

Golomb Exponencial de orden 0 o de orden 1, por ejemplo, o un esquema de binarizacion unaria truncada, un esquema de binarizacion de orden 0 de Golomb Exponencial truncada y reordenada o un esquema de binarizacion no sistematica.

Por consiguiente, los codificadores por entropfa 116 se podnan configurar para operar sobre un alfabeto binario. Por ultimo, se debena hacer notar que el simbolizador 122 se puede considerar como que es parte del codificador de PIPE 104 en sf tal como se muestra en la figura 1a. Como alternativa, no obstante, la unidad de binarizacion se puede considerar como que es externa con respecto al codificador de PIPE.

De forma similar a lo que se ha hecho indicado anteriormente, se debena hacer notar que la unidad de asignacion 114, a pesar de que se muestra que esta conectado en serie entre el simbolizador 122 y el selector 120, como alternativa se puede considerar como que esta conectada entre una salida del simbolizador 124 y una primera entrada del selector 120, con una salida de la unidad de asignacion 114 estando conectada con otra entrada del selector 120 tal como se describe posteriormente con respecto a la figura 3. En efecto, la unidad de asignacion 114 acompana cada sfmbolo alfabetico con la medida que se ha mencionado en lo que antecede para una estimacion de la distribucion de probabilidad.

En lo que respecta a la salida del aparato de codificacion por entropfa de la figura 1a, la misma esta compuesta por el primer tren de bits 112 que es emitido por el codificador de VLC 102 y la pluralidad de segundos trenes de bits 118 que son emitidos por la pluralidad de codificadores por entropfa 116. Tal como se describe adicionalmente en lo sucesivo, la totalidad de estos trenes de bits se pueden transmitir en paralelo. Como alternativa, los mismos se pueden intercalar para dar un tren de bits comun 126 mediante el uso de un intercalador 128. Las figuras 22 a 24 muestran ejemplos con tal intercalacion de trenes de bits. Tal como se muestra adicionalmente en la figura 1, el codificador de PIPE 104 en sf puede comprender su propio intercalador 130 con el fin de intercalar la pluralidad de segundos trenes de bits 118 en un tren de bits codificado de PIPE comun 132. A partir de la descripcion de las figuras 5 a 13 se pueden obtener posibilidades para tal intercalador 130. El tren de bits 132 y el tren de bits 112 pueden representar, en una configuracion en paralelo, la salida del aparato de codificacion por entropfa de la figura 1a. Como alternativa, otro intercalador 134 puede intercalar ambos trenes de bits, caso en el cual, el intercalador 130 y 134 formana dos fases de un intercalador de dos fases 128.

Tal como se ha descrito en lo que antecede, el subdivisor 100 puede realizar la subdivision por elementos de sintaxis, es decir los sfmbolos de origen sobre los que opera el subdivisor 100 pueden ser elementos de sintaxis completos o, hablando de forma alternativa, el subdivisor 100 puede operar en unidades de elementos de sintaxis.

No obstante, el aparato de codificacion por entropfa de la figura 1a puede comprender la unidad de descomposicion 136 con el fin de descomponer elementos de sintaxis dentro de un tren de bits que se puede analizar sintacticamente 138 de forma individual en uno o mas de los sfmbolos de origen de la secuencia de sfmbolos de origen 106 que entran en el subdivisor 100. En particular, la unidad de descomposicion 136 se puede configurar para convertir la secuencia 138 de elementos de sintaxis en la secuencia 106 de sfmbolos de origen mediante la descomposicion de forma individual de cada elemento de sintaxis en un numero entero respectivo de sfmbolos de origen. El numero entero puede variar entre los elementos de sintaxis. En particular, algunos de los elementos de sintaxis incluso pueden ser dejados sin cambios por la unidad de descomposicion 136, mientras que otros elementos de sintaxis se descomponen en exactamente dos, o por lo menos dos, sfmbolos de origen. El subdivisor 100 se puede configurar para reenviar uno de los sfmbolos de origen de tales elementos de sintaxis descompuestos a la primera subsecuencia 108 de sfmbolos de origen y otro de los sfmbolos de origen del mismo elemento de sintaxis descompuesto a la segunda subsecuencia 110 de sfmbolos de origen. Tal como se ha mencionado en lo que antecede, los elementos de sintaxis en el interior del tren de bits 138 pueden ser de diferente tipo, y la unidad de descomposicion 136 se puede configurar para realizar la descomposicion individual dependiendo del tipo del elemento de sintaxis. La unidad de descomposicion 136 preferiblemente realiza la descomposicion individual de los elementos de sintaxis de tal modo que existe una puesta en correspondencia inversa unica previamente determinada que se usa mas adelante en el lado de descodificacion, a partir del numero entero de sfmbolos de origen hasta el elemento de sintaxis respectivo, comun para todos los elementos de sintaxis.

Por ejemplo, la unidad de descomposicion 136 se puede configurar para descomponer los elementos de sintaxis z en el tren de bits que se puede analizar sintacticamente 138, en dos sfmbolos de origen x e y de tal modo que z = x + y, z = xy, o z = x : y. Mediante esta medida, el subdivisor 100 puede descomponer los elementos de sintaxis en dos componentes, en concreto los sfmbolos de origen del tren de sfmbolos de origen 106, uno de los cuales es adecuado para someterse a codificacion de VLC en terminos de la eficiencia de compresion, tal como x, y el otro de los cuales no es adecuado para la codificacion de VLC y se pasa, por lo tanto, al segundo subtren 110 en lugar del primer subtren 108, tal como y. No es necesario que la descomposicion usada por la unidad de descomposicion 136 sea biyectiva. No obstante, tal como se ha mencionado antes, debena existir una puesta en correspondencia inversa que permita una unica recuperacion de los elementos de sintaxis de las posibles descomposiciones entre las cuales puede elegir la unidad de descomposicion 136 si la descomposicion no es biyectiva.

Hasta la fecha, se han descrito diferentes posibilidades para la manipulacion de diferentes elementos de sintaxis. En

5

10

15

20

25

30

35

40

45

50

55

60

lo que respecta a si existen tales elementos de sintaxis o casos, es opcional. La descripcion adicional, no obstante, se centra en los elementos de sintaxis que se descomponen por la unidad de descomposicion 136 de acuerdo con el siguiente principio.

Tal como se muestra en la figura 1b, la unidad de descomposicion 136 esta configurada para descomponer determinados elementos de sintaxis z en el tren de bits que se puede analizar sintacticamente 138 en fases. Pueden existir dos o mas fases. Las fases son para dividir el intervalo de valores de elemento de sintaxis z en dos o mas subintervalos o subrangos adyacentes tal como se muestra en la figura 1c. El intervalo de valores de elemento de sintaxis puede tener dos puntos de extremo infinitos, meramente uno o puede tener unos puntos de extremo definidos. En la figura 1c, el intervalo de valores de elemento de sintaxis se subdivide a modo de ejemplo en tres particiones 14O1-3. Tal como se muestra en la figura 1b, si el elemento de sintaxis es mayor o igual que el lfmite 142 de la primera particion 1401, es decir el lfmite superior que separa las particiones 1401 y 1402, entonces al elemento de sintaxis se le sustrae el lfmite lfmite1 de la primera particion 1401 y z se comprueba de nuevo en lo que respecta a si la misma es incluso mayor o igual que el lfmite 144 de la segunda particion 1402, es decir el lfmite superior que separa las particiones 1402 y 1403. Si z' es mayor o igual que el lfmite 144, entonces a z' se le sustrae el lfmite lfmite2 de la segunda particion 1402 lo que da como resultado z”. En el primer caso en el que z es mas pequeno que lfmite1, el elemento de sintaxis z se envfa al subdivisor 100 en lenguaje claro. En el caso de que z se encuentre entre el lfmite1 y el lfmite2, el elemento de sintaxis z se envfa al subdivisor 100 en como una tupla (lfmite1, z') con z = lfmite1 + z', y en el caso de que z se encuentre por encima de lfmite2, el elemento de sintaxis z se envfa al subdivisor 100 en como una tripleta (lfmite1, lfmite2 - lfmite1, z') con z = lfmite1 + lfmite2 + z'. La primera (o la unica) componente, es decir z o lfmite1, forma un primer sfmbolo de origen que va a codificarse por el subdivisor 100, la segunda componente, es decir z' o lfmite2 - lfmite1 forma un segundo sfmbolo de origen que va a codificarse por el subdivisor 100, de encontrarse presente, y la tercera componente, es decir z”, forma un tercer sfmbolo de origen que va a codificarse por el subdivisor 100, de encontrarse presente. Por lo tanto, de acuerdo con la figura 1b y 1c, el elemento de sintaxis se pone en correspondencia con cualquiera de 1 a 3 sfmbolos de origen, pero se pueden obtener facilmente generalizaciones acerca de un numero mas o menos maximo de sfmbolos de origen a partir de la descripcion anterior, y tales alternativas tambien se describiran en lo sucesivo.

En cualquier caso, la totalidad de estas diferentes componentes o sfmbolos de origen resultantes son de acuerdo con las realizaciones posteriores, codificados con alternativas de codificacion de entre las mismas. Por lo menos uno de estos se reenvfa por el subdivisor al codificador de PIPE 104, y por ultimo otro de los mismos se envfa al codificador de VLC 102.

En lo sucesivo se esbozan con mas detalle realizaciones ventajosas particulares.

Despues de haber descrito en lo que antecede un aparato de codificacion por entropfa, un aparato de descodificacion por entropfa se describe con respecto a la figura 2a. El aparato de descodificacion por entropfa de la figura 2a comprende un descodificador de VLC 200 y un descodificador de PIPE 202. El descodificador de VLC 200 esta configurado para reconstruir por codigos los sfmbolos de origen de una primera subsecuencia 204 a partir de palabras de codigo de un primer tren de bits 206. El primer tren de bits 206 es igual a un tren de bits 112 de la figura 1, y lo mismo es de aplicacion a la subsecuencia 204 en lo que respecta a la subsecuencia 108 de la figura 1a. El descodificador de PIPE 202 esta configurado para reconstruir una segunda subsecuencia 208 de sfmbolos de origen, que se representa en la forma de una secuencia de sfmbolos alfabeticos, y comprende una pluralidad de descodificadores por entropfa 210, una unidad de asignacion 212 y un selector 214. La pluralidad de descodificadores por entropfa 210 estan configurados para convertir uno respectivo de los segundos trenes de bits 216 en sfmbolos alfabeticos de la secuencia de sfmbolos alfabeticos. La unidad de asignacion 212 esta configurada para asignar una medida de una estimada de una distribucion de probabilidad entre los posibles valores que pueden asumir los sfmbolos alfabeticos respectivos, a cada sfmbolo alfabetico de la secuencia de sfmbolos alfabeticos que representa la segunda subsecuencia 208 de sfmbolos de origen que se va a reconstruir, sobre la base de la informacion que esta contenida dentro de sfmbolos alfabeticos previamente reconstruidos de la secuencia de sfmbolos alfabeticos. Con este fin, la unidad de asignacion 212 se puede conectar en serie entre una salida del selector 214 y una entrada del mismo, mientras que entradas adicionales del selector 214 tienen salidas de los descodificadores por entropfa 210 conectadas a los mismos de forma respectiva. El selector 214 esta configurado para recuperar cada sfmbolo alfabetico de la secuencia de sfmbolos alfabeticos a partir de uno seleccionado de la pluralidad de descodificadores por entropfa 210, dependiendo la seleccion de la medida asignada al sfmbolo alfabetico respectivo. Dicho de otra forma, el selector 214 junto con la unidad de asignacion 212 es operativo para recuperar los sfmbolos alfabeticos obtenidos mediante los descodificadores por entropfa 210 en un orden entre los descodificadores por entropfa 210 obtenidos mediante informacion de prospeccion contenida dentro de sfmbolos alfabeticos previos de la secuencia de sfmbolos alfabeticos. Dicho incluso de otra forma, la unidad de asignacion 212 y el selector 214 son capaces de reconstruir el orden original de los sfmbolos alfabeticos de sfmbolo alfabetico a sfmbolo alfabetico. Junto con el pronostico del siguiente sfmbolo alfabetico, la unidad de asignacion 212 es capaz de determinar la medida que se ha mencionado en lo que antecede de la estimada de la distribucion de probabilidad para el sfmbolo alfabetico respectivo mediante el uso del cual el selector 214 selecciona entre los descodificadores por entropfa 210 para recuperar el valor real de este sfmbolo alfabetico. Para ser incluso mas precisos, tal como se

5

10

15

20

25

30

35

40

45

50

55

60

describira con mas detalle en lo sucesivo, el descodificador de PIPE 202 se puede configurar para reconstruir la subsecuencia 208 de sfmbolos de origen, que se representa en la forma de la secuencia de sfmbolos alfabeticos, sensible a solicitudes de sfmbolo alfabetico que solicitan de forma secuencial los sfmbolos alfabeticos, y la unidad de asignacion 212 se puede configurar para asignar a cada solicitud para un sfmbolo alfabetico de la secuencia de sfmbolos alfabeticos que representa la segunda subsecuencia (208) de sfmbolos de origen que se va a reconstruir, la medida que se ha mencionado en lo que antecede de una estimada de una distribucion de probabilidad entre los posibles valores que puede asumir el sfmbolo alfabetico respectivo. Por consiguiente, el selector 214 se puede configurar para recuperar, para cada solicitud para un sfmbolo alfabetico de la secuencia de sfmbolos alfabeticos que representa la segunda subsecuencia (208) de sfmbolos de origen que se va a reconstruir, el sfmbolo alfabetico respectivo de la secuencia de sfmbolos alfabeticos a partir de uno seleccionado de la pluralidad de descodificadores por entropfa 210, dependiendo la seleccion de la medida asignada a la solicitud respectiva del sfmbolo alfabetico respectivo. La concordancia entre solicitudes en el lado de descodificacion por un lado, y la codificacion o flujo de datos en el lado de codificacion por otro lado se bosquejara con mas detalle con respecto a la figura 4.

Como la primera subsecuencia 214 de sfmbolos de origen y la segunda subsecuencia 208 de sfmbolos de origen comunmente a partir de una secuencia comun 210 de sfmbolos de origen, el aparato de descodificacion por entropfa de la figura 2a puede comprender de forma opcional un recombinador 220 que esta configurado para recombinar la primera subsecuencia 204 y la segunda subsecuencia 208 para obtener la secuencia comun 218 de sfmbolos de origen. Esta secuencia comun 208 de sfmbolos de origen da una reconstruccion de la secuencia 106 de la figura 1a.

De acuerdo con la descripcion que se ha presentado en lo que antecede con respecto a la figura 1, los sfmbolos de origen de la primera y la segunda subsecuencias 204 y 208 pueden ser elementos de sintaxis de un tren de bits que se puede analizar sintacticamente. En este caso, el recombinador 220 se podna configurar para reconstruir este tren de bits que se puede analizar sintacticamente de la secuencia 218 de elementos de sintaxis mediante la intercalacion de los sfmbolos de origen que llegan por medio de la primera y la segunda subsecuencias 204 y 208 en un orden que es dictado por una cierta regla de analisis sintactico que define un orden entre los elementos de sintaxis. En particular, los elementos de sintaxis pueden ser, tal como se ha descrito en lo que antecede, de diferente tipo y el recombinador 220 se puede configurar para recuperar o solicitar elementos de sintaxis de un primer grupo de tipos a partir del descodificador de VLC 200 por medio del subtren 204, y elementos de sintaxis de un segundo tipo a partir del descodificador de PIPE 202 por medio del subtren 208. Por consiguiente, siempre que la regla de analisis sintactico recien mencionada indique que un elemento de sintaxis de un tipo dentro del primer grupo es el siguiente en lmea, el recombinador 202 inserta un sfmbolo de origen real de la subsecuencia 204 en la secuencia comun 218, y a partir de la subsecuencia 208 de lo contrario.

De forma similar, el descodificador de PIPE 202 podna comprender un desimbolizador 222 conectado entre la salida del selector 214 y una entrada del recombinador 220. De forma similar a la descripcion en lo que antecede con respecto a la figura 1, el desimbolizador 222 se podna considerar como que es externo con respecto al descodificador de PIPE 202 e incluso se podna disponer por detras del recombinador 202, es decir en el lado de salida del recombinador 220, como alternativa. El desimbolizador 222 se podna configurar para volver a establecer una correspondencia, en unidades de secuencias parciales de sfmbolos alfabeticos, de la secuencia de sfmbolos alfabeticos 224 que es emitida por el selector 214 con los sfmbolos de origen, es decir elementos de sintaxis de la subsecuencia 208. De forma similar al recombinador 220, el desimbolizador 222 tiene conocimiento sobre la construccion de secuencias parciales posibles de sfmbolos alfabeticos. En particular, el desimbolizador 222 puede analizar sfmbolos alfabeticos recientemente recibidos a partir del selector 214 con el fin de determinar en lo que respecta a si estos sfmbolos alfabeticos recientemente recibidos dan una secuencia parcial valida de sfmbolos alfabeticos asociados con un valor respectivo del elemento de sintaxis respectivo, o en lo que respecta a si este no es el caso, y que sfmbolo alfabetico es el siguiente que esta ausente. Dicho incluso de otra forma, el simbolizador 222 tiene conocimiento, en cualquier instante, en lo que respecta a si se han de recibir sfmbolos alfabeticos adicionales a partir del selector 214 con el fin de acabar la recepcion de un elemento de sintaxis respectivo o no, y por consiguiente, a que elemento de sintaxis pertenece uno respectivo de los sfmbolos alfabeticos que son emitidos por el selector 214. Con este fin, el desimbolizador 222 puede usar un esquema de puesta en correspondencia de (de)simbolizacion que difiere para elementos de sintaxis de diferente tipo. De forma similar, la unidad de asignacion 212 tiene conocimiento sobre la asociacion de un sfmbolo alfabetico actual que va a recuperarse a partir de cualquiera de los descodificadores por entropfa 210 por el selector 214, hasta uno respectivo de los elementos de sintaxis y puede establecer la medida que se ha mencionado en lo que antecede de estimacion de una distribucion de probabilidad de este sfmbolo alfabetico en consecuencia, es decir dependiendo del tipo de elemento de sintaxis asociado. Lo que es mas, la unidad de asignacion 212 puede diferenciar entre diferentes sfmbolos alfabeticos que pertenecen a la misma secuencia parcial de un sfmbolo alfabetico actual y puede establecer la medida de la estimada de distribucion de probabilidad de forma diferente para estos sfmbolos alfabeticos. En lo sucesivo se describen con mas detalle detalles a este respecto. Tal como se ha descrito en los mismos, la unidad de asignacion 212 se puede configurar para asignar contextos a los sfmbolos alfabeticos. La asignacion puede ser dependiente del tipo de elemento de sintaxis y / o la posicion dentro de la secuencia parcial de sfmbolos alfabeticos del elemento de sintaxis actual. Tan pronto como la unidad de asignacion 212 ha asignado un contexto a un sfmbolo alfabetico actual que va a recuperarse a partir de cualquiera de los descodificadores por entropfa 210 por el selector 214, el sfmbolo

5

10

15

20

25

30

35

40

45

50

55

60

alfabetico puede tener de forma inherente la medida de la estimada de distribucion de probabilidad asociada al mismo debido a que cada contexto tiene su medida de estimada asociada al mismo. Ademas, el contexto - y su medida asociada de la estimada de distribucion de probabilidad - puede adaptarse de acuerdo con las estadfsticas reales de los sfmbolos alfabeticos del contexto respectivo que se ha recuperado a partir de los descodificadores por entropfa 210 hasta el momento. En lo sucesivo se presentan con mas detalle detalles a este respecto.

De forma similar al analisis anterior de la figura 1, puede ser posible que la correspondencia entre los sfmbolos de origen que se han mencionado en lo que antecede de las subsecuencias 204 y 208 en los elementos de sintaxis no sea una correspondencia biumvoca. En su lugar, los elementos de sintaxis se pueden haber descompuesto en un numero entero de sfmbolos de origen con el numero variando, con el tiempo, entre los elementos de sintaxis, pero que es, en cualquier caso, mayor que uno por lo menos para un elemento de sintaxis. Tal como se ha hecho notar en lo que antecede, la siguiente descripcion se centra en la manipulacion de estos tipos de elementos de sintaxis, e incluso puede que no se encuentren presentes elementos de sintaxis de otros tipos.

Para manipular los elementos de sintaxis recien mencionados, el aparato de descodificacion por entropfa de la figura 2a puede comprender una unidad de composicion 224 que esta configurada para volver a hacer la descomposicion que es realizada por la unidad de descomposicion 136 de la figura 1a. En particular, la unidad de composicion 224 se puede configurar para componer la secuencia 226 de elementos de sintaxis a partir de los sfmbolos de origen de la secuencia 218 o, si el recombinador 220 esta ausente, las subsecuencias 204 y 208, mediante la composicion de forma individual de cada elemento de sintaxis a partir de un numero entero respectivo de sfmbolos de origen con uno de los sfmbolos de origen del numero entero de sfmbolos de origen que pertenecen a la primera subsecuencia 204 y otro de los sfmbolos de origen del numero entero de sfmbolos de origen del mismo elemento de sintaxis que pertenece a la segunda subsecuencia 208. Mediante esta medida, determinados elementos de sintaxis se pueden haber descompuesto en el lado de codificador con el fin de separar componentes adecuadas para la descodificacion de VLC a partir de una componente restante que tienen que pasarse a traves de la trayectoria de descodificacion de

PIPE. De forma similar al analisis anterior, el elemento de sintaxis puede ser de diferente tipo y la unidad de

composicion 224 se puede configurar para realizar la composicion individual dependiendo del tipo de los elementos de sintaxis. En particular, la unidad de composicion 224 se puede configurar para obtener los elementos de sintaxis respectivos al combinar de forma logica o matematica el numero entero de sfmbolos de origen del elemento de sintaxis respectivo. Por ejemplo, la unidad de composicion 224 puede configurarse, para cada elemento de sintaxis, para aplicar +, -, : o ■ a un primer y un segundo sfmbolos de origen de un elemento de sintaxis.

Tal como se ha descrito en lo que antecede, las realizaciones que se describen en lo sucesivo en el presente

documento, no obstante, se centran en elementos de sintaxis que se descomponen por la unidad de

descomposicion 136 de acuerdo con la figura 1b y 1c y las alternativas que se describen en lo que respecta a las mismas. La figura 2a muestra lo que respecta a como puede funcionar la unidad de composicion 224 para reconstruir estos elementos de sintaxis a partir de sus sfmbolos de origen 218.

Tal como se muestra en la figura 2b, la unidad de composicion 224 esta configurada para componer tales elementos de sintaxis z en fases a partir de unos sfmbolos de origen entrantes s1 a sx con x siendo cualquiera de 1 a 3 en el presente ejemplo. Pueden existir dos o mas fases. Tal como se muestra en la figura 2b, la unidad de composicion 224 establece preliminarmente que z es el primer sfmbolo s1 y comprueba en lo que respecta a si z es igual al primer Kmite1. Si este no es el caso, se ha hallado z. De lo contrario, la unidad de composicion 224 anade el siguiente sfmbolo de origen s2 del tren de sfmbolos de origen 218 a z y comprueba de nuevo en lo que respecta a si esta z es igual al lfmite2. De no ser asf, se ha hallado z. De no ser asf, la unidad de composicion 224 anade el siguiente sfmbolo de origen s3 del tren de sfmbolos de origen 218 a z, con el fin de obtener z en su forma final. Se pueden obtener facilmente generalizaciones acerca de un numero mas o menos maximo de sfmbolos de origen a partir de la descripcion anterior, y tales alternativas tambien se describiran en lo sucesivo.

En cualquier caso, la totalidad de estas diferentes componentes o sfmbolos de origen resultantes son de acuerdo con la descripcion posterior, codificados con alternativas de codificacion de entre las mismas. Por lo menos uno de estos se reenvfa por el subdivisor al codificador de PIPE 104, y por ultimo otro de los mismos se envfa al codificador de VLC 102.

En lo sucesivo se esbozan con mas detalle detalles ventajosos particulares. Estos detalles se centran en posibilidades favorables de dividir el intervalo de valores de los elementos de sintaxis y los esquemas de codificacion de VLC y de PIPE por entropfa los cuales se pueden usar para codificar los sfmbolos de origen.

Ademas, tal como se ha descrito tambien en lo que antecede con respecto a la figura 1, el aparato de descodificacion por entropfa de la figura 2a se puede configurar para recibir el primer tren de bits 206 asf como la pluralidad de segundos trenes de bits 216 por separado o en una forma intercalada por medio de un tren de bits intercalado 228. En este ultimo caso, el aparato de descodificacion por entropfa de la figura 2a puede comprender un desintercalador 230 que esta configurado para desintercalar el tren de bits intercalado 228 para obtener el primer tren de bits 206 por un lado y la pluralidad de segundos trenes de bits 216 por otro lado. De forma similar al analisis

5

10

15

20

25

30

35

40

45

50

55

60

anterior de la figura 1, el desintercalador 230 se puede subdividir en dos fases, en concreto un desintercalador 232 para desintercalar el tren de bits intercalado 228 en dos partes, en concreto el tren de bits 206 por un lado y una forma intercalada 234 del segundo tren de bits 216 por otro lado, y un desintercalador 236 para desintercalar este ultimo tren de bits 234 para obtener los trenes de bits individuales 216.

Por lo tanto, la figura 1a y la figura 2a mostraron un aparato de codificacion por entropfa por un lado y un aparato de descodificacion por entropfa adecuado para descodificar el resultado de codificacion que se obtiene por el aparato de codificacion por entropfa de la figura 1, por otro lado. Detalles en lo que respecta a muchos de los elementos que se muestran en la figura 1a y 2 se describen con mas detalle con respecto a las figuras adicionales. Por consiguiente, se hace referencia a estos detalles en la siguiente descripcion y estos detalles se debenan considerar como que tambien son de aplicacion a la figura 1a y 2 de forma individual, siempre que estos detalles se puedan implementar por separado en los codificadores y los descodificadores que se han descrito en lo que antecede. Meramente con respecto a los intercaladores y desintercaladores 132 y 234, se realiza en el presente caso alguna notificacion adicional. En particular, una intercalacion de los trenes de bits 112 y 118 puede ser favorable en el caso de que los trenes de bits hayan de multiplexarse en un canal con el fin de transmitirse. En este caso, puede ser favorable intercalar el tren de bits de VLC 112 por un lado y los trenes de bits de codificacion de PIPE 118 por otro lado con el fin de obedecer determinadas condiciones que se han de satisfacer tales como obedecer un cierto retardo de descodificacion maximo. Dicho incluso de otra forma, puede ser necesario que el desplazamiento de tiempo relativo entre los instantes en los que los elementos de sintaxis y los sfmbolos de origen, de forma respectiva, se pueda recuperar en el lado de descodificacion por un lado y el desplazamiento relativo en el tiempo de acuerdo con su posicion en el tren de bits que se puede analizar sintacticamente por otro lado, no supere un cierto retardo maximo. Muchas alternativas para resolver este problema se describen en lo sucesivo. Una de estas posibilidades comporta que los codificadores por entropfa 116 sean de un tipo de codificador de longitud variable que esta configurado para poner en correspondencia secuencias de sfmbolos alfabeticos con palabras de codigo, y los descodificadores por entropfa 210 para realizar la puesta en correspondencia inversa. Las palabras de codigo del tren de bits de VLC 112 y los trenes de bits de PIPE 118 pueden estar, pero no tienen que estar, seleccionadas de tal modo que ninguna palabra de codigo de alguno de estos trenes de bits es un prefijo de cualquier palabra de codigo de cualquiera de los otros trenes de bits, de tal modo que las fronteras de palabra de codigo siguen pudiendo determinarse de forma unica en el lado de descodificador. En cualquier caso, el intercalador 128 puede configurarse para reservar y almacenar en memoria intermedia una secuencia de entradas de palabra de codigo para la palabra de codigo dentro del primer tren de bits 112 y el segundo tren de bits 118 en un orden secuencial dependiendo de un orden en el cual los sfmbolos alfabeticos de la secuencia 124 de sfmbolos alfabeticos reenviados por el selector 120 a la pluralidad de codificadores por entropfa 116 dan como resultado un comienzo de una nueva secuencia de sfmbolos alfabeticos que van a ponerse en correspondencia con una palabra de codigo respectiva en el codificador por entropfa respectivo 116 y un nuevo sfmbolo de origen del segundo subtren 108 se pone en correspondencia por el codificador de VLC 102, de forma respectiva. Dicho de otra forma, el intercalador 128 inserta las palabras de codigo del tren de bits 112 en el tren de bits comun 126 en el orden de los sfmbolos de origen del que se han obtenido mediante codificacion de VLC, en su orden en el interior del subtren 108 y el tren de sfmbolos de origen 106, de forma respectiva. Las palabras de codigo que son emitidas por los codificadores por entropfa 116 se insertan en el tren de bits comun 126 entre unas consecutivas de las palabras de codigo del tren de bits de VLC 112. Debido a la categorizacion de la codificacion de PIPE de los sfmbolos alfabeticos por la unidad de asignacion 114 y el selector 120, de forma respectiva, cada una de las palabras de codigo de los codificadores por entropfa 116 tiene sfmbolos alfabeticos de diferentes sfmbolos de origen del subtren 110 codificados en las mismas. La posicion de las palabras de codigo de los trenes de bits codificados de PIPE 118 dentro del tren de bits comun 126 entre estos y en relacion con la palabra de codigo de VLC del tren de bits 112 se determina mediante el primer sfmbolo alfabetico codificado en cada palabra de codigo, de forma respectiva, es decir el mas antiguo en el tiempo. El orden de estos sfmbolos alfabeticos primarios codificados en las palabras de codigo de los trenes de bits 118 en el tren de sfmbolos alfabeticos 124 determina el orden de las palabras de codigo de los trenes de bits 118 dentro del tren de bits comun 126 entre estos; en relacion con las palabras de codigo de VLC del tren de bits 112, el sfmbolo de origen al cual pertenecen estos sfmbolos alfabeticos primarios codificados en las palabras de codigo de los trenes de bits 118, determina entre que palabras de codigo consecutivas del tren de bits 112 ha de situarse la palabra de codigo respectiva de cualquiera de los trenes de bits 118. En particular, las palabras de codigo de VLC consecutivas entre las cuales se ha de situar la palabra de codigo respectiva de cualquiera de los trenes de bits 118, son aquellas entre las cuales se situa el sfmbolo de origen del subtren 110 de acuerdo con el orden original del tren de sfmbolos de origen sin subdividir 106, al cual pertenece el sfmbolo alfabetico primario respectivo codificado en la palabra de codigo respectiva de los trenes de bits 118. El intercalador 128 se puede configurar para retirar palabras de codigo introducidas en las entradas de palabra de codigo que se han mencionado en lo que antecede en orden secuencial para obtener el tren de bits comun 126 de palabras de codigo intercaladas. Tal como ya se ha descrito en lo que antecede, los codificadores por entropfa 116 se pueden configurar para introducir de forma secuencial sus palabras de codigo en las entradas de palabra de codigo que se han reservado para el codificador por entropfa respectivo 116 y el selector 120 se puede configurar para reenviar los sfmbolos alfabeticos que representan los sfmbolos de origen del segundo subtren 110 en un orden manteniendo un orden en el cual los sfmbolos de origen del primer subtren 108 y el segundo subtren 110 se intercalaron dentro de la secuencia 106 de sfmbolos de origen.

5

10

15

20

25

30

35

40

45

50

55

60

Se pueden proporcionar medidas adicionales con el fin de hacer frente a situaciones en las que unos determinados de los codificadores por entropfa 116 se seleccionan tan raramente que lleva demasiado tiempo obtener una palabra de codigo valida dentro de ese codificador por entropfa 116 muy raramente usado. En lo sucesivo se describen con mas detalle ejemplos para tales medidas. En particular, el intercalador 128 junto con el codificador por entropfa 116 puede configurarse, en este caso, para evacuar sus sfmbolos alfabeticos recogidos hasta el momento y las palabras de codigo que se han introducido en las entradas de palabra de codigo que se han mencionado en lo que antecede, de forma respectiva, de una forma de tal modo que el tiempo de este procedimiento de evacuacion se puede pronosticar o emular en el lado de descodificacion.

En el lado de descodificacion, el desintercalador 230 puede actuar en el sentido inverso: siempre que, de acuerdo con el esquema de analisis sintactico que se ha mencionado en lo que antecede, el siguiente sfmbolo de origen que va a ser descodificado, sea un sfmbolo codificado de VLC, una palabra de codigo actual dentro del tren de bits comun 228 se considera como una palabra de codigo VLC y se reenvfa en el interior del tren de bits 206 al descodificador de VLC 200. Por otro lado, siempre que cualquiera de los sfmbolos alfabeticos que pertenecen a cualquiera de los sfmbolos codificados de PIPE del subtren 208 sea un sfmbolo alfabetico primario, es decir necesite una nueva puesta en correspondencia de una palabra de codigo de uno respectivo de los trenes de bits 216 con una secuencia de sfmbolos alfabeticos respectiva por el descodificador por entropfa respectivo 210, la palabra de codigo actual del tren de bits comun 228 se considera como una palabra de codigo codificada de PIPE y se reenvfa al descodificador por entropfa respectivo 210. La deteccion de la siguiente frontera de palabra de codigo, es decir la deteccion de la extension de la siguiente palabra de codigo desde el final de la palabra de codigo que acaba de reenviarse a cualquiera de los descodificadores 200 y 202, de forma respectiva, hasta su extremo dentro del tren de bits intercalado entrante 228 se puede aplazar, y realizarse con el conocimiento del descodificador 200 y 202 siendo el destinatario dedicado de esta siguiente palabra de codigo de acuerdo con la regla que se ha bosquejado en lo que antecede: sobre la base de este conocimiento, el libro de codigos que es usado por el descodificador destinatario es conocido y la palabra de codigo respectiva es detectable. Si, por otro lado, los libros de codigos se disenaran de tal modo que las fronteras de palabra de codigo fueran detectables sin el conocimiento a priori acerca del descodificador destinatario entre 200 y 202, entonces la separacion de palabras de codigo se podna realizar en paralelo. En cualquier caso, debido a la intercalacion, los sfmbolos de origen se encuentran disponibles en el descodificador en una forma descodificada por entropfa, es decir como sfmbolos de origen, en su orden correcto con un retardo razonable.

Despues de haber descrito en lo que antecede realizaciones para un aparato de codificacion por entropfa y un aparato de descodificacion por entropfa respectivo, a continuacion se describen mas detalles para los codificadores de PIPE y los descodificadores de PIPE que se han mencionado en lo que antecede.

Un codificador de PIPE se ilustra en la figura 3. El mismo se puede usar como codificador de PIPE en la figura 1a. El codificador de PIPE convierte de una forma sin perdida un tren de sfmbolos de origen 1 en un conjunto de dos o mas trenes de bits parciales 12. Cada sfmbolo de origen 1 puede estar asociado con una categona o tipo de un conjunto de una o mas categonas o tipos. Como un ejemplo, las categonas pueden especificar el tipo del sfmbolo de origen. En el contexto de la codificacion de video tnbrida, una categona separada puede estar asociada con modos de codificacion de macrobloques, modos de codificacion de bloques, indices de imagenes de referencia, diferencias de vector de movimiento, indicadores de subdivision, indicadores de bloques codificados, parametros de cuantificacion, niveles de coeficiente de transformada, etc. En otras areas de aplicacion tales como la codificacion de audio, de habla, de textos, de documentos o de datos generales, son posibles diferentes categorizaciones de sfmbolos de origen. En general, cada sfmbolo de origen puede adoptar un valor de un conjunto finito o infinito contable de valores, en donde el conjunto de posibles valores de sfmbolo de origen puede diferir para diferentes categonas de sfmbolos de origen. Para reducir la complejidad del algoritmo de codificacion y de descodificacion y para permitir un diseno de codificacion y de descodificacion general para diferentes sfmbolos de origen y categonas de sfmbolos de origen, los sfmbolos de origen 1 se convierten en unos conjuntos ordenados de decisiones binarias y estas decisiones binarias se procesan entonces mediante unos algoritmos de codificacion binarios simples. Por lo tanto, la unidad de binarizacion 2 pone en correspondencia de forma biyectiva el valor de cada sfmbolo de origen 1 con una secuencia (o cadena) de contenedores 3. La secuencia de contenedores 3 representa un conjunto de decisiones binarias ordenadas. Cada contenedor 3 o decision binaria puede adoptar un valor de un conjunto de dos valores, por ejemplo uno de los valores 0 y 1. El esquema de binarizacion puede ser diferente para diferentes categonas de sfmbolos de origen. El esquema de binarizacion para una categona de sfmbolos de origen particular puede depender del conjunto de posibles valores de sfmbolo de origen y / u otras propiedades de los sfmbolos de origen para la categona particular. La tabla 1 ilustra tres esquemas de binarizacion a modo de ejemplo para conjuntos infinitos contables. Los esquemas de binarizacion para conjuntos infinitos contables tambien se pueden aplicar para conjuntos finitos grandes de valores de sfmbolo. En particular para conjuntos finitos grandes de valores de sfmbolo, la falta de eficiencia (resultante de secuencias sin usar de contenedores) puede ser despreciable, pero la universalidad de tales esquemas de binarizacion proporciona una ventaja en terminos de la complejidad y de los requisitos de memoria. Para conjuntos finitos pequenos de valores de sfmbolo, a menudo es preferible (en terminos de la eficiencia de codificacion) adaptar el esquema de binarizacion al numero de valores de sfmbolo posibles. La tabla 2 ilustra tres esquemas de binarizacion a modo de ejemplo para conjuntos finitos de 8 valores. Los esquemas

de binarizacion para conjuntos finitos se pueden obtener a partir de los esquemas de binarizacion universales para conjuntos infinitos contables modificando algunas secuencias de contenedores de una forma tal que los conjuntos finitos de secuencias de contenedores representan un codigo libre de redundancia (y potencialmente mediante la reordenacion de las secuencias de contenedores). Como un ejemplo, el esquema de binarizacion unaria truncada en 5 la tabla 2 se creo modificando la secuencia de contenedores para el sfmbolo de origen 7 de la binarizacion unaria universal (vease la tabla 1). La binarizacion de Golomb Exponencial truncada y reordenada de orden 0 en la tabla 2 se creo modificando la secuencia de contenedores para el sfmbolo de origen 7 de la binarizacion de orden 0 de Golomb Exponencial universal (vease la tabla 1) y mediante la reordenacion de las secuencias de contenedores (la secuencia de contenedores truncada para el sfmbolo 7 se asigno al sfmbolo 1). Para conjuntos finitos de sfmbolos, 10 tambien es posible usar unos esquemas de binarizacion no sistematica / no universal, tal como se ejemplifica en la ultima columna de la tabla 2.

Tabla 1: Ejemplos de binarizacion para conjuntos infinitos contables (o conjuntos finitos grandes).

valor de: binarizacion binarizacion de orden 0 de Golomb binarizacion de orden 1 de Golomb

sfmbolo: unaria Exponencial Exponencial

0: 1 1 10

1: 01 010 11

2: 001 011 0100

3: 0001 0010 0 0101

4: 0000 1 0010 1 0110

5: 0000 01 0011 0 0111

6: 0000 001 0011 1 0010 00

7: 0000 0001 0001 000 0010 01

15 _______________________Tabla 2: Ejemplos de binarizacion para conjuntos finitos.

valor de sfmbolo: binarizacion unaria truncada binarizacion de orden 0 de Golomb Exponencial truncada y reordenada binarizacion no sistematica

0: 1 1 000

1: 01 000 001

2: 001 010 01

3: 0001 011 1000

4: 0000 1 0010 0 1001

5: 0000 01 0010 1 1010

6: 0000 001 0011 0 1011 0

7: 0000 000 0011 1 1011 1

Cada contenedor 3 de la secuencia de contenedores creado por la unidad de binarizacion 2 se alimenta a la unidad

de asignacion de parametros 4 en orden secuencial. La unidad de asignacion de parametros asigna un conjunto de

uno o mas parametros a cada contenedor 3 y emite el contenedor con el conjunto asociado de parametros 5. El

20 conjunto de parametros se determina exactamente de la misma forma en el codificador y en el descodificador. El

conjunto de parametros puede consistir en uno o mas de los siguientes parametros:

- una medida para una estimada de la probabilidad para uno de los dos valores de contenedor posibles para el contenedor actual,

25 - una medida para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable

para el contenedor actual,

- un identificador que especifica una estimada para cual de los dos valores de contenedor posibles representa el valor de contenedor menos probable o mas probable para el contenedor actual,

- la categona del sfmbolo de origen asociado,

30 - una medida para la importancia del sfmbolo de origen asociado,

- una medida para la ubicacion del sfmbolo asociado (por ejemplo, en conjuntos de datos temporales, espaciales o volumetricos),

- un identificador que especifica la proteccion de codigo de canal para el contenedor o el sfmbolo de origen asociado,

35 - un identificador que especifica el esquema de cifrado para el contenedor o el sfmbolo de origen asociado,

- un identificador que especifica una clase para el sfmbolo asociado,

- el numero de contenedor en la secuencia de contenedores para el sfmbolo de origen asociado.

5

10

15

20

25

30

35

40

45

50

55

60

La unidad de asignacion de parametros 4 puede asociar cada contenedor 3, 5 con una medida para una estimada

de la probabilidad para uno de los dos valores de contenedor posibles para el contenedor actual. La unidad de

asignacion de parametros 4 asocia cada contenedor 3, 5 con una medida para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable para el contenedor actual y un identificador que especifica una estimada para cual de los dos valores de contenedor posibles representa el valor de contenedor menos probable o mas probable para el contenedor actual. Se debena hacer notar que la probabilidad para el valor de contenedor menos probable o mas probable y el identificador que especifica cual de los dos valores de contenedor posibles representa el valor de contenedor menos probable o mas probable son unas medidas equivalentes para la probabilidad de uno de los dos valores de contenedor posibles.

de la probabilidad para uno de los dos valores de contenedor posibles para el contenedor actual y uno o mas

parametros adicionales (que puede ser uno o mas de los parametros que se han enumerado en lo que antecede). Ademas, la unidad de asignacion de parametros 4 puede asociar cada contenedor 3, 5 con una medida para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable para el contenedor actual, un identificador que especifica una estimada para cual de los dos valores de contenedor posibles representa el valor de contenedor menos probable o mas probable para el contenedor actual, y uno o mas parametros adicionales (que puede ser uno o mas de los parametros que se han enumerado en lo que antecede).

La unidad de asignacion de parametros 4 puede determinar una o mas de las medidas de probabilidad que se han mencionado en lo que antecede (una medida para una estimada de la probabilidad para uno de los dos valores de contenedor posibles para el contenedor actual, una medida para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable para el contenedor actual, un identificador que especifica una estimada para cual de los dos valores de contenedor posibles representa el valor de contenedor menos probable o mas probable para el contenedor actual) sobre la base de un conjunto de uno o mas sfmbolos ya codificados. Los sfmbolos codificados que se usan para determinar las medidas de probabilidad pueden incluir uno o mas sfmbolos ya codificados de la misma categona de sfmbolos, uno o mas sfmbolos ya codificados de la misma categona de sfmbolos que se corresponden con conjuntos de datos (tales como bloques o grupos de muestras) de unas ubicaciones espaciales y / o temporales cercanas (en relacion con el conjunto de datos que esta asociado con el sfmbolo de origen actual), o uno o mas sfmbolos ya codificados de diferentes categonas de sfmbolos que se corresponden con conjuntos de datos de las mismas ubicaciones espaciales y / o temporales y / o unas cercanas (en relacion con el conjunto de datos que esta asociado con el sfmbolo de origen actual).

Cada contenedor con un conjunto asociado de parametros 5 que es una salida de la unidad de asignacion de parametros 4 se alimenta en un selector de memoria intermedia de contenedores 6. El selector de memoria intermedia de contenedores 6 potencialmente modifica el valor del contenedor de entrada 5 sobre la base del valor de contenedor de entrada y los parametros asociados 5 y alimenta el contenedor de salida 7 - con un valor potencialmente modificado - en una de dos o mas memorias intermedias de contenedores 8. La memoria intermedia de contenedores 8 a la que se envfa el contenedor de salida 7 se determinar sobre la base del valor del contenedor de entrada 5 y / o el valor de los parametros asociados 5.

El selector de memoria intermedia de contenedores 6 puede no modificar el valor del contenedor, es decir, el contenedor de salida 7 tiene siempre el mismo valor que el contenedor de entrada 5.

El selector de memoria intermedia de contenedores 6 puede determinar el valor de contenedor de salida 7 sobre la base del valor de contenedor de entrada 5 y la medida asociada para una estimada de la probabilidad para uno de los dos valores de contenedor posibles para el contenedor actual. El valor de contenedor de salida 7 puede establecerse igual al valor de contenedor de entrada 5 si la medida para la probabilidad para uno de los dos valores de contenedor posibles para el contenedor actual es menor que (o menor que o igual a) un umbral particular; si la medida para la probabilidad para uno de los dos valores de contenedor posibles para el contenedor actual es mayor que o igual a (o mayor que) un umbral particular, el valor de contenedor de salida 7 se modifica (es decir, se establece en el opuesto del valor de contenedor de entrada). El valor de contenedor de salida 7 puede establecerse igual al valor de contenedor de entrada 5 si la medida para la probabilidad para uno de los dos valores de contenedor posibles para el contenedor actual es mayor que (o mayor que o igual a) un umbral particular; si la medida para la probabilidad para uno de los dos valores de contenedor posibles para el contenedor actual es menor que o igual a (o menor que) un umbral particular, el valor de contenedor de salida 7 se modifica (es decir, se establece en el opuesto del valor de contenedor de entrada). El valor del umbral se puede corresponder con un valor de 0,5 para la probabilidad estimada para ambos valores de contenedor posibles.

El selector de memoria intermedia de contenedores 6 puede determinar el valor de contenedor de salida 7 sobre la base del valor de contenedor de entrada 5 y el identificador asociado que especifica una estimada para cual de los dos valores de contenedor posibles representa el valor de contenedor menos probable o mas probable para el contenedor actual. El valor de contenedor de salida 7 puede establecerse igual al valor de contenedor de entrada 5 si el identificador especifica que el primero de los dos valores de contenedor posibles representa el valor de contenedor menos probable (o mas probable) para el contenedor actual, y el valor de contenedor de salida 7 se

5

10

15

20

25

30

35

40

45

50

55

60

modifica (es decir, se establece en el opuesto del valor de contenedor de entrada) si el identificador especifica que el segundo de los dos valores de contenedor posibles representa el valor de contenedor menos probable (o mas probable) para el contenedor actual.

El selector de memoria intermedia de contenedores 6 puede determinar la memoria intermedia de contenedores 8 a la que se envfa el contenedor de salida 7 sobre la base de la medida asociada para una estimada de la probabilidad para uno de los dos valores de contenedor posibles para el contenedor actual. El conjunto de valores posibles para la medida para una estimada de la probabilidad para uno de los dos valores de contenedor posibles puede ser finito y el selector de memoria intermedia de contenedores 6 contiene una tabla que asocia exactamente una memoria intermedia de contenedores 8 con cada valor posible para la estimada de la probabilidad para uno de los dos valores de contenedor posibles, en donde diferentes valores para la medida para una estimada de la probabilidad para uno de los dos valores de contenedor posibles pueden asociarse con la misma memoria intermedia de contenedores 8. Ademas, el intervalo de valores posibles para la medida para una estimada de la probabilidad para uno de los dos valores de contenedor posibles se puede subdividir en particiones para dar un numero de intervalos, el selector de memoria intermedia de contenedores 6 determina el mdice de intervalo para la medida actual para una estimada de la probabilidad para uno de los dos valores de contenedor posibles, y el selector de memoria intermedia de contenedores 6 contiene una tabla que asocia exactamente una memoria intermedia de contenedores 8 con cada valor posible para el mdice de intervalo, en donde diferentes valores para el mdice de intervalo pueden asociarse con la misma memoria intermedia de contenedores 8. Los contenedores de entrada 5 con medidas opuestas para una estimada de la probabilidad para uno de los dos valores de contenedor posibles (son medidas opuestas aquellas que representan unas estimadas de probabilidad P y 1 - P) pueden alimentarse a la misma memoria intermedia de contenedores 8. Ademas, la asociacion de la medida para una estimada de la probabilidad para uno de los dos valores de contenedor posibles para el contenedor actual con una memoria intermedia de contenedores particular se adapta con el tiempo, por ejemplo con el fin de asegurar que los trenes de bits parciales creados tienen unas tasas de bits similares.

El selector de memoria intermedia de contenedores 6 puede determinar la memoria intermedia de contenedores 8 a la que se envfa el contenedor de salida 7 sobre la base de la medida asociada para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable para el contenedor actual. El conjunto de valores posibles para la medida para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable puede ser finito y el selector de memoria intermedia de contenedores 6 contiene una tabla que asocia exactamente una memoria intermedia de contenedores 8 con cada valor posible de la estimada de la probabilidad para el valor de contenedor menos probable o mas probable, en donde diferentes valores para la medida para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable pueden asociarse con la misma memoria intermedia de contenedores 8. Ademas, el intervalo de valores posibles para la medida para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable se puede subdividir en particiones para dar un numero de intervalos, el selector de memoria intermedia de contenedores 6 determina el mdice de intervalo para la medida actual para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable, y el selector de memoria intermedia de contenedores 6 contiene una tabla que asocia exactamente una memoria intermedia de contenedores 8 con cada valor posible para el mdice de intervalo, en donde diferentes valores para el mdice de intervalo pueden asociarse con la misma memoria intermedia de contenedores 8. La asociacion de la medida para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable para el contenedor actual con una memoria intermedia de contenedores particular puede adaptarse con el tiempo, por ejemplo con el fin de asegurar que los trenes de bits parciales creados tienen unas tasas de bits similares.

Cada una de las dos o mas memorias intermedias de contenedores 8 se conecta con exactamente un codificador de contenedores 10 y cada codificador de contenedores solo se conecta con una memoria intermedia de contenedores 8. Cada codificador de contenedores 10 lee contenedores a partir de la memoria intermedia de contenedores asociada 8 y convierte una secuencia de contenedores 9 en una palabra de codigo 11, la cual representa una secuencia de bits. Las memorias intermedias de contenedores 8 representan unas memorias intermedias de tipo primero en entrar primero en salir; los contenedores que se alimentan posteriormente (en orden secuencial) a una memoria intermedia de contenedores 8 no se codifican antes que los contenedores que se alimentan con anterioridad (en orden secuencial) a la memoria intermedia de contenedores. Las palabras de codigo 11 que son una salida de un codificador de contenedores particular 10 se escriben en un tren de bits parcial particular 12. El algoritmo de codificacion global convierte los sfmbolos de origen 1 en dos o mas trenes de bits parciales 12, en donde el numero de trenes de bits parciales es igual al numero de memorias intermedias de contenedores y codificadores de contenedores. Un codificador de contenedores 10 puede convertir un numero variable de contenedores 9 en una palabra de codigo 11 de un numero variable de bits. Una ventaja de la codificacion de PIPE que se ha bosquejado en lo que antecede y que se bosqueja en lo sucesivo es que la codificacion de contenedores se puede realizar en paralelo (por ejemplo, para diferentes grupos de medidas de probabilidad), que reduce el tiempo de procesamiento para varias implementaciones.

Otra ventaja de la codificacion de PIPE es que la codificacion de contenedores, la cual es realizada por los

5

10

15

20

25

30

35

40

45

50

55

60

codificadores de contenedores 10, se puede disenar de forma espedfica para diferentes conjuntos de parametros 5. En particular, la codificacion y la codificacion de contenedores se puede optimizar (en terminos de la complejidad y / o la eficiencia de codificacion) para diferentes grupos de probabilidades estimadas. Por un lado, esto permite una reduccion de la complejidad de codificacion / descodificacion en relacion con algoritmos de codificacion aritmetica con una eficiencia de codificacion similar. Por otro lado, esto permite una mejora de la eficiencia de codificacion en relacion con los algoritmos de codificacion de VLC con una complejidad de codificacion / descodificacion similar. Los codificadores de contenedores 10 pueden implementar diferentes algoritmos de codificacion (es decir una puesta en correspondencia de secuencias de contenedores con palabras de codigo) para diferentes grupos de medidas para una estimada de la probabilidad para uno de los dos valores de contenedor posibles 5 para el contenedor actual. Los codificadores de contenedores 10 pueden implementar diferentes algoritmos de codificacion para diferentes grupos de medidas para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable para el contenedor actual. Como alternativa, los codificadores de contenedores 10 pueden implementar diferentes algoritmos de codificacion para diferentes codigos de proteccion de canal. Los codificadores de contenedores 10 pueden implementar diferentes algoritmos de codificacion para diferentes esquemas de cifrado. Los codificadores de contenedores 10 pueden implementar diferentes algoritmos de codificacion para diferentes combinaciones de codigos de proteccion de canal y grupos de medidas para una estimada de la probabilidad para uno de los dos valores de contenedor posibles 5 para el contenedor actual. Los codificadores de contenedores 10 implementan diferentes algoritmos de codificacion para diferentes combinaciones de codigos de proteccion de canal y grupos de medidas para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable 5 para el contenedor actual. Los codificadores de contenedores 10 pueden implementar diferentes algoritmos de codificacion para diferentes combinaciones de esquemas de cifrado y grupos de medidas para una estimada de la probabilidad para uno de los dos valores de contenedor posibles 5 para el contenedor actual. Los codificadores de contenedores 10 pueden implementar diferentes algoritmos de codificacion para diferentes combinaciones de esquemas de cifrado y grupos de medidas para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable 5 para el contenedor actual.

Los codificadores de contenedores 10 - o uno o mas de los codificadores de contenedores - pueden representar motores de codificacion aritmetica binaria. Uno o mas de los codificadores de contenedores pueden representar un motor de codificacion aritmetica binaria, en el que la puesta en correspondencia a partir de la probabilidad de LPS / LPB representativa p lps de una memoria intermedia de contenedores dada con una anchura de intervalo de codigo correspondiente R lps - es decir la subdivision en intervalos del estado interno del motor de codificacion aritmetica binaria, la cual se define mediante la anchura de intervalo actual R y el desplazamiento de intervalo actual L, que identifica, por ejemplo, el lfmite inferior del intervalo de codigo - se realiza mediante el uso de una consulta de tabla. Para cada motor de codificacion aritmetica binaria basado en tabla que esta asociado con una memoria intermedia de contenedores dada, se pueden usar K valores de anchura de intervalo representativos {Qo, ... , Qk-?} para representar R lps con la eleccion de K y los valores de anchura de intervalo representativos {Qo, ... , Qk-?} siendo dependientes de la memoria intermedia de contenedores. Para una eleccion de K > 1, la codificacion aritmetica de un contenedor puede implicar las subetapas de puesta en correspondencia de la anchura de intervalo actual R con un mdice de cuantificacion q con valores en {0, ... , K-1} y de realizacion de la subdivision en intervalos accediendo al valor de anchura de intervalo parcial correspondiente Qq a partir una tabla de consulta usando q como un mdice. Para una eleccion de K = 1, es decir, para el caso en el que solo se da un valor de anchura de intervalo representativo Qo, este valor Qo se puede elegir como una potencia de dos con el fin de permitir la descodificacion de multiples valores de MPS / MPB que entran en la memoria intermedia de contenedores correspondiente dentro de un unico ciclo de renormalizacion. Las palabras de codigo resultantes de cada motor de codificacion aritmetica se pueden transmitir, paquetizar o almacenar por separado, o estas se pueden intercalar para el fin de transmision o almacenamiento tal como se describe en lo sucesivo en el presente documento.

Es decir, un motor de codificacion aritmetica binaria 10 podna realizar las siguientes etapas en la codificacion de los contenedores en su memoria intermedia de contenedores 8:

1. Recibir el contenedor valLPS a partir de una memoria intermedia de contenedores (recuerdese: el motor de codificacion aritmetica binaria respectivo 10 considerado en el presente caso se habfa elegido para recibir “contenedor” debido a que (o, dicho de otra forma, “contenedor” estaba asociado con el motor de codificacion aritmetica binaria respectivo 10) la estimada de distribucion de probabilidad, tal como p_state[contenedor], estaba asociada con ese motor de codificacion aritmetica binaria 10)

2. Cuantificacion de R:

q_index = Qtab[R>>q] (o alguna otra forma de cuantificacion)

3. Determinacion de R lps y R:

R lps = Rtab [q_index] (observese que p_state no se menciona en el presente caso, debido a que este es fijo para el motor de codificacion aritmetica binaria 10 considerado, es decir p_state[codificador], y Rtab tiene almacenado en la misma unos valores previamente calculados para p[p_state[codificador]] ■ Q[q_index]

R = R - R lps [es decir, R se pre-actualiza preliminarmente como si “contenedor” fuera MPS]

4. Calculo del nuevo intervalo parcial: si (contenedor = 1 - vaIMPS) entonces

5

10

15

20

25

30

35

40

45

50

55

60

L ^ L + R

R ^ R lps

5. Renormalizacion de L y R, escribiendo bits, en donde

q_index describe el mdice de un valor de cuantificacion ^do de Qtab,

p_state describe el estado actual (fijo para el motor de codificacion aritmetica binaria 10),

R lps describe la anchura de intervalo que se corresponde con el LPS y vaIMPS describe el valor del bit que se corresponde con el MPS.

Por consiguiente, un motor de descodificacion aritmetica binaria 22 podna realizar las siguientes etapas en la descodificacion de los contenedores que se emiten a la memoria intermedia de contenedores 20:

1. Recibir la solicitud para un contenedor (recuerdese: el motor de descodificacion aritmetica binaria respectivo 22 considerado en el presente caso se habfa elegido para descodificar “contenedor” debido a que (o, dicho de otra forma, “contenedor” estaba asociado con el motor de descodificacion aritmetica binaria respectivo 22) la estimada de distribucion de probabilidad, tal como p_state[contenedor], estaba asociada con ese motor de descodificacion aritmetica binaria 22)

2. Cuantificacion de R:

q_index = Qtab[R>>q] (o alguna otra forma de cuantificacion)

3. Determinacion de R lps y R:

R lps = Rtab [q_index] (observese que p_state no se menciona en el presente caso, debido a que este es fijo para el motor de descodificacion aritmetica binaria 22 considerado, es decir p_state[codificador], y Rtab tiene almacenado en la misma unos valores previamente calculados para p[p_state[codificador]] ■ Q[q_index]

R = R - R lps [es decir, R se re-actualiza preliminarmente como si “contenedor” fuera MPS]

4. Determinacion de contenedor dependiendo de la posicion del intervalo parcial: si (V > R) entonces

contenedor ^ 1 - vaIMPS (contenedor se descodifica como LPS; el selector de memoria intermedia de contenedores 18 obtendra el valor de contenedor real mediante el uso de esta informacion de contenedor y vaIMPS)

V ^ V - R

R ^ R lps

o bien

contenedor ^ vaIMPS (contenedor se descodifica como MPS; el selector de memoria intermedia de contenedores 18 obtendra el valor de contenedor real mediante el uso de esta informacion de contenedor y valMPS)

5. Renormalizacion de R, lectura de un bit y actualizacion de V, en donde

q_index describe el mdice de un valor de cuantificacion lefdo de Qtab,

p_state describe el estado actual (fijo para el motor de descodificacion aritmetica binaria 22),

R lps describe la anchura de intervalo que se corresponde con el LPS,

vaIMPS describe el valor del bit que se corresponde con el MPS, y V describe un valor procedente del interior del intervalo parcial actual.

Los codificadores de contenedores 10 - o uno o mas de los codificadores de contenedores - pueden representar unos codificadores por entropfa que ponen en correspondencia directamente las secuencias de contenedores de entrada 9 con las palabras de codigo 10. Tales puestas en correspondencia se pueden implementar de forma eficiente y no requieren un motor de codificacion aritmetica compleja. La puesta en correspondencia inversa de palabras de codigo con unas secuencias de contenedores (al igual que se hace en el descodificador) debena ser unica con el fin de garantizar una descodificacion perfecta de la secuencia de entrada, pero no se necesita que la puesta en correspondencia de secuencias de contenedores 9 con las palabras de codigo 10 sea necesariamente unica, es decir, es posible que una secuencia de contenedores particular se pueda poner en correspondencia con mas de una secuencia de palabras de codigo. La puesta en correspondencia de las secuencias de contenedores de entrada 9 con las palabras de codigo 10 tambien puede ser biyectiva. Preferiblemente, los codificadores de contenedores 10 - o uno o mas de los codificadores de contenedores - pueden representar unos codificadores por entropfa que ponen en correspondencia directamente unas secuencias de longitud variable de los contenedores de entrada 9 con unas palabras de codigo de longitud variable 10. Las palabras de codigo de salida pueden representar unos codigos libres de redundancia tales como codigos de Huffman generales o codigos de Huffman canonicos.

En la tabla 3 se ilustran dos ejemplos para la puesta en correspondencia biyectiva de secuencias de contenedores con unos codigos libres de redundancia. Las palabras de codigo de salida pueden representar unos codigos redundantes adecuados para la deteccion de errores y la recuperacion de errores. Las palabras de codigo de salida pueden representar unos codigos de cifrado adecuados para cifrar los sfmbolos de origen.

Tabla 3: Ejemplos para puestas en correspondencia entre secuencias de contenedores y palabras de codigo.

5

10

15

20

25

30

35

secuencia de contenedores (el orden de los contenedores es de izquierda a derecha): palabras de codigo (el orden de los bits es de izquierda a derecha)

0000 0000: 1

0000 0001: 0000

0000 001: 0001

0000 01: 0010

0000 1: 0011

0001: 0100

001: 0101

01: 0110

1: 0111

000: 10

01: 11

001: 010

11: 011

1000 0: 0001

1001: 0010

1010: 0011

1000 1 1011: 0000 0 0000 1

Los codificadores de contenedores 10 - o uno o mas de los codificadores de contenedores - pueden representar unos codificadores por entropfa que ponen en correspondencia directamente unas secuencias de longitud variable de los contenedores de entrada 9 con unas palabras de codigo de longitud fija 10. Los codificadores de contenedores 10 - o uno o mas de los codificadores de contenedores - representan unos codificadores por entropfa que ponen en correspondencia directamente unas secuencias de longitud fija de los contenedores de entrada 9 con las palabras de codigo de longitud variable 10.

Un descodificador de PIPE se ilustra en la figura 4. El descodificador realiza basicamente las operaciones inversas del codificador de la figura 3, de tal modo que la secuencia (previamente codificada) de sfmbolos de origen 27 se descodifica a partir de un conjunto de dos o mas trenes de bits parciales 24. El descodificador incluye dos flujos de proceso diferentes: Un flujo para solicitudes de datos, el cual reproduce el flujo de datos del codificador, y un flujo de datos, el cual representa la inversa del flujo de datos de codificador. En la ilustracion en la figura 4, las flechas de trazo discontinuo representan el flujo de solicitudes de datos, mientras que las flechas de trazo continuo representan el flujo de datos. Los bloques basicos del descodificador basicamente reproducen los bloques basicos del codificador, pero implementan las operaciones inversas.

La descodificacion de un sfmbolo de origen es desencadenada por una solicitud para un nuevo sfmbolo de origen descodificado 13 que se envfa a la unidad de binarizacion 14. Cada solicitud para un nuevo sfmbolo de origen descodificado 13 puede asociarse con una categona de un conjunto de una o mas categonas. La categona que esta asociada con una solicitud para un sfmbolo de origen es la misma que la categona que estaba asociada con el sfmbolo de origen correspondiente durante la codificacion.

La unidad de binarizacion 14 pone en correspondencia la solicitud para un sfmbolo de origen 13 con una o mas solicitudes para un contenedor que se envfan a la unidad de asignacion de parametros 16. Como respuesta final a una solicitud para un contenedor que se envfa a la unidad de asignacion de parametros 16 por la unidad de binarizacion 14, la unidad de binarizacion 14 recibe un contenedor descodificado 26 a partir del selector de memoria intermedia de contenedores 18. La unidad de binarizacion 14 compara la secuencia recibida de contenedores descodificados 26 con las secuencias de contenedores de un esquema de binarizacion particular para el sfmbolo de origen solicitado y, si la secuencia recibida de contenedores descodificados 26 coincide con la binarizacion de un sfmbolo de origen, la unidad de binarizacion vacfa su memoria intermedia de contenedores y emite el sfmbolo de origen descodificado como respuesta final a la solicitud para un nuevo sfmbolo descodificado. Si la secuencia ya recibida de contenedores descodificados no coincide con cualquiera de las secuencias de contenedores para el esquema de binarizacion para el sfmbolo de origen solicitado, la unidad de binarizacion envfa otra solicitud para un contenedor a la unidad de asignacion de parametros hasta que la secuencia de contenedores descodificados

5

10

15

20

25

30

35

40

45

50

55

60

coincide con una de las secuencias de contenedores del esquema de binarizacion para el sfmbolo de origen solicitado. Para cada solicitud para un sfmbolo de origen, el descodificador usa el mismo esquema de binarizacion que se uso para codificar el sfmbolo de origen correspondiente. El esquema de binarizacion puede ser diferente para diferentes categonas de sfmbolos de origen. El esquema de binarizacion para una categona de sfmbolos de origen particular puede depender del conjunto de posibles valores de sfmbolo de origen y / u otras propiedades de los sfmbolos de origen para la categona particular.

La unidad de asignacion de parametros asigna un conjunto de uno o mas parametros a cada solicitud para un contenedor y envfa la solicitud para un contenedor con el conjunto asociado de parametros al selector de memoria intermedia de contenedores. El conjunto de parametros que se asignan a un contenedor solicitado por la unidad de asignacion de parametros es el mismo que se asigno al contenedor correspondiente durante la codificacion. El conjunto de parametros puede consistir en uno o mas de los parametros que se mencionan en la descripcion de codificador.

La unidad de asignacion de parametros 16 puede asociar cada solicitud para un contenedor con una medida para una estimada de la probabilidad para uno de los dos valores de contenedor posibles para el contenedor solicitado actual. En particular, la unidad de asignacion de parametros 16 puede asociar cada solicitud para un contenedor con una medida para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable para el contenedor solicitado actual y un identificador que especifica una estimada para cual de los dos valores de contenedor posibles representa el valor de contenedor menos probable o mas probable para el contenedor solicitado actual.

La unidad de asignacion de parametros 16 puede asociar cada solicitud para un contenedor 15, 17 con una medida para una estimada de la probabilidad para uno de los dos valores de contenedor posibles para el contenedor solicitado actual y uno o mas parametros adicionales. La unidad de asignacion de parametros 16 puede asociar cada solicitud para un contenedor 15, 17 con una medida para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable para el contenedor solicitado actual, un identificador que especifica una estimada para cual de los dos valores de contenedor posibles representa el valor de contenedor menos probable o mas probable para el contenedor solicitado actual, y uno o mas parametros adicionales (que puede uno o mas de los parametros que se han enumerado en lo que antecede).

La unidad de asignacion de parametros 16 puede determinar una o mas de las medidas de probabilidad que se han mencionado en lo que antecede (una medida para una estimada de la probabilidad para uno de los dos valores de contenedor posibles para el contenedor solicitado actual, una medida para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable para el contenedor solicitado actual, un identificador que especifica una estimada para cual de los dos valores de contenedor posibles representa el valor de contenedor menos probable o mas probable para el contenedor solicitado actual) sobre la base de un conjunto de uno o mas sfmbolos ya descodificados. La determinacion de las medidas de probabilidad para a particular solicitud para un contenedor reproduce el proceso en el codificador para el contenedor correspondiente. Los sfmbolos descodificados que se usan para determinar las medidas de probabilidad pueden incluir uno o mas sfmbolos ya descodificados de la misma categona de sfmbolos, uno o mas sfmbolos ya descodificados de la misma categona de sfmbolos que se corresponden con conjuntos de datos (tal como bloques o grupos de muestras) de unas ubicaciones espaciales y / o temporales cercanas (en relacion con el conjunto de datos que esta asociado con la solicitud actual para un sfmbolo de origen), o uno o mas sfmbolos ya descodificados de diferentes categonas de sfmbolos que se corresponden con conjuntos de datos de las mismas y / o unas ubicaciones espaciales y / o temporales cercanas (en relacion con el conjunto de datos que esta asociado con la solicitud actual para un sfmbolo de origen).

Cada solicitud para un contenedor con un conjunto asociado de parametros 17 que es una salida de la unidad de asignacion de parametros 16 se alimenta a un selector de memoria intermedia de contenedores 18. Sobre la base del conjunto asociado de parametros 17, el selector de memoria intermedia de contenedores 18 envfa una solicitud para un contenedor 19 a una de dos o mas memorias intermedias de contenedores 20 y recibe un contenedor descodificado 25 a partir de la memoria intermedia de contenedores seleccionada 20. El contenedor de entrada descodificado 25 se modifica potencialmente y el contenedor de salida descodificado 26 - con un valor potencialmente modificado - se envfa a la unidad de binarizacion 14 como respuesta final a la solicitud para un contenedor con un conjunto asociado de parametros 17.

La memoria intermedia de contenedores 20 a la cual se reenvfa la solicitud para un contenedor se selecciona de la misma forma que la memoria intermedia de contenedores a la que se envio el contenedor de salida del selector de memoria intermedia de contenedores en el lado de codificador.

El selector de memoria intermedia de contenedores 18 puede determinar la memoria intermedia de contenedores 20 a la que se envfa la solicitud para un contenedor 19 sobre la base de la medida asociada para una estimada de la probabilidad para uno de los dos valores de contenedor posibles para el contenedor solicitado actual. El conjunto de valores posibles para la medida para una estimada de la probabilidad para uno de los dos valores de contenedor

5

10

15

20

25

30

35

40

45

50

55

60

posibles puede ser finito y el selector de memoria intermedia de contenedores 18 contiene una tabla que asocia exactamente una memoria intermedia de contenedores 20 con cada valor posible de la estimada de la probabilidad para uno de los dos valores de contenedor posibles, en donde diferentes valores para la medida para una estimada de la probabilidad para uno de los dos valores de contenedor posibles pueden asociarse con la misma memoria intermedia de contenedores 20. El intervalo de valores posibles para la medida para una estimada de la probabilidad para uno de los dos valores de contenedor posibles se puede subdividir en particiones para dar un numero de intervalos, el selector de memoria intermedia de contenedores 18 determina el mdice de intervalo para la medida actual para una estimada de la probabilidad para uno de los dos valores de contenedor posibles, y el selector de memoria intermedia de contenedores 18 contiene una tabla que asocia exactamente una memoria intermedia de contenedores 20 con cada valor posible para el mdice de intervalo, en donde diferentes valores para el mdice de intervalo pueden asociarse con la misma memoria intermedia de contenedores 20. Solicitudes para unos contenedores 17 con medidas opuestas para una estimada de la probabilidad para uno de los dos valores de contenedor posibles (son medidas opuestas aquellas que representan unas estimadas de probabilidad P y 1 - P) puede reenviarse a la misma memoria intermedia de contenedores 20. Ademas, la asociacion de la medida para una estimada de la probabilidad para uno de los dos valores de contenedor posibles para la solicitud de contenedor actual con una memoria intermedia de contenedores particular puede adaptarse con el tiempo.

El selector de memoria intermedia de contenedores 18 puede determinar la memoria intermedia de contenedores 20 a la que se envfa la solicitud para un contenedor 19 sobre la base de la medida asociada para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable para el contenedor solicitado actual. El conjunto de valores posibles para la medida para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable puede ser finito y el selector de memoria intermedia de contenedores 18 puede contener una tabla que asocia exactamente una memoria intermedia de contenedores 20 con cada valor posible de la estimada de la probabilidad para el valor de contenedor menos probable o mas probable, en donde diferentes valores para la medida para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable pueden asociarse con la misma memoria intermedia de contenedores 20. El intervalo de valores posibles para la medida para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable se puede subdividir en particiones para dar un numero de intervalos, el selector de memoria intermedia de contenedores 18 determina el mdice de intervalo para la medida actual para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable, y el selector de memoria intermedia de contenedores 18 contiene una tabla que asocia exactamente una memoria intermedia de contenedores 20 con cada valor posible para el mdice de intervalo, en donde diferentes valores para el mdice de intervalo pueden asociarse con la misma memoria intermedia de contenedores 20. En la asociacion de la medida para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable para la solicitud de contenedor actual con una memoria intermedia de contenedores particular se adapta con el tiempo.

Despues de recibir un contenedor descodificado 25 a partir de la memoria intermedia de contenedores seleccionada 20, el selector de memoria intermedia de contenedores 18 potencialmente modifica el contenedor de entrada 25 y envfa el contenedor de salida 26 - con un valor potencialmente modificado - a la unidad de binarizacion 14. La puesta en correspondencia de contenedores de entrada / salida del selector de memoria intermedia de contenedores 18 es la inversa de la puesta en correspondencia de contenedores de entrada / salida del selector de memoria intermedia de contenedores en el lado de codificador.

El selector de memoria intermedia de contenedores 18 se puede configurar para no modificar el valor del contenedor, es decir, el contenedor de salida 26 tiene siempre el mismo valor que el contenedor de entrada 25.

El selector de memoria intermedia de contenedores 18 puede determinar el valor de contenedor de salida 26 sobre la base del valor de contenedor de entrada 25 y la medida para una estimada de la probabilidad para uno de los dos valores de contenedor posibles para el contenedor solicitado actual que se asocia con la solicitud para un contenedor 17. El valor de contenedor de salida 26 puede establecerse igual al valor de contenedor de entrada 25 si la medida para la probabilidad para uno de los dos valores de contenedor posibles para la solicitud de contenedor actual es menor que (o menor que o igual a) un umbral particular; si la medida para la probabilidad para uno de los dos valores de contenedor posibles para la solicitud de contenedor actual es mayor que o igual a (o mayor que) un umbral particular, el valor de contenedor de salida 26 se modifica (es decir, se establece en el opuesto del valor de contenedor de entrada). El valor de contenedor de salida 26 puede establecerse igual al valor de contenedor de entrada 25 si la medida para la probabilidad para uno de los dos valores de contenedor posibles para la solicitud de contenedor actual es mayor que (o mayor que o igual a) un umbral particular; si la medida para la probabilidad para uno de los dos valores de contenedor posibles para la solicitud de contenedor actual es menor que o igual a (o menor que) un umbral particular, el valor de contenedor de salida 26 se modifica (es decir, se establece en el opuesto del valor de contenedor de entrada). El valor del umbral se puede corresponder con un valor de 0,5 para la probabilidad estimada para ambos valores de contenedor posibles.

El selector de memoria intermedia de contenedores 18 puede determinar el valor de contenedor de salida 26 sobre la base del valor de contenedor de entrada 25 y el identificador, que especifica una estimada para cual de los dos

5

10

15

20

25

30

35

40

45

50

55

60

valores de contenedor posibles representa el valor de contenedor menos probable o mas probable para la solicitud de contenedor actual, que se asocia con la solicitud para un contenedor 17. El valor de contenedor de salida 26 puede establecerse igual al valor de contenedor de entrada 25 si el identificador especifica que el primero de los dos valores de contenedor posibles representa el valor de contenedor menos probable (o mas probable) para la solicitud de contenedor actual, y el valor de contenedor de salida 26 se modifica (es decir, se establece en el opuesto del valor de contenedor de entrada) si el identificador especifica que el segundo de los dos valores de contenedor posibles representa el valor de contenedor menos probable (o mas probable) para la solicitud de contenedor actual.

Tal como se ha descrito en lo que antecede, el selector de memoria intermedia de contenedores envfa una solicitud para un contenedor 19 a una de las dos o mas memorias intermedias de contenedores 20. Las memorias intermedias de contenedores 20 representan unas memorias intermedias de tipo primero en entrar primero en salir, que se alimentan con unas secuencias de contenedores descodificados 21 a partir de los descodificadores de contenedores conectados 22. Como respuesta a una solicitud para un contenedor 19 que se envfa a una memoria intermedia de contenedores 20 a partir del selector de memoria intermedia de contenedores 18, la memoria intermedia de contenedores 20 retira el contenedor de su contenido que en primer lugar se alimento a la memoria intermedia de contenedores 20 y lo envfa al selector de memoria intermedia de contenedores 18. Los contenedores que se envfan con anterioridad a la memoria intermedia de contenedores 20 se retiran con anterioridad y se envfan al selector de memoria intermedia de contenedores 18.

Cada una de las dos o mas memorias intermedias de contenedores 20 se conecta con exactamente un descodificador de contenedores 22 y cada descodificador de contenedores solo se conecta con una memoria intermedia de contenedores 20. Cada descodificador de contenedores 22 lee las palabras de codigo 23, las cuales representan unas secuencias de bits, a partir de un tren de bits parcial separado 24. El descodificador de contenedores convierte una palabra de codigo 23 en una secuencia de contenedores 21 que se envfa a la memoria intermedia de contenedores conectada 20. El algoritmo de descodificacion global convierte dos o mas trenes de bits parciales 24 en un numero de sfmbolos de origen descodificados, en donde el numero de trenes de bits parciales es igual al numero de memorias intermedias de contenedores y de descodificadores de contenedores y la descodificacion de sfmbolos de origen es desencadenada por solicitudes para nuevos sfmbolos de origen. Un descodificador de contenedores 22 puede convertir las palabras de codigo 23 de un numero variable de bits en una secuencia de un numero variable de contenedores 21. Una ventaja de la configuracion de PIPE anterior es que la descodificacion de contenedores a partir de los dos o mas trenes de bits parciales se puede realizar en paralelo (por ejemplo, para diferentes grupos de medidas de probabilidad), que reduce el tiempo de procesamiento para varias implementaciones.

Otra ventaja de la descodificacion de PIPE anterior es que la descodificacion de contenedores, la cual es realizada por los descodificadores de contenedores 22, se puede disenar de forma especifica para diferentes conjuntos de parametros 17. En particular, la codificacion y la descodificacion de contenedores se puede optimizar (en terminos de la complejidad y / o la eficiencia de codificacion) para diferentes grupos de probabilidades estimadas. Por un lado, esto permite una reduccion de la complejidad de codificacion / descodificacion en relacion con algoritmos de codificacion aritmetica con una eficiencia de codificacion similar. Por otro lado, esto permite una mejora de la eficiencia de codificacion en relacion con los algoritmos de codificacion de VLC con una complejidad de codificacion / descodificacion similar. Los descodificadores de contenedores 22 pueden implementar diferentes algoritmos de descodificacion (es decir la puesta en correspondencia de secuencias de contenedores con palabras de codigo) para diferentes grupos de medidas para una estimada de la probabilidad para uno de los dos valores de contenedor posibles 17 para la solicitud de contenedor actual. Los descodificadores de contenedores 22 pueden implementar diferentes algoritmos de descodificacion para diferentes grupos de medidas para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable para el contenedor solicitado actual. Los descodificadores de contenedores 22 pueden implementar diferentes algoritmos de descodificacion para diferentes codigos de proteccion de canal. Los descodificadores de contenedores 22 pueden implementar diferentes algoritmos de descodificacion para diferentes esquemas de cifrado. Los descodificadores de contenedores 22 pueden implementar diferentes algoritmos de descodificacion para diferentes combinaciones de codigos de proteccion de canal y grupos de medidas para una estimada de la probabilidad para uno de los dos valores de contenedor posibles 17 para el contenedor solicitado actual. Los descodificadores de contenedores 22 pueden implementar diferentes algoritmos de descodificacion para diferentes combinaciones de codigos de proteccion de canal y grupos de medidas para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable 17 para el contenedor solicitado actual. Los descodificadores de contenedores 22 pueden implementar diferentes algoritmos de descodificacion para diferentes combinaciones de esquemas de cifrado y grupos de medidas para una estimada de la probabilidad para uno de los dos valores de contenedor posibles 17 para el contenedor solicitado actual. Los descodificadores de contenedores 22 pueden implementar diferentes algoritmos de descodificacion para diferentes combinaciones de esquemas de cifrado y grupos de medidas para una estimada de la probabilidad para el valor de contenedor menos probable o mas probable 17 para el contenedor solicitado actual.

Los descodificadores de contenedores 22 do la puesta en correspondencia inversa de los codificadores de contenedores correspondientes en el lado de codificador.

5

10

15

20

25

30

35

40

45

50

55

60

Los descodificadores de contenedores 22 - o uno o mas de los descodificadores de contenedores - pueden representar motores de descodificacion aritmetica binaria.

Los descodificadores de contenedores 22 - o uno o mas de los descodificadores de contenedores - pueden representar unos descodificadores por entropfa que ponen en correspondencia directamente las palabras de codigo 23 con las secuencias de contenedores 21. Tales puestas en correspondencia se pueden implementar de forma eficiente y no requieren un motor de codificacion aritmetica compleja. La puesta en correspondencia de palabras de codigo con secuencias de contenedores ha de ser unica. La puesta en correspondencia de las palabras de codigo 23 con las secuencias de contenedores 21 puede ser biyectiva. Los descodificadores de contenedores 10 - o uno o mas de los descodificadores de contenedores - pueden representar unos descodificadores por entropfa que ponen en correspondencia directamente unas palabras de codigo de longitud variable 23 con unas secuencias de longitud variable de contenedores 21. Las palabras de codigo de entrada pueden representar unos codigos libres de redundancia tales como codigos de Huffman generales o codigos de Huffman canonicos. En la tabla 3 se ilustran dos ejemplos para la puesta en correspondencia biyectiva de unos codigos libres de redundancia con unas secuencias de contenedores. Las palabras de codigo de entrada pueden representar unos codigos redundantes adecuados para la deteccion de errores y la recuperacion de errores. Las palabras de codigo de entrada pueden representar codigos de cifrado.

Los descodificadores de contenedores 22 - o uno o mas de los descodificadores de contenedores - pueden representar unos descodificadores por entropfa que ponen en correspondencia directamente unas palabras de codigo de longitud fija 23 con unas secuencias de longitud variable de contenedores 21. Como alternativa, los descodificadores de contenedores 22 - o uno o mas de los descodificadores de contenedores - representan unos descodificadores por entropfa que ponen en correspondencia directamente las palabras de codigo de longitud variable 23 con unas secuencias de longitud fija de contenedores 21.

Por lo tanto, la figura 3 y 4 mostraron un codificador de PIPE para codificar una secuencia de sfmbolos de origen 1 y un descodificador de PIPE para reconstruir la misma. Es decir, el codificador de PIPE de la figura 3 se puede usar como el codificador de PIPE 104 en la figura 1a con la unidad de binarizacion 2 que actua como el simbolizador 122, la unidad de asignacion de parametros 4 que actua como la unidad de asignacion 114, el selector de memoria intermedia de contenedores 6 que actua como selector 120, y el par de la memoria intermedia de contenedores 8 y el codificador de contenedores 10 conectado en serie que actua como uno respectivo de los codificadores por entropfa 116 cada uno de los cuales emite unos trenes de bits 12 que se corresponden con los trenes de bits 118 en la figura 1a. Como queda claro a partir de la comparacion de la figura 3 y la figura 1, la unidad de asignacion 114 de la figura 1a puede tener su entrada como alternativa conectada con el lado de entrada del simbolizador 122 en lugar del lado de salida de este ultimo. De forma similar, el descodificador de PIPE de la figura 4 se puede usar como el descodificador de PIPE 202 en la figura 2a con unos trenes de bits parciales 24 que se corresponden con los trenes de bits 216 en la figura 2, los pares de la memoria intermedia 20 y el descodificador de contenedores 22 conectado en serie que se corresponden con los descodificadores por entropfa individuales 210, el selector de memoria intermedia de contenedores 18 que actua como selector 214, la unidad de asignacion de parametros 16 que actua como la unidad de asignacion 212 y la unidad de binarizacion 14 que actua como el desimbolizador 222. De nuevo, una comparacion entre la figura 2a y la figura 4 deja claro que la interconexion entre el desimbolizador 222, la unidad de asignacion 212 y el selector 214 puede configurarse de forma diferente, de tal modo que como alternativa, las conexiones de la figura 2a se modifican para corresponderse con las que se muestran en la figura 4.

El codificador de PIPE de la figura 3 comprende una unidad de asignacion 4 configurada para asignar un numero de parametros 5 a cada sfmbolo alfabetico de la secuencia de sfmbolos alfabeticos 3. La asignacion se basa en informacion contenida dentro de sfmbolos alfabeticos previos de la secuencia de sfmbolos alfabeticos tales como la categona del elemento de sintaxis 1 a la cual pertenece la representacion - tal como binarizacion - del sfmbolo alfabetico actual y la cual, de acuerdo con la estructura sintactica de los elementos de sintaxis 1, es de esperar en la actualidad, expectativa que, a su vez, es deducible a partir de la historia de los elementos de sintaxis 1 y los sfmbolos alfabeticos 3 previos. Ademas, el codificador comprende una pluralidad de codificadores por entropfa 10 cada uno de los cuales esta configurado para convertir los sfmbolos alfabeticos 3 reenviados al codificador por entropfa respectivo en un tren de bits respectivo 12, y un selector 6 configurado para reenviar cada sfmbolo alfabetico 3 a uno seleccionado de la pluralidad de codificadores por entropfa 10, dependiendo la seleccion del numero de parametros 5 asignado al sfmbolo alfabetico respectivo 3. El descodificador de PIPE de la figura 4 comprende una pluralidad de descodificadores por entropfa 22, cada uno de los cuales esta configurado para convertir un tren de bits respectivo 23 en sfmbolos alfabeticos 21; una unidad de asignacion 16 configurada para asignar un numero de parametros 17 a cada sfmbolo alfabetico 15 de una secuencia de sfmbolos alfabeticos que se va a reconstruir sobre la base de informacion contenida dentro de sfmbolos alfabeticos previamente reconstruidos de la secuencia de sfmbolos alfabeticos (veanse 26 y 27 en la figura 4); y un selector 18 que esta configurado para recuperar cada sfmbolo alfabetico de la secuencia de sfmbolos alfabeticos que se va a reconstruir a partir de uno seleccionado de la pluralidad de descodificadores por entropfa 22, dependiendo la seleccion del numero de parametros que se definen para el sfmbolo alfabetico respectivo. La unidad de asignacion 16 puede configurarse de

5

10

15

20

25

30

35

40

45

50

55

60

tal modo que el numero de parametros asignado a cada s^bolo alfabetico comprende, o es, una medida para una estimada de una probabilidad de distribucion entre los posibles valores de sfmbolo alfabetico que puede asumir un s^bolo alfabetico respectivo. La secuencia de sfmbolos alfabeticos que se va a reconstruir puede ser de un alfabeto binario y la unidad de asignacion 16 puede configurarse de tal modo que la estimada de la distribucion de probabilidad consiste en una medida para una estimada de una probabilidad de un valor de contenedor menos probable o mas probable de los dos valores de contenedor posibles del alfabeto binario y un identificador que especifica una estimada para cual de los dos valores de contenedor posibles representa el valor de contenedor menos probable o mas probable. La unidad de asignacion 16 puede configurarse adicionalmente para asignar de forma interna un contexto a cada sfmbolo alfabetico de la secuencia de sfmbolos alfabeticos 15 que se va a reconstruir sobre la base de la informacion contenida dentro de sfmbolos alfabeticos previamente reconstruidos de la secuencia de sfmbolos alfabeticos que se va a reconstruir con cada contexto teniendo una estimada de distribucion de probabilidad respectiva asociado a ello, y adaptar la estimada de distribucion de probabilidad para cada contexto a una estadfstica de sfmbolos real sobre la base de los valores de sfmbolo de sfmbolos alfabeticos previamente reconstruidos a los que se asigna el contexto respectivo. El contexto puede tener en cuenta una relacion espacial o proximidades de posiciones a las cuales pertenecen los elementos de sintaxis tal como en la codificacion de video o de imagenes, o incluso en tablas en el caso de las aplicaciones financieras. Entonces, la medida para la estimada de la distribucion de probabilidad para cada sfmbolo alfabetico puede determinarse sobre la base de la estimada de distribucion de probabilidad asociada con el contexto asignado al sfmbolo alfabetico respectivo tal como mediante la cuantificacion de la estimada de distribucion de probabilidad asociada con el contexto asignado con el sfmbolo alfabetico respectivo a una de una pluralidad de representantes de estimada de distribucion de probabilidad con el fin de obtener la medida para la estimada de la distribucion de probabilidad. El selector puede configurarse de tal modo que se define una asociacion sobreyectiva entre la pluralidad de codificadores por entropfa y la pluralidad de representantes de estimada de distribucion de probabilidad, es decir cada codificador por entropfa tiene por lo menos una representante de estimada de distribucion de probabilidad asociado con el mismo, pero mas de una representante de estimada de distribucion de probabilidad se pueden asociar con un codificador por entropfa. La asociacion incluso puede ser biyectiva. El selector 18 se puede configurar para cambiar una puesta en correspondencia de cuantificacion de un intervalo de las estimadas de distribucion de probabilidad a la pluralidad de representantes de estimada de distribucion de probabilidad de una forma determinista previamente determinada dependiendo de sfmbolos alfabeticos previamente reconstruidos de la secuencia de sfmbolos alfabeticos, con el tiempo. Es decir, el selector 18 puede cambiar los tamanos de paso de cuantificacion, es decir los intervalos de distribuciones de probabilidad puestos en correspondencia con los indices de probabilidad individuales los cuales, a su vez, pueden asociarse de forma sobreyectiva con los descodificadores por entropfa individuales. La pluralidad de descodificadores por entropfa 22, a su vez, se pueden configurar para adaptar su forma de convertir sfmbolos alfabeticos en unos trenes de bits sensibles a un cambio en la puesta en correspondencia de cuantificacion. Por ejemplo, cada descodificador por entropfa 22 se puede optimizar para, es decir puede tener una tasa de compresion optima para, una determinada estimada de distribucion de probabilidad dentro del intervalo de cuantificacion de estimadas de distribucion de probabilidad respectivo, y puede cambiar su correspondencia de secuencia de sfmbolos / palabras de codigo con el fin de adaptar la posicion de esta determinada estimada de distribucion de probabilidad dentro del intervalo de cuantificacion de estimadas de distribucion de probabilidad respectivo con un cambio de este ultimo con el fin de optimizarse. El selector se puede configurar para cambiar la puesta en correspondencia de cuantificacion de tal modo que las tasas mediante las cuales se recuperan los sfmbolos alfabeticos a partir de la pluralidad de descodificadores por entropfa, se hacen menos dispersas. En lo que respecta a la unidad de binarizacion 14 se hace notar que el mismo puede no usarse si los elementos de sintaxis ya son binarios. Ademas, dependiendo del tipo de descodificador 22, no es necesaria la existencia de las memorias intermedias 20. Ademas, las memorias intermedias pueden estar integradas dentro de los descodificadores.

Hasta el momento, se han descrito en lo que antecede mas detalles para el codificador de PIPE 104 y el descodificador de PIPE 202 en la figura 1a y 2, con respecto a la figura 3 y 4, que, si se implementa facilmente en los aparatos de la figura 1a y 2, conducen a una salida de tren de bits en paralelo en la cual los trenes de bits parciales de VLC y de PIPE se transportan en paralelo. En lo sucesivo, se describen posibilidades, como combinar los trenes de bits parciales de PIPE para transmitirse, entonces, a lo largo del tren de bits de VLC en paralelo, o con una intercalacion en segundo lugar de ambos trenes de bits, es decir el tren de bits de VLC y el tren de bits de PIPE intercalado.

Terminacion de secuencias de simbolos de origen finitas

En los codificadores y descodificadores de PIPE, la codificacion y la descodificacion se pueden realizar para un conjunto finito de sfmbolos de origen. A menudo una cierta cantidad de datos tal como una imagen fija, una trama o campo de una secuencia de video, una rebanada de una imagen, una rebanada de una trama o un campo de una secuencia de video, o un conjunto de muestras de audio sucesivas, etc. se codifica. Para conjuntos finitos de sfmbolos de origen, en general, han de determinarse los trenes de bits parciales que se crean en el lado de codificador, es decir, se ha de asegurar que todos los sfmbolos de origen se pueden descodificar a partir de los trenes de bits parciales transmitidos o almacenados. Despues de que el ultimo contenedor se haya insertado en la memoria intermedia de contenedores 8 correspondiente, el codificador de contenedores 10 ha de asegurar que una

5

10

15

20

25

30

35

40

45

50

55

60

palabra de codigo completa se escribe en el tren de bits parcial 12. Si el codificador de contenedores 10 representa un motor de codificacion aritmetica binaria, la palabra de codigo aritmetica ha de determinarse. Si el codificador de contenedores 10 representa un codificador por entropfa que implementa una puesta en correspondencia directa de secuencias de contenedores con palabras de codigo, la secuencia de contenedores que se almacena en la memoria intermedia de contenedores despues de la escritura del ultimo contenedor en la memoria intermedia de contenedores podna no representar una secuencia de contenedores que se asocia con una palabra de codigo (es decir, esta podna representar un prefijo de dos o mas secuencias de contenedores que estan asociadas con palabras de codigo). En caso de este tipo, cualquiera de las palabras de codigo que estan asociadas con una secuencia de contenedores que contiene la secuencia de contenedores en la memoria intermedia de contenedores como prefijo ha de escribirse en el tren de bits parcial (se ha de evacuar la memoria intermedia de contenedores). Esto se podna realizar mediante la insercion de contenedores con un valor particular o uno arbitrario en la memoria intermedia de contenedores hasta que se escribe una palabra de codigo. El codificador de contenedores puede seleccionar una de las palabras de codigo con una longitud minima (ademas de la propiedad de que la secuencia de contenedores asociada debe contener la secuencia de contenedores en la memoria intermedia de contenedores como prefijo). En el lado de descodificador, el descodificador de contenedores 22 puede descodificar mas contenedores de los que se requieren para la ultima palabra de codigo en un tren de bits parcial; estos contenedores no son solicitados por el selector de memoria intermedia de contenedores 18 y se descartan y se ignoran. La descodificacion del conjunto finito de sfmbolos se controla mediante solicitudes para sfmbolos de origen descodificados; si no se solicita sfmbolo de origen adicional alguno para una cantidad de datos, la descodificacion se termina.

Transmision y multiplexacion de los trenes de bits parciales

Los trenes de bits parciales 12 que se crean por el codificador de PIPE se pueden transmitir por separado, o estos se pueden multiplexar para dar un unico tren de bits, o las palabras de codigo de los trenes de bits parciales se pueden intercalar en un unico tren de bits.

Cada tren de bits parcial para una cantidad de datos se puede escribir en un paquete de datos. La cantidad de datos puede ser un conjunto arbitrario de sfmbolos de origen tales como una imagen fija, un campo o trama de una secuencia de video, una rebanada de una imagen fija, una rebanada de un campo o trama de una secuencia de video, o una trama de muestras de audio, etc.

Dos o mas de los trenes de bits parciales para una cantidad de datos o todos los trenes de bits parciales para una cantidad de datos se pueden multiplexar para dar un paquete de datos. La estructura de un paquete de datos que contiene unos trenes de bits parciales multiplexados se ilustra en la figura 5. Es decir, el paquete de datos que se muestra en la figura 5 podna ser parte del tren intercalado intermedio 132 y 234, de forma respectiva.

El paquete de datos 300 consiste en un encabezamiento y una particion para los datos de cada tren de bits parcial (para la cantidad considerada de datos). El encabezamiento 300 del paquete de datos contiene indicaciones para la subdivision en particiones de (el resto de) el paquete de datos en segmentos de los datos de tren de bits 302. Ademas de las indicaciones para la subdivision en particiones, el encabezamiento puede contener una informacion adicional. Las indicaciones para la subdivision en particiones del paquete de datos pueden ser las ubicaciones del comienzo de los segmentos de datos en unidades de bits o bytes o multiples de bits o multiples de bytes. Las ubicaciones del comienzo de los segmentos de datos se pueden codificar como valores absolutos en el encabezamiento del paquete de datos, o bien en relacion con el comienzo del paquete de datos o bien en relacion con el final del encabezamiento o en relacion con el comienzo del paquete de datos previo. Las ubicaciones del comienzo de los segmentos de datos se pueden codificar de forma diferencial, es decir, solo la diferencia entre el comienzo real de un segmento de datos y una prediccion para el comienzo del segmento de datos se codifica. La prediccion se puede obtener sobre la base de una informacion ya conocida o transmitida tal como el tamano global del paquete de datos, el tamano del encabezamiento, el numero de segmentos de datos en el paquete de datos, la ubicacion del comienzo de segmentos de datos precedentes. La ubicacion del comienzo del primer paquete de datos puede no codificarse, sino inferirse sobre la base del tamano del encabezamiento de paquete de datos. En el lado de descodificador, las indicaciones de particion transmitidas se usan para obtener el comienzo de los segmentos de datos. Los segmentos de datos se usan entonces como trenes de bits parciales y los datos que estan contenidos en los segmentos de datos se alimentan a los descodificadores de contenedores correspondientes en orden secuencial.

Hay varias alternativas para multiplexar los trenes de bits parciales 12 en un paquete de datos. Una alternativa, la cual puede reducir la informacion conexa requerida, en particular para los casos en los que los tamanos de los trenes de bits parciales son muy similares, se ilustra en la figura 6. La cabida util del paquete de datos, es decir, el paquete de datos 310 sin su encabezamiento 311, se subdivide en particiones para dar unos segmentos 312 de una forma previamente definida. Como un ejemplo, la cabida util de paquete de datos se puede subdividir en particiones para dar unos segmentos del mismo tamano. Entonces cada segmento se asocia con un tren de bits parcial o con la primera parte de un tren de bits parcial 313. Si un tren de bits parcial es mayor que el segmento de datos asociado, su resto 314 se coloca en el espacio sin usar al final de otros segmentos de datos. Esto se puede realizar de una forma tal que la parte restante de un tren de bits se inserta en el orden inverso (comenzando a partir del final del

5

10

15

20

25

30

35

40

45

50

55

60

segmento de datos), que reduce la informacion conexa. La asociacion de los restos de los trenes de bits parciales con unos segmentos de datos y, cuando mas de un resto se anade a un segmento de datos, el punto de inicio para uno o mas de los restos se ha de senalizar en el interior del tren de bits, por ejemplo en el encabezamiento de paquete de datos.

Intercalacion de palabras de codigo de longitud variable

Para algunas aplicaciones, la multiplexacion que se ha descrito en lo que antecede de los trenes de bits parciales 12 (para una cantidad de sfmbolos de origen) en un paquete de datos puede tener las siguientes desventajas: Por un lado, para unos paquetes de datos pequenos, el numero de bits para la informacion conexa que se requiere para senalizar la subdivision en particiones se puede volver significativa en relacion con los datos reales en los trenes de bits parciales, lo que en ultima instancia reduce la eficiencia de codificacion. Por otro lado, la multiplexacion puede no ser adecuada para las aplicaciones que requieren un bajo retardo (por ejemplo, para aplicaciones de videoconferencia). Con la multiplexacion descrita, el codificador de PIPE no puede iniciar la transmision de un paquete de datos antes de que los trenes de bits parciales se hayan creado completamente, debido a que las ubicaciones del comienzo de las particiones no se conodan con anterioridad. Ademas, en general, el descodificador de PIPE ha de esperar hasta que este recibe el comienzo del ultimo segmento de datos antes de que este pueda iniciar la descodificacion de un paquete de datos. Para aplicaciones como sistemas de videoconferencia, estos retardos pueden sumarse a un retardo global adicional del sistema de varias imagenes de video (en particular para unas tasas de bits que se encuentran cerca de la tasa de bits de transmision y para codificadores / descodificadores que requieren casi el intervalo de tiempo entre dos imagenes para codificar / descodificar una imagen), que es cntico para tales aplicaciones. Con el fin de superar las desventajas para determinadas aplicaciones, el codificador de PIPE puede configurarse de una forma tal que las palabras de codigo que se generan mediante los dos o mas codificadores de contenedores se intercalan para dar un unico tren de bits. El tren de bits con las palabras de codigo intercaladas puede enviarse directamente al descodificador (cuando se desprecia un pequeno retardo de memoria intermedia, vease en lo sucesivo). En el lado de descodificador de PIPE, los dos o mas descodificadores de contenedores leen las palabras de codigo directamente a partir del tren de bits en el orden de descodificacion; la descodificacion se puede iniciar con el primer bit recibido. Ademas, no se requiere informacion conexa alguna para senalizar la multiplexacion (o intercalacion) de los trenes de bits parciales.

La estructura basica de un codificador de PIPE con una intercalacion de palabras de codigo se muestra en la figura 7. Los codificadores de contenedores 10 no escriben las palabras de codigo directamente en los trenes de bits parciales, sino que se conectan con una unica memoria intermedia de palabras de codigo 29, a partir de las cual se escriben palabras de codigo en el tren de bits 34 en el orden de codificacion. Los codificadores de contenedores 10 envfan solicitudes para una o mas nuevas entradas de memoria intermedia de palabras de codigo 28 a la memoria intermedia de palabras de codigo 29 y posteriormente envfan las palabras de codigo 30 a la memoria intermedia de palabras de codigo 29, que se almacenan en las entradas de memoria intermedia reservadas. Las palabras de codigo (en general de longitud variable) 31 de la memoria intermedia de palabras de codigo 29 se acceden por una unidad de escritura de palabras de codigo 32, que escribe los bits 33 correspondientes en el tren de bits producido 34. La memoria intermedia de palabras de codigo 29 opera como una memoria intermedia de tipo primero en entrar primero en salir; las entradas de palabra de codigo que se reservan con anterioridad se escriben con anterioridad en el tren de bits.

En una generalizacion adicional, son posibles multiples memorias intermedias de palabras de codigo y trenes de bits parciales 12, en donde el numero de memorias intermedias de palabras de codigo es menor que el numero de codificadores de contenedores. Un codificador de contenedores 10 reserva una o mas palabras de codigo en la memoria intermedia de palabras de codigo 29, mediante lo cual la reserva de las una o mas palabras de codigo en la memoria intermedia de palabras de codigo es desencadenada por determinados eventos en la memoria intermedia de contenedores conectada 8. La memoria intermedia de palabras de codigo 29 se puede operar de una forma tal que el descodificador de PIPE puede descodificar de forma instantanea el tren de bits 34 el cual se corresponde con 132 en la figura 1a y 134 en la figura 2, de forma respectiva. El orden de codificacion en el cual las palabras de codigo se escriben en el tren de bits es el mismo que el orden en el cual las palabras de codigo correspondientes se reservan en la memoria intermedia de palabras de codigo. Cada codificador de contenedores 10 puede reservar una palabra de codigo, con la reserva siendo desencadenado por un determinado evento en la memoria intermedia de contenedores conectada. Cada codificador de contenedores 10 puede reservar mas de una palabra de codigo, con la reserva siendo desencadenado por un determinado evento en la memoria intermedia de contenedores conectada. Los codificadores de contenedores 10 pueden reservar una cantidad diferente de palabras de codigo, en donde la cantidad de palabras de codigo que son reservadas por un codificador de contenedores particular puede ser dependiente del codificador de contenedores particular y / u otras propiedades del codificador de contenedores / memoria intermedia de contenedores particular (tal como la medida de probabilidad asociada, el numero de bits ya escritos, etc.).

La memoria intermedia de palabras de codigo puede operar tal como sigue. Si un nuevo contenedor 7 se envfa a una memoria intermedia de contenedores particular 8 y el numero de contenedores ya almacenados en la memoria

5

10

15

20

25

30

35

40

45

50

55

60

intermedia de contenedores es cero y en la actualidad no hay palabra de codigo alguna reservada en la memoria intermedia de palabras de codigo para el codificador de contenedores que se conecta con la memoria intermedia de contenedores particular, el codificador de contenedores conectado 10 envfa una solicitud a la memoria intermedia de palabras de codigo, mediante lo cual una o mas entradas de palabra de codigo se reservan en la memoria intermedia de palabras de codigo 29 para el codificador de contenedores particular. Las entradas de palabra de codigo pueden tener un numero variable de bits; un umbral superior para el numero de bits en una entrada de memoria intermedia viene dado por lo general por el tamano de palabra de codigo maximo para el codificador de contenedores correspondiente. La siguiente palabra de codigo o las siguientes palabras de codigo que se producen por el codificador de contenedores (para lo cual la entrada de palabra de codigo o entradas de palabra de codigo se han reservado) se almacenan en la entrada o entradas reservadas de la memoria intermedia de palabras de codigo. Si todas las entradas de memoria intermedia reservadas en la memoria intermedia de palabras de codigo para un codificador de contenedores particular se llenan con palabras de codigo y el siguiente contenedor se envfa a la memoria intermedia de contenedores que se conecta con el codificador de contenedores particular, una o mas nuevas palabras de codigo se reservan en la memoria intermedia de palabras de codigo para el codificador de contenedores particular, etc. La memoria intermedia de palabras de codigo 29 representa una memoria intermedia de tipo primero en entrar primero en salir de una cierta forma. Las entradas de memoria intermedia se reservan en orden secuencial. Las palabras de codigo para las que las entradas de memoria intermedia correspondientes se han reservado con anterioridad se escriben con anterioridad en el tren de bits. La unidad de escritura de palabras de codigo 32 comprueba el estatus de la memoria intermedia de palabras de codigo 29, o bien de forma continua o bien despues de que una palabra de codigo 30 se escriba en la memoria intermedia de palabras de codigo 29. Si la primera entrada de memoria intermedia contiene una palabra de codigo completa (es decir, la entrada de memoria intermedia no esta reservada, sino que incluye una palabra de codigo), la palabra de codigo 31 correspondiente y la entrada de memoria intermedia correspondiente se retiran de la memoria intermedia de palabras de codigo 20 y los bits de la palabra de codigo 33 se escriben en el tren de bits. Este proceso se repite hasta que la primera entrada de memoria intermedia no contiene una palabra de codigo (es decir, esta esta reservada o es libre). Al final del proceso de descodificacion, es decir, si se han procesado todos los sfmbolos de origen de la cantidad considerada de datos, se ha de evacuar la memoria intermedia de palabras de codigo. Para ese proceso de evacuacion, lo sucesivo es de aplicacion para cada memoria intermedia de contenedores / codificador de contenedores como primera etapa: Si la memoria intermedia de contenedores contiene, de hecho, unos contenedores, un contenedor con un valor particular o uno arbitrario se anade hasta que la secuencia de contenedores resultante representa una secuencia de contenedores que se asocia con una palabra de codigo (tal como se ha hecho notar en lo que antecede, una forma preferida de adicion de contenedores es anadir aquellos valores de contenedor que producen la palabra de codigo posible mas corta - o una de ellas - que se asocia con una secuencia de contenedores que contiene el para el contenido original de la memoria intermedia de contenedores como prefijo), entonces la palabra de codigo se escribe en la siguiente entrada de memoria intermedia reservada para el codificador de contenedores correspondiente (y la correspondiente) memoria intermedia de contenedores se vacfa. Si se ha reservado mas de una entrada de memoria intermedia para uno o mas codificadores de contenedores, la memoria intermedia de palabras de codigo puede seguir conteniendo entradas de palabra de codigo reservadas. En ese caso, estas entradas de palabra de codigo se llenan con unas palabras de codigo arbitrarias pero validas para los codificadores de contenedores correspondientes. Preferiblemente, se inserta la palabra de codigo valida mas corta o una de las palabras de codigo validas mas cortas (de haber una multitud). Por ultimo, todas las palabras de codigo restantes en la memoria intermedia de palabras de codigo se escriben en el tren de bits.

En la figura 8 se ilustran dos ejemplos para el estatus de la memoria intermedia de palabras de codigo. En el ejemplo (a), la memoria intermedia de palabras de codigo contiene 2 entradas que se llenan con una palabra de codigo y 5 entradas reservadas. Ademas, se marca la siguiente entrada de memoria intermedia libre. La primera entrada se llena con una palabra de codigo (es decir, el codificador de contenedores 2 acababa de escribir una palabra de codigo en una entrada previamente reservada). En la siguiente etapa, esta palabra de codigo se retirara de la memoria intermedia de palabras de codigo y se escribira en el tren de bits. Entonces, la primera palabra de codigo reservada para el codificador de contenedores 3 es la primera entrada de memoria intermedia, pero esta entrada no se puede retirar de la memoria intermedia de palabras de codigo, debido a que esta solo esta reservada, pero no se ha escrito palabra de codigo alguna en esta entrada. En el ejemplo (b), la memoria intermedia de palabras de codigo contiene 3 entradas que se llenan con una palabra de codigo y 4 entradas reservadas. La primera entrada se marca como reservada y, por lo tanto, la unidad de escritura de palabras de codigo no puede escribir una palabra de codigo en el tren de bits. A pesar de que 3 palabras de codigo estan contenidas en la memoria intermedia de palabras de codigo, la unidad de escritura de palabras de codigo ha de esperar hasta que se escriba una palabra de codigo en la primera entrada de memoria intermedia reservada para el codificador de contenedores 3. Observese que las palabras de codigo deben escribirse en el orden en el cual fueron reservadas, con el fin de ser capaces de invertir el proceso en el lado de descodificador (vease en lo sucesivo).

La estructura basica de un descodificador de PIPE con una intercalacion de palabras de codigo se muestra en la figura 9. Los descodificadores de contenedores 10 no leen las palabras de codigo directamente a partir de trenes de bits parciales separados, sino que estan conectados con una memoria intermedia de bits 38, a partir de la que las palabras de codigo 37 se leen en el orden de codificacion. Se debena hacer notar que la memoria intermedia de bits

5

10

15

20

25

30

35

40

45

50

55

60

38 no se requiere necesariamente, debido a que las palabras de codigo tambien se podnan leer directamente a partir del tren de bits. La memoria intermedia de bits 38 se incluye principalmente en la ilustracion para separar claramente diferentes aspectos de la cadena de procesamiento. Los bits 39 del tren de bits 40 con palabras de codigo intercaladas, lo que por lo tanto se corresponde con el tren de bits 234 en la figura 2, se insertan de forma secuencial en la memoria intermedia de bits 38, la cual representa una memoria intermedia de tipo primero en entrar primero en salir. Si un descodificador de contenedores particular 22 recibe una solicitud para una o mas secuencias de contenedores 35, el descodificador de contenedores 22 lee una o mas palabras de codigo 37 a partir de la memoria intermedia de bits 38 por medio de solicitudes para bits 36. El descodificador de PIPE puede descodificar de forma instantanea los sfmbolos de origen. Observese que el codificador de PIPE (tal como se ha descrito en lo que antecede) ha de asegurar, al operar de forma conveniente la memoria intermedia de palabras de codigo, que las palabras de codigo se escriben en el mismo orden en el tren de bits en el que estas son solicitadas por los descodificadores de contenedores. En el descodificador de PIPE, la totalidad del proceso de descodificacion es desencadenado por solicitudes para sfmbolos de origen. Parametros como el numero de palabras de codigo que son reservados en el lado de codificador por un codificador de contenedores particular y el numero de palabras de codigo que se leen por el descodificador de contenedores correspondiente han de ser los mismos.

En una generalizacion adicional, son posibles multiples memorias intermedias de palabras de codigo y trenes de bits parciales, en donde el numero de memorias intermedias de bits es menor que el numero de descodificadores de contenedores. Un descodificador de contenedores 22 lee una o mas palabras de codigo a partir de la memoria intermedia de bits 38 en un instante en el tiempo, mediante lo cual la lectura de las una o mas palabras de codigo a partir de la memoria intermedia de bits es desencadenada por determinados eventos en la memoria intermedia de contenedores conectada 20. El descodificador se puede operar de una forma tal que una o mas palabras de codigo se leen cuando una solicitud para un contenedor 19 se envfa a una memoria intermedia de contenedores particular 20 y la memoria intermedia de contenedores no contiene contenedor alguno. Pero tambien es posible desencadenar la lectura de palabras de codigo mediante otros eventos, por ejemplo si el numero de contenedores en la memoria intermedia de contenedores se encuentra por debajo de un umbral previamente definido. Cada descodificador de contenedores 22 puede leer una palabra de codigo, con la lectura siendo desencadenado por un determinado evento en la memoria intermedia de contenedores conectada. Como alternativa, cada descodificador de contenedores 22 puede leer mas de una palabra de codigo, con la lectura siendo desencadenado por un determinado evento en la memoria intermedia de contenedores conectada. Los descodificadores de contenedores 22 pueden ser lefdos una cantidad diferente de palabras de codigo, en donde la cantidad de palabras de codigo que se leen por un descodificador de contenedores particular puede ser dependiente del descodificador de contenedores particular y / u otras propiedades del descodificador de contenedores / memoria intermedia de contenedores particular (tal como la medida de probabilidad asociada, el numero de bits ya lefdos, etc.).

La lectura de palabras de codigo a partir de la memoria intermedia de bits se puede operar tal como sigue. Si una nueva solicitud de contenedor 19 se envfa a partir del selector de memoria intermedia de contenedores 18 a una memoria intermedia de contenedores particular 20 y el numero de contenedores en la memoria intermedia de contenedores es cero, el descodificador de contenedores conectado 22 lee una o mas palabras de codigo 37 a partir de la memoria intermedia de bits 38, por medio de solicitud de bit 36 en la memoria intermedia de bits 38. El descodificador de contenedores 22 convierte las palabras de codigo 37 lefdas en las secuencias de contenedores 21 y almacena estas secuencias de contenedores en la memoria intermedia de contenedores conectada 20. Como respuesta final a la solicitud para un contenedor 19, el contenedor insertado en primer lugar se retira de la memoria intermedia de contenedores 20 y se envfa al selector de memoria intermedia de contenedores 18. Como respuesta a las solicitudes de contenedor adicionales, los contenedores restantes en la memoria intermedia de contenedores son removed hasta que la memoria intermedia de contenedores esta vada. Una solicitud de contenedor adicional desencadena que el descodificador de contenedores lea una o mas nuevas palabras de codigo a partir de la memoria intermedia de bits, etc. La memoria intermedia de bits 38 representa una memoria intermedia de tipo primero en entrar primero en salir de un tamano previamente definido y se llena continuamente con los bits 39 a partir del tren de bits 40. Con el fin de asegurar que las palabras de codigo se escriben en el tren de bits de la misma forma que estas son solicitadas por el proceso de descodificacion, la memoria intermedia de palabras de codigo en el lado de codificador se puede operar de la forma que se ha descrito en lo que antecede.

Por lo tanto, cada uno de la pluralidad de descodificadores por entropfa puede ser un descodificador de longitud variable que esta configurado para poner en correspondencia palabras de codigo de longitudes fijas con unas secuencias de sfmbolos de longitudes variables, y una entrada de palabra de codigo tal como la salida de la memoria intermedia de palabras de codigo 43 puede proporcionarse para recibir un unico tren de palabras de codigo intercaladas. La pluralidad de descodificadores por entropfa 22 se pueden configurar para recuperar las palabras de codigo de la entrada de palabra de codigo en un orden secuencial dependiendo de un orden en el cual los sfmbolos de la secuencia de sfmbolos que se va a reconstruir como recuperada por el selector 18 a partir de la pluralidad de descodificadores por entropfa dan como resultado una nueva secuencia de sfmbolos que va a ponerse en correspondencia a partir de una nueva palabra de codigo en los descodificadores por entropfa respectivos.

Intercalacion de palabras de codigo de longitud variable con una restriccion de retardo baja

5

10

15

20

25

30

35

40

45

50

55

60

La intercalacion de palabras de codigo descrita para la codificacion de PIPE no requiere que se envfe informacion alguna de subdivision en particiones como informacion conexa. Y debido a que las palabras de codigo se intercalan en el tren de bits, el retardo es en general pequeno. No obstante, no se garantiza que se obedezca una restriccion de retardo particular (por ejemplo, especificada por un numero maximo de bits que se almacenan en la memoria intermedia de palabras de codigo). Ademas, el tamano de memoria intermedia requerido para la memoria intermedia de palabras de codigo se puede volver, en teona, muy grande. Cuando se considera el ejemplo en la figura 8(b), podna ser posible que no se enviara contenedor adicional alguno a la memoria intermedia de contenedores 3 y, por lo tanto, el codificador de contenedores 3 no enviara palabra de codigo nueva alguna a la memoria intermedia de palabras de codigo hasta que se aplique el proceso de evacuacion al final del paquete de datos. Entonces todas las palabras de codigo para los codificadores de contenedores 1 y 2 tendnan que esperar hasta el final del paquete de datos, antes de que estas se puedan escribir en el tren de bits. Este inconveniente puede sortearse mediante la adicion de un mecanismo adicional al proceso de codificacion de PIPE (y tambien al proceso de descodificacion de PIPE tal como se describe posteriormente). El concepto basico de ese mecanismo adicional es que si una medida en relacion con el retardo o un lfmite superior del retardo (vease en lo sucesivo) supera un umbral especificado, la primera entrada de memoria intermedia reservada se llena mediante la evacuacion de la memoria intermedia de contenedores correspondiente (usando un mecanismo similar al del final de un paquete de datos). Mediante un mecanismo de este tipo, el numero de entradas de memoria intermedia en espera se reduce hasta que la medida de retardo asociada es menor que el umbral especificado. En el lado de descodificador, se han de descartar los contenedores que se han insertado en el lado de codificador con el fin de obedecer la restriccion de retardo. Para este descarte de contenedores se puede usar basicamente el mismo mecanismo que en el lado de codificador. En lo sucesivo se describen dos posibilidades para un control de retardo de este tipo.

En una posibilidad, la medida para el retardo (o un lfmite superior del retardo) es el numero de entradas de memoria intermedia activas en la memoria intermedia de palabras de codigo, en donde el numero de entradas de memoria intermedia activas es el numero de entradas de memoria intermedia reservadas mas el numero de entradas de memoria intermedia que contienen palabras de codigo. Observese que la primera entrada de memoria intermedia es siempre una entrada de memoria intermedia reservada o una entrada de memoria intermedia libre, debido a que si la primera entrada de memoria intermedia contiene una palabra de codigo, esta palabra de codigo se escribe en el tren de bits. Si por ejemplo, el maximo retardo de memoria intermedia admitido (segun sea determinado por la aplicacion) es D bits y el tamano de palabra de codigo maximo para todos los codificadores de contenedores es L, un lfmite inferior para el numero maximo de palabras de codigo que puede estar contenido en la memoria intermedia de palabras de codigo sin violar la restriccion de retardo se puede calcular por N = D / L. La medida de retardo D en bits no se requiere por el sistema, pero el numero maximo de palabras de codigo N ha de ser conocido tanto por el codificador como por el descodificador. El numero maximo de entradas de memoria intermedia de palabras de codigo N puede estar fijado por la aplicacion. Como alternativa, el numero maximo de entradas de memoria intermedia de palabras de codigo N se puede senalizar en el interior del tren de bits, por ejemplo, en el encabezamiento del paquete de datos (o el encabezamiento de rebanada) o en un conjunto de parametros, el cual se incluye en el tren de bits. Si un codificador de contenedores 10 envfa una solicitud para la reserva de una o mas nuevas entradas de memoria intermedia a la memoria intermedia de palabras de codigo 29, el siguiente proceso se ejecuta antes de que se reserve una nueva entrada de memoria intermedia de palabras de codigo (es decir, se ejecuta multiples veces si multiples entradas de memoria intermedia de palabras de codigo son reservadas por una solicitud): Si el numero de entradas de memoria intermedia activas en la actualidad mas 1 (teniendo en cuenta la entrada de memoria intermedia que se reservara a continuacion) es mayor que el numero maximo de entradas de memoria intermedia de palabras de codigo N, la primera entrada de memoria intermedia (la cual esta reservada) se evacua por el proceso que se describe en lo sucesivo hasta que el numero de entradas de memoria intermedia activas en la actualidad mas 1 sea menor que o igual al numero maximo de entradas de memoria intermedia de palabras de codigo N. La evacuacion de una entrada de memoria intermedia reservada es similar a la evacuacion al final de un paquete de datos: El codificador de contenedores 10 que ha reservado la primera entrada de memoria intermedia correspondiente se evacua mediante la adicion de contenedores con unos valores particulares o arbitrarios a la memoria intermedia de contenedores conectada 8 hasta que la secuencia de contenedores resultante representa una secuencia de contenedores que se asocia con una palabra de codigo, entonces la palabra de codigo se escribe en la entrada de memoria intermedia reservada y, en ultima instancia, se anade al tren de bits (al tiempo que se vacfa la memoria intermedia de contenedores y se retira la entrada de memoria intermedia previamente reservada). Tal como se ha mencionado en lo que antecede, una forma preferida para anadir contenedores a la memoria intermedia de contenedores es anadir aquellos contenedores que producen la palabra de codigo posible mas corta. En el lado de descodificador, se ejecuta un proceso similar para descartar los contenedores que se han anadido para obedecer la restriccion de retardo. Por lo tanto, el descodificador mantiene un contador C que recuenta las palabras de codigo que se han lefdo a partir de la memoria intermedia de bits (este contador puede mantenerse en la memoria intermedia de bits). Este contador C se inicializa (por ejemplo, con cero) en el comienzo de la descodificacion de un paquete de datos y se incrementa en uno despues de que se lea una palabra de codigo. Ademas, cada descodificador de contenedores 22 contiene un contador Cx, que almacena el valor del contador de palabras de codigo C antes de que la ultima palabra de codigo sea lefda por el descodificador de contenedores 22 correspondiente. Es decir, cuando un descodificador de contenedores particular 22 lee una nueva palabra de codigo,

5

10

15

20

25

30

35

40

45

50

55

60

su contador Cx se establece igual a C como una primera etapa y entonces la palabra de codigo se lee a partir de la memoria intermedia de bits. Cuando una solicitud para un contenedor 19 se env^a a una memoria intermedia de contenedores particular 20 y la diferencia (C - Cx) entre el contador de palabras de codigo global C y el contador Cx del descodificador de contenedores conectado 22 es mayor que el numero maximo de entradas de memoria intermedia de palabras de codigo N, todos los contenedores que se almacenan en la actualidad en la memoria intermedia de contenedores particular 20 se descartan y se ignoran. Ademas de esa etapa adicional, la descodificacion se opera tal como se ha descrito en lo que antecede. Si la memoria intermedia de contenedores 20 a la cual se envfa una solicitud para un contenedor 19 esta vada (o bien debido a que ya se han retirado todos los contenedores o bien debido a que el mecanismo de bajo retardo descarto todos los contenedores en la primera etapa despues de que se haya recibido la solicitud de contenedor), el descodificador de contenedores conectado 22 lee una o mas nuevas palabras de codigo a partir de la memoria intermedia de bits 38 etc.

La medida para el retardo (o un lfmite superior del retardo) puede ser la suma de las longitudes de palabra de codigo maximas para las entradas de memoria intermedia activas en la memoria intermedia de palabras de codigo, en donde la longitud de palabra de codigo maxima para una entrada de memoria intermedia particular depende del contenedor descodificado que se asocia con esa entrada de memoria intermedia. Como ilustracion, las longitudes de palabra de codigo maximas para las entradas de memoria intermedia estan indicadas en los ejemplos en 6. Observese de nuevo que la primera entrada de memoria intermedia es siempre una entrada de memoria intermedia reservada o una entrada de memoria intermedia libre, debido a que si la primera entrada de memoria intermedia contiene una palabra de codigo, esta palabra de codigo se escribe en el tren de bits. Sea el maximo retardo de memoria intermedia admitido (segun sea determinado por la aplicacion) de D bits. Este maximo retardo de memoria intermedia D ha de ser conocido tanto por el codificador como por el descodificador. El maximo retardo de memoria intermedia D puede estar fijado por la aplicacion. El maximo retardo de memoria intermedia D se puede senalizar en el interior del tren de bits, por ejemplo, en el encabezamiento del paquete de datos (o el encabezamiento de rebanada) o en un conjunto de parametros, el cual se incluye en el tren de bits. Este se puede senalizar en unidades de bits, o bytes, o un multiplo de bits, o un multiplo de bytes. Si un codificador de contenedores 10 envfa una solicitud para la reserva de una o mas nuevas entradas de memoria intermedia a la memoria intermedia de palabras de codigo 29, el siguiente proceso se ejecuta antes de que se reserve una nueva entrada de memoria intermedia de palabras de codigo (es decir, se ejecuta multiples veces si multiples entradas de memoria intermedia de palabras de codigo son reservadas por una solicitud).

Si la suma de las longitudes de palabra de codigo maximas para todas las entradas de memoria intermedia activas en la actualidad mas la longitud de palabra de codigo maxima para la entrada de memoria intermedia que se reservara es mayor que el maximo retardo de memoria intermedia D, la primera entrada de memoria intermedia (la cual esta reservada) se evacua por el proceso que se ha descrito en lo que antecede hasta que la suma de las longitudes de palabra de codigo maximas para todas las entradas de memoria intermedia activas mas la longitud de palabra de codigo maxima para la entrada de memoria intermedia que se reservara es menor que o igual al maximo retardo de memoria intermedia D. Como un ejemplo, considerese el ejemplo en la figura 8(b). La suma de las longitudes de palabra de codigo maximas para todas las entradas de memoria intermedia activas en la actualidad es 29. Supongase que el maximo retardo de memoria intermedia D se establece igual a 32. Si la siguiente entrada de memoria intermedia es reservada por el codificador de contenedores 2 para el que la longitud de palabra de codigo maxima es igual a 3, la primera entrada de memoria intermedia no se evacua, debido a que 29 + 3 no es mayor que 32. Pero si la siguiente entrada de memoria intermedia es reservada por el codificador de contenedores 1 para el que la longitud de palabra de codigo maxima es igual a 7, la primera entrada de memoria intermedia se evacua, debido a que 29 + 7 es mayor que 32. La evacuacion de la entrada de memoria intermedia reservada se realiza tal como se ha descrito en lo que antecede (mediante la adicion de un contenedor con unos valores particulares o arbitrarios a la memoria intermedia de contenedores correspondiente).

En el lado de descodificador, se ejecuta un proceso similar para descartar los contenedores que se han anadido para obedecer la restriccion de retardo. Por lo tanto, el descodificador mantiene un contador C que recuenta la longitud de palabra de codigo maxima para las palabras de codigo que se han lefdo a partir de la memoria intermedia de bits (este contador puede mantenerse en la memoria intermedia de bits). Observese que las longitudes de palabra de codigo maximas que estan asociadas con diferentes descodificadores de contenedores pueden ser diferentes. El contador C se inicializa (por ejemplo, con cero) en el comienzo de la descodificacion de un paquete de datos y este se incrementa despues de que se lea una palabra de codigo. Este contador no se incrementa en la longitud real de las palabras de codigo lefdas, sino en su longitud maxima. Es decir, si una palabra de codigo se lee por un descodificador de contenedores particular y la longitud de palabra de codigo maxima que se asocia con la tabla de palabras de codigo que es usada por el descodificador de contenedores particular es Lx (un descodificador de contenedores diferente puede asociarse con una longitud de palabra de codigo maxima diferente), el contador C se incrementa en Lx. Ademas del contador global C, cada descodificador de contenedores 22 contiene un contador Cx, que almacena el valor del contador de palabras de codigo C antes de que la ultima palabra de codigo sea lefda por el descodificador de contenedores 22 correspondiente. Es decir, cuando un descodificador de contenedores particular 22 lee una nueva palabra de codigo, su contador Cx se establece igual a C como una primera etapa y entonces la palabra de codigo se lee a partir de la memoria intermedia de bits. Cuando una solicitud

5

10

15

20

25

30

35

40

45

50

55

60

para un contenedor 19 se envfa a una memoria intermedia de contenedores particular 20 y la diferencia (C - Cx) entre el contador global C y el contador Cx del descodificador de contenedores conectado 22 es mayor que el maximo retardo de memoria intermedia D, todos los contenedores que estan almacenados en la actualidad en la memoria intermedia de contenedores particular 20 se descartan y se ignoran. Ademas de esa etapa adicional, la descodificacion se opera tal como se ha descrito en lo que antecede. Si la memoria intermedia de contenedores 20 a la cual se envfa una solicitud para un contenedor 19 esta vada (o bien debido a que ya se han retirado todos los contenedores o debido a que el mecanismo de bajo retardo descarto todos los contenedores en la primera etapa despues de que se haya recibido la solicitud de contenedor), el descodificador de contenedores conectado 22 lee una o mas nuevas palabras de codigo a partir de la memoria intermedia de bits 38 etc.

Por lo tanto, la pluralidad de descodificadores por entropfa 22 y el selector 18 se pueden configurar para descartar de forma intermitente sufijos de secuencias de sfmbolos con el fin de no participar en la formacion de la secuencia de sfmbolos que se va a reconstruir 29. El descarte de forma intermitente se puede realizar en unos eventos en los que un numero de palabras de codigo que se han recuperado a partir de la entrada de palabra de codigo por la pluralidad de descodificadores por entropfa entre dos recuperaciones de palabra de codigo consecutivas de un descodificador por entropfa respectivo a partir de la entrada de palabra de codigo, satisface un criterio previamente determinado. La pluralidad de codificadores por entropfa y la memoria intermedia de palabras de codigo, a su vez, puede configurarse para ampliar de forma intermitente unos sfmbolos reenviados en la actualidad pero aun no puestos en correspondencia a unas secuencias de sfmbolos validas mediante unos sfmbolos de “no importa” que tienen los sfmbolos reenviados en la actualidad pero aun no puestos en correspondencia como prefijo, poner en correspondencia las secuencias de sfmbolos asf ampliadas con palabras de codigo, introducir las palabras de codigo asf obtenidas en las entradas de palabra de codigo reservadas y evacuar las entradas de palabra de codigo. La ampliacion de forma intermitente, la entrada y la evacuacion pueden tener lugar en unos eventos en los que un numero de entradas de palabra de codigo reservadas mas un numero de entradas de palabra de codigo que tienen palabras de codigo introducidas en las mismas satisface un criterio previamente determinado. Los criterios previamente determinados pueden tener en cuenta las longitudes maximas de palabras de codigo de la pluralidad de pares de codificador / descodificador.

Para algunas arquitecturas, la forma que se ha descrito en lo que antecede de intercalacion de palabras de codigo podna dar como resultado un inconveniente en terminos de la complejidad de descodificacion. Tal como se ilustra en la figura 9, todos los descodificadores de contenedores 22 leen palabras de codigo (en el caso general, palabras de codigo de longitud variable) a partir de una unica memoria intermedia de bits 38. La lectura de las palabras de codigo no se puede realizar en paralelo, debido a que la palabra de codigo debe leerse en el orden correcto. Eso quiere decir que un descodificador de contenedores particular ha de esperar hasta que otros descodificadores de contenedores acaban la lectura de palabras de codigo. Y cuando la complejidad de la lectura de las palabras de codigo de longitud variable es significativa en relacion con el resto del proceso de descodificacion (parcialmente paralelizado), este acceso de las palabras de codigo de longitud variable puede ser un cuello de botella para la totalidad del proceso de descodificacion. Hay algunas variaciones que pueden emplearse para reducir la complejidad del acceso a partir de la unica memoria intermedia de bits, unas pocas de estas se describiran en lo sucesivo. Existe, por ejemplo, un unico conjunto de palabras de codigo (que representa por ejemplo un codigo de prefijo libre de redundancia) y el conjunto de palabras de codigo que se usa para cada descodificador de contenedores 22 es un subconjunto del unico conjunto de palabras de codigo. Observese que diferentes descodificadores de contenedores 22 pueden usar diferentes subconjuntos del unico conjunto de palabras de codigo. Incluso si los conjuntos de palabras de codigo que se usan por algunos de los descodificadores de contenedores 22 son los mismos, su asociacion con secuencias de contenedores es diferente para diferentes descodificadores de contenedores 22. El mismo conjunto de palabras de codigo se puede usar para todos los descodificadores de contenedores 22. Si se tiene un unico conjunto de palabras de codigo que incluye los conjuntos de palabras de codigo para todos los descodificadores de contenedores como subconjuntos, el analisis sintactico de las palabras de codigo se puede realizar fuera de los descodificadores de contenedores, lo que puede reducir la complejidad del acceso a palabras de codigo. El proceso de codificacion de PIPE no se modifica en relacion con el proceso que se ha descrito en lo que antecede. El proceso de descodificacion de PIPE modificado se ilustra en la figura 10. Un unico lector de palabras de codigo se alimenta con los bits 46 a partir del tren de bits 40 y analiza sintacticamente las palabras de codigo - en general de longitud variable. Las palabras de codigo lefdas 44 se insertan en una memoria intermedia de palabras de codigo 43, la cual representa una memoria intermedia de tipo primero en entrar primero en salir. Un descodificador de contenedores 22 envfa una solicitud para una o mas palabras de codigo 41 a la memoria intermedia de palabras de codigo 43 y como respuesta a esta solicitud, las una o mas palabras de codigo se retiran de la memoria intermedia de palabras de codigo (en orden secuencial) y se envfan al descodificador de contenedores 22 correspondiente. Observese que en este caso, el potencialmente complejo analisis sintactico de palabras de codigo se puede realizar en un proceso de segundo plano y no es necesario que este espere a los descodificadores de contenedores. Los descodificadores de contenedores acceden a unas palabras de codigo ya analizadas sintacticamente, el potencialmente complejo analisis sintactico de palabras de codigo ha dejado de ser parte de una solicitud a la memoria intermedia global. En su lugar, unas palabras de codigo ya analizadas sintacticamente se envfan a los descodificadores de contenedores, que tambien pueden implementarse de una forma tal que solo se envfan indices de palabras de codigo a los descodificadores de

5

10

15

20

25

30

35

40

45

50

55

60

contenedores.

Intercalacion de secuencias de bits de longitud fija

Una forma adicional de reducir la complejidad del descodificador de PIPE puede conseguirse cuando los descodificadores de contenedores 22 no leen palabras de codigo de longitud variable a partir de la memoria intermedia de bits global 38 sino que, en su lugar, siempre leen unas secuencias de longitud fija de bits a partir de la memoria intermedia de bits global 38 y anaden estas secuencias de longitud fija de bits a una memoria intermedia de bits local, en donde cada descodificador de contenedores 22 esta conectado con una memoria intermedia de bits local separada. Las palabras de codigo de longitud variable se leen entonces a partir de la memoria intermedia de bits local. Por lo tanto, el analisis sintactico de palabras de codigo de longitud variable se puede realizar en paralelo, solo el acceso de secuencias de longitud fija de bits se ha de realizar de una forma sincronizada, pero un acceso de este tipo de secuencias de longitud fija de bits es por lo general muy rapido, de tal modo que la complejidad de descodificacion global puede reducirse para algunas arquitecturas. El numero fijado de contenedores que se envfan a una memoria intermedia de bits local particular puede ser diferente para diferentes memorias intermedias de bits locales y tambien puede variar con el tiempo, dependiendo de determinados parametros como eventos en el descodificador de contenedores, la memoria intermedia de contenedores o la memoria intermedia de bits. No obstante, el numero de bits que se leen por un proceso particular no depende de los bits reales que se leen durante el acceso particular, que es la diferencia importante para la lectura de palabras de codigo de longitud variable. La lectura de las secuencias de longitud fija de bits es desencadenada por determinados eventos en las memorias intermedias de contenedores, los descodificadores de contenedores o las memorias intermedias de bits locales. Como un ejemplo, es posible solicitar la lectura de una nueva secuencia de longitud fija de bits cuando el numero de bits que se encuentran presentes en una memoria intermedia de bits conectada cae por debajo de un umbral previamente definido, en donde se pueden usar diferentes valores de umbral para diferentes memorias intermedias de bits. En el codificador, se ha de asegurar que las secuencias de longitud fija de contenedores se insertan en el mismo orden en el tren de bits, en el que se leen a partir del tren de bits en el lado de descodificador. Tambien es posible combinar esta intercalacion de secuencias de longitud fija con un control de retardo bajo similar a los que se han explicado en lo que antecede. En lo sucesivo, se describe una forma para la intercalacion de secuencias de longitud fija de bits.

La figura 11 muestra una ilustracion de una estructura de codificador de PIPE que intercala secuencias de longitud fija de bits para dos o mas codificadores de contenedores. En contraste con la figura 7, los codificadores de contenedores 10 no estan conectados con una unica memoria intermedia de palabras de codigo. En su lugar, cada codificador de contenedores 10 esta conectado con una memoria intermedia de bits 48 separada, que almacena bits para el tren de bits parcial correspondiente. Todas las memorias intermedias de bits 48 estan conectadas con una memoria intermedia de bits global 51. La memoria intermedia de bits global 51 esta conectada con una unidad de escritura de bits 53, la cual retira los bits 52 en el orden de codificacion / descodificacion de la memoria intermedia de bits global y escribe los bits retirados 54 en el tren de bits 55. Tras un determinado evento en una memoria intermedia de bits particular 48 o el codificador de contenedores conectado 10 o la memoria intermedia de contenedores 8, la memoria intermedia de bits 48 envfa una solicitud 49 a la memoria intermedia de bits global 51 mediante la cual se reserva un determinado numero de bits en la memoria intermedia de bits global 51. Las solicitudes para la reserva de las secuencias de bits de longitud fija 49 se procesan en orden secuencial. La memoria intermedia de bits global 51 representa una memoria intermedia de tipo primero en entrar primero en salir de una cierta forma; los bits que se reservan con anterioridad se escriben con anterioridad en el tren de bits. Se debena hacer notar que diferentes memorias intermedias de bits 48 pueden reservar una cantidad diferente de bits, que tambien puede variar con el tiempo sobre la base de unos sfmbolos ya codificados; pero el numero de bits que son reservados por una solicitud particular se conoce en el momento en el que se envfa la solicitud a la memoria intermedia de bits global.

En particular, las memorias intermedias de bits 48 y la memoria intermedia de bits global 51 se operan tal como se describe en lo sucesivo. La cantidad de bits que es reservada por una memoria intermedia de bits particular 48 se indica como Nx. Este numero de bits Nx puede ser diferente para diferentes memorias intermedias de bits 48 y tambien puede variar con el tiempo. El numero de bits Nx que son reservados por una memoria intermedia de bits particular 48 puede ser fijo con el tiempo. Las reservas para un numero fijado Nx de bits 49 se desencadenan sobre la base del numero de bits Mx en las memorias intermedias de bits 48, el numero de bits Nx para las solicitudes de reserva, y la longitud de palabra de codigo maxima Lx asociada. Observese que cada codificador de contenedores 10 puede asociarse con una longitud de palabra de codigo maxima Lx diferente. Si un contenedor 7 se envfa a una memoria intermedia de contenedores particular 8, y la memoria intermedia de contenedores particular 8 esta vacfa, y se reserva no mas de una secuencia de Nx bits en la memoria intermedia de bits global para la memoria intermedia de bits 48 que esta conectada con la memoria intermedia de contenedores particular (por medio de un codificador de contenedores), y la diferencia Nx - Mx entre el numero Nx de bits que son reservados por una solicitud de reserva de la memoria intermedia de bits 48 que esta conectada (por medio de un codificador de contenedores) con la memoria intermedia de contenedores particular 8 y el numero de bits Mx que se encuentran presentes en la actualidad en esta memoria intermedia de bits 48 es menor que la longitud de palabra de codigo maxima Lx que se asocia con el

5

10

15

20

25

30

35

40

45

50

55

60

codificador de contenedores 10 correspondiente, la memoria intermedia de bits conectada 49 env^a una solicitud 49 para la reserva de Nx bits a la memoria intermedia de bits global 51. La memoria intermedia de bits global 51 reserva Nx bits para la memoria intermedia de bits particular 48 e incrementa su puntero para la siguiente reserva. Despues de que se hayan reservado los Nx bits en la memoria intermedia de bits global, el contenedor 7 se almacena en la memoria intermedia de contenedores 8. Si este unico contenedor ya representa, de hecho, una secuencia de contenedores que se asocia con una palabra de codigo, el codificador de contenedores 10 retira este contenedor de la memoria intermedia de contenedores 8 y escribe la palabra de codigo 47 correspondiente en la memoria intermedia de bits conectada 48. De lo contrario (este unico contenedor ya representa, de hecho, una secuencia de contenedores que se asocia con una palabra de codigo), unos contenedores adicionales 7 se aceptan por la memoria intermedia de contenedores particular 8 hasta que la memoria intermedia de contenedores 8 contiene una secuencia de contenedores que se asocia con una palabra de codigo. En este caso, el codificador de contenedores conectado 10 retira la secuencia de contenedores 9 de la memoria intermedia de contenedores 8 y escribe la palabra de codigo 47 correspondiente en la memoria intermedia de bits conectada 48. Si el numero resultante de bits Mx en la memoria intermedia de bits 48 es mayor que o igual al numero de bits reservados Nx, los Nx bits que se escribieron en primer lugar en la memoria intermedia de bits 48 se insertan en el espacio previamente reservado en la memoria intermedia de bits global 51. Para el siguiente contenedor 7 que se envfa a la memoria intermedia de contenedores particular 8, se ejecuta el mismo proceso que se ha especificado en lo que antecede; es decir, se comprueba en primer lugar si se ha de reservar un nuevo numero de Nx bits en la memoria intermedia de bits global (si Nx - Mx es menor que Lx) y entonces el contenedor se inserta en la memoria intermedia de contenedores 8, etc. La unidad de escritura de bits escribe las secuencias de bits de longitud fija de la memoria intermedia de bits global en el orden en el cual se han reservado estas. Si la primera entrada de longitud fija en la memoria intermedia de bits global 51 contiene una secuencia de bits de longitud fija que se ha insertado en la practica en la memoria intermedia de bits global (es decir, no solo se reserva), la unidad de escritura de bits 53 retira los bits para esta secuencia de bits 52 de la memoria intermedia de bits global 51 y escribe los bits 54 en el tren de bits. Este proceso se repite hasta que la primera entrada de longitud fija en la memoria intermedia de bits global representa una entrada reservada o una libre. Si la primera entrada de longitud fija en la memoria intermedia de bits global representa una entrada reservada, la unidad de escritura de bits 53 espera hasta que esta entrada se ha llenado con bits reales antes de que esta escriba unos bits adicionales 54 en el tren de bits 55.

Al final de un paquete de datos, las memorias intermedias de contenedores se evacuan tal como se ha descrito en lo que antecede. Ademas, las memorias intermedias de bits se han de evacuar mediante la adicion de bits con un valor particular o uno arbitrario hasta que todas las entradas de memoria intermedia reservadas en la memoria intermedia de bits global se han llenado y escrito en el tren de bits.

En la figura 12 se ilustran dos ejemplos para el posible estatus de la memoria intermedia de bits global 51. En el ejemplo (a), se ilustra un caso en el que diferentes memorias intermedias de bits / codificadores de contenedores reservan un numero diferente de bits. La memoria intermedia de bits global contiene 3 entradas con unas secuencias de bits de longitud fija escritas en la practica y 4 entradas con unas secuencias de bits de longitud fija reservadas. La primera entrada de longitud fija ya contiene bits reales (los cuales han de estar recien insertados por la memoria intermedia de bits / codificador de contenedores 2); esta entrada (es decir, los 8 bits correspondientes) puede retirarse y escribirse en el tren de bits. La siguiente entrada reserva 10 bits para el codificador de contenedores 3, pero aun no se han insertado bits reales. Esta entrada no se puede escribir en el tren de bits; ha de esperarse hasta que se han insertado los bits reales. En el segundo ejemplo (b), todas las memorias intermedias de bits / codificadores de contenedores reservaron el mismo numero de bits (8 bits). La memoria intermedia de bits global contiene 4 reservas para secuencias de 8 bits y 3 secuencias de 8 bits escritas en la practica. La primera entrada contiene una reserva para 8 bits para el codificador de contenedores 3. Antes de que se pueda escribir algun bit nuevo en el tren de bits, la unidad de escritura de bits ha de esperar hasta que la memoria intermedia de bits / codificador de contenedores 3 escriba los valores reales de los 8 bits en esta entrada reservada.

La figura 13 muestra una ilustracion de una estructura de descodificador de PIPE que intercala secuencias de longitud fija de bits. En contraste con la figura 9, los descodificadores de contenedores 22 no estan conectados con una unica memoria intermedia de bits. En su lugar, cada descodificador de contenedores 22 esta conectado con una memoria intermedia de bits 58 separada, que almacena bits a partir del tren de bits parcial correspondiente. Todas las memorias intermedias de bits 58 estan conectadas con una memoria intermedia de bits global 61. Los bits 62 a partir del tren de bits 63 se insertan en la memoria intermedia de bits global 61. Tras un determinado evento en una memoria intermedia de bits particular 58 o el descodificador de contenedores conectado 22 o la memoria intermedia de contenedores 20, la memoria intermedia de bits 58 envfa una solicitud 59 a la memoria intermedia de bits global 61 mediante lo cual una secuencia de longitud fija de bits 60 se retira de la memoria intermedia de bits global 61 y se inserta en la memoria intermedia de bits particular 58. Las solicitudes para las secuencias de bits de longitud fija 59 se procesan en orden secuencial. La memoria intermedia de bits global 61 representa una memoria intermedia de tipo primero en entrar primero en salir; los bits que se insertan con anterioridad en la memoria intermedia de bits global se retiran con anterioridad. Se debena hacer notar que diferentes memorias intermedias de bits 58 pueden solicitar una cantidad diferente de bits, que tambien puede variar con el tiempo sobre la base de unos sfmbolos ya descodificados; pero el numero de bits que son solicitados por una solicitud particular se conoce en el momento en

5

10

15

20

25

30

35

40

45

50

55

60

el que se envfa la solicitud a la memoria intermedia de bits global. Se debena hacer notar que la memoria intermedia de bits global 61 no se requiere necesariamente, debido a que las palabras de codigo tambien se podnan leer directamente a partir del tren de bits. La memoria intermedia de bits global 61 se incluye principalmente en la ilustracion para separar claramente diferentes aspectos de la cadena de procesamiento.

Las memorias intermedias de bits 58 y la memoria intermedia de bits global 61 se pueden operar tal como se describe en lo sucesivo. La cantidad de bits que son solicitados y lefdos por una memoria intermedia de bits particular 58 se indica como Nx, esta es igual a la cantidad de bits que se escribe en la memoria intermedia de bits global por la memoria intermedia de bits correspondiente en el lado de codificador. Este numero de bits Nx puede ser diferente para diferentes memorias intermedias de bits 58 y tambien puede variar con el tiempo. Preferiblemente, el numero de bits Nx que son solicitados y lefdos por una memoria intermedia de bits particular 58 puede ser fijo con el tiempo. La lectura de un numero fijado Nx de bits 60 se desencadena sobre la base del numero de bits Mx en la memoria intermedia de bits 58 y la longitud de palabra de codigo maxima Lx asociada. Observese que cada descodificador de contenedores 22 puede asociarse con una longitud de palabra de codigo maxima Lx diferente. Si una solicitud para un contenedor 19 se envfa a una memoria intermedia de contenedores particular 20, y la memoria intermedia de contenedores particular 20 esta vada, y el numero Mx de bits en la memoria intermedia de bits 58 que esta conectada (por medio de un descodificador de contenedores) con la memoria intermedia de contenedores particular 20 es menor que la longitud de palabra de codigo maxima Lx que se asocia con el descodificador de contenedores 22 correspondiente, la memoria intermedia de bits conectada 58 envfa una solicitud 59 para una nueva secuencia de Nx bits a la memoria intermedia de bits global 61. Como respuesta a esta solicitud, los primeros Nx bits se retiran de la memoria intermedia de bits global 61 y esta secuencia de Nx bits 60 se envfa a la memoria intermedia de bits 58 a partir de la cual se envio la solicitud. Por ultimo, esta secuencia de Nx bits se anade a la memoria intermedia de bits 58 correspondiente. Entonces la siguiente palabra de codigo 57 se lee a partir de esta memoria intermedia de bits, y el descodificador de contenedores conectado 22 inserta la secuencia de contenedores asociada 21 en la memoria intermedia de contenedores conectada 20. Como respuesta final a la solicitud original para un contenedor 19, el primer contenedor se retira de la memoria intermedia de contenedores 20 y este contenedor descodificado 25 se envfa al selector de memoria intermedia de contenedores 18. Cuando la siguiente solicitud de contenedor 19 se envfa a la memoria intermedia de contenedores particular 20 y la memoria intermedia de contenedores no esta vada, el siguiente bit se retira de la memoria intermedia de contenedores 20. Si la memoria intermedia de contenedores esta vada pero el numero Mx de bits en la memoria intermedia de bits conectada 58 es mayor que o igual a la longitud de palabra de codigo maxima Lx asociada, la siguiente palabra de codigo se lee a partir de la memoria intermedia de bits y una nueva secuencia de contenedores se inserta en la memoria intermedia de contenedores, a partir de la cual se retira el primer bit y se envfa al selector de memoria intermedia de contenedores. Si la memoria intermedia de contenedores esta vada y el numero Mx de bits en la memoria intermedia de bits conectada 58 es menor que la longitud de palabra de codigo maxima Lx asociada, la siguiente secuencia de Nx bits se lee a partir de la memoria intermedia de bits global 61 y se inserta en la memoria intermedia de bits local conectada 58, la siguiente palabra de codigo se lee a partir de la memoria intermedia de bits, una nueva secuencia de contenedores se inserta en la memoria intermedia de contenedores, y el primer contenedor de la secuencia es removed y se envfa al selector de memoria intermedia de contenedores. Este proceso se repite hasta que se han descodificado todos los sfmbolos de origen.

Al final de un paquete de datos, mas contenedores y / o bits de los que se requieren para descodificar los sfmbolos de origen solicitados se podnan insertar en la memoria intermedia de contenedores y / o la memoria intermedia de bits. Los contenedores restantes en la memoria intermedia de contenedores y los bits restantes en la memoria intermedia de bits se descartan y se ignoran.

Intercalacion de secuencias de bits de longitud fija con una restriccion de retardo baja

El codificador y descodificador de PIPE con una intercalacion de secuencias de bits de longitud fija tambien se pueden combinar con el esquema para controlar el retardo de memoria intermedia de codificador, el cual se ha descrito en lo que antecede. El concepto de codificacion de PIPE es el mismo que en el caso de comportar el control de retardo que se ha descrito en lo que antecede. Si una medida en relacion con el retardo o un lfmite superior del retardo (vease en lo sucesivo) supera un umbral especificado, la primera entrada de memoria intermedia reservada se llena mediante la evacuacion de la memoria intermedia de contenedores correspondiente (usando un mecanismo similar al del final de un paquete de datos) y potencialmente mediante la escritura de bits adicionales para llenar todos los bits de la entrada de memoria intermedia de longitud fija reservada. Mediante un mecanismo de este tipo, el numero de entradas de memoria intermedia en espera se reduce hasta que la medida de retardo asociada es menor que el umbral especificado. En el lado de descodificador, se han de descartar los contenedores y los bits que se han insertado en el lado de codificador con el fin de obedecer la restriccion de retardo. Para este descarte de contenedores y bits se puede usar basicamente el mismo mecanismo que en el lado de codificador.

La medida para el retardo (o un lfmite superior del retardo) puede ser el numero de bits en las entradas de memoria intermedia activas en la memoria intermedia de bits global, en donde el numero de entradas de memoria intermedia activas es el numero de entradas de memoria intermedia de longitud fija reservadas mas el numero de entradas de

5

10

15

20

25

30

35

40

45

50

55

60

memoria intermedia de longitud fija que contienen unos bits ya escritos. Observese que la primera entrada de memoria intermedia es siempre una entrada de memoria intermedia de longitud fija reservada o una entrada de memoria intermedia libre, debido a que si la primera entrada de memoria intermedia contiene bits escritos, estos bits se escriben en el tren de bits. Sea el maximo retardo de memoria intermedia admitido (segun sea determinado por la aplicacion) de D bits. Este maximo retardo de memoria intermedia D ha de ser conocido tanto por el codificador como por el descodificador. El maximo retardo de memoria intermedia D puede estar fijado por la aplicacion. El maximo retardo de memoria intermedia D se puede senalizar en el interior del tren de bits, por ejemplo, en el encabezamiento del paquete de datos (o el encabezamiento de rebanada) o en un conjunto de parametros, el cual se incluye en el tren de bits. Este se puede senalizar en unidades de bits, o bytes, o un multiplo de bits, o un multiplo de bytes. Si un codificador de contenedores 10 envfa una solicitud para la reserva de una nueva secuencia de bits de longitud fija a la memoria intermedia de bits global 51, el siguiente proceso se ejecuta antes de que se reserve una nueva entrada de memoria intermedia de longitud fija.

Si el numero de bits en las entradas de memoria intermedia activas en la memoria intermedia de bits global mas el numero de bits que seran reservados por la solicitud de reserva actual es mayor que el maximo retardo de memoria intermedia D, la primera entrada de memoria intermedia (la cual esta reservada) se evacua por el proceso que se describe en lo sucesivo hasta que el numero de bits en las entradas de memoria intermedia activas en la memoria intermedia de bits global mas el numero de bits que seran reservados por la solicitud de reserva actual sea menor que o igual al maximo retardo de memoria intermedia D. La evacuacion de una entrada de memoria intermedia de longitud fija reservada es similar a la evacuacion al final de un paquete de datos: El codificador de contenedores 10 que esta conectado con la memoria intermedia de bits 48 que ha reservado la primera entrada de memoria intermedia correspondiente se evacua mediante la adicion de contenedores con unos valores particulares o arbitrarios a la memoria intermedia de contenedores conectada 8 hasta que la secuencia de contenedores resultante representa una secuencia de contenedores que se asocia con una palabra de codigo, entonces la palabra de codigo se inserta en la memoria intermedia de bits 48 correspondiente. Tal como se ha mencionado en lo que antecede, una forma preferida para anadir contenedores a la memoria intermedia de contenedores es anadir aquellos contenedores que producen la palabra de codigo posible mas corta. Si, despues de la escritura de la palabra de codigo en la memoria intermedia de bits conectada y una insercion potencial de una secuencia de bits de longitud fija en la memoria intermedia de bits global, sigue habiendo bits en la memoria intermedia de bits (es decir, la palabra de codigo escrita no lleno por completo la secuencia de longitud fija reservada de bits), unos bits adicionales con unos valores particulares o arbitrarios se anaden a la memoria intermedia de bits hasta que todos los bits se han retirado de la memoria intermedia de bits y se han escrito en la entrada de memoria intermedia reservada. Por ultimo, al final de este proceso, la entrada de memoria intermedia completada (la primera entrada de longitud fija en la memoria intermedia de bits global) se retira de la memoria intermedia de bits global y se escribe en el tren de bits.

En el lado de descodificador, se ejecuta un proceso similar para descartar los contenedores y los bits que se han anadido para obedecer la restriccion de retardo. Por lo tanto, el descodificador mantiene un contador C que recuenta los bits que se han lefdo a partir de la memoria intermedia de bits global (este contador puede mantenerse en la memoria intermedia de bits global). El contador C se inicializa (por ejemplo, con cero) en el comienzo de la descodificacion de un paquete de datos y este se incrementa despues de que se lea una secuencia de longitud fija. Si una secuencia de longitud fija de Nx bits se lee a partir de la memoria intermedia de bits global 61, el contador C se incrementa en Nx. Ademas del contador global C, cada memoria intermedia de bits 58 contiene un contador Cx, que almacena el valor del contador de bits C antes de que la ultima secuencia de bits de longitud fija se inserte en la memoria intermedia de bits 58 correspondiente. Cuando una memoria intermedia de bits particular 58 lee una nueva secuencia de bits de longitud fija, su contador Cx se establece igual a C como una primera etapa y entonces la secuencia de bits de longitud fija se lee a partir de la memoria intermedia de bits global 61. Cuando una solicitud para un contenedor 19 se envfa a una memoria intermedia de contenedores particular 20 y la diferencia (C - Cx) entre el contador global C y el contador Cx de la memoria intermedia de bits conectada 58 es mayor que el maximo retardo de memoria intermedia D, todos los contenedores que se almacenan en la actualidad en la memoria intermedia de contenedores particular 20 y todos los bits que se almacenan en la memoria intermedia de bits conectada 58 se descartan y se ignoran. Ademas de esa etapa adicional, la descodificacion se opera tal como se ha descrito en lo que antecede. Si la memoria intermedia de contenedores 20 a la cual se envfa una solicitud para un contenedor 19 esta vacfa (o bien debido a que ya se han retirado todos los contenedores o bien debido a que el mecanismo de bajo retardo descarto todos los contenedores en la primera etapa despues de que se haya recibido la solicitud de contenedor), el descodificador de contenedores conectado 22 intenta leer una nueva palabra de codigo a partir de la memoria intermedia de bits conectada 58. Si el numero de bits en la memoria intermedia de bits 58 es menor que la longitud de palabra de codigo maxima, una nueva secuencia de bits de longitud fija se lee a partir de la memoria intermedia de bits global 61, antes de que se lea la palabra de codigo, etc.

Las figuras 7 a 13 se refieren a posibilidades para conseguir una trayectoria de trenes de bits intercalados entre el codificador de PIPE 104 por un lado y el descodificador de PIPE 202 por otro lado. Tal como se ha descrito en lo que antecede con respecto a las figuras 1 y 2, un aparato de codificacion y descodificacion por entropfa puede conectarse entre sf por dos canales separados, uno de los cuales transporta el tren de bits de VLC 112 y el otro de los cuales transporta el tren de bits codificado de PIPE intercalado. No obstante, hay tambien posibilidades de

5

10

15

20

25

30

35

40

45

50

55

60

intercalar incluso tanto el tren de bits de VLC 112 asf como los trenes de bits codificados de PIPE 118, y tales posibilidades se describiran mas adelante con respecto a las figuras 20 a 24. No obstante, antes de eso, se proporciona trasfondo matematico con respecto al esquema de codificacion de PIPE asf como detalles en lo que respecta a como subdividir de forma optima el intervalo de probabilidad con la asignacion de los intervalos parciales individuales resultantes a los codificadores por entropfa 116 y los descodificadores por entropfa 210 individuales, de forma respectiva.

Tal como ya se ha hecho notar, en la codificacion de PIPE el espacio de eventos de la secuencia de entrada de sfmbolos discretos se pone en correspondencia con un pequeno conjunto de intervalos de probabilidad binaria. Los modelos de probabilidad para los sfmbolos de origen pueden ser fijos o adaptativos al tiempo la realizacion de una codificacion por entropfa usando los intervalos de probabilidad permanece fijada y esta desacoplada de la fase de modelado. Cada uno de los intervalos de probabilidad se puede codificar usando un codigo por entropfa muy simple que tiene el nivel de complejidad de los codigos de Huffman. El exceso de tasa del codigo de entropfa de subdivision en particiones de intervalos de probabilidad (PIPE, probability interval partitioning entropy) es similar a la de la codificacion aritmetica pura.

La codificacion por entropfa, en general, se puede considerar como la forma mas generica de compresion de datos sin perdida. La compresion sin perdida tiene por objeto representar unos datos discretos con menos bits de los necesarios para la representacion de datos original pero sin perdida alguna de informacion. Los datos discretos se pueden dar en forma de texto, graficos, imagenes, video, audio, habla, fax, datos medicos, datos meteorologicos, datos financieros, o cualquier otra forma de datos digitales. En muchas aplicaciones de codificacion, los datos de origen originales se ponen en correspondencia en primer lugar con unos asf denominados sfmbolos de codificacion y estos sfmbolos de codificacion a continuacion se codifican por entropfa. La puesta en correspondencia con sfmbolos de codificacion puede incluir cuantificacion, caso en el cual, el esquema de codificacion global tiene perdidas. Un sfmbolo de codificacion s puede adoptar cualquier valor de un alfabeto M-ario (M > 2) A = {a0, ... , aM-1}. Para el fin de codificar el sfmbolo s, el alfabeto se asocia con una funcion de masa de probabilidad (pmf, probability mass function) estimada {ps(a0), ... , ps(aw-1)} y todas las dependencias entre sfmbolos de codificacion que no se consideran en esta pmf se desprecian. Para estos escenarios abstractos, la entropfa

m- 1

H,=- Zft (°l )l0§2Ps («/) (B'1 )

/=0

es el mas grande lfmite inferior para la longitud de palabra de codigo esperada en bits por sfmbolos, para codificar los sfmbolos s, que pueden conseguirse con tecnicas de codificacion por entropfa. Durante decadas, la codificacion de Huffman y la codificacion aritmetica han dominado la codificacion por entropfa practica. Estos son ejemplos bien conocidos de codigos practicos capaces de aproximarse al lfmite de entropfa (en un cierto sentido).

Para una distribucion de probabilidad fija, los codigos de Huffman son relativamente sencillos de construir. La propiedad mas atractiva de los codigos de Huffman es que su implementacion puede realizarse de forma eficiente mediante el uso de tablas de codigos de longitud variable (VLC, variable length code). No obstante, cuando se abordan unas estadfsticas de origen variables en el tiempo, es decir, unas probabilidades de sfmbolo cambiantes, la adaptacion del codigo de Huffman y sus tablas de VLC correspondientes es bastante exigente, tanto en terminos de la complejidad algontmica como en terminos de los costes de implementacion. Asimismo, en el caso de tener un valor de alfabeto dominante con ps(a) > 0,5, la redundancia del codigo de Huffman correspondiente (sin usar ampliacion de alfabeto alguna tal como la codificacion de longitud de series) puede ser bastante sustancial. Otra deficiencia de los codigos de Huffman viene dada por el hecho de que en el caso de tratar con un modelado de probabilidad de orden superior, se pueden requerir multiples conjuntos de tablas de VLC.

La codificacion aritmetica, por otro lado, a pesar de ser sustancialmente mas compleja que VLC, ofrece la ventaja de una manipulacion mas consistente y adecuada cuando se hace frente a un modelado de probabilidad adaptativo y de orden superior asf como con el caso de unas distribuciones de probabilidad muy sesgadas. En la practica, esta caractenstica basicamente resulta del hecho de que la codificacion aritmetica proporciona un mecanismo, por lo menos conceptualmente, para poner en correspondencia cualquier valor dado de estimada de probabilidad de una forma mas o menos directa con una porcion de la palabra de codigo resultante. Estando provista con una interconexion de este tipo, la codificacion aritmetica permite una separacion limpia entre las tareas de modelado de probabilidad y de estimacion de probabilidad, por un lado, y la codificacion por entropfa real, es decir, la puesta en correspondencia de sfmbolos con palabras de codigo, por otro lado.

Diferente de los esquemas de codificacion por entropfa convencionales recien analizados, la codificacion de PIPE usa subdivision en particiones de intervalos de probabilidad, el trasfondo matematico de lo cual se describe con mas detalle en lo sucesivo.

Considerese la secuencia de sfmbolos de codificacion {s0, ... , sw-1}. Cada sfmbolo se extrae de un alfabeto si e A.

34

5

10

15

20

25

30

35

40

45

50

Los alfabetos -4 — a't..} contienen dos o mas letras estando cada una asociada con una estimada de

probabilidad Ps(am^) • Las estimadas de probabilidad PsK) son conocidas por el codificador y el descodificador y pueden ser fijas o variables. Se supone que se estiman probabilidades variables de forma simultanea en el codificador y en el descodificador. O bien los alfabetos Ai pueden ser identicos para la secuencia de sfmbolos o bien diferentes tipos de sfmbolo estan asociados con diferentes alfabetos. En este ultimo caso, se supone que el descodificador conoce el alfabeto de cada sfmbolo en la secuencia. Esta suposicion se justifica debido a que las descripciones de codec de origen practicas contienen una sintaxis que estipula el orden de los sfmbolos y sus alfabetos.

La secuencia de sfmbolos {so, ... , s«-i} se convierte a una secuencia de sfmbolos binarios, a los que tambien se hace referencia como contenedores. Para cada sfmbolo s, la binarizacion

*- Pi-} = ri(4)

(B2)

representa una puesta en correspondencia biyectiva de las letras del alfabeto am con unos conjuntos ordenados de

contenedores b 'm . La puesta en correspondencia de binarizacion Yb puede ser diferente para diferente simbolos s, o categorias de simbolos. Cada secuencia de contenedores / para un simbolo particular s, consiste en uno o mas

contenedores bk . En e| lado de descodificador, un simbolo s, se puede reconstruir por la puesta en

S,

wr'(b')

correspondencia inversa Vu ) dada la secuencia de contenedores b1. Como resultado de la

binarizacion, se obtiene una secuencia de contenedores {bo, ... , bB-i} que representa la secuencia de simbolos de origen {so, ... , sW-i}.

Todos los contenedores by estan asociados con el mismo alfabeto binario B = {0, 1}, pero las pmf binarias

correspondientes {^o ’ P\) ’ con P\ = Pa > son por lo general diferentes. Una pmf binaria {Pa->P\} se puede describir mediante el valor del contenedor menos probable (LPB, less probable bin) blpb y su probabilidad plpb (con p lpb ^ 0,5). Esta descripcion de probabilidad binaria {b lpb, p lpb} se puede obtener directamente a partir de las

estimadas de probabilidad Ps{am) para los alfabetos de simbolos dadas las puestas en correspondencia de

binarizacion Yb • Tambien es posible (y a menudo preferible) estimar directamente {hilpb, plpb} de forma simultanea en el codificador y en el lado de descodificador. Por lo tanto, los contenedores pueden asociarse con un modelo de probabilidad (al que tambien se hace referencia como contexto) sobre la base de la sintaxis y los contenedores o simbolos previamente codificados. Y para cada modelo de probabilidad, la descripcion de probabilidad {blpb, plpb} puede estimarse sobre la base de los valores de los contenedores que se codifican con el modelo de probabilidad. Un ejemplo para un modelado de probabilidad binaria de este tipo se describe con respecto a CABAC de la norma H.264.

Debido a que la funcion de entropfa binaria

H(p) = -p logip) - (1 - p)log2(l - p)

(B3)

es simetrica en torno a p = 0,5, el mismo codificador binario se puede usar para codificar todos los contenedores que estan asociados con la misma probabilidad de LPB p lpb, independiente del valor de hi lpb- Por lo tanto, la secuencia

de contenedores {bo, ... , £>b-i} se convierte a una secuencia de contenedores de codificacion Para

cada contenedor by, la puesta en correspondencia biyectiva correspondiente Yc se especifica por

LPB

(B4)

en la que © indica el operador o exclusivo. En el lado de descodificador, los contenedores bj se pueden reconstruir dados los contenedores de codificacion bj y el valor de LPB correspondiente P lpb por la puesta en

correspondencia inversa bj = = bj © &LPB • Un contenedor de codificacion b^ = 0 especifica que

el valor del contenedor correspondiente bj es igual al valor de LPB hi lpb, y un contenedor de codificacion bc. = 1 especifica que el valor del contenedor correspondiente bj es igual al valor del contenedor mas probable (MPB, more

35

5

10

15

20

25

30

35

40

45

probable bin) 1 - blpb.

La secuencia de contenedores de codificacion {^o > • • • > ^b-i } representa, de hecho, de forma unica la secuencia de sfmbolos de origen {so, ... , sw-i} y las estimadas de probabilidad correspondientes, que puede emplearse para la codificacion por entropfa, se describen completamente mediante las probabilidades de LPB p lpb (con p lpb ^ 0,5). Por lo tanto, solo es necesario considerar probabilidades en el intervalo semiabierto (0, 0,5] para disenar el

codificador por entropia binario para los contenedores de codificacion bf .

Para la codificacion por entropia binaria real, la secuencia de contenedores de codificacion se

proyecta sobre un pequeno numero de intervalos de probabilidad Ik. El intervalo de probabilidad de LPB (0, 0,5] se subdivide en particiones para dar K intervalos Ik = (pk, Pk+i]

K-\

(B5)

El conjunto de K intervalos se caracteriza por K-1 fronteras de intervalos pk con k = 1, ... , K-1. Sin perdida de generalidad, se supone pk < Pk+i para k = 0, ... , K. Las fronteras de intervalo exteriores son fijas y vienen dadas por po = 0 y pk = 0,5. Se disena un codificador por entropia binario no adaptativo simple para cada intervalo Ip Todos los

contenedores de codificacion bj con las probabilidades de LPB asociadas plpb e //<estan asignados al intervalo Ik y se codifican con el codificador por entropia fijo correspondiente.

En la siguiente descripcion, todos los contenedores representan unos contenedores de codificacion bj y todas las probabilidades p son unas probabilidades de LPB plpb-

Para investigar el impacto de la discretizacion de intervalo de probabilidad sobre la eficiencia de codificacion, se supone que se puede disenar un codificador por entropia optimo para una probabilidad fija que alcanza el lfmite de entropia. Cada intervalo de probabilidad Ik = (pk, pk+i] se asocia con una probabilidad representativa pik e Ik y el codificador por entropia optimo correspondiente alcanzara el lfmite de entropia para esta probabilidad representativa. Bajo esta suposicion, la tasa para codificar un contenedor con una probabilidad p usando el codificador por entropia optimo para la representante de intervalo pIk viene dada por

R(P: Plt P lOgjify ) - (1 - J0)lOg2(:1 - )

=tf(P,,) + 0>(B6)

en la que H(p) representa la funcion de entropia binaria 3 y

imagen1

es su primera derivada. Se supone adicionalmente que la distribucion de las probabilidades en el intervalo (0, 0,5]

r0,5

viene dada por f(p), con Jq ^P ^ • Entonces, la tasa esperada, en bits por contenedor, para un

conjunto dado de K intervalos {Ik} con unas probabilidades representativas correspondientes p} puede escribirse como

=ii

*=0

La primera derivada parcial con respecto a cualquier probabilidad representativa pIk, con k = 0, ... , K-1, viene dada por

imagen2

5

10

15

20

25

30

35

B Pi P'+'f(P) dp-\Pk+'p f(p) dp

a R _ k JPk____________W_____________

dP,k P,k (1 ~ Pik) In 2

La ecuacion

imagen3

0 tiene

una unica solucion

imagen4

(B9)

para la probabilidad representativa pik en el interior del dominio de definicion Ik. La segunda derivada parcial para esta solucion

imagen5

P+\f(p) dp

JPk____________

P]k (1 ~ P]k) In 2

es siempre mayor que cero si

(B11)

imagen6

Por lo tanto, si se satisface la condicion B12, el valor dado Prk en la eq. B10 es la probabilidad representativa para

un intervalo Ik que reduce al mmimo la tasa global esperada R dados los lfmites de intervalo pk y pk+i. De lo contrario, no se proyecta contenedor alguno en el intervalo Ik y la probabilidad representativa pik e Ik se puede elegir de forma arbitraria sin impacto alguno sobre la tasa global R; pero una configuracion de este tipo debena evitarse, debido a que el intervalo Ik no se empleana para la codificacion por entropfa.

Para hallar una condicion para unas fronteras de intervalo optimas, se investigan las primeras derivadas de la tasa global esperada R con respecto a las fronteras de intervalo pk con k = 1, ... , K-1. Si f{p) > 0 para todo p e [plk.h plk)t

la ecuacion ------R = 0 tiene una unica solucion

imagen7

para la frontera de intervalo pk en el interior del dominio de definicion [pIk-1, pIk) y la segunda derivada parcial para esta solucion

imagen8

*

es siempre mayor que cero, de tal modo que pk es la frontera de intervalo pk e [pik_-pik) que reduce al minimo la tasa global esperada R dadas las representantes de intervalo pikA y pik. Si existen unas probabilidades p e \pikA, p/k)

d *

con f(p) = 0, la ecuacion---R — 0 tiene multiples soluciones, pero Pk tal como se da en la eq. B13 sigue siendo

fyk

optima incluso a pesar de que pueden existir soluciones optimas adicionales.

Dado el numero de intervalos K y la distribucion de probabilidad f(p), las fronteras de intervalo pk, con k = 1, ... , K-1

37

5

10

15

20

25

30

35

40

45

50

y las representantes de intervalo pik, con k = 0, ... , K-1, que reducen al mmimo la tasa global esperada R pueden obtenerse resolviendo el sistema de ecuaciones dado por las ecuaciones B10 y B 13 sujeto a las condiciones B12 para k = 0, ... , K-1. Esto puede conseguirse con el siguiente algoritmo iterativo.

Algoritmo 1:

1) Subdividir en particiones el intervalo (0, 0,5] para dar K intervalos arbitrarios Ik = (pk, pk+i] con p0 = 0, pk = 0,5, y

Pk < Pk+i para todo k = 0, ... , K-1 de una forma tal que las condiciones B 12 se obedecen para todo k = 0, ... , K-1.

2) Actualizar las representantes pik con k = 0, ... , K-1 de acuerdo con la eq. B10

3) Actualizar las fronteras de intervalo pk con k = 1, ... , K-1 de acuerdo con la eq. B13

4) Repetir las dos etapas previas hasta la convergencia

La figura 14 muestra un ejemplo para la discretizacion de intervalo optima usando el algoritmo descrito. Para el presente ejemplo, se supuso una distribucion de probabilidad uniforme f(p) = 2 para 0 < p < 0,5 y se subdividio en particiones el intervalo de probabilidad (0, 0,5] para dar K = 4 intervalos. Puede verse que la discretizacion de intervalo de probabilidad conduce a una aproximacion lineal por trozos A(p) de la funcion de entropfa binaria H(p) con A(p) > H(p) para todo p e (0, 0,5].

Como medida para el impacto de la discretizacion de intervalo sobre la eficiencia de codificacion, se puede usar el aumento de tasa global esperada en relacion con el lfmite de entropfa

D

.

|0 H(P).f(P)

(a H = (/>) m dp

Para el ejemplo particular de la figura 14, el valor esperado de la entropf

es igual a

1 / (2 In 2) bit por contenedor y la tara de tasa p es igual a un 1,01 %. La tabla 4 enumera unas taras de tasa pun; y pan para la distribucion de probabilidad uniforme y una distribucion de probabilidad creciente lineal f(p) = 8p con p e (0, 0,5], de forma respectiva, para numeros seleccionados de intervalos K.

Tabla 4: Tara de tasa frente al numero de intervalos de probabilidad para la distribucion de probabilidad uniforme y

para una distribucion de probabilidad creciente^ lineal

K: 1 2 4 8 12 16

uni [%]: 12,47 3,67 1,01 0,27 0,12 0,07

lin [%]: 5,68 1,77 0,50 0,14 0,06 0,04

Las investigaciones en esta seccion mostraron que la discretizacion del intervalo de probabilidad de LPB (0, 0,5] en un pequeno numero de intervalos con una probabilidad fija (por ejemplo, de 8 a 10 intervalos) tiene un impacto muy pequeno sobre la eficiencia de codificacion.

La codificacion por entropfa que se ha analizado en lo que antecede para intervalos de probabilidad, permite por lo tanto codificadores individuales usando unas probabilidades fijas.

En lo sucesivo, en primer lugar se muestra como se puede disenar un codigo simple para unas probabilidades fijas. Dados estos resultados, se desarrolla un algoritmo que optimiza de forma conjunta el diseno de codigo y la subdivision en particiones del intervalo de probabilidad de LPB (0, 0,5].

La codificacion por entropfa para unas probabilidades fijas p = pik se puede realizar usando codificacion aritmetica o codificacion de longitud variable. Para este ultimo caso, el siguiente enfoque parece ser simple y muy eficiente.

Se considera un esquema de codificacion por entropfa binaria mediante el cual un numero variable de contenedores se pone en correspondencia con palabras de codigo de longitud variable. Para la capacidad de descodificacion unica, la puesta en correspondencia inversa de una palabra de codigo con una secuencia de contenedores ha de ser unica. Y debido a que se desea disenar un codigo que se aproxime al lfmite de entropfa tanto como sea posible, las consideraciones realizadas por los inventores de la presente invencion se limitan a las puestas en correspondencias biyectivas. Una puesta en correspondencia biyectiva de este tipo se puede representar por un arbol binario en el que todos los nodos hoja estan asociados con palabras de codigo, tal como se ilustra en la figura 15. Las aristas del arbol representan eventos binarios. En el ejemplo de la figura 15, las aristas inferiores representan el valor de contenedor de LPB y las aristas superiores representan el valor de contenedor de MPB. El arbol binario representa

38

5

10

15

20

25

30

35

40

45

50

un codigo de prefijo para los contenedores si este es un arbol binario completo, es decir, si cada nodo es o bien una hoja o bien tiene dos descendientes. Cada nodo hoja se asocia con una probabilidad sobre la base de la probabilidad de LPB dada p. El nodo rafz tiene la probabilidad praiz = 1. La probabilidad para todos los otros nodos se obtiene al multiplicar la probabilidad del predecesor correspondiente con p para los descendientes de LPB y q = 1 - p para los descendientes de MPB. Cada nodo hoja Li se caracteriza por el numero de aristas de LPB ai y el numero de aristas de MPB bi desde el nodo rafz hasta el nodo hoja. Para una probabilidad de LPB particular p, la probabilidad pi para un nodo hoja Li = {ai, bi} es igual a

Pi = /' 0-p)b' (B16)

El arbol binario T esta completamente caracterizado por el numero de nodos hoja L y los pares asociados {ai, bi} con i = 0, ... , L-1.

Dado un arbol binario completo T y una probabilidad de LPB p, la asignacion optima de palabras de codigo a los nodos hoja puede obtenerse mediante el algoritmo de Huffman. La puesta en correspondencia del numero variable resultante de bits con las palabras de codigo de longitud variable (V2V) C se caracteriza por el numero de palabras de codigo L, el cual es identico al numero de nodos hoja, y las tuplas {ai, b, ii} para i = 0, ... , L-1, en las que ii representa la longitud de palabra de codigo que se asocia con el nodo hoja correspondiente Lt = {ai, bi}. Se debena hacer notar que hay multiples posibilidades para la asignacion de palabras de codigo dadas las longitudes de palabra de codigo {ii} y la asignacion de palabras de codigo real no es importante siempre que las palabras de codigo representen un codigo de prefijo que se puede descodificar de forma unica. La tasa esperada R(p, C) en bits por contenedor para un codigo C dado y una probabilidad de LPB p es la relacion de la longitud de palabra de codigo esperada y el numero esperado de contenedores por palabra de codigo

imagen9

El diseno de codigo a menudo esta limitado por factores como el numero maximo de palabras de codigo L, el numero maximo de contenedores por palabra de codigo, o la longitud de palabra de codigo maxima, o este se restringe a codigos de estructuras particulares (por ejemplo, para permitir un analisis sintactico optimizado). Si se supone que se da el conjunto Sc de codigos utilizables para una aplicacion particular, el codigo optimo C* e Sc para una probabilidad de LPB particular p se puede hallar mediante la reduccion al mmimo de la tasa esperada R(p, C)

C'(p)= &rg min^(p,C) (B18)

VCeSc

Como una alternativa mas rapida, se considera que la reduccion al mmimo tambien puede proseguir sobre un conjunto dado de arboles binarios St y para cada arbol solo un codigo de V2V C que se obtiene mediante el algoritmo de Huffman. Como un ejemplo, se disenaron codigos de V2V para diversas probabilidades de LPB p al considerar todos los arboles binarios T para los que el numero de nodos hoja L es menor que o igual a un maximo Lm dado. En la figura 16, el aumento relativo de tasa p(p,C*(p)) = R(p, C*(p)) / H(p) se representa graficamente sobre la probabilidad de LPB p para unos tamanos de tabla maximos seleccionados Lm. El aumento de tasa p(p) puede reducirse por lo general permitiendo unos tamanos de tabla mas grandes. Para unas probabilidades de LPB mas grandes, un pequeno tamano de tabla L de 8 a 16 palabras de codigo es por lo general suficiente para mantener el aumento de tasa p(p) razonablemente pequeno, pero para unas probabilidades de LPB mas pequenas (por ejemplo, p < 0,1), se requieren unos tamanos de tabla mas grandes L.

En las secciones previas, se considero la discretizacion de probabilidad optima suponiendo unos codigos optimos y el diseno de codigo para unas probabilidades de LPB fijas. Pero debido a que, en general, no se puede lograr el lfmite de entropfa con codigos de V2V reales de tamanos de tabla limitados, el diseno de codigo y la subdivision en particiones del intervalo de probabilidad de LPB (0, 0,5] se han de considerar de forma conjunta para obtener un diseno optimizado de codificacion por entropfa.

Para un intervalo k = (pk, pk+i] dado, un codigo Ck de un conjunto dado Sc es un codigo optimo Ck si este reduce al

minimo

la tasa esperada R ~ f R(p, Ck~) f (P) dP para el intervalo dado.

J Pl '

’Pk

5

10

15

20

25

30

35

40

45

50

imagen10

Para los disenos practicos, la reduccion al minimo de la integral en la eq. B19 puede simplificarse, con un impacto

*

minimo sobre la eficiencia de codificacion, determinando en primer lugar una probabilidad representative optima Pi

para el intervalo lk de acuerdo con la eq. B10 y entonces elegir el codigo optimo Ck del conjunto dado Sc para la

*

probabilidad representativa P,k de acuerdo con la eq. B18.

Unas fronteras de intervalo optimas pk, con k = 1, ... , K-1, dado el conjunto de codigos Ck, con k = 0, ... , K-1, se pueden obtener mediante la reduccion al minimo de la tasa global esperada

imagen11

Establecer las primeras derivadas con respecto a las fronteras de intervalo iguales a cero, ------R = 0, para k = 1,

dPk

... , K-1, da

p\ = py con R(pk,Ck.i) = R(pk,Ck) (B21)

*

De forma similar a la eq. B 13, se puede mostrar que Pk es siempre una solucion optima, pero dependiendo de la

distribucion de probabilidad ffp) podrian existir soluciones optimas adicionales. Por lo tanto, una frontera de intervalo *

optima Pk entre dos intervals lk--\ e Ik con codigos asociados CkA y Ck dados, de forma respectiva, es el punto de interseccion de las funciones R(p, Ck-i) y R(p, Ck).

En consecuencia, el siguiente algoritmo interactivo se puede usar para obtener de forma conjunta la subdivision en particiones de intervalos de probabilidad y los codigos asociados dado el numero K de intervalos de probabilidad, el conjunto de posibles codigos Sc, y la distribucion de probabilidad f(p), con p e (0, 0,5].

Algoritmo 2:

1) Obtener los lfmites de intervalo de probabilidad inicial pk, con k = 0, ... , K, usando el algoritmo 1 que se especifica en la sec. 3

2) Obtener unas representantes pik para los intervalos de probabilidad Ik, con k = 0, ... , K -1, de acuerdo con la eq. B10

3) Obtener codigos Ck e Sc para las representantes de intervalo pik, con k = 0, ... , K -1, de acuerdo con la eq. B18

4) Actualizar fronteras de intervalo pk, con k = 1, ... , K-1, de acuerdo con la eq. B21

5) Repetir las tres etapas previas hasta la convergencia

Las etapas 2 y 3 en el algoritmo 2 tambien se podnan sustituir por una obtencion directa de los codigos Ck e Sc, con k = 0, ... , K-1, sobre la base de las fronteras de intervalo pk, con k = 0, ... , K, de acuerdo con la eq. B19. Y, tal como se ha mencionado en la sec. 4.1, la reduccion al minimo en la etapa 3 tambien puede proseguir sobre un conjunto dado de arboles binarios St en los que para cada arbol binario T solo se considera un codigo de V2V Ck obtenido mediante el algoritmo de Huffman.

Como un ejemplo, se obtuvo de forma conjunta la subdivision en particiones para dar K = 12 intervalos de probabilidad y codigos de V2V correspondientes usando el algoritmo 2. En este, la reduccion al minimo en la etapa 3 del algoritmo se sustituyo con una reduccion al minimo equivalente sobre un conjunto dado de arboles binarios St en los que el codigo evaluado C para cada arbol T se obtuvo mediante el algoritmo de Huffman. Se consideraron unos arboles T con un numero maximo de Lm = 65 nodos hoja y, por lo tanto, codigos C con hasta 65 entradas de tabla. Todos los arboles binarios T con hasta 16 nodos hoja se han evaluado en la reduccion al minimo; para unos arboles con mas de 16 nodos hoja, se empleo una busqueda suboptima dados los mejores resultados para unos arboles con un numero mas pequeno de nodos hoja.

En la figura 17 el aumento de tasa esperada en relacion con el lfmite de entropfa AR(p) = R(p) - H(p) para el ejemplo

5

10

15

20

25

30

35

40

45

de diseno de codigo se representa graficamente sobre la probabilidad de LPB p. Como comparacion, tambien se represento graficamente el aumento de tasa esperada AR para la discretizacion de intervalo de probabilidad teoricamente optima (tal como se desarrolla en la sec. 3) y la discretizacion de probabilidad teoricamente optima con la restriccion adicional pik-1 = 0,5 en el interior del diagrama. Puede verse que la discretizacion de intervalo de probabilidad conjunta y el diseno de codigo de V2V conduce a un desplazamiento de las fronteras de intervalo (las fronteras de intervalo pk, con k = 1, ... , K-1, vienen dadas por los maximos locales de las curvas de AR(p)). El aumento relativo de tasa global esperada en relacion con el lfmite de entropfa para el ejemplo de diseno con codigos de V2V reales es p = 0,24 %, cuando se supone una distribucion de probabilidad uniforme fp). Los aumentos relativos de tasa correspondientes para la discretizacion de intervalo de probabilidad teoricamente optima y la discretizacion de probabilidad teoricamente optima con la restriccion adicional pik-1 = 0,5 son p = 0,12 % y p = 0,13 %, de forma respectiva.

La terminacion de palabras de codigo se puede realizar tal como sigue. Cuando se codifica una secuencia finita de simbolos {so, ... , s«-i}, cada uno de los K codificadores binarios procesa una secuencia finita de contenedores de

codificacion b bg^_i}k , con k = 0, ... , K-1. Y se ha de haber asegurado que, para cada uno de los K

codificadores binarios, todos los contenedores de codificacion de la secuencia se pueden

reconstruir dada la palabra de codigo o la secuencia de palabras de codigo

Cuando se emplea la codificacion aritmetica, la palabra de codigo aritmetica para la secuencia de contenedores de codificacion ha de determinarse de una forma tal que todos los contenedores de codificacion se puedan descodificar dada la palabra de codigo. Para los codigos de V2V que se han descrito en lo que antecede, los contenedores al

final de la secuencia pueden no representar una secuencia de contenedores que se asocia con una palabra de

codigo. En caso de este tipo, se puede escribir cualquier palabra de codigo que contenga la secuencia de contenedores restante como prefijo. La tara se puede reducir al mmimo si se elige la palabra de codigo correspondiente que tiene la longitud minima (o una de estas palabras de codigo). En el lado de descodificador, se descartan los contenedores lefdos adicionalmente al final de la secuencia de contenedores, los cuales se pueden identificar dados los esquemas de binarizacion y de sintaxis de trenes de bits.

Un ejemplo de diseno de codigo simple se presenta en lo sucesivo. Por razones de ilustracion, se considera el ejemplo simple de un origen {s} con tres letras y unas probabilidades asociadas fijas de ps(aa) = 0,7, ps(ai) = 0,18, y Ps(a2) = 0,12. El arbol de eleccion ternario correspondiente puede convertirse en un arbol binario completo tal como se muestra en la figura 18.

Una binarizacion para el arbol binario completo en la figura 18 se da en la tabla 5. El sfmbolo ternario pmf ps se convierte a dos pmf binarias p*0 = (0,7, 0,3) y pb1 = (0,6, 0,4). Para cada sfmbolo s en el tren de bits, el contenedor b0 se encuentra presente. Cuando b0 es igual a 0, tambien b1 se encuentra presente. Observese que la binarizacion que se da en la tabla 2 es identica a un codigo de Huffman de una sola letra optimo para el origen s.

Tabla 5: Binarizacion de un origen de tres letras. Las probabilidades de LPB p lpb son 0,3 para el primer contenedor

y 0,4 para el seg: undo contenedor

Sfmbolo a.: Probabilidad p(a,) Contenedor b0 Contenedor b1

a0: 0,7 1

a1: 0,18 0 1

a2: 0,12 0 0

LPB Prob.: p LPB = p(bj = 0) 0,3 0,4

La entropfa para el origen s es

H (0,7, 0,18, 0,12) = H (0,7, 0,3) + 0,3 H (0,6, 0,4)

= 1,1726 bits / sfmbolo (B22)

La longitud de palabra de codigo promedio del codigo de Huffman de una sola letra se da como

5

10

15

20

25

30

35

40

imagen12

(B23)

que se corresponde con una redundancia de p hc = 0,1274 bits / sfmbolo o un 10,87 % de la tara de tasa esperada.

Para el ejemplo de binarizacion particular con unas pmf fijas, los contenedores ba y b1 ya representan unos contenedores de codificacion, debido a que para ambos contenedores, el valor de LpB b lpb es igual a 0. La distribucion f(s) de las probabilidades de LpB es discreta, con fp) = 0 excepto por p = 0,3 y p = 0,4. En consecuencia, la discretizacion de probabilidad optima con duce a K = 2 intervalos con las representantes pi0 = 0,3 y pi1, = 0,4. La frontera de intervalo p1 entre estos intervalos se puede elegir de forma arbitraria en [0,3, 0,4).

Para codificar el origen, la secuencia de sfmbolos de origen se binariza para dar una secuencia de contenedores. El contenedor b0 se transmite para cada sfmbolo de origen. El contenedor b1 solo se transmite cuando b0 = 0. Los contenedores b0 y b1 se codifican por separado con unas probabilidades de LPB constantes de pi0 = 0,3 y pi1 = 0,4, de forma respectiva.

Una codificacion eficiente de un alfabeto binario con probabilidad fija puede conseguirse mediante una puesta en correspondencia de V2V simple. En la tabla 6 y la tabla 7 se dan, de forma respectiva, ejemplos para puestas en correspondencia de V2V con unas tablas de codificacion pequenas para las probabilidades de LPB p lpb = 0,3 y p lpb = 0,4. La puesta en correspondencia de V2V para p lpb = 0,3 da una redundancia de 0,0069 bits / contenedor o un 0,788 %. Para la probabilidad de LPB de p lpb = 0,4, la redundancia es 0,0053 bits / contenedor o un 0,548 %.

Tabla 6: Arbol de contenedores y codigos para una probabilidad de LPB de p lpb = 0,3. La redundancia de este

___________codigo es de un 0,788 % ________

Arbol de contenedores: Probabilidad Codigos

'11': 0,72 = 0,4 9 '1'

'01': 0,7 ■ 0,3 = 0,21
'01'

'0': 0,3 '00'

Tabla 7: Arbol de contenedores y codigos para una probabilidad de LPB de p lpb = 0,4. La redundancia de este

codig: o es de un 0,548 %

Arbol de contenedores: Probabilidad Arbol de codigos

'111': 0,63 = 0,216 '11'

'110': '001'

: 0,62 ■ 0,4 = 0,144

'10': 0,6 ■ 0,4 = 0,24 '11'

'01': 0,4 ■ 0,6 = 0,24
'01'

'00': 0,42 = 0,16 '000'

La tasa esperada global provocada por el nuevo metodo de codificacion es

7 =7 +03-7

(B24)

” 1,181 bits / shnbolo

La redundancia global es de un 0,73 % en relacion con el lfmite de entropfa, lo cual representa una mejora significativa en comparacion con el codigo de Huffman de una sola letra.

Se podna argumentar que se podna obtener una mejora en la eficiencia de codificacion similar creando un codigo de longitud de series. Para el ejemplo anterior, se podna construir un codigo de longitud de series para el sfmbolo mas probable al considerar unas series de hasta dos sfmbolos. Cada uno de los eventos {a0a0, a0a1, a0a2, a1, a2} se asociana con una palabra de codigo separada. Un codigo de este tipo da una redundancia de un 1,34 % en relacion con el lfmite de entropfa. En la practica, los codigos de V2V se pueden considerar como una generalizacion de los codigos de longitud de series para sfmbolos binarios (el codigo de V2V en la tabla 3 representa, de hecho, de forma

5

10

15

20

25

30

35

40

45

50

55

efectiva un codigo de longitud de series). Para un unico alfabeto de s^bolos con unas probabilidades fijas, una eficiencia de codificacion similar como para el enfoque presentado tambien puede conseguirse creando un codigo que pone en correspondencia un numero variable de sfmbolos de origen con palabras de codigo de longitud variable. La ventaja principal del enfoque presentado es su flexibilidad en la puesta en correspondencia de unas secuencias de sfmbolos de origen arbitrarias con unas estimadas de probabilidad fijas o adaptativas con un pequeno numero de codificadores binarios simples que se operan con unas probabilidades de LPB fijas.

Se considera a continuacion como lograr una capacidad de descodificacion unica.

Con el esquema de codificacion por entropfa presentado, la codificacion de una secuencia de sfmbolos de origen s = {so, ... , sw-i} consiste en las siguientes tres etapas basicas:

• binarizacion de sfmbolos b = {bo, ... , be-i} = Yb(s) que da una secuencia de contenedores b = {bo, ... , bB-i}

• conversion de la secuencia de contenedores en una secuencia de contenedores de codificacion

* - {b‘,...,bl,}=yc( b)

• codificacion por entropia binaria de la secuencia de contenedores de codificacion b c~ usando

una discretizacion de intervalo de probabilidad y K codificadores binarios fijos

La secuencia de simbolos s = {so, ... , s«-i} se puede descodificar de forma unica, si la secuencia de contenedores de codificacion b c~ {b£ ,...,bcB ,} se puede descodificar de forma unica y las puestas en correspondencia y * y yc son invertibles.

Permitase que ye notifique la puesta en correspondencia de codificador de una secuencia de uno o mas contenedores de codificacion b c= {^jcon una secuencia de una o mas palabras de codigo c(bc) = {co, ...}

imagen13

Para una capacidad de descodificacion unica de una secuencia de contenedores de codificacion bc dada la secuencia de palabras de codigo c(bc), la puesta en correspondencia de codificador Ye debe tener la propiedad de que una palabra de codigo unica c(bc) se asigna a cada posible secuencia de contenedores de codificacion bc:

V&ic,&jc bftb? c(bf) * c(bf) (B26)

Esta propiedad se satisface siempre cuando se usan codigos aritmeticos o codigos de prefijo. Esta se satisface en particular para los codigos de V2V que se describen en la sec. 4.1 (incluyendo la terminacion de palabras de codigo que se describe en la sec. 4.3), debido a que los codigos de V2V representan codigos de prefijo para numeros variables de contenedores.

No obstante, en el enfoque de codificacion por entropia binaria presentado, la secuencia de contenedores de codificacion bc se subdivide en particiones para dar K subsecuencias £ ? con k = 0, ... , K -1,

{*oc,...,6K-ic} = rP(bc)

(B27)

y a cada una de las subsecuencias b £ , se asigna una secuencia de palabras de codigo Ck(6kc) usando una

puesta en correspondencia de codificador particular y . En consecuencia, se ha de ampliar la condicion sobre la

capacidad de descodificacion unica. Una secuencia de contenedores de codificacion b c se puede descodificar de forma unica dadas K secuencias de palabras de codigo Ck(bkc), con k = 0, ... , K -1, si cada subsecuencia de contenedores de codificacion bk c se puede descodificar de forma unica dada la palabra de codigo correspondiente Ck(bkc) y la regla de subdivision en particiones Yp es conocida por el descodificador. La regla de subdivision en particiones yp viene dada por la discretizacion de intervalo de probabilidad de LPB {/*<} y las probabilidades de LPB p'

lpb que estan asociadas con los contenedores de codificacion b°j , con j = 0, ... , B-1. Por lo tanto, la discretizacion de intervalo de probabilidad de LPB {/*<} ha de ser conocida en el lado de descodificador y la probabilidad de LPB p7 lpb para cada contenedor de codificacion b°j , con j = 0, ... , B-1, se ha de obtener de la misma forma en el lado de codificador y de descodificador.

5

10

15

20

25

30

35

40

45

50

Para la puesta en correspondencia Yc de una secuencia de contenedores con una secuencia de contenedores de codificacion c, cada unico bj, con j = 0, ... , 6-1, se convierte por la puesta en correspondencia binaria

En el lado de descodificador, la secuencia de contenedores se puede obtener mediante las puestas en correspondencia binarias

bl = (7,j'(b‘) = bcl®bJu,B (B28)

imagen14

con j = 0, ... , 6-1. Si el valor de LPB A lpb para cada contenedor bj se obtiene de la misma forma en el lado de codificadory de descodificador, estas puestas en correspondencia (Yc ) representan las inversas de las puestas en correspondencia de codificador correspondientes y-' } debido a que

(B29)

y por lo tanto, la conversion ya de una secuencia de contenedores b en una secuencia de contenedores de codificacion bc es invertible.

Por ultimo, se investiga la invertibilidad de la binarizacion b = yb(s) mediante la cual cada simbolo s,, con / = 0, ... , N- 1, se pone en correspondencia con una secuencia de contenedores b Un sfmbolo s, se puede

descodificar de forma unica dada la secuencia de contenedores correspondiente b1 si la puesta en correspondencia

de binarizacion Yb asigna una secuencia de contenedores diferente b Jm a cada letra am del alfabeto A, para el sfmbolo s. No obstante, esta condicion no es suficiente, debido a que la subdivision en particiones de la secuencia de contenedores b = {bo, ... , Ab-i} en unas secuencias de contenedores b' que se corresponden con los sfmbolos s, con / = 0, ... , A/-1, no es conocida por el descodificador. Se da una condicion suficiente, cuando para cada simbolo

' ’ i

, que estan asociadas con las letras u-m del alfabeto correspondiente A,

Si, las secuencias de contenedores 1

forman un codigo de prefijo y las puestas en correspondencia de binarizacion 7b para cada simbolo s,, con / = 0, N-1, se conocen en el lado de descodificador.

Las condiciones de la capacidad de descodificacion unica para el enfoque de codificacion por entropfa binaria presentado se pueden resumirtal como sigue:

• las puestas en correspondencia de binarizacion 7b representan codigos de prefijo y son conocidas por el descodificador (en el orden de codificacion de sfmbolos)

• los modelos de probabilidad (A lpb, p lpb) para todos los contenedores bj se obtienen de la misma forma en el lado de codificador y de descodificador

• la subdivision en particiones del intervalo de probabilidad de LPB (0, 0,5] en K intervalos Ik, con k = 0, ... , K-1, es conocida por el descodificador

vk

• la puesta en correspondencia f e para cada intervalo de probabilidad k, con k= 0, ... , K-1, representa un codigo que se puede descodificar de forma unica

En lo sucesivo, se describen con mas detalle ejemplos para el diseno global de codificador y de descodificador. Los inventores de la presente invencion se centran en los esquemas de codificacion en los que los modelos de probabilidad {A lpb, p lpb} para los contenedores son estimados directamente en el lado de codificador y de descodificador y los K codificadores binarios usan unas puestas en correspondencia de V2V que se han descrito en lo que antecede. Cada simbolo de origen s se asociara con una categona de sfmbolos cs, la cual determina el tipo del simbolo incluyendo su intervalo de valores. El orden de los sfmbolos y las categonas de sfmbolos asociadas debena venir dado por la sintaxis, que se presupone que se conoce en el lado de codificador y de descodificador.

El diagrama de bloques para un ejemplo diseno de codificador de PIPE y de descodificador de PIPE se ilustra en la figura 19. En el lado de codificador, los simbolos s con unas categorias de simbolos asociadas cs se alimentan a la

unidad de binarizacion, que convierte cada simbolo s en una secuencia de contenedores

imagen15

El esquema de binarizacion 7b usado se determina sobre la base de la categona de simbolos cs. Ademas, la unidad de binarizacion asocia cada contenedor b de una secuencia de contenedores s con una indicacion de modelo de probabilidad Cb, la cual especifica el modelo de probabilidad que se usa para codificar el contenedor A. La indicacion de modelo de probabilidad Cb se puede obtener sobre la base de la categona de simbolos Cs, el numero

5

10

15

20

25

30

35

40

45

50

55

60

de contenedor del contenedor actual en el interior de la secuencia de contenedores s, y / o los valores de contenedores y s^bolos ya codificados.

El estimador de probabilidad y unidad de asignacion mantiene multiples modelos de probabilidad, que se caracterizan por unos pares de valores {b lpb, p lpb}. Este recibio unos contenedores b y unas indicaciones de modelo de probabilidad asociadas Cb a partir de la unidad de binarizacion, y reenv^a el valor de LPB b lpb y la probabilidad de LPB p lpb del modelo de probabilidad indicado a la unidad de obtencion de contenedores de codificacion y la unidad de cuantificacion de probabilidad, de forma respectiva. A continuacion de lo anterior, el modelo de probabilidad correspondiente {b lpb, p lpb} se actualiza usando el valor del contenedor recibido b.

La unidad de obtencion de contenedores de codificacion recibe los contenedores b y los valores de LPB asociados b lpb a partir de la unidad de binarizacion y el estimador de probabilidad y la unidad de asignacion, de forma

respectiva, y envfa unos contenedores de codificacion bc, los cuales se obtienen mediante bc = b © b lpb, a la unidad de cuantificacion de probabilidad. La unidad de cuantificacion de probabilidad reenvfa cada contenedor de codificacion bc a uno de los K codificadores binarios. Esta contiene informacion sobre la cuantificacion de intervalo de probabilidad de LPB {/k}. La probabilidad de LPB p lpb, que se asocia con un contenedor de codificacion bc y se recibe a partir del estimador de probabilidad y la unidad de asignacion, se compara con las fronteras de intervalo p} y el mdice de intervalo de probabilidad k, para el cual se obtiene p lpb e Ik. Entonces, el contenedor de codificacion bc se reenvfa al codificador binario asociado.

Cada uno de los K codificadores binarios consiste en una memoria intermedia de contenedores y un codificador de contenedores. La memoria intermedia de contenedores recibe unos contenedores de codificacion bc a partir de la unidad de cuantificacion de probabilidad y almacena estos en el orden de codificacion. El codificador de contenedores implementa una puesta en correspondencia de V2V particular y compara la secuencia de contenedores en la memoria intermedia de contenedores con las secuencias de contenedores que estan asociadas con palabras de codigo. Si la secuencia de contenedores en la memoria intermedia de contenedores es igual a una de esas secuencias de contenedores, el codificador de contenedores retira la secuencia de contenedores {bc} de la memoria intermedia de contenedores y escribe la palabra de codigo asociada ({bc}) en el tren de palabras de codigo correspondiente. Al final del proceso de codificacion para una secuencia de sfmbolos, para todos los codificadores binarios para los cuales las memorias intermedias de contenedores no estan vacfas, una palabra de codigo de terminacion se escribe tal como se describe en la sec. 4.3.

Los K trenes de palabras de codigo resultantes se pueden transmitir, paquetizar o almacenar por separado, o estos se pueden intercalar (comparese con la sec. 6.2) para el fin de transmision o almacenamiento.

En el lado de descodificador, cada uno de los K descodificadores binarios que consisten en un descodificador de contenedores y una memoria intermedia de contenedores recibe un tren de palabras de codigo. El descodificador de contenedores lee las palabras de codigo ({bc}) a partir del tren de palabras de codigo e inserta la secuencia de contenedores asociada {bc}, en el orden de codificacion, en la memoria intermedia de contenedores.

La descodificacion de la secuencia de sfmbolos es impulsada por la sintaxis subyacente. Solicitudes para un sfmbolo s se envfan junto con la categona de sfmbolos cs a la unidad de binarizacion. La unidad de binarizacion convierte estas solicitudes de sfmbolo en una solicitud para contenedores. Una solicitud para un contenedor se asocia con una indicacion de modelo de probabilidad cb, la cual se obtiene de la misma forma que en el codificador, y se envfa al estimador de probabilidad y la unidad de asignacion. El estimador de probabilidad y la unidad de asignacion se operan de forma similar a su homologo en el lado de codificador. Sobre la base de la indicacion de modelo de probabilidad cb, esta identifica un modelo de probabilidad y reenvfa su valor de LPB b lpb y la probabilidad de LPB p lpb a la unidad de obtencion de contenedores y la unidad de cuantificacion de probabilidad, de forma respectiva.

La unidad de cuantificacion de probabilidad determina uno de los K descodificadores binarios sobre la base de la probabilidad de LPB p lpb, de la misma forma que el codificador binario se determina en el lado de codificador, retira el primer contenedor de codificacion bc, en el orden de codificacion, de la memoria intermedia de contenedores correspondiente, y lo reenvfa a la unidad de obtencion de contenedores. La unidad de obtencion de contenedores recibe unos contenedores de codificacion bc y los valores de LPB asociados b lpb a partir de la unidad de cuantificacion de probabilidad y el estimador de probabilidad y la unidad de asignacion, de forma respectiva, y

la unidad de binarizacion, la unidad de obtencion de contenedores envfa el valor de contenedor descodificado b a la unidad de binarizacion y el estimador de probabilidad y la unidad de asignacion.

En el estimador de probabilidad y la unidad de asignacion, el valor del contenedor descodificado b se usa para actualizar el modelo de probabilidad {b lpb, p lpb}, el cual fue elegido por el valor asociado cb, de la misma forma que en el lado de codificador. Por ultimo, la unidad de binarizacion anade el contenedor recibido b a la secuencia de contenedores s la cual ya se ha recibido para una solicitud de sfmbolo y compara esta secuencia de contenedores s

45

5

10

15

20

25

30

35

40

45

50

55

60

con las secuencias de contenedores que estan asociadas con unos valores de simbolo por el esquema de

c

binarizacion ybs . Si la secuencia de contenedores s coincide con una de esas secuencias de contenedores, el sfmbolo descodificado correspondiente s se emite como respuesta final a la solicitud de s^bolo. De lo contrario, la unidad de binarizacion envfa solicitudes de contenedor adicionales hasta que el s^bolo s se ha descodificado.

La descodificacion de una secuencia de sfmbolos se termina si no se reciben solicitudes de sfmbolo adicionales, las cuales son impulsadas por la sintaxis. Se descartan los contenedores de codificacion bc que pueden estar contenidos en las memorias intermedias de contenedores al final del proceso de descodificacion por entropfa (como resultado de las palabras de codigo de terminacion).

Despues de haber descrito determinados codificadores de PIPE y descodificadores de PIPE con respecto a las figuras 3 a 13 y de haber proporcionado un trasfondo matematico en lo que respecta a la codificacion de PIPE en general con respecto a las figuras 14 a 19, con respecto a las figuras 20 a 24, se describen mas detalles para aparatos de codificacion y descodificacion por entropfa. Los siguientes ejemplos de las figuras 22 a 24 no solo intercalan los trenes de bits codificados de PIPE entre sf, sino que intercalan el tren de bits de VLC y los trenes de bits codificados de PIPE completamente. En comparacion con esto, los codificadores de PIPE y los descodificadores de PIPE con una intercalacion para los trenes de bits codificados de PIPE, que se muestran en las figuras 7 a 13, proporcionados meramente para una intercalacion separada de los trenes de bits codificados de PIPE. Tal como ya se ha mencionado en lo que antecede, incluso estos mismos pueden servir como base para conseguir un tren de bits completamente intercalado mediante el uso de otro par de intercalador / desintercalador 134 y 228, de forma respectiva (veanse las figuras 1 y 2), tal como, por ejemplo, mediante el uso de una intercalacion de trenes de bits tal como se muestra en las figuras 5 y 6. No obstante, las posibilidades que se describen a continuacion realizan la intercalacion al mismo tiempo tanto en el tren de bits de vLc como en los trenes de bits codificados de PIPE con el uso, dicho de otra forma, el intercalador / desintercalador de una fase 128 y 230, de forma respectiva.

Antes de describir con detalle casos en los que unos sfmbolos codificados de VLC y de PIPE se intercalan en el interior de un tren de bits, con el fin de conseguir una compensacion redproca mas adecuada entre la complejidad y la eficiencia de codificacion, una estructura basica del mismo sin una intercalacion se describe con respecto a la figura 20 y 21.

La estructura del aparato de codificacion por entropfa de la figura 1a se muestra en la figura 20. El aparato de codificacion por entropfa convierte un tren de sfmbolos de origen 1a, que se corresponden con la combinacion de sfmbolos de origen codificados de VLC y codificados de PIPE de las figuras 1 y 2, en concreto 106 y 218, de forma respectiva, en un conjunto de dos o mas trenes de bits parciales 12, 12a, con el tren de bits 12a correspondiendose con los trenes de bits 112 y 206 de las figuras 1 y 2.

Tal como ya se ha hecho notar en lo que antecede, cada sfmbolo de origen 1a puede tener asociado al mismo una indicacion que especifica si el sfmbolo de origen se codifica usando codigos de VLC convencionales dentro del codificador de VLC 22a, el cual se corresponde con el codificador de VLC 102 en la figura 1, o en lo que respecta a si el sfmbolo de origen se va a codificar con un concepto de codificacion de PIPE. Tal como ya se ha descrito en lo que antecede con respecto a las figuras 1 y 2, esta indicacion puede no transmitirse de forma explfcita al lado de descodificacion. En su lugar, la indicacion asociada puede resultar del tipo o la categona del propio sfmbolo de origen.

Los sfmbolos codificados de VLC 1b se codifican con codigos de VLC convencionales, que a su vez, pueden depender de la categona de sfmbolos o el tipo de sfmbolo recien mencionado usando un codificador de vLc 22a. Las palabras de codigo 11a correspondientes se escriben en un tren de bits parcial distinto 12a. Los sfmbolos no de codigo VLC 1 se codifican usando codificacion de PIPE tal como se ha descrito en lo que antecede con respecto a las figuras 1 y 3, por ejemplo, con lo cual se obtienen multiples trenes de bits parciales 12. Algunos de los sfmbolos de origen 1a ya se pueden haber binarizado de una forma tal que la binarizacion consiste en dos partes tal como ya se ha mencionado en lo que antecede con respecto a la figura 1a. Una de estas partes se puede codificar con el enfoque de PIPE y escribirse en los trenes de bits parciales 12 correspondientes. La otra parte de la secuencia de contenedores se puede codificar con los codigos de VLC convencionales y escribirse en el tren de bits parcial 12a correspondiente.

El aparato de descodificacion por entropfa basico adecuado para la figura 20 se muestra en la figura 21.

El descodificador realiza basicamente las operaciones inversas del codificador de la figura 20, de tal modo que la secuencia previamente codificada de sfmbolos de origen 27, 27a se descodifica a partir de un conjunto de dos o mas trenes de bits parciales (24, 24a). El descodificador incluye dos flujos de proceso diferentes: Un flujo para solicitudes de datos, el cual reproduce el flujo de datos del codificador, y un flujo de datos, el cual representa la inversa del flujo de datos de codificador. En la ilustracion en la figura 21 las flechas de trazo discontinuo representan el flujo de solicitudes de datos, mientras que las flechas de trazo continuo representan el flujo de datos. Los bloques basicos del descodificador basicamente reproducen los bloques basicos del codificador, pero implementan las operaciones

46

5

10

15

20

25

30

35

40

45

50

55

60

inversas.

Cada solicitud de s^bolo 13a puede asociarse con una indicacion que especifica si el sfmbolo de origen se codifica usando codigos de VLC convencionales o con el concepto de codificacion de PIPE. Tal como ya se ha mencionado en lo que antecede con respecto a la figura 20, esta indicacion puede resultar de las reglas de analisis sintactico o la sintaxis de los elementos de sintaxis representados por el propio sfmbolo de origen. Por ejemplo, con respecto a las figuras 1 y 2, se ha descrito que diferentes tipos de elemento de sintaxis pueden asociarse con los diferentes esquemas de codificacion, en concreto la codificacion de VLC o la codificacion de PIPE. Lo mismo puede ser de aplicacion para diferentes porciones de binarizaciones, o mas en general, otras simbolizaciones de los elementos de sintaxis. Si un sfmbolo se somete a codificacion de VLC, la solicitud se pasa al descodificador de VLC 22a y una palabra de codigo de VCL 23a se lee a partir de un tren de bits parcial distinto 24a. El sfmbolo de descodificacion 27a correspondiente se emite. Si un sfmbolo se codifica con PIPE, el sfmbolo 27 se descodifica a partir de un conjunto de trenes de bits parciales 24 tal como se ha descrito en lo que antecede con respecto a la figura 4, por ejemplo.

Algunos de los sfmbolos de origen se pueden binarizar de una forma tal que la binarizacion consiste en dos partes. Una de estas partes se codifica con el enfoque de PIPE se descodifica de forma correspondiente a partir de los trenes de bits parciales asociados 24. Y la otra parte de la secuencia de contenedores se codifica con codigos de VLC convencionales y se descodifica con un descodificador de VLC 22a que lee las palabras de codigo 23a correspondientes a partir de un tren de bits parcial distinto 24a.

Transmision y multiplexacion de los trenes de bits parciales (sometidos a codificacion de VLC y sometidos a codificacion de PIPE)

Los trenes de bits parciales 12, 12a que se crean por el codificador se pueden transmitir por separado, o estos se pueden multiplexar para dar un unico tren de bits, o las palabras de codigo de los trenes de bits parciales se pueden intercalar en un unico tren de bits.

Dos o mas de los trenes de bits parciales 12, 12a para una cantidad de datos o todos los trenes de bits parciales para una cantidad de datos se pueden multiplexar para dar un paquete de datos. La estructura de un paquete de datos que contiene unos trenes de bits parciales multiplexados puede ser tal como se ilustra en la figura 5.

El paquete de datos 300 consiste en un encabezamiento y una particion para los datos de cada tren de bits parcial (para la cantidad considerada de datos). El encabezamiento 301 del paquete de datos contiene indicaciones para la subdivision en particiones de (el resto de) el paquete de datos en segmentos de los datos de tren de bits 302. Ademas de las indicaciones para la subdivision en particiones, el encabezamiento puede contener una informacion adicional. Las indicaciones para la subdivision en particiones del paquete de datos pueden ser las ubicaciones del comienzo de los segmentos de datos en unidades de bits o bytes o multiples de bits o multiples de bytes. Las ubicaciones del comienzo de los segmentos de datos se pueden codificar como valores absolutos en el encabezamiento del paquete de datos, o bien en relacion con el comienzo del paquete de datos o en relacion con el final del encabezamiento o bien en relacion con el comienzo del paquete de datos previo. Las ubicaciones del comienzo de los segmentos de datos se pueden codificar de forma diferencial, es decir, solo se codifica la diferencia entre el comienzo real de un segmento de datos y una prediccion para el comienzo del segmento de datos. La prediccion se puede obtener sobre la base de una informacion ya conocida o transmitida tal como el tamano global del paquete de datos, el tamano del encabezamiento, el numero de segmentos de datos en el paquete de datos, la ubicacion del comienzo de segmentos de datos precedentes. La ubicacion del comienzo del primer paquete de datos puede no codificarse, sino inferirse sobre la base del tamano del encabezamiento de paquete de datos. En el lado de descodificador, las indicaciones de particion transmitidas se usan para obtener el comienzo de los segmentos de datos. Los segmentos de datos se usan entonces como los trenes de bits parciales 12, 12a y los datos que estan contenidos en los segmentos de datos se alimentan a los descodificadores de contenedores y los descodificadores de VLC correspondientes en orden secuencial.

Intercalacion de palabras de codigo (palabras de codigo de VLC y de PIPE)

Para algunas aplicaciones, la multiplexacion que se ha descrito en lo que antecede de los trenes de bits parciales (para una cantidad de sfmbolos de origen) en un paquete de datos puede tener las siguientes desventajas: Por un lado, para unos paquetes de datos pequenos, el numero de bits para la informacion conexa que se requiere para senalizar la subdivision en particiones se puede volver significativa en relacion con los datos reales en los trenes de bits parciales, lo que en ultima instancia reduce la eficiencia de codificacion. Por otro lado, la multiplexacion puede

5

10

15

20

25

30

35

40

45

50

55

60

no ser adecuada para las aplicaciones que requieren un bajo retardo (por ejemplo, para aplicaciones de videoconferencia). Con la multiplexacion descrita, el codificador no puede iniciar la transmision de un paquete de datos antes de que los trenes de bits parciales se hayan creado completamente, debido a que las ubicaciones del comienzo de las particiones no se conodan con anterioridad. Ademas, en general, el descodificador ha de esperar hasta que este recibe el comienzo del ultimo segmento de datos antes de que este pueda iniciar la descodificacion de un paquete de datos. Para aplicaciones como sistemas de videoconferencia, estos retardos pueden sumarse a un retardo global adicional del sistema de varias imagenes de video (en particular para unas tasas de bits que se encuentran cerca de la tasa de bits de transmision y para codificadores / descodificadores que requieren casi el intervalo de tiempo entre dos imagenes para codificar / descodificar una imagen), que es cntico para tales aplicaciones. Con el fin de superar las desventajas para determinadas aplicaciones, el codificador o puede configurarse de una forma tal que las palabras de codigo que se generan mediante los dos o mas codificadores de contenedores y el codificador de VLC se intercalan para dar un unico tren de bits. El tren de bits con las palabras de codigo intercaladas puede enviarse directamente al descodificador (cuando se desprecia un pequeno retardo de memoria intermedia, vease en lo sucesivo). En el lado de descodificador, los dos o mas descodificadores de contenedores y el descodificador de VLC leen las palabras de codigo directamente a partir del tren de bits en el orden de descodificacion; la descodificacion se puede iniciar con el primer bit recibido. Ademas, no se requiere informacion conexa alguna para senalizar la multiplexacion (o intercalacion) de los trenes de bits parciales.

La estructura basica de un codificador con una intercalacion de palabras de codigo se muestra en la figura 22. Los codificadores de contenedores 10 y el codificador de VLC 10a no escriben las palabras de codigo directamente en los trenes de bits parciales, sino que se conectan con una unica memoria intermedia de palabras de codigo 29, a partir de las cual se escriben palabras de codigo en el tren de bits 34 en el orden de codificacion. Los codificadores de contenedores 10 envfan solicitudes para una o mas nuevas entradas de memoria intermedia de palabras de codigo 28 a la memoria intermedia de palabras de codigo 29 y posteriormente envfan las palabras de codigo 30 a la memoria intermedia de palabras de codigo 29, que se almacenan en las entradas de memoria intermedia reservadas. El codificador de VLC 10a escribe directamente las palabras de codigo de VLC 30a en la memoria intermedia de palabras de codigo 29. Las palabras de codigo (en general de longitud variable) 31 de la memoria intermedia de palabras de codigo 29 se acceden por una unidad de escritura de palabras de codigo 32, que escribe los bits 33 correspondientes en el tren de bits producido 34. La memoria intermedia de palabras de codigo 29 opera como una memoria intermedia de tipo primero en entrar primero en salir; las entradas de palabra de codigo que se reservan con anterioridad se escriben con anterioridad en el tren de bits.

La memoria intermedia de palabras de codigo se puede operar tal como sigue. Si un nuevo contenedor 7 se envfa a una memoria intermedia de contenedores particular 8 y el numero de contenedores ya almacenados en la memoria intermedia de contenedores es cero y en la actualidad no hay palabra de codigo alguna reservada en la memoria intermedia de palabras de codigo para el codificador de contenedores que esta conectado con la memoria intermedia de contenedores particular, el codificador de contenedores conectado 10 envfa una solicitud a la memoria intermedia de palabras de codigo, mediante la cual una o mas entradas de palabra de codigo se reservan en la memoria intermedia de palabras de codigo 29 para el codificador de contenedores particular 10. Las entradas de palabra de codigo pueden tener un numero variable de bits; un umbral superior para el numero de bits en una entrada de memoria intermedia viene dado por lo general por el tamano de palabra de codigo maximo para el codificador de contenedores correspondiente. La siguiente palabra de codigo o las siguientes palabras de codigo que se producen por el codificador de contenedores (para el que se han reservado la entrada de palabra de codigo o entradas de palabra de codigo) se almacenan en la entrada o entradas reservadas de la memoria intermedia de palabras de codigo. Si todas las entradas de memoria intermedia reservadas en la memoria intermedia de palabras de codigo para un codificador de contenedores particular se llenan con palabras de codigo y el siguiente contenedor se envfa a la memoria intermedia de contenedores que esta conectada con el codificador de contenedores particular, una o mas nuevas palabras de codigo se reservan en la memoria intermedia de palabras de codigo para el codificador de contenedores particular, etc. El codificador de VLC 10a escribe directamente las palabras de codigo de VLC 30a en la siguiente entrada libre de la memoria intermedia de palabras de codigo 29, es decir, para el codificador de VLC, la reserva de palabras de codigo y la escritura de la palabra de codigo se realizan al mismo tiempo. La memoria intermedia de palabras de codigo 29 representa una memoria intermedia de tipo primero en entrar primero en salir de una cierta forma. Las entradas de memoria intermedia se reservan en orden secuencial. Las palabras de codigo para las que las entradas de memoria intermedia correspondientes se han reservado con anterioridad se escriben con anterioridad en el tren de bits. La unidad de escritura de palabras de codigo 32 comprueba el estatus de la memoria intermedia de palabras de codigo 29, o bien de forma continua o bien despues de que una palabra de codigo 30 se escriba en la memoria intermedia de palabras de codigo 29. Si la primera entrada de memoria intermedia contiene una palabra de codigo completa (es decir, la entrada de memoria intermedia no esta reservada, sino que incluye una palabra de codigo), la palabra de codigo 31 correspondiente y la entrada de memoria intermedia correspondiente se retiran de la memoria intermedia de palabras de codigo 20 y los bits de la palabra de codigo 33 se escriben en el tren de bits. Este proceso se repite hasta que la primera entrada de memoria intermedia no contiene una palabra de codigo (es decir, esta esta reservada o es libre). Al final del proceso de descodificacion, es decir, si se han procesado todos los sfmbolos de origen de la cantidad considerada de datos, se ha de evacuar la memoria intermedia de palabras de codigo. Para ese proceso de evacuacion, lo sucesivo es de

5

10

15

20

25

30

35

40

45

50

55

60

aplicacion para cada memoria intermedia de contenedores / codificador de contenedores como una primera etapa: Si la memoria intermedia de contenedores contiene, de hecho, unos contenedores, se anade un contenedor con un valor particular o uno arbitrario hasta que la secuencia de contenedores resultante representa una secuencia de contenedores que se asocia con una palabra de codigo (tal como se ha hecho notar en lo que antecede, una forma preferida de adicion de contenedores es anadir aquellos valores de contenedor que producen la palabra de codigo posible mas corta - o una de ellas - que se asocia con una secuencia de contenedores que contiene el para contenido original de la memoria intermedia de contenedores como prefijo), entonces la palabra de codigo se escribe en la siguiente entrada de memoria intermedia reservada para el codificador de contenedores (y la correspondiente) memoria intermedia de contenedores se vacfa. Si se ha reservado mas de una entrada de memoria intermedia para uno o mas codificadores de contenedores, la memoria intermedia de palabras de codigo puede seguir conteniendo entradas de palabra de codigo reservadas. En ese caso, estas entradas de palabra de codigo se llenan con unas palabras de codigo arbitrarias pero validas para los codificadores de contenedores correspondientes. Se puede insertar la palabra de codigo valida mas corta o una de las palabras de codigo validas mas cortas (de haber una multitud). El codificador de VLC no requiere terminacion alguna. Por ultimo, todas las palabras de codigo restantes en la memoria intermedia de palabras de codigo se escriben en el tren de bits.

En la figura 23 se ilustran dos ejemplos para el estatus de la memoria intermedia de palabras de codigo. En el ejemplo (a), la memoria intermedia de palabras de codigo contiene 4 entradas que se llenan con una palabra de codigo (dos de estas son entradas de VLC) y 3 entradas reservadas. Ademas, se marca la siguiente entrada de memoria intermedia libre. La primera entrada se llena con una palabra de codigo (es decir, el codificador de contenedores 2 acababa de escribir una palabra de codigo en una entrada previamente reservada). En la siguiente etapa, esta palabra de codigo se retirara de la memoria intermedia de palabras de codigo y se escribira en el tren de bits. Entonces, la primera palabra de codigo reservada para el codificador de contenedores 3 es la primera entrada de memoria intermedia, pero esta entrada no se puede retirar de la memoria intermedia de palabras de codigo, debido a que esta solo esta reservada, pero no se ha escrito palabra de codigo alguna en esta entrada. En el ejemplo (b), la memoria intermedia de palabras de codigo contiene 4 entradas que se llenan con una palabra de codigo (una de estas es una entrada de memoria intermedia de VLC) y 4 entradas reservadas. La primera entrada se marca como reservada y, por lo tanto, la unidad de escritura de palabras de codigo no puede escribir una palabra de codigo en el tren de bits. A pesar de que 4 palabras de codigo estan contenidas en la memoria intermedia de palabras de codigo, la unidad de escritura de palabras de codigo ha de esperar hasta que se escriba una palabra de codigo en la primera entrada de memoria intermedia reservada para el codificador de contenedores 3. Observese que las palabras de codigo deben escribirse en el orden en el cual se reservaron, con el fin de ser capaces de invertir el proceso en el lado de descodificador (vease en lo sucesivo). Y observese adicionalmente que una entrada de memoria intermedia de VLC siempre esta completada, debido a que la reserva y la escritura de la palabra de codigo se realizan al mismo tiempo.

La estructura basica de un descodificador con una intercalacion de palabras de codigo se muestra en la figura 24. Los descodificadores de contenedores 22 y el descodificador de VLC 2a no leen las palabras de codigo directamente a partir de trenes de bits parciales separados, sino que estan conectados con una memoria intermedia de bits 38, a partir de la que las palabras de codigo 37, 37a se leen en el orden de codificacion. Se debena hacer notar que la memoria intermedia de bits 38 no se requiere necesariamente, debido a que las palabras de codigo tambien se podnan leer directamente a partir del tren de bits. La memoria intermedia de bits 38 se incluye principalmente en la ilustracion para separar claramente diferentes aspectos de la cadena de procesamiento. Los bits 39 del tren de bits 40 con palabras de codigo intercaladas se insertan de forma secuencial en la memoria intermedia de bits 38, la cual representa una memoria intermedia de tipo primero en entrar primero en salir. Si un descodificador de contenedores particular 22 recibe una solicitud para una o mas secuencias de contenedores 35, el descodificador de contenedores 22 lee una o mas palabras de codigo 37 a partir de la memoria intermedia de bits 38 por medio de solicitudes para bits 36. El descodificador puede descodificar de forma instantanea los sfmbolos de origen. De forma similar, si el descodificador de VLC 22a recibe una solicitud para un nuevo sfmbolo 19a, lee la palabra de codigo de VLC 37a correspondiente a partir de la memoria intermedia de bits 38 y devuelve el sfmbolo descodificado 27a. Observese que el codificador (tal como se ha descrito en lo que antecede) ha de asegurar, al operar de forma conveniente la memoria intermedia de palabras de codigo, que las palabras de codigo se escriban en el mismo orden en el tren de bits en el que estas son solicitadas por los descodificadores de contenedores. En el descodificador, la totalidad del proceso de descodificacion es desencadenado por solicitudes para sfmbolos de origen. Parametros como el numero de palabras de codigo que son reservados en el lado de codificador por un codificador de contenedores particular y el numero de palabras de codigo que se leen por el descodificador de contenedores correspondiente han de ser los mismos.

La intercalacion de palabras de codigo descrita no requiere que se envfe informacion alguna de subdivision en particiones como informacion conexa. Y debido a que las palabras de codigo se intercalan en el tren de bits, el retardo es en general pequeno. No obstante, no se garantiza que se obedezca una restriccion de retardo particular (por ejemplo, especificada por un numero maximo de bits que se almacenan en la memoria intermedia de palabras

5

10

15

20

25

30

35

40

45

50

55

60

de codigo). Ademas, el tamano de memoria intermedia requerido para la memoria intermedia de palabras de codigo se puede volver, en teona, muy grande. Cuando se considera el ejemplo en la figura 23(b), podna ser posible que no se enviara contenedor adicional alguno a la memoria intermedia de contenedores 3 y, por lo tanto, el codificador de contenedores 3 no enviara palabra de codigo nueva alguna a la memoria intermedia de palabras de codigo hasta que se aplique el proceso de evacuacion al final del paquete de datos. Entonces todas las palabras de codigo para los codificadores de contenedores 1 y 2 tendnan que esperar hasta el final del paquete de datos, antes de que estas se puedan escribir en el tren de bits. Este inconveniente puede sortearse mediante la adicion de un mecanismo adicional al proceso de codificacion (y tambien al proceso de descodificacion tal como se describe posteriormente). El concepto basico de ese mecanismo adicional es que si una medida en relacion con el retardo o un lfmite superior del retardo (vease en lo sucesivo) supera un umbral especificado, la primera entrada de memoria intermedia reservada se llena mediante la evacuacion de la memoria intermedia de contenedores correspondiente (usando un mecanismo similar al del final de un paquete de datos). Mediante un mecanismo de este tipo, el numero de entradas de memoria intermedia en espera se reduce hasta que la medida de retardo asociada es menor que el umbral especificado. En el lado de descodificador, se han de descartar los contenedores que se han insertado en el lado de codificador con el fin de obedecer la restriccion de retardo. Para este descarte de contenedores se puede usar basicamente el mismo mecanismo que en el lado de codificador.

Despues de haber descrito con detalle posibilidades para intercalar los trenes de bits de VLC y la codificacion de PIPE, en lo sucesivo, la descripcion de nuevo se centra en los elementos de sintaxis ya mencionados en lo que antecede descompuestos en sfmbolos de origen tal como se menciona con respecto a la figura 1b, 1c y 2b. Por razones de ilustracion, la siguiente descripcion supone que los elementos de sintaxis asf descompuestos son un nivel de coeficiente de transformada absoluto. No obstante, esto es solo un ejemplo, y otros tipos de elementos de sintaxis se pueden manipular de forma similar. En particular, en lo sucesivo se describe la codificacion de niveles absolutos mediante la subdivision en particiones y el uso de diferentes codigos por entrop^a en codificadores de v^deo y de imagenes basados en bloques.

Por ejemplo, las imagenes de una secuencia de video se descomponen por lo general en bloques. Los bloques o las componentes de color de los bloques se predicen mediante o bien prediccion compensada por movimiento o bien intraprediccion. Los bloques pueden tener diferentes tamanos y pueden ser o bien cuadrados o bien rectangulares. Todas las muestras de un bloque o una componente de color de un bloque se predicen usando el mismo conjunto de parametros de prediccion, tal como indices de referencia (que identifican una imagen de referencia en el conjunto de imagenes ya codificado), parametros de movimiento (que especifican una medida para el movimiento de un bloque entre una imagen de referencia y la imagen actual), parametros para especificar el filtro de interpolacion, modos de intraprediccion, etc. Los parametros de movimiento se pueden representar por unos vectores de desplazamiento con una componente horizontal y vertical o por unos parametros de movimiento de orden superior tales como unos parametros de movimiento afm que consisten en 6 componentes. Tambien es posible que mas de un conjunto de parametros de prediccion (tal como indices de referencia y parametros de movimiento) esten asociados con un unico bloque. En ese caso, para cada conjunto de parametros de prediccion, se genera una unica senal de prediccion intermedia para el bloque o la componente de color de un bloque, y la senal de prediccion final se construye mediante una suma ponderada de las senales de prediccion intermedias. Los parametros de ponderacion y potencialmente tambien una desviacion constante (que se anade a la suma ponderada) pueden o bien ser fijos para una imagen, o una imagen de referencia o un conjunto de imagenes de referencia, o bien estos se pueden incluir en el conjunto de parametros de prediccion para el bloque correspondiente. De forma similar, las imagenes fijas tambien se descomponen a menudo en bloques, y los bloques se predicen mediante un metodo de intraprediccion (que puede ser un metodo de intraprediccion espacial o un metodo de intraprediccion simple que predice la componente de CC del bloque). En un caso lfmite, la senal de prediccion tambien puede ser cero.

La diferencia entre los bloques originales o las componentes de color de los bloques originales y las senales de prediccion correspondientes, a la que tambien se hace referencia como senal residual, por lo general se transforma y se cuantifica. Una transformada bidimensional se aplica a la senal residual y los coeficientes de transformada resultantes se cuantifican. Para esta codificacion de transformada, los bloques o las componentes de color de los bloques, para los cuales se ha usado un conjunto particular de parametros de prediccion, se pueden dividir adicionalmente antes de la aplicacion de la transformada. Los bloques de transformada pueden ser iguales a o mas pequenos que los bloques que se usan para la prediccion. Tambien es posible que un bloque de transformada incluya mas de uno de los bloques que se usan para la prediccion. Diferentes bloques de transformada en una imagen fija o una imagen de una secuencia de video pueden tener diferentes tamanos y los bloques de transformada pueden representar unos bloques cuadrados o rectangulares.

La totalidad de estos parametros de prediccion y residuales pueden formar el tren de los elementos de sintaxis 138 y 226, de forma respectiva.

Los coeficientes de transformada cuantificados resultantes, a los que tambien se hace referencia como niveles de coeficiente de transformada, se pueden transmitir entonces usando una codificacion por entropfa mediante cualquiera de los esquemas de codificacion anteriores. Con este fin, un bloque de niveles de coeficientes de

5

10

15

20

25

30

35

40

45

50

55

60

transformada se puede poner en correspondencia con un vector (es dedr, un conjunto ordenado) de valores de coeficiente de transformada usando una exploracion, en donde se pueden usar diferentes exploraciones para diferentes bloques. A menudo se usa una exploracion en zig-zag. Para los bloques que contienen solo muestras de un campo de una trama intercalada (estos bloques pueden ser bloques en campos codificados o bloques de campos en tramas codificadas), tambien es comun el uso de una exploracion diferente que esta disenada de forma espedfica para los bloques de campos. Un posible esquema de codificacion para codificar la secuencia ordenada resultante de coeficientes de transformada es la codificacion de nivel de series. Por lo general, un gran numero de los niveles de coeficiente de transformada son cero, y un conjunto de niveles de coeficiente de transformada sucesivos que son iguales a cero se puede representar de forma eficiente mediante la codificacion del numero de niveles de coeficiente de transformada sucesivos que son iguales a cero (la serie) por un elemento de sintaxis respectivo. Para los coeficientes de transformada (no nulos) restantes, el nivel real se codifica en la forma de unos elementos de sintaxis respectivos. Hay diversas alternativas de codigos de nivel de series. La serie antes de un coeficiente no nulo y el nivel del coeficiente de transformada no nulo se pueden codificar de forma conjunta usando un unico elemento de sintaxis. A menudo, se incluyen elementos de sintaxis especiales para el fin de bloque, el cual se envfa despues del ultimo coeficiente de transformada no nulo. O es posible codificar en primer lugar el numero de niveles de coeficiente de transformada no nulo, y dependiendo de este numero, se codifican los niveles y las series.

Un enfoque algo diferente se usa en la muy eficiente codificacion por entropfa de CABAC en la norma H.264 / AVC. En el presente caso, la codificacion de los niveles de coeficiente de transformada se divide en tres etapas. En la primera etapa, un elemento de sintaxis binario encoded_block_flag se transmite para cada bloque de transformada, el cual senaliza si el bloque de transformada contiene niveles de coeficiente de transformada significativos (es decir, coeficientes de transformada que son no nulos). Si este elemento de sintaxis indica que se encuentran presentes unos niveles de coeficiente de transformada significativos, se codifica una correspondencia de significacion de valores binarios, la cual especifica cual de los niveles de coeficiente de transformada tiene unos valores no nulos. Y entonces, en un orden inverso al de exploracion, se codifican los valores de los niveles de coeficiente de transformada no nulo. La correspondencia de significacion se codifica para dar el tren de elementos de sintaxis 138 tal como sigue. Para cada coeficiente en el orden de exploracion, se codifica un elemento de sintaxis binario significant_coeff_flag, el cual especifica si el nivel de coeficiente de transformada correspondiente no es igual a cero. Si el contenedor significant_coeff_flag es igual a uno, es decir, si existe un nivel de coeficiente de transformada no nulo en la posicion de exploracion, se codifica un elemento de sintaxis binario adicional last_significant_coeff_flag. Este contenedor indica si el nivel de coeficiente de transformada significativo actual es el ultimo nivel de coeficiente de transformada significativo en el interior de un bloque o si niveles de coeficiente de transformada significativos adicionales siguen en el orden de exploracion. Si last_significant_coeff_flag indica que no sigue coeficiente de transformada significativo adicional alguno, no se codifica elemento de sintaxis adicional alguno para especificar la correspondencia de significacion para el bloque. En la siguiente etapa, se codifican los valores de los niveles de coeficiente de transformada significativos, cuyas ubicaciones en el interior de un bloque ya estan determinadas por la correspondencia de significacion. Los valores de los niveles de coeficiente de transformada significativos se codifican en el orden inverso al de exploracion mediante el uso de los siguientes tres elementos de sintaxis. El elemento de sintaxis binario coeff_abs_greater_one indica si el valor absoluto del nivel de coeficiente de transformada significativo es mayor que uno. Si el elemento de sintaxis binario coeff_abs_greater_one indica que el valor absoluto es mayor que uno, se envfa un elemento de sintaxis adicional coeff_abs_level_minus_two, el cual especifica el valor absoluto del nivel de coeficiente de transformada menos dos. Este es el tipo de elemento de sintaxis el procesamiento el cual se puede realizar de acuerdo con la figura 1b, 1c y 2b. Por ultimo, el elemento de sintaxis binario coeff_sign_flag, el cual especifica el signo del valor de coeficiente de transformada, se codifica para cada nivel de coeficiente de transformada significativo. Se debena hacer notar de nuevo que los elementos de sintaxis que se refieren a la correspondencia de significacion se codifican en el orden de exploracion, mientras que los elementos de sintaxis que se refieren a los valores reales de los niveles de coeficientes de transformada se codifican en el orden inverso al de exploracion permitiendo el uso de mas modelos de contexto adecuados. Tambien es posible que se use un patron de exploracion adaptativo para la correspondencia de significacion como en el primer modelo de prueba de la norma H.265 / HEVC. Otro concepto se usa para la codificacion de los niveles de coeficiente de transformada absolutos para unos bloques de transformada mas grandes que 4 x 4 en el primer modelo de prueba de la norma H.265 / HEVC. En el caso de unos bloques de transformada mas grandes que 4 x 4, el bloque de transformada mas grande se subdivide en particiones para dar bloques de 4 x 4 y los bloques de 4 x 4 se codifican en el orden de exploracion mientras que para cada bloque de 4 x 4, se usa el orden inverso al de exploracion.

En la codificacion por entropfa de CABAC en la norma H.264 / AVC, todos los elementos de sintaxis para los niveles de coeficiente de transformada se codifican usando un modelado de probabilidad binaria. El elemento de sintaxis no binario coeff_abs_level_minus_two, por ejemplo, se binariza en primer lugar, es decir, se pone en correspondencia con una secuencia de decisiones binarias (contenedores), y estos contenedores se codifican de forma secuencial. Los elementos de sintaxis binarios significant_coeff_flag, last_significant_coeff_flag, coeff_abs_greater_one, y coeff_sign_flag se codifican directamente. Cada contenedor codificado (incluyendo los elementos de sintaxis binarios) se asocia con un contexto. Un contexto representa un modelo de probabilidad para una clase de contenedores codificados. Una medida en relacion con la probabilidad para uno de los dos valores de contenedor

5

10

15

20

25

30

35

40

45

50

55

60

posibles se estima para cada contexto sobre la base de los valores de los contenedores que ya se han codificado con el contexto correspondiente. Para varios contenedores en relacion con la codificacion de transformada, el contexto que se usa para la codificacion se selecciona sobre la base de elementos de sintaxis ya transmitidos o sobre la base de la posicion en el interior de un bloque.

Despues de la codificacion de la correspondencia de significacion, el bloque se procesa en el orden inverso al de exploracion. Tal como se ha mencionado antes, otro concepto se usa en el primer modelo de prueba de la norma H.265 / HEVC. Los bloques de transformada mas grandes que 4 x 4 se subdividen en particiones para dar bloques de 4 x 4 y los bloques de 4 x 4 resultantes se procesan en el orden de exploracion, mientras que los coeficientes de los bloques de 4 x 4 se codifican en el orden inverso al de exploracion. La siguiente descripcion es valida para todos los bloques de 4 x 4 en el primer modelo de prueba de la norma H.265 / HEVC y H.264 / AVC y tambien para los bloques de 8 x 8 en la norma H.264 / AVC y esta descripcion tambien se puede aplicar a la construccion del tren de los elementos de sintaxis 138 y 226, de forma respectiva.

Si una posicion de exploracion es significativa, es decir, el coeficiente es diferente de cero, el elemento de sintaxis binario coeff_abs_greater_one se transmite dentro del tren 138. Inicialmente (en el interior de un bloque), el segundo modelo de contexto del conjunto de modelo de contexto correspondiente se selecciona para el elemento de sintaxis coeff_abs_greater_one. Si el valor codificado de cualquier elemento de sintaxis coeff_abs_greater_one en el interior de un bloque es igual a uno (es decir, el coeficiente absoluto es mayor que 2), el modelado de contexto conmuta de vuelta al primer modelo de contexto del conjunto y usa este modelo de contexto hasta el final del bloque. De lo contrario (todos los valores codificados de coeff_abs_greater_one en el interior de un bloque son cero y los niveles de coeficiente absolutos correspondientes son iguales a uno), el modelo de contexto se elige dependiendo del numero de los elementos de sintaxis coeff_abs_greater_one igual a cero que ya se han procesado en la exploracion inversa del bloque considerado. La seleccion de modelo de contexto para el elemento de sintaxis coeff_abs_greater_one se puede resumir por la siguiente ecuacion, en la que el mdice de modelo de contexto actual Ct+i se selecciona sobre la base del mdice de modelo de contexto previo Ct y el valor del elemento de sintaxis previamente codificado coeff_abs_greater_one, el cual se representa por contenedort en la ecuacion. Para el primer elemento de sintaxis coeff_abs_greater_one en el interior de un bloque, el mdice de modelo de contexto se establece igual a Ci = 1.

imagen16

0

min(C, +1,4)

bin, = 1 bin, = 0

El segundo elemento de sintaxis para codificar los niveles de coeficiente de transformada absolutos, coeff_abs_level_minus_two solo se codifica cuando el elemento de sintaxis coeff_abs_greater_one para la misma posicion de exploracion es igual a uno. El elemento de sintaxis no binario coeff_abs_level_minus_two se binariza en una secuencia de contenedores y para el primer contenedor de esta binarizacion; un mdice de modelo de contexto se selecciona tal como se describe en lo sucesivo. Los contenedores restantes de la binarizacion se codifican con unos contextos fijos. El contexto para el primer contenedor de la binarizacion se selecciona tal como sigue. Para el primer elemento de sintaxis coeff_abs_level_minus_two, se selecciona el primer modelo de contexto del conjunto de modelos de contexto para el primer contenedor del elemento de sintaxis coeff_abs_level_minus_two, el mdice de modelo de contexto correspondiente se establece igual a Ci = 0. Para cada primer contenedor adicional del elemento de sintaxis coeff_abs_level_minus_two, el modelado de contexto conmuta al siguiente modelo de contexto en el conjunto, en donde el numero de modelos de contexto en el conjunto esta limitado a 5. La seleccion de modelo de contexto puede expresarse por la siguiente formula, en la que el mdice de modelo de contexto actual Ct+i se selecciona sobre la base del mdice de modelo de contexto previo Ct.

Ct+i (Ct) = mm (Ct+1, 4)

Tal como se ha mencionado antes, para el primer elemento de sintaxis coeff_abs_remain_minus_two en el interior de un bloque, el mdice de modelo de contexto se establece igual a Ct = 0. Observese que se pueden definir diferentes conjuntos de modelos de contexto para los elementos de sintaxis coeff_abs_greater_one y coeff_abs_remain_minus_two. Tambien observese que para el primer modelo de prueba de la norma H.265 / HEVC, los bloques de transformada mas grandes que 4 x 4 se pueden subdividir en particiones para dar bloques de 4 x 4. Los bloques de 4 x 4 subdivididos en particiones se pueden procesar en el orden de exploracion y para cada bloque de 4 x 4 subdividido en particiones, un conjunto de contexto se puede obtener sobre la base del numero de coeficientes mayor que uno en el bloque de 4 x 4 previo. Para el primer bloque de 4 x 4 de un bloque de transformada mas grande que 4 x 4 y para los bloques de transformada de 4 x 4 de origen se pueden usar un conjunto de contexto separado.

Es decir, siempre que en la siguiente descripcion se use una codificacion basada en contexto para cualquiera de los sfmbolos de origen en la que coeff_abs_greater_one y coeff_abs_remain_minus_two puede descomponerse tal como sigue, entonces esta obtencion de contexto puede ser usada por la unidad de asignacion 114 y 212 y el

5

10

15

20

25

30

35

40

45

50

55

60

codificador / descodificador de VLC 102 y 202, por ejemplo.

Con el fin de reducir la complejidad en terminos del numero de contenedores que son procesados por CABAC o PIPE en comparacion con las tecnicas del estado de la tecnica y tambien en terminos de la complejidad de computacion o tambien para incrementar la eficiencia de codificacion, la explicacion posterior describe un enfoque para codificar niveles absolutos mediante el uso de diferentes codigos de longitud variable para diferentes particiones 140i a 1403 en codificadores y descodificadores de imagen y de video. La posibilidad que se bosqueja en lo sucesivo se puede aplicar, no obstante, a todo tipo de niveles absolutos para codificadores de video y de imagen, como diferencias de vector de movimiento o coeficientes del filtro de lazo adaptativo. Mientras que la codificacion de niveles de coeficientes de transformada se realiza tal como se bosqueja en lo sucesivo, la codificacion de la correspondencia de significacion puede permanecer como en el primer modelo de prueba de la norma H.265 / HEVC o tal como se ha descrito en lo que antecede, o la codificacion de la correspondencia de significacion tambien se puede realizar como en la norma H.264 / AVC o de otro modo.

Tal como se ha descrito en lo que antecede, la codificacion de los niveles de transformada absolutos se realiza en multiples particiones 140i-3. El esquema de codificacion se ha ilustrado a modo de ejemplo en la figura 1b con tres particiones 140i-3. Los lfmites 142 y 144 del esquema son variables, lo que da como resultado unos tamanos de particion variables. El esquema de codificacion se realiza tal como sigue.

Un primer codigo por entropfa se usa para codificar la primera componente o sfmbolo de origen, es decir un nivel de coeficiente de transformada absoluto (z) en el caso de que el mismo sea mas pequeno que Kmite1, o lfmite1 en el caso de que el mismo no lo sea. Si el nivel de coeficiente de transformada absoluto es mayor que o igual al lfmite lfmite1 de la primera particion 1401, entonces el lfmite lfmite1 (142) de la primera particion (1401) se resta del nivel de coeficiente de transformada absoluto y el valor resultante z' se codifica con un segundo codigo por entropfa. Si el nivel de coeficiente de transformada absoluto restante z' es mayor que o igual a un lfmite lfmite2 - lfmite1 para la segunda particion 1402, entonces el lfmite lfmite2 - lfmite1 de la segunda particion se resta de nuevo del nivel de coeficiente de transformada absoluto z' y el valor resultante se codifica con un tercer codigo por entropfa. Hablando en terminos generales, cuando se alcanza el lfmite de una particion, el codigo por entropfa para la siguiente particion hasta el lfmite se usa para codificar el valor resultante de los niveles de coeficiente de transformada absolutos menos el lfmite de la particion correspondiente.

Los codigos por entropfa pueden ser codigos de longitud variable simples como codigos de longitud de series o tablas de consulta (por ejemplo, el codigo de Huffman) o codigos por entropfa mas complejos que emplean modelos de probabilidad como CABAC o PIPE. El numero de particiones y el lfmite de las particiones pueden ser variables o dependientes del elemento de sintaxis real. El concepto de subdivision en particiones que se muestra en la figura 1b tiene los siguientes beneficios. En lo sucesivo, se usan los coeficientes de transformada absolutos como un ejemplo, pero se debena entender que estos se pueden sustituir con cualquier otro elemento de sintaxis. Como un ejemplo, la distribucion de probabilidad de los niveles de coeficiente de transformada absolutos puede ser aproximadamente una distribucion geometrica. Por lo tanto, los codigos por entropfa optimizados para distribuciones geometricas se pueden emplear para codificar los niveles de coeficiente de transformada absolutos. Pero un modelo de este tipo no es siempre localmente optimo, incluso si se emplean modelado de contexto y seleccion de modelos de probabilidad. Por ejemplo, para un bloque de transformada, los niveles de coeficiente de transformada absolutos locales siguen una distribucion la cual no es en absoluto geometrica si esta contiene la misma cantidad de niveles de coeficiente de transformada de rango muy bajo y medio, mientras que el modelo puede ser cierto (con una cierta precision) para una cantidad espedfica de bloques en imagenes o video debido a la ley de los grandes numeros. Para un caso de este tipo, la distribucion geometrica no es un modelo adecuado. Asimismo, cuando se consideran unos niveles de coeficiente de transformada absolutos con valores grandes, la distribucion de estos valores grandes es a menudo uniforme. El concepto de subdivision en particiones permite diferentes modelos de probabilidad para diferentes niveles de coeficiente de transformada absolutos. Para unos valores absolutos mas bajos, se pueden aplicar codigos por entropfa mas complejos para una eficiencia mas alta, mientras que para niveles absolutos grandes, se pueden emplear codigos por entropfa menos complejos para reducir la complejidad.

Tal como se ha mencionado antes, se usan codigos por entropfa adecuados para las diferentes particiones. Se pueden emplear tres tipos de codigos por entropfa. El primer codigo por entropfa usa PIPE. No obstante, se debena hacer notar que, de acuerdo con una alternativa, un metodo de codificacion por entropfa como CABAC o, como alternativa, se puede usar cualquier otro codificador aritmetico. Es decir, los primeros sfmbolos s1 (vease la figura 2b) se pueden codificar por medio de la trayectoria de codificacion de PIPE. El subdivisor 100 y el recombinador 220 actuan en consecuencia.

Para el segundo tipo, se pueden usar codigos de Golomb y algunas variantes truncadas incluyendo subconjuntos (por ejemplo, codigos de Golomb-Rice). Es decir, los segundos sfmbolos s2 (vease la figura 2b) se pueden codificar por medio de tales codigos de VLC en el codificador / descodificador de VLC 102 / 202. El subdivisor 100 y el recombinador 220 actuan en consecuencia.

Se usan codigos de Golomb Exponencial como el tercer tipo. Es decir, los terceros sfmbolos s3 (vease la figura 2b)

5

10

15

20

25

30

35

40

45

50

55

se pueden codificar por medio de tales codigos de VLC en el codificador / descodificador de VLC 102 / 202. El subdivisor 100 y el recombinador 220 actuan en consecuencia. Son posibles diferentes codigos de VLC y diferentes combinaciones de codigos de VLC y de PIPE o de VLC y aritmeticos.

Mientras que el primer codigo es mas complejo pero da un mejor rendimiento de compresion, los segundos codigos por entropfa representan una compensacion redproca razonable entre la complejidad y el rendimiento. Los ultimos codigos por entropfa, por ejemplo los codigos de Golomb Exponencial, son de una complejidad muy baja. En lo sucesivo, se describe la codificacion de las diferentes particiones.

Si una particion tal como la particion 1401, tal como el sfmbolo s1, se va a codificar por entropfa usando un codificador por entropfa empleando modelos de probabilidad como el codificador de PIPE 104 (de nuevo, se puede usar CABAC o cualquier otro codificador aritmetico en una alternativa que no se describe adicionalmente en el presente caso), el subdivisor 120 dirige la misma hacia el codificador de PIPE 104. En primer lugar, los niveles de coeficiente de transformada absolutos de valor no binario se pueden binarizar en el simbolizador 122 usando un metodo de binarizacion. La binarizacion pone en correspondencia los niveles de coeficiente de transformada absolutos de valor no binario con una secuencia de contenedores binarios. Cada contenedor de la cadena de contenedores se codifica con un contexto elegido por la unidad de asignacion 114. El modelado de contexto se puede realizar para el primer contenedor y ser fijo para los siguientes contenedores de la secuencia de contenedores como coeff_abs_level_minus_two en la norma H.264 / AVC o se puede usar un modelado de contexto diferente para cada contenedor de la cadena de contenedores. Observese que la binarizacion puede ser un codigo de longitud variable como los codigos de Golomb o los codigos de Golomb Exponencial u otros codigos de longitud variable.

A continuacion, una particion tal como la particion 1402 o los sfmbolos s2 se pueden codificar con un codigo de Golomb, en el presente caso en el codificador de VLC 102 y se pueden descodificar de forma respectiva en el descodificador de VLC. Los codigos de Golomb son un conjunto de codigos por entropfa que estan disenados para un origen distribuido geometrico. Si el orden del codigo de Golomb es cero, el codigo de Golomb tambien se conoce como codigo unario. El codigo unario se refiere a la binarizacion de coeff_abs_level_minus_two en la norma H.264 / AVC. Los codigos de Golomb se construyen tal como sigue. Para un parametro de Golomb k espedfico, el valor n se divide por el parametro de Golomb k usando division de numeros enteros y se calcula el resto r.

imagen17

r = n - pk

Despues de obtener los parametros especificados por las formulas en lo que antecede, el valor n se puede codificar con dos partes. La primera parte, a la que tambien se hace referencia como parte de prefijo, es un codigo unario. El valor resultante p + 1 especifica el numero de unos y un cero de terminacion o viceversa. El valor del resto, al que tambien se hace referencia como parte de resto y se indica por r, se representa con un codigo binario truncado. Los codigos de Golomb-Rice se emplean para codificar los sfmbolos de origen tales como los sfmbolos de origen s2, siendo los codigos de Golomb-Rice un subconjunto de los codigos de Golomb. Asimismo, cuando se usan tales codigos por entropfa para las particiones 1401-3 que contienen un lfmite, tal como la particion 1402 el alfabeto de los sfmbolos de origen respectivos (tales como los sfmbolos de origen s2) esta limitado y el codigo de Golomb-Rice se puede modificar de tal modo que se puede mejorar la eficiencia de codificacion. El parametro del codigo de Golomb- Rice puede ser fijo o variable. Si el parametro es variable, el parametro se puede estimar como una parte de la fase de modelado de contexto. Por ejemplo, si un sfmbolo de origen s2 entra en el codificador de VLC 102, este ultimo puede determinar el parametro del codigo de Golomb-Rice a partir de un contexto de s2. Los codigos de Golomb- Rice son codigos de Golomb con unos parametros elevados a la potencia de dos. Por lo tanto, estos se basan en la division y multiplicacion por dos y, por lo tanto, estos se pueden implementar de forma eficiente en una arquitectura binaria con unas operaciones de desplazamiento y de adicion. La relacion entre el parametro de Golomb-Rice y el parametro de Golomb es, por lo tanto, kGOLOMB = 2kRICE. En el caso del codigo de Golomb-Rice, la parte de resto es exactamente la representacion binaria del valor del resto. Para el parametro de Golomb-Rice de cero, el codigo resultante es identico al codigo unario y no tiene una parte de resto. Para el parametro igual a uno, la parte de resto consiste en un contenedor con dos sfmbolos de entrada que comparten el mismo prefijo unario. En lo sucesivo, se ilustran algunas tablas a modo de ejemplo para unos parametros de Golomb-Rice seleccionados.

Valor: Prefijo Resto Prefijo Resto Prefijo Resto Prefijo Resto

: k = 0 k = 1 k = 2 k = 3

0
0: 0 0 0 00 0 000

5

10

15

20

25

30

35

40

45

1: 10 0 1 0 01 0 001

2: 110 10 0 0 10 0 010

3: 1110 10 1 0 11 0 011

4: 11110 110 0 10 00 0 100

5: 111110 110 1 10 01 0 101

6: 1111110 1110 0 10 10 0 110

7: 11111110 1110 1 10 11 0 111

8: 111111110 11110 0 110 00 10 000

9: 1111111110 11110 1 110 01 10 001

10: 11111111110 111110 0 110 10 10 010

11: 111111111110 111110 1 110 11 10 011

12: 1111111111110 1111110 0 1110 00 10 100

13: 11111111111110 1111110 1 1110 01 10 101

Dado el rango de la particion tal como por ejemplo Kmite2 - Kmite1 en el caso de la particion 1402 y el parametro del codigo de Golomb-Rice, el truncamiento se puede realizar tal como sigue. El parametro de Golomb-Rice describe el numero de contenedores que se requieren para representar la parte de resto y el dos elevado a la potencia del valor de parametro describe el numero de valores, el cual se puede representar con el mismo prefijo. Estos valores forman un grupo de prefijo. Por ejemplo, para el parametro cero, solo un prefijo puede representar un valor espedfico, mientras que para el parametro tres, ocho valores de entrada comparten el mismo prefijo y, por lo tanto, un grupo de prefijo contiene ocho valores para el parametro tres. Para un alfabeto de origen limitado y un codigo de Golomb-Rice dado, el ultimo contenedor del prefijo se puede omitir para los valores en el ultimo grupo de prefijo lo que da como resultado un codigo de prefijo con una longitud fija.

Por ejemplo, el rango puede ser nueve y el parametro de Golomb-Rice es dos. Para el presente caso a modo de ejemplo, el numero de valores que se puede representar con un mismo prefijo es cuatro. El valor maximo es nueve, lo que tambien indica que se supera la frontera y que se ha de usar el siguiente codigo por entropfa de la siguiente particion. En el presente caso a modo de ejemplo, los valores de 0 a 3 tienen el prefijo 0, los valores de 4 a 7 tienen el prefijo 10 y de 8 a 9 el prefijo 110. Debido a que los valores 8 - 9 formaron el ultimo grupo de prefijo, su cero final se puede omitir y los valores 8 - 9 se pueden representar por 11. Dicho de otra forma, imagmese que un sfmbolo de origen s2 entro en el codificador de VLC 102 con el numero de valores posibles de s2 siendo 9 (= lfmite2 - lfmite1 + 1) y el parametro de Golomb-Rice para ese sfmbolo de origen siendo dos. Entonces, una palabra de codigo de Golomb-Rice respectiva sena emitida por el codificador de VLC 102 para ese sfmbolo de origen, el cual tiene un prefijo tal como se acaba de describir. Para la parte de resto de la palabra de codigo, el codigo truncado se puede obtener tal como sigue por el codificador de vLc 102. Normalmente, el parametro de los codigos de Golomb-Rice indica el numero de contenedores de la parte de resto. En un caso truncado, no es necesario que se codifiquen todos los contenedores del resto. Para un caso truncado, se recuentan todos los valores con un prefijo fijo (por ejemplo, se omite un contenedor del prefijo). Observese que el valor contado es siempre mas pequeno que o igual al numero maximo de valores para un prefijo debido a que el codigo esta truncado. Si es posible un truncamiento de la parte de resto, la obtencion de la parte de resto truncado para el ultimo grupo de prefijo puede proseguir en las siguientes etapas. En primer lugar, se obtiene el numero mas grande l elevado a la potencia de dos menor o igual que el numero contado. Entonces, en la segunda etapa, se obtiene el mas pequeno numero h elevado a la potencia de dos mayor que el numero contado. El primer valor l describe el numero de valores en el grupo de prefijo con un resto de h contenedores. Todos los restos de estos valores comienzan con un 0 seguido por la representacion binaria del resto limitada al numero de valores en el grupo de restos. Para los valores restantes del ultimo grupo de prefijo, que se tratan ahora como un nuevo grupo de prefijo, se realiza el mismo procedimiento excepto por los valores resultantes que formaban el primer grupo de restos, el resto comienza con un 1. Este procedimiento se realiza hasta que se obtienen todos los restos. Como un ejemplo, el rango es 14 y el parametro es tres. El primer grupo de prefijo contiene unos valores de 0 a 7 y el segundo grupo de prefijo contiene unos valores de 8 a 13. El segundo grupo de prefijo contiene seis valores. Los parametros son l = 2 y h = 3. Por lo tanto, los primeros cuatro valores de los grupos de prefijo se representan por un resto con tres contenedores (un cero final y la representacion binaria para distinguir los cuatro valores). Para los ultimos dos valores, el mismo procedimiento se realiza de nuevo. Los parametros son l = y h = 2. El resto de los ultimos dos valores se pueden representar entonces como 10 y 11. Otro ejemplo para mostrar el metodo es un parametro de Golomb-Rice de cuatro y un rango de diez. Para el presente ejemplo, los parametros son l = 3 y h = 4. Con estos parametros, la parte de resto truncado para los primeros ocho valores se representa por cuatro contenedores. Los dos valores restantes tienen la misma parte de resto que en el ejemplo previo en lo que antecede. Si el rango es nueve para el ejemplo previo, el parametro para la segunda serie es l = 0 y h = 1. La parte de resto del unico valor que queda es 1.

El tercer tipo de codigos por entropfa pueden ser codigos de Golomb Exponencial. Estos se pueden emplear para

5

10

15

20

25

30

35

40

45

50

55

unas distribuciones equiprobables (por ejemplo, con parametro cero) tales como los s^bolos de origen S3. Es dedr, el par de codificador / descodificador de VLC puede ser responsable de su codificacion. Tal como se ha mencionado antes, los niveles de coeficiente de transformada absolutos mas grandes a menudo se distribuyen de manera uniforme. Mas precisamente, el codigo de Golomb Exponencial de orden cero se puede usar para codificar la ultima particion 1403. El comienzo y, por lo tanto, la frontera 144 para la particion previa 1402 pueden ser variables. La posicion de la frontera 144 puede ser controlada por el codificador / descodificador de VLC 102 / 200 con dependencia de los sfmbolos de origen 106, 108 y / o 110 previamente codificados / descodificados o los elementos de sintaxis 138 (o 218, 204 y / o 208 o los elementos de sintaxis 226).

El numero de particiones puede ser tres tal como se muestra en la figura 1b y los lfmites 142 y 144 pueden ser variables. Para la primera particion 1401, la codificacion de PIPE se puede emplear tal como se ha analizado en lo que antecede. No obstante, como alternativa tambien se puede usar CABAC. En ese caso, el par de codificador / descodificador de PIPE se sustituina por un par de codificador / descodificador de codificacion aritmetica binaria. Los codigos de Golomb-Rice truncados se pueden usar para la segunda particion 1402 y el codigo de Golomb Exponencial de orden cero se puede usar para la ultima particion 1403.

El numero de particiones puede ser igual a dos. La primera particion 1401 podna usar CABAC o PIPE. La segunda particion podna usar codigos de Golomb-Rice tales como 1402.

El numero de particiones puede ser igual a tres mientras que ambas fronteras 142 y 144 son variables. Por ejemplo, para la primera particion 1401, se emplea CABAC o PIPE, mientras que la segunda particion 1402 puede usar el codigo de Golomb-Rice truncado y la tercera particion 1403 usa el codigo de Golomb Exponencial de orden cero.

El lfmite 142 de la primera particion 1401 usando CABAC o PIPE, que emplea modelos de probabilidad adaptativos, puede ser dos. El modelado de contexto para el primer contenedor se puede realizar tal como se describe para coeff_abs_greater_one tal como se ha descrito en lo que antecede y el modelado de contexto para el segundo contenedor se puede realizar tal como se describe para coeff_abs_level_minus_two en la norma H.264 / AVC tal como se ha descrito tambien en lo que antecede. Esta ultima determinacion de contexto sena determinada por las unidades de asignacion 114 y 212, de forma respectiva. El lfmite 142 de la primera particion 1401 usando una codificacion por entropfa que emplea modelado de probabilidad (por ejemplo, PIPE o CABAC) puede ser dos y el modelado de contexto tanto para el primero como para el segundo contenedor se puede realizar tal como se describe para coeff_abs_greater_one en la norma H.264 / AVC tal como se ha descrito en lo que antecede. La evaluacion de conjuntos de contexto tal como se describe para coeff_abs_greater_one se puede realizar por separado para el segundo contenedor.

Se puede usar un conjunto de codigos de Golomb-Rice truncados como codigos por entropfa de la segunda particion 1402. El lfmite 144 de la segunda particion que especifica el comienzo de la tercera particion 1403 dependiendo del parametro de codigo por entropfa puede ser variable. Asimismo, el parametro de Golomb-Rice puede estar limitado por tres y la seleccion de parametros se puede realizar como el modelado de contexto para coeff_abs_level_minus_two en la norma H.264 / AVC. El rango lfmite - lfmite2 puede ser variable y puede depender del parametro de Golomb-Rice. Si el parametro es cero, el rango es 8. Para el parametro uno, el rango es 10. En el caso del parametro dos, el rango es 12 y para el parametro tres, el rango es igual a 16. En el presente ejemplo, el parametro de Golomb-Rice puede establecerse a cero en el comienzo de un bloque de coeficientes de transformada. Para cada nivel de coeficiente de transformada codificado en el bloque mas grande o igual que el primer lfmite, se usa el codigo de Golomb-Rice correspondiente. Despues de la codificacion (o la descodificacion) de un nivel, se hace la siguiente evaluacion para actualizar el parametro de Golomb-Rice para la codificacion (o la descodificacion) del siguiente nivel mayor o igual que el primer lfmite. Observese que el parametro de Golomb-Rice no se puede disminuir mediante el uso de esta forma de adaptacion.

La regla de adaptacion de parametros se puede resumir tal como sigue, en donde k+1 indica el parametro de Golomb-Rice que se va a usar para la codificacion del siguiente valor de nivel y valort indica el valor previamente codificado con el parametro de Golomb-Rice correspondiente kt

'0: valor, e [0,1] a kt < 1

1: valor, e [2,3] a kt < 2

2: valor, £ [4,5] a k, < 3

3: valor, > 5 a k, <4

A: en otro caso

(QQ)

En una realizacion preferida, se puede usar un conjunto de codigos de Golomb-Rice truncados entropfa de la segunda particion 1402. El lfmite 144 de la segunda particion 1402 que especifica

56

como codigos por el comienzo de la

5

10

15

20

25

30

35

40

45

50

55

60

tercera particion 1403 dependiendo del parametro de codigo por entropfa puede ser variable. Tambien en la presente realizacion preferida, el parametro de Golomb-Rice puede estar limitado por tres y la seleccion de parametros se puede realizar como modelado de contexto para coeff_abs_level_minus_two en la norma H.264 / AVC. El rango puede ser variable y depender del parametro de Golomb-Rice. Si el parametro es cero, el rango es 8. Para el parametro uno, el rango es 10. En el caso del parametro dos, el rango es 12 y para el parametro tres, el rango es igual a 16. En la presente realizacion preferida, el parametro de Golomb-Rice se establece a cero en el comienzo del bloque. La adaptacion de parametros de Golomb-Rice se realiza tal como se describe mediante la ecuacion (QQ). Observese que el parametro no se puede disminuir mediante el uso de esta forma de adaptacion.

En otra realizacion preferida, se puede usar un conjunto de codigos de Golomb-Rice truncados como codigos por entropfa de la segunda particion 1402. El lfmite 144 de la segunda particion 1402 que especifica el comienzo de la tercera particion 1403 dependiendo del parametro de codigo por entropfa puede ser fijo. Tambien en la presente realizacion preferida, el parametro de Golomb-Rice puede estar limitado a tres y la seleccion de parametros se puede realizar como modelado de contexto para coeff_abs_level_minus_two en la norma H.264 / AVC. El rango de la segunda particion 1402 se puede fijar a 14. En la presente realizacion preferida, el parametro de Golomb-Rice puede establecerse a cero en el comienzo del bloque. La adaptacion de parametros de Golomb-Rice se realiza tal como se describe mediante la ecuacion (QQ). Observese que el parametro no se puede disminuir mediante el uso de esta forma de adaptacion.

En otra realizacion preferida, se puede usar un conjunto de codigos de Golomb-Rice truncados como codigos por entropfa de la segunda particion 1402. El lfmite 144 de la segunda particion 1402 que especifica el comienzo de la tercera particion 1403 dependiendo del parametro de codigo por entropfa puede ser variable. Tambien en la presente realizacion preferida, el parametro de Golomb-Rice puede estar limitado a tres y la seleccion de parametros se puede realizar como modelado de contexto para coeff_abs_level_minus_two en la norma H.264 / AVC. El rango puede ser variable y depender del parametro de Golomb-Rice. Si el parametro puede ser cero, el rango puede ser 8. Para el parametro uno, el rango puede ser 10. En el caso del parametro dos, el rango puede ser 12 y para el parametro tres, el rango puede ser igual a 16. En la presente realizacion preferida, el parametro de Golomb-Rice puede establecerse a cero en el comienzo del bloque. La adaptacion de parametros de Golomb-Rice se realiza tal como se describe mediante la ecuacion (QQ). Observese que el parametro no se puede disminuir mediante el uso de esta forma de adaptacion. Y observese tambien que es posible una conmutacion directa, por ejemplo de cero a tres. En la presente realizacion preferida, la parte de prefijo de los codigos de Golomb-Rice se codifica con codigos por entropfa empleando modelos de probabilidad. El modelado de contexto se puede realizar como para coeff_abs_level_minus_two en la norma H.264 / AVC.

En otra realizacion preferida, un parametro de Golomb-Rice fijo se puede usar para codificar todos los niveles de coeficiente de transformada en el bloque de transformada actual. En la presente realizacion, el mejor parametro del bloque previo se puede calcular y usar para el bloque de transformada actual. Para la presente realizacion, el rango se puede fijar a 14.

En otra realizacion preferida, un parametro de Golomb-Rice fijo se puede usar para codificar todos los niveles de coeficiente de transformada en el bloque de transformada actual. En la presente realizacion, el mejor parametro del bloque previo se puede calcular y usar para el bloque de transformada actual. Para la presente realizacion, el rango puede ser variable tal como se ha descrito anteriormente.

En otra realizacion preferida, se evalua si las proximidades ya codificadas (o descodificadas) del mdice de exploracion actual contienen unos niveles de coeficiente de transformada absolutos mas grandes que el lfmite previo. Para la presente realizacion preferida, el mejor parametro se puede obtener mediante el uso de vecinos en una plantilla causal local.

Por lo tanto, las realizaciones que se han mencionado en lo que antecede describieron entre otras cosas, un aparato de codificacion por entropfa que comprende una unidad de descomposicion 136 que esta configurada para convertir una secuencia 138 de elementos de sintaxis en una secuencia 106 de sfmbolos de origen 106 mediante la descomposicion de forma individual de por lo menos un subgrupo de los elementos de sintaxis en un numero respectivo n de sfmbolos de origen si con i = 1 ... n, el numero respectivo n de sfmbolos de origen dependiendo de en cual de una secuencia de n particiones 1401-3 en las cuales esta subdividido un intervalo de valores de los elementos de sintaxis respectivos, cae un valor z de los elementos de sintaxis respectivos, de tal modo que una suma de valores del numero respectivo de sfmbolos de origen Si da z, y, si n > 1, para todo i = 1 ... n-1, el valor de si se corresponde con un intervalo de la i-esima particion; un subdivisor 100 que esta configurado para subdividir la secuencia 106 de sfmbolos de origen en una primera subsecuencia 108 de sfmbolos de origen y una segunda subsecuencia 110 de sfmbolos de origen de tal modo que todos los sfmbolos de origen sx con x siendo miembro de un primer subconjunto de {1 ... n} estan contenidos dentro de la primera subsecuencia 108 y todos los sfmbolos de origen sy con y siendo miembro de un segundo subconjunto de {1 ... n} que es disjunto con respecto al primer subconjunto, estan contenidos dentro de la segunda subsecuencia 110; un codificador de VLC 102 que esta configurado para codificar por sfmbolos los sfmbolos de origen de la primera subsecuencia 108; y un codificador de

5

10

15

20

25

30

35

40

45

50

55

60

PIPE o aritmetico 104 que esta codificado para codificar la segunda subsecuencia 110 de s^bolos de origen.

Los valores z del subgrupo de los elementos de sintaxis pueden ser valores absolutos. El segundo subconjunto puede ser {1} con la secuencia de n particiones estando dispuesta de tal modo que una p-esima particion cubre valores mas altos del intervalo de valores que una q-esima particion para todo p, q e {1 .. n} con p > q. n puede ser 3. El primer subconjunto puede ser {2, 3} con el un codificador de VLC (102) configurado para usar un codigo de Golomb-Rice para codificar por sfmbolos los sfmbolos de origen s2, y un codigo de Golomb Exponencial para codificar por sfmbolos los sfmbolos de origen s3. Mas en general, 2 puede ser un elemento del primer subconjunto con el un codificador de VLC (102) estando configurado para usar un codigo de Golomb-Rice para codificar por sfmbolos los sfmbolos de origen s2 y adaptar un parametro de Golomb-Rice, es decir k, del codigo de Golomb-Rice de acuerdo con unos sfmbolos de origen previamente codificados. La unidad de descomposicion se puede configurar para adaptar uno o mas de los lfmites entre las particiones de acuerdo con unos sfmbolos de origen previamente codificados. Ambas adaptaciones se pueden combinar. Es decir, unas posiciones de los lfmites que limitan la segunda particion se pueden adaptar de tal modo que estas estan separadas entre sf de tal modo que la longitud del codigo de Golomb-Rice, es decir el numero de palabras de codigo del mismo, se corresponde con (o dicta) la longitud de la anchura de la segunda particion. El lfmite entre la separacion de la primera y la segunda particion se puede adaptar de acuerdo con otra dependencia del contexto, caso en el cual, la adaptacion de k puede definir la posicion del lfmite que separa la segunda y la tercera particion por medio de la longitud del codigo de Golomb-Rice y la anchura de la segunda particion, de forma respectiva. Mediante el acoplamiento de la adaptacion de k de tal modo que la anchura de la segunda particion se corresponde con la longitud del codigo de Golomb-Rice, la eficiencia de codigo se usa de forma optima. Adaptar k a las estadfsticas del elemento de sintaxis posibilita adaptar la anchura de la segunda particion de tal modo que la tercera particion puede cubrir tanto como sea posible con el fin de reducir la complejidad de codificacion global debido a que se puede haber usado un codigo menos complejo para la tercera particion tal como el codigo de Golomb Exponencial. Ademas, la longitud de la primera particion se puede restringir a j e {1, 2, 3} valores de elemento de sintaxis posibles, tal como los tres niveles mas bajos. Los elementos de sintaxis que se estan considerando se pueden codificar de forma diferencial o representan un residuo de prediccion, este es el caso con los niveles de coeficiente de transformada ejemplificados en lo que antecede los cuales representan un residuo de prediccion. Los primeros sfmbolos de origen s1 se pueden simbolizar / desimbolizar mediante el uso de un codigo unario truncado con los j contenedores resultantes codificandose - parcialmente o la totalidad de estos - de forma adaptativa con el contexto o no tal como se ha mencionado en lo que antecede.

El subgrupo de los elementos de sintaxis puede abarcar unos niveles de coeficiente de transformada absolutos de coeficientes de transformada absolutos de los bloques de transformada de una imagen con los niveles de coeficiente de transformada absolutos de un bloque de transformada respectivo estando dispuestos dentro de la secuencia (138) de elementos de sintaxis de acuerdo con una trayectoria de exploracion que conduce a traves de los coeficientes de transformada absolutos de los bloques de transformada respectivos, en donde la unidad de descomposicion se puede configurar para adaptar uno o mas de los lfmites entre las particiones durante la descomposicion de los niveles de coeficiente de transformada absolutos de los coeficientes de transformada absolutos de un bloque de transformada respectivo dependiendo de unos niveles de coeficiente de transformada absolutos ya codificados de coeficientes de transformada absolutos de los bloques de transformada respectivos precedentes en el orden de exploracion o dependiendo de una posicion del nivel de coeficiente de transformada absoluto que se va a descomponer en la actualidad en el orden de exploracion, o sobre la base de una evaluacion de los niveles de coeficiente de transformada absolutos ya reconstruidos de coeficientes de transformada en las proximidades - o bien espacialmente o bien en el orden de exploracion - de la posicion del nivel de coeficiente de transformada absoluto que se va a descomponer en la actualidad.

Ademas, las realizaciones que se han mencionado en lo que antecede describen entre otras cosas un aparato de descodificacion por entropfa que comprende un descodificador de VLC 200 que esta configurado para reconstruir por palabras de codigo unos sfmbolos de origen de una primera subsecuencia 204 de sfmbolos de origen a partir de palabras de codigo de un primer tren de bits 206; un descodificador de PIPE o aritmetico 202 que esta configurado para reconstruir una segunda subsecuencia 208 de sfmbolos de origen; una unidad de composicion 224 que esta configurada para componer una secuencia 226 de elementos de sintaxis a partir de la primera subsecuencia 204 de sfmbolos de origen y la segunda subsecuencia 208 de sfmbolos de origen mediante la composicion de forma individual de cada elemento de sintaxis a partir de un numero respectivo de sfmbolos de origen, en donde la unidad de composicion esta configurada para determinar, para por lo menos un subgrupo de los elementos de sintaxis, el numero respectivo n de sfmbolos de origen si con i = 1 ... n dependiendo de en cual de una secuencia de n particiones 1401-3 en las cuales esta subdividido un intervalo de valores de los elementos de sintaxis respectivos, cae un valor z de los elementos de sintaxis respectivos, mediante la adicion de los valores del numero respectivo de sfmbolos de origen si de 1 a n siempre que el valor de si se corresponda con un intervalo de la i-esima particion con el fin de obtener el valor del elemento de sintaxis z, en donde la unidad de composicion 224 esta configurada para recuperar todos los sfmbolos de origen sx con x siendo miembro de un primer subconjunto de {1 ... n} a partir de la primera subsecuencia (204) y todos los sfmbolos de origen sy con y siendo miembro de un segundo subconjunto de {1 ... n} que es disjunto con respecto al primer subconjunto, a partir de la segunda subsecuencia 208. Los valores z

5

10

15

20

25

30

35

40

45

50

55

60

del subgrupo de los elementos de sintaxis pueden ser valores absolutos. El segundo subconjunto puede ser {1} con la secuencia de n particiones estando dispuesta de tal modo que una p-esima particion cubre valores mas altos del intervalo de valores que una q-esima particion para todo p, q e {1 .. n} con p > q. n puede ser 3. El primer subconjunto puede ser {2, 3} con el un descodificador de VLC 200 estando configurado para usar un codigo de Golomb-Rice para reconstruir por palabras de codigo los sfmbolos de origen s2, y un codigo de Golomb Exponencial para reconstruir por palabras de codigo los sfmbolos de origen s3. Mas en general, 2 puede ser un elemento del primer subconjunto con el un descodificador de VLC 102 estando configurado para usar un codigo de Golomb-Rice para reconstruir por palabras de codigo los sfmbolos de origen s2 y adaptar un parametro de Golomb-Rice del codigo de Golomb-Rice de acuerdo con unos sfmbolos de origen previamente reconstruidos. El aparato de descodificacion por entropfa puede comprender adicionalmente un recombinador 220 que esta configurado para recombinar la primera subsecuencia 204 de sfmbolos de origen y la segunda subsecuencia de sfmbolos de origen para obtener la secuencia 218 de sfmbolos de origen. Los elementos de sintaxis pueden ser de diferente tipo y la unidad de composicion se puede configurar para realizar la composicion individual dependiendo del tipo de los elementos de sintaxis. El subgrupo de los elementos de sintaxis puede abarcar unos niveles de coeficiente de transformada absolutos de coeficientes de transformada absolutos de los bloques de transformada de una imagen con los niveles de coeficiente de transformada absolutos de un bloque de transformada respectivo estando dispuestos dentro de la secuencia 138 de elementos de sintaxis de acuerdo con una trayectoria de exploracion que conduce a traves de los coeficientes de transformada absolutos de los bloques de transformada respectivos, en donde la unidad de composicion se puede configurar para adaptar uno o mas de los lfmites entre las particiones durante la composicion de los niveles de coeficiente de transformada absolutos de los coeficientes de transformada absolutos de un bloque de transformada respectivo dependiendo de unos niveles de coeficiente de transformada absolutos ya reconstruidos de coeficientes de transformada absolutos de los bloques de transformada respectivos precedentes en el orden de exploracion o dependiendo de una posicion del nivel de coeficiente de transformada absoluto que se va a componer en la actualidad en el orden de exploracion, o sobre la base de una evaluacion de los niveles de coeficiente de transformada absolutos ya reconstruidos de coeficientes de transformada en las proximidades - o bien espacialmente o bien en el orden de exploracion - de la posicion del nivel de coeficiente de transformada absoluto que se va a componer en la actualidad.

En lo que respecta a la combinacion de la codificacion de PIPE con la codificacion de VLC usando la descomposicion de acuerdo con la figura 1b, lo sucesivo se hace notar con el fin de repetir algunos aspectos de la misma con otras palabras.

Se ha descrito la puesta en correspondencia de una secuencia de sfmbolos con un tren de bits y la puesta en correspondencia inversa. Cada sfmbolo porta un parametro o parametros asociados con este que se conocen de forma simultanea en el codificador y en el descodificador. El codec por entropfa contiene multiples memorias intermedias de tipo primero en entrar primero en salir (FIFO, first-in first-out) con cada una de ellas asignada a subconjuntos de un parametro o parametros que estan asociados con los sfmbolos. Para un parametro o parametros dados de un sfmbolo, el codificador asigna el sfmbolo a la memoria intermedia de tipo FIFO correspondiente. Debido a que la regla de asignacion de codificadores se conoce en el lado de descodificador, el descodificador lee a partir de la memoria intermedia de tipo FIFO a cual el codificador ha asignado el sfmbolo.

Algunos elementos de sintaxis se codifican usando codigos de longitud variable convencionales y se escriben en una memoria intermedia particular. Otros elementos de sintaxis se codifican usando el concepto de codificacion de entropfa de subdivision en particiones de intervalos de probabilidad (PIPE, probability interval partitioning entropy). En este, los sfmbolos se binarizan en primer lugar y los contenedores resultantes se clasifican sobre la base de estimadas de probabilidad asociadas. La estimada de probabilidad se puede dar u obtener a partir de una medicion que se puede llevar a cabo de forma simultanea en el codificador y en el descodificador. Una memoria intermedia de tipo FIFO particular contiene sfmbolos con unos valores de probabilidad estimada que caen dentro de un subconjunto de probabilidades que se elige de tal modo que se puede mejorar la codificacion por entropfa. La mejora lograda por una combinacion del concepto de PIPE con VLC es una reduccion en la complejidad al tiempo que se sigue proporcionando una eficiencia de codificacion alta. Unos sfmbolos para los cuales un codigo de vLc convencional es adecuado se codifican con el enfoque de VLC simple y de baja complejidad, mientras que otros sfmbolos para los cuales la tasa de bits se incremental de forma significativa mediante la codificacion de estos con un codigo de VLC se codifican con el mas sofisticado concepto de PIPE.

Por lo tanto, con el fin de reducir adicionalmente la complejidad de la codificacion por entropfa, los sfmbolos se han dividido en dos categonas. Los sfmbolos de una primera categona se pueden representar bien con codigos de VLC y no requieren la mas compleja codificacion de PIPE, mientras que los sfmbolos de una segunda categona no se pueden representar de forma eficiente con codigos de VLC y una codificacion de PIPE para estos los sfmbolos redujo de forma significativa la tasa de bits requerida.

A pesar de que algunos aspectos se han descrito en el contexto de un aparato, es evidente que estos aspectos tambien representan una descripcion del metodo correspondiente, en donde un bloque o dispositivo se corresponde con una etapa de metodo o una caractenstica de una etapa de metodo. De forma analoga, los aspectos que se

5

10

15

20

25

30

35

40

45

50

55

60

describen en el contexto de una etapa de metodo tambien representan una descripcion de un bloque o arffculo o caractenstica correspondiente de un aparato correspondiente. Algunas o la totalidad de las etapas de metodo pueden ser ejecutadas por (o usando) un aparato de soporte ffsico, como por ejemplo, un procesador, un ordenador programable o un circuito electronico. En algunas realizaciones, algunas una o mas de las etapas de metodo mas importantes pueden ser ejecutadas por un aparato de este tipo.

Las senales codificadas / comprimidas de la invencion se pueden almacenar en un medio de almacenamiento digital o se pueden transmitir por un medio de transmision tal como un medio de transmision inalambrica o un medio de transmision por cable tal como Internet.

Dependiendo de determinados requisitos de implementacion, se pueden implementar realizaciones de la invencion en soporte ffsico o en soporte logico. La implementacion se puede realizar usando un medio de almacenamiento digital, por ejemplo un disco flexible, un DVD, un Blue-Ray, un CD, una ROM, una PROM, una EPROM, una EEPROM o una memoria FLASH, que tiene unas senales de control legibles por medios electronicos almacenadas en el mismo, las cuales cooperan (o son capaces de cooperar) con un sistema informatico programable de tal modo que se realiza el metodo respectivo. Por lo tanto, el medio de almacenamiento digital puede ser legible por ordenador.

Algunas realizaciones de acuerdo con la invencion comprenden un medio de soporte de datos que tiene unas senales de control legibles por medios electronicos, las cuales son capaces de cooperar con un sistema informatico programable, de tal modo que se realiza uno de los metodos que se describen en el presente documento.

En general, se pueden implementar realizaciones de la presente invencion como un producto de programa informatico con un codigo de programa, siendo el codigo de programa operativo para realizar uno de los metodos cuando el producto de programa informatico se ejecuta en un ordenador. El codigo de programa se puede almacenar por ejemplo en un medio de soporte legible por maquina.

Otras realizaciones comprenden el programa informatico para realizar uno de los metodos que se describen en el presente documento, almacenado en un medio de soporte legible por maquina.

Dicho de otra forma, una realizacion del metodo de la invencion es, por lo tanto, un programa informatico que tiene un codigo de programa para realizar uno de los metodos que se describen en el presente documento, cuando el programa informatico se ejecuta en un ordenador.

Una realizacion adicional de los metodos de la invencion es, por lo tanto, un medio de soporte de datos (o un medio de almacenamiento digital, o un medio legible por ordenador) que comprende, registrado en el mismo, el programa informatico para realizar uno de los metodos que se describen en el presente documento.

Una realizacion adicional del metodo de la invencion es, por lo tanto, un tren de datos o una secuencia de senales que representan el programa informatico para realizar uno de los metodos que se describen en el presente documento. El tren de datos o la secuencia de senales se puede configurar por ejemplo para transferirse por medio de una conexion de comunicacion de datos, por ejemplo por medio de Internet.

Una realizacion adicional comprende unos medios de procesamiento, por ejemplo un ordenador, o un dispositivo logico programable, configurado para o adaptado para realizar uno de los metodos que se describen en el presente documento.

Una realizacion adicional comprende un ordenador que tiene instalado en el mismo el programa informatico para realizar uno de los metodos que se describen en el presente documento.

En algunas realizaciones, un dispositivo logico programable (por ejemplo una matriz de puertas programable en campo) se puede usar para realizar algunas o la totalidad de las funcionalidades de los metodos que se describen en el presente documento. En algunas realizaciones, una matriz de puertas programable en campo puede cooperar con un procesador con el fin de realizar uno de los metodos que se describen en el presente documento. En general, preferiblemente los metodos son realizados por cualquier aparato de soporte ffsico.

Las realizaciones que se han descrito en lo que antecede son meramente ilustrativas de los principios de la presente invencion. Se entiende que modificaciones y variaciones de las disposiciones y los detalles que se describen en el presente documento seran evidentes a otros expertos en la materia. La intencion es, por lo tanto, estar limitado solo por el alcance de las inminentes reivindicaciones de patente y no por los detalles espedficos que se presentan a modo de descripcion y explicacion de las realizaciones en el presente documento.

Claims

5

10

15

20

25

30

35

40

45

50

55

60

REIVINDICACIONES

1. Aparato de codificacion por entrc^a que comprende

una unidad de descomposicion (136) que esta configurada para convertir una secuencia (138) de elementos de sintaxis que tienen un intervalo de valores el cual esta subdividido en una secuencia de N particiones (1401-3) en una secuencia (106) de sfmbolos de origen (106) mediante la descomposicion de forma individual de por lo menos un subgrupo de los elementos de sintaxis en un numero respectivo n de sfmbolos de origen si con i = 1 ... n, el numero respectivo n de sfmbolos de origen dependiendo de en cual de la secuencia de N particiones (14O1-3) cae un valor z de los elementos de sintaxis respectivos, de tal modo que una suma de valores del numero respectivo de sfmbolos de origen si da z, y, si n > 1, para todo i = 1 ... n-1, el valor de si se corresponde con un intervalo de la i-esima particion;

un subdivisor (100) que esta configurado para subdividir la secuencia (106) de sfmbolos de origen en una primera subsecuencia (108) de sfmbolos de origen y una segunda subsecuencia (110) de sfmbolos de origen de tal modo que todos los sfmbolos de origen sx con x siendo miembro de un primer subconjunto de {1 ... N} estan contenidos dentro de la primera subsecuencia (108) y todos los sfmbolos de origen sy con y siendo miembro de un segundo subconjunto de {1 ... N} que es disjunto con respecto al primer subconjunto, estan contenidos dentro de la segunda subsecuencia (110);

un codificador de VLC (102) que esta configurado para codificar por sfmbolos los sfmbolos de origen de la primera subsecuencia (108); y

un codificador aritmetico (104) que esta codificado para codificar la segunda subsecuencia (110) de sfmbolos de origen, caracterizado por que

los valores z del subgrupo de los elementos de sintaxis son valores absolutos, y

en el que la unidad de descomposicion esta configurada para adaptar uno o mas de los lfmites entre las particiones de acuerdo con unos sfmbolos de origen previamente codificados.
2. Aparato de descodificacion por entropfa que comprende

un descodificador de VLC (200) que esta configurado para reconstruir por palabras de codigo los sfmbolos de origen de una primera subsecuencia (204) de sfmbolos de origen a partir de palabras de codigo de un primer tren de bits (206);

un descodificador aritmetico (202) que esta configurado para reconstruir una segunda subsecuencia (208) de sfmbolos de origen;

una unidad de composicion (224) que esta configurada para componer una secuencia (226) de elementos de sintaxis que tienen un intervalo de valores el cual esta subdividido en una secuencia de N particiones (1401-3) a partir de la primera subsecuencia (204) de sfmbolos de origen y la segunda subsecuencia (208) de sfmbolos de origen mediante la composicion de forma individual de cada elemento de sintaxis a partir de un numero respectivo n de sfmbolos de origen mediante, para por lo menos un subgrupo de los elementos de sintaxis, la determinacion del numero respectivo n de sfmbolos de origen si con i = 1 ... n dependiendo de en cual de la secuencia de N particiones (1401-3) en las cuales esta subdividido un intervalo de valores de los elementos de sintaxis respectivos, cae un valor z de los elementos de sintaxis respectivos, mediante la adicion de los valores del numero respectivo de sfmbolos de origen si de 1 a n siempre que el valor de si se corresponda con un intervalo de la i-esima particion con el fin de obtener el valor del elemento de sintaxis z, en el que la unidad de composicion (224) esta configurada para recuperar todos los sfmbolos de origen sx con x siendo miembro de un primer subconjunto de {1 ... N} a partir de la primera subsecuencia (204) y todos los sfmbolos de origen sy con y siendo miembro de un segundo subconjunto de {1 ... N} que es disjunto con respecto al primer subconjunto, a partir de la segunda subsecuencia (208), caracterizado por que

los valores z del subgrupo de los elementos de sintaxis son valores absolutos, y

en el que la unidad de composicion esta configurada para adaptar uno o mas de los lfmites entre las particiones de acuerdo con unos sfmbolos de origen previamente reconstruidos.
3. Aparato de descodificacion por entropfa de acuerdo con la reivindicacion 2, en el que el segundo subconjunto es {1} con la secuencia de N particiones estando dispuesta de tal modo que una p-esima particion cubre valores mas altos del intervalo de valores que una q-esima particion para todo p, q e {1 .. N} con p > q.
4. Aparato de descodificacion por entropfa de acuerdo con la reivindicacion 3, en el que N = 3.
5. Aparato de descodificacion por entropfa de acuerdo con la reivindicacion 2, en el que 2 es un elemento del primer subconjunto con el descodificador de VLC (102) estando configurado para usar un codigo de Golomb-Rice para reconstruir por palabras de codigo los sfmbolos de origen s2 y adaptar un parametro de Golomb-Rice del codigo de Golomb-Rice de acuerdo con unos sfmbolos de origen previamente reconstruidos.
6. Aparato de descodificacion por entropfa de acuerdo con cualquiera de las reivindicaciones 2 a 4 que comprende adicionalmente un recombinador (220) que esta configurado para recombinar la primera subsecuencia (204) de sfmbolos de origen y la segunda subsecuencia de sfmbolos de origen para obtener la secuencia (218) de sfmbolos de origen.

5

10

15

20

25

30

35

40
7. Metodo de codificacion por entropfa que comprende

convertir una secuencia (138) de elementos de sintaxis que tienen un intervalo de valores el cual esta subdividido en una secuencia de N particiones (1401-3) en una secuencia (106) de sfmbolos de origen (106) mediante la descomposicion de forma individual de por lo menos un subgrupo de los elementos de sintaxis en un numero respectivo n de sfmbolos de origen si con i = 1 ... n, el numero respectivo n de sfmbolos de origen dependiendo de en cual de la secuencia de N particiones (14O1-3) cae un valor z de los elementos de sintaxis respectivos, de tal modo que una suma de valores del numero respectivo de sfmbolos de origen si da z, y, si n > 1, para todo i = 1 ... n- 1, el valor de si se corresponde con un intervalo de la i-esima particion;

subdividir la secuencia (106) de sfmbolos de origen en una primera subsecuencia (108) de sfmbolos de origen y una segunda subsecuencia (110) de sfmbolos de origen de tal modo que todos los sfmbolos de origen sx con x siendo miembro de un primer subconjunto de {1 ... N} estan contenidos dentro de la primera subsecuencia (108) y todos los sfmbolos de origen sy con y siendo miembro de un segundo subconjunto de {1 ... N} que es disjunto con respecto al primer subconjunto, estan contenidos dentro de la segunda subsecuencia (110);

mediante codificacion de VLC, codificar por sfmbolos los sfmbolos de origen de la primera subsecuencia (108); y mediante codificacion aritmetica, codificar la segunda subsecuencia (110) de sfmbolos de origen, caracterizado por que los valores z del subgrupo de los elementos de sintaxis son valores absolutos, en el que la conversion mediante una descomposicion individual comprende adaptar uno o mas de los lfmites entre las particiones de acuerdo con unos sfmbolos de origen previamente codificados.
8. Metodo de descodificacion por entropfa que comprende

mediante descodificacion de VLC, reconstruir por palabras de codigo los sfmbolos de origen de una primera subsecuencia (204) de sfmbolos de origen a partir de palabras de codigo de un primer tren de bits (206); mediante descodificacion aritmetica, reconstruir una segunda subsecuencia (208) de sfmbolos de origen; componer una secuencia (226) de elementos de sintaxis que tienen un intervalo de valores el cual esta subdividido en una secuencia de N particiones (1401-3) a partir de la primera subsecuencia (204) de sfmbolos de origen y la segunda subsecuencia (208) de sfmbolos de origen mediante la composicion de forma individual de cada elemento de sintaxis a partir de un numero respectivo n de sfmbolos de origen mediante, para por lo menos un subgrupo de los elementos de sintaxis, la determinacion del numero respectivo n de sfmbolos de origen si con i = 1 ... n dependiendo de en cual de la secuencia de N particiones (1401-3) en las cuales esta subdividido un intervalo de valores de los elementos de sintaxis respectivos, cae un valor z de los elementos de sintaxis respectivos, mediante la adicion de los valores del numero respectivo de sfmbolos de origen si de 1 a n siempre que el valor de si se corresponda con un intervalo de la i-esima particion con el fin de obtener el valor del elemento de sintaxis z, en el que la composicion (224) comprende recuperar todos los sfmbolos de origen sx con x siendo miembro de un primer subconjunto de {1 ... N} a partir de la primera subsecuencia (204) y todos los sfmbolos de origen sy con y siendo miembro de un segundo subconjunto de {1 ... N} que es disjunto con respecto al primer subconjunto, a partir de la segunda subsecuencia (208), caracterizado por que

los valores z del subgrupo de los elementos de sintaxis son valores absolutos, en el que la composicion comprende adaptar uno o mas de los lfmites entre las particiones de acuerdo con unos sfmbolos de origen previamente reconstruidos.
9. Un programa informatico que tiene un codigo de programa para realizar, cuando se ejecuta en un ordenador, un metodo de acuerdo con la reivindicacion 7 u 8.