Eletrônica Digital - Códigos Detetores e Corretores de Erros

Códigos Detetores e Corretores de Erros
Os códigos numéricos são adequados à representação dos dígitos decimais, mas são pouco resistentes a erros de transmissão, que podem ocorrer devido a falhas de equipamentos ou a ruídos no canal de transmissão.
Em qualquer sistema físico existe a probabilidade não nula de ocorrer uma falha simples(erro). A probabilidade ocorrer 2 ou mais erros, em geral, é muito menor.

Códigos Detetores de Erros
Num código de 4 dígitos, a ocorrência de erro em um dos dígitos pode resultar em outra palavra do código, incorreta, embora válida.Por exemplo, em BCD, se acontece um erro no dígito menos significativo da palavra 0110 resulta na palavra 0111, que é uma palavra válida do código, provocando interpretação errada da mensagem.
Se um código possui a propriedade de que a ocorrência de um erro simples transforma uma palavra código válida em outra , inválida, então este código é detetor de erro.A figura abaixo mostra alguns exemplos.

	Nestes códigos, a deteção do erro é feita pelo teste da paridade da palavra.Adiciona-se dígitos extras às palavras de modo que o números 1 na palavra seja par(ou ímpar).Em todos os exemplos da Fig.7 a paridade é par. O código 2 em 5( 2 entre 5 ) consiste de todas as 10 combinações possíveis de dois dígitos 1 em um arranjo de cinco dígitos. Com exceção do código para o dígito 0, este código é ponderado, de pesos (0,1,2,4,7). O código biquinário é um código ponderado com pesos (5, 0, 4, 3, 2, 1, 0) onde os dois dígitos mais significativos especificam se o arranjo está no intervalo entre 0 e 4, ou no intervalo entre 5 e 9. O código BCD Par é o BCD com paridade par e é obtido do código BCD acrescentando-se o dígito P, de paridade, que pode ser 0 ou 1, para tornar o número de 1 no arranjo sempre par.
Fig.7
Em qualquer um dos três exemplos, a ocorrência de um erro simples transforma o arranjo válido em outro inválido, possibilitando a deteção do erro.

Chama-se distância entre dois arranjos códigos o número de dígitos que precisam ser complementados em um arranjo para ficar igual ao outro arranjo.Assim, a distância entre os dois arranjos 1010 e 0100 é igual a 3, pois os dois arranjos diferem em três posições.A distância mínima de um código é a menor distância entre duas palavras quaisquer deste código.

Códigos Corretores de Erros
Seja um código formado por duas palavras 000 e 111.Se acontecer um erro simples na primeira palavra, então ela pode mudar para 001, 010 ou 100.A segunda palavra do código pode ser modificada por um erro simples para 110, 101 ou 011.Veja que as palavras erradas em cada caso são diferentes: 001, 010, 100 para erro em 000 e 110, 101 e 011 pare erro em 111, então um erro simples pode ser detectado e corrigido e o código é dito corretor de erro simples.
Em geral, um código é chamado corretor de erro se a palavra correta pode ser obtida de qualquer palavra incorreta.
Se a distância mínima de um código é igual a 3, qualquer erro simples muda a palavra válida em outra inválida, que está a uma distância 1 da palavra original correta e à distância 2 de qualquer outra palavra código válida.Assim, num código de distância mínima 3, qualquer erro simples pode ser corrigido ou qualquer erro duplo pode ser detetado.Do mesmo modo, um código de distância mínima 4 pode corrigir erros simples e detetar erros duplos e triplos.

Códigos Cíclicos
A distância entre duas seqüências binárias com comprimento igual, dentro de um código, considerando os 0s e 1s, é chamada distância de Hamming.

