CODIFICAÇÃO DE CANAL PARA

SISTEMAS DE COMUNICAÇÃO DIGITAL

CÓDIGOS CÍCLICOS

Evelio M. G. Fernández - 2011

Códigos Cíclicos: Definição

• Um código de bloco linear é um código cíclico se cada deslocamento cíclico das palavras-código é também uma palavra-código. Vantagens:

– Descrição algébrica elegante

• c(x) = m(x)g(x), g(x) polinômio gerador

• c(x)h(x) = 0 mod (xn 1) h(x) polinômio de verificação de paridade

• c(β1) = 0, ..., c(βt) = 0, onde βi GF(pm)

– Codificação e cálculo de síndromes utilizando registradores de deslocamento

– Correção de surtos de erros

– Correção de erros aleatórios através da solução de equações de polinômios

C: (n, k), C: SubEsp Vn

Se Cvvvv n 110 ,,, : código cíclico, então deslocamentos

cíclicos de v também pertencem a C, isto é:

C

vvvvv

vvvvv

vvvvv

nn

nnn

nn

01221

31012

22101

,,,,

,,,,,

,,,,,

Representação Polinomial:

110 ,,, nvvvv ↔ 1

1

2

210

n

n xvxvxvvxv

onde: x = variável auxiliar

vi GF(q); q primo.

Deslocamentos Cíclicos de n-uplas e Polinômios

x·v(x): deslocamento cíclico no tempo ou rotação à direita sujeita à condição,

01ou 1 nn xx

Cxvxvxvxvv

xxvxvxvxvx

n

nn

n

n

1

1

2

2

101

1

1

1

2

10

multiplicação módulo 1nx

Cíclico Código :2

1

3

3

1

2

012

1

2

1

3

3

1

2

01

1

2

Cxv

xvxvxvxvv

xvxvxvxvxv

xxvxvx

n

nnn

n

n

n

nn

Cxxvxxxvxv n 1mod,,, 2

Isto é, para i o polinômio Cxxvx ni 1mod .

Deslocamentos Cíclicos de n-uplas e Polinômios

Corpos Finitos

• Um corpo finito com q elementos é chamado de GF(q)

(Galois Field)

• GF(p) = inteiros com aritmética módulo um número primo,

p

• GF(pm) = polinômios sobre GF(p) com aritmética módulo

um polinômio primo de grau m (extension field)

• Todo corpo finito é o espaço vetorial de m-uplas sobre o

corpo GF(p) de inteiros com aritmética módulo um número

primo p. Portanto, GF(q) = GF(pm)

Corpos Finitos

• Teorema: A característica, λ, de um corpo finito é um

número primo

• Teorema: Seja a um elemento diferente de zero em GF(q).

Então, a(q1) = 1

• Teorema: Seja a um elemento diferente de zero em GF(q).

Seja n a ordem de a. Então, n divide q1

• Resultado: Se a ordem de a for q1, então a é um elemento

primitivo de GF(q)

Aritmética de Corpos Finitos

• Polinômios com uma variável X e coeficientes em um corpo F (denotados por F[x]), são expressões da forma

• O grau de f(X) é a maior potência de X (com coeficiente de X ≠ 0)

• Polinômio mônico: O coeficiente da maior potência de X é 1 Todos os polinômios diferentes de zero sobre GF(2) são mônicos

• Para qualquer dividendo f(X) F[x] e divisor diferente de zero, g(X) F[x] existirão um par de polinômios únicos q(X), cociente e r(X), resto, tal que

n

n XfXfXffXf 2

210

XgXrXrXgXqXf degdegonde,

Definição:

Seja p(X) um polinômio de grau m sobre GF(2). Se p(X) não

for divisível por nenhum polinômio sobre GF(2) de grau

m – 1 ou menos, então p(X) é irredutível sobre GF(2).

Resultado:

Qualquer polinômio irredutível sobre GF(2) de grau m divide

112 m

X

Aritmética de Corpos Finitos

Definição:

Seja p(X) um polinômio irredutível de grau m sobre GF(2);

