Professor Dr. Luis Henrique Assumpção Lolis - Home - C odigos …professorluislolis.weebly.com/uploads/1/3/2/7/13273601/3... · 2018. 9. 7. · Encontre H, a partir de Gdo c odigo

Codigos de bloco

Luis Henrique Assumpcao Lolis

1 de novembro de 2013

Luis Henrique Assumpcao Lolis Codigos de bloco 1

Conteudo

1 Codigos de bloco lineares

2 Codigos sistematicos

3 Sındrome

4 Distancia de Hamming

5 Arranjo padrao e decodificacao de sındrome

6 Codigo de Hamming

7 Codigos corretores de erros unicos e detectores de erros duplos

8 O codigo de Golay(24,12)


Introducao

Somente o Galois Field binario vai ser considerado GF (2).

A palavra da fonte contem k bits.

A palavra do codigo contem n bits.

A redundancia e entao de n− k.

O codigo e conhecido como codigo de bloco (n, k)

A taxa do codigo e entao R = k/n


A mensagem e denotada como m = {m0,m1, ...,mk−1}Existem 2k blocos distintos.

A palavra codigo e denotada como c = {c0, c1, ..., cn−1}De todas as 2n combinacoes possıveis, somente 2k saorealmente palavras codigo, logo existem 2n − 2k combinacoes,que se recebidas, sao identificadas como um erro.

Existem diversas maneiras de obter os n bits da palavracodigo a partir dos k bits da mensagem da fonte. Nos vamosnos concentrar em uma classe particular de blocos que reduzas complexidade de codificacao. O Codigos de bloco lineares


O processo de controle de erro


Sumario



3 Sındrome



6 Codigo de Hamming




Codigos de bloco lineares

O codigo (n, k) e linear se as 2k palavras codigo formam umsubespaco C de k dimensoes do espaco vetorial Vn quecontem todas as n-uplas no campo GF (2), GF (2n). Existementao k palavras codigo que sao linearmente independentes.Essas palavras codigos sao denotadasgj = {gj0, gj1, ..., gjn−1}, 0 ≤ j ≤ k − 1.

O codigo de bloco e linear se a soma modulo-2 de duaspalavras codigo tambem e uma palavra codigo. Cada bit damensagem da fonte e denotado mij , i para representar aposicao do bit de 0 ≤ i ≤ k − 1 e j para representar amensagem de 0 ≤ j ≤ 2k − 1. Em C cada palavra codigocj = {cj0, cj1, ..., cjn−1} e uma combinacao linear dessas kpalavras codigo:

cj = mj0g0 +mj1g1 + · · ·+mjk−1gk−1


Representacao Grafica de Subespacos


O processo de codificacao pode ser representado de maneiramatricial:

cj = mj ·G

= (mj0,mj1, · · ·,mjk−1) ·

g0g1...

gk−1

= mj0g0 +mj1g1 + · · ·+mjk−1gk−1

Desenvolvendo a matriz G:

G =

g0g1...

gk−1

=

g00 g01 g02 . . . g0,n−1g10 g11 g12 . . . g1,n−1

......

......

...gk−1,0 gk−1,1 gk−1,2 . . . gk−1,n−1

Como gj gera cj , a matriz G e chamada de matriz geradora.


Exemplo de codigo linear(7, 4), com a seguintematriz geradora:

G =

g0g1...

gk−1

=

1 1 0 1 0 0 00 1 1 0 1 0 01 1 1 0 0 1 01 0 1 0 0 0 1

Mensagens Palavras codigo

(0 0 0 0) (0 0 0 0 0 0 0)(1 0 0 0) (1 1 0 1 0 0 0)(0 1 0 0) (0 1 1 0 1 0 0)(1 1 0 0) (1 0 1 1 1 0 0)(0 0 1 0) (1 1 1 0 0 1 0)(1 0 1 0) (0 0 1 1 0 1 0)(0 1 1 0) (1 0 0 0 1 1 0)(1 1 1 0) (0 1 0 1 1 1 0)(0 0 0 1) (1 0 1 0 0 0 1)(1 0 0 1) (0 1 1 1 0 0 1)(0 1 0 1) (1 1 0 0 1 0 1)(1 1 0 1) (0 0 0 1 1 0 1)(0 0 1 1) (0 1 0 0 0 1 1)(1 0 1 1) (1 0 0 1 0 1 1)(0 1 1 1) (0 0 1 0 1 1 1)(1 1 1 1) (1 1 1 1 1 1 1)


