MÉTODO DE CODIFICACIÓN ARITMÉTICA DISTRIBUIDA.

La presente invención se refiere a un método de codificación distribuida de fuentes. Más específicamente, la invención se refiere a un método para realizar la codificación y la decodificación de datos de comunicación que provienen de fuentes estadísticamente dependientes. El documento US 2002/176494 da a conocer un método de codificación y decodificación del tipo de la presente invención. En los últimos años, los académicos que se enfrentan al procesado de análisis y de señales han prestado una atención creciente a la codificación distribuida de fuentes. La codificación distribuida de fuentes considera la situación en la que dos o más fuentes de datos estadísticamente dependientes se deben codificar mediante dos codificadores independientes a los que no se permite comunicarse entre sí, es decir, cuando las dos fuentes no están disponibles de manera conjunta (es decir, no están dentro del mismo dispositivo) y, por lo tanto, la comunicación entre ellas resultaría imposible o muy cara, como en el caso de una red de sensores inalámbricos. En este caso, cada codificador tiene disponibles solamente los datos provenientes de una de las dos fuentes. Resulta también atractiva la posibilidad de aplicar principios de la codificación distribuida de fuentes a situaciones en las que una única fuente está subdividida artificialmente en sub-fuentes correlacionadas que se codifican por separado, por ejemplo, tramas diferentes de una secuencia de vídeo. En este caso, la ventaja es que ya no se requiere la decorrelación entre las sub-fuentes, simplificando de este modo el codificador (aunque a costa del decodificador). Los dos codificadores pueden realizar una compresión sin pérdidas de las dos fuentes, cada uno de ellos, usando una velocidad de bits mayor que la entropía de cualquiera de las fuentes; no obstante, este tipo de compresión independiente constituye una pérdida de eficacia con respecto al uso de un codificador que comprime conjuntamente las dos fuentes, puesto que, en este caso, se podría usar una velocidad de bits igual a la entropía conjunta de las fuentes, que es menor que la entropía de cada fuente. La teoría de la codificación distribuida de fuentes ha demostrado que, bajo ciertas suposiciones, se puede lograr el mismo resultado que la codificación conjunta usando dos codificadores independientes, siempre que las dos fuentes se decodifiquen por medio de un decodificador conjunto. Es posible llegar a esto realizando una codificación convencional de una de las dos fuentes (denominada información lateral) en su valor de entropía, y una codificación ambigua de la otra fuente a una velocidad menor que su entropía, sin ninguna información sobre la primera fuente disponible en el segundo codificador. Una fuente se codifica de manera ambigua cuando datos de dicha fuente se transmiten en forma de una secuencia de símbolos de manera que en el decodificador no se garantiza un acuse de recibo perfecto y unívoco del símbolo transmitido. Los codificadores que realizan la codificación distribuida de fuentes se implementan típicamente usando códigos de canal, es decir, representando la fuente mediante el uso de su síndrome (o los bits de paridad) para un código de canal dado adecuado para una magnitud de correlación dada entre las dos fuentes. Los códigos de canal se usan debido a que, al disponer de la información lateral, permiten realizar la decodificación de una fuente codificada de manera ambigua, con una probabilidad de error mínima. La teoría de codificación distribuida de fuentes comprende no solamente la compresión sin pérdidas sino también la compresión con pérdidas; se ha observado que, bajo ciertas condiciones, no se produce ninguna pérdida de rendimiento en el uso de la codificación distribuida de fuentes por contraposición a la codificación conjunta. En la práctica, la codificación distribuida de fuentes con pérdidas se implementa típicamente usando un cuantificador convencional seguido por una codificación distribuida de fuentes sin pérdidas (codificación de entropía), mientras que el decodificador consiste en un decodificador de entropía conjunta seguido por un decuantificador conjunto. Las aplicaciones de los esquemas de codificación distribuida de fuentes en señales realistas están limitadas típicamente por algunos problemas. En particular, por ejemplo, los códigos de canal requieren bloques de datos muy grandes (típicamente por encima de 10.000 símbolos). Este requisito no es siempre compatible con las aplicaciones prácticas, donde las unidades básicas a codificar son del orden de entre unos cientos y unos miles de símbolos. Además, los códigos de canal requieren que los símbolos contenidos en cada bloque sigan siempre una distribución estadística estacionaria, hipótesis que no resulta adecuada para datos como imágenes y secuencias de vídeo, por ejemplo. Por otra parte, la entropía condicional de una distribución estacionaria restringe la velocidad de bits. Los códigos de canal tienen una alta complejidad de codificación, típicamente del orden del cuadrado de la dimensión del bloque de datos, y, por lo tanto, esta complejidad aumenta muy rápidamente cuando se incrementa la dimensión del bloque; por otro lado, una dimensión de bloque grande es un prerrequisito para el uso de estos códigos de canal, de lo cual se deriva la alta complejidad del proceso de codificación. 2 ES 2 367 747 T3 Un objetivo de la presente invención es proponer un método de codificación y decodificación de fuentes que pueda superar los problemas mencionados anteriormente. Este y otros objetivos se logran, según la invención, con un método de codificación y decodificación cuyas características principales se definen en las reivindicaciones 1 y 7. Otras características y ventajas de la invención resultarán evidentes a partir de la siguiente descripción detallada, proprociona únicamente a título de ejemplo no limitativo, haciendo referencia a los dibujos adjuntos, en los que: - la figura 1 es un esquema ilustrativo de un método de codificación aritmética binaria según la técnica anterior; - la figura 2 es un esquema relacionado con un método de codificación distribuida aritmética binaria según la invención; - la figura 3 es un esquema de una rama de un árbol de decodificación aritmética distribuida; y - la figura 4 es un esquema de ramas de un árbol de decodificación aritmética distribuida que tiene una información lateral codificada de manera ambigua. La figura 1 muestra un esquema de un método de codificación aritmética o codificación AC (Codificación Aritmética) según la técnica anterior. En la codificación aritmética, el punto de partida es un conjunto de símbolos [X0, X1,..., Xi, ..., XN-1] que es una secuencia de símbolos de longitud N en la que cada símbolo pertenece a un alfabeto M-ario. El proceso de codificación aritmética se basa o bien en el conocimiento o bien en la estimación de la probabilidad de cada carácter del alfabeto M-ario en el instante de tiempo i, que se indica como p1,i, p2,i,..., pM,i. El sumario de la probabilidad asociada a los diversos caracteres del alfabeto M-ario, en cada momento, es igual a 1. Para simplificar, el conjunto de probabilidades se indicará como p1, p2,..., pM, aunque se pretende que estas probabilidades puedan variar en cada etapa de codificación, por ejemplo, cuando se use un algoritmo de estimación basado en estadísticas de símbolos. La codificación aritmética se basa en la partición recursiva de intervalos según una probabilidad dada, conocida como codificación de Elías, la cual codifica símbolos a través de intervalos. Los símbolos de la fuente se asocian a sub-intervalos de un intervalo de partida de manera que los mismos constituyen una partición de este último, es decir, no se solapan y su unión es igual al intervalo de partida. En el comienzo, el intervalo actual es igual al intervalo de partida y se fija a [0,1). Para cada símbolo de entrada Xi de la secuencia a codificar, el intervalo actual se particiona en un conjunto de M sub-intervalos adyacentes cuyas longitudes son proporcionales a p1, p2, ..., pM. El sub-intervalo que representa el símbolo Xi se selecciona como el siguiente intervalo actual. Después de que se hayan procesado la totalidad de los N símbolos, la secuencia se representa por el último intervalo actual, indicado como intervalo final. La representación de la secuencia M-aria puede consistir en un número cualquiera dentro de dicho intervalo final. Por ejemplo, es posible seleccionar un punto extremo del intervalo final, el punto medio del sub-intervalo o cualquier otro número perteneciente al intervalo. Para la transmisión o para la escritura en un soporte numérico, dicho número se deberá transformar en una representación del mismo (típicamente binaria), indicada como palabra de código. En... [Seguir leyendo]

