codificación distribuida luca martino teoría de la información master interuniversitario en...
TRANSCRIPT
Codificación Distribuida
Luca Martino Teoría de la Información
Master Interuniversitario en Comunicaciones y Multimedia
Antes del 1973….
(Teoría Clásica) Antes del 1973 se pensaba que:
Dada dos fuentes X y Y correlacionadas entre si, pueden ser codificadas sin perdidas:
1) a una tasa si la codifica es separada.
2) a una tasa inferior, si el codificador tiene acceso contemporáneamente a ambas fuentes (codifica conjunta).
)()( yHxHR
),( yxHR
H(x,y)
H(x)
H(y)
H(y|x)H(x|y) I(x;y)
)()(),( yHxHyxH
Resultado de Slepian-Wolf
Resultado de Slepian-Wolf (1973): dos fuentes correlacionadas pueden ser codificadas separadamente a un como si la codifica fuera conjunta, si el decodificador es capaz de aprovechar la correlación entre las 2 fuentes.
Comentario: Este resultado es posible complicando el diseño de decodificador (que ahora utiliza la información sobre la correlación entre las fuentes).
),( yxHR
Teorema de Slepian-Wolf
Indicando con Rx y Ry las tasas de compresión de las fuentes X y Y, cuanto dicho anteriormente se expresa en formulas así:
),(
)|(
)|(
yxHRR
xyHR
yxHR
yx
y
x
)(yH
)(xH)|( yxH
)|( xyH
),( yxH
),( yxH
R
Rx
Ry
Conceptos previos
en general:
Entre todas las posibles combinaciones, nos concentraremos en esto:
Codificador
Codificador
Decodificador
Decodificador
X
Y
X*
Y*
Codificador
Codificador
Decodificador
Decodificador
X
Y
X*
Y*
Conceptos previos
En las siguientes trasparencias demostraremos que dadas dos fuentes correlacionadas Y y X, podemos codificar sin perdidas la Y (dicha side information) con una tasa:
y separadamente codificar sin perdidas la fuente X a una tasa:
es decir: nuestro decodificador tienes que ser capaz conociendo Y, de decodificar sin perdidas X aprovechando la correlación entre las fuentes. Se puede pensar a Y=X+ruido como a una versión de X distorsionada por un ruido (como si la enviaríamos en un canal).La información añadida que sirve al receptor para neutralizar el ruido es propio H(x|y). Por esto, muchas soluciones propuestas para realizar la codificación distribuida se basan en codificación de canal.
Codificador DecodificadorX X*
Y
0 )( YYy yHR
0 )()|( XXx xHyxHR
Introducción
X y Y son variables aleatorias discretas que tomas valores en:
Considerando las parejas dadas por n-realizaciones independientes, tendremos:
),(),....,,(),,( 2211 nn YXYXYX
nYn
nXn
n
iiiXYXY
Ayyyy
Axxxx
yxpyYxXyxP
),...,,(
),...,,(
),(],Pr[),(
21
21
1
},...,2,1{
},...,2,1{
],Pr[),(
YY
XX
XY
aAy
aAx
yYxXyxp
Idea general
El teorema de codificación de canal nos dice que por n grande y cualquier ε, existe un decodificador y un código Q1 compuesto por vectores n-dim. que pueden ser utilizados como entradas de dicho canal, y decodificados con una pequeña probabilidad de error, cuando la salidas y están conocidas.
En general podríamos encontrar varios códigos Q2, Q3,…QM’ con mismo tamaño de Q1, y misma prestaciones.
)),((exp YXInM
)|( xypx y
Mxxx 11211 ,...,,
Idea general
Esquema de codificación: trasmitiremos al decodificador el índice i del código Qi che contiene la secuencia de entrada . El decodificador de X-Y utilizará el código Qi apropiado, según el canal, para decodificar bien la entrada. Recordando las secuencias típicas existirán secuencia de alta probabilidad en X, entonces nosotros necesitamos:
números de códigos Qi (M es el numero adecuado de vectores en Qi ). Utilizaremos esta notación luego:
))((exp XHn
)])|((exp[)exp(
)])((exp[)exp(
0 )|(
0 )(
Xxx
Yyy
XXx
YYy
yxHnnRM
yHnnRM
yxHR
yHR
))|((exp
)),((exp
))((exp))((exp' XYXHn
YXIn
XHn
M
XHnM
x
Idea general
Codificación a Intervalos casuales: (aplicado a una sola fuente) para cada secuencia de longitud n de la fuente X se extrae un índice a caso . El conjunto de las secuencias de X con mismo índice forman un “bin” (un intervalo). El codificador envia el indice al decodificador.
para decodificar se busca una secuencia típica en el intervalo, correspondiente al índice recibido; si hay una sola secuencia típica esta será nuestra estimación . Sino se declara un error en decodificación.
En practica se ha decidido decodificar solo secuencias típicas, porque la probabilidad que una secuencia sea típica es muy grande ( ). Si la secuencia enviada es típica en el intervalo correspondiente habrá por lo menos una (esta misma). Si la secuencia enviada no es típica se cometerá siempre un error. Por otra parte se el numero de intervalos es suficientemente alto, la prob. que haya más de un secuencia típica en un ‘bin’ es muy baja.
*x
1
x '2 2,...,2,2,1 nM
x
Secuencias Típicas
Nos hace falta recordar que para un conjunto típico T(n,ε) (por ejemplo de Y) valen las siguientes propiedades (teorema-1):
1) Por n grande prácticamente todas las secuencias son típicas:
2) existe un A>0 tal que por cada secuencia y de T(n,ε), vale:
3) el numero N de secuencias típicas será:
0 1)],(Pr[ nTY
nAYnHyPnAYnH Y )(exp)()(exp
n
YHnN
n
n
0)(
))()((exp
),( nT Conjunto típico de Y (hay N secuencias)
n Numero de elementos en las fuentes Y y X
YMNNN yyyyyy ,...,,,..., 2121
L
T NMY
Observaciones
Yn )(Eligiendo un
Codificador-Y
1
)min()( i
Y
yyiyf
si si
Ly
Ly
nYA YM
)(yfI Yy
Codificador-X
, M vectores de , con .
Con Q (‘X-supercode’) indicamos un conjunto de MX posible Qi (‘X-code’).
Q es como una matriz de 3 dimensiones (M lo vamos a elegir nosotros según convenga!).
},...,,{ 21 iMiii xxxQ
nXA xMi ,...2,1
1
)min()( i
X
Qyixf
si si
Qx
Qx
MAnX XM
)(xfI XX
nMM x
Decodificadores
El decodificador de X es más complicado; siendo j el mínimo índice tal que:
Nosotros tenemos que mostrar que existe un Q (‘X-supercode’) de manera
que para cualquier valga:
),(
),(*
*
YXY
YXX
IIgY
IIgX
}]{}Pr[{)( ** YYXXQPe
0
jiYXX
kiiXYjiiXY
X
XYXY
xiig
xyPxyP
),(
)|()|( ||
Mk ,....2,1 YXYX MMii ),(
Un Súper-Código Q esta definido por unos específicos MMX valores de los vectores aleatorios , .
Dicho E el conjunto de todos los posibles supercódigos Q, la estructura probabilística de E es:
nXij AX xMi ,...2,1
Estructura probabilística
Mj ,...,2,1
n
kkX
M
i
M
jijXxijij
xpxP
xPMjMixXx
1
)()(
)(],...,1,,...,1,Pr[
Probabilidad de error
Si enumeramos todos los posibles supercódigos de E como Q(1), Q(2)…la probabilidad de error media será:
Podemos acotar esta probabilidad:
}]|}{}Pr[{)()( )(**)1( j
je QQYYXXQQPQP
],,Pr[
]Pr[
]Pr[
*3
2
1
XXQXLYP
QXP
LYP
LY Si entonces no puedo
cometer errores en codificarlo (Y=Y*).
321)( PPPQPe
La prob. de la unión es menor o igual a la suma de las probabilidades (son iguales cuando hay
independencia(?)).
Acotar P1
Vamos a acotar cada una de estas probabilidades; la primera es trivial por definición de secuencia típica:
dado que L incluye T(n,ε), conjunto típico de Y; recordamos que:
]Pr[1 LYP
n
nTY 1)],(Pr[
Acotar P2
Recordando la estructura probabilística:
podemos expresar P2:
x
MMXX
x
XxPxPP
xXQXxXQXP
)](1[)(
]|Pr[]Pr[]Pr[
2
2
n
kkX
M
i
M
jijXxijij
xpxP
xPMjMixXx
1
)()(
)(],...,1,,...,1,Pr[
Acotando P2 …
Siempre considerando el teorema-1 que define las secuencias típicas, vale:
(1)
(2)
(3)
(4)
(5)
)(]})([exp{'
xPn
AxHn X
cXX
X
X
cX
X
X
TxX
TxX
MM
MMX
TxX
MMX
TxX
xPxPn
AXHn
xPxPxPxPP
)()()(exp1
)](1)[()](1)[(
'
2
Por la (1) 1 0
ZP
nAXHn
XMM
2
')(exp1
Acotando P2 …
Continuando, aplicamos un logaritmo a ambos miembros:
(6)
Y como por , y eligiendo:
(7)
Teniendo en cuenta que :
(8)
nAXHnMMZ X
')(exp1loglog
xx )1log( 0x
]))([exp(]))|([exp(])),([exp(
]))|([exp(
])),([exp(
'
21
21
nAXHnYXHnYXIn
YXHnM
YXInM
XX
XX
X
)|()();( YXHXHYXI
nA
xnZ'
21explog
P2 acotado!!!
Con un ε>0 fijo, por :
(9)
Es decir por n grande Z<ε, entonces:
(10)
n
0
log
Z
Z
22
2
P
ZP
Acotar P3
teniendo en cuenta que :
donde con A(x,y) indicamos:
Es decir me equivoco i-1 veces “en la columna”…:
xyXY
xyXY yxAyxPyYxXXXQXyxP
XXQXXXQXLYP
),(),(],|,Pr[),(
],Pr[],,Pr[*
**3
)(),( xpyxp
)()|(),( xpyxpyxp <1 <1
y
yxpxp ),()(
XM
iii yYxXXXQXQXQXQX
yYxXXXQXyxA
1
*121
*
],|,,,...,,Pr[
],|,Pr[),(
MX
M
],|,,,...,,Pr[),(
),()](1[),(
*)1(21
1 1
)1(
yYxXXXxXxXxXxXyxB
yxBxPyxA
ijjiiiij
M
i
M
jij
MiX
X
(11)
(12)
(13)
Acotando P3 …
De la misma manera me equivoco j-1 veces y acierto 1 vez:
),()()](1[),( 1 yxCxPxPyxB ijXj
Xij
(j-1) fallos 1 éxito
yYxXxXxXjxyPXyPyxC
yYxXXXyxC
ijiXYiXYij
ij
,,,...,|con ),|()|(Pr),(
],|Pr[),(
1||
*
Recordando el decodificador-X; la desigualdad vale porque (?) en decodifica se elegía el mínimo índice…
D
Probabilidad de error en decodifica de X
DxyPXyP
DxyPXyPyxC
jXYiXY
XYiXYj
ij
|)|()|(Pr
|)|()|(Pr),(
||
||
(14)
(15)
10 (16)
Acotando P3 …
Si α>j, una parte de información en D no aporta nada:
También en el caso α<j podemos reducir D:
Finalmente:
yYxXxyPXyPDxyPXyP XYiXYXYiXY
,|)|()|(Pr|)|()|(Pr |||| (17)
yYxXxXyYxXxyPXyP
yYxXxXyYxXxXxyPXyP
yYxXxXxyPXyPDxyPXyP
iXYiXY
iiXYiXY
iXYiXYXYiXY
,|Pr,|)|()|(Pr
,|Pr,|),|()|(Pr
,,|)|()|(Pr|)|()|(Pr
||
||
||||
(18)
)(),( xpyxp
1)](1[],|Pr[
],|)|()|(Pr[]|)|()|(Pr[ ||1
||
xPyYxXxXa
yYxXxyPXyPaDxyPXyP
Xi
XYiXYXYiXY
(19)
Acotando P3 …
Juntando la (16) con la (17) y la (19), logramos:
Donde la suma está restringida a los para los cuales . Por este conjunto entonces y podemos escribir:
Para cualquier s≥0.
UiX
XYiXYij
xPjMaj
yYxXxyPXyPjMajyxC
)()1(
,|)|()|(Pr)1(),(
1
||1
α<j α>j
ix )|()|( || xyPxyP XYiXY
1)|()|( || xyPxyP XYiXY
' |
|1
)|(
)'|()'()1(),(
x
s
XY
XYXij xyP
xyPxPjMajyxC
(20)
(21)
Acotando P3 …resumiendo
Hemos llegado a esta ‘batería’ de formulas (11),(13),(14) y (21):
),()()](1[),(
),()](1[),(
),(),(
)1(
1 1
)1(
3
yxCxPxPyxB
yxBxPyxA
yxAyxPP
ijXj
Xij
M
i
M
jij
MiX
xyXY
X
' |
|1
)|(
)'|()'()1(),(
x
s
XY
XYXij xyP
xyPxPjMajyxC
1)](1[ xPa X
(22)
Seguimos acotando…
Sustituyendo las expresiones de a,A(x,y) y Bij(x,y) hallamos:
Falta solo por sustituir Cij(x,y):
xy
M
i
M
jijX
jMiXY
X
yxCxPaayxPP1 1
)1()1(3 ),()(),(
(23)
xy
M
i x
s
XY
XYX
M
jX
jMiXY
X
xyP
xyPxPjMajxPaayxPP
' |
|11)1(3 )|(
)'|()'()1()(),(
(24)
… acotando …
Se puede demostrar que:
Sustituyendo la expresión y a la (24):
)(
)1( 11)1(
xP
MjMajaa
X
M
i
M
j
jMiX
(25)
'|
1|3
'|
|
|3
)'|()'()|()(
)'|()'()(
)()|(
)|()(
x
sXYX
xy
sXYX
x
sXYX
XX
xys
XY
XYX
xyPxPMxyPxPP
xyPxPxP
MxP
xyP
xyPxPP
(26)
)()|(),( xpxypyxp
… acotando …
Eligiendo la (26) queda:
Donde T es una cantidad conocida en Teoría de la Información (cota superior por la probabilidad de error en un canal sin memoria encontrada por Gallager). Luego teniendo en cuenta la (28) y sustituyendo arriba:
y xXYX xyPxPMTP
1
|31
1
)|()(
(27)
)1(1 s
n
iiiXYXY
n
iiX
x
xypxyP
xpxP
YXnIM
)|()|,(
)()(
),(exp
||
21
(28)
P3 acotado!!!
….con simples calculos (y haciendo una derivata…) llegamos por fin a una expresión de este tipo:
y juntado los resultados obtenidos:
demostración terminada.
nP
nP X
4exp
3
03
(29)
4)(
)( 321
QP
PPPQP
e
e
Ejemplo
X e Y son 2 fuentes, con 8 palabras códigos (3 bits) equiprobables (H(x)=log(8)=3). Están correlacionadas en manera que sus distancia de Hamming es como máximo 1: es decir si Y es 010 X puede ser solo 000,011,110,010.
Codifica predictiva clásica: Y conocida por el codificador y por decodificador.
para codificar X con Y conocida, necesitamos solo 2 bits porque X puede tomar solo 4 valores distintos.
Codificador DecodificadorX X*
Y
Ejemplo
Codifica distribuida: Y conocida solo por el decodificador.
000
100
010
001
011
101
110
111
El Codificador enviará solo el índice del “Bin”; necesitará solo 2 bits.
Bin1={000,111}
Bin2={001,110}
Bin3={010,101}
Bin4={100,011}
Decodificador: Elige la palabra código dentro del “Bin” más cercana a Y.
Índice “Bin” (ejemplo=1)
Y =(010)
X*=(000)
X=(000)
Realmente hemos utilizado la información sobre la correlación en el codificador, creando “Bins” con palabra codigos con distancia 2 (la distancia entre Y y X al maximo será 1).
Codificador DecodificadorX X*
Y