Codigos Ciclicos

Capıtulo 9

Codigos cıclicos

9.1. Codigos cıclicos

Los codigos cıclicos son los codigos lineales de mayor interes. En general,

se pueden implementar de un modo mas facil, de ahı su importancia desde el

punto de vista practico. No obstante, tambien tienen un gran interes teorico.

Si el alfabeto A es un cuerpo, sabemos que An es un espacio vectorial

de dimension n. Un subespacio S de An se dira que es cıclico si tiene la

propiedad siguiente

(a0, a1, ...., an−1) ∈ S ⇒ (an−1, a0, a1, ..., an−2) ∈ S.

Es decir, toda permutacion cıclica de una cadena que pertenece a S tambien

pertenece a S.

Definicion 9.1.1. Un codigo cıclico sobre el alfabeto A es cualquier subes-

pacio cıclico de An.

Ejemplos 9.1.2. 1) Si A es el alfabeto binario y n = 7, el codigo lineal

C = {(0000000), (1011100), (0101110), (0010111), (1110010), (0111001),

141

142 CAPITULO 9. CODIGOS CICLICOS

(1001011), (1100101)}es cıclico.

2) C = {000, 210, 021, 102, 201, 120, 012, 222, 111} es un codigo cıclico so-

bre el alfabeto A = Z3 = {0, 1, 2}. Su dimension es 2, pues esta generado por

las cadenas independientes 111 y 210.

En relacion con los codigos cıclicos se plantean las siguientes cuestiones:

a) ¿Como se determinan los subespacios cıclicos de An?

b) Para un valor de k < n dado, ¿existe algun subespacio cıclico de An

que tenga por dimension k?

c) ¿Cuantos subespacios cıclicos contiene An?

d) ¿Que tiene que ocurrir para que un vector junto con sus permutaciones

cıclicas generen un subespacio cıclico?

Ejemplo 9.1.3. Si A es el alfabeto binario y n = 6, consideremos el subes-

pacio S generado por los vectores

v1 = (111000), v2 = (011100), v3 = (001110), v4 = (000111).

La base esta formada por el vector v1 junto con tres de sus permutaciones

cıclicas. Sin embargo, el vector v = (101010) = v1 + v2 + v3 pertenece a

S y solo tiene una permutacion cıclica (010101) con la que determina un

subespacio de dimension 2.

Terminamos esta seccion indicando, sin demostracion, que todo codigo

binario de Hamming es equivalente a uno cıclico. Si el alfabeto A tiene q

elementos, un codigo de Hamming de redundancia r sobre dicho alfabeto es

equivalente a un codigo cıclico si y solo si mcd(r, q − 1) = 1

9.2. Subespacios cıclicos y polinomios

A cada cadena v = (v0, v1, .., vn−1) de An le asociamos el polinomio v(x) =

v0+v1x+ · · ·+vn−1xn−1. Si realizamos el producto xv(x) resulta el polinomio

9.2. SUBESPACIOS CICLICOS Y POLINOMIOS 143

v0x+v1x2+· · ·+vn−2x

n−1+vn−1xn. Si en lugar de considerar el anillo A[x] de

todos los polinomios en la indeterminada x, consideramos las clases de restos

modulo f(x) = xn − 1, la clase del polinomio producto xv(x) es la de v0x +

v1x2+· · ·+vn−2x

n−1+vn−1, ya que xn ≡ 1 (modulo xn−1). Notese que la clase

del producto xv(x) tiene un representante que es importante en esta historia:

es el polinomio que le corresponderıa a la cadena (vn−1, v0, v1, ..., vn−2), que

es una permutacion cıclica de v. Esta es la razon de realizar la asociacion

siguiente: dada una cadena v = (v0, v1, ..., vn−1) de An, le asociamos la clase

formada por todos los polinomios que son congruentes, modulo xn − 1, con

v(x) = v0 + v1x + · · · + vn−1xn−1. Es decir, consideramos la aplicacion I

definida por

v = (v0, v1, .., vn−1) ∈ An → [v(x)] ∈ A[x]/(xn − 1).

A[x]/(xn− 1) es el anillo cociente formado por las clases de resto modulo

xn− 1. Hay tantas clases como polinomios de grado menor o igual que n− 1.

Si un polinomio P (x) tiene grado menor que n, el mismo puede tomarse como

representante de su clase. Si su grado es mayor o igual que n, se dividira por

xn − 1 y el resto de la division

P (x) = (xn − 1)C(x) + R(x)

(que tiene grado menor que n) es un polinomio congruente con P (x) que

puede tomarse como representante de la clase. De esta forma, siempre pode-

mos tomar como representante de una clase un polinomio de grado menor que

n. Por ello, podemos operar con las clases como lo harıamos con polinomios

de grado menor que n y solo cuando, al realizar alguna de las operaciones

(suma o producto), obtengamos como resultado un polinomio de grado mayor

o igual que n, dividiremos por xn− 1 para obtener el representante de grado

menor que n de la clase.

