CÓDIGOS CORRETORES DE ERROS
CÓDIGOS CONVOLUCIONAIS
Evelio M. G. Fernández - 2007
Estrutura e Codificação de Códigos Convolucionais
Códigos de Bloco: (n, k)
n dígitos codificados = função dos k dígitos (informação) da entrada
no instante atual.
Código Convolucional: (n, k, m)
n dígitos codificados = função dos k dígitos de entrada e de K dígitos
de informação guardados em uma memória (conjunto de SR’s: shift
register).
Codificador Convolucional C1: (2, 1, 3)
+
v1
u1
v=(v 1v 2)
+
u1: seqüência de entrada, k = 1.
v = (v1v2): seqüência codificada, n = 2.
m: ordem do codificador, m = 3
Memória: 1 SR de 3 estágios (3 FFD)
Taxa: R = 1/2
v2
Equação de Codificação em forma de Matrizes
 g 01 g 02

G


g11 g12
g 01 g 02
g 12 g 22 
g 1m g m2
g11 g12  g 1m 1 g m2 1
g 01 g 02  g 1m  2 g m2  2

g 1m g m2
g 1m 1 g m2 1



1 2
gm gm 
 
ou
G0

G


G1
G0
G2  Gm
G1 G2 
G0 G1 G2

Equação de codificação:
v  uG
Gm



Gm 



onde: Gi  gi1gi2

Codificador Convolucional C2: (3, 2, 1)
1
u
v1
+
v2
v
+
u
u2
v3
+
u = (u1u2): seqüência de entrada, k = 2.
v = (v1v2v3): seqüência codificada, n = 3.
Memória: 1 SR de um estágio, v1 = v2 = 1 (1FFD) em paralelo com a entrada.
Ordem do codificador:
m  max vi  1, vi = tamanho do i-ésimo SR, i = 1, 2, , k
i 1, 2
Taxa: R = 2/3
Equação de Codificação em forma de Matrizes
 g11, 0 g12, 0 g13, 0
 g1 g 2 g 3
 2, 0 2, 0 2, 0
G



g11,1 g12,1 g13,1
g 12,1 g 22,1 g 23,1
g11,0 g12, 0 g13, 0
g 12, 0 g 22,0 g 23,0

Equação de codificação:
v  uG
g11,m g12,m g13,m

g 12,m g 22,m g 23,m

 g11,m1 g12,m1 g13,m1
 g11,m1 g12,m1 g13,m1



3
2
1
g1,m g1,m g1,m 
g 12,m g 22,m g 23,m 



Matriz Geradora para Codificadores Convolucionais
Em geral, para codificadores convolucionais (n, k, v)

 

Seqüência codificada: v  v v v   v v v , v v v ,, v v v ,
Seqüência geradora da saída j relativa à entrada i: g  g , g ,, g 
Seqüência de informação: u  u1u 2  u10u02 , u11u12 ,, ul1ul2 ,
1 2 3
1 2 3
0 0 0
1 2 3
1 1 1
1 2 3
l l l
j
i
Equação de codificação: v  u  G
G0
G  

G1
 Gl
G0
G1

 g11l
 1
g
onde: Gl   2l
 
 1
 g kl
 Gm
 Gl

g12l
g 22l

g kl2

 g1nl 

 g 2nl 

 

n
 g kl 

Gm 
 
j
i0
j
i1
j
im
Constraint Length
• O constraint length v de um codificador convolucional é
definido como
v
v
1i  k
i
• Um codificador convolucional com taxa R = k/n e constraint
length v é chamado de codificador (n, k, v)
• Um código convolucional (n, k, v) é o conjunto de todas as
seqüências de saída (palavras-código) produzidas por um
codificador (n, k, v)  é o espaço das linhas da matriz G
Código C1: (2, 1, 3): Análise do Domínio da Transformada
+
v1
u1
v=(v 1v 2)
+
n = 2, k = 1, v= 3, m = 3
Seqüências geradoras Polinômios geradores
g1 = (1011)
 g1 (D)  1  D2  D3
g2 = (1111)
 g 2 (D)  1  D  D2  D3
