teoría de códigos (sin animación)
TRANSCRIPT
Teoría de Códigos: polinomios
Javier Artiga Garijo Sonia Escorza Santos
Dariel Figueredo Piñero Arturo Hermosa Moreno
Andrés Tomás Campo
Códigos correctores de errores
• Palabras, códigos y errores – Distancia d(a,b): Desigualdad Triangular, Teorema del
vecino más próximo, Corrección de errores
• Códigos Lineales – Magnitudes: longitud, dimensión, distancia
mínima, generador – Dimensión – Peso ω(z) o Código Lineal: Puntos Cardinales
• Códigos Cíclicos – Ideal – Utilidad de los códigos cíclicos o Código Cíclico: Samoano
Palabras, códigos y errores
Vn = conjunto de palabras binarias de longitud n
Ej.: V = 2 Hay 2n palabras binarias de longitud n
Distancia d(a,b)
i. d(x,y) = 0 ↔ x = y
ii. d(x,y) = δ(x,y)
iii. d(x,y) ≤ d(x,z) + d(z,y)► Desigualdad Triangular
→ distancia mínima δ = min{d(x,y) | a, b c, a ≠ b}
z
x y
Palabras, códigos y errores
Teorema17.1 del Principio del vecino más próximo d ≥ 2e + 1
Dem:
en C
c = palabra −con e errores→ recibe palabra z por (iii) de δ
d(c,z) = e c' = otra palabra
por (iii) de d = des. triangular
por definición de δ
por hipótesis
d(c,z) + d(z,c') ≥ d(c,c')
≥ δ
≥ 2e + 1; e + d(z,c') ≥ 2e + 1 → d(z,c') ≥ e + 1 →
→ c es la única palabra C que está a distancia e de z
Palabras, códigos y errores
• Corrección de errores Representación Gráfica
Palabras, códigos y errores
Códigos Lineales
• Magnitudes
Significado
Longitud n Las palabras son de n bits
Dimensión k Hay 2k palabras disponibles
Distancia mínima δ
Pueden corregirse hasta e
errores, siempre que δ ≥ 2e + 1.
Generador < g(x) >
Polinomio g(x) de un código
cíclico C tal que C = < g(x) >
Teresacto: representación de la cuarta dimensión en un cubo
• Dimensión Relación: representación física
Códigos Lineales
• Peso ω(z) = d(z,0)
d(x,y) = d(x-y, y-y) = d(x-y, 0) = ω(x-y)
Teorema17.2: δ ≥ ωmin
Dem: c* c tal que ω(c*)= ωmin
δ ≤ d(c*,0) = ω(c*) = ωmin
c1,c2 están a distancia mínima c1-c2 c, porque es lineal
δ = d(c1-c2) = ω(c1-c2) ≥ ωmin
Códigos Lineales
Código Lineal: Puntos Cardinales N 1111 NE 1100 NNE 1110 NNW 0111
E 1001 SE 1000 NEE 1101 NWW 0111
W 0110 NW 0101 SSE 1000 SSW 0001
S 0000 SW 0011 SEE 1000 SWW 0010
Los generadores son
cualquier conjunto de
4 palabras, porque
C4 = V4
En el código C4 observamos que la detección de errores es imposible, al pertenecer todas las palabras disponibles a nuestro código.
δmin = ωmin = 1 C4 = V4
Si duplicásemos K tendríamos C8 perteneciente a V8. (código no lineal), y la detección de errores sería muy sencilla, aunque no tanto su
corrección. Las detecciones de un error siempre serían posibles, e incluso la mayoría de las de dos errores, siempre que no sean en
dígitos contiguos y equivalentes a lo que en V4 era un sólo dígito; es decir, siempre que no se dé que, por ejemplo:
a4 = (1101) = a8 = (11 11 00 11), a4 pertenece a V a4 pertenece a C4
a8 pertenece a V a8 pertenece a C8
↓ error ↓
a'4 = (1100) = a'8 = (11 11 00 00), a'4 pertenece a V a'4 pertenece a C4
a'8 pertenece a V a'8 pertenece a C8
En los demás casos (por ejemplo, si b8 = (11.00.11.00) y en la transmisión errónea obtenemos b'8 = (11.00.11.01), resulta que
podemos detectar el error, pero no dispondríamos de información suficiente para su corrección con esta longitud de palabras,
ya que no sabríamos si en el par de dígitos erróneo ha sido confundido el 0 o el 1).
Código Lineal: Puntos Cardinales
N 1111
NNW NNE
0111 1110
NW NE
0101 1100
NWW NEE
0100 1101
W 1001 E 0110
SWW SEE
0010 1000
SW SE
0011 1000
SSW SSE
0001 1000
S 0000
Un código C de Vn es cíclico si es lineal y si corresponde a un ideal de Vn[x].
• Ideal Sea R un anillo con un producto conmutativo. Se dice que un subconjunto S de R es un ideal si
i. a,b s → a+b S (lineal)
ii. r R y a S → ra S
Códigos Cíclicos
C es ideal si a,b C→ a+b C (lineal)
p(x) y a(x) C → p(x)·a(x) C si a(x) C → xa(x) C
En otras palabras, S es cerrado respecto de la suma y respecto del producto por
cualquier elemento de
La construcción de un CC de longitud n es equivalente a la construcción de ideales en Vn[x].
El ideal se denota por <f(x)> y nos referimos a él como el ideal generado por f(x).s
Un código cíclico puede tener más de un generador, pero sólo uno tendrá grado mínimo, que será el
generador canónico de C.
Códigos Cíclicos
• Utilidad de los códigos cíclicos
– Pueden tratarse mediante mecanismos sencillos: registros de desplazamientos*.
– Pueden construirse e investigarse mediante la teoría algebraica de los anillos de polinomios.
Vn Vn[x]
110101 1+x+x3+x5
010110 x+x3+x4
*desplazamientos cíclicos: ejemplo en V6
Código Cíclico: Samoano El idioma samoano (gagana Samoa) es una lengua austronesia del grupo malayo-polinesio oriental, originaria de Samoa y
hablada principalmente en ese país, en la vecina colonia estadounidense de Samoa Americana y en Nueva Zelanda.
Las vocales pueden ser
breves o largas; en el
segundo caso se marcan con
un macrón: (ˉ).
Los fonemas samoanos son 16: 5 vocales y 10 consonantes. Se escribe con un alfabeto latino
de 16 letras, una para representar cada fonema: a, f, g, i, l, m, n, o, p, s, t, u y v.
Adicionalmente, existen las letras h, k y r para escribir préstamos de otros idiomas.
Conocemos las traducciones al castellano de algunas palabras, como
agua = vai, amor = alofa, elefante = elefane, estrella = fetū
montaña = mauga nube = ao, paz = filamu, pilemu, África = Aferika
Traducido a binario
En Z2 y en V8 podemos diseñar un código C perteneciente a V8 con K=4 y 2k=16 palabras o,
en este caso, letras.
Los generadores son las cuatro primeras letras, sin contar la a (porque a = 00000000):
f = 00000101 i = 01010101
g = 00001010 m = 10101010, a partir de las cuales generamos:
A 00000000 S 01011111
F 00000101 T 11111111
G 00001010 U 10100000
I 01010101 V 01011010
M 10101010 L 10100101
N 01010000 H 11111010
O 00001111 K 11110101
P 10101111 R 11110000