Sistemas de Numeração 2 - Conversão de Representação

Considere dois sistemas de numeração posicionais com as seguintes características:

O TGE (ver o post anterior desta série) garante que qualquer número inteiro possui representação nos dois sistemas. Vamos supor que estamos habituados a realizar operações aritméticas com as representações b-árias dos números inteiros (no próximo artigo desta série vamos tratar disso). Então temos duas situações que precisamos analisar:

• Conhecida a representação b-ária de um número inteiro N, como encontrar a sua representação B-ária equivalente?
• Conhecida a representação B-ária de um número inteiro N, como encontrar a sua representação b-ária equivalente?

Vejamos o primeiro problema. Pelo TGE sabemos que N = P(b) = P(B). Dividindo N[b] por B[b] obtemos o quociente q[b] e o resto r[b]. Mas:

E estas operações evidenciam as seguintes equivalências:

Então vemos que a divisão da representação b-ária de N resultou em um quociente e um resto (expressos como números b-ários), onde o resto corresponde ao valor do coeficiente do termo de mais baixa ordem do polinônio de potências de B equivalente a N. Se substituirmos este valor do resto b-ário pelo símbolo de valor equivalente no conjunto dos algarismos do sistema B-ário teremos o dígito de mais baixa ordem da representção B-ária de N.

Repetindo este processo sobre o quociente b-ário obtido na primeira divisão, o resto b-ário nos dá condição de determinar o segundo dígito de mais baixa ordem da representação B-ária de N. E, assim por diante, enquanto o quociente b-ário obtido não for menor que B, obtemos os dígitos restantes da representação B-ária de N, em ordem crescente de grandeza. Quando o quiciente b-ário obtido for menor que B ele representa o dígito de mais alta ordem da representação B-ária de N.

O procedimento (algoritmo) abaixo formaliza a solução para o nosso primeiro problema:

1. Obter N[b], B[b] e Alg(B) - conjunto dos algarismos do sistema B-ário;
2. Considere G - ordem de grandeza - igual a zero;
3. Efetue a divisão de N[b] por B[b];
4. Procure em Alg(B) o símbolo de valor equivalente ao resto obtido no passo 3;
5. Escreva o algarismo obtido no passo 4 como o dígito de ordem B^G da representação B-ária de N;
6. O quociente obtido no passo 4 é menor que B?
   SIM: vá para o passo 10,
   NÃO: vá para o passo 7;
7. Incremente o valor de OG em uma unidade;
8. Atribua a N[b] o valor do quociente encontrado no passo 3;
9. Volte ao passo 3;
10. Procure em Alg(B) o símbolo de valor equivalente ao quociente obtido no passo 3;
11. Incremente o valor de G em uma unidade;
12. Escreva o algarismo obtido no passo 4 como o dígito de ordem B^G da representação B-ária de N.

A título de exemplo, vamos aplicar este algoritmo para obter a representação hexadecimal equivalente do número decimal 95207.

O sistema binário possui uma peculiaridade: todos os termos não nulos dos polinômios de representação dos números neste sistema são potências de dois, porque os coeficientes dos termos do polinômio de representação neste sistema só podem ser zero ou um. Isto permite um algoritmo alternativo para o caso da conversão de números representados no sistema b-ário (lembrando: este é sistema no qual estamos habituados a executar operações aritméticas) para o sistema binário:

1. Obter N[b];
2. Encontre o maior k para o qual 2^k seja menor ou igual a N[b];
3. Considere o dígito de N[2] de ordem 2^k igual a 1;
4. Calcule a diferença N[b] - 2^k;
5. A diferença obtida no passo 4 é igual a zero? SIM: vá para o passo 8,
   NÃO: vá para o passo 6;
6. Atribua a N[b] o valor da diferença obtida no passo 4;
7. Vá para o passo 2;
8. Considere todos os dígitos de N[2] de ordens de grandeza menores que o maior k obtido no passo 2 e diferentes dos valores de k obtidos no passo 2 como iguais a zero.

Vamos exemplificar o uso deste algoritmo obtendo a representação binária equivalente ao mesmo número decimal que usamos no exemplo anterior:

Existe outro caso particular de algoritmo de conversão, usado quando as bases dos sistemas de numeração para os quais desejamos fazer conversões de representação são tais que existe a relação:

Então (não vou fazer a demonstração disto) existe uma relação bijetora entre os elementos do conjunto de algarismos B-ários e o conjunto de todos os arranjos de k elementos, com repetição, que podem ser formados a partir dos elementos do conjunto de algarismos b-ários.

Por exemplo: no caso dos sistemas binário (base 2) e hexadecimal (base 16) temos este tipo de relação, com k = 4, conforme mostrado na tabela abaixo.

O algoritmo para conversão de representações no sistema b-ário para o sistema B-ário é:

1. Obter N[b] e a tabela de correspondência entre algarismos B-ários e grupos de k algarismos b-ários;
2. Se o número de dígitos de N[b] é um múltiplo de k,
   SIM: vá para o passo 4,
   NÃO: vá para o passo 3;
3. Acrescente à esquerda de N[b] o menor número de algarismos b-ários que representam a quantidade nula que sejam suficientes para que o número de dígitos de N[b] torne-se um múltiplo de k;
4. Separe (da esquerda para a direita) os dígitos de N[b] em grupos de k elementos;
5. Substitua cada um dos grupos formados no passo 2 pelos seus algarismos B-ários correspondentes.

Como exemplo, vamos usar este algoritmo e a tabela de correspondência binário-hexadecimal acima para obter  representação hexadecimal equivalente de 10111001111100111[2].

Então: 10111001111100111[2] = 173E7[16], o que é coerente (conforme esperado) com o que já tínhamos visto nos exemplos anteriores.

Passando agora à análise do nosso segundo problema (obter a representação b-ária a partir da representação B-ária). E, já que estamos com a mão na massa, o caso inverso da conversão binário para hexadecimal apresentada acima é um algoritmo que replica os mesmos passos, porém na ordem inversa:

1. Obter N[B] e a tabela de correspondência entre algarismos B-ários e grupos de k algarismos b-ários;
2. Substitua cada algarismo da representação B-ária pelo grupo de k algarismos b-ários correspondente;
3. Elimine evntuais algarismos nulos não significativos.

O próprio exemplo anterior pode ser usado para demonstrar este algoritmo. Basta acompanhar a sequência de operações de baixo para cima.

Para o caso genérico de conversão B-ário para b-ário usamos o seguinte algoritmo:

1. Obter N[B];
2. Escreva o polinômio P(B) conforme o TGE, substituindo os coeficientes e a base das potências pelos seus valores equivalentes b-ários;
3. Execute as operações de potneciação, multiplicação e soma para obter Obter N[b].

Como exemplo da aplicaçõe deste algoritmo vamos executar o caso inverso do primeiro exemplo apresentado acima: obter a representação decimal equivalente de 173E7[16].

E obtemos, como esperado, o valor decimal 95207.

No primeiro artigo desta série elencamos dois assuntoa a tratar. Com este artigo encerramos o assunto conversão de representação. O próximo artigo deverá tratar da generalização dos procedimentos da aritmética para que eles sejam aplicáveis a qualquer sistema de numeração.