Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Código de Golay

Mi casa
by

Max Zanatoz

on 7 May 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Código de Golay

Códigos de Golay Se trata de un código corrector de errores linear perfecto. Cumple con el teorema que dice: Un código es perfecto si y solo si la distancia es impar y se alcanza la igualdad en la cota de Hamming. d=2t+1 sea impar y Definición t= número de errores. M= 2^k q= es el tamaño del alfabeto (en este caso 2). Se debe notar de la existencia de numeros n, M y t que satisfacen la cota de Hamming.

Como n= 90, M=2^78 y t=2. ya que Es decir: (2^78)(2^12)=2^90 Pero no implica la existencia de un código perfecto con parametros (n, M, 2t+1). Para esto existen algunas relaciones de combinatoria que nos indican la existencia del código. Por ejemplo: Si C es un (n, M, d)- código binario perfecto entonces los números: son enteros para todo 1<=s<=t Retomando el ejemplo tenemos: Luego, no existe un código binario perfecto con parametros (90, 2^78, 5) Hay dos versiones distintas de Códigos Golay La versión binaria. La versión ternaria La versión binaria: Se denota por G 23 Tiene como parametros (23, 12, 7) En consecuencia tiene 2^12 palabras de código. La versión ternaria: Tiene como parametros (11, 6, 5) En consecuencia tiene 3^6 palabras de código. Longitud 11. Código binario de Golay (23,12,7) de n= 23, k=12, d=7 Donde r es la redundancia = n-k y d es la distancia mínima donde: Códificación La matriz generadora G se útiliza en el codificador en donde: C= i*G Código binario de Golay (24,12,8)
EXTENDIDO de n= 24, k=12, d=8 Corrige 3 errores y detecta más errores que el Código (23,12,7) debido a que se le agrega un bit más de redundancia. Decodificación 1.Se calcula el síndrome s=rHT , así como su peso w(s)
2.Si su peso w(s)=0 , aquí termina el procedimiento porque no hay error en la palabra recibida
3.Si w(s) es menor o igual a t (que en este caso es 3) entonces la palabra enviada c= r- (s<<k), sino pasa al siguiente punto
4.Busca s en la tabla, si está entonces la palabra recibida es c=r-ei , sino pasa al siguiente punto
5.Calcula sd=s-si , donde si va a ser el síndrome de la tabla al que más se acerque s, y calcula el peso de w(sd)
6.Si w(sd) es menor o igual a 1, entonces c= r – (sd << k)-ei, sino pasa al siguiente punto
7.Se calcula r’ = (corrimiento a la izquierda de los n-k bits en) r, y calcula el síndrome s’=r’HT y su peso
8.Si w(s’)=t , entonces c=r-(s<<k), entonces c’=r’-(s’<<k)
9.Así que c=(corrimiento a la derecha de los n-k bits) de c’
10.Si en 9 w(s’)=t calcula sd’=s’-sd y calcula c’=r’-(s<<k)-ei y regresa al paso 9 Ejemplo: La palabra m=(100000000000) es codificada en la palabra de código c=(10101110001100000000000) . Si la palabra recibida es r=(10111110001100010001000) el procedimiento para decodificarle es:
1. Calculamos el síndrome s=rHT =(10000110010) y su peso w(s)=4
2. Como su peso no es 0, seguimos con el algoritmo
3. Como el peso no es menor a 3, vamos al paso siguiente.
4. s no está en la tabla así que pasamos al siguiente paso
5. sd=s-si=s-s46=(10000110010)-(10010110010)=(00010000000) y su peso w(sd)=1
6. Como el síndrome es igual a 1 la palabra enviada está dada por c=r – (sd Aplicaciones Polinomio generador Sea C un código cíclio (n,k) sobre un determinado campo GF(q). El polinomio generador es único. El grado del polinomio generador es n-k. En caso de existir dos polinomios generadores, | cada uno de ellos debería ser divisor del mismo. Los códigos de Golay binarios La descomposición factorial de X^23+1 es: x^23+1=(x+1)(x^11+x^10+x^6+x^5+x^4+x^2+1) (x^11+x^9+x^7+x^6+x^5+x+1) Pongamos f1=x^11+x^10+x^6+x^5+x^4+x^2+1 f2=x^11+x^9+x^7+x^6+x^5+x+1 Si se consideran los códigos cíclicos C1 y C2 engendrados por f1 y f2, respecivamente. Ambos tienden a 2^23 como espacio ambiente. Por esta razón el polinomio generador esta dado por: g(x)= x^11+x^9+x^7+x^6+x^5+x+1 Grado: n-k = 11
n = 23
k = 12 y por consiguiente con polinomio revisor de paridad h(x)=(X^23+1)/(g(x))=
1+x^2+x^5+x^8+x^9+x^10+x^11+x^12
es perfecto para 3 errores. Las matrices generadoras de los polinomios generadores están dadas por: Teorema. El código de Golay G23 es perfecto. Demostración: El código G23 tiene 2^12=4096 palabras,
mientas que el espacio ambiente tiene 2^23=8388608.
El número de palabras en cada esfera de centro una palabra de código y radio 3 es: Habrá 2^12*2^11=2^23 palabras,
lo que cubre todo el espacio ambiente.
Así G23 es perfecto. Código Golay ternario Es (11,6)
No binario perfecto
Corrige dos errores Distancia mínima más grande que otros códigos con (n,k)
Matriz de verificación de paridad: Puede ser extendido a (12,6)
Se agrega un bit de verificación
Full transcript