Mensagem:
u = (10111)
 u( D)  1  D2  D3  D4
v2
Codificador Sistemático Feedforward, R = 2/3
Realizações
Equivalentes de
um Codificador
com R = 1/3
Realizações
Equivalentes de
um Codificador
com R = 2/3
Codificador Convolucional (2, 1, 3)
+
v1
u1
v=(v 1v 2)
+

GD  1  D2  D3 1  D  D2  D3

v2
Inversor do Codificador Convolucional (2, 1, 3)
Codificador Convolucional (3, 2, 2)
v1
1
u
+
v2
+
u
u2
v3
+
G D   1  D
 D
D
1
1  D
1 
v
Inversor do Codificador Convolucional (3, 2, 2)
Propriedades Estruturais de Códigos Convolucionais
Codificador convolucional  circuito seqüencial (máquina de estados finita).
 operação descrita por diagramas de estados (treliça, árvore, etc)
EXEMPLO
v1
u
v=(v 1v 2)
+
v2
Código (2, 1, 1)
Propriedades Estruturais de Códigos Convolucionais
Diagrama de Estados
1/11
0/00
0
1
1/10
0/01
# de estados = 2v = 2
Diagrama treliça
0
1
0/00
1/10
0
0/1
1/1
1
1
1
Distância Livre, dfree
d free  min d H v, v, u   u 
v,vC
onde:
v, v : seqüências codificadas correspondentes à u  e u  .
d H v, v : distância de Hamming entre duas seqüências quaisquer em C.
Para código linear,
v  0  d H (0, v)  wH (v)
onde wH (v) : peso de Hamming de v.
Portanto:
d free (C)  min wH (C); v  u  G, u  0
código linear
Função Distribuição de Pesos
T ( X , Y , Z )   Ai , j ,l X iY j Z l
i , j ,l
onde:
i = peso de Hamming de um caminho (seqüência codificada); i = wH(v).
j = peso de Hamming de um caminho de entrada (seqüência u); j = wH(u).
l = comprimento dos caminhos (entrada ou saída) em arcos (diagrama de
estados) ou em ramos (diagrama treliça).
Ai,j,l = número de caminhos com pesos i e j e comprimento igual a l.
Diagrama de Estados Aumentado
Codificador (2, 1, 1)
v1
u
v=(v 1v 2)
+
v2
Diagrama de Estados Aumentado:
Diagrama de Estados:
1/11
XYZ
0/00
0
1
0/01
1/10
0
Estado
Inicial
X 2YZ
1
XZ
0
Estado
Final
Treliça do Código Convolucional (2, 1, 3)
Seqüência Codificada
Decodificação Seqüencial
Decodificação Seqüencial
Decodificação Seqüencial
Decodificação Seqüencial
Desempenho de Esquemas de Codificação Padrões
Treliça de um Código Convolucional (3, 1, 2) com h = 5
Algoritmo de Viterbi
A cada unidade de tempo:
• Somar 2k métricas de ramo às métricas dos
caminhos previamente armazenados
• Comparar as métricas de todos os 2k caminhos
que chegam a cada estado
• Selecionar o caminho com a maior métrica
(sobrevivente)
• Armazenar o caminho sobrevivente e sua métrica
Algoritmo de Viterbi
• Passo 1: t  m , calcular a métrica parcial para o único
caminho entrando a cada estado. Armazenar o caminho
(sobrevivente) e sua métrica para cada estado.
• Passo 2: t  t  1 , calcular a métrica parcial para todos os 2k
caminhos que entram num estado somando a métrica de ramo
que entra no estado com a métrica do sobrevivente no instante
anterior. Para cada estado, comparar as métricas de todos os 2k
caminhos que entram nele, selecionar o de maior métrica,
armazenar este caminho e sua métrica e eliminar todos os
outros caminhos.
• Passo 3: Se t  h  m , repetir passo 2. Caso contrário: FIM.
Algoritmo de Viterbi para um DMC
Algoritmo de Viterbi para um BSC
Desempenho de Códigos Convolucionais
Desempenho de Códigos Convolucionais
Melhores Códigos
Convolucionais
Conhecidos de Taxa
1/2 e 1/3