284 CAPÍTULO 10 DETECÇÃO E CORREÇÃO DE ERROS

Figura 10.13 Correção de erros em rajada utilizando o código de Hamming

Transmissor Receptor

0 0 0 1 1 0 1 Palavra de código 4 Palavra de código 4 0 0 0 1 0 0 1

0 1 1 0 1 0 0 Palavra de código 3 Palavra de código 3 0 1 1 0 0 0 0

1 0 0 0 1 1 0 Palavra de código 2 Palavra de código 2 1 0 0 1 1 1 0

1 1 1 1 1 1 1 Palavra de código 1 Palavra de código 1 1 1 1 0 1 1 1

Erros em rajada

0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1

Unidade de dados em trânsito

Bits corrompidos

tabela uma coluna por vez. A Figura 10.13 mostra que, quando um erro em rajada de tamanho 4
corrompe o frame, apenas 1 bit de cada palavra de código é corrompido. O bit corrompido em
cada palavra de código pode ser facilmente corrigido no receptor.

10.4 CÓDIGOS CÍCLICOS

Códigos cíclicos são códigos de blocos lineares especiais com uma propriedade extra. Em um
código cíclico, se uma palavra de código for deslocada ciclicamente (em rotação), o resultado
é outra palavra de código. Por exemplo, se 1011000 for uma palavra de código válida, ao exe-
cutarmos um deslocamento cíclico para a esquerda, então 0110001 também será uma palavra
de código válida. Nesse caso, se chamarmos os bits na primeira palavra de a0 até a6 e os bits na
segunda palavra b0 a b6, poderemos deslocar os bits pela seguinte equação:

b1 = a0 b2 = a1 b3 = a2 b4 = a3 b5 = a4 b6 = a5 b0 = a6

Na equação mais à direita, o último bit da primeira palavra é deslocado ciclicamente e se

torna o primeiro bit da segunda palavra.

CRC — Cyclic Redundant Check

Podemos criar códigos cíclicos para a correção de erros. Entretanto, o conhecimento teórico ne-
cessário está fora do escopo de nosso livro. Na presente seção, discutiremos apenas a categoria
de códigos cíclicos, denominada CRC (Cyclic Redundant Check), que é amplamente usada em
redes LANs e WANs.

Identificação interna do documento

 SEÇÃO 10.4 CÓDIGOS CÍCLICOS 285

A Tabela 10.6 apresenta um exemplo de código CRC. Podemos observar tanto as propriedades
lineares quanto cíclicas desse código.

Tabela 10.6 Código CRC de C(7, 4)

Palavras de dados Palavras de código Palavras de dados Palavras de código
0000 0000000 1000 1000101
0001 0001011 1001 1001110
0010 0010110 1010 1010011
0011 0011101 1011 1011000
0100 0100111 1100 1100010
0101 0101100 1101 1101001
0110 0110001 1110 1110100
0111 0111010 1111 1111111

A Figura 10.14 mostra um projeto possível para o codificador e decodificador.

Figura 10.14 Codificador e decodificador CRC

Emissor Receptor
Codificador Decodificador
Palavra de dados Palavra de dados
a 3 a 2 a1 a 0 a 3 a 2 a 1 a0

Aceitar
000

Descartar
Lógica
de decisão
Síndrome s2 s1 s0
Divisor
Gerador d 3 d2 d 1 d0 Verificador
Resto

Transmissão
não confiável
a3 a2 a1 a0 r2 r1 r0 b 3 b 2 b 1 b 0 q 2 q1 q 0
Palavra de código Palavra de código

No codificador, a palavra de dados tem k bits (4, neste caso) e a palavra de código tem n bits
(7, nesse caso). O tamanho da palavra de dados é aumentado adicionando-se n – k (3, nesse caso)
0s ao lado direito da palavra. O resultado de n bits alimenta o gerador. O gerador usa um divisor
de tamanho n – k + 1 (4, nesse caso), predefinido e estabelecido por ambas as partes. O gerador
divide a palavra de dados aumentada pelo divisor (divisão de módulo 2). O quociente da divisão
é descartado; o resto (r2r1r0) é anexado à palavra de dados para criar a palavra de código.
O decodificador recebe a palavra de código possivelmente corrompida. Uma cópia de todos
os n bits é alimentada no verificador, que é uma réplica do gerador. O resto produzido pelo

