La codificación de fuente distribuida ( DSC ) es un problema importante en la teoría de la información y la comunicación . Los problemas de DSC se refieren a la compresión de múltiples fuentes de información correlacionadas que no se comunican entre sí. [1] Al modelar la correlación entre múltiples fuentes en el lado del decodificador junto con los códigos de canal , DSC puede cambiar la complejidad computacional del lado del codificador al lado del decodificador, por lo tanto, proporciona marcos apropiados para aplicaciones con emisores con restricciones de complejidad, como redes de sensores. y compresión de video / multimedia (ver codificación de video distribuida [2]). Una de las principales propiedades de la codificación de fuente distribuida es que la carga computacional en los codificadores se traslada al descodificador conjunto.
Historia
En 1973, David Slepian y Jack Keil Wolf propusieron el límite de compresión sin pérdida teórica de la información en la compresión distribuida de dos fuentes iid correlacionadas X e Y. [3] Después de eso, este límite se extendió a casos con más de dos fuentes por Thomas M. Cover en 1975, [4] mientras que los resultados teóricos en el caso de compresión con pérdidas fueron presentados por Aaron D. Wyner y Jacob Ziv en 1976. [5]
Aunque los teoremas sobre DSC se propusieron en la década de 1970, fue después de unos 30 años que se iniciaron los intentos de técnicas prácticas, basados en la idea de que DSC está estrechamente relacionado con la codificación de canales propuesta en 1974 por Aaron D. Wyner . [6] El problema DSC asimétrico fue abordado por SS Pradhan y K. Ramchandran en 1999, que se centraron en fuentes binarias y gaussianas estadísticamente dependientes y utilizaron construcciones escalares y trellis coset para resolver el problema. [7] Ampliaron aún más el trabajo al caso DSC simétrico. [8]
La tecnología de decodificación de síndrome se utilizó por primera vez en la codificación de fuente distribuida por el sistema DISCUS de SS Pradhan y K Ramachandran (Codificación de fuente distribuida mediante síndromes). [7] Comprimen datos de bloques binarios de una fuente en síndromes y transmiten datos de la otra fuente sin comprimir como información secundaria . Este tipo de esquema DSC logra tasas de compresión asimétricas por fuente y da como resultado DSC asimétrico . Este esquema DSC asimétrico puede extenderse fácilmente al caso de más de dos fuentes de información correlacionadas. También hay algunos esquemas de DSC que utilizan bits de paridad en lugar de bits de síndrome.
La correlación entre dos fuentes en DSC se ha modelado como un canal virtual que generalmente se denomina canal simétrico binario . [9] [10]
A partir de DISCUS , DSC ha atraído una importante actividad de investigación y se han adoptado técnicas de codificación de canales más sofisticadas en los marcos de DSC, como Turbo Code , LDPC Code, etc.
De manera similar al marco de codificación sin pérdidas anterior basado en el teorema de Slepian-Wolf, se han realizado esfuerzos en casos con pérdidas basados en el teorema de Wyner-Ziv. R. Zamir y S. Shamai proporcionaron resultados teóricos sobre diseños de cuantificadores, [11] mientras que se han propuesto diferentes marcos basados en este resultado, incluido un cuantificador de red anidado y un cuantificador codificado en trellis.
Además, DSC se ha utilizado en la compresión de video para aplicaciones que requieren codificación de video de baja complejidad, como redes de sensores, videocámaras de múltiples vistas, etc. [12]
Con discusiones deterministas y probabilísticas del modelo de correlación de dos fuentes de información correlacionadas, se han desarrollado esquemas de DSC con tasas comprimidas más generales. [13] [14] [15] En estos esquemas no asimétricos , se comprimen las dos fuentes correlacionadas.
Bajo un cierto supuesto determinista de correlación entre fuentes de información, X. Cao y M. Kuijper han demostrado un marco de DSC en el que cualquier número de fuentes de información puede comprimirse de forma distribuida. [16] Este método realiza una compresión no asimétrica con tasas flexibles para cada fuente, logrando la misma tasa de compresión general que aplica repetidamente DSC asimétrico para más de dos fuentes. Luego, al investigar la conexión única entre síndromes y palabras clave complementarias de códigos lineales, han traducido los pasos principales de la decodificación conjunta DSC en decodificación de síndrome seguida de codificación de canal a través de un código de bloque lineal y también a través de su código de complemento, [17] que teóricamente ilustró un método para ensamblar un decodificador conjunto DSC a partir de codificadores y decodificadores de código lineal.
Límites teóricos
La compresión teórica sin pérdidas de la información ligada a DSC (la liga de Slepian-Wolf ) fue propuesta por primera vez por David Slepian y Jack Keil Wolf en términos de entropías de fuentes de información correlacionadas en 1973. [3] También mostraron que dos fuentes aisladas pueden comprimir datos como eficientemente como si se estuvieran comunicando entre sí. Este límite se ha extendido al caso de más de dos fuentes correlacionadas por Thomas M. Cover en 1975. [4]
Aaron D. Wyner y Jacob Ziv obtuvieron resultados similares en 1976 con respecto a la codificación con pérdida de fuentes gaussianas conjuntas. [5]
Slepian-Wolf obligado
La codificación distribuida es la codificación de dos o más fuentes dependientes con codificadores separados y decodificadores conjuntos. Dadas dos secuencias aleatorias de alfabeto finito iid estadísticamente dependientes X e Y, el teorema de Slepian-Wolf incluye un límite teórico para la tasa de codificación sin pérdidas para la codificación distribuida de las dos fuentes como se muestra a continuación: [3]
Si tanto el codificador como el descodificador de las dos fuentes son independientes, la tasa más baja que podemos lograr para la compresión sin pérdidas es y por y respectivamente, donde y son las entropías de y . Sin embargo, con la decodificación conjunta, si se acepta la probabilidad de error de desaparición para secuencias largas, el teorema de Slepian-Wolf muestra que se puede lograr una tasa de compresión mucho mejor. Siempre que la tasa total de y es más grande que su entropía conjunta y ninguna de las fuentes está codificada con una velocidad mayor que su entropía, la codificación distribuida puede lograr una probabilidad de error arbitrariamente pequeña para secuencias largas.
Un caso especial de codificación distribuida es la compresión con información del lado del decodificador, donde la fuente está disponible en el lado del decodificador pero no es accesible en el lado del codificador. Esto puede tratarse como la condición que ya se ha utilizado para codificar , mientras que tenemos la intención de usar para codificar . Todo el sistema funciona de forma asimétrica (la tasa de compresión de las dos fuentes es asimétrica).
Con destino a Wyner – Ziv
Poco después de que se publicara el teorema de Slepian-Wolf sobre la compresión distribuida sin pérdidas, se propuso la extensión a la compresión con pérdidas con información lateral del decodificador como teorema de Wyner-Ziv. [5] De manera similar al caso sin pérdidas, dos fuentes de iid estadísticamente dependientes y se dan, donde está disponible en el lado del decodificador pero no es accesible en el lado del codificador. En lugar de la compresión sin pérdidas en el teorema de Slepian-Wolf, el teorema de Wyner-Ziv examinó el caso de la compresión con pérdidas.
El teorema de Wyner-Ziv presenta el límite inferior alcanzable para la tasa de bits de a una distorsión dada . Se encontró que para fuentes gaussianas sin memoria y distorsión de error cuadrático medio, el límite inferior para la tasa de bits de siguen siendo los mismos sin importar si la información complementaria está disponible en el codificador o no.
Canal virtual
Modelo determinista
Modelo probabilístico
DSC asimétrico frente a DSC simétrico
DSC asimétrico significa que se utilizan diferentes velocidades de bits para codificar las fuentes de entrada, mientras que se utiliza la misma velocidad de bits en DSC simétrico. Tomando un diseño DSC con dos fuentes, por ejemplo, en este ejemplo y son dos fuentes discretas, sin memoria y distribuidas uniformemente que generan un conjunto de variables y de longitud 7 bits y la distancia de Hamming entre y es como máximo uno. El Slepian-Wolf con destino a ellos es:
Esto significa que el límite teórico es y DSC simétrico significa 5 bits para cada fuente. Otros pares con son casos asimétricos con diferentes distribuciones de velocidad de bits entre y , dónde , y , representan dos casos extremos llamados decodificación con información complementaria.
Práctica codificación de fuente distribuida
Codificación Slepian-Wolf: codificación distribuida sin pérdidas
Se entendió que la codificación de Slepian-Wolf está estrechamente relacionada con la codificación de canales en 1974, [6] y después de unos 30 años, la DSC práctica comenzó a implementarse mediante diferentes códigos de canal. La motivación detrás del uso de códigos de canal proviene del caso de dos fuentes, la correlación entre las fuentes de entrada se puede modelar como un canal virtual que tiene la entrada como fuente y salida como fuente . El sistema DISCUS propuesto por SS Pradhan y K. Ramchandran en 1999 implementó DSC con decodificación de síndrome , que funcionó para el caso asimétrico y se extendió aún más al caso simétrico. [7] [8]
El marco básico de DSC basado en síndrome es que, para cada fuente, su espacio de entrada se divide en varias clases laterales de acuerdo con el método de codificación de canal particular utilizado. Cada entrada de cada fuente obtiene una salida que indica a qué clase lateral pertenece la entrada, y el decodificador conjunto puede decodificar todas las entradas mediante los índices de clase lateral recibidos y la dependencia entre las fuentes. El diseño de códigos de canal debe considerar la correlación entre las fuentes de entrada.
Se puede utilizar un grupo de códigos para generar particiones coset, [18] como códigos trellis y códigos reticulares. Pradhan y Ramchandran diseñaron reglas para la construcción de subcódigos para cada fuente, y presentaron el resultado de las construcciones de coset basadas en trellis en DSC, que se basan en código de convolución y reglas de partición de conjuntos como en la modulación Trellis , así como en DSC basado en código de celosía. . [7] [8] Después de esto, se propuso el código Trellis incrustado para la codificación asimétrica como una mejora con respecto a sus resultados. [19]
Después de que se propuso el sistema DISCUS, se han adaptado códigos de canal más sofisticados al sistema DSC, como Turbo Code , LDPC Code y Iterative Channel Code. Los codificadores de estos códigos suelen ser simples y fáciles de implementar, mientras que los decodificadores tienen una complejidad computacional mucho mayor y pueden obtener un buen rendimiento utilizando estadísticas de origen. Con códigos de canal sofisticados que tienen un rendimiento que se acerca a la capacidad del canal de correlación, el sistema DSC correspondiente puede acercarse al límite de Slepian-Wolf.
Aunque la mayor parte de la investigación se centró en DSC con dos fuentes dependientes, la codificación de Slepian-Wolf se ha extendido a más de dos casos de fuentes de entrada, y V. Stankovic, AD Liveris, etc. propusieron métodos de generación de subcódigos a partir de un código de canal. modelos de correlación. [20]
Teorema general de la codificación de Slepian-Wolf con síndromes para dos fuentes
Teorema : cualquier par de fuentes correlacionadas uniformemente distribuidas,, con , se puede comprimir por separado a un par de tasas tal que , dónde y son enteros, y . Esto se puede lograr utilizando un código lineal binario.
Prueba : El Hamming con destino a un el código lineal binario es , y tenemos el código de Hamming logrando este límite, por lo tanto, tenemos un código lineal binario con matriz generadora . A continuación, mostraremos cómo construir una codificación de síndrome basada en este código lineal.
Dejar y formarse tomando primero filas de , tiempo se forma utilizando el resto filas de . y son los subcódigos del código Hamming generado por y respectivamente, con y como sus matrices de control de paridad.
Por un par de entradas , el codificador viene dado por y . Eso significa que podemos representar y como , , dónde son los representantes de las clases sociales con respecto a respectivamente. Desde que tenemos con . Podemos obtener, dónde , .
Suponga que hay dos pares de entrada diferentes con los mismos síndromes, eso significa que hay dos cadenas diferentes , tal que y . Así tendremos. Porque el peso mínimo de Hamming del código es , la distancia entre y es . Por otro lado, según Juntos con y , tendremos y , que contradice con . Por tanto, no podemos tener más de un par de entradas con los mismos síndromes.
Por lo tanto, podemos comprimir con éxito las dos fuentes dependientes con subcódigos construidos a partir de un código lineal binario, con par de tasas tal que , dónde y son enteros, y . El registro indica el registro 2 .
Ejemplo de codificación Slepian-Wolf
Tome el mismo ejemplo que en la parte anterior DSC asimétrico vs. DSC simétrico , esta parte presenta los esquemas de DSC correspondientes con códigos y síndromes de clase lateral, incluyendo caso asimétrico y caso simétrico. El destino de Slepian-Wolf para el diseño DSC se muestra en la parte anterior.
Caso asimétrico
En el caso donde y , la longitud de una variable de entrada de la fuente es de 7 bits, por lo que se puede enviar sin pérdidas con 7 bits independientemente de cualquier otro bit. Basado en el conocimiento de que y tener una distancia de Hamming como máximo uno, para la entrada de la fuente , ya que el receptor ya tiene , el único posible son los que tienen como máximo 1 distancia de . Si modelamos la correlación entre dos fuentes como un canal virtual, que tiene entrada y salida , siempre que tengamos , todo lo que necesitamos para "decodificar" correctamente son "bits de paridad" con una capacidad particular de corrección de errores, tomando la diferencia entre y como error de canal. También podemos modelar el problema con la partición de clases laterales. Es decir, queremos encontrar un código de canal, que sea capaz de dividir el espacio de entrada.en varias clases sociales, donde cada clase tiene un síndrome único asociado. Con una clase lateral dada y, sólo hay uno que es posible que sea la entrada dada la correlación entre dos fuentes.
En este ejemplo, podemos usar el código de Hamming binario , con matriz de control de paridad . Para una entrada de la fuente , solo el síndrome dado por se transmite, que es de 3 bits. Con recibido y , suponga que hay dos entradas y con el mismo síndrome . Eso significa, cual es . Dado que el peso mínimo de Hamming de El código de Hamming es 3, . Por lo tanto, la entrada se puede recuperar desde .
Del mismo modo, la distribución de bits con , puede lograrse invirtiendo los roles de y .
Caso simétrico
En un caso simétrico, lo que queremos es la misma tasa de bits para las dos fuentes: 5 bits cada una con codificador separado y descodificador conjunto. Todavía usamos códigos lineales para este sistema, como usamos para el caso asimétrico. La idea básica es similar, pero en este caso, necesitamos hacer una partición de clases laterales para ambas fuentes, mientras que para un par de síndromes recibidos (corresponde a una clase lateral), solo es posible un par de variables de entrada dada la correlación entre dos fuentes.
Supongamos que tenemos un par de código lineal y y un par codificador-decodificador basado en códigos lineales que pueden lograr una codificación simétrica. La salida del codificador viene dada por: y . Si existen dos pares de entradas válidas y generando los mismos síndromes, es decir y , podemos seguir ( representa el peso de Hamming):
, dónde
, dónde
Por lo tanto:
dónde y . Eso significa, siempre que tengamos la distancia mínima entre los dos códigos mayor que, podemos lograr una decodificación sin errores.
Los dos códigos y se pueden construir como subcódigos de la Código Hamming y, por lo tanto, tiene una distancia mínima de . Dada la matriz del generador del código Hamming original, la matriz generadora por se construye tomando dos filas cualesquiera de , y está construido por las dos filas restantes de . El correspondiente La matriz de verificación de paridad para cada subcódigo se puede generar de acuerdo con la matriz del generador y se puede usar para generar bits de síndrome.
Codificación Wyner-Ziv: codificación distribuida con pérdida
En general, un esquema de codificación Wyner-Ziv se obtiene agregando un cuantificador y un descuantificador al esquema de codificación de Slepian-Wolf. Por lo tanto, un diseño de codificador Wyner-Ziv podría centrarse en el cuantificador y el diseño del método de reconstrucción correspondiente. Se han propuesto varios diseños de cuantificadores, como un cuantificador de celosía anidado, [21] cuantificador de código trellis [22] y el método de cuantificación de Lloyd. [23]
Cuantización distribuida a gran escala
Desafortunadamente, los enfoques anteriores no se escalan (en requisitos de complejidad operativa o de diseño) a redes de sensores de gran tamaño, un escenario en el que la compresión distribuida es más útil. Si hay N fuentes que transmiten a R bits cada una (con algún esquema de codificación distribuida), el número de reconstrucciones posibles aumenta. Incluso para valores moderados de N y R (digamos N = 10, R = 2), los esquemas de diseño anteriores se vuelven imprácticos. Recientemente, se ha propuesto un enfoque, [24] que utiliza ideas tomadas de Fusion Coding of Correlated Sources, en el que el diseño y la complejidad operativa se intercambian con el rendimiento del decodificador. Esto ha permitido el diseño de cuantificadores distribuidos para tamaños de red que llegan a 60 fuentes, con ganancias sustanciales sobre los enfoques tradicionales.
La idea central es la presencia de un selector de subconjunto de bits que mantiene un cierto subconjunto de los bits recibidos (NR bits, en el ejemplo anterior) para cada fuente. Dejar ser el conjunto de todos los subconjuntos de los NR bits, es decir
Luego, definimos el mapeo del selector de subconjuntos de bits como
Tenga en cuenta que cada elección del selector de subconjunto de bits impone un requisito de almacenamiento (C) que es exponencial en la cardinalidad del conjunto de bits elegidos.
Esto permite una elección juiciosa de bits que minimizan la distorsión, dadas las limitaciones del almacenamiento del decodificador. Aún se necesitan limitaciones adicionales en el conjunto de subconjuntos permitidos. La función de costo efectivo que debe minimizarse es una suma ponderada de distorsión y almacenamiento del decodificador
El diseño del sistema se realiza optimizando iterativamente (e incrementalmente) los codificadores, el descodificador y el selector de subconjuntos de bits hasta la convergencia.
DSC no asimétrico
DSC no asimétrico para más de dos fuentes
El enfoque del síndrome todavía se puede utilizar para más de dos fuentes. Considerar fuentes binarias de longitud . Dejar Ser las matrices de codificación correspondientes de tamaños. . Luego, las fuentes binarias de entrada se comprimen en del total bits. Aparentemente, dos tuplas de origen no se pueden recuperar al mismo tiempo si comparten el mismo síndrome. En otras palabras, si todas las tuplas de origen de interés tienen diferentes síndromes, entonces se pueden recuperar sin pérdidas.
El resultado teórico general no parece existir. Sin embargo, para un tipo restringido de fuente denominada fuente Hamming [25] que sólo tiene como máximo una fuente diferente del resto y como máximo una ubicación de bit, no todos idénticos, se muestra que existe DSC práctico sin pérdidas en algunos casos. Para el caso de que haya más de dos fuentes, el número de tuplas de fuentes en una fuente de Hamming es. Por lo tanto, un embalaje obligaba aobviamente tiene que satisfacer. Cuando el límite de empaquetado se satisface con igualdad, podemos decir que dicho código es perfecto (un código análogo al código perfecto en el código de corrección de errores). [25]
Un conjunto más simple de Satisfacer el embalaje obligado con igualdad es . Sin embargo, resulta que dicho código de síndrome no existe. [26] El código de síndrome más simple (perfecto) con más de dos fuentes tiene y . Dejar
, y tal que son alguna partición de .
puede comprimir una fuente de Hamming (es decir, las fuentes que no tienen más de un bit diferente tendrán síndromes diferentes). [25] Por ejemplo, para el caso simétrico, un posible conjunto de matrices de codificación son
Ver también
- Código lineal
- Decodificación del síndrome
- Código de verificación de paridad de baja densidad
- Código Turbo
Referencias
- ^ "Codificación de fuente distribuida para redes de sensores" por Z. Xiong, AD Liveris y S. Cheng
- ^ "Codificación de video distribuida en redes de sensores inalámbricos" por Puri, R. Majumdar, A. Ishwar, P. Ramchandran, K.
- ^ a b c "Codificación silenciosa de fuentes de información correlacionadas" por D. Slepian y J. Wolf
- ^ a b "Una prueba del teorema de compresión de datos de Slepian y Wolf para fuentes ergódicas" por T. Cover
- ^ a b c "La función de distorsión de velocidad para la codificación de fuente con información lateral en el decodificador" por A. Wyner y J. Ziv
- ^ a b "Resultados recientes en la teoría de Shannon" por AD Wyner
- ^ a b c d "Codificación de fuente distribuida mediante síndromes (DISCUS): diseño y construcción" por SS Pradhan y K. Ramchandran
- ^ a b c "Codificación de fuente distribuida: tasas simétricas y aplicaciones a redes de sensores" por SS Pradhan y K. Ramchandran
- ^ "Construcciones de código distribuido para toda la región de tasa de Slepian-Wolf para fuentes correlacionadas arbitrariamente" por Schonberg, D. Ramchandran, K. Pradhan, SS
- ^ "Códigos de clase lateral generalizados para agrupamiento distribuido" por Pradhan, SS Ramchandran, K.
- ^ "Códigos anidados lineales / de celosía para la codificación Wyner-Ziv" por R. Zamir y S. Shamai
- ^ "Codificación de video distribuido" por B. Girod, etc.
- ^ "Sobre el diseño de código para el problema de Slepian-Wolf y redes multiterminales sin pérdidas" por Stankovic, V. Liveris, AD Zixiang Xiong Georghiades, CN
- ^ "Un marco general y óptimo para lograr toda la región de velocidad para la codificación Slepian-Wolf" por P. Tan y J. Li
- ^ "Codificación de fuente distribuida utilizando códigos LDPC compatibles con la tasa de longitud corta a moderada: toda la región de tasa de Slepian-Wolf" por Sartipi, M. Fekri, F.
- ^ "Un marco de codificación de fuente distribuida para múltiples fuentes" por Xiaomin Cao y Kuijper, M.
- ^ [1] "Codificación de fuente distribuida a través de códigos de bloques lineales: un marco general para múltiples fuentes" por Xiaomin Cao y Kuijper, M.
- ^ "Códigos de Coset. I. Introducción y clasificación geométrica" por GD Forney
- ^ "Diseño de códigos Trellis para codificación fuente con información lateral en el decodificador" por X. Wang y M. Orchard
- ^ "Diseño de códigos Slepian-Wolf por partición de código de canal" por V. Stankovic, AD Liveris, Z. Xiong y CN Georghiades
- ^ "Cuantización anidada y codificación Slepian-Wolf: un paradigma de codificación Wyner-Ziv para fuentes iid" por Z. Xiong, AD Liveris, S. Cheng y Z. Liu
- ^ "Codificación Wyner-Ziv basada en códigos TCQ y LDPC" por Y. Yang, S. Cheng, Z. Xiong y W. Zhao
- ^ "Diseño de cuantificadores óptimos para codificación de fuente distribuida" por D. Rebollo-Monedero, R. Zhang y B. Girod
- ^ "Hacia la codificación de fuentes distribuidas a gran escala" por S. Ramaswamy, K. Viswanatha, A. Saxena y K. Rose
- ^ a b c "Códigos de Hamming para múltiples fuentes" por R. Ma y S. Cheng
- ^ "La inexistencia de códigos de tres fuentes Slepian-Wolf de longitud 5" por S. Cheng y R. Ma Archivado el 25 de abril de 2012 en la Wayback Machine.