então, p(X) divide Xn + 1 para n = 2m – 1. Se este valor de n

for o menor inteiro positivo para o qual p(X) divide xn + 1,

então p(X) é um polinômio primitivo de grau m sobre GF(2)

Aritmética de Corpos Finitos

+ 0 1 2 3 4 5 6 7

0 0 1 2 3 4 5 6 7

1 1 2 3 4 5 6 7 0

2 2 3 4 5 6 7 0 1

3 3 4 5 6 7 0 1 2

4 4 5 6 7 0 1 2 3

5 5 6 7 0 1 2 3 4

6 6 7 0 1 2 3 4 5

7 7 0 1 2 3 4 5 6

0 1 2 3 4 5 6 7

0 0 0 0 0 0 0 0 0

1 0 1 2 3 4 5 6 7

2 0 2 4 6 0 2 4 6

3 0 3 6 1 0 3 6 1

4 0 4 0 4 0 4 0 4

5 0 5 2 7 4 1 6 3

6 0 6 4 2 0 6 4 2

7 0 7 6 5 4 3 2 1

Soma Módulo-8 Produto Módulo-8

000 001 010 011 100 101 110 111

000 000 001 010 011 100 101 110 111

001 001 000 011 010 101 100 111 110

010 010 011 000 001 110 111 100 101

011 011 010 001 000 111 110 101 100

100 100 101 110 111 000 001 010 011

101 101 100 111 110 001 000 011 010

110 110 111 100 101 010 011 000 001

111 111 110 101 100 011 010 001 000

Soma Módulo-2 (Bit-a-Bit)

001 010 011 100 101 110 111

001 001 010 011 100 101 110 111

010 010 100 110 011 001 111 101

011 011 110 101 111 100 001 010

100 100 011 111 110 010 101 001

101 101 001 100 010 111 011 110

110 110 111 001 101 011 010 100

111 111 101 010 001 110 100 011

Operação de “Multiplicação” das 3-uplas

0000

1001

010

1011

100

1101

110

1111

2

2

2

2

Representação

Definição:

Um elemento de GF(2m) de ordem 2m – 1 é um elemento

primitivo.

se é um elemento primitivo em GF(2m), então as

potências distintas de geram todos os elementos (diferentes

de zero) de GF(2m).

Definição:

Um polinômio irredutível, p(x), de grau m sobre GF(2) é um

polinômio primitivo se tiver como raiz um elemento

primitivo de GF(2m)

Construção de GF(2m)

Elementos de GF(24) construído a partir de

