Algebra AbstractaTeoría y Aplicaciones

1

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

2

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

3

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

1. \((011010), (011100)\)

2. \((11110101), (01010100)\)

3. \((00110), (01111)\)

4. \((1001), (0111)\)

4

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

1. \((011010)\)

2. \((11110101)\)

3. \((01111)\)

4. \((1011)\)

5

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

6

Para cada uno de los siguientes códigos, ¿cuál es la distancias mínima del código? ¿Cuál es la mejor situación que podemos esperar en relación a detección y corrección de errores?

1. \((011010) \; (011100) \; (110111) \; (110000)\)

2. \((011100) \; (011011) \; (111011) \; (100011)\) \; \((000000) \; (010101) \; (110100) \; (110011)\)

3. \((000000) \; (011100) \; (110101) \; (110001)\)

4. \((0110110) \; (0111100) \; (1110000) \; (1111111)\) \; \((1001001) \; (1000011) \; (0001111) \; (0000000)\)

7

Calcule el espacio nulo de cada una de las siguientes matrices. ¿Qué tipo de códigos de bloque \((n,k)\) son los espacios nulos? ¿Puede encontrar una matriz (no necesariamente una matriz generadora estándar) que genere cada código? ¿Son únicas sus matrices generadoras?

1. \begin{equation*} \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix} \end{equation*}

2. \begin{equation*} \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} \end{equation*}

3. \begin{equation*} \begin{pmatrix} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix} \end{equation*}

4. \begin{equation*} \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} \end{equation*}

8

Construya un código de bloque \((5,2)\text{.}\) Discuta las capacidades de detección y corrección de errores de su código.

9

Sea \(C\) el código obtenido como espacio nulo de la matriz

Decodifique el mensaje

si es posible.

10

Supongamos que se transmite un mensaje binario de 1000 bits, que la probabilidad de error en un bit es \(p\) y que los errores que puedan ocurrir en bits diferentes son independientes entre ellos. 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 el problema para \(p = 0.0001\text{.}\)

11

¿Qué matrices son matrices verificadoras canónicas? Para aquella matrices que sean matrices verificadoras canónicas, ¿cuáles son las correspondientes matrices generadoras estándar? ¿Cuáles son las capacidades de detección y corrección de errores de cada una de estas matrices?

1. \begin{equation*} \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \end{pmatrix} \end{equation*}

2. \begin{equation*} \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} \end{equation*}

3. \begin{equation*} \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix} \end{equation*}

4. \begin{equation*} \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} \end{equation*}

12

Liste todos los posible síndromes para los códigos generados por cada una de las matrices del Ejercicio 8.5.11.

13

Sea

Calcule 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

Sea \(C\) el código de grupo en \({\mathbb Z}_2^3\) definido por las palabras \((000)\) and \((111)\text{.}\) Calcule las clases laterales de \(H\) en \({\mathbb Z}_2^3\text{.}\) ¿Por qué no es necesario especificar si se trata de clases laterales derechas o izquierdas? Entregue el error singular de transmisión, si lo hay, que corresponda con cada clase lateral.

15

Para cada una de las siguientes matrices, encuentre las clases laterales para el código \(C\) correspondiente. Entregue una tabla de decodificación para cada código si es posible.

1. \begin{equation*} \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix} \end{equation*}

2. \begin{equation*} \begin{pmatrix} 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix} \end{equation*}

3. \begin{equation*} \begin{pmatrix} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix} \end{equation*}

4. \begin{equation*} \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} \end{equation*}

16

Sean \({\mathbf x}\text{,}\) \({\mathbf y}\text{,}\) y \({\mathbf z}\) \(n\)-tuplas binarias. Demuestre cada uno de los siguientes enunciados.

1. \(w({\mathbf x}) = d( {\mathbf x}, {\mathbf 0})\)

2. \(d( {\mathbf x}, {\mathbf y}) = d( {\mathbf x} + {\mathbf z}, {\mathbf y} + {\mathbf z} )\)

3. \(d({\mathbf x}, {\mathbf y}) = w({\mathbf x}- {\mathbf y})\)

17

Una métrica en un conjunto \(X\) es una función \(d: X \times X \rightarrow {\mathbb R}\) que satisface las siguientes condiciones.

1. \(d( {\mathbf x}, {\mathbf y}) \geq 0\) para todo \({\mathbf x}, {\mathbf y} \in X\text{;}\)

2. \(d( {\mathbf x}, {\mathbf y}) = 0\) si y solo si \({\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 otros 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 corresponde a decidir cuál es la palabra del código más cercana en términos de la distancia de Hamming.

18

Sea \(C\) un código lineal binario. Muestre que entre las \(i\)-ésimas coordenadas de la palabras en \(C\) hay puros ceros o exactamente la mitad son ceros.

19

Sea \(C\) un código lineal binario. Muestre que ya sea todas las palabras tienen peso par o exactamente la mitad de ellas tienen peso par.

20

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

21

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

22

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

23

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

24

Sea \({\mathbf e}_i\) la \(n\)-tupla binaria con un 1 en la \(i\)-ésima coordenada y \(0\) en las demás y supongamos que \(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\) Muestre que \(H{\mathbf e}_i\) es la \(i\)-ésima columna de la matriz \(H\text{.}\)

25

Sea \(C\) un código lineal \((n,k)\text{.}\) Definamos el código dual o código ortogonal de \(C\) como

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

   \begin{equation*} \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix}. \end{equation*}

2. Muestre que \(C^\perp\) es un código lineal \((n, n-k)\text{.}\)

3. Encuentre las matrices verificadora canónica y generadora estándar de \(C\) y \(C^\perp\text{.}\) ¿Qué sucede en general? Demuestre su conjetura.

26

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

1. Muestre que la matriz

   \begin{equation*} H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \end{pmatrix} \end{equation*}

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

2. La columna correspondiente al síndrome también marca el bit donde ocurrió el error; es decir, la \(i\)-ésima columna de la matriz es \(i\) escrito como número binario, y el síndrome inmediatamente nos dice cuál es el bit erróneo. Si la palabra recibida es \((101011)\text{,}\) Calcule el síndrome. ¿En qué bit ocurrió el error en este caso, y cuál era la palabra originalmente transmitida?

3. Entregue un matriz binaria \(H\) para el código de Hamming con seis posiciones de informacióny cuatro de verificación. ¿Cuáles son la posiciones de verificación y cuáles son las de información? Codifique los mensajes \((101101)\) y \((001001)\text{.}\) Decodifique 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 de Hamming de bloque \((m,n)\text{?}\) Encuentre tanto una cota superior como una cota inferior para el número de bits de información en términos del número de bits de verificación. Códigos de Hamming que tengan el máximo posible número de bits de información con \(k\) bits de verificación se llaman perfectos. Cada posible síndrome a excepción de \({\mathbf 0}\) ocurre como una columna. Si el número de bits de información es menor al máximo, entonces el código se llama recortado. En este caso, dé un ejemplo donde algunos síndromes puedan representar errores múltiples.