A distância de Hamming representa a diferença entre os bits de uma seqüência para outra.O código BCD é um código com distância de Hamming variável, isto é, de uma palavra código para outra o número de dígitos que mudam não é constante.
Em várias aplicações se usam códigos com distâncias de Hamming constantes e igual a unidade.Nesses códigos, palavras sucessivas diferem, entre si, por um único dígito.Códigos com distância de Hamming igual a unidade são chamados de códigos cíclicos ou de reflexão.

Código de Hamming
Seja m uma mensagem de k bits que deve ser codificada e seja G a matriz geradora do código utilizado.As palavras códigos v=[v₁v₂...v_n] com (n>k) são geradas pelo produto matricial lógico v=m.G, onde o produto matricial lógico é definido através das operações lógicas AND e XOR.
Pode-se definir uma matriz H, tal que

G.H^t=[00...0] (n-k zeros)

Assim, se v é uma palavra código válida, então v.H^t=[00...0], caso contrário o produto v.H^t não é nulo e é denominado síndrome do erro(s).
Um código é denominado de código Hamming se as colunas de sua matriz H são formadas por todas as

2^(n-k)-1

possíveis palavras de (n-k) bits, excetuada a palavra nula.
Note que H é uma matriz de (n-k) linhas e 2^(n-k)-1 colunas, portanto n=2^(n-k)-1.
Se (n-k)=2 , n=3, k=1, então

H=		1	0	1
		0	1	1

G.H^t=[0 0] e G=[1 1 1]
v=[v₁ v₂ v₃]=[m₁].[1 1 1]=[m₁ m₁ m₁]

isto é, como o bit m₁ pode assumir os valores 0 e 1, o código é formado pelas palavras [0 0 0 ] e [1 1 1]. Observe que a distancia entre as palavras códigos é 3, ou seja, o código é capaz de corrigir um erro.
Se (n-k)=3, n=7, k=4, então

H=	1	0	0	0	1	1	1
	0	1	0	1	0	1	1
	0	0	1	1	1	0	1

G.H^t=[0 0 0]

G=	0	1	1	1	0	0	0
	1	0	1	0	1	0	0
	1	1	0	0	0	1	0
	1	1	1	0	0	0	1

v=[v₁ v₂ v₃ v₄ v₄v₆ v₇]=[m₁ m₂ m₃ m₄].G=[m₂⊕m₃⊕m₄⊕ m₁⊕m₃⊕m₄m₁⊕m₂⊕m₄m₁m₂ m₃m₄]

Assim, o bit v₁ forma paridade par com os bits v₅, v₆ e v₇, o bit v₂ com os bits v₄, v₆ e v₇ e o bit v₃ com v₄, v₅ e v₇.

O código Hamming completo para os 10 dígitos binários, com n=7 e k=4 é dado na tabela abaixo. Note que a distância mínima do código é 3, isto é, pode corrigir qualquer erro simples.

Dígito Decimal	Código Hamming
Dígito Decimal	v₁	v₂	v₃	v₄	v₅	v₆	v₇
0	0	0	0	0	0	0	0
1	1	1	1	0	0	0	1
2	1	1	1	0	0	0	1
3	0	0	1	0	0	1	1
4	1	0	1	0	1	0	0
5	0	1	0	0	1	0	1
6	0	1	1	0	1	1	0
7	1	0	0	0	1	1	1
8	0	1	1	1	0	0	0
9	1	0	0	1	0	0	1

Suponha que a palavra v=1001101 foi recebida. A operação v.H^t=s produz:

[1 0 0 1 1 0 1].

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

=[1⊕1⊕1 1⊕1 1⊕1⊕1]=[1 0 1]=s

s pode ser identificada como a quinta coluna da matriz H( ou a quinta linha da transposta de H), o que indica erro na posição v₅ da palavra recebida, ou seja, a palavra transmitida foi 1001001. Se uma palavra válida for recebida, então s=[0 0 0].

Questões de Revisão
Resolva on-line questões sobre sistemas numéricos, conversão entre sistemas numéricos, códigos e deteção e correção de erros.