Hay, por tanto, una correspondencia biunıvoca entre An y A[x]/(xn −1). Vamos a aprovechar este hecho para descubrir como son los subespacios

cıclicos de An. Veremos que S es un subespacio cıclico de An si y solo si I(S)

es un ideal del anillo cociente.


Recordemos que un subconjunto no vacıo I de un anillo A se dice que es

un ideal si tiene las propiedades siguientes:

(I1) I es un grupo abeliano para la suma

(I2) Cualesquiera que sean a ∈ A e y ∈ I, se verifica que a · y ∈ A.

Una forma simple de determinar un ideal en cualquier anillo es la si-

guiente: se escoge b ∈ A, b 6= 0 y se define I = {a · b : a ∈ A}. Es inmediato

comprobar que I es un ideal, que recibe el nombre de ideal generado por b. En

general, no es cierto que todo ideal de un anillo cualquiera se pueda obtener

de este modo. Precisamente, cuando un anillo tiene la propiedad de que todos

sus ideales son de esta forma, el anillo se denomina anillo principal.

Teorema 9.2.1. Un subconjunto no vacıo S de An es un subespacio cıclico

si y solo si I(S) es un ideal en A[x]/(xn − 1).

DEMOSTRACION: Supongamos que S es un subespacio cıclico de An. I(S)

es el conjunto formado por las clases [v(x)], recorriendo v el conjunto S. Es

decir, I(S) = {[v(x)] : v ∈ S}. Si v ∈ S, el producto [x][v(x)] es la clase

[xv(x)] y, segun hemos visto antes, se trata de la clase que corresponde al

polinomio vn−1 + v0x + v1x2 + · · · + vn−2x

n−1, que pertenece a I(S) pues

(vn−1, v0, v1, ..., vn−2) ∈ S, ya que este es cıclico. Este razonamiento puede

repetirse para probar que [xk][v(x)] ∈ I(S), para cada k ∈ N. Vemos que al

multiplicar un elemento de I(S) por las clases [xk] el resultado permanece

en I(S). Para terminar, debemos hacer el producto por una clase arbitraria

[

p∑0

akxk] y comprobar que el resultado permanece en I(S). Esto se sigue

facilmente de la igualdad

[

p∑0

akxk][v(x)] =

p∑0

ak[xk][v(x)].

De un modo similar se prueba que, si I(S) es un ideal, entonces S es un

subespacio cıclico. ¤

9.2. SUBESPACIOS CICLICOS Y POLINOMIOS 145

La importancia del resultado anterior radica en el hecho de que se sabe que

el anillo cociente es principal y, por tanto, todos sus ideales estan generados

por una clase. Es decir, todos los ideales de A[x]/(xn − 1) son de la forma

I = {[a(x) · g(x)] : a(x) ∈ A[x]}. El polinomio g(x) recibe el nombre de

polinomio generador del ideal. Se sabe que g(x) es el polinomio monico de

menor grado que puede haber en las clases que pertenecen a I. El Teorema

siguiente muestra que el polinomio (monico) generador de un ideal debe ser

divisor de xn − 1.

Teorema 9.2.2. Si I es el ideal de A[x]/(xn − 1) generado por el polinomio

monico g(x), entonces g(x) divide a xn − 1.

DEMOSTRACION: El grado de g(x) es menor que n (recuerdese que en

cada clase hay un polinomio de grado menor o igual que n − 1 y g(x) es el

polinomio de menor grado que podemos encontrar en alguna clase del ideal).

Entonces podemos hacer la division entera de xn − 1 por g(x):

xn − 1 = g(x) · C(x) + R(x),

con R(x) identicamente nulo o con grado menor que n. Tomando clases en

la igualdad anterior, resulta

0 = [g(x)] · [C(x)] + [R(x)].

Es decir, se tiene [R(x)] = [−C(x)] · [g(x)]. Como I es un ideal, se sigue que

[R(x)] ∈ I, lo que es imposible salvo que sea R(x) ≡ 0, ya que habrıa en el

ideal una clase con un representante cuyo grado es menor que el de g(x). ¤

Omitimos la prueba, pero de igual forma se demuestra que todo divisor

monico de xn − 1 es el polinomio generador de un ideal de A[x]/(xn − 1).

Terminamos esta seccion probando que la dimension del ideal I (considerando

su estructura de espacio vectorial) generado por un divisor (monico) g(x) de

xn − 1 es igual a k, si n− k es el grado de g(x).


Sea I = {[a(x) · g(x)] : a(x) ∈ A[x]}, vamos a comprobar que B =

{[g(x)], [xg(x)], ..., [xk−1g(x)]} es una base de I, considerado como espacio

vectorial sobre el cuerpo A.

a) Independencia lineal. Supongamos que [k−1∑i=0

λixig(x)] = 0 y probemos

que λi = 0, para cada i = 0, 1, .., k − 1. Veamos como se prueba que λk−1 =

0. La clase nula solo contiene los multiplos de xn − 1, por tanto, el unico

polinomio con grado menor que n que contiene dicha clase es el polinomio

