PDF de programación - Lección 13: Codificación de Canal

Lección 13: Codificación de Canal.

Parte III

Gianluca Cornetta, Ph.D.
Dep. de Ingeniería de Sistemas de Información y Telecomunicación
Universidad San Pablo-CEU

Contenido

Utilidad de la Matriz Estándar
Códigos Cíclicos
Códigos de Hamming

04/04/2013

© 2012 Gianluca Cornetta, Comunicaciones Digitales

2

Utilidad de la Matriz Estándar

 La matriz estándar es una herramienta muy potente que
permite estudiar la capacidad de detección y corrección de
un código de bloque lineal (n, k) incluso para códigos con n
grande

 Un indicador de las capacidad de un código de detectar y

corregir t errores es límite de Hamming (Hamming bound)

 El límite de Hamming permite establecer cuál es el mínimo
número de bits de paridad o de filas de la matriz estándar
necesarios para corregir todas las posibles combinaciones
de t errores y es definido como:

04/04/2013

© 2012 Gianluca Cornetta, Comunicaciones Digitales

3

tnnntnnnn-kn-k2112:cosets ofNumber 211log:bitsparity ofNumber 2Utilidad de la Matriz Estándar

 La capacidad de detección y corrección de error de un
código (n, k) depende de la distancia mínima dmin entre
palabras y viceversa

 El número mínimo t de errores que se desea corregir
determina pues la distancia de Hamming mínima del código
dmin :



 El t mínimo deseable en t=2 lo que lleva a una distancia

mínima dmin =5

 Es deseable poder transmitir al menos 2 bits de dato por
cada palabra de código (es decir, el código más sencillo debe
ser de tipo (n, 2) y tener pues k=2)

 Cuando k=2 el espacio de las n-tuplas tiene 2k=4 elementos

que corresponden a las 4 posibles palabras de código

04/04/2013

© 2012 Gianluca Cornetta, Comunicaciones Digitales

4

1221minmintddtUtilidad de la Matriz Estándar
 k=t=2 se utilizan para determinar el límite de Hamming mínimo



 La desigualdad anterior se resuelve numéricamente encontrando que el

valor mínimo de n que la satisface es n=7:



 Es deseable diseñar un código con n mínimo por cuestiones de eficiencia

de banda y sencillez de implementación

 Por tanto el código de dimensiones mínimas es el (7, 2). La matriz
generadora G de este código está formada por k=2 7-tuplas linealmente
independiente y cada 7-tupla está formada por 5 bits de paridad y 2 de
dato

04/04/2013

© 2012 Gianluca Cornetta, Comunicaciones Digitales

5

21122nnn-2921712717132221!27!2!7277!17!1!71727-Utilidad de la Matriz Estándar
 Una posible matriz generadora del código (7, 2) es:



 Es fácil verificar que las dos filas de G forman una base del
subespacio S de V7 ya que V1 + V2  {V1, V2} y V1 + V2  S
 El código U2 relativo al mensaje m2 = [0 1] se calcula como:



 Recordando que:

 Se observa que el código no (7, 2) con la restricción dmin =5

ya que por este código dmin =3

04/04/2013

© 2012 Gianluca Cornetta, Comunicaciones Digitales

6

10001100110011|221IPVVG1000110100011001100111022GmU3,min221minUUUwwwdUtilidad de la Matriz Estándar

 Por consiguiente el límite de Hamming no es una condición suficiente para

el código (7, 2)

 Es necesario verificar el cumplimiento de otro límite que se denomina

límite de Plotkin:



 En general un código de bloque lineal (n, k) debe cumplir con ambos

límites con las siguientes diferencias:
 Para códigos con relación de código k/n elevada, si el código cumple con el

límite de Hamming entonces satisfará también el límite de Plotkin

 Para códigos con relación de código k/n baja (como es el caso de este ejemplo),
si el código cumple con el límite de Plotkin entonces satisfará también el límite
de Hamming

 Por consiguiente el código más pequeño que asegura dmin =5 es el (8, 2)
 Obviamente se trata de un código realizable pero poco práctico debido a su
baja eficiencia de banda ya que 2 bits de dato implican la transmisión de 6
bits de paridad

04/04/2013

© 2012 Gianluca Cornetta, Comunicaciones Digitales

7

1221minkkndUtilidad de la Matriz Estándar

 La matriz generadora del código (8, 2) es:



 La operación de detección empieza calculando el síndrome del
código (n, k), por ello es necesario determinar la transpuesta HT de
la matriz de control de paridad H

 HT es una matriz n(n-k), por lo que para un código (8, 2) es:



04/04/2013

© 2012 Gianluca Cornetta, Comunicaciones Digitales

8

1000111101111100|2IPG0011111111001000000100000010000001000000100000016PIHTUtilidad de la Matriz Estándar

 El síndrome por cada uno de los posible 2n-k patrones de error es Si =eiHT, con

