capacidad de canal - udl...

Capacidad decanal

Canal:definiciones ytipos

Codificación

Segundoteorema deShannon, CCT

Capacidad de canalCTI: Lección 4, Segundo teorema de Shannon (CCT)

(cf. Cap. 5 de Informació i codis, J. M. Brunat y E. Ventura,Edicions UPC, 2001)

Ramiro Moreno Chiral

12 de marzo de 2007

Capacidad decanal

Codificación

Índice

1 Canal: definiciones y tipos

2 Codificación

3 Segundo teorema de Shannon, CCT

Capacidad decanal

Canal:definiciones ytipos¿Qué es un canal?

Capacidad de canal

Tipos de canal

Codificación

Índice

1 Canal: definiciones y tipos¿Qué es un canal?Capacidad de canalTipos de canal

2 Codificación

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Definición de canal

Un canal es una terna K = (X , Y , T ), dondeX es una v.a. (fuente) que toma valores sobre unalfabeto de entrada, X = {a1, . . . , am};Y es otra v.a. (receptor) con valores en un alfabeto desalida, Y = {b1, . . . , bn};Y T es la matriz de transición, de dimensionesm × n, estocástica por filas, definida

T = P(Y = bj |X = ai) = (pij),con 1 ≤ i ≤ m, 1 ≤ j ≤ n.

RCanalF

P(X) P(Y)T=P(Y|X)

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Un canal es una terna K = (X , Y , T ), donde

X es una v.a. (fuente) que toma valores sobre unalfabeto de entrada, X = {a1, . . . , am};Y es otra v.a. (receptor) con valores en un alfabeto desalida, Y = {b1, . . . , bn};Y T es la matriz de transición, de dimensionesm × n, estocástica por filas, definida

RCanalF

P(X) P(Y)T=P(Y|X)

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Un canal es una terna K = (X , Y , T ), dondeX es una v.a. (fuente) que toma valores sobre unalfabeto de entrada, X = {a1, . . . , am};

Y es otra v.a. (receptor) con valores en un alfabeto desalida, Y = {b1, . . . , bn};Y T es la matriz de transición, de dimensionesm × n, estocástica por filas, definida

RCanalF

P(X) P(Y)T=P(Y|X)

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Un canal es una terna K = (X , Y , T ), dondeX es una v.a. (fuente) que toma valores sobre unalfabeto de entrada, X = {a1, . . . , am};Y es otra v.a. (receptor) con valores en un alfabeto desalida, Y = {b1, . . . , bn};

Y T es la matriz de transición, de dimensionesm × n, estocástica por filas, definida

RCanalF

P(X) P(Y)T=P(Y|X)

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

RCanalF

P(X) P(Y)T=P(Y|X)

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

RCanalF

P(X) P(Y)T=P(Y|X)

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

RCanalF

P(X) P(Y)T=P(Y|X)

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Algunas propiedades

Si A es una matriz m × n, estocástica por filas y X unadistribución de probabilidad dada como un m-vector fila,entonces

Y = X · A,

es una distribución de probabilidad dada por el n-vectorfila Y .

Podemos considerar, fijada T , la información mutua

I(X ; Y ) = H(X )− H(X |Y ) = H(Y )− H(Y |X ),

como una función en las pi = P(X = ai), 1 ≤ i ≤ m:I(X ; Y ) = f (p1, p2, · · · , pm)

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Algunas propiedades

Y = X · A,

I(X ; Y ) = H(X )− H(X |Y ) = H(Y )− H(Y |X ),

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Algunas propiedades

Y = X · A,

I(X ; Y ) = H(X )− H(X |Y ) = H(Y )− H(Y |X ),

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Algunas propiedades

Y = X · A,

I(X ; Y ) = H(X )− H(X |Y ) = H(Y )− H(Y |X ),

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Algunas propiedades

Y = X · A,

I(X ; Y ) = H(X )− H(X |Y ) = H(Y )− H(Y |X ),

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Definición de capacidad de canal

Por lo tanto, tiene sentido calcular el máximo de lainformación mutua, I(X ; Y ) = f (p1, p2, · · · , pm), respecto alas probabilidades de entrada pi = P(X = ai), 1 ≤ i ≤ m.

Definición

Dado un canal K = (X , Y , T ), llamaremos capacidad deK al valor

