Codificações BCD e Aritmética

Prévia do material em texto

8-1
Capítulo
OITO
Codificações BCD, Numérica e Alfanumérica
8.1 Números e Aritmética BCD
Os computadores digitais atuais trabalham com números binários, uma vez que isto facilita
enormemente a construção destes computadores. No dia-a-dia, entretanto, o sistema decimal
é largamente utilizado (ainda!). Isto obriga a existência de rotinas de conversão de números
decimais para binário e vice-versa; estas rotinas existem em todos os computadores atuais.
Nos computadores mais antigos, entretanto, procurou-se desenvolver uma aritmética binária
que operasse com dígitos decimais, de forma a facilitar estas rotinas de conversão. Neste
sistema, em desuso nos dias de hoje, um grupo codificado de quatro bits é utilizado para
representar cada um dos dez dígitos decimais. Esta é a base do sistema BCD (Binary Coded
Decimal – Decimal Codificado em Binário).
Com quatro bits podem ser codificadas 16 combinações distintas (de 0000 a 1111), mas
existem somente 10 dígitos binários (de 0 até 9). Com isto tem-se 16!/6! = 2,9x1010
diferentes possibilidades para implementar-se uma codificação BCD. Algumas das
combinações mais usuais são ilustradas na tabela apresentada a seguir. A segunda coluna
utiliza o NBCD (Natural BCD), visto que os dígitos são codificados de acordo com sua
representação em binário (com pesos 8,4, 2 e 1 para cada bit). O código de Aiken usa os
pesos 2, 4, 2 e 1 para cada bit, enquanto que o código de Stibitz (também chamado de
excesso de 3) usa os mesmos pesos do NBCD, mas soma três a cada representação. O
código 7421 usa os pesos 7, 4, 2 e 1, enquanto que o código 642-1 utiliza os pesos 6, 4, 2 e
–1.
Dígito decimal Cód. NBCD
(8421)
Cód.Aiken
(2421)
Cód.Stibitz
(8421 – 3)
Cód.7421
(7421)
Cód. 642-1
(642-1)
0 0000 0000 0011 0000 0000
1 0001 0001 0100 0001 0011
2 0010 0010 0101 0010 0010
3 0011 0011 0110 0011 0101
4 0100 0100 0111 0100 0100
5 0101 1011 1000 0101 0111
6 0110 1100 1001 0110 1000
7 0111 1101 1010 0111 1011
8 1000 1110 1011 1001 1010
9 1001 1111 1100 1010 1101
Tabela 8.1 - Codificações BCD
Por sua proximidade do sistema binário, a codificação NBCD é a mais utilizada, e é
denominada por muitos autores simplesmente por BCD, e a aritmética com este código é
denominada de aritmética BCD. Nesta aritmética, os dígitos decimais são operados em
binário, agrupados de quatro em quatro. Quando se soma dois dígitos BCD em binário, o
dígito resultado pode estar em um de três casos:
1. Dígito legal (entre 0 e 9), sem “vai-um”. Neste caso o resultado está correto, e não
existe “vai-um” para o dígito seguinte.
8-2
2. Dígito ilegal sem “vai-um”. Neste caso o resultado está entre 10 e 15 (em binário); para
obter-se o dígito correto deve-se subtrair 10 do dígito (ou somar seis, o que é
equivalente), e gerar-se um “vai-um” para o dígito decimal seguinte.
3. Dígito legal com “vai-um”. Este caso ocorre quando o resultado cai entre 16 e 19; da
mesma maneira que o caso 2, para obter-se o dígito correto deve-se subtrair 10 do
dígito (ou somar seis). O “vai-um” gerado está correto.
Por exemplo, seja A=0832 e B=0983. Então tem-se:
A = 0000 1000 0011 0010
B = 0000 1001 1000 0011
0001 0001 1011 0101
caso 1 caso 3 caso 2 caso 1
Para corrigir o resultado, deve-se somar seis nos dígitos dos casos 2 e 3. No caso 2, ainda é
necessário propagar um “vai-um” (isto não é necessário no caso 3, pois o “vai-um” já foi
gerado).
 1
