Ejercicio 1

En un instituto se han formado, en igual número, equipos de fútbol (11 jugadores) y de balonmano (7 jugadores).

1. Suponga que se sabe que, en un equipo elegido al azar, no hay dos alumnos que hayan nacido el mismo día de la semana. ¿Cuánta incertidumbre existe acerca del deporte que practica el equipo? Considere que el año tiene 52 semanas exactas.
2. Ídem si se sabe que en el equipo sí hay alumnos nacidos el mismo día.

Solución

1. Ninguna. En el equipo de fútbol necesariamente debe haber jugadores que hayan nacido el mismo día de la semana.
2. Sea E el evento “alumnos nacidos el mismo día de la semana” y sea X el tipo de equipo. Entonces
   Se calcula fácilmente que

Ejercicio 2

Suponga que el alfabeto de una fuente discreta sin memoria está formado por las 27 entradas del diccionario. Suponga que es uniforme la función de masa de probabilidad de dicha fuente y que se codifican los símbolos de la fuente uno a uno.

1. Determine la eficiencia de un codificador compacto binario.
2. Determine la eficiencia de un codificador compacto ternario.

Solución

1. Un codificador compacto binario de una fuente uniforme produce palabras cuyas longitudes difieren a lo sumo una unidad (véase prob. 10 del boletín 2); en este caso, 5 palabras de longitud 4 y 22 palabras de longitud 5. Por tanto, la longitud del código es
   L = 4 × 5/27 + 5 × 22/27 ≈ 4,81.
   y la eficiencia vale η = H₂(X) / L ≈ 98,7%.
   Observe que no es necesario construir el árbol de codificación Huffman.
2. La eficiencia es 1 puesto que las probabilidades de los símbolos de la fuente son potencias enteras de 3 (el número de elementos del alfabeto de codificación).

Ejercicio 3

¿Cuál es el tamaño del alfabeto de una fuente que genera todos los símbolos equiprobablemente si, para transmitir fiablemente sus mensajes a través de un canal ideal de capacidad 3 bits, el régimen de generación de símbolos no puede exceder el régimen de transmisión del canal?

Solución

Simplemente ha de cumplirse log₂ n ≤ 3. Luego n ≤ 8.

Ejercicio 4

Sea C el código binario definido por la matriz de comprobación de paridad

1. Determine, razonadamente, la longitud, dimensión y distancia de C.
2. Escriba una matriz generadora de C.
3. ¿Cuál es el mayor entero t tal que el código es capaz de corregir cualquier patrón con hasta t errores?
4. ¿Cómo se decodificaría el vector recibido 101010101?

Solución

1. Se trata de un código [9, 3, 3]. H_{6 × 9} tiene todas sus filas linealmente independientes. Es, en realidad, el código de repetición (xxx, yyy, zzz) x, y, z ∈ {0, 1} de donde se sigue fácilmente que la distancia es 3.
2. Por ejemplo
3. t = 1. El código es corrector de errores simples.
4. La palabra del código más cercana es 111000111, que posee un símbolo distinto del vector recibido en cada terna de bits. No existe otra a distancia menor y es la única a distancia 3, por lo que sería la salida del decodificador.

Ejercicio 5

Considere el código binario de paridad simple (n, n-1) en el que la redundancia es tal que el número de símbolos no nulos de todas las palabras del código es par.

1. Demuestre que es cíclico y obtenga su polinomio generador.
2. Calcule la probabilidad de que no se detecte un error cuando se transmite sobre un canal binario simétrico sin memoria.

Solución

1. En primer lugar, veamos que el código es lineal, lo que es cierto porque este código consta de todos los vectores de n bits y peso par, que contiene el vector nulo y es un conjunto cerrado para la suma. Para ver que es cíclico, es suficiente con notar que la rotación cíclica de cualquiera de las palabras del código preserva su peso (par) y da como resultado otra palabra del código. El polinomio generador es x + 1.
2. La probabilidad de no detectar un error es:
   siendo A_2i = (ⁿ_2i) el número de palabras del código de peso 2i.

Ejercicio 6

Considere un enlace de las siguientes características: C = 1 Mbits/s, tasa de error de bit ε = 5 ·10^-6 y tiempo de asentimiento despreciable. Si se usa un protocolo ARQ de parada y espera con m = 100, ¿para qué rango de valores de n no supera la cadencia eficaz los 500 Kbits/s?

Solución

Conocida la forma de variación de la cadencia eficaz (o de la eficiencia) del protocolo con n, el problema plantea una cuestión geométrica simple: se trata de determinar las soluciones, si las hay, de la ecuación (1 – k(n + m))(n/n + m)=1/2
Si la ecuación no tiene solución real o hay una sola, entonces para ningún valor de n supera la cadencia eficaz los 500 Kbits/s.
Pero si la ecuación tiene dos soluciones reales distintas, como es el caso:
n₁ ≈ 100,5 y n₂ ≈ 99799,5, entonces la cadencia eficaz no supera los 500 Kbits/s para
{n : n ≤ 100 o n ≥ 99800}.

Etiquetas: canal, Codificación, Ejercicios, Protocolo ARQ, Teoría de la Información