• Categories
• Integral
• Probabilidad
• Modulación
• Información
• Electrónica

Citation preview

Problemas 1 | PROBLEMAS Entropía 9.1 Sea p la probabilidad de cierto evento. Grafique la cantidad de información ganada por la ocurrencia de este evento para 0 < p < 1. 9.2

Una fuente emite uno de cuatro posibles símbolos durante cada intervalo de transmisión de señales. Los símbolos ocurren con las probabilidades:

Po = °-4 Pi = 0-3 Pi

9.3 9.4 9.5

= O-2 P3 = o.i Determine la cantidad de información ganada al observar la fuente que emite cada uno de estos símbolos. Una fuente emite uno de cuatro símbolos s0, Sj, s2 y s3 con probabilidades 1/3, 1/6, 1/4 y 1/4, respectivamente. Los símbolos sucesivos emitidos por la fuente son estadísticamente independientes. Calcule la entropía de la fuente. Considere que X representa el resultado de un solo lanzamiento de un dado sin alterar. ¿Cuál es la entropía de X? La función de muestreo de un proceso gaussiano de media cero y varianza unitaria se muestrea de manera uniforme y luego se aplica a un cuantizador uniforme que tiene la característica de amplitud de entrada-salida que se muestra en la figura P9.5. Calcule la entropía de la salida del cuantizador. Salida 1.5 0.5 ■ Entrada -0.5 -1.5

FIGURA P9.5

9.6

Considere una fuente discreta sin memoria con alfabeto de fuente 3 = {s0, st, ..., sK1} y estadísticas de fuente {p0, p¡t ..., p^}. La n-ésima extensión de esta fuente es otra fuente discreta sin memoria con alfabeto de fuente 3" = {o Q, Oj, ..., Om_[}> donde M = Kn. Considere que P(g) denota la probabilidad de o.. a) Demuestre que ivi—i

que es lo que se esperaba, b) Demuestre que £p(°,)i°g2

f\i p‘i v*/

donde p¡ es la probabilidad del símbolo s , y H(3) V es la entropía de la fuente original, c) Por tanto, demuestre que M-l . H(^) = YP(o,)iog2—!— K2P(o,) = n H{3)

2 CAPÍTULO 9 « LÍMITES FUNDAMENTALES EN LA TEORÍA DE LA INFORMACIÓN

9.7

Considere una fuente discreta sin memoria con alfabeto de fuente SH= {s0, s2} y estadísticas de fuente {0.7, 0.15, 0.15}.

a) Calcule la entropía de la fuente. b) Calcule la entropía de la extensión de segundo orden de la fuente. 9.8

Posiblemente sea una sorpresa, pero el número de bits necesario para almacenar texto es mucho menor que el requerido para almacenar su equivalente hablado. ¿Puede usted explicar la razón de ello?

Compactación de datos 9.9

Considere una fuente discreta sin memoria cuyo alfabeto consiste en K símbolos igualmente probables. a) Explique por qué el uso de un código de longitud fija para la representación de una fuente de este tipo es aproximadamente tan eficiente como puede serlo cualquier código.

b) ¿Qué condiciones tiene que satisfacer K y la longitud de palabra de código para que la eficiencia de la codificación sea de 100%? 9.10 Considere los cuatro códigos listados a continuación: Símbolo s

o

S

3

S

4

Código I

Código II

Código III

Código IV

0

0

0

00

10 110 1110 1111

01 001 0010 0011

01 011 110 111

01 10 110 111

a) Dos de estos cuatro son códigos de prefijo. Identifíquelos y construya sus árboles de decisión individuales.

b) Aplique la desigualdad de Kraft-McMillan a los códigos I, II, III y IV. Discuta sus resultados a la luz de los que se obtuvieron en la parte a. 9.11 Considere una secuencia de letras del alfabeto inglés con sus probabilidades de ocurrencia como en las dadas a continuación: Letra a i l Probabilidad 0.1 0.1 0.2 0.1 0.1 0.2 0.1 0.1

m

m

o

p

y

Calcule los diferentes códigos de Huffman para este alfabeto. En un caso, mueva un símbolo combinado en el procedimiento de codificación tan alto como sea posible, y en el segundo caso, muévalo lo más bajo posible. Por tanto, para cada uno de los dos códigos determine la longitud promedio de palabra de código y la varianza de esta misma longitud con respecto al conjunto de letras. 9.12 Una fuente discreta sin memoria tiene un alfabeto de siete símbolos cuyas probabilidades de ocu- rrencia se describen a continuación: Símbolo s0 Sj s2 s3 Probabilidad 0.25 0.25 0.125 0.125 0.125 0.0625 0.0625

s4

s5

s6

