El registro ciclo a ciclo

Los dos ejercicios trabajan sobre el código cíclico (15,5) de la práctica, el de polinomio generador

$$g(X)=1+X+X^2+X^4+X^5+X^8+X^{10}$$

con polinomio de paridad $h(X)=1+X+X^3+X^5$, distancia mínima 7 y $t=3$. Los dos usan el mismo circuito, un registro de desplazamiento de diez etapas que divide por $g(X)$. En el 4 codifica. En el 5 calcula el síndrome, y después sigue andando sin entrada: cada ciclo de más es el síndrome de la palabra girada una posición. Los vectores van con la posición 0 a la izquierda.

01 · Ejercicio 4: la traza del codificador

El enunciado, textual: «Para el código (15,5), con el registro de $n-k=10$ etapas y el mensaje $\mathrm{u}=10110$,

1. Indicar en qué orden ingresan los bits del mensaje al registro.
2. Completar el contenido del registro ciclo a ciclo, partiendo del estado nulo.
3. Verificar que el contenido final coincide con el resto de dividir $X^{10}u(X)$ por $g(X)$.
4. Escribir la palabra de código completa.»

Antes de resolver: qué se entrega. Cuatro cosas de forma distinta. Un orden: los cinco bits del mensaje en fila. Una tabla de seis renglones, el estado inicial y uno por ciclo, con diez bits cada uno. Una división de polinomios cuyo resto tiene que dar el último renglón. Y un vector de quince bits, la palabra de código.

Lo primero es leer bien el mensaje. El vector $\mathrm{u}=10110$ tiene la posición 0 a la izquierda: $u_0=1$, $u_1=0$, $u_2=1$, $u_3=1$, $u_4=0$, y entonces

$$u(X)=1+X^2+X^3$$

02 · Las herramientas del ejercicio 4

Codificar en forma sistemática es una sola división. Se corre el mensaje $n-k$ lugares hacia los grados altos y se lo divide por $g(X)$:

$$X^{10}u(X)=a(X)g(X)+b(X),b(X)=R_{g(X)}\{X^{10}u(X)\}$$

Como en GF(2) sumar y restar son lo mismo, $b(X)+X^{10}u(X)=a(X)g(X)$: es un múltiplo de $g(X)$ de grado menor que 15, y las palabras del código son exactamente esos múltiplos. Ésa es la palabra:

$$v(X)=\underset{\text{paridad}}{\underbrace{b_0+b_{1}X+\cdots +b_9{X}^9}}+\underset{\text{mensaje}}{\underbrace{u_0{X}^{10}+\cdots +u_4{X}^{14}}}$$

con la forma sistemática del apunte: la paridad en las diez primeras posiciones y el mensaje intacto en las cinco últimas.

El circuito hace esa división bit por bit. Tiene diez etapas, $b_0,\dots ,b_9$, y en cada ciclo de reloj entra un bit $u_i$ del mensaje. La realimentación es la entrada más la última etapa, y vuelve a cada etapa cuyo coeficiente en $g(X)$ no es cero:

$$f=u_i+b_9,b_0^{\prime }=f,b_j^{\prime }=b_{j-1}+g_{j}f(1\le j\le 9)$$

Para este $g(X)$ las tomas están en $b_0$, $b_1$, $b_2$, $b_4$, $b_5$ y $b_8$. Cuando $f=1$, el registro desplazado recibe $g(X)$ sin su $X^{10}$, o sea $1110110010$; cuando $f=0$, sólo se desplaza.

03 · El razonamiento: qué guarda el registro

Primero pensar: por qué entra primero $u_4$. La división larga arranca por el término de mayor grado, y el registro es una división larga. Hay una forma más precisa de decirlo: después de cada ciclo, el registro guarda el resto de $X^{10}$ por lo que entró hasta ahí, leído con el primer bit en el grado más alto. Si hasta ahora entró $p(X)$ y entra el bit $c$, lo entrado pasa a ser $Xp(X)+c$. El registro hace exactamente eso. Desplazar es multiplicar por $X$. El bit que se cae por la punta vale $b_9{X}^{10}$, la entrada aporta $c{X}^{10}$, y su suma es $f{X}^{10}$. Como $X^{10}\equiv 1+X+X^2+X^4+X^5+X^8$ módulo $g(X)$, reducirlo es sumar $1110110010$ cuando $f=1$.

Por eso la entrada se suma en el punto de realimentación y no en $b_0$: ahí ya viene multiplicada por $X^{10}$. Y por eso el orden importa: el último bit en entrar queda con grado 0, así que el mensaje tiene que entrar desde $u_4$ hasta $u_0$, es decir 0, 1, 1, 0, 1.

