TÉCNICAS DE CODIFICAÇÃO DE SINAIS

CÓDIGOS DE BLOCO

Evelio M. G. Fernández - 2009

Sejam:

Vn: espaço vetorial das n-uplas ppqqFaVaaa min ,,1,,1,0,,,, 21

primo, m inteiro.

S = Subespaço de Vn, Dim(S) = k.

DEF: Código linear C:

C é um código linear C = S sub Vn.

nn VSSvaaavC sub,/,,,: 21

v = palavra-código.

Se S tem Dim(S) = k

C: (n, k).

k = comprimento da informação em dígitos.

n = comprimento da palavra código em dígitos.

Código de Bloco Linear

É o código linear C’ associado ao espaço nulo S’ de S (SS’) C’:

(n, n – k), [pois Dim(Vn) = Dim(S) + Dim(S’)].

EX: Dado S = {000, 111, 101, 010}, determine:

- S’ / S’S.

- Dim(S) e Dim(S’).

- Código C associado a S’.

- Código dual C’ associado a S’.

- Matriz geradora de S (código C)

- Matriz geradora de S’ (código C’).

- C: (n, k) = ?

- C’ = (?)

Código Dual de C(n, k)

DEF: Matriz G geradora de um código linear C:

As linhas (n-uplas) de G formam uma base para S sub Vn.

Dim(S) = k nkG e rank(G) = k.

DEF: Equação de codificação:

Uma palavra código v C: (n, k) corresponde a uma combinação linear

das linhas da matriz geradora de C.

u v = uG

u = [u1, u2, ..., uk]: vetor informação.

v = [v1, v2, ..., vk]: palavra código.

G: Matriz geradora de C: (n, k).

Codificador linear

Matriz Geradora, G

DEF: Matriz H de paridade de um código linear C.

Seja C S Sub Vn com Dim(S) = k. As linhas (n-uplas) de H formam uma

base para S’ = espaço nulo de G. S’ é o espaço das linhas de H.

- Se Dim(S) = k Código C: (n, k) Dim(S’) = n – k; S’S.

H é uma matriz nkn e rank(H) = n – k = no de linhas L.I. de H.

A matriz geradora de C’ dual de C é equivalente à matriz H (obtida por operações

lineares sobre as linhas).

Matriz de Verificação de Paridade, H

Seja C = Subespaço de V com Dim(S) = k. Então o seu código dual C’ = S’, Subespaço

de V onde S’S, Dim(S’) = n – k C’: (n, n – k). Se G gera o código C, G’ H (matriz

de paridade de C) gera o código C’ dual de C.

Então: 0 TGG

ou equação de verificação de paridade do código C.

Seja C: (n, k) com matriz geradora nkG e matriz de paridade nknH .

Então:

C = espaço das linhas de G ou espaço nulo de H.

C’: Dual de C = espaço das linhas de H ou espaço nulo de G.

Condição necessária e suficiente para v G,

0 THv

0 THG

Códigos Duais

A matriz geradora de um código equivalente a um código C, é obtida por

permutações de colunas da matriz G geradora de C. Códigos equivalentes apresentam

a mesma probabilidade de erro PE em canais DMC.

Código Sistemático:

knkkk

kn

kn

kn

ppp

ppp

ppp

ppp

G

,21

,33231

,22221

,11211

*

|1000

|

|0100

|0010

|0001

nkk PI ,

Teorema 3.2 (P & W):

Todo código linear é equivalente a um código sistemático.

Códigos Equivalentes

Teorema 3.3 (P & W).

Seja C* o espaço das linhas de G* = [Ik | P], então C* é o espaço nulo da

matriz,

kn

qq

T IPH |

ario- códigopara moduloadição na inverso

*

Isto é: knkTHG ,

* 0

Códigos Sistemáticos

Teorema 3.1 (P & W).

Seja C:(n, k) um código linear que é o espaço nulo de uma matriz H (matriz de

verificação de paridade de C). Então para cada palavra-código de peso de Hamming

igual a w, existem em correspondência w colunas L.D. em H e vice-versa. (para w

colunas L.D. palavra código de peso = w).

DEF: Peso de Hamming.

No de dígitos diferentes de zero em uma n-upla, sobre GF(q).

EX: PH(10110) = ?

PH(20120) = ? Corolário 3.1 (P & W):