Códigos de Barras
Códigos de Barras e Scanners de Código de Barras
Várias caixas registradoras e pontos-de-vendas identificam os produtos que estão vendendo através da leitura óptica de um código de linhas impressas em rótulos ou na embalagem do produto.O código formado por linhas claras e escuras é chamado código de barras. Um código de barras típico é mostrado na Fig.1.

fig8
Fig.8

Códigos de barras geralmente são horizontais com barras verticais alternadas escuras e espaços claros.Os dados são codificados variando as larguras dessas barras e espaços. Para ler um dado, um scanner é movido sobre o código de barras por um operador ou um feixe de luz é emitido pelo scanner sobre o código de barras.
Existem vários padrões de códigos de barras.Os principais são os seguintes:

MSI
UPC(Universal Product Code)
EAN(European Article Number)
CODABAR
2-of-5
2-of-5-Interleaved
Code 39

Especificações detalhadas e tolerâncias dos vários códigos de barras não existem. A falta dessas especificações possibilita amplas variações em um código de barras simples.Como resultado, qualquer scanner de código de barras deve ser projetado para manipular as diversas variações do código de barras.
Os primeiros scanners (leitores) de códigos de barras tinham uma fonte e um detetor de luz(ópticos) no mesmo equipamento.A luz emitida pelo emissor(fonte) passava por uma pequena abertura, localizada na extremidade do equipamento.O feixe óptico(de luz) atinge o código de barras e é refletido, pela mesma abertura, para o detetor de luz.Geralmente, a fonte de luz é ligada a extremidade do leitor através de fibra óptica e esta mesma fibra é usada pela luz refletida no código de barras para alcançar o detetor.
A abertura de um leitor refere-se ao diâmetro da janela na extremidade do leitor pode onde passa a luz refletida. A abertura determina quanto do código de barras o leitor verá.Não deve ser confundida a abertura do leitor e a janela na extremidade leitora.A janela do leitor é escolhida de modo que todo o código seja visto pela abertura do scanner.
A quantidade de luz que atinge o detetor depende do tamanho da abertura do leitor.Um leitor com grande abertura permite que grande quantidade de luz alcance o detetor, enquanto que um pequena abertura deixa pouca luz chegar ao detetor.Como o detetor tem uma faixa de luz nominal ao qual responde, leitores com aberturas menores podem precisar de mais luz da fonte que aberturas maiores, para atender aos requisitos de luz do detetor.Em geral, leitores com pequenas abertura consomem mais luz da fonte que os scanners com maiores aberturas.
Alguns códigos de barras podem ser lidos melhor por leitores com maiores aberturas enquanto para outros códigos de barras, pequenas aberturas são melhores.A Fig.9 abaixo mostra como funciona.

Na figura temos dois tipos de abertura: na superior, um leitor com abertura grande e, na inferior, o leitor tem uma pequena abertura. Se abertura do leitor fôr muito grande e as barras com larguras muito estreitas, então pode ocorrer que o scanner não reconheça as barras.Por exemplo, se as barras têm larguras iguais a 4X10^-3 polegadas(aproximadamente, 9mm) e abertura do leitor é 10X10^-3 polegadas (em torno de 22,5mm), então 60% da abertura refletirá a luz dos espaços em branco ao lado de cada barra.A luz detectada pode não diminuir para um nível que permitirá a barra ser reconhecida. Se a abertura fôr escolhida muito pequena, então qualquer marca ou borrão impresso, como um ponto de tinta, na região das barras, pode ser reconhecida como uma barra estreita; ou uma falha de tinta na barra ser reconhecida como um espaço. Contraste ou tolerância de reconhecimento e consumo de potência formam o critério de seleção para a escolha da abertura de um scanner em relação a determinado código de barras. Então, a abertura do leitor deve ser bastante pequena para reconhecer as barras e larga o suficiente para tolerar erros de impressão. O consumo de potência óptica deve ser aceitável para aplicação desejada.
Fig.9