41)( xxxp

Teorema:

Seja f(X) um polinômio com coeficientes em GF(2). Seja

um elemento de GF(2m). Se é uma raiz de f(X), então para

qualquer l ≥ 0 ,

é também uma raiz de f(X)

O elemento é chamado de conjugado de .

l2

l2

Propriedades de GF(2m)

Teorema:

Os 2m – 1 elementos diferentes de zero de GF(2m) compõem

todas as raízes de

O elemento 0 de GF(2m) é a raiz de X. Portanto,

Corolário:

Os elementos de GF(2m) compõem todas as raízes de

β pode ser uma raiz de um polinômio sobre GF(2) de grau

menor que 2m

112 m

X

Propriedades de GF(2m)

XXm

2

Definição:

Seja um elemento de GF(2m). O polinômio minimal, (X),

de é o polinômio de menor grau com coeficientes em GF(2)

tal que () = 0.

Teorema:

Sejam (X) o polinômio minimal de um elemento em

GF(2m) e e o menor inteiro tal que . Então:

e2

1

0

2e

i

i

XX

Propriedades de GF(2m)

Polinômios minimais dos elementos de GF(24)

Polinômio Gerador

Seja C um código cíclico (n, k) sobre GF(q)

• Existe um polinômio mônico g(x), chamado de polinômio gerador, tal que uma n-upla c(x) é uma palavra-código se e somente se g(x) for um divisor de c(x).

• O polinômio gerador é único.

• O grau do polinômio gerador é n k.

• g(x) é o polinômio código de menor grau entre todos os polinômios código.

• O polinômio gerador é um divisor de xn 1.

kn

kn xgxgxgxg

2

211

),(:1mod)()()( knCxxgxaxc n

onde:

Grau [c(x)] n – 1.

Grau [g(x)] = n – k.

Grau [a(x)] k – 1.

a(x): polinômio em x associado à mensagem a ser codificada em c(x).

Seja 1

1

2

210)(

k

k xaxaxaaxa

C

k

k

CC

xgxaxxgaxgaxgxa

)()()()()( 1

110

Portanto:

a(x)g(x) = combinação linear de palavras código que resulta em uma outra

palavra código de C.

Polinômio Gerador

Matriz Geradora não Sistemática

• Código cíclico C: (n, k) gerado por g(x) de grau r = n k

r

r

r

r

k

k

ggg

ggg

ggg

ggg

xgx

xgx

xxg

xg

G

10

10

10

10

1

2

0000

0000

0000

0000

mensagemdebitsk

k

paridadedechequedebitskn

kn mmmbbbv 110110 ,,,,,,,

Seja m(x): polinômio-mensagem,

1

110)(

k

k xmxmmxm

v(x): polinômio código de código sistemático.

)(

1

1

1

10

)(

1

110)(

xmx

k

k

knkn

xb

kn

kn

kn

xmxmxmxbxbbxv

Se v(x) = a(x)g(x)

)(

)()(

)(

)(

xg

xbxa

xg

xmx kn

Código Cíclico Sistemático

1. ?)( knxxm

2. Resto da divisão ?)()(

)(xb

xg

xmx kn

3. )()()( xvxmxxb kn

EXEMPLO:

31)( xxm , 31)( xxxg , código cíclico C: (7, 4).

Palavra código correspondente à m(x)?

a(x) tal que a(x)g(x) = v(x)?

Procedimento para Codificação Sistemática

)()(1 xgxhxn

ou: 01mod)()( nxxgxh

g(x): polinômio gerador de C: (n, k)

h(x): polinômio de verificação de paridade de C: (n, k)

Grau [g(x)] = n – k

Grau [h(x)] = k

Teorema 4.7 (Lin & Costelo, pág. 94):

Seja C: (n, k) um código cíclico q-ário com polinômio gerador g(x), em

GF(q). O código dual de C é também cíclico e é gerado pelo polinômio

1)( xhxxh k

k , onde )(xhk é o polinômio recíproco do polinômio de

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

Polinômio de Verificação de Paridade

Codificador de um Código Cíclico (n, k)

b0 b1 b2 bn-k-1 bn-k-2

xmx kn

Codificador do Código Cíclico (7, 4)

Circuito de Cálculo das Síndromes

s0 s1 sn-k-1

r(x)

Cálculo de Síndromes Código (7, 4)

• Um código cíclico (n, k) é capaz de detectar qualquer surto

de erros de comprimento n k ou menor, incluindo surtos do

tipo end-around.

• A fração de surtos não detectáveis de comprimento n k +1

é 2 (n k 1)

• Para l > n k +1, a fração de surtos não detectáveis de

comprimento l é 2 (n k)

Capacidade de Detecção de Erros

Decodificação de Códigos Cíclicos

• Passo 1: Calcular a síndrome de r(x) e armazenar r(x) no registrador

• Passo 2: Determinar padrão de erro. A saída do detector é 1 se e

somente se a síndrome no registrador corresponde a um padrão de erro

corrigível contendo um erro na posição xn 1

• Passo 3: O buffer e o registrador de síndrome são deslocados uma

posição à direita. A saída do detector faz a correção do primeiro

símbolo (se en 1 = 1) e também é realimentada no registrador de

síndrome. Nova síndrome corresponde à r(x) deslocado

• Passo 4: Detectar se xn 2 (agora na última posição) é um símbolo

errado. Repetir passos 2 e 3. O segundo símbolo é corrigido da mesma

forma que o anterior.

• Passo 5: Decodificar o vetor recebido símbolo a símbolo da forma

descrita anteriormente

Decodificação de Códigos Cíclicos

Decodificador de Meggitt para o Código Cíclico (7, 4)

Processo de

Correção de Erros

Códigos Cíclicos Binários vistos a partir de GF(2m)

• Teorema: Seja g(x) o polinômio gerador de um código

cíclico binário de comprimento n = 2m 1 com zeros 1,..., r

em GF(2m). O polinômio c(x) sobre GF(2) é um polinômio

código se e somente se

c(1) = c(2) = ··· = c(r) = 0

onde c(i) é avaliado em GF(2m)

BCH bound

Se um código cíclico linear é construído de forma que:

• Cada palavra-código tem n bits;

• é um elemento de ordem n em GF(2m);

• O polinômio gerador do código, g(x), inclui, entre suas

raízes, ( - 1) potências consecutivas de .

Então,

• É garantido que o código tem distância mínima igual a ou

maior.

Construção de Códigos BCH

• Para cada raiz r incluída em g(x), existe um polinômio

minimal f(r)(x) que tem r como raiz [i.e., f(r)(r) = 0] e com

coeficientes em GF(2).

• O polinômio gerador, com coeficientes binários, que

contém todas as raízes necessárias pode ser obtido como

sendo o mínimo comum múltiplo (LCM) de todos os

polinômios minimais correspondentes às raízes utilizadas:

g(x) = LCM{f(b+1)(x), f(b+2)(x), ..., f(b+-1)(x)}

Tipos de Códigos BCH

• Se é um elemento primitivo de GF(2m), o código BCH

resultante é chamado de código BCH primitivo e as suas

palavras-código têm comprimento 2m – 1 bits.

• Se não é um elemento primitivo de GF(2m), o código

BCH resultante é chamado de código BCH não primitivo

e as suas palavras-código têm comprimento igual à ordem

de .

• Se b = 0, a primeira das ( - 1) potências de será 1 = ,

código BCH no sentido estrito.

• Se b 0, código BCH no sentido amplo.

Códigos BCH Binários Primitivos

Para qualquer m 3 e t 2m 1, existe um código BCH com os seguinte parâmetros:

n = 2m 1,

n k mt,

dmin 2t + 1

O polinômio gerador do código, g(x), é o polinômio de menor grau sobre GF(2) contendo

como raízes, onde α é um elemento primitivo de GF(2m)

t232 ,,,,

Elementos de GF(24)

Decodificação de Códigos BCH

1. Computar as síndromes S = (S1, S2, ..., S2t) a partir

de r(x)

2. Determinar σ(x) a partir de S1, S2, ..., S2t

3. Determinar as localizações dos erros, 1, 2, ..., υ

encontrando as raízes de σ(x) e corrigir os erros

em r(x)

Códigos BCH Primitivos sobre GF(q)

Seja α um elemento primitivo em GF(qm ).

O polinômio gerador, g(x), de um código BCH q-

ário primitivo corretor de t erros é o polinômio de

menor grau sobre GF(q) contendo

como raízes. Seja i(x) o polinômio minimal de αi,

1 i 2t. Então,

g(x) = LCM{1(x), 2(x), ..., 2t(x)}

t232 ,,,,

Códigos de Reed-Solomon

Um código de Reed-Solomon (ou código RS) é

um código BCH primitivo (não binário) de

comprimento n = q – 1 sobre GF(q). O polinômio

gerador desse código tem a forma

onde é um elemento primitivo de GF(q), d é a

distância mínima do código e gi GF(q)

tt

t

t

xxgxgxggxxxxg

212

12

2

210

22

Desempenho de Códigos

RS sobre GF(26) com

n = 31, considerando

modulação 32-FSK

Desempenho de Códigos

RS sobre GF(26) com

n = 31, considerando

modulação 32-FSK

Desempenho de Códigos RS com R = 7/8

Desempenho de Códigos RS com n = 64

Desempenho de Códigos RS com n = 31 e Modulação BPSK

Decodificador de Códigos BCH q-ários

Desempenho de Códigos de Reed-Solomon