nulo. Como el grado de la sumak−1∑i=0

λixig(x) es menor o igual que k−1+n−

k = n−1, se sigue que debe ser identicamente nulo el polinomiok−1∑i=0

λixig(x).

En particular, es nulo el coeficiente lıder que es igual a λk−1. Razonando de

esta forma se puede ir probando que son nulos uno a uno los λi.

b) Sistema generador. Consideremos, en primer lugar, una clase con re-

presentante de la forma a(x) ·g(x), siendo a(x) un polinomio de grado menor

que k. Entonces a(x) =k−1∑i=0

aixi, luego

[a(x) · g(x)] = [k−1∑i=0

aixig(x)] =

k−1∑i=0

ai[xig(x)].

Por tanto, en este caso, queda probado que B es un sistema generador. Con-

sideremos ahora una clase [a(x) ·g(x)] con a(x) un polinomio de grado mayor

o igual que k. Ahora el grado de a(x) ·g(x) es mayor o igual que k+n−k = n

y, por tanto, podemos hacer la division entera de a(x) · g(x) entre xn − 1:

a(x) · g(x) = (xn − 1) · C(x) + R(x),

siendo el grado de R(x) menor que n o R(x) identicamente nulo. Como g(x)

es divisor de xn − 1, se sigue de la igualdad anterior que g(x) divide al resto

R(x). Esto prueba que la clase [R(x)] es la misma que la dada [a(x)·g(x)], pero

R(x) tiene la ventaja de que puede expresarse en la forma R(x) = b(x) · g(x)

9.3. SUBESPACIOS CICLICOS DE AN 147

con el grado de b(x) menor que k y puede aplicarse el caso anterior para

probar que [a(x) · g(x)] = [R(x)] es combinacion lineal de los elementos de

B.

9.3. Subespacios cıclicos de An

Si S es un subespacio cıclico de An, hemos probado que I(S), es decir,

el propio S mirado como un subconjunto de A[x]/(xn − 1), es un ideal. Por

tanto, I(S) esta generado por un polinomio monico g(x) que es divisor de

xn− 1. Si el grado de g(x) es n− k, entonces k es la dimension de I(S) como

subespacio vectorial del anillo cociente y, por tanto, tambien es la dimension

de S (I es un isomorfismo). Hemos visto que una base de I(S) esta dada

por las clases [g(x)], [xg(x)], ..., [xk−1g(x)]. Para obtener una base de S, basta

escribir los coeficientes de los polinomios xig(x) (i = 0, .., k − 1) en orden

creciente de las potencias de x. Como estos polinomios tienen grado menor o

igual que i + (n− k) ≤ k− 1 + n− k = n− 1, no hay que hacer la reduccion

modulo xn − 1. Entonces, si g(x) = xn−k +∑n−k−1

0 cixi, una base de S esta

dada por

c0 c1 c2 ..... cn−k−1 1 0 0.... 0 0

0 c0 c1 ......, cn−k−2 cn−k−1 1 0 .... 0

0 0 c0 c1 ....... cn−k−1 1 0 ... 0

.... .... ..... .... .... .... .... ... ... ...

0 0 ... 0 c0 c1 c2 ..... cn−k−1 1

Notese que se trata del vector (c0, c1, ...., cn−k−1, 1, 0, 0, ..., 0) y k − 1 de sus

permutaciones cıclicas .

9.4. Codificacion con un codigo cıclico

Suponemos en toda la seccion que C es un (n, k)-codigo cıclico sobre

el alfabeto A. Como su dimension es k, el polinomio generador g(x) tiene


grado n− k. Vamos a ver como se codifica ”polinomicamente” con un codigo

cıclico. Segun acabamos de ver, una matriz generadora es la formada por

los polinomios g(x), xg(x), x2g(x), ..., xk−1g(x). Los mensajes a codificar los

denotaremos por a(x) y no son otra cosa que los polinomios de grado menor o

igual que k−1. El mensaje codificado de a(x) es a(x)g(x), es decir, la cadena

formada por los coeficientes del polinomio producto a(x) ·g(x), dispuestos en

orden creciente de las potencias de x. Como el grado de a(x) · g(x) es menor

o igual que k − 1 + n − k = n − 1, no hay que hacer la reduccion modulo

xn − 1. Notese que, si a(x) =k−1∑0

aixi, entonces a(x)g(x) =

k−1∑0

aixi · g(x) es

una combinacion lineal de los polinomios basicos y, por tanto, a(x) · g(x) es

una palabra-codigo (la codificacion del mensaje a(x)).

Ahora vamos a ver una forma de obtener una matriz generadora de la

forma G = [R Ik], donde Ik denota la matriz unidad de orden k. Hacemos la

division entera de xn−k+i por g(x), para i = 0, 1, ..., k − 1:

xn−k+i = g(x) · C(x) + Ri(x),

donde Ri(x) es identicamente nulo o tiene grado menor que n− k. Tenemos

entonces

xn−k+i −Ri(x) = g(x) · C(x) ∈ C.