i=1,…, 2n-k
 ei representa el i-ésimo líder de coset (una fila de la matriz estándar), es decir, uno de los 2n-k

patrones de error que pueden perturbar todos los posibles 2k códigos Uj del conjunto

 Utilizando esta ecuación se construye la tabla de síndromes que permite detectar el

patrón de error que corresponde a un síndrome dado

 El patrón de error estimado se suma (módulo 2) al código corrompido recibido por

el detector para calcular el código correcto

 Un código suele ser diseñado para corregir  errores y detectar simultáneamente 

errores (  ) siempre que se cumpla la condición siguiente:



 Por tanto existen las siguientes posibilidades:



Detect ()

Correct ()

2
3
4



2
1
0

04/04/2013

© 2012 Gianluca Cornetta, Comunicaciones Digitales

9

41511minminddUtilidad de la Matriz Estándar

 La detección es un proceso sencillo ya que un error es
detectado si el síndrome del vector recibido es distinto de
cero

 El proceso de corrección es más complejo ya que implica
también detectar el patrón de error que ha generado un
síndrome dado para poderlo corregir

 Esto proceso equivale a realizar las siguientes operaciones

(en el caso de nuestro código (8, 2)):

04/04/2013

© 2012 Gianluca Cornetta, Comunicaciones Digitales

10

7667558744873382281187654321001111111100100000010000001000000100000010000001rrsrrsrrrsrrrsrrsrrsrrrrrrrrHrTiiSUtilidad de la Matriz Estándar

 La complejidad de la tabla de corrección depende del número de errores simultáneos

(1 ó 2) que se desea corregir

 En el caso de corrección de error sencillo ( =1)el decodificador se diseña para evaluar

sólo los primeros 9 cosets de la matriz estándar entre los 64 posibles

 En el caso de corrección hasta error dobles ( =2)el decodificador se diseña para

evaluar sólo los primeros 37 cosets de la matriz estándar entre los 64 posibles

 Los cosets de 38 a 64 se utilizan para la corrección de un subconjunto de errores triples
(26 de los 53 posibles). Estos cosets no se utilizan en decodificadores de distancia
limitada (los cuales sólo corrigen hasta errores de orden t)

 Un código (n, k) diseñado para corregir errores hasta grado t no puede ser
reorganizado para corregir sólo errores de tipo t+1 ,aunque la matriz estándar tenga el
tamaño suficiente para contener todos los cosets relativos a estos tipo de error

 El único parámetro que fija el máximo número de errores simultáneos errores es posible corregir es

la distancia de Hamming mínima dmin (dmin =5 impone t=2)

 Una secuencia de x bits erróneos sólo podría ser corregible si todos los vectores de peso x son
líderes de coset (es decir, sólo aparecen en la primera columna de la matriz estándar), si un vector
de peso x aparece en alguna otra columna el error no es corregible incluso si la matriz estándar
tiene tamaño suficiente para contener todos los patrones de error de peso x

04/04/2013

© 2012 Gianluca Cornetta, Comunicaciones Digitales

11

Códigos Cíclicos

 Los códigos cíclicos binarios son una subclase muy importante de los códigos

de bloque lineales

 Esta clase de códigos puede implementarse fácilmente utilizando un registro

de desplazamiento realimentado lineal (Linear Feedback Shift Register –LFSR)

 El síndrome puede calcularse utilizando registros análogos
 Un código lineal es (n, k) es un código cíclico cuando se verifica la siguiente

condición:
 Si la n-tupla es un código U=(u0, u1,…, un-1) en el subespacio S  también
U(1)=(un-1, u0, u1,…, un-2), obtenido rotando U en sentido horario una única vez,
pertenece a S

 En general U(i)=(un-i, un-i+1,…, un-1, u0, u1,…, un-i-1), obtenido rotando U en

sentido horario i veces, todavía es un elemento de S

 Los componentes de U=(u0, u1,…, un-1) pueden considerarse como los

coeficientes de un polinomio de grado n -1:



 En general, una n-tupla es descrita por un polinomio de grado menor o igual a

n -1

04/04/2013

© 2012 Gianluca Cornetta, Comunicaciones Digitales

12

1,0112210innuXuXuXuuXUCódigos Cíclicos

 Si U(X) es un polinomio de grado n -1  U(i)(X) es el resto de la división

XiU(X)/(Xn+1), es decir:



 Multiplicando ambos miembros por se obtiene (Xn+1):



 O, de forma equivalente, en términos de artimética modular:



 Consideremos la expresión anterior para el caso i =1:



 Sumando y restando un-1 (en aritmética módulo 2 esta operación equivale a sumar un-1

dos veces) se obtiene:

04/04/2013

© 2012 Gianluca Cornetta, Comunicaciones Digitales

13

11niniXXXXXXUqUremainder1XXXXXiniUqU1modniiXXXXUUnnnnnnnnXuXuX