Codigo De Redundancia Ciclica

• Códigos polinómicos o de redundancia cíclica
- Conceptos previos
• Es natural contar de forma cíclica

Códigos para tratamiento de errores

- LOS GRADOS: Supongamos que contamos un número de grados entero. El orden es: 0, 1, 2, ..., 45, ..., 180, ..., 357, 358, 359, 360=0, 1, etc.

90º 180º 270º
Escuela Politécnica Superior

0º=360º

Códigos para tratamiento de errores
• Códigospolinómicos o de redundancia cíclica
- Conceptos previos
- LOS GRADOS: Es fácil operar » El siguiente a 359 es 0 » El anterior a 0 es 359 » Tres más que 358 es 1 » Cinco menos que 2 es 357

Escuela Politécnica Superior

Códigos para tratamiento de errores
• Códigos polinómicos o de redundancia cíclica
- Conceptos previos
El orden es 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,16, 17, 18, 19, 20, 21, 22, 23, 0, 1, ... - LAS HORAS DEL DÍA

6h

12h
Y operar es como antes
Escuela Politécnica Superior

0h=24h 18h

Códigos para tratamiento de errores
• Códigos polinómicos o de redundancia cíclica
- Conceptos previos • El conjunto de los enteros módulo 2
- {0, 1} - Su orden cíclico

1

0

- Las operaciones pueden representarse con tablas 1+1=0 0-1=1

+0 0 0 1 1

1 1 0

0 1

0 0 1

1 1 0

* 0 1

0 0 0

1 0 1

Escuela Politécnica Superior

Códigos para tratamiento de errores
• Códigos polinómicos o de redundancia cíclica
- Conceptos previos • Observaciones sobre los polinomios Q[x] - División de polinomios con coeficientes racionales (Q)
Ejemplo: D = 6x4 + 9x3 + 5x + 2 y d = 2x2 - 1 +2 2x2 +0x -1 3x2 +(9/2)x +(3/2) +9x3+0x2 +5x +0x3 -3x2 +9x3 +3x2 0x3 +3x2 +3x2 +5x +(19/2)x +2 +0x -(3/2) +(19/2)x +(7/2)

6x4 6x4 0x4

+9x3 +0x2 -(9/2)x

0x2

Se obtiene: q = 3x2 + (9/2)x + (3/2) y r = (19/2)x + (7/2)
Escuela Politécnica Superior

Códigos para tratamiento de errores
• Códigos polinómicos o de redundancia cíclica
- Conceptos previos • Observaciones sobre los polinomios Q[x]
9 0 9 9 0 0 -3 +3 0 3 3 5-(9/2) +(19/2) 0 (19/2) 2 -(3/2) +(7/2) 5 2 2 3 0 9/2 Ejemplo: Se puede representar abreviadamente: -1 3/2

6 6 0

0

Escuela Politécnica Superior

• Códigos polinómicos o de redundancia cíclica
- Conceptos previos
• Polinomios con coeficientes enteros módulo 2

Códigos para tratamiento de errores

- Se puede demostrar (no objeto de este curso) que esta división también es posiblecuando los coeficientes son enteros módulo 2 siempre que las operaciones (resta, productos, etc.) sean definidas en ese conjunto - Ejemplo: D = x13 + x12 + x10 + x8 + x7 + x5 + x4 y d = x4 + x + 1 10011 1 1 0 1 0 1101 1 0 000
1 00 1 1 01 0 0 1 1 1 00 1 1 000 001 0 1 1 00 0 01 1 0 1100001010

1 0 0 1 0 0
1 1 00 1 1 0 1 1 10

Resultado: q = x9 + x8 + x3 + x y r = x3 + x2 + x
EscuelaPolitécnica Superior

Códigos para tratamiento de errores
• Códigos polinómicos o de redundancia cíclica
- Presentación de la técnica
• Se interpretan las cadenas de 1’s y 0’s como coeficientes enteros módulo 2 de polinomios • Los k bits de cada mensaje se tratan como si fueran los coeficientes de un polinomio M(x), de orden k-1, en el que las operaciones se hacen en módulo 2 • Si el mensaje fuese:10010110 el polinomio considerado sería: M(x) = 1 • x7 + 0 • x6 + 0 • x5 + 1 • x4 + 0 • x3 + 1 • x2 + 1 • x1 + 0 • x0 = = x7 + x4 + x2 + x • Se utiliza un polinomio generador G(x) de grado r. Este polinomio está predeterminado, y es el mismo en el emisor y el receptor
Escuela Politécnica Superior

Códigos para tratamiento de errores
• Códigos polinómicos o de redundancia cíclica
-Presentación de la técnica
• Operaciones en módulo 2: 0+0=0 0+1=1 1+0=1 1 + 1 = 0 (sin acarreo) 0–0=0 0 – 1 = 1 (sin acarreo) 1–0=1 1–1=0

Escuela Politécnica Superior

Códigos para tratamiento de errores
• Códigos polinómicos o de redundancia cíclica
- Presentación de la técnica
• Objetivo del procedimiento: Añadir r bits al mensaje de k bits, de forma tal que el polinomio resultante, T(x),...