Después escribir, ciclo a ciclo.

• Ciclo 1. Entra $u_4=0$ y $b_9=0$, así que $f=0$. El registro sigue en $0000000000$: lo entrado es el polinomio nulo.
• Ciclo 2. Entra $u_3=1$, $f=1+0=1$. El desplazamiento de cero es cero, más las tomas: $1110110010$, que es $R_{g(X)}\{X^{10}\}$.
• Ciclo 3. Entra $u_2=1$, $b_9=0$, $f=1$. Desplazado: $0111011001$; más $1110110010$: $1001101011$. Lo entrado es $X+1$, y el registro guarda $R_{g(X)}\{X^{10}+X^{11}\}$.
• Ciclo 4. Entra $u_1=0$, pero $b_9=1$: $f=1$. Desplazado: $0100110101$; más $1110110010$: $1010000111$. La realimentación no la decide la entrada sola.
• Ciclo 5. Entra $u_0=1$ con $b_9=1$: $f=1+1=0$, y el registro sólo se desplaza: $0101000011$.

Cada renglón se puede controlar contra la división del prefijo. Calculados aparte, los restos de $X^{10}$ por $0$, $1$, $1+X$, $X+X^2$ y $1+X^2+X^3$ dan los cinco estados de la traza, uno por uno.

El punto 3: la división escrita. $X^{10}u(X)=X^{10}+X^{12}+X^{13}$. Se va sumando $X^{s}g(X)$ para matar el término de mayor grado, hasta bajar de grado 10:

El cociente es $a(X)=X+X^2+X^3$ y el resto, escrito como vector de diez posiciones, $0101000011$: el último renglón de la traza.

Con $u_4$ primero, el registro termina en $0101000011$ y la palabra tiene síndrome nulo. Volvé a cero y probá el orden al revés con el mismo mensaje: el registro termina en otra cosa, y la palabra que se arma con eso no es del código. Después probá el orden al revés con un mensaje capicúa, como $10101$.

04 · La resolución del ejercicio 4

1. Los bits entran empezando por el de mayor orden, $u_4$: en el orden $u_4,u_3,u_2,u_1,u_0$, que para este mensaje es 0, 1, 1, 0, 1.

2. El registro, ciclo a ciclo:

3. El registro termina en $b(X)=X+X^3+X^8+X^9$. La división de la sección 03 da el mismo resto, con cociente $a(X)=X+X^2+X^3$.

4. La paridad adelante y el mensaje atrás:

$$\mathrm{v}=\underset{\text{paridad}}{\underbrace{0101000011}}\underset{\text{mensaje}}{\underbrace{10110}}$$

o, como polinomio,

$$v(X)=X+X^3+X^8+X^9+X^{10}+X^{12}+X^{13}$$

Control final: dividido por $g(X)$, $v(X)$ da resto cero, con el mismo cociente $a(X)$.

05 · Ejercicio 5: el síndrome y un ciclo más

El enunciado, textual: «Se transmite la palabra del ejercicio anterior y el canal introduce un error en la posición $X^{12}$, de modo que se recibe

$$\mathrm{r}=010100001110010.$$

1. Calcular el síndrome $s(X)$, resto de dividir $r(X)$ por $g(X)$.
2. Obtener $s^{(1)}(X)$ y $s^{(2)}(X)$ aplicando ciclos de reloj al registro, es decir como los restos de $Xs(X)$ y $X^{2}s(X)$ módulo $g(X)$.
3. Calcular por separado el síndrome de ${\mathrm{r}}^{(1)}$ y el de ${\mathrm{r}}^{(2)}$, dividiendo desde cero.
4. Comparar y enunciar qué resultado de la teoría se acaba de verificar.»

Antes de resolver: qué se entrega. Tres vectores de diez bits que salen del registro, $s,s^{(1)},s^{(2)}$; dos más que salen de dividir de nuevo; y el nombre de un teorema. Conviene leer también $\mathrm{r}$ contra la palabra del ejercicio 4: difiere sólo en la posición 12, donde $\mathrm{v}$ tenía un 1. Entonces

$$r(X)=v(X)+X^{12}=X+X^3+X^8+X^9+X^{10}+X^{13}$$

06 · Las herramientas del ejercicio 5

El síndrome es un resto, y sólo ve el error. Si $r(X)=v(X)+e(X)$, con $e(X)$ el patrón de error, y $g(X)$ divide a $v(X)$,

$$s(X)=R_{g(X)}\{r(X)\}=R_{g(X)}\{e(X)\}$$