Ilustrando o calculo da palavra codigo

Se m13 = (1101) e a mensagem a ser codificada, a palavrachave correspondente e:

c13 = 1 · g0 + 1 · g1 + 0 · g2 + 1 · g3

= 1 · (1101000)+1 · (0110100)+0 · (1110010)+1 · (0001101) =(1101000)+(0110100)+(1010001) =(0001101)


Sumario



3 Sındrome



6 Codigo de Hamming




Codigos sistematicos

Uma caracterıstica desejavel do codigo para que ele seja maisfacil de decodificar e que ele seja sistematico.

Definicao de sistematico:

E um codigo que as palavras codigos contem uma repeticao damensagem da fonte com k bits mais a parte de checagemredundante de n− k bits, que sao chamados bits de paridade.



Exercıcio: como construir a matriz geradora do codigosistematico

Primeiro criar a matriz P que cria os bits de paridade. Ela ede dimensao k × (n− k)Depois a parte que constroi a repeticao da mensagem dafonte na parte direita da palavra codigo.

Matriz identidade k × k

G = [P...Ik]


G =

g0g1g2

...gk−1

=

p00 p01 . . . p0,n−k−1 | 1 0 0 . . . 0p10 p11 . . . p1,n−k−1 | 0 1 0 . . . 0p20 p21 . . . p2,n−k−1 | 0 0 1 . . . 0

|pk−1,0 pk−1,1 . . . pk−1,n−k−1 | 0 0 0 . . . 1


Exercıcio: exemplo de codigo sistematico

c = (m0,m1,m2,m3) ·

1 1 0 1 0 0 00 1 1 0 1 0 01 1 1 0 0 1 01 0 1 0 0 0 1

Nos vamos calcular c em funcao de m:

(c0, c1, c3, c4, c5, c6) =µ0 · (1101000)µ1 · (0110100)µ2 · (1110010)µ3 · (1010001)

c0 = m0 +m2 +m3

c1 = m0 +m1 +m2

c2 = m1 +m2 +m3

c3 = m0

c4 = m1

c5 = m2

c6 = m3


Circuito codificador do codigo sistematico

m0

+ +

m1 m2 m3

+c0 c1 c2

Registro da mensagem

Canal

Registro de paridade


Matriz de verificacao de paridade

Existe uma outra matriz ainda mais interessante para adecodificacao. Ela e menor que a matriz G e serve paraindicar a paridade do sinal recebido. O resultado do sinalrecebido multiplicado por essa matriz da zero quando nao haerros de transmissao.

Vamos definir a matriz de verificacao de paridade dada por

H = [In−k...P T ], onde P T e a matriz transposta de P . Veja

que a matriz H e menor que a matriz G.

Vamos verificar o resultado de HGT :

HGT = [In−k...P T ]

P T

. . .Ik

= P T + P T

Em binario a soma P T + P T = 0, sendo 0 nesse caso umamatriz (n− k)xk nula.

Multiplicando o sinal codificado c sem erros pela matriz H:

cHT = mGHT = 0


Exercıcio:

Encontre H, a partir de G do codigo (7, 4) do slide 9



Exercıcio

Encontre a matriz geradora e a matriz verificadora deparidade de um codigo de repeticao (n, 1), criando n bitsidenticos para cada bit da mensagem. Faca para n = 5

G =[1 1 1 1

... 1

]

H =

1 0 0 0

... 1

0 1 0 0... 1

0 0 1 0... 1

0 0 0 1... 1


Sumario



3 Sındrome



6 Codigo de Hamming




Sındrome

r = c+ eCodificador Canal

RuidosoDecodificador

��

O sinal recebido atraves de um canal com ruıdo e o sinalenviado mais o erro.

Para identificar a posicao em que houve um erro:

ei(1 ≤ i ≤ n) ={

10

se houver erro na i-esima posicaose nao houver erro

O vetor sındrome e: s = r ·HT = (s0, s1, . . . , sn−k−1) vale zero quando naoha erroOs sındromes diferentes de zero sao provindos de varios padroes de erro.

O erro mais provavel e o considerado.


Propriedades da sındrome

1 A sındrome depende somente do padrao do erro, e nao dapalavra-codigo transmitida.

s = r ·HT = (c+ e)HT = cHT + eHT = eHT

2 A sındrome e uma combinacao linear dos padroes de erro.Mas havendo 2k mensagens da fonte, existem 2k erros quedao a mesma sındrome.

3 Nesse caso e necessario haver um criterio para identificar quale o erro mais provavel de ter ocorrido. No caso do codigobinario sistematico, e o padrao de erro que possua menositens nao nulos.


Exemplo de um circuito de calculo de sındrome

Considerando o codigo (7, 4) utilizado no slide 9, nos criamosa matriz HT :

s = (s0, s1, s2) = (r0, r1, r2, r3, r4, r5, r6)

1 0 00 1 00 0 11 1 00 1 11 1 11 0 1

Os dıgitos da sındrome sao:

s0 = r0 + r3 + r5 + r6s1 = r1 + r3 + r4 + r5s2 = r2 + r4 + r5 + r6


Circuito da sındrome


Sumario



3 Sındrome



6 Codigo de Hamming




Distancia de Hamming

O peso de Hamming e definido como o numero de elementosnao nulos numa palavra codigo, w(c) (w para weight).

A distancia de Hamming e o numero de lugares onde duaspalavras codigos diferem.

A distancia mınima dmin e a menor distancia de Hammingobservada entre duas palavras codigo diferentes dentro de umgrupo do codigo de bloco C.

dmin , {d(c,d) : c,d ∈ C, c 6= d}Num codigo linear, a soma de duas palavras chave e outrapalavra chave. Logo a distancia entre duas palavras chave e opeso de uma terceira. Como qualquer palavra chave e a somade duas outras palavras-chave, a distancia mınima e o peso docodigo sao os mesmos em um codigo linear.

dmin = {w(c+ d) : c,d ∈ C, c 6= d}= {w(x) : x ∈ C,x 6= 0}

, wmin


Capacidade de correcao de um codigo de bloco

O sinal recebido r com erro e distancia l do sinal c enviado.

Como duas palavras codigo diferem de dmin, nenhum padraode erro com com dmin − 1 ou menos erros erros muda umapalavra codigo em outra.

Um codigo dmin garante deteccao de erros dmin − 1.

Existem 2n − 1 padroes de erro possıveis, dentro desses,2k − 1 sao palavras codigo. Portanto, existem 2n − 2k errosdetectaveis , alguns contendo um peso superior a dmin − 1.Por isso existem 2k − 1 erros nao detectaveis.


Probabilidade de erro indetectavel

Pu(E) =

n∑i=1

Aipi(1− p)n−i. Ai e o numero de palavras

codigo de peso i. p probabilidade de transicao.

pi sao i posicoes havendo transicao e (1− p)n−i, sao n− iposicao nao havendo transicao.

Se definido dmin, entao A1 a Admin−1 igual a zero.

Considerando o codigo do slide 9, calcular a probabilidade deerro indetectavel.


Capacidade de correcao de erro e probabilidade dedeteccao erronea

Considere um erro de peso t

2t+ 1 ≤ dmin ≤ 2t+ 2

Se o erro tem peso t ou menos, ele sera mais proximo dapalavra codigo transmitida que qualquer outra palavra codigo.

No entanto, se l > t o vetor de erro sera mais proximo de umapalavra codigo incorreta, do que a palavra codigo transmitida.

O codigo garante correcao para erros onde t = b(dmin − 1)/2cou menos.

Probabilidade de deteccao erronea:

P (E) ≤n∑

i=t+1

(ni

)pi(1− p)n−i

Um codigo de bloco linear com distancia mınima dmin edenotado (n, k, dmin).


Sumario



3 Sındrome



6 Codigo de Hamming




Arranjo padrao de decodificacao de sındrome

O arranjo padrao e uma tabela que contem todas as combinacoesde sinais recebidos. Ele contem a combinacao de cada palavracodigo com cada padrao de erro.

As palavras codigo possıveis sao denominadas ci, que vai de c1 atec2k .

Os padroes de erro denominados ei, de e2 ate e2n−k , e1 nao emarcado e zero erro.

As linhas do conjunto padrao sao os conjuntos complementares, eos primeiros elementos e2, ..., e2n−k sao os conjuntoscomplementares principais.


Usando um codigo (6, 3) de matriz geradora:

G =

0 1 1 1 0 01 0 1 0 1 01 1 0 0 0 1

, temos o seguinte arranjo

padrao:


Decodificando:1 Calcular a sındrome s = rHT

2 Dentro do conjunto complementar encontre o conjuntocomplementar principal que gera a sındrome. O padrao de errocom maior probabilidade de ocorrencia e aquele com o menorpeso. Denomine de e0

3 c = r+ e0


Exemplo

Aplicando o codigo do slide 9 vamos fazer o circuito decorrecao de erro.


Codigo dual

Com um codigo de bloco linear:

GHT = 0

O codigo tem matriz geradora G e matriz de verificacao deparidade H, sendo um codigo (n, k). Existe um codigo dualcom parametros (n, n− k), com matriz geradora H everificacao de paridade G.


Sumario



3 Sındrome



6 Codigo de Hamming




Codigo de Hamming

Para qualquer inteiro positivo m ≥ 3, existe um codigo deHamming com os seguintes parametros:

Tamanho do codigo n = 2m − 1Tamanho da mensagem da fonte k = 2m −m− 1Numero de bits de paridade n− k = mCapacidade de correcao de erro t=1 (dmin = 3)


Sumario



3 Sındrome



6 Codigo de Hamming




SEC - DED / Single error correction - Double error detection.

E originado a partir de um codigo de Hamming

A matriz verificadora de paridade e alterada para garantirdistancia mınima 4.

Excluir colunas de H de maneira a obter:

Cada coluna com um numero ımpar de ”1’s”.Reduzir ao maximo o numero de ”1’s”.Garantir o numero de ”1’s”em cada linha o mais proximo damedia de ”1’s”por linha.


Sumario



3 Sındrome



6 Codigo de Hamming




O unico outro codigo perfeito fora o de Hamming, construıdopor M.J.E. Golay em 1949.dmin = 7, t = 3.Ele tem um formato cıclico tambem que sera estudadoposteriormente. Adicionando um bit de paridade (24,12) ocodigo corrige ate t = 3 erros e detecta todos os padroes deerros de 4 bits.]A matriz geradora: G =

