Signed Binary Representations Revisited

Conceitos e tecnologias estudadas

Relações entre as formas de representação

       Nesta seção falaremos das relações entre as formas MOF x NAF e MOF x wNAF. Conforme veremos a seguir, as formas NAF e wNAF podem ser obtidas a partir da forma MOF.

MOF x NAF

       Aplicando o método das janelas deslizantes da DIREITA para ESQUERDA (sem carry) para o MOF de d, obtemos o NAF de d.

       Utilizando as seguintes conversões, temos:

       Com essa tabela e a forma MOF do número 345, por exemplo, obtemos a forma NAF:

   345=    1   0   1   0   1   1   0   0   1   (Binary representation) 

      1   -1   1  -1   1   0  -1   0   1  -1   (MOF representation)    

      1   -1   1  -1   1   0  -1   0   0   1                           

      1   -1   1   0  -1   0  -1   0   0   1                           

      1    0  -1   0  -1   0  -1   0   0   1   (NAF representation)    

MOF x wNAF

       Aplicando o método das janelas deslizantes de largura w (sem carry), da DIREITA para ESQUERDA, para o MOF de d, obtemos o wNAF de d.

       Utilizando novamente como exemplo w = 3, temos a tabela de conversão:

       Obs 1: Os casos não englobados na tabela são as janelas que terminam por 0. Neste caso, copia-se o 0 e vai para os próximos w dígitos. Se os próximos w dígitos terminarem por 0, repete-se o processo até encontrar w dígitos que terminem por valor diferente de 0.

      Obs 2: Não há a necessidade de se utilizar tabelas de conversão para cada tamanho de w, como as descritas na seção 4.1, página 08 de [ 2 ], uma vez que os valores das duas colunas são os mesmos, apenas escritos de formas diferentes (transformando ambas as colunas para decimal, notamos que são os mesmos valores). Basta apenas seguir a idéia do algoritmo wNAF:

             Começando pelo bit mais a direita (menos significativo), é verificado se esse bit é nulo ou não. Caso o bit seja igual a 0, copia-se o 0. Caso contrário, são selecionados w bits. Esses w bits representam algum número na representação binária (potência 2) e são transformados na representação decimal (potência 10). A partir daí, verifica-se se essa representação decimal satisfaz as condições para ser um wNAF e as substituições são feitas. Maiores detalhes deste processo serão vistos adiante, em Algoritmo - Implementação e Análise : wNAF.

       Com essa tabela, a Obs 1 e a forma MOF (ou utilizando somente a Obs 2) para o número 345, por exemplo, obtemos a forma 3NAF:

   345 =  1   0   1   0   1   1   0   0   1  (Binary representation) 

      1  -1   1  -1   1   0  -1   0   1  -1  (MOF representation)    

      1  -1   1  -1   1   0  -1   0   0   1                          

      1  -1   1  -1   0   0   3   0   0   1                          

      1   0   0  -3   0   0   3   0   0   1   (3NAF representation)  

       Teorema: Todo inteiro d não-negativo tem uma representação wNAF, que é única exceto pelo número de zeros a esquerda.

       Demonstração:
              Há 3 casos a tratar:

                     - conversão MOF → wNAF (já visto acima)

                     - conversão wNAF → MOF (basta percorrer a forma wNAF da DIREITA para a ESQUERDA, aplicando a tabela de conversão da ESQUERDA para a DIREITA, ou seja, o que estiver na coluna da ESQUERDA vai ser substituído pelo que está na coluna da DIREITA. Quando o dígito não nulo da janela w, na forma wNAF, for positivo (ou negativo), substitui-se pelo valor da tabela com o dígito mais significativo positivo (ou negativo). Se não houver valor correspondente na tabela, copia-se o primeiro dígito da esquerda e continua-se o processo com os próximos w dígitos.)


                     - estas 2 conversões são inversas uma da outra.