Es el síndrome de siempre, calculado de otra manera: el síndrome cíclico sale del mismo registro del codificador, alimentado con la palabra recibida. Con una diferencia de cableado: $r(X)$ entra por $s_0$, desde $r_{14}$, y no en el punto de realimentación. Por eso tarda quince ciclos y no cinco:

$$f=s_9,s_0^{\prime }=r_i+f,s_j^{\prime }=s_{j-1}+g_{j}f$$

El teorema 5 del apunte. Si $s(X)$ es el síndrome de $r(X)$, el de su desplazamiento cíclico $r^{(1)}(X)$ es

$$s^{(1)}(X)=R_{g(X)}\{Xs(X)\}$$

y, aplicado $i$ veces,

$$s^{(i)}(X)=R_{g(X)}\{X^{i}s(X)\}$$

La prueba entra en un renglón. Girar es $r^{(1)}(X)=Xr(X)+r_{14}(X^{15}+1)$, y $X^{15}+1=h(X)g(X)$ es múltiplo de $g(X)$: módulo $g(X)$, girar es multiplicar por $X$. Y $Xs(X)$ reducido es lo que hace el registro en un ciclo con la entrada cortada.

07 · El razonamiento: el síndrome sólo ve el error

Primero pensar. No hace falta dividir $r(X)$: el error es $e(X)=X^{12}$, así que $s(X)=R_{g(X)}\{X^{12}\}$. Y como $v(X)$ girada sigue siendo palabra, $r^{(1)}(X)$ es una palabra más un error en $X^{13}$, y $r^{(2)}(X)$, una palabra más un error en $X^{14}$. Todo el ejercicio se reduce a los restos de las potencias altas de $X$.

La tabla de restos. Se arma de a un renglón: cada uno es el anterior multiplicado por $X$, y si aparece un $X^{10}$ se lo cambia por $1+X+X^2+X^4+X^5+X^8$.

El renglón 12, desarrollado: el 11 por $X$ da un $X^{10}$, y se lo cambia.

Punto 1. Por el error, $s(X)=R_{g(X)}\{X^{12}\}$, el renglón 12: $s=1101011110$. Por la palabra recibida, que es la cuenta que pide el enunciado, la parte de grado menor que 10 queda como está y cada potencia alta se cambia por su renglón: $r(X)$ tiene $X+X^3+X^8+X^9$ abajo y $X^{10}+X^{13}$ arriba, así que

Los dos caminos dan lo mismo porque $v(X)$ es palabra; si el ejercicio 4 hubiera salido mal, acá no coincidirían.

Punto 2. Un ciclo con la entrada cortada. En $s$, la última etapa vale 0: no hay realimentación, el registro sólo se desplaza, y $Xs(X)$ ya tiene grado menor que 10. Queda $s^{(1)}=0110101111$. En $s^{(1)}$ la última etapa vale 1: desplazado da $0011010111$ con un $X^{10}$ que se cae, y sumando las tomas,

$$s^{(2)}=0011010111+1110110010=1101100101$$

Son los renglones 13 y 14 de la tabla, como tenía que ser: el error se corrió a $X^{13}$ y a $X^{14}$.

Punto 3. Ahora las palabras giradas, cada una dividida desde cero con la misma tabla. Girar una posición manda cada bit al siguiente y el $r_{14}$ a la posición 0:

En cada suma, el primer término es la parte baja de la palabra girada y los otros, los renglones de sus potencias altas. Las cuentas usan bits distintos de las del punto 2, y llegan a los mismos vectores.

Seguí de largo después del segundo ciclo de más. En el tercero el registro queda en $1000000000$: el error dio la vuelta hasta la posición 0, y desde ahí el registro muestra el error tal cual mientras éste recorre la paridad. Probá también con dos errores separados, o con tres juntos.

08 · La resolución del ejercicio 5

1. $s(X)=R_{g(X)}\{r(X)\}$ vale $s=1101011110$, el polinomio $1+X+X^3+X^5+X^6+X^7+X^8$. El circuito de síndrome llega ahí en quince ciclos.

2. Con dos ciclos más del registro, sin entrada: $s^{(1)}=0110101111$ y $s^{(2)}=1101100101$.

3. Dividiendo desde cero, $R_{g(X)}\{r^{(1)}(X)\}$ da $0110101111$ y $R_{g(X)}\{r^{(2)}(X)\}$ da $1101100101$.

4. Coinciden. Es el teorema 5: el síndrome del desplazamiento cíclico de la palabra recibida es el resto de $Xs(X)$ módulo $g(X)$. Dicho en circuito: para recorrer los quince giros de $\mathrm{r}$ alcanza con quince ciclos de reloj del mismo registro, sin ninguna división nueva. Comprobado sobre los $2^{15}=32768$ vectores de quince bits, el síndrome girado y el síndrome de la palabra girada coinciden en todos.

