Siguiente: Programas Arriba: Terceras listas Anterior: Terceras listas

Ejercicios

1. Sea $a$ un elemento primitivo en un campo $\mathbb{F}_q$. Demuestre las siguientes dos implicaciones:

$$\begin{eqnarray*} \kappa\not=0\bmod(q-1) &\Longrightarrow& \sum_{\lambda=0}^{q-2... ...&\Longrightarrow& \sum_{\lambda=0}^{q-2} a^{\kappa\lambda} = q-1 \end{eqnarray*}$$

2. Sea $g(X)=1+X+X^2+X^4+X^5+X^8+X^{10}$ un polinomio generador de un código cíclico-$[15,5]$. Calcule el polinomio de paridad $h(X)$ de $g(X)$.

3. Sea $g(X)\in\mathbb{F}_2[X]$ un polinomio de grado $m\in\mathbb{N}$ que no sea un binomio, y sea $n$ el entero mínimo tal que $g(X)$ divide a $X^n+1$. Muestre que el código cíclico de longitud $n$ generado por $g(X)$ tiene peso mínimo al menos 3.

4. Sea $C$ un código cíclico-$[n,k]$ binario. Muestre que si $n$ es impar y $X+1$ no divide a $g(X)$ entonces el vector constante 1, $1^{(n)}$, está en el código $C$.

5. Sea $g(X)=1+X^4+X^6+X^7+X^8$ un polinomio generador de un código cíclico-$[15,7]$. Calcule el síndrome del polinomio $a(X)=1+X+X^5+X^{14}$ y decida si $a(X)$ está o no en el código.

6. Sea $C$ el código-$[15,11]$ cíclico binario generado por el polinomio $g(X)=1+X+X^4$, y suponga que se ha recibido el polinomio $c(X)=1+X+X^4+X^{10}$ cuando se ha utilizado una codificación no-sistemática. Recupere el mensaje $a(X)$ que le dió origen.

7. Sea $H_m\in\mathbb{F}_2^{(2^m-1)\times m}$ la matriz revisora de paridad del código de Hamming- $\left(2^m-1,2^m-m-1\right)$, dado en la definición 4.7, y sea $C_m\subset\mathbb{F}_2^{2^m-1}$ el código cuya generatriz es $H_m$.

1. Decida si acaso $C_m$ es un código cíclico.
2. Muestre que para cada ${\bf u}\in C_m-\{{\bf0}\}$ y para cada $k\in[\![1,2^m-2]\!]$, $\rho_{2^m-1}^k({\bf u})\not={\bf u}$, donde $\rho_{2^m-1}$ es la rotación a la izquierda de longitud $2^m-1$.

8. Sea $H_m\in\mathbb{F}_2^{(2^m-1)\times m}$ la matriz revisora de paridad del código de Hamming- $\left(2^m-1,2^m-m-1\right)$, dado en la definición 4.7, y sea $C_m\subset\mathbb{F}_2^{2^m-1}$ el código cuya generatriz es $H_m$.

1. Muestre que las palabras de código no-nulas de $C_m$ poseen todas un peso de Hamming $2^{m-1}$.
2. Sea $M\in\mathbb{F}_2^{(2^m-1)\times(2^m-1)}$ la matriz tal que la entrada $m_{ij}$ es la $j$-ésima entrada del $i$-ésimo vector no nulo en $C_m$. De acuerdo con el inciso anterior en cada renglón hay $2^{m-1}$ 1's. Muestre que también en cada columna hay $2^{m-1}$ 1's.

9. Código CRC-16. Sea $g(X) = 1 + X^2 + X^{15} + X^{16}\in\mathbb{F}_2[X]$, el llamado polinomio CRC-16. Se tiene que, en $\mathbb{F}_2[X]$:

$$g(X) = (X+1)\,h(X) = (X+1)\,( 1 + X + X^{15})$$

y $h(X)$ es primitivo.

1. ¿Cuál es el mínimo $n\in\mathbb{N}$ tal que $g(X)$ genera un código cíclico de longitud $n$?
2. Diseñe un algoritmo, a nivel de bits, para realizar la codificación no-sistemática en ese código.

10. Código CRC-CCITT. Sea $g(X) = 1 + X^5 + X^{12} + X^{16}\in\mathbb{F}_2[X]$, el llamado polinomio CRC-CCITT. Se tiene que, en $\mathbb{F}_2[X]$:

$$g(X) = (X+1)\,h(X) = (X+1)\,( 1 + X + X^2 + X^3 + X^4 + X^{12} + X^{13} + X^{14} + X^{15})$$

y $h(X)$ es primitivo.

1. ¿Cuál es el mínimo $n\in\mathbb{N}$ tal que $g(X)$ genera un código cíclico de longitud $n$?
2. Diseñe un algoritmo, a nivel de bits, para realizar la codificación no-sistemática en ese código.

11. El código de Golay es un código-$(23,12)$ perfecto de distancia mínima 7.

1. Muestre que hay palabras de código, es decir, vectores en el código de Golay, de peso 16.
2. Muestre que hay un mismo número de vectores en el código de peso 7 que de peso 16.

12. Encuentre el polinomio generador de un código de BCH de longitud 31 que corrija errores dobles y el de otro que corrija errores triples.

13. Encuentre el polinomio generador de un código de Reed-Solomon con símbolos en $\mathbb{F}_{2^5}$ que corrija errores dobles.

14. ¿Cuántos códigos cíclicos de longitud $8$ hay sobre $\mathbb{F}_3$?

Siguiente: Programas Arriba: Terceras listas Anterior: Terceras listas