Si consideramos la matriz G cuyas filas son los coeficientes en orden cre-

ciente de los polinomios xn−k+i − Ri(x), esta matriz tiene la forma indicada

(la matriz R tiene por filas los coeficientes de −Ri(x)). Con esta matriz

generadora, al codificar un mensaje m = (a0, a1, ..., ak−1), resulta la palabra-

codigo c = (s0, s1, ..., sn−k−1, a0, a1, ..., ak−1). Vemos que los dıgitos del men-

saje original aparecen tal cual al final del mensaje codificado. Los dıgitos

iniciales s0, .., sn−k−1 son los dıgitos de control que en forma polinomica se

corresponden con la suma −k−1∑0

aiRi(x).

Ejemplo 9.4.1. Consideremos el codigo binario cıclico C(7, 4) generado por

g(x) = 1 + x + x3.

9.5. DECODIFICACION DE UN CODIGO CICLICO 149

Si queremos codificar el mensaje m = (1001), consideramos el polinomio

m(x) = 1+x3 y hacemos el producto m(x)g(x) = 1+x+x4 +x6. El mensaje

codificado es c = (1100101).

9.5. Decodificacion de un codigo cıclico

Iniciamos esta seccion probando que los errores a rafagas de longitud

t ≤ n − k son detectados. Notese que, realizando un numero adecuado de

permutaciones cıclicas, toda rafaga cıclica de longitud t se convierte en una

cadena que tiene n− t ceros al principio. De esta idea se sigue facilmente que

toda rafaga cıclica de longitud t se puede expresar en la forma xip(x), con

p(x) un polinomio de grado menor que t.

Ejemplo 9.5.1. Consideremos la cadena y = 0100000100. Se trata de una

rafaga cıclica de longitud 5. Con 8 permutaciones cıclicas sucesivas se con-

vierte en la cadena 0000010001, que puede expresarse en la forma polinomica

siguiente x5(1+x4). Aplicando a esta otras dos permutaciones cıclicas la con-

vertimos en la original. Por tanto, nuestra cadena inicial se puede expresar

como y(x) = x7(1 + x4).

Teorema 9.5.2. Sea C un codigo cıclico generado por el polinomio g(x) de

grado n− k, siendo n la longitud. C no puede contener una rafaga cıclica de

longitud t ≤ n − k y, por tanto, detecta cualquier error que sea una rafaga

cıclica de longitud menor o igual que n− k.

DEMOSTRACION: Segun acabamos de ver, una rafaga cıclica de longitud

t puede expresarse en forma polinomica como xip(x), siendo p(x) un poli-

nomio de grado menor que t. Desde luego p(x) no puede pertenecer al codigo

por tener menos grado que el polinomio generador. Entonces tampoco puede

pertenecer xip(x), ya que realizando n− i permutaciones cıclicas obtenemos

p(x), que no pertenece. Para terminar, vamos a probar que se detectan todos


los errores que sean rafagas cıclicas de longitud menor o igual que n− k. Si

se emite una palabra-codigo c y se produce uno de tales errores e, entonces

recibimos y = c+e. y no puede pertenecer al codigo, ya que entonces tambien

pertenecerıa e = y − c. ¤

Consideremos un codigo cıclico C(n, k) sobre el alfabeto A y con poli-

nomio generador g(x) de grado n − k. Sabemos encontrar una matriz gene-

radora de la forma G = [−R Ik], donde R es una matriz cuyas filas son los

coeficientes de los restos Ri(x) obtenidos al hacer la division entera de xn−k+i

por g(x). A partir de esta matriz, podemos determinar una matriz de control

para el codigo de la forma H = [In−k Rt] (recuerdese que HGt = 0). Para

cada cadena y ∈ An, el sındrome de y viene dado por s = Hyt. Se trata

de una columna de n − k componentes. El teorema siguiente nos da una

interpretacion polinomial del sındrome.

Teorema 9.5.3. Si y(x) y s(x) son las representaciones polinomicas de y y

s, respectivamente, entonces s(x) es el resto de dividir y(x) por g(x).

DEMOSTRACION: Sea y(x) = a0 +a1x+a2x2 + · · ·+an−1x

n−1. Notese que

la representacion polinomica de la columna i de H,para i ≤ n− k − 1, es el

polinomio xi, mientras que se trata del polinomio Ri−n+k(x) para i ≥ n− k.

Entonces, se tiene

s(x) = H · yt =n−1∑i=0

aici =n−k−1∑

i=0

aixi +

n−1∑

i=n−k

aiRi−n+k(x) = (9.1)

=n−k−1∑

i=0

aixi − an−k(x

n−k + C0(x)g(x)) + · · · − an−1(xn−1 + Ck−1(x)g(x)) =

= y(x)− (an−kC0(x) + · · ·+ an−1Ck−1(x))g(x).

Hemos obtenido la identidad

s(x) = y(x)− g(x)(an−kC0(x) + · · ·+ an−1Ck−1(x))g(x),