Identificação interna do documento

286 CAPÍTULO 10 DETECÇÃO E CORREÇÃO DE ERROS

verificador é uma síndrome de n – k (3, nesse caso) bits que alimenta o analisador lógico de
decisão. O analisador tem uma função simples. Se os bits de síndrome forem todos 0s, os 4 bits
mais à esquerda da palavra de código são aceitos como palavras de dados (interpretado como
não sendo um erro); caso contrário, os 4 bits são descartados (erro).

Codificador
Examinemos com mais cuidado o codificador. O codificador pega a palavra de dados e a incre-
menta com um número n – k de bits 0s. Em seguida, ele divide a palavra de dados resultante pelo
divisor, conforme mostrado na Figura 10.15.

Figura 10.15 Divisão no codificador CRC

Palavra de dados 1 0 0 1

Divisão
Quociente
1 0 1 0
Dividendo:
Divisor 1 0 1 1 1 0 0 1 0 0 0 palavra de
dados aumentada
1 0 1 1

0 1 0 0
Bit 0 mais à esquerda:
0 0 0 0
Use o divisor 0000
1 0 0 0
1 0 1 1

0 1 1 0
Bit 0 mais à esquerda:
0 0 0 0
Use o divisor 0000
1 1 0 Resto

Palavra de código 1 0 0 1 1 1 0
Palavra de Resto
dados

O processo de divisão binária de módulo 2 é similar ao processo de divisão de números de-

cimais. Entretanto, conforme mencionado no início do capítulo, a adição e a subtração utilizam
a operação XOR.
Como na divisão decimal, o processo é realizado passo a passo. Em cada etapa, aplica-se
a operação XOR entre uma cópia do divisor e os 4 bits do dividendo. O resultado da operação
XOR, de 3 bits (nesse caso), é reutilizada na etapa seguinte após ser baixado 1 bit extra para
torná-lo com um comprimento de 4 bits. Há uma questão importante a ser realçada nesse tipo
de divisão. Se o bit mais à esquerda do dividendo (ou a parte usada em cada etapa) for 0, a etapa
não poderá usar o divisor normal; precisamos usar um divisor alternativo formado por todos os
bits iguais a 0s.
Quando todos os bits remanescentes terminam de ser baixados, temos o resultado. O resto
de 3 bits forma os bits de verificação (r2, r1 e r0). Eles são anexados à palavra de dados para criar
a palavra de código.

Identificação interna do documento

 SEÇÃO 10.4 CÓDIGOS CÍCLICOS 287

Decodificador
A palavra de código pode ser corrompida durante sua transmissão. O decodificador realiza o
mesmo processo de divisões sucessivas do codificador. O resto da divisão é a síndrome. Se a
síndrome for formada completamente por 0s, não existem erros; a palavra de dados é separada
da palavra de código recebida e aceita. Caso contrário, tudo é descartado. A Figura 10.16 expõe
os dois casos: a figura da esquerda exibe o valor da síndrome quando não há ocorrência de erro;
a síndrome é 000. A parte direita da figura mostra o caso no qual ocorre um único erro. A sín-
drome não é formada completamente por 0s (ela é 011).

Figura 10.16 Divisões sucessivas no decodificador CRC para dois casos

Palavra de código 1 0 0 1 1 1 0 Palavra de código 1 0 0 0 1 1 0

Divisão Divisão
1 0 1 0 1 0 1 0
1 0 1 1 1 0 0 1 1 1 0 Palavra de 1 0 1 1 1 0 0 0 1 1 0 Palavra de
código código
1 0 1 1 1 0 1 1