Calcule el código de Huffman para esta fuente, moviendo un “símbolo combinado” tan alto como sea posible. Explique por qué el código fuente calculado tiene una eficiencia del 100%. 9.13 Considere una fuente discreta sin memoria con alfabeto {s0, Sj, s2} y estadísticas {0.7, 0.15, 0.15} para su salida. a) Aplique el algoritmo de Huffman para esta fuente. Por lo tanto, demuestre que la longitud promedio del código de Huffman es igual a 1.3 bits/símbolo. b) Deje que la fuente se extienda hasta el orden dos. Aplique el algoritmo de Huffman a la fuente extendida resultante y demuestre que la longitud promedio del nuevo código es igual a 1.1975 bits/símbolo.

Problemas 3 c) Compare la longitud promedio de palabra de código calculada en la parte b con la entropía de la fuente original. 9.14

La figura P9.14 muestra un árbol de Hufftnan. ¿Cuál es la palabra de código para cada uno de los símbolos A, B, C, D, E, F y G representada por este árbol de Huffman? ¿Cuáles son sus longitudes de palabra de código individuales?

3/8

1

9.15

Una computadora ejecuta cuatro instrucciones que se designan mediante las palabras de código (00, 01, 10, 11). Suponiendo que las instrucciones se usan independientemente con las probabilida- des (1/2, 1/8, 1/8, 1/4), calcule el porcentaje mediante el cual el número de bits utilizados para las instrucciones puede reducirse mediante el uso de un código de fuente óptimo. Construya un código de Huffman para realizar la reducción.

9.16

Considere la siguiente secuencia binaria

11101001100010110100. .. Utilice el algoritmo de Lempel-Ziv para codificar esta secuencia. Suponga que los símbolos binarios 0 y 1 se encuentran ya en el registro de código.

Canal simétrico binario 9.17

Considere el diagrama de probabilidad de transición del canal simétrico binario que se muestra en la figura 9.8. Los símbolos binarios de entrada 0 y 1 ocurren con igual probabilidad. Determine las probabilidades de los símbolos binarios 0 y 1 que aparecen a la salida del canal.

9.18

Repita el cálculo del problema 9.17 suponiendo que los símbolos de entrada 0 y 1 ocurren con probabilidades 1/4 y 3/4, respectivamente.

Información mutua y capacidad del canal 9.19

Considere un canal simétrico binario caracterizado por la probabilidad de transición p. Grafique la información mutua del canal como una función de pv la probabilidad a priori del símbolo 1 a la entrada del canal; realice sus cálculos para la probabilidad de transición p = 0, 0.1, 0.2, 0.3, 0.5.

4 CAPÍTULO 9 « LÍMITES FUNDAMENTALES EN LA TEORÍA DE LA INFORMACIÓN

9.20 9.21

La figura 9.10 describe la variación de la capacidad de canal de un canal simétrico binario con la probabilidad de transición p. Recurra a los resultados del problema 9.19 para explicar esta variación. Considere el canal simétrico binario descrito en la figura 9.8. Sea p0 la probabilidad de enviar el símbolo binario x0 = 0, y sea p¡ = 1 — pg la probabilidad de enviar el símbolo binario x = 1, Considere que p denota la probabilidad de transición del canal. a) Demuestre que la información mutua entre la entrada y la salida del canal está dada por !(&■,&) = &(z)-¿0(ti)

donde 1

H(z) = ?:log2| - |+(l-z) log

v1-*/

z = pop + ( l - p o ) ( l - p )

H ( p ) = p log2

+ (l-p) log¡

l-p

b) Demuestre que el valor de p0 que hace máxima a 1(¿0, W) es igual a 1/2. c) Por tanto, compruebe que la capacidad del canal es igual a C = l-H(p) 9.22

Dos canales simétricos binarios se conectan en cascada, en la forma que se indica en la figura P9.22. Determine la capacidad total del canal de la conexión en cascada, suponiendo que ambos canales tienen el mismo diagrama de probabilidad de transición que se muestra en la figura 9.8.

FIGURA P9.22

9.23

El canal de borradura binaria tiene dos entradas y tres salidas, como se describe en la figura P9.23. Las entradas se marcan con 0 y 1, y las salidas con 0, 1 y e. Una fracción a de los bits entrantes se borra por medio del canal. Determine la capacidad de este mismo.

1-a

FIGURA P9.23

Problemas 5

6 CAPÍTULO 9 « LÍMITES FUNDAMENTALES EN LA TEORÍA DE LA INFORMACIÓN

9.24

Considere un sistema de comunicación digital que utiliza un código de repetición para la codificación/ decodificación del canal. En particular, cada transmisión se repite n veces, donde n = 2m + 1 es un entero impar. El decodificador opera del modo siguiente. Si en un bloque de n bits recibido, el número de ceros supera al número de unos, el decodificador decide a favor de un 0. En otro caso, lo hace a favor de un 1. Ocurre un error cuando m + 1 o más transmisiones fuera de n = 2m + 1 son incorrectas. Suponga un canal simétrico binario. a) Para n = 3, demuestre que la probabilidad promedio de error está dada por