Um código de bloco C, que é o espaço nulo de uma matriz H, tem distância mínima igual a w se e somente se todas as combinações de (w – 1) colunas de H ou menos, são L.I.

Peso de Hamming

Singleton Bound

• A distância mínima de qualquer código de bloco (n, k) satisfaz,

• Códigos cuja distância mínima cumpre com,

são chamados de códigos de distância máxima (MDS: maximum-

distance separable codes)

1min knd

1min knd

Seja um código linear C:(n, k) de matriz geradora [G]k,n e matriz de paridade [H]n – k, n.

Seja vi C; vi = palavra código de C, i = 1, 2, ..., qk.

kqvvvC ,,,0 11 e seja gj V; gj = n-upla do espaço vetorial Vn; j = 1, 2, ...,

qn. O arranjo padrão para o código C é um arranjo especial de todas as n-uplas de Vn.

qn-k linhas (cosets).

Líderes dos cosets qk colunas.

# palavras códigos = qk.

# cosets = qn-k.

# elementos arranjo padrão = qn (total de n-uplas de Vn).

v1 0 v2 v3 vqk

g1 + v1 g1 g1 + v2 g1 + v3 g1 + vqk

g2 + v2 g2 g2 + v2 g2 + v3 g2 + vqk

: : : : : : : :

Arranjo Padrão (Standard Array)

Arranjo Padrão para Códigos Binários

u v r u

v = palavra código de C: (n, k) (n-upla q-ária).

r = vetor recebido após canal com ruído (n-upla q-ária).

(v, r) Vn.

DEF: Padrão de erro:

e = r – v (n-upla q-ária).

Teorema 3.5 (P & W):

Se o arranjo padrão for usado como tabela de decodificação de um código de bloco C,

então um vetor recebido r, r Vn será decodificado corretamente na palavra código

transmitida v se e somente se o padrão de erro e = r – v for líder de coset.

Codificador Canal Ruidoso

Decodificador

Sistema Codificado (simplificado)

DEF: Síndrome:

A síndrome de um vetor recebido r é o vetor de (n – k) dígitos:

THrs

onde: [H]n – k, n = matriz de paridade do código C.

[r]1, n = n-upla recebida.

[s]1, n – k = síndrome de r.

Propriedade: A síndrome de v C é o vetor zero:

0 THvs v {espaço nulo de H} {espaço das linhas de G}

Síndrome

Teorema 3.6 (P & W): Dois vetores ri e rg estão no mesmo coset se e somente se

suas síndromes forem iguais.

s

Tq

TTT HrHrHrHes k 32

“Cada síndrome distinta corresponde a apenas 1 padrão de erro e”.

# síndromes = # cosets = # padrões de erro = knq .

DEF: Potencialidade de correção de erro.

2

1mindt

t = peso (máximo) dos padrões de erro corrigíveis.

v1 0 v2 v3 vqk

r1 = e r2 = v2 + e r3 = v3 + e rqk = vq

k + e

Síndrome

Procedimento:

r si = rHT

si ei

Palavra decodificada: vi = r – ei

Teorema 3.7 (P & W): Supondo palavras código equiprováveis, a probabilidade média de

decodificação correta PC, é máxima se a tabela de decodificação (“decodificação ótima”) for

o arranjo padrão que tiver em cada coset o vetor de menor peso como o líder de coset.

Propriedade:

222

110

nnnC QppQQP

i = # de líderes de coset com peso = i.

p = probabilidade de transição do BSC.

Q = 1 – p

s e s1 e1 s2 e2

knqs knqe

Tabela de Síndromes como Tabela de Decodificação

Exemplo: Decodificador de um Código (6, 3)

6533

5422

6411

654321

101

110

011

100

010

001

rrrs

rrrs

rrrs

rrrrrrs

Hrs T

Tipos de Decodificadores

• Três possíveis resultados da decodificação:

1. Decodificação correta, ĉ = c2. Erro não corrigível detectado, c = indefinido3. Erro de decodificação, ĉ ≠ c

• Decodificação completa: Toda palavra recebida é decodificada em alguma palavra-código

• Decodificação incompleta (bounded-distance decoding): Correção de todos os padrões de erro de peso ≥ t.

DEF: Código Perfeito

Os líderes de cosets de seu arranjo padrão correspondem a todos os padrões de erro

de peso t.

DEF: Códigos quase-perfeitos:

Os líderes de cosets correspondem a todos os padrões de erro de peso t ou menos,