0 1 0 1 0 1 1 1
0 0 0 0 0 0 0 0

1 0 1 1 1 1 1 1
1 0 1 1 1 0 1 1

0 0 0 0 1 0 0 0
0 0 0 0 1 0 1 1

0 0 0 Síndrome 0 1 1 Síndrome

Palavra de dados Palavra de dados

1 0 0 1
aceita descartada

Divisor
Você pode estar imaginando por que foi escolhido o divisor 1011. Posteriormente, ainda neste
capítulo, apresentaremos alguns critérios, em geral, porém, ele envolve uma certa dose de álge-
bra abstrata.

Implementação no Hardware
Uma das vantagens de um código cíclico é que o codificador e o decodificador podem ser imple-
mentados em um hardware específico por meio de dispositivos eletrônicos. Uma implementação
de hardware aumenta a velocidade do processo de cálculo dos bits de síndrome e de verificação.
Na seção a seguir, iremos mostrar, passo a passo, o processo. A seção é, entretanto, opcional e
não afeta a compreensão do restante do capítulo.

Divisor
Consideremos, primeiro, o divisor. Precisamos notar os seguintes pontos:

1. São aplicadas, repetidamente, operações XOR entre o divisor e parte do dividendo.

Identificação interna do documento

288 CAPÍTULO 10 DETECÇÃO E CORREÇÃO DE ERROS

2. O divisor tem n – k + 1 bits que são predefinidos ou, então, é formado completamente por
0s. Em outras palavras, os bits não mudam de uma palavra de dados para outra. Em nosso
exemplo anterior, os bits do divisor eram 1011 ou então 0000. A escolha se baseava no bit
mais à esquerda dos bits de dados aumentados que faziam parte da operação XOR.
3. Um exame mais cuidadoso mostra que são necessários apenas n – k bits do divisor na opera-
ção XOR. O bit mais à esquerda não é necessário, pois o resultado da operação é sempre 0;
não interessa o valor desse bit. A razão para tal é que as entradas para a operação XOR são
ambas 0s ou ambas 1s. No exemplo anterior apenas 3 bits, e não 4, são realmente usados na
operação XOR.
Usando esses pontos, é possível construir um divisor fixo (hardwired) que pode ser usado para
um código cíclico, caso saibamos o padrão da divisão. A Figura 10.17 mostra um projeto desses
para nosso exemplo anterior. Também mostramos os dispositivos XOR usados para a operação.

Figura 10.17 Projeto de hardware de um divisor de CRC

Bit mais à esquerda da

parte do dividendo
envolvido na operação XOR

d2 d1 d0

Linha interrompida:
+ + +
Esse bit é sempre 0
XOR XOR XOR

Observe que, se o bit mais à esquerda da parte do dividendo a ser usada nessa etapa for 1, os
bits do divisor (d2d1d0) serão 011; se o bit mais à esquerda for 0, os bits do divisor serão 000.
O projeto oferece a escolha adequada tomando como base o bit mais à esquerda.

Palavra de Dados Aumentada

Em nosso processo de divisão manual da Figura 10.15, mostramos que a palavra de dados au-
mentada permanecia fixa em uma posição, com os bits do divisor se deslocando para a direita,
1 bit em cada etapa. Os bits do divisor são alinhados com parte da palavra de dados aumentada.
Agora que nosso divisor é fixo, precisamos, em vez de deslocar para a esquerda os bits da pala-
vra de dados aumentada (direção oposta), alinhar os bits do divisor com a parte apropriada. Não
há necessidade de armazenar os bits da palavra de dados aumentada.

Resto
Em nosso exemplo anterior, o resto tem um comprimento de 3 bits (n – k bits em termos ge-
néricos). Podemos usar três registradores (dispositivos de armazenamento de um único bit)
para armazenar esses bits. Para encontrar o resto final da divisão, precisamos modificar nosso
processo de divisão. A seguir, apresentamos um processo passo a passo que pode ser usado para
simular o procedimento de divisão sucessiva em hardware (ou até mesmo em software):
1. Partimos do pressuposto de que o resto é originalmente composto apenas por 0s (000, em
nosso exemplo).