Pe~ 3f>2 (1 — f>) + f>3 donde p es la probabilidad de transición del canal. b) Para n = 5, demuestre que la probabilidad promedio de error está dada por Pe = 10p3(l-p)2+5p4(l-i>) + f>s

c) Por tanto, para el caso general, deduzca que la probabilidad promedio de error se determina mediante

l(?)

_ p'(i-py ¿=m+l

Entropía diferencial 9.25

Sean Xp X2 ......... Xn los elementos de un vector gaussiano X. Las X son independientes con media ¡i. y varianza C52., i = 1, 2, ..., n. Demuestre que la entropía diferencial del vector X es igual a h(X) = ylog2[27Ce(oJo^. . . CJ2)1/n] ¿A qué se reduce h(X) si las varianzas son iguales?

9.26

Una variable aleatoria continua X está restringida a una magnitud pico M; es decir, —M < X < M.

a) Compruebe que la entropía diferencial de X es un máximo cuando ésta se distribuye uniformemente, según se indica mediante , , , Í1/2M, - M < x < M fx (^0 — ] [0, en otro caso

b) Demuestre que la entropía diferencial máxima de X es log2 2M. 9.27

Pruebe las propiedades dadas en las ecuaciones de la (9.79) a la (9.81) para la información mutua KX;Y).

9.28

Considere la variable aleatoria continua Y definida por Y=X+N donde X y N son independientes estadísticamente. Demuestre que la entropía diferencial condicional de Y, dada X, es igual a h(Y|X) = h ( N ) donde h(N) es la entropía diferencial de N.

Capacidad de información 9.29

Un canal de calidad de voz de la red telefónica tiene un ancho de banda de 3.4 kHz.

a) Calcule la capacidad de información del canal telefónico para una relación señal a ruido de 30 dB. b) Calcule la relación señal a ruido mínima que se requiere para soportar la transmisión de información a través del canal telefónico a una tasa de 9,600 b/s.

7 CAPÍTULO 9 « LÍMITES FUNDAMENTALES EN LA TEORÍA DE LA INFORMACIÓN

9.30

9.31

9.32

9.33

Se alimentan datos alfanuméricos a una computadora desde una terminal remota a través de un canal telefónico de calidad de voz. El canal tiene un ancho de banda de 3.4 kHz y una relación de señal de salida a ruido de 20 dB. La terminal tiene un total de 128 símbolos. Suponga que éstos son igualmente probables y que las transmisiones sucesivas son estadísticamente independientes. a) Calcule la capacidad de información del canal. b) Calcule la velocidad de símbolos máxima para la cual es posible la transmisión sin errores por el canal. Una imagen de televisión en blanco y negro puede considerarse como si estuviera compuesta de aproximadamente 3 x 105 elementos, cada uno de los cuales quizás ocupe uno de diez distintos niveles de brillantez con igual probabilidad. Suponga que: 1) la velocidad de transmisiones es de 30 cuadros de imagen por segundo, y 2) que la relación de señal a ruido corresponde a 30 dB. Empleando el teorema de la capacidad de información, calcule el ancho de banda mínimo que se requiere para soportar la transmisión de la señal de video resultante. Nota: como una cuestión de interés, las transmisiones de televisión comercial emplean en realidad un ancho de banda de 4.2 MHz, el cual encaja dentro del ancho de banda asignado de 6 MHz. En este problema continuamos con el ejemplo 9.9. Suponga que la constelación estrechamente empaquetada de la figura 9.15b se escala hacia arriba de manera que la energía de la señal transmitida por símbolo se mantiene en el mismo valor promedio que la consumida por la constelación cuadrada QAM 64 de la figura 9.15a. Construya la nueva constelación que se produce a partir de este escalamiento. ¿Cómo se compara la tasa de error de bits de esta nueva constelación con la de la figura 9.15a? Justifique su respuesta. La respuesta en magnitud al cuadrado de un canal de par trenzado puede modelarse como |H(/)f = exp (-ajf)

La constante a está definida por

donde k es una constante que depende del calibre del alambre, í es una longitud de la línea de referencia y I es la longitud real del par trenzado bajo estudio. La respuesta en magnitud al cuadrado del acoplamiento responsable de la NEXT tiene la forma |Hnext(/)| = P/3/2 donde