9.5. DECODIFICACION DE UN CODIGO CICLICO 151

de donde se sigue

y(x) = g(x)(−an−kC0(x)− · · · − an−1Ck−1(x))g(x) + s(x),

Ahora basta notar que el grado de s(x) es menor o igual que n− k − 1 para

convencernos que la igualdad anterior es la division entera de y(x) entre g(x).

En efecto, en la igualdad (9.1) todos los polinomios Ri(x) tienen grado menor

o igual que n− k − 1 por ser los restos de divisiones por g(x). ¤

Nuestro objetivo ahora consiste en determinar los sındromes de las per-

mutaciones cıclicas de y. Concretamente, vamos a probar que el sındrome de

xy(x), que denotaremos por s1(x), esta relacionado con s(x) por la formula

s1(x) =

{xs(x) si grad(s(x)) < n− k − 1

xs(x)− sn−k−1g(x) si grad(s(x)) = n− k − 1.(9.2)

Para probar esta relacion, partimos de la division entera de y(x) por g(x):

y(x) = g(x)C(x) + s(x). (9.3)

Sabemos, por el Teorema anterior, que s(x) es el sındrome de y(x). Si mul-

tiplicamos la igualdad anterior por x, resulta

xy(x) = g(x)C(x)x + xs(x). (9.4)

Si xs(x) tiene grado menor o igual que n− k− 1, entonces el teorema prece-

dente nos garantiza que xs(x) es el sındrome de xy(x), por ser el resto de la

division de xy(x) por g(x). Pero el grado de xs(x) puede ser igual a n−k−1.

Si este es el caso, procederemos como sigue. Expresamos s(x) en la forma

s(x) = s(x) + sn−k−1xn−k−1, donde s(x) =

n−k−2∑i=0

sixi y g(x) = g(x) + xn−k,

donde g(x) =n−k−1∑

i=0

gixi. Calculamos xs(x):

xs(x) = xs(x) + sn−k−1xn−k.


Como xn−k = g(x)− g(x), sustituyendo en la igualdad anterior, obtenemos

xs(x) = xs(x) + sn−k−1(g(x)− g(x)) = sn−k−1g(x) + (xs(x)− sn−k−1g(x)).

Sustituyendo la expresion obtenida de xs(x) en (9.4), resulta

xy(x) = g(x)C(x)x + sn−k−1g(x) + xs(x)− sn−k−1g(x) =

= g(x)(xC(x) + sn−k−1

)+ s1(x),

donde s1(x) = xs(x)− sn−k−1g(x). Como el grado de s1(x) es menor o igual

que n− k − 1, se sigue que la igualdad

xy(x) = g(x)(xC(x) + sn−k−1

)+ s1(x)

es la division entera de xy(x) por g(x). Esto permite afirmar, en virtud del

teorema precedente, que s1(x) es el sındrome de xy(x), con lo que queda

probada la relacion (??)

9.6. Decodificacion cıclica

En principio, el proceso de decodificacion con un codigo cıclico sigue el

esquema sındrome-lıder valido para cualquier codigo lineal. Hemos visto que

su mayor inconveniente radica en el enorme tamano de la tabla necesaria

para desarrollar el metodo. No obstante, en el caso de los codigos cıclicos

hay la posibilidad de reducir de forma importante el tamano de la tabla. El

metodo que vamos a desarrollar a continuacion se denomina decodificacion

cıclica.

Se construye una tabla reducida de sındromes y lıderes que contenga

unicamente a los lıderes cuya coordenada ultima es no nula. Por ello, cuando

se calcula el sındrome de una cadena recibida cuya ultima componente es

correcta, este no aparece en la tabla reducida pues, en caso contrario, al co-

rregir la cadena con el lıder correspondiente alteramos la ultima componente

y hemos supuesto que era correcta. Una vez elaborada la tabla reducida, se

procede como sigue.

9.6. DECODIFICACION CICLICA 153

Recibida una cadena y = c + e = y0, y1, y2, .., yn−1 (con un numero de

errores t menor o igual que la capacidad correctora del codigo), supongamos

que la componente erronea que esta situada mas a la derecha es yk. Aplicando

n− k− 1 permutaciones cıclicas a la cadena y, esta se convierte en otra, que

denotamos por πh(y) = πh(c) + πh(e), con la ultima componente erronea. El

sındrome s(πh((y)) sı aparecera en la tabla reducida, lo que permite corrigir

πh(y) con el lıder correspondiente, obteniendo una palabra-codigo d. Como

el codigo es cıclico, πh(c) es una palabra-codigo. Por otra parte, es obvio que

ω(e) = ω(πh(e)) ≤ t. Como d(πh(c), πh(y)) = ω(πh(e)) ≤ t, se sigue que

tambien d(d, πh(y)) ≤ t. Por tanto, se tiene

d(d, πh(c)) ≤ d(d, πh(y)) + d(πh(y), πh(c)) ≤ 2t ≤ 2(d− 1

2

)= d− 1 < d,

lo que es imposible, salvo que d = πh(c).

Vemos, pues, que hemos sido capaces de determinar correctamente πh(c),

es decir, conocemos una permutacion cıclica de la palabra-codigo buscada.

Para determinar c, basta aplicar k + 1 permutaciones cıclicas sucesivas a

πh(c). El razonamiento anterior tiene el inconveniente de que no conocemos

la posicion que ocupa el error que esta situado mas a la derecha, pero este

inconveniente puede subsanarse en la practica procediendo como se indica a

continuacion.

1) Se van calculando los sındromes de las permutaciones cıclicas de la

palabra recibida y = c+ e hasta encontrar el primero que aparece en la tabla

reducida: s(πh(y)).

2) Corregimos πh(y) con el lıder correspondiente de la tabla y obtenemos

