Codificación de código fuente distribuida

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 trasladar la complejidad computacional del lado del codificador al lado del decodificador, por lo que 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 propiedades principales de la codificación de fuente distribuida es que la carga computacional en los codificadores se traslada al decodificador conjunto.

Historia

En 1973, David Slepian y Jack Keil Wolf propusieron la cota de compresión sin pérdidas basada en la teoría de la información para la compresión distribuida de dos fuentes i.i.d. correlacionadas X e Y. ^{[ 3 ]} Posteriormente, esta cota fue extendida 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 aproximadamente 30 años después que se iniciaron los intentos de técnicas prácticas, basadas en la idea de que DSC está estrechamente relacionada con la codificación de canal propuesta en 1974 por Aaron D. Wyner . ^{[ 6 ]} El problema de DSC asimétrico fue abordado por SS Pradhan y K. Ramchandran en 1999, quienes se centraron en fuentes binarias y gaussianas estadísticamente dependientes y utilizaron construcciones de clases laterales escalares y de enrejado para resolver el problema. ^{[ 7 ]} Posteriormente extendieron el trabajo al caso de DSC simétrico. ^{[ 8 ]}

La tecnología de decodificación de síndromes se utilizó por primera vez en la codificación de fuente distribuida por el sistema DISCUS de SS Pradhan y K Ramachandran (Distributed Source Coding Using Syndromes). ^{[ 7 ]} Estos sistemas comprimen datos binarios de bloques de una fuente en síndromes y transmiten datos de la otra fuente sin comprimir como información auxiliar . Este tipo de esquema DSC logra tasas de compresión asimétricas por fuente y da como resultado un DSC asimétrico . Este esquema DSC asimétrico se puede extender fácilmente al caso de más de dos fuentes de información correlacionadas. También existen algunos esquemas 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 binario simétrico . ^{[ 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 canal más sofisticadas en los marcos de DSC, como Turbo Code , LDPC Code, etc. Las construcciones de matrices dispersas son otra línea de teoría de la codificación: Muramatsu y Miyake introdujeron un marco de propiedad hash para conjuntos de matrices dispersas y codificación de máxima verosimilitud, demostrando la viabilidad para la codificación de Wyner-Ziv y problemas de codificación de fuente relacionados. ^{[ 11 ]}

De forma 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 ^{[ 12 ]} , y se han propuesto diferentes marcos basados en este resultado, incluyendo un cuantificador de retículo anidado y un cuantificador codificado en enrejado.

Además, DSC se ha utilizado en la compresión de vídeo para aplicaciones que requieren una codificación de vídeo de baja complejidad, como redes de sensores, videocámaras multivista, etc. ^{[ 13 ]}

Con discusiones deterministas y probabilísticas del modelo de correlación de dos fuentes de información correlacionadas, se han desarrollado esquemas DSC con tasas de compresión más generales. ^{[ 14 ]}^{[ 15 ]}^{[ 16 ]} En estos esquemas no asimétricos , ambas de las dos fuentes correlacionadas se comprimen.

Bajo una cierta suposición determinista de correlación entre fuentes de información, X. Cao y M. Kuijper demostraron un marco DSC en el que cualquier número de fuentes de información puede comprimirse de forma distribuida. ^{[ 17 ]} 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 al aplicar 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, tradujeron los pasos principales de la decodificación conjunta DSC en una 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 complementario, ^{[ 18 ]} lo que ilustró teóricamente un método para ensamblar un decodificador conjunto DSC a partir de codificadores y decodificadores de código lineal.

Límites teóricos

La cota de compresión sin pérdidas basada en la teoría de la información para DSC (la cota 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 demostraron que dos fuentes aisladas pueden comprimir datos con la misma eficiencia que si se comunicaran entre sí. Esta cota fue extendida al caso de más de dos fuentes correlacionadas por Thomas M. Cover en 1975. ^{[ 4 ]}

Resultados similares fueron obtenidos en 1976 por Aaron D. Wyner y Jacob Ziv con respecto a la codificación con pérdidas de fuentes gaussianas conjuntas. ^{[ 5 ]}

Slepian-Wolf unido

La codificación distribuida es la codificación de dos o más fuentes dependientes con codificadores separados y decodificador conjunto. Dadas dos secuencias aleatorias de alfabeto finito e i.i.d. 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 ]}

R_{X}\geq H(X|Y),\,

R_{Y}\geq H(Y|X),\,

R_{X}+R_{Y}\geq H(X,Y).\,

Si tanto el codificador como el decodificador de las dos fuentes son independientes, la tasa más baja que podemos lograr para la compresión sin pérdidas es $H(X)$ y $H(Y)$ para $X$ y $Y$ respectivamente, donde $H(X)$ y $H(Y)$ son las entropías de $X$ y $Y$ Sin embargo, con la decodificación conjunta, si se acepta una probabilidad de error nula 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 $X$ y $Y$ es mayor que su entropía conjunta $H(X,Y)$ y dado que ninguna de las fuentes se codifica con una tasa 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 $Y$ está disponible en el lado del decodificador pero no es accesible en el lado del codificador. Esto puede tratarse como la condición de que $R_{Y}=H(Y)$ ya se ha utilizado para codificar $Y$ , mientras que pretendemos utilizar $H(X|Y)$ codificar $X$ Todo el sistema funciona de forma asimétrica (la tasa de compresión para las dos fuentes es asimétrica).

Wyner-Ziv se unió

Poco después de la publicación del teorema de Slepian-Wolf sobre compresión distribuida sin pérdidas, se propuso la extensión a la compresión con pérdidas con información del lado del decodificador como el teorema de Wyner-Ziv. ^{[ 5 ]} De manera similar al caso sin pérdidas, dos fuentes i.i.d. estadísticamente dependientes $X$ y $Y$ se dan, donde $Y$ 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 del teorema de Slepian-Wolf, el teorema de Wyner-Ziv analizó 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 $X$ con una distorsión dada $D$ 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 $X$ permanecen iguales independientemente de si la información lateral está disponible en el codificador o no.

Para más de dos terminales, la codificación de fuente multiterminal estudia las regiones de distorsión de la tasa cuando varias observaciones correlacionadas se codifican por separado y se decodifican conjuntamente. Yasutada Oohama obtuvo resultados para la codificación de fuente multiterminal gaussiana, un caso central de alfabeto continuo de este problema. ^{[ 19 ]}

Canal virtual

Modelo determinista

Modelo probabilístico

DSC asimétrico frente a DSC simétrico

DSC asimétrico significa que se utilizan diferentes tasas de bits para codificar las fuentes de entrada, mientras que en DSC simétrico se utiliza la misma tasa de bits. Tomando como ejemplo un diseño DSC con dos fuentes, en este ejemplo $X$ y $Y$ son dos fuentes discretas, sin memoria y distribuidas uniformemente que generan un conjunto de variables $\mathbf {x}$ y $\mathbf {y}$ de longitud 7 bits y la distancia de Hamming entre $\mathbf {x}$ y $\mathbf {y}$ es como máximo uno. El Slepian-Wolf que se dirige hacia ellos es:

R_{X}+R_{Y}\geq 10

R_{X}\geq 5

R_{Y}\geq 5

Esto significa que el límite teórico es $R_{X}+R_{Y}=10$ y DSC simétrico significa 5 bits para cada fuente. Otros pares con $R_{X}+R_{Y}=10$ son casos asimétricos con diferentes distribuciones de tasa de bits entre $X$ y $Y$ , dónde $R_{X}=3$ , $R_{Y}=7$ y $R_{Y}=3$ , $R_{X}=7$ representan dos casos extremos llamados decodificación con información adicional.

Codificación de código fuente distribuida práctica

Codificación Slepian-Wolf: codificación distribuida sin pérdidas

En 1974 se comprendió que la codificación Slepian-Wolf está estrechamente relacionada con la codificación de canal ^{[ 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. $X$ y salida como fuente $Y$ 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 posteriormente se extendió al caso simétrico. ^{[ 7 ]}^{[ 8 ]}

El marco básico del DSC basado en síndromes consiste en que, para cada fuente, su espacio de entrada se divide en varias clases laterales según el método de codificación de canal utilizado. Cada entrada de cada fuente recibe una salida que indica a qué clase lateral pertenece, y el decodificador conjunto puede decodificar todas las entradas mediante los índices de clases laterales recibidos y la dependencia entre las fuentes. El diseño de los códigos de canal debe tener en cuenta la correlación entre las fuentes de entrada.

Se puede utilizar un grupo de códigos para generar particiones de clases laterales, ^{[ 20 ]} como códigos de enrejado 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 construcciones de clases laterales basadas en enrejado en DSC, que se basa en el código de convolución y reglas de partición de conjuntos como en la modulación de enrejado , así como DSC basado en código reticular. ^{[ 7 ]}^{[ 8 ]} Después de esto, se propuso el código de enrejado incrustado para la codificación asimétrica como una mejora sobre sus resultados. ^{[ 21 ]}

Tras la propuesta del sistema DISCUS, se han adaptado códigos de canal más sofisticados al sistema DSC, como el código Turbo , el código LDPC y el código de canal iterativo. Los codificadores de estos códigos suelen ser sencillos y fáciles de implementar, mientras que los decodificadores presentan una complejidad computacional mucho mayor y logran un buen rendimiento mediante el uso de estadísticas de la fuente. Con códigos de canal sofisticados cuyo rendimiento se aproxima a la capacidad del canal de correlación, el sistema DSC correspondiente puede alcanzar el límite de Slepian-Wolf.

Aunque la mayoría de las investigaciones se centraron en DSC con dos fuentes dependientes, la codificación Slepian-Wolf se ha extendido al caso de más de dos 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 dados modelos de correlación particulares. ^{[ 22 ]}

Teorema general de la codificación de Slepian-Wolf con síndromes para dos fuentes

Teorema : Cualquier par de fuentes correlacionadas distribuidas uniformemente, $X,Y\in \left\{0,1\right\}^{n}$ , con $\mathbf {d_{H}} (X,Y)\leq t$ , se pueden comprimir por separado a una tasa de par $(R_{1},R_{2})$ de tal manera que $R_{1},R_{2}\geq nk,R_{1}+R_{2}\geq 2n-k$ , dónde $R_{1}$ y $R_{2}$ son números enteros y $k\leq n-\log(\sum _{i=0}^{t}{n \choose i})$ Esto se puede lograr utilizando un $(n,k,2t+1)$ código lineal binario.

Prueba : El límite de Hamming para un $(n,k,2t+1)$ El código lineal binario es $k\leq n-\log(\sum _{i=0}^{t}{n \choose i})$ y tenemos un código de Hamming que alcanza este límite, por lo tanto tenemos un código lineal binario de este tipo. $\mathbf {C}$ con $k\times n$ matriz generadora $\mathbf {G}$ A continuación, mostraremos cómo construir una codificación de síndromes basada en este código lineal.

Dejar $R_{1}+R_{2}=2n-k$ y $\mathbf {G_{1}}$ ser formado tomando primero $(n-R_{1})$ filas de $\mathbf {G}$ , mientras $\mathbf {G_{2}}$ se forma utilizando el resto $(n-R_{2})$ filas de $\mathbf {G}$ . $\mathbf {C_{1}}$ y $\mathbf {C_{2}}$ son los subcódigos del código Hamming generado por $\mathbf {G_{1}}$ y $\mathbf {G_{2}}$ respectivamente, con $\mathbf {H_{1}}$ y $\mathbf {H_{2}}$ como sus matrices de verificación de paridad.

Para un par de entradas $\mathbf {(x,y)}$ , el codificador viene dado por $\mathbf {s_{1}} =\mathbf {H_{1}} \mathbf {x}$ y $\mathbf {s_{2}} =\mathbf {H_{2}} \mathbf {y}$ . Eso significa que podemos representar $\mathbf {x}$ y $\mathbf {y}$ como $\mathbf {x=u_{1}G_{1}+c_{s1}}$ , $\mathbf {y=u_{2}G_{2}+c_{s2}}$ , dónde $\mathbf {c_{s1},c_{s2}}$ son los representantes de los cosets de $\mathbf {s1,s2}$ con respecto a $\mathbf {C_{1},C_{2}}$ respectivamente. Dado que tenemos $\mathbf {y=x+e}$ con $w(\mathbf {e} )\leq t$ Podemos conseguirlo. $\mathbf {x+y=uG+c_{s}=e}$ , dónde $\mathbf {u=\left[u_{1},u_{2}\right]}$ , $\mathbf {c_{s}=c_{s1}+c_{s2}}$ .

Supongamos que hay dos pares de entrada diferentes con los mismos síndromes, eso significa que hay dos cadenas diferentes. $\mathbf {u^{1},u^{2}} \in \left\{0,1\right\}^{k}$ , de tal manera que $\mathbf {u^{1}G+c_{s}=e}$ y $\mathbf {u^{2}G+c_{s}=e}$ . Por lo tanto tendremos $\mathbf {(u^{1}-u^{2})G=0}$ . Porque el peso mínimo de Hamming del código $\mathbf {C}$ es $2t+1$ , la distancia entre $\mathbf {u_{1}G}$ y $\mathbf {u_{2}G}$ es $\geq 2t+1$ Por otro lado, según $w(\mathbf {e} )\leq t$ junto con $\mathbf {u^{1}G+c_{s}=e}$ y $\mathbf {u^{2}G+c_{s}=e}$ , tendremos $d_{H}(\mathbf {u^{1}G,c_{s}} )\leq t$ y $d_{H}(\mathbf {u^{2}G,c_{s}} )\leq t$ , que contradicen $d_{H}(\mathbf {u^{1}G,u^{2}G} )\geq 2t+1$ Por lo 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 $(n,k,2t+1)$ código lineal binario, con par de tasas $(R_{1},R_{2})$ de tal manera que $R_{1},R_{2}\geq n-k,R_{1}+R_{2}\geq 2n-k$ , dónde $R_{1}$ y $R_{2}$ son números enteros y $k\leq n-\log(\sum _{i=0}^{t}{n \choose i})$ . El registro indica Registro ₂ .

Ejemplo de codificación Slepian-Wolf

Tomando el mismo ejemplo que en la sección anterior sobre DSC asimétrico frente a DSC simétrico , esta sección presenta los esquemas DSC correspondientes con códigos de clases laterales y síndromes, incluyendo el caso asimétrico y el caso simétrico. La cota de Slepian-Wolf para el diseño de DSC se muestra en la sección anterior.

caso asimétrico

En el caso donde $R_{X}=3$ y $R_{Y}=7$ la longitud de una variable de entrada $\mathbf {y}$ de la fuente $Y$ es de 7 bits, por lo tanto, se puede enviar sin pérdidas con 7 bits independientemente de cualquier otro bit. Basándonos en el conocimiento de que $\mathbf {x}$ y $\mathbf {y}$ tener distancia de Hamming como máximo uno, para entrada $\mathbf {x}$ de la fuente $X$ , puesto que el receptor ya tiene $\mathbf {y}$ , la única posible $\mathbf {x}$ son aquellos con como máximo 1 distancia de $\mathbf {y}$ . Si modelamos la correlación entre dos fuentes como un canal virtual, que tiene entrada $\mathbf {x}$ y salida $\mathbf {y}$ , siempre y cuando consigamos $\mathbf {y}$ , todo lo que necesitamos para "descifrar" con éxito $\mathbf {x}$ son "bits de paridad" con una capacidad particular de corrección de errores, tomando la diferencia entre $\mathbf {x}$ y $\mathbf {y}$ como error de canal. También podemos modelar el problema con partición de clases laterales. Es decir, queremos encontrar un código de canal que sea capaz de particionar el espacio de entrada. $X$ en varios grupos, donde cada grupo tiene un síndrome único asociado. Con un grupo dado y $\mathbf {y}$ , solo hay uno $\mathbf {x}$ Eso es posible que sea la entrada dada la correlación entre dos fuentes.

En este ejemplo, podemos usar el $(7,4,3)$ Código Hamming binario $\mathbf {C}$ , con matriz de verificación de paridad $\mathbf {H}$ . Para una entrada $\mathbf {x}$ de la fuente $X$ , solo el síndrome dado por $\mathbf {s} =\mathbf {H} \mathbf {x}$ se transmite, que son 3 bits. Con recibido $\mathbf {y}$ y $\mathbf {s}$ Supongamos que hay dos entradas $\mathbf {x_{1}}$ y $\mathbf {x_{2}}$ con el mismo síndrome $\mathbf {s}$ Eso significa $\mathbf {H} \mathbf {x_{1}} =\mathbf {H} \mathbf {x_{2}}$ , que es $\mathbf {H} (\mathbf {x_{1}} -\mathbf {x_{2}} )=0$ . Dado que el peso mínimo de Hamming de $(7,4,3)$ El código de Hamming es 3, $d_{H}(\mathbf {x_{1}} ,\mathbf {x_{2}} )\geq 3$ . Por lo tanto, la entrada $\mathbf {x}$ puede recuperarse ya que $d_{H}(\mathbf {x} ,\mathbf {y} )\leq 1$ .

De manera similar, la distribución de bits con $R_{X}=7$ , $R_{Y}=3$ se puede lograr invirtiendo los roles de $X$ y $Y$ .

Caso simétrico

En el caso simétrico, buscamos una tasa de bits igual para ambas fuentes: 5 bits cada una con un codificador independiente y un decodificador conjunto. Seguimos utilizando códigos lineales para este sistema, al igual que en el caso asimétrico. La idea básica es similar, pero en este caso, necesitamos realizar una partición de clases laterales para ambas fuentes, mientras que para un par de síndromes recibidos (que corresponde a una clase lateral), solo es posible un par de variables de entrada dada la correlación entre las dos fuentes.

Supongamos que tenemos un par de códigos lineales $\mathbf {C_{1}}$ y $\mathbf {C_{2}}$ y un par codificador-decodificador basado en códigos lineales que puede lograr una codificación simétrica. La salida del codificador viene dada por: $\mathbf {s_{1}} =\mathbf {H_{1}} \mathbf {x}$ y $\mathbf {s_{2}} =\mathbf {H_{2}} \mathbf {y}$ . Si existen dos pares de entradas válidas $\mathbf {x_{1}} ,\mathbf {y_{1}}$ y $\mathbf {x_{2}} ,\mathbf {y_{2}}$ generando los mismos síndromes, es decir $\mathbf {H_{1}} \mathbf {x_{1}} =\mathbf {H_{1}} \mathbf {x_{2}}$ y $\mathbf {H_{1}} \mathbf {y_{1}} =\mathbf {H_{1}} \mathbf {y_{2}}$ , podemos obtener lo siguiente( $w()$ representa el peso de Hamming):

$\mathbf {y_{1}} =\mathbf {x_{1}} +\mathbf {e_{1}}$ , dónde $w(\mathbf {e_{1}} )\leq 1$

$\mathbf {y_{2}} =\mathbf {x_{2}} +\mathbf {e_{2}}$ , dónde $w(\mathbf {e_{2}} )\leq 1$

De este modo: $\mathbf {x_{1}} +\mathbf {x_{2}} \in \mathbf {C_{1}}$

$\mathbf {y_{1}} +\mathbf {y_{2}} =\mathbf {x_{1}} +\mathbf {x_{2}} +\mathbf {e_{3}} \in \mathbf {C_{2}}$

dónde $\mathbf {e_{3}} =\mathbf {e_{2}} +\mathbf {e_{1}}$ y $w(\mathbf {e_{3}} )\leq 2$ . Eso significa que, siempre y cuando tengamos la distancia mínima entre los dos códigos mayor que $3$ Podemos lograr una decodificación sin errores.

Los dos códigos $\mathbf {C_{1}}$ y $\mathbf {C_{2}}$ se pueden construir como subcódigos del $(7,4,3)$ código Hamming y por lo tanto tiene distancia mínima de $3$ . Dada la matriz generadora $\mathbf {G}$ del código Hamming original, la matriz generadora $\mathbf {G_{1}}$ para $\mathbf {C_{1}}$ se construye tomando cualesquiera dos filas de $\mathbf {G}$ , y $\mathbf {G_{2}}$ se construye con las dos filas restantes de $\mathbf {G}$ . El correspondiente $(5\times 7)$ La matriz de verificación de paridad para cada subcódigo se puede generar de acuerdo con la matriz generadora y utilizarse 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 añadiendo un cuantificador y un descuantizador al esquema de codificación Slepian-Wolf. Por lo tanto, el diseño de un 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 retículo anidado, ^{[ 23 ]} un cuantificador de código de enrejado ^{[ 24 ]} y el método de cuantificación de Lloyd. ^{[ 25 ]}

Cuantización distribuida a gran escala

Desafortunadamente, los enfoques anteriores no son escalables (en cuanto a diseño o requisitos de complejidad operativa) para redes de sensores de gran tamaño, un escenario donde 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. $2^{NR}$ Incluso para valores moderados de N y R (por ejemplo, N=10, R=2), los esquemas de diseño previos resultan poco prácticos. Recientemente, se ha propuesto un enfoque ^{[ 26 ]} que utiliza ideas de la codificación de fusión de fuentes correlacionadas, donde la complejidad del diseño y la operación se compensan con el rendimiento del decodificador. Esto ha permitido el diseño de cuantificadores distribuidos para redes de hasta 60 fuentes, con mejoras sustanciales respecto a 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 (bits NR, en el ejemplo anterior) para cada fuente. ${\mathcal {B}}$ sea el conjunto de todos los subconjuntos de los bits NR, es decir

{\mathcal {B}}=2^{\{1,...,NR\}}

Luego, definimos la asignación del selector de subconjunto de bits como

{\mathcal {S}}:\{1,...,N\}\rightarrow {\mathcal {B}}

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.

C=\sum _{n=1}^{N}2^{|{\mathcal {S}}(n)|}

Esto permite una selección juiciosa de bits que minimicen la distorsión, dadas las restricciones de almacenamiento del decodificador. Aún se necesitan limitaciones adicionales en el conjunto de subconjuntos permitidos. La función de costo efectiva que debe minimizarse es una suma ponderada de la distorsión y el almacenamiento del decodificador.

J=D+\lambda C

El diseño del sistema se lleva a cabo optimizando de forma iterativa (e incremental) los codificadores, el decodificador y el selector de subconjuntos de bits hasta alcanzar la convergencia.

DSC no asimétrico para más de dos fuentes

El enfoque del síndrome aún puede utilizarse para más de dos fuentes. Considere $a$ fuentes binarias de longitud- $n$ $\mathbf {x} _{1},\mathbf {x} _{2},\cdots ,\mathbf {x} _{a}\in \{0,1\}^{n}$ . Dejar $\mathbf {H} _{1},\mathbf {H} _{2},\cdots ,\mathbf {H} _{s}$ sean las matrices de codificación correspondientes de tamaños $m_{1}\times n,m_{2}\times n,\cdots ,m_{a}\times n$ Luego, las fuentes binarias de entrada se comprimen en $\mathbf {s} _{1}=\mathbf {H} _{1}\mathbf {x} _{1},\mathbf {s} _{2}=\mathbf {H} _{2}\mathbf {x} _{2},\cdots ,\mathbf {s} _{a}=\mathbf {H} _{a}\mathbf {x} _{a}$ del total $m=m_{1}+m_{2}+\cdots m_{a}$ bits. Aparentemente, no se pueden recuperar dos tuplas de origen al mismo tiempo si comparten el mismo síndrome. En otras palabras, si todas las tuplas de origen de interés tienen síndromes diferentes, entonces se pueden recuperar sin pérdida de información.

No parece existir un resultado teórico general. Sin embargo, para un tipo restringido de fuente, denominada fuente de Hamming ^{[ 27 ],} que tiene como máximo una fuente diferente del resto y como máximo una ubicación de bit no idéntica, se demuestra que existe DSC sin pérdidas en algunos casos. Para el caso en que hay más de dos fuentes, el número de tuplas de fuente en una fuente de Hamming es $2^{n}(an+1)$ . Por lo tanto, un límite de empaquetamiento que $2^{m}\geq 2^{n}(an+1)$ Obviamente, debe satisfacerse. Cuando se satisface la cota de empaquetamiento con igualdad, podemos decir que dicho código es perfecto (un análogo del código perfecto en el código corrector de errores). ^{[ 27 ]}

Un conjunto más simple de $a,n,m$ para satisfacer el empaquetado ligado con igualdad es $a=3,n=5,m=9$ . Sin embargo, resulta que tal código de síndrome no existe. ^{[ 28 ]} El código de síndrome más simple (perfecto) con más de dos fuentes tiene $n=21$ y $m=27$ . Dejar

$\mathbf {Q} _{1}={\begin{pmatrix}1\;0\;0\;0\;0\;0\;1\;0\;0\;0\;0\;1\;1\;1\;0\;1\;1\;0\;0\;0\;0\\0\;1\;0\;0\;0\;0\;1\;1\;0\;0\;0\;0\;1\;0\;0\;0\;0\;0\;1\;1\;1\\0\;0\;1\;0\;0\;0\;0\;1\;1\;0\;0\;0\;0\;1\;1\;1\;0\;1\;0\;1\;1\\0\;0\;0\;1\;0\;0\;0\;0\;1\;1\;0\;0\;0\;1\;0\;0\;1\;1\;1\;1\;0\\0\;0\;0\;0\;1\;0\;0\;0\;0\;1\;1\;0\;1\;0\;1\;1\;0\;1\;1\;1\;1\\0\;0\;0\;0\;0\;1\;0\;0\;0\;0\;1\;1\;0\;0\;1\;0\;0\;1\;1\;0\;1\end{pmatrix}},$ $\mathbf {Q} _{2}={\begin{pmatrix}0\;0\;0\;1\;0\;1\;1\;0\;1\;1\;1\;1\;0\;1\;0\;0\;0\;1\;1\;1\;1\\1\;0\;0\;0\;1\;0\;1\;1\;0\;1\;1\;1\;1\;0\;1\;1\;1\;1\;0\;0\;0\\0\;1\;0\;0\;0\;1\;1\;1\;1\;0\;1\;1\;1\;0\;0\;0\;0\;0\;1\;0\;1\\1\;0\;1\;0\;0\;0\;1\;1\;1\;1\;0\;1\;0\;1\;1\;1\;0\;0\;1\;1\;1\\0\;1\;0\;1\;0\;0\;1\;1\;1\;1\;1\;0\;0\;0\;1\;0\;1\;1\;0\;1\;1\\0\;0\;1\;0\;1\;0\;0\;1\;1\;1\;1\;1\;1\;1\;0\;1\;0\;1\;1\;1\;0\end{pmatrix}},$ $\mathbf {Q} _{3}={\begin{pmatrix}1\;0\;0\;1\;0\;1\;0\;0\;1\;1\;1\;0\;1\;0\;0\;1\;1\;1\;1\;1\;1\\1\;1\;0\;0\;1\;0\;0\;0\;0\;1\;1\;1\;0\;0\;1\;1\;1\;1\;1\;1\;1\\0\;1\;1\;0\;0\;1\;1\;0\;0\;0\;1\;1\;1\;1\;1\;1\;0\;1\;1\;1\;0\\1\;0\;1\;1\;0\;0\;1\;1\;0\;0\;0\;1\;0\;0\;1\;1\;1\;1\;0\;0\;1\\0\;1\;0\;1\;1\;0\;1\;1\;1\;0\;0\;0\;1\;0\;0\;1\;1\;0\;1\;0\;0\\0\;0\;1\;0\;1\;1\;0\;1\;1\;1\;0\;0\;1\;1\;1\;1\;0\;0\;0\;1\;1\end{pmatrix}},$ $\mathbf {G} =[\mathbf {0} |\mathbf {I} _{9}]$ , y $\mathbf {G} ={\begin{pmatrix}\mathbf {G} _{1}\\\mathbf {G} _{2}\\\mathbf {G} _{3}\end{pmatrix}}$ de tal manera que $\mathbf {G} _{1},\mathbf {G} _{2},\mathbf {G} _{3}$ son cualquier partición de $\mathbf {G}$ .

$\mathbf {H} _{1}={\begin{pmatrix}\mathbf {G} _{1}\\\mathbf {Q} _{1}\end{pmatrix}},\mathbf {H} _{2}={\begin{pmatrix}\mathbf {G} _{2}\\\mathbf {Q} _{2}\end{pmatrix}},\mathbf {H} _{3}={\begin{pmatrix}\mathbf {G} _{3}\\\mathbf {Q} _{3}\end{pmatrix}}$ puede comprimir una fuente Hamming (es decir, las fuentes que no tienen más de un bit de diferencia tendrán todas síndromes diferentes). ^{[ 27 ]} Por ejemplo, para el caso simétrico, un posible conjunto de matrices de codificación son $\mathbf {H} _{1}={\begin{pmatrix}0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;1\;0\;0\\0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;1\;0\\0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;1\\1\;0\;0\;0\;0\;0\;1\;0\;0\;0\;0\;1\;1\;1\;0\;1\;1\;0\;0\;0\;0\\0\;1\;0\;0\;0\;0\;1\;1\;0\;0\;0\;0\;1\;0\;0\;0\;0\;0\;1\;1\;1\\0\;0\;1\;0\;0\;0\;0\;1\;1\;0\;0\;0\;0\;1\;1\;1\;0\;1\;0\;1\;1\\0\;0\;0\;1\;0\;0\;0\;0\;1\;1\;0\;0\;0\;1\;0\;0\;1\;1\;1\;1\;0\\0\;0\;0\;0\;1\;0\;0\;0\;0\;1\;1\;0\;1\;0\;1\;1\;0\;1\;1\;1\;1\\0\;0\;0\;0\;0\;1\;0\;0\;0\;0\;1\;1\;0\;0\;1\;0\;0\;1\;1\;0\;1\end{pmatrix}},$ $\mathbf {H} _{2}={\begin{pmatrix}0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;1\;0\;0\;0\;0\;0\\0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;1\;0\;0\;0\;0\\0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;1\;0\;0\;0\\0\;0\;0\;1\;0\;1\;1\;0\;1\;1\;1\;1\;0\;1\;0\;0\;0\;1\;1\;1\;1\\1\;0\;0\;0\;1\;0\;1\;1\;0\;1\;1\;1\;1\;0\;1\;1\;1\;1\;0\;0\;0\\0\;1\;0\;0\;0\;1\;1\;1\;1\;0\;1\;1\;1\;0\;0\;0\;0\;0\;1\;0\;1\\1\;0\;1\;0\;0\;0\;1\;1\;1\;1\;0\;1\;0\;1\;1\;1\;0\;0\;1\;1\;1\\0\;1\;0\;1\;0\;0\;1\;1\;1\;1\;1\;0\;0\;0\;1\;0\;1\;1\;0\;1\;1\\0\;0\;1\;0\;1\;0\;0\;1\;1\;1\;1\;1\;1\;1\;0\;1\;0\;1\;1\;1\;0\end{pmatrix}},$ $\mathbf {H} _{3}={\begin{pmatrix}0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;1\;0\;0\;0\;0\;0\;0\;0\;0\\0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;1\;0\;0\;0\;0\;0\;0\;0\\0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;1\;0\;0\;0\;0\;0\;0\\1\;0\;0\;1\;0\;1\;0\;0\;1\;1\;1\;0\;1\;0\;0\;1\;1\;1\;1\;1\;1\\1\;1\;0\;0\;1\;0\;0\;0\;0\;1\;1\;1\;0\;0\;1\;1\;1\;1\;1\;1\;1\\0\;1\;1\;0\;0\;1\;1\;0\;0\;0\;1\;1\;1\;1\;1\;1\;0\;1\;1\;1\;0\\1\;0\;1\;1\;0\;0\;1\;1\;0\;0\;0\;1\;0\;0\;1\;1\;1\;1\;0\;0\;1\\0\;1\;0\;1\;1\;0\;1\;1\;1\;0\;0\;0\;1\;0\;0\;1\;1\;0\;1\;0\;0\\0\;0\;1\;0\;1\;1\;0\;1\;1\;1\;0\;0\;1\;1\;1\;1\;0\;0\;0\;1\;1\end{pmatrix}}.$

Véase también

Referencias

↑ "Codificación de fuente distribuida para redes de sensores" por Z. Xiong, AD Liveris y S. Cheng
↑ "Codificación de vídeo distribuida en redes de sensores inalámbricas" por Puri, R. Majumdar, A. Ishwar, P. Ramchandran, K.
1 2 3 "Codificación sin ruido de fuentes de información correlacionadas" por D. Slepian y J. Wolf
1 2 "Una demostración del teorema de compresión de datos de Slepian y Wolf para fuentes ergódicas" por T. Cover
1 2 3 "La función de distorsión de tasa para la codificación de fuente con información lateral en el decodificador" por A. Wyner y J. Ziv
1 2 "Resultados recientes en la teoría de Shannon" por AD Wyner
1 2 3 4 "Codificación de código fuente distribuida mediante síndromes (DISCUS): diseño y construcción" por SS Pradhan y K. Ramchandran
1 2 3 "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 tasas de Slepian-Wolf para fuentes arbitrariamente correlacionadas" por Schonberg, D. Ramchandran, K. Pradhan, SS
↑ "Códigos de clases laterales generalizados para la agrupación distribuida" por Pradhan, SS Ramchandran, K.
↑ Muramatsu, Jun; Miyake, Shigeki (mayo de 2010). "Propiedad hash y teoremas de codificación para matrices dispersas y codificación de máxima verosimilitud". IEEE Transactions on Information Theory . 56 (5): 2143– 2167. arXiv : 0801.3878 . doi : 10.1109/TIT.2010.2043781 .
↑ "Códigos lineales/reticulares anidados para la codificación Wyner-Ziv" por R. Zamir y S. Shamai
↑ "Codificación de vídeo distribuida" 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 tasas 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 código fuente distribuido para múltiples fuentes" por Xiaomin Cao y Kuijper, M.
↑"Codificación de código fuente distribuida mediante códigos de bloques lineales: un marco general para múltiples fuentes" por Xiaomin Cao y Kuijper, M.
↑ Oohama, Yasutada (1997). "Codificación de fuente multiterminal gaussiana". IEEE Transactions on Information Theory . 43 (6): 1912– 1923. doi : 10.1109/18.641555 .
↑ "Códigos de clases laterales. I. Introducción y clasificación geométrica" por GD Forney
↑ "Diseño de códigos de enrejado para codificación de fuente con información auxiliar en el decodificador" por X. Wang y M. Orchard
↑ "Diseño de códigos Slepian-Wolf mediante partición de código de canal" por V. Stankovic, AD Liveris, Z. Xiong y CN Georghiades
↑ "Cuantización anidada y codificación de Slepian-Wolf: un paradigma de codificación de Wyner-Ziv para fuentes i.i.d." 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 código fuente distribuida a gran escala" por S. Ramaswamy, K. Viswanatha, A. Saxena y K. Rose" (PDF) . Archivado del original (PDF) el 1 de abril de 2011. Consultado el 19 de enero de 2011 .
1 2 3 "Códigos de Hamming para múltiples fuentes" por R. Ma y S. Cheng
↑ "La inexistencia de códigos Slepian-Wolf de longitud 5 de tres fuentes" por S. Cheng y R. Ma. Archivado el 25 de abril de 2012 en Wayback Machine .

[1] "Codificación de fuente distribuida para redes de sensores" por Z. Xiong, AD Liveris y S. Cheng

[2] "Codificación de vídeo distribuida en redes de sensores inalámbricas" por Puri, R. Majumdar, A. Ishwar, P. Ramchandran, K.

[swbound-3] 1 2 3 "Codificación sin ruido de fuentes de información correlacionadas" por D. Slepian y J. Wolf

[swergodic-4] 1 2 "Una demostración del teorema de compresión de datos de Slepian y Wolf para fuentes ergódicas" por T. Cover

[wzbound-5] 1 2 3 "La función de distorsión de tasa para la codificación de fuente con información lateral en el decodificador" por A. Wyner y J. Ziv

[swpractical-6] 1 2 "Resultados recientes en la teoría de Shannon" por AD Wyner

[discus-7] 1 2 3 4 "Codificación de código fuente distribuida mediante síndromes (DISCUS): diseño y construcción" por SS Pradhan y K. Ramchandran

[discus2-8] 1 2 3 "Codificación de fuente distribuida: tasas simétricas y aplicaciones a redes de sensores" por SS Pradhan y K. Ramchandran

[9] "Construcciones de código distribuido para toda la región de tasas de Slepian-Wolf para fuentes arbitrariamente correlacionadas" por Schonberg, D. Ramchandran, K. Pradhan, SS

[10] "Códigos de clases laterales generalizados para la agrupación distribuida" por Pradhan, SS Ramchandran, K.

[11] Muramatsu, Jun; Miyake, Shigeki (mayo de 2010). "Propiedad hash y teoremas de codificación para matrices dispersas y codificación de máxima verosimilitud". IEEE Transactions on Information Theory . 56 (5): 2143– 2167. arXiv : 0801.3878 . doi : 10.1109/TIT.2010.2043781 .

[wzquantize-12] "Códigos lineales/reticulares anidados para la codificación Wyner-Ziv" por R. Zamir y S. Shamai

[dvc-13] "Codificación de vídeo distribuida" por B. Girod, etc.

[14] "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

[15] "Un marco general y óptimo para lograr toda la región de tasas para la codificación Slepian-Wolf" por P. Tan y J. Li

[16] "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.

[17] "Un marco de codificación de código fuente distribuido para múltiples fuentes" por Xiaomin Cao y Kuijper, M.

[18] "Codificación de código fuente distribuida mediante códigos de bloques lineales: un marco general para múltiples fuentes" por Xiaomin Cao y Kuijper, M.

[19] Oohama, Yasutada (1997). "Codificación de fuente multiterminal gaussiana". IEEE Transactions on Information Theory . 43 (6): 1912– 1923. doi : 10.1109/18.641555 .

[20] "Códigos de clases laterales. I. Introducción y clasificación geométrica" por GD Forney

[21] "Diseño de códigos de enrejado para codificación de fuente con información auxiliar en el decodificador" por X. Wang y M. Orchard

[22] "Diseño de códigos Slepian-Wolf mediante partición de código de canal" por V. Stankovic, AD Liveris, Z. Xiong y CN Georghiades

[23] "Cuantización anidada y codificación de Slepian-Wolf: un paradigma de codificación de Wyner-Ziv para fuentes i.i.d." por Z. Xiong, AD Liveris, S. Cheng y Z. Liu

[24] "Codificación Wyner-Ziv basada en códigos TCQ y LDPC" por Y. Yang, S. Cheng, Z. Xiong y W. Zhao

[25] "Diseño de cuantificadores óptimos para codificación de fuente distribuida" por D. Rebollo-Monedero, R. Zhang y B. Girod

[26] ""Hacia la codificación de código fuente distribuida a gran escala" por S. Ramaswamy, K. Viswanatha, A. Saxena y K. Rose" (PDF) . Archivado del original (PDF) el 1 de abril de 2011. Consultado el 19 de enero de 2011 .

[HCMS-27] 1 2 3 "Códigos de Hamming para múltiples fuentes" por R. Ma y S. Cheng

[28] "La inexistencia de códigos Slepian-Wolf de longitud 5 de tres fuentes" por S. Cheng y R. Ma. Archivado el 25 de abril de 2012 en Wayback Machine .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ],

[ 28 ]