0001 0001 1011 0101
0110 0110
0001 1000 0001 0101
Com isto tem-se 1815, que é o resultado correto. Uma desvantagem da correção do resultado
dessa maneira é que as correções do tratamento do “vai-um” no caso 2 podem criar novas
correções, como por exemplo no caso de A=0372 e B=0633:
A = 0000 0011 0111 0010
B = 0000 0110 0011 0011
0001 1001 1010 0101
caso 2
Com a correção do caso 2, tem-se:
 1
0000 1001 1010 0101
0110
0000 1010
caso 2
0000 0101
E a nova correção deste novo caso 2 fornece o resultado correto (1005). Para evitar este
tratamento especial, foi criado o algoritmo de Hellerman, que soma 6 em todos os dígitos de
um dos operandos antes da soma das duas parcelas. Assim, só existem dois casos a serem
tratados, distinguidos pelo “vai-um”:
1. O resultado não deu “vai-um” e então caiu entre 6 e 15. Deve-se subtrair 6 para obter o
dígito correto.
2. O resultado produziu um “vai-um”. Então este “vai-um” já foi propagado e o dígito
está correto entre 0 e 9.
Por exemplo, seja A=0372 e B=0633. Então tem-se:
A = 0000 0011 0111 0010
soma de 6 0110 0110 0110 0110
0110 1001 1101 1000
Se a primeira etapa produzir um “vai-um” entre dígitos decimais, isto significa que o dígito
original do operando terá sido ilegal; este número está mal representado. A segunda etapa
realiza a soma de (A+6) com o segundo operando (B):
8-3
 1 1