Identificação interna do documento

 SEÇÃO 10.4 CÓDIGOS CÍCLICOS 289

2. A cada pulso de clock (chegada de 1 bit de uma palavra de dados aumentada), repetimos as
duas ações a seguir:
a. Usamos o bit mais à esquerda para tomar a decisão sobre o padrão do divisor (011 ou 000).
b. Aplica-se uma operação XOR entre os outros 2 bits do resto e o bit seguinte da palavra
de dados aumentada (total de 3 bits) com o divisor de 3 bits para criar o próximo resto.

A Figura 10.18 mostra esse simulador. Note, porém, note que este não é o projeto final, ha-
verá melhorias e simplificações adicionais.

Figura 10.18 Simulação da divisão no codificador CRC

0 0 0 Palavra de dados aumentada

Instante: 1 0 + 0 + 0 + 1 0 0 1 0 0 0

0 0 0
Instante: 2 0 + 0 + 1 + 0 0 1 0 0 0

0 0 0
Instante: 3 0 + 1 + 0 + 0 1 0 0 0

0 1 1
Instante: 4 1 + 0 + 0 + 1 0 0 0

0 0 0
Instante: 5 0 + 1 + 0 + 0 0 0

0 1 1
Instante: 6 1 + 0 + 0 + 0 0

0 0 0
Instante: 7 0 + 1 + 1 + 0

1 1 0

Resto final

A cada pulso de clock, mostrado como instantes diferentes, um dos bits da palavra de dados
aumentada é usado no processo de cálculo XOR. Se examinarmos cuidadosamente o projeto,
temos um total de sete etapas, ao passo que, no método manual tradicional, tínhamos quatro
etapas. As três primeiras etapas foram adicionadas para tornar cada etapa igual e para tornar o
projeto de cada etapa também igual. As etapas 1, 2 e 3 empurram os 3 primeiros bits para os
registradores de resto; as etapas 4, 5, 6 e 7 são iguais ao projeto manual. Note que os valo-
res no registrador de resto nas etapas 4 a 7 coincidem exatamente com os valores do projeto
manual. O resto final também é o mesmo.
O objetivo do projeto anterior é apenas para fins de demonstração. Na prática, ele necessita
de simplificação. Primeiro, não precisamos preservar os valores intermediários dos bits do resto;
necessitamos apenas dos bits finais. Portanto, somente de três registradores em vez de 24. Após
as operações XOR, não precisamos dos valores dos bits do resto anterior. Da mesma forma, não

Identificação interna do documento

290 CAPÍTULO 10 DETECÇÃO E CORREÇÃO DE ERROS

são necessários 21 dispositivos XOR; dois são suficientes, pois a saída de uma operação XOR,
na qual um dos bits é 0, simplesmente é o valor do outro bit. Esse outro bit pode ser usado como
saída. Com essas modificações, o projeto se torna mais simples e muito mais barato, conforme
mostrado na Figura 10.19.

Figura 10.19 O projeto de um codificador CRC empregando registradores de deslocamento

Palavra de dados aumentada

0 0 + 0 + 1 0 0 1 0 0 0

Precisamos, porém, fazer que os registradores sejam registradores de deslocamento. Um

registrador de deslocamento de 1 bit armazena um bit pela duração de um período de clock.
A cada novo pulso de clock, o registrador de deslocamento aceita o bit em sua porta de entrada,
armazena o novo bit e o exibe na porta de saída. O conteúdo e a saída permanecem os mesmos
até chegar um novo pulso de clock. Quando conectamos em cascata diversos registradores de
deslocamento de 1 bit o efeito é como se o conteúdo do registrador estivesse se deslocando.

Projeto Geral
O projeto geral de um codificador e decodificador CRC é mostrado na Figura 10.20.

Figura 10.20 Projeto geral do codificador e decodificador de um código CRC