09 · Lo que se lleva a otros ejercicios

La tabla de restos. Con los restos de $X^j$ para $j=n-k,\dots ,n-1$, cualquier resto módulo $g(X)$ es la parte baja más una suma de renglones: sirvió para la paridad del ejercicio 4 (renglones 10, 12 y 13), para el síndrome y para las dos palabras giradas. Es, además, la parte de paridad de la matriz generadora sistemática: la fila $i$ de $G$ es $R_{g(X)}\{X^{10+i}\}$ seguido de un 1 en la posición $10+i$.

El registro guarda el resto del prefijo. Para trazar un codificador no hace falta simular a ciegas: el estado después del ciclo $c$ es $R_{g(X)}\{X^{n-k}p(X)\}$, con $p(X)$ los $c$ bits que entraron, el primero en el grado más alto. Cualquier renglón se controla solo.

Cuándo conviene el otro codificador. En el (15,5) hay más paridad que mensaje, $n-k=10>k=5$. El apunte da también un codificador de $k$ etapas, cableado según $h(X)$ en vez de $g(X)$, y en ese caso es el de registro más corto: cinco etapas en lugar de diez.

Seguir girando es decodificar. Con dos ciclos de más el error está en la posición 14, la última, que es la que examina el decodificador de Meggitt en cada ciclo. Con tres, el registro vale $R_{g(X)}\{X^{15}\}=1$, de peso 1: el error cayó en la ventana de paridad, y el síndrome es el error. Es la captura de errores, y no pide ningún circuito nuevo.

10 · Las trampas

Cuál es la posición 0. Los vectores se escriben con la posición 0 a la izquierda, y el polinomio, de grado creciente. $\mathrm{u}=10110$ es $1+X^2+X^3$, no $X+X^2+X^4$.

En qué orden entra el mensaje. Primero $u_4$. Al revés, el registro calcula la paridad del mensaje dado vuelta: con $10110$ termina en $0111100010$, y la palabra que se arma con esa paridad tiene síndrome $0010100001$. Lo traicionero es que el error no siempre se ve. Con un mensaje capicúa los dos órdenes dan lo mismo: de los 32 mensajes, en 8 el orden al revés arma una palabra del código. Para probar el circuito hace falta un mensaje que no sea capicúa.

Cuál es el bit de mayor orden del registro. Es $b_9$, el de la derecha cuando el registro se escribe $b_0\dots b_9$. La realimentación es $u_i+b_9$, no $u_i+b_0$, y desplazar mueve los bits hacia la derecha. En el ciclo 4 entra un 0 y aun así hay realimentación, porque $b_9=1$.

El ciclo que no hace nada también va. $u_4=0$ deja el registro en cero, pero la tabla tiene cinco ciclos, no cuatro.

Codificador y síndrome no se alimentan igual. El codificador suma la entrada en la realimentación, que equivale a multiplicarla por $X^{10}$, y termina en $k$ ciclos. El circuito de síndrome la mete por $s_0$ y termina en $n$. En la palabra del ejercicio 5 los once primeros ciclos sólo desplazan: la primera realimentación llega en el ciclo 12.

Para tener a mano

1. $b(X)=R_{g(X)}\{X^{n-k}u(X)\}$ y $v(X)=b(X)+X^{n-k}u(X)$: la paridad primero, el mensaje al final.
2. El codificador: $f=u_i+b_{n-k-1}$, el mensaje desde $u_{k-1}$, $k$ ciclos. Después de cada ciclo guarda el resto de $X^{n-k}$ por lo que entró.
3. Ejercicio 4: orden 0, 1, 1, 0, 1; registro 0000000000, 0000000000, 1110110010, 1001101011, 1010000111, 0101000011; $\mathrm{v}=010100001110110$.
4. $s(X)=R_{g(X)}\{r(X)\}=R_{g(X)}\{e(X)\}$. El circuito de síndrome mete $\mathrm{r}$ por $s_0$ desde $r_{n-1}$ y tarda $n$ ciclos.
5. Teorema 5: $s^{(i)}(X)=R_{g(X)}\{X^{i}s(X)\}$. Un ciclo sin entrada es un giro de la palabra.
6. Ejercicio 5: $s=1101011110$, $s^{(1)}=0110101111$, $s^{(2)}=1101100101$: los restos de $X^{12}$, $X^{13}$ y $X^{14}$.
7. La tabla de $R_{g(X)}\{X^j\}$ para $j\ge n-k$ resuelve cualquier resto con sumas, y es la paridad de la $G$ sistemática.