alguns de peso t + 1 e nenhum de peso maior.

DEF: Código ótimo para canal BSC:

Um código binário de grupo é “ótimo” para canal BSC se a sua probabilidade de

erro PE é a menor possível para os mesmos valores de n e k.

Propriedade:

Todo código quase-perfeito (quando existir para dados n e k) se constitui em um código ótimo.

Códigos Perfeitos e Códigos Ótimos

A) Códigos Cíclicos.

B) Códigos de paridade simples (altas taxas)

C: (k + 1, k) ou (n, n – 1)

dmin = 2 02

1min

dt

“sem potencialidade de correção (t = 0) são usados em esquemas de detecção

de erro simples”.

C) Códigos de repetição simples (baixas taxas)

C: (n, 1) R = 1/n

dmin = n

Exemplos de Códigos de Bloco

D) Códigos de Hamming Binários (Hamming, 1950).

mC mm 12,12:

12 mn e k = n – m

m = n – k dígitos de verificação de paridade

São códigos cujos Hmxn: colunas correspondem as m-uplas 0 (# m-uplas = 2m – 1)

dmin = 3, independe de m 12

13

t correção de erros simples

São códigos perfeitos.

E) Códigos de Hamming q-ários (dmin = 3)

Para GF(q) e dado m

C: (n, k); 1

1

q

qn

m

k = n – m dmin = 3 t = 1

São códigos para correção de erros simples (t = 1).

Exemplos de Códigos de Bloco

F) Códigos de Hamming incompletos (códigos de Hamming com dmin = 3 e n )

Dado n qualquer e m = menor inteiro tal que:

nm 12

C: (n, n – m) e dmin = 3

Construção: Consiste em apagar colunas do código de Hamming de mesmo valor de m.

G) Código de Hamming com paridade nos bits (dmin = 4)

Dado m qualquer são códigos com mn 2 e m + 1 dígitos de paridade

12,2: mC mm .

Construção:

111 de valor dado o

para Hamm. cód.

do Matriz

0

0

m

H

H

OBS: São conhecidos como os códigos quase-perfeitos de Hamming.

Exemplos de Códigos de Bloco

H) Códigos de Hamming com dmin = 4 e n .

Dado n qualquer e m = menor inteiro tal que nm 12

C: (n, n – m); dmin = 4

Construção: Consiste em apagar colunas do código de Hamming com paridade nos bits

e mesmo valor de m.

I) Código de Golay (dmin = 7).

1123

23

2

23

1

23

0

23

corrige todos os padrões de erro de peso t = 1, 2 e 3 é código perfeito C: (23, 12).

J) Códigos ótimos para BSC.

Alguns códigos quase-perfeitos e portanto ótimos:

a) Repetição simples com n = par (dmin = n)

b) Código de Hamming com bit de paridade (dmin = 4)

c) Código de Hamming incompletos (n) (dmin = 3)

d) BCH (Bose – Chaudhuri – Hocquenghem)

Exemplos de Códigos de Bloco

Seja C: (n, k) um código de bloco. Seja Ai = No de palavras código de peso “i”,

DEF:

{Ai; i = 0, 1, 2, ..., n} = espectro de pesos ou distribuição de pesos de C

(‘weight spectrum’, ‘weight distribution’)

Aplicação: determinação da probabilidade de erro não detectável de C.

DEF: Erro não detectável:

Padrão de erro = palavra código não zero (para código não linear).

DEF: Probabilidade de não detecção Pnd,

n

i

iniind ppAP

1

1

p = probabilidade de transição do canal BSC.

Espectro de Pesos para Códigos de Bloco

Sejam: {A0, A1, ..., An} = espectro de pesos C e {B0, B1, ..., Bn} = espectro

de pesos de C’C.

Representação polinomial:

n

n

nn

zBzBBzB

zAzAAzA

10

10

OBS: Idéia: calcular Ai a partir dos Bi.

z

zBzzA nkn

1

112 → Identidade de MacWilliams

Identidades de MacWilliams

Códigos de Bloco Lineares Modificados

• Comprimento de bloco de projeto de um código: determinado por propriedades algébricas e combinacionais de matrizes ou polinômios.

• Comprimento de bloco desejado: frequentemente diferente do comprimento de bloco de projeto.

Exemplo:• Comprimento de bloco de projeto de um código de Hamming:

n = 2m 1 (7, 15, 31, ...)• Número de bits de informação pode não ser k = 2m 1 m (4,

11, 26, ...) Existem seis formas de modificar parâmetros de um código de

bloco linear (n, k, n k)

• Encurtar: n k fixo, diminuir k e, portanto, n.

• Símbolos de informação são apagados para se obter um comprimento de bloco menor do que o comprimento de projeto.

• Os símbolos que serão apagados são supostos como sendo zeros das palavras-códigos

• Exemplo: Pacotes Ethernet têm no máximo 1500 bytes de dados ou 12000 bits. O checksum Ethernet de 32 bits provem de um código de Hamming com n = 232 1 = 4294967295 bits ou 536870907 bytes.

Códigos Encurtados (Shortened Codes)

Códigos Encurtados: Exemplo

• Um código de Hamming binário (15, 11) tem a seguinte matriz de verificação de paridade,

• Um código encurtado (12, 8) pode ser obtido apagando as colunas de peso máximo 12, 13, e 14 da matriz H.

111101011001000

011110101100100

001111010110010

111010110010001

H

101011001000

010101100100

011010110010

110110010001

H

Códigos Alongados (Lengthened Codes)

• Alongar: n k fixo, aumentar k e, portanto, n.

• Novos símbolos de informação são introduzidos e incluídos nas equações de paridade.

• Exemplo: Códigos de Reed-Solomon estendidos obtidos alongando códigos RS(Q 1, k) para códigos RS(Q +1, k +2) adicionando duas coluna à matriz H,

22

2242

22

22

2242

22

110

100

101

1

1

1

Qddd

Q

Q

Qddd

Q

Q

HH

Códigos Expurgados (Expurgated Codes)

• Expurgar: n fixo, diminuir k e incrementar n k.

• Palavras-código são apagadas adicionando equações de paridade, reduzindo a dimensão do código. Objetivo: aumentar a capacidade de correção de erros.

• Exemplo: O código BCH (15, 7) pode ser obtido a partir do código de Hamming (15, 11) adicionando quatro linhas à matriz H. A matriz de verificação de paridade é,

42393612963

141312432

11

HH

Códigos Aumentados (Augmented Codes)

• Aumentar: n fixo, aumentar k e diminuir n k.

• Incluir novos vetores na base (novas linhas na matriz geradora). Isto aumenta a taxa do código e (possivelmente) diminui a distância mínima.

• Exemplo: Matrizes geradoras de códigos de Reed-Muller, R(r, m) são definidas por

• Submatrix Gi tem linhas e n = 2m colunas. O número de bits de informação é,

• A distância mínima é 2m r

rG

G

G

G

1

0

i

m

r

mmmk

10

Códigos Expandidos (Espanded Codes)

• Expandir: k fixo, aumentar n k e n.

• Incluir novos símbolos de paridade com as correspondentes equações de paridade.

• Exemplo: Códigos de Hamming estendidos (códigos de Hamming com paridade nos bits). Isto aumenta a distância mínima para 4.

• Quando a distância mínima de um código de bloco binário linear é ímpar, adicionar paridade sobre todos os bits incrementa a distância mínima em 1.

• Exemplo: Código de Golay (23, 12), dmin = 7 (código perfeito). Uma equação de paridade sobre todos os bits incrementa dmin para 8.

• O código de Golay estendido com parâmetros (24, 12, 8) foi usado para correção de erros nas missões espaciais Voyager I e II.

Códigos Puncionados (Punctured Codes)

• Puncionar: k fixo, diminuir n k e, portanto, n.

• Apagar símbolos de paridade pode reduzir a distância mínima.

• Porém, códigos puncionados podem corrigir a grande maioria dos erros corrigíveis pelo código original.

• Puncionar pode reduzir a distância mínima mas não reduz significativamente o desempenho do código.

• Códigos puncionados podem ser obtidos a partir de códigos simples que tenham muita redundância.

Modificação de Códigos de Bloco Lineares: Resumo

• Encurtar: Apagar símbolos de informaçãon k fixo, k n

• Alongar: Adicionar símbolos de informação

n k fixo, k n

• Expurgar: Apagar palavras-código, adicionar símbolos de paridade

n fixo, k n k

• Aumentar: Adicionar palavras-código, apagar equações de paridade

n fixo, k n k

• Expandir (estender): Adicionar símbolos de paridade

k fixo, n k n

• Puncionar: Apagar símbolos de paridade

k fixo, n k n