C(K) = max{p1,··· ,pm}

I(X ; Y ).

La capacidad es fácilmente calculable en los llamadoscanales simétricos.

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Definición

C(K) = max{p1,··· ,pm}

I(X ; Y ).

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Definición

C(K) = max{p1,··· ,pm}

I(X ; Y ).

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Definición

C(K) = max{p1,··· ,pm}

I(X ; Y ).

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Canales simétricos respecto a la entrada

Definición

Dado un canal K = (X , Y , T ), diremos que es simétricorespecto a la entrada, si todas las filas de T tienen losmismos valores (posiblemente en diferentes columnas).

Proposición

Sea K = (X , Y , T ) un canal simétrico respecto a laentrada, entonces

1 Todas las filas de T tienen la misma entropía, H0.2 I(X ; Y ) = H(Y )− H0. Por lo tanto, C(K) ≤ log n − H0.3 Se alcanza la igualdad, C(K) = log n − H0, si existe

una X para la que Y es uniforme.

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Definición

Proposición

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Definición

Proposición

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Canales simétricos respecto a la salida

Definición

Dado un canal K = (X , Y , T ), diremos que es simétricorespecto a la salida, si todas las columnas de T tienenlos mismos valores (posiblemente en diferentes filas).

Si K = (X , Y , T ) es un canal simétrico respecto a la saliday X es una v.a. uniforme, entonces Y también lo es.

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Definición

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Definición

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Capacidad de los canales simétricos

Definición

Un canal K = (X , Y , T ) se llama simétrico si es simétricorespecto a la entrada y a la salida.

Proposición

Con las notaciones anteriores, si K = (X , Y , T ) es uncanal simétrico, se tiene

C(K) = log n − H0.

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Definición

Proposición

C(K) = log n − H0.

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Definición

Proposición

C(K) = log n − H0.

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Capacidad de los canales BSC

Corolario

Como los BSC son simétricos se tiene

C(KBSC) = 1− h(p).

Sea KBSC con probabilidad de error en un bit p = 0′2.Entonces es C(KBSC) = 1− h(0′2) = 0′28 bits.

0’4 0’6 0’8 1

1−h(p) Capacidad del BSC

0’20

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Corolario

C(KBSC) = 1− h(p).

0’4 0’6 0’8 1

0’20

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Corolario

C(KBSC) = 1− h(p).

Sea KBSC con probabilidad de error en un bit p = 0′2.Entonces es

C(KBSC) = 1− h(0′2) = 0′28 bits.

0’4 0’6 0’8 1

0’20

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Corolario

C(KBSC) = 1− h(p).

0’4 0’6 0’8 1

0’20

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Corolario

C(KBSC) = 1− h(p).

0’4 0’6 0’8 1

0’20

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Capacidad de los canales BEC

Corolario

Los BEC son simétricos respecto a la entrada, pero norespecto a la salida. Luego, C(KBEC) ≤ log 3− H0.

Como el sistema en p1 y p2

(p1, p2)