Para decodificar a informação do código de barras, as larguras relativas de barras claras e escuras devem ser determinadas. Se a velocidade do leitor sobre o código de barras fôsse constante, a distância percorrida pelo leitor poderia ser medida linearmente e as larguras seriam expressas em milésimos de polegadas. Porém, a velocidade do leitor não é constante. A velocidade de varredura está na faixa de 76 a 760 mm/seg.

Desde que o movimento do leitor é variável, as larguras das barras são determinadas medindo-se o tempo relativo em que o leitor as vê.Isto é feito através da amostragem da saída do leitor em uma taxa constante e comparando a taxa de mudança entre barras claras e escuras com essa taxa constante.

Fig.10

Quando o leitor é movimentado sobre o código de barras, como mostrado na Fig.10a, o sinal elétrico é produzido pelo scanner apresenta a forma da Fig.10b.Esse sinal é convertido para o sinal digital mostrado na Fig.10c, e interpretado para determinar o caractere apropriado representado pelo código de barras. Cada espaço claro e escuro no código de barras é igual ou maior que uma unidade de tamanho chamado módulo.

Períodos de sinais elétricos não são medidos em termos de polegadas ou centímetros, mas em termos de tempo.Para produzir o sinal, o scanner é movimentado através do código de barras com certa velocidade.Se a velocidade do scanner fôr conhecida e constante, o sinal poderia ser dado em polegadas ou centímetros com precisão.As larguras das barras e espaços então seriam determinadas e comparadas.Desde que a velocidade do scanner não é conhecida, a largura de espaços e barras é expressa como uma função do tempo.A velocidade do scanner nem é conhecida nem constante sobre o código de barras.Mesmo que a velocidade do scanner fôsse constante, dimensões de larguras diferentes entre diferentes tamanhos de códigos de barras poderiam produzir sinais de larguras variáveis em termos de tempo.

Uma velocidade de 76 a 760mm/s é tolerável para maioria dos operadores e tipos de códigos.

Isto representa uma relação variável de 1 para 10.Desde que a variação de módulo na Fig.10a é apenas 2 para 1, a medida do módulo individual é desprezível.Assim, a comparação da largura do módulo é a única solução possível.

Para o código de barras da Fig.10, o caractere é representado por 7 bits.Sete bits fornecem 128 combinações diferentes.Contudo, neste caso, outras restrições são impostas ao código, como permitir auto-detecção.Isto limita as possibilidades de variações de combinações para 20 e a decodificação pode ser simplificada.Em lugar de usar as larguras de tempo representadas por t₁, t₃, t₄, t₅, e t₆ como aproximadamente iguais, e metade das larguras representadas por t₂ e t₇, que poderia fornecer um numéro binário 0100001, uma maneira diferente é usada.
Os tempos ímpares representando as barras são comparados um ao outro, em base de par-a-par.A possibilidade para cada comparação é que o segundo tempo é igual, menor ou maior que o primeiro tempo.
Exemplos:

t₁ : t₃ igual
t₃ : t₅ igual
t₅ : t₇ maior

Do mesmo modo, tempos pares representando espaços podem ser comparados.
Exemplos:

t₂ : t₄ menor
t₄ : t₆ igual

Para entender esse método, dígitos podem ser designados para essas relações comparativas.

igual é 1
maior é 2
menor é 0

O resultado das comparações acima seria o número 11201.Este número é menor em tamanho que o número 0100001.O número 11201 poderia ser usado com um ponteiro de uma tabela para obter o caractere resultante.A vantagem desse método é que a tabela pode ser dividida em cinco partes.Quando cada comparação é feita, o número de possibilidades é reduzido de modo que a parte da tabela a ser considerada pode ser reduzida até finalmente a quinta comparação localizar o número exato para obter o dígito.Se a interpretação binária fôr usada, o dígito não pode ser obtido até que todos os tempos sejam apresentados(ou seja, o caractere completo seja lido).