TÉCNICAS DE CODIFICAÇÃO DE SINAIS
CÓDIGOS DE BLOCO
Evelio M. G. Fernández - 2009
Código de Bloco Linear
Sejam:
m
Vn: espaço vetorial das n-uplas a1, a2 ,, an V , ai  F  0,1,, q 1, q  p , p
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.
C : v  a1 , a2 ,, an / v  S , S sub Vn 
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 Dual de C(n, k)
É o código linear C’ associado ao espaço nulo S’ de S (SS’)  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’ = (?)
Matriz Geradora, G
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  Gkn 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.
Codificador
linear
u
u = [u1, u2, ..., uk]: vetor informação.
v = [v1, v2, ..., vk]: palavra código.
G: Matriz geradora de C: (n, k).
v = uG
Matriz de Verificação de Paridade, H
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 n  k  n 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).
Códigos Duais
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: GGT  0
ou
GHT  0
equação de verificação de paridade do código C.
Seja C: (n, k) com matriz geradora Gkn e matriz de paridade H nkn .
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,
v  H T  0
Códigos Equivalentes
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:
1
0

*
G  0


0

0 0  0 |
p11
p12 
1 0  0 |
p21
p22 
0 1  0 |
    |
p31

p32 
 
0 0  1 |
pk1
pk 2 
p1,nk 
p2,nk 
p3,nk 

 
pk ,nk 
 I k  Pk ,n
Teorema 3.2 (P & W):
Todo código linear é equivalente a um código sistemático.
Códigos Sistemáticos
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,




H*   
PT
| I nk 

inverso na adição

moduloq para

código
q
ario


T
Isto é: G *  H   0k , nk
Peso de Hamming
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.
Singleton Bound
• A distância mínima de qualquer código de bloco (n, k) satisfaz,
dmin  n  k  1
• Códigos cuja distância mínima cumpre com,
dmin  n  k  1
são chamados de códigos de distância máxima (MDS: maximumdistance separable codes)
Arranjo Padrão (Standard Array)
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.


 C  v1  0, v1,, v qk 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.
v1  0
g1 + v1  g1
g2 + v2  g2
:
:
v2
g1 + v2
g2 + v2
:
:
v3
g1 + v3
g2 + v3
:
:
Líderes dos cosets





vqk
g1 + vqk
g2 + vqk
:
:
qn-k linhas (cosets).
qk colunas.
# palavras códigos = qk.
# cosets = qn-k.
# elementos arranjo padrão = qn (total de n-uplas de Vn).
Arranjo Padrão para Códigos Binários
Sistema Codificado (simplificado)
Codificador
u
v
Canal
Ruidoso
Decodificador
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.
Síndrome
DEF: Síndrome:
A síndrome de um vetor recebido r é o vetor de (n – k) dígitos:
s  rH T
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:
s  vH T  0  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.
v1  0
v2
v3

vqk
r1 = e
r2 = v2 + e
r3 = v3 + e

rqk = vqk + e
s
s  eH T  r 2 H T  r 3 H T    r qk H T
“Cada síndrome distinta corresponde a apenas 1 padrão de erro e”.
 # síndromes = # cosets = # padrões de erro = q nk .
DEF: Potencialidade de correção de erro.
 d  1
t   min 
 2 
t = peso (máximo) dos padrões de erro corrigíveis.
Tabela de Síndromes como Tabela de Decodificação
s
s1
s2

e
e1
e2

s qnk
e qnk
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:
PC  0Qn  1 pQn1  2 p 2Qn2  
i = # de líderes de coset com peso = i.
p = probabilidade de transição do BSC.
Q=1–p
Exemplo: Decodificador de um Código (6, 3)
s  rH T
1
0

0
s  r1 r2 r3 r4 r5 r6 
1
0

1
s1  r1  r4  r6
s 2  r2  r4  r5
s 3  r3  r5  r6
0
1
0
1
1
0
0
0
1

0
1

1
Tipos de Decodificadores
•
Três possíveis resultados da decodificação:
1. Decodificação correta, ĉ = c
2. Erro não corrigível detectado, c = indefinido
3. 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.
Códigos Perfeitos e Códigos Ótimos
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.
Exemplos de Códigos de Bloco
A) Códigos Cíclicos.
B) Códigos de paridade simples (altas taxas)
C: (k + 1, k) ou (n, n – 1)
 d  1
dmin = 2  t   min   0
 2 
“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).


C : 2m 1, 2m 1  m
n  2m 1 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)
 3  1
dmin = 3, independe de m t  
 1  correção de erros simples

2


São códigos perfeitos.
E) Códigos de Hamming q-ários (dmin = 3)
Para GF(q) e dado m
q m 1
 C: (n, k); n 
q 1
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:
2m 1  n
 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 n  2 m e m + 1 dígitos de paridade 


C : 2m , 2m  m  1 .
Construção:
0

0
H 

1

MatrizH do

cód. Hamm.para  


o dado valorde m 
1
1 
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 2m 1  n
 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).
 23  23  23  23 11
            2
0 1 2 3
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)
Espectro de Pesos para 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
Pnd   Ai p i 1  p 
n i
i 1
p = probabilidade de transição do canal BSC.
Identidades de MacWilliams
Sejam: {A0, A1, ..., An} = espectro de pesos C e {B0, B1, ..., Bn} = espectro
de pesos de C’C.
Representação polinomial:
A z   A0  A1 z    An z n
B  z   B0  B1 z    Bn z n
OBS: Idéia: calcular Ai a partir dos Bi.
n  1 z 
Az   2nk  1  z  B
 → Identidade de MacWilliams
1 z 
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)
Códigos Encurtados (Shortened Codes)
• 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: Exemplo
• Um código de Hamming binário (15, 11) tem a seguinte
matriz de verificação de paridade,
1
0
H 
0

0
0
1
0
0
0
0
1
0
0
0
0
1
1
1
0
0
0
1
1
0
0
0
1
1
1
1
0
1
1
0
1
0
0
1
0
1
1
1
1
0
0
1
1
1
1
1
1
1
1
0
1
1
1
0
0

1
• Um código encurtado (12, 8) pode ser obtido apagando as
colunas de peso máximo 12, 13, e 14 da matriz H.
1
0
H 
0

0
0
1
0
0
0
0
1
0
0
0
0
1
1
1
0
0
0
1
1
0
0
0
1
1
1
1
0
1
1
0
1
0
0
1
0
1
1
1
1
0
1
0
0

1
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,
1 

1 2

H
 

d
1 
2
4

 2d
 Q 2 

  2 Q  2  
1

0
 H  


 

d Q  2  
 

0


0 1 2
0 1



1 1 d
 Q2 

  2 Q  2  
2
4



 2d

d Q  2  
 


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 é,
 H   1   2  3  4   12  13  14 
 H   1  3  6  9  12   36  39  42 
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
G0 
G 
G   1
 
 
Gr 
• Submatrix Gi tem
informação é,
 m
 
i
linhas e n = 2m colunas. O número de bits de
• A distância mínima é 2m  r
 m  m
 m




k           
0 1
r
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ção
n  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 