(1− p − q q p

p q 1− p − q

(13,13,13

tiene solución p1 = p2 = 12 para cualquier p ∈ [0, 1] y

cuando q = 13 , ese valor máximo se alcanza.

Si KBEC es un canal con probabilidades de error p = 0′1 yde borrón q = 1

3 , se tiene

C(KBEC) = log 3− H(1730

,13, 0′1) = 0′26 bits.

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Corolario

(p1, p2)

(1− p − q q p

p q 1− p − q

(13,13,13

3 , se tiene

C(KBEC) = log 3− H(1730

,13, 0′1) = 0′26 bits.

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Corolario

(p1, p2)

(1− p − q q p

p q 1− p − q

(13,13,13

3 , se tiene

C(KBEC) = log 3− H(1730

,13, 0′1) = 0′26 bits.

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Corolario

(p1, p2)

(1− p − q q p

p q 1− p − q

(13,13,13

3 , se tiene

C(KBEC) = log 3− H(1730

,13, 0′1) = 0′26 bits.

Capacidad decanal

Capacidad de canal

Tipos de canal

Codificación

Corolario

(p1, p2)

(1− p − q q p

p q 1− p − q

(13,13,13

3 , se tiene

C(KBEC) = log 3− H(1730

,13, 0′1) = 0′26 bits.

Capacidad decanal

CodificaciónIntroducción

Ejemplo

Probabilidades de erroral decodificar

Otro ejemplo

Índice

2 CodificaciónIntroducciónEjemploProbabilidades de error al decodificarOtro ejemplo

Capacidad decanal

Ejemplo

Otro ejemplo

Codificación de canal

P(X)T=P(Y|X)

COD zyxCanal

RDECOD

zruido

MODELO GENERAL DE UN CANAL

x’x’

C(x)=y f(z)=y’

Capacidad decanal

Ejemplo

Otro ejemplo

P(X)T=P(Y|X)

COD zyxCanal

RDECOD

zruido

x’x’

C(x)=y f(z)=y’

Capacidad decanal

Ejemplo

Otro ejemplo

P(X)T=P(Y|X)

COD zyxCanal

RDECOD

zruido

x’x’

C(x)=y f(z)=y’

1. Modelo probabilístico, K = (X , Y , T ):

1.1 Una fuente F emite caracteres x ∈ A de un alfabetosegún una v.a. X .

1.2 Se recibe en R un carácter x ′ ∈ A con probabilidadregida por la v.a. Y .

1.3 El canal introduce un ruido expresado por la matriz deprobabilidades de transición, T Y |X .

Capacidad decanal

Ejemplo

Otro ejemplo

P(X)T=P(Y|X)

COD zyxCanal

RDECOD

zruido

x’x’

C(x)=y f(z)=y’

Capacidad decanal

Ejemplo

Otro ejemplo

P(X)T=P(Y|X)

COD zyxCanal

RDECOD

zruido

x’x’

C(x)=y f(z)=y’

Capacidad decanal

Ejemplo

Otro ejemplo

P(X)T=P(Y|X)

COD zyxCanal

RDECOD

zruido

x’x’

C(x)=y f(z)=y’

Capacidad decanal

Ejemplo

Otro ejemplo

P(X)T=P(Y|X)

COD zyxCanal

RDECOD

zruido

x’x’

C(x)=y f(z)=y’

2. Codificador (COD):

2.1 Es un algoritmo determinista: P(x) = P(y).2.2 Consiste en una aplicación

C : A → C ⊆ Bn

x 7→ y ,

siendo B un alfabeto de canal y C, el código.

Capacidad decanal

Ejemplo

Otro ejemplo

P(X)T=P(Y|X)

COD zyxCanal

RDECOD

zruido

x’x’

C(x)=y f(z)=y’

2.1 Es un algoritmo determinista: P(x) = P(y).

2.2 Consiste en una aplicación

C : A → C ⊆ Bn

x 7→ y ,

Capacidad decanal

Ejemplo

Otro ejemplo

P(X)T=P(Y|X)

COD zyxCanal

RDECOD

zruido

x’x’

C(x)=y f(z)=y’

2.1 Es un algoritmo determinista: P(x) = P(y).2.2 Consiste en una aplicación

C : A → C ⊆ Bn

x 7→ y ,

Capacidad decanal

Ejemplo

Otro ejemplo

P(X)T=P(Y|X)

COD zyxCanal

RDECOD

zruido

x’x’

C(x)=y f(z)=y’

3. El canal introduce ruido que convierte la palabra–códigoy ∈ C ⊆ Bn en una palabra z ∈ Bn.

Capacidad decanal

Ejemplo

Otro ejemplo

P(X)T=P(Y|X)

COD zyxCanal

RDECOD

zruido

x’x’

C(x)=y f(z)=y’

4. Decodificador (DECOD):

4.1 Es un algoritmo determinista: P(z) = P(x ′).4.2 Se trata de una aplicación f : Bn → C, tal que

f (z) = y ′, llamada esquema de decisión o regla dedecodificación, que minimiza la probabilidad deerror al decodificar, P(y ′ 6= y).

Capacidad decanal

Ejemplo

Otro ejemplo

P(X)T=P(Y|X)

COD zyxCanal

RDECOD

zruido

x’x’

C(x)=y f(z)=y’

4.1 Es un algoritmo determinista: P(z) = P(x ′).

4.2 Se trata de una aplicación f : Bn → C, tal quef (z) = y ′, llamada esquema de decisión o regla dedecodificación, que minimiza la probabilidad deerror al decodificar, P(y ′ 6= y).

Capacidad decanal

Ejemplo

Otro ejemplo

P(X)T=P(Y|X)

COD zyxCanal

RDECOD

zruido

x’x’

C(x)=y f(z)=y’

4.1 Es un algoritmo determinista: P(z) = P(x ′).4.2 Se trata de una aplicación f : Bn → C, tal que

f (z) = y ′, llamada esquema de decisión o regla dedecodificación, que minimiza la probabilidad deerror al decodificar, P(y ′ 6= y).

Capacidad decanal

Ejemplo

Otro ejemplo

P(X)T=P(Y|X)

COD zyxCanal

RDECOD

zruido

x’x’

C(x)=y f(z)=y’

5. Finalmente, el decodificador recupera, a partir de lapalabra–código y ′, un carácter fuente x ′ que R recibe.

Capacidad decanal

Ejemplo

Otro ejemplo

Un código de repetición (I)

1. Modelo probabilístico. Sea un KBSC con probabilidadde error en un bit 0 < p < 1

2 . Y un único alfabetofuente y canal, A = B = F2 = {0, 1}.

2. Código. Usamos un código de repetición 3,Rep(3) = {(000), (111)},

C : F2 → Rep(3) ⊂ F32

x = b 7→ y = (bbb).

3. Esquema de decisión. Será la regla dedecodificación por lógica mayoritaria,

f : F32 → Rep(3)

z = (b′1b′2b′3) 7→ y ′ =

{(000), si 2 o 3 de los b′i son ceros,

(111), si 2 o 3 de los b′i son unos.

Capacidad decanal

Ejemplo

Otro ejemplo

C : F2 → Rep(3) ⊂ F32

x = b 7→ y = (bbb).

f : F32 → Rep(3)

z = (b′1b′2b′3) 7→ y ′ =

Capacidad decanal

Ejemplo

Otro ejemplo

C : F2 → Rep(3) ⊂ F32

x = b 7→ y = (bbb).

f : F32 → Rep(3)

z = (b′1b′2b′3) 7→ y ′ =

Capacidad decanal

Ejemplo

Otro ejemplo

C : F2 → Rep(3) ⊂ F32

x = b 7→ y = (bbb).

f : F32 → Rep(3)

z = (b′1b′2b′3) 7→ y ′ =

Capacidad decanal

Ejemplo

Otro ejemplo

Un código de repetición (II)

4. El decodificador dará a R el bit x ′ = 0 o 1 según seay ′ = (000) o (111).

Llamemos P(Ef ) a la probabilidad de error en ladecodificación. En nuestro caso,

P(Ef ) = P(2 o 3 errores)

)p2(1− p) +

)p3 = 3p2 − 2p3.

Pero, P(Ef ) = 3p2 − 2p3 < p ⇐⇒ 2p2 − 3p + 1 > 0, locual siempre es cierto para 0 < p < 1

2 , ya que2p2 − 3p + 1 = 2(p − 1

2)(p − 1)

Capacidad decanal

Ejemplo

Otro ejemplo

)p2(1− p) +

)p3 = 3p2 − 2p3.

2 , ya que2p2 − 3p + 1 = 2(p − 1

2)(p − 1)

Capacidad decanal

Ejemplo

Otro ejemplo

Llamemos P(Ef ) a la probabilidad de error en ladecodificación.

En nuestro caso,

)p2(1− p) +

)p3 = 3p2 − 2p3.

2 , ya que2p2 − 3p + 1 = 2(p − 1

2)(p − 1)

Capacidad decanal

Ejemplo

Otro ejemplo

)p2(1− p) +

)p3 = 3p2 − 2p3.

2 , ya que2p2 − 3p + 1 = 2(p − 1

2)(p − 1)

Capacidad decanal

Ejemplo

Otro ejemplo

)p2(1− p) +

)p3 = 3p2 − 2p3.

Pero, P(Ef ) = 3p2 − 2p3 < p ⇐⇒ 2p2 − 3p + 1 > 0,

locual siempre es cierto para 0 < p < 1

2 , ya que2p2 − 3p + 1 = 2(p − 1

2)(p − 1)

Capacidad decanal

Ejemplo

Otro ejemplo

)p2(1− p) +

)p3 = 3p2 − 2p3.

