8.7: Ejercicios

1

¿Por qué no es aceptable el siguiente esquema de codificación?

Información	\(0\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)
Palabra de código	\(000\)	\(001\)	\(010\)	\(011\)	\(101\)	\(110\)	\(111\)	\(000\)	\(001\)

2

Sin hacer ninguna adición, explique por qué el siguiente conjunto de\(4\) -tuplas en\({\mathbb Z}_2^4\) no puede ser un código de grupo.

\[ (0110) \quad (1001) \quad (1010) \quad (1100) \nonumber \]

3

Compute las distancias de Hamming entre los siguientes pares de\(n\) -tuplas.

1. \(\displaystyle (011010), (011100)\)
2. \(\displaystyle (11110101), (01010100)\)
3. \(\displaystyle (00110), (01111)\)
4. \(\displaystyle (1001), (0111)\)

4

Compute los pesos de las siguientes\(n\) -tuplas.

1. \(\displaystyle (011010)\)
2. \(\displaystyle (11110101)\)
3. \(\displaystyle (01111)\)
4. \(\displaystyle (1011)\)

5

Supongamos que un código lineal\(C\) tiene un peso mínimo de\(7\text{.}\) ¿Cuáles son las capacidades de detección y corrección de errores de\(C\text{?}\)

6

En cada uno de los siguientes códigos, ¿cuál es la distancia mínima para el código? ¿Cuál es la mejor situación que podríamos esperar en relación con la detección y corrección de errores?

1. \(\displaystyle (011010) \; (011100) \; (110111) \; (110000)\)
2. \(\displaystyle (011100) \; (011011) \; (111011) \; (100011) \\ (000000) \; (010101) \; (110100) \; (110011)\)
3. \(\displaystyle (000000) \; (011100) \; (110101) \; (110001)\)
4. \(\displaystyle (0110110) \; (0111100) \; (1110000) \; (1111111) \\ (1001001) \; (1000011) \; (0001111) \; (0000000)\)

7

Compute el espacio nulo de cada una de las siguientes matrices. ¿Qué tipo de códigos\((n,k)\) -block son los espacios nulos? ¿Se puede encontrar una matriz (no necesariamente una matriz generadora estándar) que genere cada código? ¿Tus matrices generadoras son únicas?

1. \[ \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix} \nonumber \]
2. \[ \begin{pmatrix} 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} \nonumber \]
3. \[ \begin{pmatrix} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix} \nonumber \]
4. \[ \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \end{pmatrix} \nonumber \]

8

Construye un código\((5,2)\) -block. Discuta tanto las capacidades de detección de errores como de corrección de errores de su código.

9

Dejar\(C\) ser el código obtenido del espacio nulo de la matriz

\[ H = \begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{pmatrix}\text{.} \nonumber \]

Decodificar el mensaje

\[ 01111 \quad 10101 \quad 01110 \quad 00011 \nonumber \]

si es posible.

10

Supongamos que se transmite un mensaje binario de\(1000\) -bit. Supongamos que la probabilidad de un solo error es\(p\) y que los errores que ocurren en diferentes bits son independientes entre sí. Si\(p = 0.01\text{,}\) ¿cuál es la probabilidad de que ocurra más de un error? ¿Cuál es la probabilidad de que ocurran exactamente dos errores? Repita este problema para\(p = 0.0001\text{.}\)

11

¿Qué matrices son matrices canónicas de comprobación de paridad? Para aquellas matrices que son matrices canónicas de comprobación de paridad, ¿cuáles son las matrices generadoras estándar correspondientes? ¿Cuáles son las capacidades de detección y corrección de errores del código generado por cada una de estas matrices?

1. \[ \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \end{pmatrix} \nonumber \]
2. \[ \begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} \nonumber \]
3. \[ \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix} \nonumber \]
4. \[ \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} \nonumber \]

12

Enumerar todos los síndromes posibles para los códigos generados por cada una de las matrices en Ejercicio\(8.6.11\).

13

Let

\[ H = \begin{pmatrix} 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \end{pmatrix}\text{.} \nonumber \]

Computar el síndrome causado por cada uno de los siguientes errores de transmisión.

1. Un error en el primer bit.
2. Un error en el tercer bit.
3. Un error en el último bit.
4. Errores en el tercer y cuarto bits.

14

Dejar\(C\) ser el código de grupo en\({\mathbb Z}_2^3\) definido por las palabras de código\((000)\) y\((111)\text{.}\) Calcular los cosets de\(C\) en\({\mathbb Z}_2^3\text{.}\) ¿Por qué no hubo necesidad de especificar cosets derecho o izquierdo? Dar el único error de transmisión, en su caso, al que corresponde cada coset.

15

Para cada una de las siguientes matrices, encuentra los coconjuntos del código correspondiente\(C\text{.}\) Dar una tabla de decodificación para cada código si es posible.

1. \[ \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix} \nonumber \]
2. \[ \begin{pmatrix} 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix} \nonumber \]
3. \[ \begin{pmatrix} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix} \nonumber \]
4. \[ \begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \end{pmatrix} \nonumber \]

16

Dejar\({\mathbf x}\text{,}\)\({\mathbf y}\text{,}\) y\({\mathbf z}\) ser binarios\(n\) -tuplas. Demostrar cada una de las siguientes declaraciones.