1. Método de codificación aritmética distribuida de una primera fuente de datos (X) que tiene una entropía asociada (H), y por lo menos una segunda fuente de datos (Y) correlacionada estadísticamente con la primera (X), en el que cada una de dichas fuentes (X,Y) está asociada a una secuencia respectiva de símbolos (X0, X1, ..., XN-1; Y0, Y1, YN­ 1), en la que cada símbolo pertenece a un alfabeto M-ario, en donde M puede ser diferente para las dos fuentes (X,Y), con un grupo asociado de probabilidades (p1,... pM) cuyos valores se incluyen en el intervalo de 0 a 1; estando caracterizado el método porque se codifica un número de símbolos de dicha primera fuente (X) de manera ambigua con un número predeterminado de elementos por símbolo (X0, X1,..., XN-1), en particular bits por símbolo (X0, X1, ..., XN-1), menor que su entropía (H(x)), y porque se codifica un número correspondiente de símbolos de dicha por lo menos segunda fuente de datos (Y) de manera no ambigua con un número predeterminado de elementos por símbolo (Y0, Y1, ..., YN-1), en particular bits por símbolo (Y0, Y1, ..., YN-1), mayor o igual que su entropía (H(y)). 2. Método de codificación aritmética según la reivindicación 1, en el que dicha primera fuente (X) se codifica de manera ambigua realizando las siguientes etapas: a) subdividir un intervalo de partida de números reales (16) que se supone igual al intervalo de 0 a 1, en M subintervalos (17, 18) en los que M adopta el valor asociado a la primera fuente (X), presentando dichos subintervalos longitudes predeterminadas mayores o iguales que las longitudes correspondientes a valores de las probabilidades (p1,..., pM) del alfabeto M-ario asociado a la primera fuente (X), de manera que por lo menos dos de dichos sub-intervalos (17, 18) se solapan parcialmente; b) seleccionar un primer sub-intervalo (17) de dicho intervalo de partida (16) correspondiente al primer símbolo (X0) de dicha secuencia; c) repetir la etapa a) usando como nuevo intervalo de partida dicho primer sub-intervalo (17); d) seleccionar un segundo sub-intervalo (19) de dicho intervalo de partida nuevo (17) correspondiente al segundo símbolo (X1) de dicha secuencia (X0, X1, ..., XN-1); e) repetir las etapas c) y d) actualizando el intervalo de partida según los siguientes símbolos de la secuencia (X0, X1,..., XN-1) hasta que se agoten todos los símbolos; f) seleccionar cualquier número dentro del último sub-intervalo (22) correspondiente al último símbolo de la secuencia (X0, X1,..., XN-1) como representativo de la secuencia completa (X0, X1, ..., XN-1) así codificada y transformarlo en una representación predeterminada, palabra de código indicada, constituida por una pluralidad de dichos elementos, en particular una pluralidad de bits. 3. Método de codificación según la reivindicación 1, en el que la secuencia (X0, X1, ..., XN-1) asociada a dicha primera fuente (X) se codifica de manera ambigua realizando las siguientes etapas: i) subdividir un intervalo de partida de números reales (16), que se supone igual al intervalo de 0 a 1 en M subintervalos en los que M adopta el valor asociado a la primera fuente (X), presentando dichos sub-intervalos longitudes predeterminadas iguales a las longitudes correspondientes a los valores de probabilidades (p1, ..., pM) del alfabeto M-ario asociado a la primera fuente (X), de manera que dichos sub-intervalos no se solapen; ii) eliminar un número predeterminado de elementos de la palabra de código correspondiente a la secuencia (X0, X1, ..., XN-1). 4. Método de codificación según la reivindicación 2, en el que la secuencia (X0, X1, ..., XN-1) asociada a dicha primera fuente (X) se codifica de manera ambigua, realizando además la etapa siguiente: - eliminar un número predeterminado de elementos de la palabra de código correspondiente a la secuencia (X0, X1, ..., XN-1). 5. Método de codificación según la reivindicación 1, en el que un número de símbolos de dicha primera fuente (X) se codifica de manera ambigua realizando las siguientes etapas: a) subdividir un intervalo de partida de números reales (16) que se supone igual al intervalo de 0 a 1, en M subintervalos (17, 18) en los que M adopta el valor asociado a la primera fuente (X), presentando dichos subintervalos longitudes predeterminadas mayores o iguales que las longitudes correspondientes a valores de las probabilidades (p1, ..., pM) del alfabeto M-ario asociado a la primera fuente (X), de manera que por lo menos dos de dichos sub-intervalos (17, 18) se solapan parcialmente; b) seleccionar un primer sub-intervalo (17) de dicho intervalo de partida (16) correspondiente a un primer símbolo (X0) de dicha secuencia (X0, X1, ..., XN-1); c) repetir la etapa a) usando como nuevo intervalo de partida dicho primer sub-intervalo (17); d) seleccionar un segundo sub-intervalo (19) de dicho intervalo de partida nuevo (17) correspondiente a un segundo símbolo (X1) de dicha secuencia (X0, X1, ..., XN-1); e) repetir las etapas c) y d) actualizando el intervalo de partida según un subconjunto de los siguientes símbolos de la secuencia (X0, X1, ..., XN-1) hasta que se agoten todos los símbolos de dicho subconjunto; f) seleccionar cualquier número dentro del último sub-intervalo (22) correspondiente al último símbolo de la secuencia (X0, X1, ..., XN-1) como representativo de la secuencia completa (X0, X1, ..., XN-1) así codificada y 11 ES 2 367 747 T3 transformarlo en una representación predeterminada, palabra de código indicada, constituida por una pluralidad de dichos elementos, en particular una pluralidad de bits; y en el que el número correspondiente de símbolos de la segunda fuente de datos (Y) se codifica de manera no ambigua realizando las siguientes etapas: a) subdividir un intervalo de partida de números reales (16) que se supone igual al intervalo de 0 a 1, en M subintervalos, en los que M adoptó el valor asociado a la segunda fuente (Y), presentando dichos sub-intervalos longitudes predeterminadas iguales que las longitudes correspondientes a los valores de las probabilidades (p1, pM) del alfabeto M-ario asociado a la segunda fuente (Y), de manera que dichos sub-intervalos no se solapan; b) seleccionar un primer sub-intervalo (17) de dicho intervalo de partida (16) correspondiente a un primer símbolo (Y0) de dicha segunda fuente (Y), correspondiéndose dicho primer símbolo (Y0) de dicha segunda fuente (Y) con el primer símbolo (X0) de la primera fuente (X); c) repetir la etapa a) usando como nuevo intervalo de partida dicho primer sub-intervalo (17); d) seleccionar un segundo sub-intervalo (19) de dicho nuevo intervalo de partida (17) correspondiente a un segundo símbolo (Y1) de dicha segunda fuente (Y), correspondiéndose dicho segundo símbolo (Y1) de dicha segunda fuente (Y) con el segundo símbolo (X1) de la primera fuente (X); e) repetir las etapas c) y d) actualizando el intervalo de partida según un subconjunto de los siguientes símbolos de la secuencia (Y0, Y1, ..., YN-1) hasta que se agoten todos los símbolos de dicho subconjunto, correspondiéndose dichos símbolos de subconjunto con los símbolos del subconjunto de la primera fuente (X); f) seleccionar cualquier número dentro del último sub-intervalo (22) correspondiente al último símbolo de la secuencia (Y0, Y1, ..., YN-1) como representativo de la secuencia completa (Y0, Y1, ..., YN-1) así codificada y transformarlo en una representación predeterminada, palabra de código indicada, constituida por una pluralidad de dichos elementos, en particular una pluralidad de bits. 6. Método de codificación según la reivindicación 3, en el que la segunda fuente de datos (Y) se codifica de manera ambigua y en el que la etapa ii) se realiza sobre un grupo predeterminado de elementos de la palabra de código correspondiente a la primera fuente (X), y la etapa ii) se realiza sobre otro grupo predeterminado de elementos de la palabra de código correspondiente a por lo menos la segunda fuente de datos (Y). 7. Método de decodificación aritmética distribuida que comprende las etapas siguientes: a) adquirir por lo menos una primera palabra de código (CX) y una segunda palabra de código (CY) asociadas respectivamente a una primera fuente de datos (X) y a por lo menos una segunda fuente de datos (Y) correlacionada estadísticamente con la primera (X), en las que cada una de dichas palabras de código (CX, CY) describe una secuencia respectiva de símbolos fuente (X0, X1, ..., XN-1; Y0, Y1, ..., YN-1), en la que cada símbolo pertenece a un alfabeto M-ario, en donde M puede ser diferente para las dos fuentes (X, Y), con un grupo asociado de probabilidades (p1, ..., pM); estando vinculadas dichas por lo menos dos palabras de código (Cx, Cy) con dicha secuencia de símbolos (X0, X1, ..., XN-1; Y0, Y1, ..., YN-1) por una relación de correlación predeterminada; codificándose de manera ambigua los símbolos (X0, X1, ..., XN-1) de la primera palabra de código (CX) y codificándose de manera no ambigua los símbolos correspondientes (Y0, Y1,..., YN-1) de la segunda palabra de código (CY); b) subdividir por lo menos un intervalo de partida de números reales asociado a una de la primera y la segunda fuentes (X o Y), representando el intervalo de partida el intervalo desde 0 a 1, en M sub-intervalos, en los que M se corresponde con el alfabeto asociado a dicha fuente (X o Y), presentando dichos sub-intervalos longitudes predeterminadas mayores o iguales que las longitudes correspondientes a los valores de las probabilidades (p1, ..., pM) del alfabeto M-ario asociado a dicha fuente (X o Y), de manera que por lo menos dos de dichos sub-intervalos se solapan parcialmente; c) inicializar por lo menos un árbol de decodificación constituido por un grupo de nodos que se corresponden cada uno de ellos con un símbolo de por lo menos una de las por lo menos dos palabras de código (Cx, CY); d) comparar por lo menos una de las por lo menos dos palabras de código (CX, CY) con los sub-intervalos; e1)si dichas por lo menos palabras de código (CX, CY) pertenecen a la porción no solapada de un sub-intervalo, decodificar el símbolo correspondiente y seleccionar el sub-intervalo correspondiente como un intervalo de partida nuevo; e2)si dichas por lo menos palabras de código (CX, CY) pertenecen a la porción solapada de por lo menos dos subintervalos, memorizar KM trayectos alternativos correspondientes a los K símbolos que se pueden decodificar, actualizar su relación de correlación y seleccionar el sub-intervalo correspondiente como intervalo de partida nuevo; f) repetir las operaciones d) y e1) ó e2) para todos los nodos del árbol; g) dar salida a la secuencia correspondiente al trayecto más probable en el por lo menos un árbol de decodificación. 12 ES 2 367 747 T3 13 ES 2 367 747 T3 14 ES 2 367 747 T3