2 , ya que2p2 − 3p + 1 = 2(p − 1

2)(p − 1)

Capacidad decanal

Ejemplo

Otro ejemplo

)p2(1− p) +

)p3 = 3p2 − 2p3.

2 , ya que2p2 − 3p + 1 = 2(p − 1

2)(p − 1)

La regla de decodificación usada ha disminuidoel error en recepción.

Capacidad decanal

Ejemplo

Otro ejemplo

)p2(1− p) +

)p3 = 3p2 − 2p3.

2 , ya que2p2 − 3p + 1 = 2(p − 1

2)(p − 1)

El costo: multiplicar por 3 la longitud del men-saje. . .

Capacidad decanal

Ejemplo

Otro ejemplo

Conjunto de errores

Definición

Dada una regla de decodificación, f : Bn → C, tal quef (z) = y ′, siendo y la palabra–código enviada al canal, elconjunto de errores es

Ef ={(y , z) ∈ C × Bn : f (z) = y ′ 6= y

siendo C ⊆ Bn un (n, M) código q-ario y B el alfabeto del canal.

Transmitida la palabra–código y , la probabilidad de errores

P(Ef |y) =∑

z /∈f−1(y)

P(z |y).

Capacidad decanal

Ejemplo

Otro ejemplo

Conjunto de errores

Definición

Ef ={(y , z) ∈ C × Bn : f (z) = y ′ 6= y

P(Ef |y) =∑

z /∈f−1(y)

P(z |y).

Capacidad decanal

Ejemplo

Otro ejemplo

Conjunto de errores

Definición

Ef ={(y , z) ∈ C × Bn : f (z) = y ′ 6= y

P(Ef |y) =∑

z /∈f−1(y)

P(z |y).

Capacidad decanal

Ejemplo

Otro ejemplo

Probabilidad media de error

Por lo tanto, la probabilidad media de error se puedeescribir de las siguientes formas

P(Ef ) =∑y∈C

P(Ef |y)P(y)

=∑y∈C

∑z /∈f−1(y)

P(z |y)P(y)

(y ,z)∈Ef

P(y , z)

= 1−∑

z∈BnP(f (z), z).

Nótese que la probabilidad media de error depende de ladistribución de la fuente, ya que P(y) = P(C(x)) = P(x) .

Capacidad decanal

Ejemplo

Otro ejemplo

P(Ef ) =∑y∈C

P(Ef |y)P(y)

=∑y∈C

∑z /∈f−1(y)

P(z |y)P(y)

(y ,z)∈Ef

P(y , z)

= 1−∑

z∈BnP(f (z), z).

Capacidad decanal

Ejemplo

Otro ejemplo

P(Ef ) =∑y∈C

P(Ef |y)P(y)

=∑y∈C

∑z /∈f−1(y)

P(z |y)P(y)

(y ,z)∈Ef

P(y , z)

= 1−∑

z∈BnP(f (z), z).

Capacidad decanal

Ejemplo

Otro ejemplo

P(Ef ) =∑y∈C

P(Ef |y)P(y)

=∑y∈C

∑z /∈f−1(y)

P(z |y)P(y)

(y ,z)∈Ef

P(y , z)

= 1−∑

z∈BnP(f (z), z).

Capacidad decanal

Ejemplo

Otro ejemplo

Mínima probabilidad media de errorDecodificación por mínima probabilidad

Definición

Un observador ideal es una regla de decodificación f talque

P(f (z), z) = max{P(y , z) : y ∈ C}, ∀z ∈ Bn.

Proposición

Dado un canal K = (X , Y , T ) y un código C, el mínimo dela probabilidad media de error, para todas las reglas dedecodificación f , se obtiene en un observador ideal.

Capacidad decanal

Ejemplo

Otro ejemplo

Definición

Proposición

Capacidad decanal

Ejemplo

Otro ejemplo

Definición

Proposición

Capacidad decanal

Ejemplo

Otro ejemplo

Probabilidad máxima de error

Definición

La probabilidad máxima de error asociada a una reglade decodificación f se define

Pmax(Ef ) = max{P(Ef |y) : y ∈ C}.

Proposición

Fijada una regla f de decodificación, la Pmax(Ef ) es unacota superior de la probabilidad de error P(Ef ), para todaslas distribuciones X de la fuente F .

Capacidad decanal

Ejemplo

Otro ejemplo

Definición

Proposición

Capacidad decanal

Ejemplo

Otro ejemplo

Definición

Proposición

Capacidad decanal

Ejemplo

Otro ejemplo

Decodificación por máxima verosimilitud

Definición

Una regla de decodificación f es de máximaverosimilitud si

P(z |f (z)) = max{P(z |y) : y ∈ C}, ∀z ∈ Bn.

Proposición

Si la distribución X de la fuente es uniforme coincidenambas reglas de decodificación: la de mínima probabilidadde error (u observador ideal) y la de máxima verosimilitud.

Capacidad decanal

Ejemplo

Otro ejemplo

Definición

Proposición

Capacidad decanal

Ejemplo

Otro ejemplo

Definición

Proposición

Capacidad decanal

Ejemplo

Otro ejemplo

Otro ejemplo: Bits de paridad (I)

Consideramos una fuente F que emite bits según una v.a.X , tal que P(X = 1) = 0′3.El alfabeto fuente es

A = {x0, x1, x2, x3} = {(00), (01), (10), (11)}.

Y el canal es un BSC con p = 0′2.Codificamos añadiendo a cada x i un bit de paridad par. Esfácil ver que

C : F22 → C ⊂ F3

2x = (b1, b2) 7→ y = (b1, b2, b1 + b2).

O lo mismo matricialmente

y = (b1, b2)

(1 0 10 1 1

Capacidad decanal

Ejemplo

Otro ejemplo

Consideramos una fuente F que emite bits según una v.a.X , tal que P(X = 1) = 0′3.

El alfabeto fuente es

A = {x0, x1, x2, x3} = {(00), (01), (10), (11)}.

C : F22 → C ⊂ F3

2x = (b1, b2) 7→ y = (b1, b2, b1 + b2).

y = (b1, b2)

(1 0 10 1 1

Capacidad decanal

Ejemplo

Otro ejemplo

A = {x0, x1, x2, x3} = {(00), (01), (10), (11)}.

Y el canal es un BSC con p = 0′2.

Codificamos añadiendo a cada x i un bit de paridad par. Esfácil ver que

C : F22 → C ⊂ F3

2x = (b1, b2) 7→ y = (b1, b2, b1 + b2).

y = (b1, b2)

(1 0 10 1 1

Capacidad decanal

Ejemplo

Otro ejemplo

A = {x0, x1, x2, x3} = {(00), (01), (10), (11)}.

C : F22 → C ⊂ F3

2x = (b1, b2) 7→ y = (b1, b2, b1 + b2).

y = (b1, b2)

(1 0 10 1 1

Capacidad decanal

Ejemplo

Otro ejemplo

A = {x0, x1, x2, x3} = {(00), (01), (10), (11)}.

C : F22 → C ⊂ F3

2x = (b1, b2) 7→ y = (b1, b2, b1 + b2).

y = (b1, b2)

(1 0 10 1 1

Capacidad decanal

Ejemplo

Otro ejemplo

Bits de paridad (II)

Por lo tanto, C = {(000), (011), (101), (110)}: un (3, 4)código binario.La matriz de transición T z|y = P(z |y) es

(000) (001) (010) (011) (100) (101) (110) (111)(000) 0’512 0’128 0’128 0’032 0’128 0’032 0’032 0’008(011) 0’032 0’128 0’128 0’512 0’008 0’032 0’032 0’128(101) 0’032 0’128 0’008 0’032 0’128 0’512 0’032 0’128(110) 0’032 0’008 0’128 0’032 0’128 0’032 0’512 0’128

La regla de decodificación por máxima verosimilitud, fMV ,decodifica cada z ∈ F3

2 como la y ∈ C con mayorprobabilidad en la columna correspondiente de T z|y :

fMV (000) = (000), fMV (100) = (000),fMV (001) = (000), fMV (101) = (101),fMV (010) = (000), fMV (110) = (110),fMV (011) = (011), fMV (111) = (011).

Capacidad decanal

Ejemplo

Otro ejemplo

Por lo tanto, C = {(000), (011), (101), (110)}: un (3, 4)código binario.

La matriz de transición T z|y = P(z |y) es(000) (001) (010) (011) (100) (101) (110) (111)

(000) 0’512 0’128 0’128 0’032 0’128 0’032 0’032 0’008(011) 0’032 0’128 0’128 0’512 0’008 0’032 0’032 0’128(101) 0’032 0’128 0’008 0’032 0’128 0’512 0’032 0’128(110) 0’032 0’008 0’128 0’032 0’128 0’032 0’512 0’128

Capacidad decanal

Ejemplo

Otro ejemplo

(000) (001) (010) (011) (100) (101) (110) (111)(000) 0’512 0’128 0’128 0’032 0’128 0’032 0’032 0’008(011) 0’032 0’128 0’128 0’512 0’008 0’032 0’032 0’128(101) 0’032 0’128 0’008 0’032 0’128 0’512 0’032 0’128(110) 0’032 0’008 0’128 0’032 0’128 0’032 0’512 0’128

Capacidad decanal

Ejemplo

Otro ejemplo

(000) (001) (010) (011) (100) (101) (110) (111)(000) 0’512 0’128 0’128 0’032 0’128 0’032 0’032 0’008(011) 0’032 0’128 0’128 0’512 0’008 0’032 0’032 0’128(101) 0’032 0’128 0’008 0’032 0’128 0’512 0’032 0’128(110) 0’032 0’008 0’128 0’032 0’128 0’032 0’512 0’128

Capacidad decanal

Ejemplo

Otro ejemplo

(000) (001) (010) (011) (100) (101) (110) (111)(000) 0’512 0’128 0’128 0’032 0’128 0’032 0’032 0’008(011) 0’032 0’128 0’128 0’512 0’008 0’032 0’032 0’128(101) 0’032 0’128 0’008 0’032 0’128 0’512 0’032 0’128(110) 0’032 0’008 0’128 0’032 0’128 0’032 0’512 0’128

Capacidad decanal

Ejemplo

Otro ejemplo

(000) (001) (010) (011) (100) (101) (110) (111)(000) 0’512 0’128 0’128 0’032 0’128 0’032 0’032 0’008(011) 0’032 0’128 0’128 0’512 0’008 0’032 0’032 0’128(101) 0’032 0’128 0’008 0’032 0’128 0’512 0’032 0’128(110) 0’032 0’008 0’128 0’032 0’128 0’032 0’512 0’128

Capacidad decanal

Ejemplo

Otro ejemplo

Bits de paridad (III)

Como (p0, p1, p2, p3) = (0′49, 0′21, 0′21, 0′09), la matriz dela probabilidad conjunta P(y , z) es

(000) (001) (010) (011) (100) (101) (110) (111)(000) 0’251 0’063 0’063 0’016 0’063 0’016 0’016 0’004(011) 0’007 0’027 0’027 0’107 0’002 0’007 0’007 0’027(101) 0’007 0’027 0’002 0’007 0’027 0’107 0’007 0’027(110) 0’003 0’001 0’012 0’003 0’012 0’003 0’046 0’012

La regla de decodificación por mínima probabilidad uobservador ideal, fmP , decodifica cada z ∈ F3

2 como lay ∈ C con mayor probabilidad en la columnacorrespondiente de la matriz P(y , z):

fmP(000) = (000), fmP(100) = (000),fmP(001) = (000), fmP(101) = (101),fmP(010) = (000), fmP(110) = (110),fmP(011) = (011), fmP(111) = (011).

Capacidad decanal

Ejemplo

Otro ejemplo

(000) (001) (010) (011) (100) (101) (110) (111)(000) 0’251 0’063 0’063 0’016 0’063 0’016 0’016 0’004(011) 0’007 0’027 0’027 0’107 0’002 0’007 0’007 0’027(101) 0’007 0’027 0’002 0’007 0’027 0’107 0’007 0’027(110) 0’003 0’001 0’012 0’003 0’012 0’003 0’046 0’012

Capacidad decanal

Ejemplo

Otro ejemplo

(000) (001) (010) (011) (100) (101) (110) (111)(000) 0’251 0’063 0’063 0’016 0’063 0’016 0’016 0’004(011) 0’007 0’027 0’027 0’107 0’002 0’007 0’007 0’027(101) 0’007 0’027 0’002 0’007 0’027 0’107 0’007 0’027(110) 0’003 0’001 0’012 0’003 0’012 0’003 0’046 0’012

Capacidad decanal

Ejemplo

Otro ejemplo

(000) (001) (010) (011) (100) (101) (110) (111)(000) 0’251 0’063 0’063 0’016 0’063 0’016 0’016 0’004(011) 0’007 0’027 0’027 0’107 0’002 0’007 0’007 0’027(101) 0’007 0’027 0’002 0’007 0’027 0’107 0’007 0’027(110) 0’003 0’001 0’012 0’003 0’012 0’003 0’046 0’012

Capacidad decanal

Ejemplo

Otro ejemplo

(000) (001) (010) (011) (100) (101) (110) (111)(000) 0’251 0’063 0’063 0’016 0’063 0’016 0’016 0’004(011) 0’007 0’027 0’027 0’107 0’002 0’007 0’007 0’027(101) 0’007 0’027 0’002 0’007 0’027 0’107 0’007 0’027(110) 0’003 0’001 0’012 0’003 0’012 0’003 0’046 0’012

Capacidad decanal

Ejemplo

Otro ejemplo

Bits de paridad (IV)

Según la matriz de transición T z|y , se trata de un canal simétrico ala entrada pero no a la salida: para calcular su capacidadhabría que ver si existe solución al sistema

(p0, p1, p2, p3)T z|y =

«, siendo pi = P(x i ).

Capacidad decanal

Ejemplo

Otro ejemplo

Según la matriz de transición T z|y , se trata de un canal simétrico ala entrada pero no a la salida:

para calcular su capacidadhabría que ver si existe solución al sistema

(p0, p1, p2, p3)T z|y =

Capacidad decanal

Ejemplo

Otro ejemplo

Según la matriz de transición T z|y , se trata de un canal simétrico ala entrada pero no a la salida: para calcular su capacidadhabría que ver si existe solución al sistema

(p0, p1, p2, p3)T z|y =

Capacidad decanal

Codificación

Índice

2 Codificación

Capacidad decanal

Codificación

NotaciónTasas de información y de redundancia

Definición

Un conjunto C es un (n, M) código q-ario cuando estáformado por M palabras–código de longitud n sobre unalfabeto con q elementos.

Definición

Dado un (n, M) código q-ario C, se llama tasa deinformación o ratio del código a

R(C) =logq M

El valor 1− R(C) es la tasa de redundancia.

Capacidad decanal

Codificación

Definición

R(C) =logq M

Capacidad decanal

Codificación

Definición

R(C) =logq M

Capacidad decanal

Codificación

Segundo teorema de ShannonCCT, Channel Coding Theorem

Teorema (CCT)

Sea K un canal con ruido con capacidad C(K) y seaR ∈ R, tal que 0 < R < C(K). Entonces existe unasucesión (Cn, fn)n∈N de (n, Mn) códigos bloque q-arios y deesquemas de decisión, tales que

1 R ≤ R(Cn) =logq Mn

n .2 lim

n→∞Pmax(Efn) = 0.

Capacidad decanal

Codificación

Segundo teorema de ShannonCCT, Channel Coding Theorem

Teorema (CCT)

Sea K un canal con ruido con capacidad C(K) y seaR ∈ R, tal que 0 < R < C(K). Entonces existe unasucesión (Cn, fn)n∈N de (n, Mn) códigos bloque q-arios y deesquemas de decisión, tales que

1 R ≤ R(Cn) =logq Mn

n .2 lim

Capacidad decanal

Codificación

Teorema recíproco del CCT

Teorema (Recíproco del CCT)

Sea K un canal con ruido con capacidad C(K). Sea(Cn, fn)n∈N una sucesión de (n, Mn) códigos bloque q-ariosy de esquemas de decisión. Si la tasa de información esR(Cn) > C(K), ∀n, entonces lim

Capacidad decanal

Codificación

Teorema recíproco del CCT

Teorema (Recíproco del CCT)

Sea K un canal con ruido con capacidad C(K). Sea(Cn, fn)n∈N una sucesión de (n, Mn) códigos bloque q-ariosy de esquemas de decisión. Si la tasa de información esR(Cn) > C(K), ∀n, entonces lim

capacidad de canal - udl...

Documents