1. \(\displaystyle w({\mathbf x}) = d( {\mathbf x}, {\mathbf 0})\)
2. \(\displaystyle d( {\mathbf x}, {\mathbf y}) = d( {\mathbf x} + {\mathbf z}, {\mathbf y} + {\mathbf z} )\)
3. \(\displaystyle d({\mathbf x}, {\mathbf y}) = w({\mathbf x}- {\mathbf y})\)

17

Una métrica en un conjunto\(X\) es un mapa\(d: X \times X \rightarrow {\mathbb R}\) que cumple las siguientes condiciones.

1. \(d( {\mathbf x}, {\mathbf y}) \geq 0\)para todos\({\mathbf x}, {\mathbf y} \in X\text{;}\)
2. \(d( {\mathbf x}, {\mathbf y}) = 0\)exactamente cuando\({\mathbf x} = {\mathbf y}\text{;}\)
3. \(d( {\mathbf x}, {\mathbf y})= d( {\mathbf y}, {\mathbf x})\text{;}\)
4. \(d( {\mathbf x}, {\mathbf y}) \leq d( {\mathbf x}, {\mathbf z}) + d( {\mathbf z}, {\mathbf y})\text{.}\)

En otras palabras, una métrica es simplemente una generalización de la noción de distancia. Demuestre que la distancia de Hamming es una métrica en\({\mathbb Z}_2^n\text{.}\) Decodificar un mensaje en realidad se reduce a decidir cuál es la palabra de código más cercana en términos de distancia.

18

Dejar\(C\) ser un código lineal. Demuestre que o bien las coordenadas\(i\) th en las palabras clave de\(C\) son todas ceros o exactamente la mitad de ellas son ceros.

19

Dejar\(C\) ser un código lineal. Demuestre que o cada palabra de código tiene un peso par o exactamente la mitad de las palabras clave tienen un peso par.

20

Mostrar que las palabras de código de peso par en un código lineal también\(C\) son un código lineal.

21

Si vamos a usar un código lineal corrector de errores para transmitir los 128 caracteres ASCII, ¿qué tamaño de matriz se debe usar? ¿Qué matriz de tamaño se debe utilizar para transmitir el conjunto de caracteres ASCII extendido de 256 caracteres? ¿Y si solo requerimos detección de errores en ambos casos?

22

Encuentre la matriz canónica de verificación de paridad que proporciona el código de bits de verificación de paridad par con tres posiciones de información. ¿Cuál es la matriz para siete puestos de información? ¿Cuáles son las matrices generadoras estándar correspondientes?

23

¿Cuántas posiciones de verificación se necesitan para un solo código de corrección de errores con 20 posiciones de información? ¿Con 32 puestos de información?

24

\({\mathbf e}_i\)Sea la\(n\) -tuple binaria con a\(1\) en la coordenada\(i\) th y\(0\)'s en otra parte y supongamos que\(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\) Mostrar que\(H{\mathbf e}_i\) es la columna\(i\) th de la matriz\(H\text{.}\)

25

Dejar\(C\) ser un código\((n,k)\) -lineal. Definir el código dual u ortogonal\(C\) de ser

\[ C^\perp = \{ {\mathbf x} \in {\mathbb Z}_2^n : {\mathbf x} \cdot {\mathbf y} = 0 \text{ for all } {\mathbf y} \in C \}\text{.} \nonumber \]

1. Encuentra el código dual del código lineal\(C\) donde\(C\) está dado por la matriz

   \[ \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix}\text{.} \nonumber \]

2. Mostrar que\(C^\perp\) es un código\((n, n-k)\) -lineal.
3. Encuentre el generador estándar y las matrices de comprobación de paridad de\(C\) y\(C^\perp\text{.}\) ¿Qué sucede en general? Demuestra tu conjetura.

26

Dejar\(H\) ser una\(m \times n\) matriz sobre\({\mathbb Z}_2\text{,}\) donde la columna\(i\) th es el número\(i\) escrito en binario con\(m\) bits. El espacio nulo de tal matriz se llama código Hamming.

1. Demostrar que la matriz

   \[ H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \end{pmatrix} \nonumber \]

   genera un código Hamming. ¿Cuáles son las propiedades correctores de errores de un código de Hamming?

2. La columna correspondiente al síndrome también marca el bit que estaba en error; es decir, la columna\(i\) th de la matriz se\(i\) escribe como un número binario, y el síndrome inmediatamente nos dice qué bit está en error. Si la palabra recibida es\((101011)\text{,}\) computar el síndrome. ¿En qué bit ocurrió el error en este caso y qué palabra de código se transmitió originalmente?
3. Dar una matriz binaria\(H\) para el código Hamming con seis posiciones de información y cuatro posiciones de verificación. ¿Cuáles son las posiciones de verificación y cuáles son las posiciones de información? Codificar los mensajes\((101101)\) y\((001001)\text{.}\) Decodificar las palabras recibidas\((0010000101)\) y\((0000101100)\text{.}\) ¿Cuáles son los posibles síndromes para este código?
4. ¿Cuál es el número de bits de verificación y el número de bits de información en un código Hamming\((m,n)\) -block? Dar tanto un límite superior como un límite inferior en el número de bits de información en términos del número de bits de verificación. Los códigos Hamming que tienen el número máximo posible de bits de información con bits de\(k\) verificación se denominan perfectos. Todo síndrome posible excepto\({\mathbf 0}\) ocurre como columna. Si el número de bits de información es menor que el máximo, entonces el código se llama acortado. En este caso, dar un ejemplo que muestre que algunos síndromes pueden representar múltiples errores.