Signed Binary Representations Revisited

Conceitos e tecnologias estudadas

wNAF (variação do NAF)

       Definimos wNAF como o resultado do método das janelas deslizantes de largura w da DIREITA para ESQUERDA sobre a representação binária usual.

       O wNAF é da forma:

       onde d[i] Є {0, ±1, ±3, ..., ±(2^w-1 - 1)}.

       Uma seqüência de dígitos com sinal é chamada wNAF se e somente se:

              - O bit mais significativo não nulo é positivo.

              - Dentre quaisquer w dígitos consecutivos, ao menos um é não nulo.

              - Cada dígito não nulo é ímpar e menor que 2^{w -1} em valor absoluto:

       Podemos obter a forma wNAF percorrendo a representação binária usual da DIREITA para ESQUERDA de w em w bits. A cada w bits, verifica-se qual a representação decimal correspondente a representação binária obtida por esses w bits. Para w = 3, temos:

              - Se a representação satisfizer as propriedades de wNAF, seu valor é substituído:

                     na representação decimal é: 0 * 2² + 0 * 2¹ + 1 * 2⁰ = 1

                     Logo, 0 0 1 na representação binária usual continua sendo 0 0 1 na representação wNAF. Agora,

                     na representação decimal é: 0 * 2² + 1 * 2¹ + 1 * 2⁰ = 3

                     Logo, 0 1 1 na representação binária usual passa a ser 0 0 3 na representação wNAF.

              - Caso contrário, ou seja, se o valor na representação decimal não satisfizer as propriedades do wNAF, utiliza-se (w + 1) bits ao invés de w na representação binária, como pode ser observado no exemplo:

                     na representação decimal é: 1 * 2² + 0 * 2¹ + 1 * 2⁰ = 5

                     Como 5 não pertence ao intervalo de valores para w = 3, transformamos esse 5 para a representação binária com sinal utilizando mais um bit:

                     onde 1 * 2³ + 0 * 2² + 0 * 2¹ + -3 * 2⁰ = 5

                     Obs: Caso a janela w termine com 0, copia-se o 0 e vai para os próximos w dígitos. Se os próximos w dígitos terminarem com 0, repete-se o processo até encontrar w dígitos que terminem por valor diferente de 0.

       Um exemplo de wNAF para w = 3 é:

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

            1  0   1  0  1  1  0  0  1                          

            1  0   1  0  0  3  0  0  1                          

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