Nota:
A linha do divisor e o XOR
são omitidos caso o bit
correspondente no divisor for 0.

dn-k-1 d1 d0
+ + + Palavra de dados
rn-k-1 r1 r0
a. Codificador

dn-k-1 d1 d0
Palavra de
+ + +
código recebida
sn-k-1 s1 s0
b. Decodificador

Note que temos n – k registradores de deslocamento de 1 bit tanto no codificador como no

decodificador. Temos até n – k dispositivos XOR, mas os divisores normalmente possuem vários
0s em seus padrões, o que reduz o número de dispositivos. Observe também que, em vez de pala-
vras de dados aumentadas, mostramos a própria palavra de dados como entrada, pois após todos
os bits da palavra de dados serem alimentados no codificador, os bits extras, que são todos 0s,
não têm efeito algum sobre o XOR mais à direita. O processo precisa passar por outras n – k etapas
antes de os bits de verificação estarem prontos. Esse fato é um dos pontos fracos desse projeto.
Foram desenvolvidos esquemas alternativos que permitem eliminar esse tempo de espera (os bits

Identificação interna do documento

 SEÇÃO 10.4 CÓDIGOS CÍCLICOS 291

de verificação prontos após k etapas); no entanto, deixamos este como um tópico de pesquisa
para o leitor. No decodificador, entretanto, toda a palavra de código tem de alimentar o decodi-
ficador antes da síndrome estar pronta.

Polinômios
A maneira correta de compreender códigos cíclicos é representá-los na forma de polinômios.
Repetindo, esta seção é opcional.
Um padrão de bits 0s e 1s pode ser representado na forma de um polinômio com coeficien-
tes 0 e 1. A potência de cada termo mostra a posição do bit; o coeficiente mostra o valor
do bit. A Figura 10.21 apresenta um padrão binário e sua representação polinomial. Na Figura
10.21a, mostramos como transformar um padrão binário em um polinômio; na Figura 10.21b,
mostramos como um polinômio pode ser reduzido eliminando-se todos os termos com coefi-
cientes zero e substituindo x1 por x e x0 por 1.

Figura 10.21 Um polinômio para representar uma palavra binária

a6 a5 a4 a3 a2 a1 a0

1 0 0 0 0 1 1 1 0 0 0 0 1 1

1x6 + 0x5 + 0x4 + 0x3 + 0x2 + 1x1 + 1x0 x6 + x + 1

a. Padrão binário e polinômio b. Forma reduzida

A Figura 10.21 apresenta um benefício imediato; um padrão de 7 bits pode ser substituído
por três termos. O benefício é ainda maior quando temos um polinômio como x23 + x3 + 1. Nes-
se caso, o padrão termos polinomiais é de 24 bits de comprimento (três 1s e vinte e um 0s), ao
passo que no polinômio temos apenas três termos.

Grau do Polinômio
O grau de um polinômio é definido pelo grau da maior potência contida no polinômio. Por
exemplo, o grau do polinômio x6 + x + 1 é 6. Note que o grau de um polinômio é 1 menos o
número de bits do padrão. O padrão de bits, nesse caso, tem 7 bits.

Adição e Subtração de Polinômios

A adição e a subtração de polinômios em matemática são feitas adicionando-se ou subtraindo-
se os coeficientes dos termos de mesma potência. Em nosso caso, os coeficientes são apenas
0s e 1s e a adição será realizada no módulo 2. Isso tem duas conseqüências. Primeiro, a adição
e a subtração são realizadas da mesma forma. Segundo, a adição e a subtração são realizadas
combinando-se termos e eliminando-se pares de termos idênticos. Por exemplo, somar x5 + x4 +
x2 e x6 + x4 + x2 dá simplesmente x6 + x5. Os termos x4 e x2 são eliminados. Note, porém, que se
somarmos, por exemplo, três polinômios e obtivermos x2 três vezes, eliminamos dois deles
e preservamos o terceiro.

Identificação interna do documento