[P I12

]


Propriedades de P

1 E simetrica pela diagonal.

2 A n esima coluna e atransposta da n esima linha.

3 P ·PT = I12.

4 Subtraindo a ultima linha,as outras linhas sao obtidasdeslocando ciclicamente aprimeira linha a esquerda.


A matriz verificadora de paridadeH =

[I12 PT

] [I12 P

]Definindo pi = u(i) ·P, pi e a i esima linha de P e u(i) e umvetor de 12 uplas que contem 1 somente na posicao (i). Ex:u(5) = (000001000000)

Sabendo que s = e ·HT e P = PT

Definindo o erro como sendo a concatenacao de dois vetoresde 12 uplas e = (x,y):

s = (x,y) ·[I12P

]= x+ y ·P

Com P ·PT = I12, y = (s+ x) ·P


Decodificacao

Existem 4 tipos de erro que podem ser analisadosconsiderando o peso da sındrome ou o peso da combinacao dasındrome e P

Considerando o primeiro caso: w(x) ≤ 3 e w(y) = 0. s = x ee = (s,0), 0 e o vetor de 12 zeros.

Para o segundo caso: w(x) ≤ 2 e w(y) = 1. y = u(i). Sendoassim: s = x+ u(i) ·P = x+ pi, logo e = (s+ pi,u

(i))

Para o terceiro caso: quando w(x = 0), sendo w(y) = 2 ou 3.y = s ·P e e = (0, s ·P)

Para o quarto caso: w(x = 1) e w(y) = 2, entao x = u(i),y = s ·P+ pi e entao e = (u(i), s ·P+ pi)


Decodificacao

Identificado os quatro casos, vamos testar os pesos da sındrome edas combinacoes da sındrome com P ou pi para definir em quecaso estamos e definir e. A decodificacao em oito etapas:

1 Computar s do sinal recebido r.2 Se w(s) ≤ 3, entao e = (s,0) e avancar a etapa 8.3 Se w(s+ pi) ≤ 2 para qualquer linha pi em P, entao

e = (s+ pi,u(i)) e avancar para a etapa 8.

4 Computar s ·P5 Se w(s ·P) = 2 ou 3, entao e = (0, s ·P) e avancar para a

etapa 8.6 Se w(ss ·P+ pi) = 2 para qualquer linha pi, entao

e = (u(i), s ·P+ pi) e avancar para a etapa 8.7 O peso da sındrome superior a 3 significa uma nao

possibilidade de correcao, entao deve-se pedir retransmissaoou parar a operacao de decodificacao, indicando erro.

8 A palavra-codigo m∗ = r+ e


Exemplo

r = (100000110100110000000001)

Aplicar o detector de erro de Golay


Documents

Professor Dr. Luis Henrique Assumpção Lolis - Home - C odigos …professorluislolis.weebly.com/uploads/1/3/2/7/13273601/3... · 2018. 9. 7. · Encontre H, a partir de Gdo c odigo