TÉCNICAS DE CODIFICAÇÃO DE SINAIS

TÉCNICAS DE CODIFICAÇÃO DE SINAIS

CÓDIGOS CÍCLICOS

Evelio M. G. Fernández - 2010

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 ↔ 11

2210

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

nnn

nn

11

22

101

1

11

210

multiplicação módulo 1nx

Cíclico Código :2

13

31

2012

12

13

31

201

12

Cxv

xvxvxvxvv

xvxvxvxvxv

xxvxvx

nnnn

nn

nnn

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

nn 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


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)


+ 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)

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


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


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.

knkn xgxgxgxg

2211

),(: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 11

2210)(

kk xaxaxaaxa

C

kk

CC

xgxaxxgaxgaxgxa

)()()()()( 1110

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

gggggg

gggggg

xgxxgx

xxgxg

G

10

10

10

10

1

2

00000000

00000000

mensagemdebitsk

k

paridadedechequedebitskn

kn mmmbbbv 110110 ,,,,,,,

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

1110)(

kk xmxmmxm

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

)(

11

110

)(

1110)(

xmx

kk

knkn

xb

knkn

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 kk , 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-1bn-k-2

xmx kn

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

Circuito de Cálculo das Síndromes

s0 s1sn-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

21212

2210

22

Desempenho de Códigos RS sobre GF(26) comn = 31, considerando modulação 32-FSK

Desempenho de Códigos RS sobre GF(26) comn = 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

Documents

TÉCNICAS DE CODIFICAÇÃO DE SINAIS