πh(c).

3) Se hacen n− h permutaciones cıclicas a πh(c) y encontramos c.

Si se quiere realizar estas operaciones de un modo automatico, deberemos

introducir un contador que recoja el numero de permutaciones cıclicas que

aplicamos a y, hasta que encontramos el primer sındrome que pertenece a la

tabla reducida.


Ejemplo 9.6.1. Consideremos el codigo de Hamming H3 cuya matriz de

control tiene la forma

H =

1 0 0 1 0 1 1

0 1 0 1 1 1 0

0 0 1 0 1 1 1

En este caso n = 7 y n − k = 3, por tanto, k = 4 es la dimension del

codigo. El numero de palabras-codigo es M = 2k = 16 y el numero de cadenas

posibles es 27 = 128. Entonces el numero de clases adjuntas es 128/16 = 8.

La tabla completa de sındromes y lıderes es la siguiente

Sındrome Lıder

000 0000000

100 1000000

010 0100000

001 0010000

110 0001000

011 0000100

111 0000010

101 0000001

Mientras que la tabla reducida tiene la forma simple siguiente

Sındrome Lıder

101 0000001

Supongamos que se transmite por el canal la palabra-codigo c = 1001011

y se recibe y = 1001111. Procedemos a calcular los sındromes de las sucesivas

permutaciones cıclicas de y hasta que se obtenga uno que pertenece a la tabla

reducida

πh(y) Sındrome

1001111 011

1100111 111

1110011 101

9.7. EL METODO DE CAPTURA DEL ERROR 155

Vemos que el sındrome de π2(y) esta en la tabla reducida y podemos corregirla

con el correspondiente lıder 0000001, resultando π2(c) = π2(c) + 0000001 =

1110010. Haciendo 5 permutaciones cıclicas sucesivas de esta cadena, obte-

nemos c = 1001011.

9.7. El metodo de captura del error

Definicion 9.7.1. Diremos que una cadena c = c1c2 · · · cn contiene una serie

cıclica de k ceros si en la cadena existen k ceros consecutivos (en sentido

amplio, es decir, los ceros pueden estar al final de la cadena y enlazar con

ceros del principio).

Ejemplos 9.7.2. 1. c = 01000101 es una cadena con una serie cıclica de tres

ceros.

2. c = 00110100 es una cadena con una serie cıclica de 4 ceros.

Notese que toda rafaga cıclica de longitud t contiene una serie cıclica de

n− t ceros.

Lema 9.7.3. Sea C un codigo lineal con distancia mınima d. En una clase

adjunta no puede haber dos cadenas con peso menor o igual que [d−12

].

DEMOSTRACION: Sean x e y dos cadenas diferentes tales que ω(x), ω(y) ≤t = [d−1

2]. Si pertenecen a la misma clase adjunta, entonces x − y ∈ C. Por

otra parte, se tiene

ω(x− y) ≤ ω(x) + ω(y) ≤ 2t ≤ 2(d− 1

2) = d− 1,

lo que es imposible por ser el peso mınimo del codigo d. ¤


Consideremos un codigo lineal C(n, k) con distancia mınima d = 2t + 1

y con una matriz de control de la forma H = [In−k A]. Si se transmite por

el canal una palabra-codigo c y se produce un error e, se recibe una cadena

y = c+e. Supongamos que el error tiene peso menor o igual que t y calculemos

su sındrome

s = Hyt = H(c + e)t = Het.

Si e = (st, 0), entonces se tiene

Het = [In−k A]

(s

0

)= In−ks + A · 0 = s.

Vemos que los sındromes de e y e coinciden. Si suponemos que ω(s) ≤ t,

entonces ω(e) ≤ t. Como e y e pertenecen a la misma clase adjunta (por

tener el mismo sındrome) y ambos tienen peso menor o igual que t, se sigue

del Lema anterior que deben ser iguales: e = e. Seguidamente, vamos a tratar

de sacarle partido a este hecho en relacion con los codigos cıclicos.

Sea e un error que posee una serie cıclica de k ceros y con peso ω(e) ≤ t.

Haciendo un numero i conveniente de permutaciones cıclicas a e, lo conver-

timos en una cadena con k ceros en los ultimos lugares. xe(x) es, en forma