(i es una

constante que depende del tipo de cable utilizado. Formule la expresión para la capacidad de información del canal dominado por la NEXT descrito aquí.

Compresión de datos 9.34

9.35

La ecuación (9.138) para la relación señal a ruido (SNR) de un cuantizador vectorial incluye la fórmula SNR de la ecuación (3.33) para la modulación por codificación de pulsos estándar como un caso especial para el cual k = 1. Justifique la validez de esta inclusión. Todos los esquemas prácticos de compresión y transmisión de datos se ubican entre dos límites impuestos por la función de distorsión de velocidad y el teorema de capacidad del canal. Ambos teoremas incluyen la noción de información mutua, aunque de manera diferente. Comente acerca de los aspectos que surgen a partir de estos dos enunciados.

Experimento de computadora 9.36

En este problema volvemos al ejemplo 9.12, el cual tiene que ver con la transmisión de señales antípodas binarias codificadas por un canal con ruido blanco gaussiano aditivo (AWGN). Empezando con la ecuación (9.112) y con la teoría subyacente, desarrolle un paquete de software para calcular el mínimo Eb/N0 requerido para una tasa de error de bits determinada, donde Eb es la energía de

yacen bajo la curva g(}'). FIGURA P9.36

la señal por bit y N0/2 es la densidad espectral del ruido. Por lo tanto, calcule los resultados que se grafican en las partes a y b de la figura 9.18. Como se menciona en el ejemplo 9.12, el cálculo de la información mutua entre la entrada y la salida del canal se aproxima adecuadamente utilizando integración de Monte Cario. Para explicar cómo funciona este método, considere una función g ( y ) que es difícil de muestrear aleatoriamente, lo cual es en realidad el caso en el problema presente. (En nuestro problema, la función g ( y ) repre- senta el integrando complicado en la fórmula correspondiente a la entropía diferencial de la salida del canal.) Para el cálculo, proceda de la siguiente manera: ► Encuentre el área A que incluye la región de interés y que se muestrea con facilidad. > Elija N puntos uniformemente al azar dentro del área A. En ese caso el teorema de integración de Monte Cario establece que la función integral g ( y ) con respecto a y es aproximadamente igual al área A multiplicada por la fracción de puntos que residen debajo de la curva g, como se ilustra en la figura P9.36. La exactitud de la aproximación mejora al crecer N.

CAPÍTULO 1

CODIFICACIÓN DE CONTROL DE ERRORES Este capítulo es la secuencia natural del anterior sobre la teoría de la información de Shannon. En particular, en él se presentan técnicas de codificación de control de errores que ofrecen maneras diferentes de poner en práctica el teorema de codificación del canal de Shannon. Cada técnica de control de errores implica el uso de un codificador de canal en el transmisor y de un algoritmo de decodificación en el receptor. Las técnicas de codificación de control de errores que se describen aquí incluyen las siguientes clases de códigos importantes: ^ Códigos de bloque lineales. ^ Códigos cíclicos. ^ Códigos convolucionales. ^ Códigos compuestos ejemplificados por códigos turbo y códigos de verificación de paridad de baja densidad, y sus variantes irregulares.

8

| 10.1 Introducción

Problemas 9

La tarea que encara el diseñador de un sistema digital de comunicaciones es proveer una instalación al costo más conveniente para transmitir información desde un extremo del sistema a una velocidad y nivel de confiabilidad y calidad aceptables para el usuario en el otro extremo. Los dos parámetros principales del sistema con que cuenta el diseñador son la potencia de la señal transmitida y el ancho de banda del canal. Estos dos parámetros, junto con la densidad espectral de potencia del ruido del receptor, establecen la razón entre la energía de la señal por bit y la densidad espectral de potencia del ruido Eh/NQ. En el capítulo 6 mostramos que esta proporción determina singularmente la tasa de error de bits en un esquema de modulación particular. Las consideraciones prácticas suelen poner un límite en el valor que podemos asignar a Eh/N0. De acuerdo con esto, en la práctica llegamos con frecuencia a un esquema de modulación y descubrimos que no es posible proporcionar una calidad de datos aceptable (es decir, un desempeño de errores suficientemente bajo). Para un Eh/NQ fijo, la única opción práctica disponible para cambiar la calidad de los datos de problemática a aceptable consiste en utilizar la codificación de control de errores. Otra motivación práctica para el empleo de la codificación radica en reducir la proporción EbfN0 requerida para una tasa de error de bits fija. Esta reducción en EbfNQ puede, a su vez, explotarse para reducir la potencia transmitida necesaria o reducir los costos de hardware requiriendo un tamaño de antena más pequeño en el caso de comunicaciones de radio. El control de errores1 para la integridad de datos puede efectuarse por medio de la corrección de errores directa (FEC). La figura 10.1a muestra el modelo de un sistema de comunicación digital que utiliza un procedimiento de este tipo. La fuente discreta genera información en la forma de símbolos binarios. El codificador de canal en el transmisor acepta los bits del mensaje y agrega redundancia de acuerdo con una regla preestablecida, produciendo de ese modo datos