A+6= 0110 1001 1101 1000
B= 0000 0110 0011 0011
0111
caso 1
0000
caso 2
0000
caso 2
1011
caso 1
Na terceira e última etapa, ao invés de subtrair 6 (0110), soma-se 10 (1010) e ignora-se o
“vai-um”).
0111 0000 0000 1011
1010 1010
0001 0000 0000 0101
O resultado, 1005, já está correto.
Para a subtração utilizam-se técnicas semelhantes. Para maiores detalhes sobre aritmética
BCD pode-se consultar o livro “Projeto de Computadores Digitais”, de Glen George
Langdon Jr. e Edson Fregni, capítulo 2 (Códigos, números e aritmética). As operações de
divisão e multiplicação operam de forma semelhante aos métodos utilizados na nossa
aritmética decimal, mas atuando sobre cada dígito BCD individualmente. Estas operações
não possuem hoje em dia nenhum interesse prático e, devido às extensões dos seus
algoritmos, não serão abordadas aqui.
8.2 Codificação
Os computadores atuais trabalham unicamente com dígitos binários (bits); nenhum outro
símbolo é utilizado. Qualquer informação, seja ela numérica ou alfabética, deve ser
representada utilizando-se combinações adequadas destes bits. A este processo genérico de
representação dá-se o nome de codificação, ou seja, um mapeamento entre os símbolos
utilizados externamente ao computador e os grupos de bits escolhidos para representar estes
símbolos.
Todas as representações de números vistas até o momento (inteiros positivos,
sinal/magnitude, complemento de um, complemento de dois, ponto fixo, ponto flutuante,
BCD) são exemplos de codificações. O objetivo comum a todas estas codificações era
representar números no sistema de numeração arábico; para cada codificação foram
estudadas a maneira de representar os números no sistema binário e inclusive a maneira de
operar com estes números codificados.
Diversas outras aplicações, entretanto, também utilizam códigos. Assim, tem-se códigos
desenvolvidos para manipular caracteres alfanuméricos, símbolos especiais (pontuação,
letras gregas, etc), símbolos matemáticos, e toda a gama de informação que deve ser
manipulada ou armazenada em um computador.
De uma forma geral, se uma determinada codificação utiliza ‘n’ bits, podem ser
representados 2n símbolos distintos, ou seja, tem-se 2n combinações distintas que podem ser
realizadas com estes ‘n’ bits. Os códigos não necessitam utilizar todas as combinações
possíveis (como é o caso dos códigos BCD), nem a informação necessita estar codificada de
forma inequívoca (como é o caso do duplo zero em sinal/magnitude ou de números não
normalizados em ponto flutuante). Cada sistema de codificação pode estabelecer suas
próprias regras de formação e manipulação dos grupos de bits.
8.3 Códigos BCD (ou códigos de 4 bits ponderados)
Conforme já foi visto, nos códigos BCD um grupo codificado de quatro bits é utilizado para
representar cada um dos dez dígitos decimais. Como uma metodologia para realizar
8-4
operações aritméticas estes códigos estão em desuso, mas como uma maneira de armazenar
números decimais eles ainda são utilizados.
Como já foi visto, existem 2,9x1010 diferentes possibilidades para implementar-se uma
codificaçãoBCD. Algumas delas foram analisadas no capítulo anterior. Dois dos códigos
BCD ainda são bastante utilizados hoje em dia: o BCD natural e o código em excesso-de-três
(Stibitz). Ambos estão reproduzidos abaixo:
Dígito decimal NBCD
(8421)
Excesso-de-3
(8421 – 3)
0 0000 0011
1 0001 0100
2 0010 0101
3 0011 0110
4 0100 0111
5 0101 1000
6 0110 1001
7 0111 1010
8 1000 1011
9 1001 1100
Tabela 8.2 - Códigos BCD de 4 bits
O código BCD natural tem uma correspondência “natural” entre os dígitos decimais e a
codificação binária. Os próprios pesos das posições binárias seguem os valores utilizados no
sistema arábico (8, 4, 2 e 1). O código em excesso de três também tem os mesmos pesos,
mas a cada codificação binária soma-se 3.
Para o código NBCD (denominado simplesmente de BCD) foi desenvolvida uma aritmética
binária, conforme já foi visto anteriormente.
O mesmo ocorre com o código de excesso-de-três, que possui duas vantagens: nenhum
código utiliza a combinação 0000, e o código é auto-complementado para 9, ou seja, para se
obter o complemento de 9 de um código decimal, basta inverter todos os bits.
A aritmética em excesso de 3 é relativamente fácil. Quando dois dígitos em excesso de 3 são
somados, o resultado será em excesso de 6, e tem-se dois casos a tratar:
• A soma dos dois dígitos é nove ou menos. Neste caso, a soma em excesso resultará
em um dígito que é 15 ou menos, e nenhum carry será gerado. Nestes casos, basta
subtrair 3 do resultado para obter o dígito corretamente codificado em excesso de 3.
• A soma dos dois dígitos é 10 ou mais. Neste caso, a representação em excesso será
16 ou mais. Como X e X+16 tem o mesmo código, a diferença está na geração de
um ‘vai-um’. Para corrigir o resultado, ou seja, representar X em excesso de 3,
basta somar 3.
Assim, a regra para a soma em excesso de três é simples: soma-se os dígitos usando
aritmética binária; se um ‘vai-um’ é gerado, somar 3 (0011) ao dígito decimal; senão,
subtrair 3 (0011) ao dígito decimal (ou somar 1101 e desprezar o ‘vai-um’).
Diversos outros códigos também podem ser desenvolvidos atribuindo-se pesos distintos às
diversas posições; o nome destes códigos é normalmente formado pelos pesos. Abaixo são
exemplificados alguns deles (4221, 2421 (Aiken), 5421, 7421, e 642(-1), com peso
negativo). Note-se que a escolha dos pesos não determina de forma inequívoca a
codificação, mas apenas facilita sua compreensão. Assim, por exemplo, no código 4221 o
dígito decimal 2 pode ser codificado tanto por 0010 (como na tabela) como por 0100; o
dígito 6 poderia ser codificado como 1010 ou por 1100 (esta última utilizada na tabela).
8-5
Dígito decimal 4221 2421 5421 7421 642(-1)
0 0000 0000 0000 0000 0000
1 0001 0001 0001 0001 0011
2 0010 0010 0010 0010 0010
3 0011 0011 0011 0011 0101
4 1000 0100 0100 0100 0100
5 0111 1011 1000 0101 0111
6 1100 1100 1001 0110 1000
7 1101 1101 1010 0111 1011
8 1110 1110 1011 1001 1010
9 1111 1111 1100 1010 1101
Tabela 8.3 - Códigos BCD pouco utilizados
Cada um destes códigos sempre é desenvolvido com algum propósito ou aplicação específica
em mente. Por exemplo, o código 4221 é auto-complementado em 9 (como o são todos os
códigos cuja soma dos pesos é 9). Nenhum dos códigos da tabela anterior, entretanto, é
apropriado para operações aritméticas.
Outros códigos possíveis seriam 5221, 5321, 6331, 5211, 6321, 7321, 4421, e 6421.
Também são possíveis códigos com pesos negativos, como 531(-1), 522(-1), 732(-1), e
621(-1). Apesar de possíveis, nenhum destes códigos já foi utilizado em qualquer aplicação
prática. Seu estudo foi meramente teórico.
8.4 Códigos de cinco bits ponderados
Várias máquinas (já ultrapassadas) foram desenvolvidas utilizando cinco bits ponderados. O
código 74210, ilustrado na tabela a seguir, é um destes códigos. Ele ainda possui a
vantagem adicional de que todos os dígitos codificados contém dois e somente dois bits em
“um”, o que facilita a verificação se uma palavra pertence ao código ou não.
Dígito decimal Cód. 74210
0 11000
1 00011
2 00101
3 00110
4 01001
5 01010
6 01100
7 10001
8 10010
9 10100
Tabela 8.4 - Código BCD de 5 bits
Os dois “uns” em cada dígito decimal torna possível a detecção de erros simples (erro em um
único bit) em cada dígito. Qualquer dígito que não apresentar “uns”, ou somente um “um”,
ou mais de dois ”uns” pode ser facilmente identificado como errôneo. O valor zero
(codificado como 11000) está contra os pesos utilizados, mas foi assim codificado para
manter a regra dos dois “uns”.
8.5 Códigos de sete bits ponderados
Um código de sete bits ponderados foi utilizado pela IBM, no modelo IBM 650. Este
código, de sete bits com pesos 5043210, é também denominado de biquinário. Ele possui
dois grupos de bits, um com dois e outro com cinco bits. Este código também pode ser
considerado como um código “m de n” (veja-se seção 8.8).
8-6
Dígito decimal 50 43210
0 01 00001
1 01 00010
2 01 00100
3 01 01000
4 01 10000
5 10 00001
6 10 00010
7 10 00100
8 10 01000
9 10 10000
Tabela 8.5 - Código BCD de 7 bits
Nos sete bits de qualquer palavra de código, somente dois bits estão em “um”, os demais são
zeros. Além disto, um destes “uns” está no grupo da esquerda (de dois bits) e o outro “um”
está no grupo da direita (de cinco bits). Qualquer código com uma quantidade de “uns”
diferente de dois, ou com mais de um “um” em cada grupo, indica um dígito inválido ou
então um erro. O grupo à esquerda indica se o dígito é menor ou igual a quatro ou então
maior ou igual a cinco. Operações aritméticas podem ser realizadas com relativa facilidade, o
que contribuiu para o seu uso. As operações aritméticas estão baseadas no fato de um dígito
ser incrementado de uma unidade deslocando-se o ‘1’ para a esquerda. Atualmente este
código caiu em desuso, exceto para algumas aplicações específicas.
Um código semelhante é o qui-binário, com pesos 8, 6, 4, 2, 0 / 1, 0.
8.6 Códigos Gray (ou códigos cíclicos)
Estes códigos não são utilizados para cálculos aritméticos, mas sim para indicar a variação de
grandezas analógicas (temperatura, ângulo, pressão, voltagem, etc) em forma digital. Estas
grandezas não alteram seus valores de forma brusca, mas sim variam de um valor para outro
de forma contínua. Assim, os códigos de Gray foram desenvolvidos de tal forma que, ao se
avançar de um número para o seguinte, somente um bit do código varia, ou seja, dois
códigos adjacentes se diferenciam somente por uma posição binária. Existem diversas
possibilidades para os códigos cíclicos. O código Gray mais comum (denominado
simplesmente de “código Gray“) é mostrado na Tabela 8.6 a seguir.
Dígito decimal Cód. Gray
0 0000
1 0001
2 0011
3 0010
4 0110
5 0111
6 0101
7 0100
8 1100
9 1101
10 1111
11 1110
12 1010
13 1011
14 1001
15 1000
Tabela 8.6 - Código Gray de 4 bits
8-7
Note-se que todas as 16 combinações possíveis estão presentes; não existem combinações
ilegais ou que indiquem erro. Mas de um código para o seguinte sempre existe somente um
bit que varia o seu valor.
Compare-se, por exemplo, a variação de 3 para 4. Em binário, isto implicaria a variação do
código 0011 para 0100, com a troca de valor de três dígitos binários. No código Gray visto
na Tabela 8.6, a variação é de 0010 para 0110, com a troca de somente um bit. Note-se
também que o código é cíclico, ou seja, do valor 15 para zero (ou vice-versa) também existe
a variação de somente um bit.
Para este código Gray pode-se desenvolver procedimentos de conversão para decimal e
binário. Um número decimal pode ser convertido para Gray convertendo-se primeiramente
este número para binário. A seguir, cada bit é somado em módulo dois com o bit à esquerda
(a soma em módulo dois é uma soma sem ‘vai-um’, ou seja, o resultado somente é um
quando os dois operandos forem diferentes).
Por exemplo, o número decimal 45 é representado por 0101101 em binário. E a conversãopara código Gray produz:
0 1 0 1 1 0 1
Ú Ú Ú Ú Ú Ú
1 1 1 0 1 1
Assim, o código Gray de 45 é 111011.
Converter do código Gray para decimal é realizado primeiro convertendo-se de Gray para
binário e depois para decimal. A conversão para binário é realizada analisando-se os bits da
esquerda para a direita. Os zeros bits de mais alta ordem são mantidos inalterados até o
primeiro ‘1’, inclusive. A partir daí, os bits zero são invertidos para um até o próximo ‘1’.
Este ‘1’ também é invertido para zero, e os zeros seguintes são copiados inalterados até o
próximo ‘1’ (que também é copiado). Passa-se então à inversão até o próximo ‘1’, a partir
do qual copia-se normalmente até o ‘1’ seguinte, e assim por diante até serem analisados
todos os bits.
Por exemplo, seja o código Gray 001001011. Convertendo-o para binário tem-se:
• 001 Copia-se todos os zeros até o primeiro ‘1’.
• 001110 Inverte-se os bits seguintes até o próximo ‘1’.
• 00111001 Copia-se todos os bits até o ‘1’ seguinte.
• 001110010 Inverte-se os bits até o próximo ‘1’.
Ou seja, obtém-se 001110010, que corresponde em decimal a 114. Note-se que a regra geral
alterna entre cópia dos bits e a inversão dos bits; cada bit ‘em 1’ indica que deve ser realizada
uma troca (deste ‘1’ inclusive).
Este código Gray em particular é um código binário refletido. Um código é dito refletido
quando ele é simétrico (com exceção do bit de mais alta ordem) em relação ao ponto médio
da lista codificada em ordem crescente de valor. Os códigos Gray que não são refletidos são
complexos de serem codificados.
Existem diversos códigos Gray com diferentes tamanhos de ciclo (números de códigos
distintos utilizados). Normalmente eles são referenciados pelo tamanho do seu ciclo e por
uma lista de números. Por exemplo, o código Gray visto acima é referenciado como sendo
de ciclo 16 (1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,4). Os números da lista indicam a posição (a
partir da direita) do bit que é invertido no código atual para formar o próximo código. A
codificação pode iniciar em qualquer número binário (no caso do exemplo, um número de 4
bits). Por exemplo, um código Gray de comprimento 6 (1,2,1,3,2,3) será diferente se
iniciado em números binários diferentes, conforme pode ser visto na tabela a seguir.
8-8
Dígito Codificação inicial em:
decimal 000 001 010 011 100 101 110 111
0 000 001 010 011 100 101 110 111
1 001 000 011 010 101 100 111 110
2 011 010 001 000 111 110 101 100
3 010 011 000 001 110 111 100 101
4 110 111 100 101 010 011 000 001
5 100 101 110 111 000 001 010 011
6 000 001 010 011 100 101 110 111
Tabela 8.7 - Codificação de código Gray
Assim, para caracterizar inequivocamente um código Gray, além do comprimento e da
seqüência de formação, também deve-se indicar a codificação inicial. Uma lista de alguns
códigos possíveis é fornecida abaixo:
• para dois bits: Comprimento 4 (1,2,1,2)
• para três bits: Comprimento 6 (1,2,1,3,2,3)
Comprimento 6 (1,2,3,1,2,3)
Comprimento 8 (1,2,1,3,1,2,1,3)
• para quatro bits: Comprimento 8 (1,2,3,4,1,4,3,2)
Comprimento 10 (1,2,1,3,4,3,1,2,1,4)
Comprimento 10 (1,2,1,3,4,1,2,1,3,4)
Um código Gray de 5 bits de comprimento 10, comumente utilizado em operações de
contagem, é o “código caminhante” (do inglês “walking code” ou “creeping code”):
Dígito Código
0 00000
1 00001
2 00011
3 00111
4 01111
5 11111
6 11110
7 11100
8 11000
9 10000
Tabela 8.8 - Código Gray de 5 bits
A razão para o uso deste código está na sua facilidade de implementação. Para avançar o
contador de uma unidade, basta mover todos os bits para a esquerda, inverter o bit mais
significativo e colocá-lo na posição mais à direita (bit menos significativo).
8.7 Códigos de detecção e correção de erros
Quando informação é transferida de uma seção para outra do computador, ou mesmo entre
dois computadores, não é incomum a ocorrência de erros, sejam eles devidos a ruídos
eletromagnéticos ou ao mau funcionamento de um componente. Se uma codificação binária
de ‘n’ bits utiliza todas as combinações possíveis (2n), então erros não podem ser nem
detectados nem corrigidos. Como todas as combinações são válidas, não existem
combinações inválidas. Um erro sempre irá transformar uma codificação válida em outra
codificação também válida.
Para ser possível a detecção de erros, e até mesmo sua correção, deve-se introduzir
redundância na codificação, seja na forma de bits extras ou do uso de combinações inválidas.
8-9
Três técnicas principais serão analisadas nas seções seguintes: códigos m-de-n, códigos com
paridade e códigos de Hamming. Todos estes códigos utilizam o mesmo comprimento em
bits para sua codificação. Existem códigos de comprimento variável, em que os símbolos
mais freqüentes utilizam menos bits que os símbolos menos freqüentes. Assim, por
exemplo, a codificação da letra “e” utilizaria muito menos bits que a letra “q”. Estes códigos,
como por exemplo código Morse, código de Shannon-Fano, código de Huffman, não serão
analisados aqui.
8.8 Códigos m-de-n
Os códigos m-de-n são compostos de tal forma que os ‘n’ bits de uma palavra binária são
formados por ‘m’ “uns” e ‘n-m’ “zeros”. Com esta limitação, de 2n combinações binárias
possíveis somente (n/m) combinações, ou seja, n!/m!(n-m)!. Este número de combinações é
maximizado quando m=n/2 (ou m=n/2 ± 1/2, se n for ímpar).
No código 2-de-5, onde palavras de 5 bits apresentam sempre 2 bits em ‘1’, tem-se então
exatamente 5!/2!(5-2)! = 5!/2!3! = 5.4/1.2 = 10 combinações válidas. Este código já foi
analisado na seção 7.3 (códigos de cinco bits ponderados, com pesos 74210). Outra
codificação possível é a 2-de-7, o código biquinário. Este código já foi analisado na seção
8.5 (códigos de sete bits ponderados, com pesos 5043210).
8.9 Códigos de paridade
Nestes códigos é adicionado um bit à palavra codificada, de tal forma que o número de “uns”
seja par (paridade par) ou ímpar (paridade ímpar). A tabela a seguir ilustra o uso de bits de
paridade par e ímpar para um código de três bits.
Código Paridade par Soma dos ‘1’ Paridade ímpar Soma dos ‘1’
000 0 0 1 1
001 1 2 0 1
010 1 2 0 1
011 0 2 1 3
100 1 2 0 1
101 0 2 1 3
110 0 2 1 3
111 1 4 0 3
Tabela 8.9 - Códigos de paridade
Se o código utilizado for de paridade par, todas as palavras com um número ímpar de “uns”
podem ser rejeitadas e sinalizadas como errôneas. Se o código for de paridade ímpar,
qualquer palavra com um número par de “uns” estará errada.
Assim, pode-se detectar qualquer erro simples (inversão de um bit). Mas não existe neste
código a capacidade de detectar dois ou mais erros (como por exemplo um erro que
transforme o código 011001 em 101001 – o número de uns permanece ímpar, mas a palavra
foi alterada). Também não existe a capacidade de corrigir o bit errôneo.
8.10 Códigos de Hamming
Os códigos de Hamming, desenvolvidos por R.W. Hamming, introduzem vários bits de
paridade, que possibilitam não só a detecção de erros mas também a sua correção. Um
conceito importante para tal é a “distância de Hamming”, ou seja, o número de bits que são
alterados entre dois códigos adjacentes.
8-10
Por exemplo, se estes dois códigos são 0001 e 0100, sua distância é de 2; entre os códigos
0000 e 1111 a distância é de 4. Se a distância de Hamming for de 1, como por exemplo em
000, 100, 101, 001, 011, 111, 110 e 010, não é possível nem a detecção nem a correção de
erros; cada erro transforma um código válido em outro também válido. Se a distância for de
2, como por exemplo em 000, 011, 110 e 101, então é possível detectar-se um erro, mas que
não pode ser corrigido (por exemplo, 001 poderia ter sido originado tanto de 000 como de
101 ou 011). Se a distância for de 3, como por exemplo em 011 e 100, então um erro
simples pode ser detectado e corrigido (por exemplo, 000 só poderia ter sido originado de
100), e um erro duplo pode ser detectado.
O código de Hamming corrige um erro alterando a palavraerrada para o código válido mais
próximo (de menor distância), desde que esta menor distância seja inequívoca, isto é, não
existam duas ou mais palavras corretas à igual distância da palavra errada.
Para possibilitar a correção de um erro simples, o código de Hamming mostrado na tabela a
seguir utiliza três bits adicionais de paridade (A, B e C) para os quatro bits de código
(ponderados por 8, 4, 2 e 1).
Posição 1 2 3 4 5 6 7
Código A B 8 C 4 2 1
0 0 0 0 0 0 0 0
1 1 1 0 1 0 0 1
2 0 1 0 1 0 1 0
3 1 0 0 0 0 1 1
4 1 0 0 1 1 0 0
5 0 1 0 0 1 0 1
6 1 1 0 0 1 1 0
7 0 0 0 1 1 1 1
8 1 1 1 0 0 0 0
9 0 0 1 1 0 0 1
10 1 0 1 1 0 1 0
11 0 1 1 0 0 1 1
12 0 1 1 1 1 0 0
13 1 0 1 0 1 0 1
14 0 0 1 0 1 1 0
15 1 1 1 1 1 1 1
Tabela 8.10 - Código de Hamming
Neste caso, o bit ‘A’ é usado para calcular a paridade par das posições 1, 3, 5 e 7. O bit ‘B’
é usado para obter-se paridade par nas posições 2, 3, 6 e 7 enquanto que ‘C’ realiza a
paridade par para as posições 4, 5, 6 e 7.
Existindo um erro, a posição do bit em erro é calculada por ‘cba’, onde ‘c’, ‘b’ e ‘a’ serão
zeros se a paridade calculada por ‘C’, ‘B’ e ‘A’ for par ou “uns” se a paridade for ímpar. Por
exemplo, se o número seis (1100110) for recebido erroneamente como 1100010, tem-se:
• verificação das posições 4, 5, 6 e 7: paridade ímpar: c = 1
• verificação das posições 2, 3, 6 e 7: paridade par: b = 0
• verificação das posições 1, 3, 5 e 7: paridade ímpar: a = 1
Assim, ‘cba’ = 101, ou seja, a posição 5 está errada e seu bit deve ser invertido para ser
corrigido. Se o número tivesse sido recebido correto, a combinação dos bits de paridade
seria zero (000).
Esta codificação pode ser estendida para qualquer número ‘n’ de bits de informação, desde
que ‘k’ bits de paridade sejam adicionados de acordo com a fórmula 2k ‡ n + k + 1. A tabela
a seguir ilustra alguns casos.
8-11
Bits de informação Bits de paridade
4 3
5 4
11 4
12 5
26 5
27 6
57 6
Tabela 8.11 - Bits de paridade no código de Hamming
8.11 Códigos alfabéticos (ou códigos alfanuméricos)
Os computadores devem manipular não somente informação numérica, mas também
informação alfabética, constituída de caracteres, sinais de pontuação e dígitos numéricos. Os
códigos que permitem este tipo de representação são denominados de códigos alfanuméricos.
Os primeiros códigos desenvolvidos utilizavam 6 bits, o que possibilitava a representação de
todos as letras maiúsculas (26), os dígitos decimais (10) e mais uma série de caracteres
especiais (ponto, vírgula, dois pontos, etc). Um destes códigos é o Hollerith, utilizado pela
IBM em cartões perfurados. Note-se que não havia a previsão para letras minúsculas.
Rapidamente os códigos foram estendidos para sete bits (inclusão das letras minúsculas) e
posteriormente para oito bits. Os dois códigos mais amplamente utilizados são o ASCII
(American Standard Code for Information Interchange) e o EBCDIC (Extended Binary
Coded Decimal Interchange Code). As letras são codificadas de tal forma a facilitarem a
ordenação alfabética de informação textual através da simples ordenação binária crescente.
O código ASCII de sete bits (com 128 combinações possíveis) é mostrado na Tabela 8.12.
Os códigos de 0 a 31 são reservados para caracteres de controle, como por exemplo
tabulação (ht), retorno de carro (cr), ejeção de página (ff), aviso sonoro (bel), retrocesso
(bsp), avanço de linha (lf), tabulação vertical (vt), escape (esc) e outros. Os caracteres
visíveis vão do código 32 (espaço em branco) até o 126 (caracter til). Note-se que dígitos e
letras estão em ordem numérica crescente (mas não contínua entre si), que não existe
codificação de nenhum caracter acentuado, e que letras maiúsculas e minúsculas possuem
uma diferença numérica de 32.
Bits Bits superiores (mais significativos)
inferiores 000 001 010 011 100 101 110 111
0000 null dle 0 @ P ` p
0001 soh dc1 ! 1 A Q a q
0010 stx dc2 " 2 B R b r
0011 etx dc3 # 3 C S c s
0100 eot dc4 $ 4 D T d t
0101 enq nak % 5 E U e u
0110 ack syn & 6 F V f v
0111 bell etb ' 7 G W g w
1000 bsp can ( 8 H X h x
1001 ht em ) 9 I Y i y
1010 lf sub * : J Z j z
1011 vt esc + ; K [ k {
1100 ff fs , < L \ l |
1101 cr gs – = M ] m }
1110 so rs . > N ^ n ~
1111 si us / ? O _ o del
Tabela 8.12 - Código ASCII de 7 bits
8-12
O código ASCII foi posteriormente estendido para oito bits, com a incorporação de mais 128
combinações à tabela acima. Com isto pode-se representar caracteres acentuados (á, à, â, ä,
ã, å, ñ, ç, etc) e diversos símbolos específicos de diversas línguas. Não existe, entretanto,
uma definição única para esta tabela ASCII de 8 bits; cada fabricante desenvolveu a sua
própria.
Atualmente oito bits já se tornaram insuficientes para representar todos os símbolos
utilizados. Não há espaço disponível, por exemplo, para codificação do alfabeto grego, árabe
ou cirílico (para não mencionar os alfabetos hindus, japoneses e chineses). Para solucionar o
problema, estuda-se atualmente um código de 16 bits, que possibilitaria representar 65536
símbolos distintos (Unicode).