polinomica el resultado de aplicar a e(x) las i permutaciones cıclicas. La for-

ma matricial de xe(x) sera (b, O), donde O es una matriz columna de k ceros.

Si denotamos por si el sındrome de xie(x), veamos que su peso es menor o

igual que t:

si = [In−k A]

(b

0

)= In−kb = b.

Por tanto, el numero de componentes no nulas de si(x) es igual al numero de

elementos no nulos que hay en b, que es el peso de xie(x) = ω(e) ≤ t. Ahora

podemos aplicar a la cadena xie(x) (que tiene un sındrome si co peso menor

o igual que t) el resultado precedente para deducir que

xie(x) = (sti, 0).

9.7. EL METODO DE CAPTURA DEL ERROR 157

De esta forma, hemos encontrado una expresion para xie(x) que nos va a

permitir encontrar el propio e. Como xn es congruente con 1 modulo xn − 1,

se tiene

e(x) = xne(x) = xn−i(xie(x)) = xn−i(sti, 0).

Es decir, si i es el numero de permutaciones cıclicas que permite convertir e

en una cadena con k ceros al final, entonces se obtiene e(x) haciendo n − i

permutaciones cıclicas a (sti, 0).

Veamos como se procede en la practica. Consideremos un codigo cıcli-

co C(n, k) con polinomio generador g(x) de grado n − k y distancia mıni-

ma d = 2t + 1. Si se transmite la palabra-codigo c y se recibe y = c + e,

el error cometido es e. Si ω(e) ≤ t = [d−12

], entonces sabemos que el e-

rror puede corregirse. Pero ahora vamos a decodificar por el procedimiento

anterior. Para ello, hay que estar seguros de que el error poese una serie

cıclica de k ceros (esto no es un grave condicionamiento ya que e es una

cadena con muchos ceros). Con esto asegurado, procedemos a calcular los

sındromes s0(x), s1(x), ..., de y(x), xy(x), x2y(x), .... (los si(x) se determinan

mediante la relacion de recurrencia que hemos estudiado con anterioridad).

Cuando encontremos el primer si(x) con peso menor o igual que t, ponemos

e(x) = xn−i(sti, 0) y se decodifica poniendo c(x) = y(x)− e(x). La idea basica

es la siguiente: como sabemos que e(x) tiene una serie cıclica de k ceros,

debe haber un valor de i tal que al aplicar i permutaciones cıclicas a e(x) lo

convierte en una cadena con k ceros al final y, segun hemos visto, el sındrome

si(x) debe tener peso menor o igual que t, lo que nos permitıa encontrar el

valor de e(x). Nosotros no conocemos el error e y, por tanto, tampoco sabe-

mos el valor de i. Por ello, vamos calculando los sucesivos sındromes hasta

hallar el primero cuyo peso es menor o igual que t.

Ejemplo 9.7.4. Consideremos el codigo binario cıclico C(7, 4) generado por

el polinomio generador g(x) = 1 + x + x3. Usar el metodo captura del error

para decodificar: a) y = 1101001, b) y = 0001111.


Primero buscamos una matriz generadora de la forma G = [AIk]. Para

ello, debemos hacer las divisiones enteras de xn−k+i por g(x), para i =

0, 1, .., k − 1. En nuestro caso n − k = 3 y encontramos los resultados sigui-

entes:

x3 = g(x) · 1 + (−x− 1), x4 = g(x) · x + (−x2 − x),

x5 = g(x) · (x2 − 1) + (−x2 + x + 1), x6 = g(x) · (x3 − x− 1) + (x2 + 1).

Recordemos que la matriz G tiene por filas los coeficientes, en orden creciente

de las potencias de x, de los polinomios xn−k+i−Ri(x), siendo Ri(x) los restos

de las divisiones anteriores. Por tanto, la matriz generadora buscada es

G =

1 1 0 1 0 0 0

0 1 1 0 1 0 0

1 1 1 0 0 1 0

1 0 1 0 0 0 1

Ahora debemos encontrar una matriz de control. Sabemos que tiene la forma

H = [In−k At], luego se trata de la matriz

H =

1 0 0 1 0 1 1

0 1 0 1 1 1 0

0 0 1 0 1 1 1

Se trata de la matriz de control de un codigo de Hamming H(7, 4), luego es

1-corrector y su distancia mınima es d = 3. Podemos aplicar el metodo de

captura del error con t = 1. Si el error tiene peso 1, e es una cadena de 7

ceros y unos con un solo 1 en un lugar desconocido. Entonces es obvio que

e es una cadena con una serie cıclica de 6 ceros. Como 6 ≥ k = 4, puede

aplicarse el metodo para determinar el error e.

a) y = 1101001. Usamos la notacion polinomica y(x) = 1 + x + x3 + x6 y

determinamos su sındrome haciendo la division entera por g(x):

y(x) = g(x) · (x3 + x) + (1 + x2).

9.8. CODIGOS CICLICOS CON MATLAB 159

Por tanto, el sındrome es s0(x) = 1 + x2, cuyo peso es 2. Tenemos que seguir

