ccanal

DEEE - ESPE

Gonzalo Fernando Olmedo Cifuentes

II. Codificaci´
on de Control de Errores

1

DEEE - ESPE

Gonzalo Fernando Olmedo Cifuentes

C´
odigos de Bloque

2

DEEE - ESPE

Gonzalo Fernando Olmedo Cifuentes

C´
odigos de bloques lineales (n, k)
Un c´
odigo de bloque es lineal si dos palabras de c´
odigo al sumarse
en m´
odulo dos producen una tercera palabra del mismo c´
odigo.
n bits dela palabra c´
odigo, {c0 , c1 , c2 , ..., cn−1 }
k bits id´enticos a la secuencia de mensaje que se va a
transmitir, {m0 , m1 , m2 , ..., mk−1 }. Total 2k bloques de
mensajes distintos.
n − k bits de paridad, {b0 , b1 , b2 , ...; bn−k−1 }.
tasa de c´
odigo r =

k
n.

3

DEEE - ESPE

Gonzalo Fernando Olmedo Cifuentes

4

Notaci´
on Matricial
m = [m0 , m1 , ..., mk−1 ]

(1)

b = [b0 , b1 , ...;bn−k−1 ]

(2)

c = [c0 , c1 , ..., cn−1 ]

(3)

Los bits de paridad pueden ser obtenidos por:
b = mP,
donde P es una matriz de orden kx(n − k), dada por:

(4)

DEEE - ESPE

Gonzalo Fernando Olmedo Cifuentes



p00


 p
 10

P=
 .

 .

pk−1,0

donde Pi,j ∈ {0, 1}.

p01

...

p0,n−k−1

p11

...

p1,n−k−1

.

.

.

.

.

.

pk−1,1

... pk−1,n−k−1

5







,





(5)

DEEE - ESPEGonzalo Fernando Olmedo Cifuentes

6

Generaci´
on de la palabra c´
odigo en el transmisor
c = [b|m]

(6)

c = [mP|m] = m [P| Ik ]

(7)

Usando (4) en (6) tenemos:

De (7) se define la matriz generadora como:
G = [P| Ik ]

(8)

c = mG.

(9)

As´ı, (6) es dada por:

DEEE - ESPE

Gonzalo Fernando Olmedo Cifuentes

7

Detecci´
on de error en el receptor
Si definimos la matriz de comprobaci´
on H dadapor:
H = [In−k | PT ],

(10)

al multiplicar HGT tenemos que:
T
P
HGT = [In−k | PT ]
Ik

= PT + PT ,

(11)

donde PT + PT al ser sumado en m´
odulo dos es una matriz nula de
orden (n − k)xk. De manera equivalente tenemos que GHT = 0.
As´ı obtenemos la ecuaci´
on de verificaci´
on de paridad dada por:
cHT = mGHT

(12)

DEEE - ESPE

Gonzalo Fernando Olmedo Cifuentes

8

S´ındrome
Considerando unvector de error e tenemos un vector recibido, v,
dado por:
v=c+e

(13)

El s´ındrome es definido como:
s = vHT

(14)

DEEE - ESPE

Gonzalo Fernando Olmedo Cifuentes

Distancia de Hamming (d )
Es el n´
umero de localidades que difieren dos palabras
Ejemplo: Sea a = [1 0 0 1 1] y b = [1 0 1 0 1], la distancia de
Hamming entre a y b es d = 2.

Peso de Hamming de una palabra c´
odigo (d )
Corresponde a ladistancia entre el vector c´
odigo y el vector c´
odigo
de puros ceros.

Distancia m´ınima de un c´
odigo de bloques lineal
(dm´ın )
Es el peso de Hamming m´
as peque˜
no de los vectores de c´
odigo
distintos de cero en el c´
odigo.

9

DEEE - ESPE

Gonzalo Fernando Olmedo Cifuentes

10

Correcci´
on de errores (t)
Un c´
odigo de bloques lineal (n, k) de distancia m´ınima dm´ın puede
corregirhasta t errores, donde:
1
t≤
(dm´ın−1 )
2

(15)

DEEE - ESPE

Gonzalo Fernando Olmedo Cifuentes

11

L´ımite de Hamming (1/2)
L´ımite para corregir errores individuales, para un c´
odigo de bloques
lineal (n, k) es dado por:
(n + 1)2k ≤ 2n

(16)

n + 1 ≤ 2n−k

(17)

o´

DEEE - ESPE

Gonzalo Fernando Olmedo Cifuentes

12

L´ımite de Hamming (2/2)
L´ımite de Hamming en funci´
on del valor m´
aximode la capacidad
de correcci´
on de errores t.













 

n
n
n


 





n − k = log2  1 +
+···+
+

t
2
1



(18)

DEEE - ESPE

Gonzalo Fernando Olmedo Cifuentes

13

Ejercicio 1 : Para el c´
odigo de Hamming (7, 4) obtenga: a) todas las
posibles palabras c´
odigo, b) la tabla de s´ındromes, c) la distancia
m´ınima del c´
odigo y d) la cantidad de errores que puedecorregir.

1

0

G=
1

1

1

0

| 1

0



0

0


0


0


1

1

| 0

1

0

1

1

| 0

0

1

0

1

| 0

0

0

1

Resp: c) dm´ın =3 d) t ≤ 1, Puede corregir m´
aximo un error.

(19)

DEEE - ESPE

Gonzalo Fernando Olmedo Cifuentes

14

Mensaje

C´
odigo

Peso

Mensaje

C´
odigo

Peso

0000

0000000

0

1000

1101000

3

0001

1010001

3

1001

0111001

4

0010

1110010

4

1010...