calculando los sındromes de xiy(x), que denotamos por si(x), hasta encontrar

el primero que tiene peso menor o igual que 1. Para determinar los sucesivos

sındromes, usamos la relacion de recurrencia (??):

s1(x) =

{xs(x) si grad(s(x)) < n− k − 1

xs(x)− sn−k−1g(x) si grad(s(x)) = n− k − 1.

Como el coeficiente lıder de s0(x) es 1, s1(x) = xs(x)−1·g(x) = 1. Vemos que

el peso es uno, luego e(x) = x7−1s1(x) = x6. Es decir, el error viene dado por

e = 00000001 y se decodifica y por c = y−e = 1101001−0000001 = 1101000.

b) y = 0001111. Ahora y(x) = x3 + x4 + x5 + x6. Hacemos la division por

g(x) para obtener el sındrome s0(x):

y(x) = g(x) · (x3 + x2 + 1) + (1 + x + x2).

Como s0(x) = 1 + x + x2 tiene peso 3 debemos seguir. La relacion de recu-

rrencia nos permite obtener s1(x) = xs0(x) − 1g(x) = 1 + x2. Buscamos el

siguiente sındrome: s2(x) = xs1(x)− 1g(x) = 1. Como el peso de s2(x) es 1,

hemos terminado. El error viene dado por e(x) = x7−2s2(x) = x5. Entonces

se decodifica poniendo c = y − e = 0001111− 0000010 = 0001101.

9.8. Codigos cıclicos con MATLAB

La funcion cyclpoly produce el polinomio generador del codigo cıclico.

Concretamente, en pantalla aparece una fila con los coeficientes en orden

creciente de las potencias de x.

>> g=cyclpoly(7,3)

ans 1 0 1 1 1

que son los coeficientes del polinomio generador, g(x), de un codigo cıclico

C(7, 3). Es decir, g(x) = 1+x2+x3+x4. Para obtener las matrices generadoras

y de control, se procede como sigue


>>[parmat,genmat]=cyclgen(7,g)

ans

parmat =

1 0 0 0 1 1 0

0 1 0 0 0 1 1

0 0 1 0 1 1 1

0 0 0 1 1 0 1

genmat =

1 0 1 1 1 0 0

1 1 1 0 0 1 0

0 1 1 1 0 0 1

Notese que la matriz generadora tiene la forma estandar G = [BI3]. Para

codificar un mensaje con un codigo cıclico, MATLAB dispone de la funcion

encode:

>> n=7;k=3;

g=cyclpoly(7,3);

[parmat,genmat]=cyclgen(7,g);

msg=[1 0 1];

codmsg=encode(msg,n,k,’cyclic’,g)

ans

codmsg = [1 1 0 0 1 0 1].

Para decodificar un mensaje recibido se usa la funcion decode:

>> x=decode(codmsg,7,3,’cyclic’,g)

9.9. Ejercicios

1. Comprobar que g(x) = 1 + x2 + x3 + x4 es un divisor de f(x) = x7 − 1 y

determinar el ideal generado por g(x).

2. Determinar el numero de subespacios cıclicos de cada uno de los siguientes

espacios vectoriales: a) A8, siendo A el alfabeto binario, b) A4, siendo

A = {0, 1, 2} = Z3.

9.9. EJERCICIOS 161

3. Determinar el polinomio generador y la dimension del menor codigo cıclico

binario que contiene: a) c = 1010011, b) c = 0011010.

4. El polinomio g(x) = 1 + x3 + x6 genera un codigo binario cıclico C(9, 3).

a) Escribe una matriz generadora de la forma G = [R I3] para C. b)

Determina una matriz de control H y encuentra los sındromes de dos

formas diferentes.

5. Sea G una matriz generadora de un codigo lineal C con la propiedad de

que cualquier permutacion cıclica de una fila de G es tambien una palabra-

codigo. Probar que C es un codigo cıclico.

6. El polinomio g(x) = 1 + x + x2 + x3 + x6 genera un codigo cıclico binario

C(15, 9). Codificar los siguientes mensajes polinomicos: a) 1+x2 +x5 +x8,

b) 1 + x + x2.

7. Consideremos el codigo del ejercicio anterior. Encontrar una matriz gene-

radora de la forma G = [R Ik] y codificar los mensajes polinomicos.

8. Un codigo cıclico binario C(7, 4) esta generado por el polinomio g(x) =

1+x+x3. Decodificar cada uno de las cadenas recibidas usando el metodo

de captura del error”: a) y = 1101011, b) y = 0101111.

9. Sea g(x) el polinomio generador de un codigo cıclico binario C. Denotamos

por CP el conjunto formado por las palabras-codigo de peso par. ¿Es

CP un codigo cıclico? Si la respuesta es afirmativa, obtener un polinomio

generador para CP .

10. Elaborar un programa para decodificar un mensaje codificado con un

codigo cıclico por el procedimiento de decodificacion cıclica.

Documents

Codigos Ciclicos