Signed Binary Representations Revisited

Conceitos e tecnologias estudadas

Mutual Opposite Form (MOF)

       Mutual Opposite Form (MOF) é um string binário com sinal que satisfaz as seguintes propriedades:

              - Os sinais dos bits adjacentes não nulos (sem considerar os bits nulos) são opostos.

              - O maior bit não nulo e o menor bit não nulo são 1 e -1, respectivamente.

       e é da forma:

       onde d[i] Є {-1, 0, 1}.

       Para gerar uma representação na forma MOF, é feita a subtração bit-a-bit (2d – d), onde d é a representação binária usual e 2d é a representação binária usual deslocada 1 bit para a esquerda. Por exemplo, a representação binária do número 345 é 1 0 1 0 1 1 0 0 1.

       Logo,

       Assim, temos:

  2d  =  1   0   1   0   1   1    0   0   1   

 - d  =      1   0   1   0   1    1   0   0   1
 

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

       Onde 1 -1 1 -1 1 0 -1 0 1 -1 é a representação MOF do número 345.

       Teorema 1: Seja n um número inteiro positivo. O (n + 1)-bit MOF tem 2ⁿ pares de representações diferentes, ou seja, qualquer n-bit de string binário pode ser unicamente representado pelo (n + 1)-bit MOF.

       Demonstração:
              - Para n = 1, temos que o 2-bit MOF é 0|0 ou 1|-1, uma vez que o 1-bit dos strings binários 0 e 1 são convertidos para os MOFs 0|0 e 1|-1, respectivamente:

     0    _                    1    _  
       0                          1    
   --------                   -------
      0 0                       1 -1     

              - Para n = k+1, temos 2 casos:
                     - (k+1)-bit do string binário é 0 → podemos assumir que o (k+2)-bit MOF é 0 e aplicar a conversão um-para-um dos k-bits restantes:

      0 *****   _ 
        0 *****   
   -------------
     0 *******  

                    onde * significa que o dígito pode ser 0 ou 1 (ou -1 para a última linha).

                     - (k+1)-bit do string binário é 1 → o k-bit do string binário pode ser 0 ou 1. Logo, convertemos o (k+1)-bit dos string binários 1|0|* e 1|1|* para o (k+2)-bit MOF 1|-1|* e 1|0|*, respectivamente:

        1  0 ****   _                     1 1 *****   _
         1 0 *****                        1 1 *****
     --------------                     --------------
      1 -1 *******                      1 0 *******

                    onde * significa que o dígito pode ser 0 ou 1 (ou -1 para a última linha).

       Proposição 1: A operação µ = 2d - d converte o string binário para µ-MOF.

       Demonstração:
              - Sabemos que µ_n = 1 se d_n-1 = 1. Por µ_i = d_i-1 – d_i, temos µ_i = 0 ou 1 para d_i = 0. Então, o bit mais a esquerda de µ será 1.

              - De µ_i = d_i-1 – d_i = 1, sabemos que d_i-1 = 1 e que µ_i-1 = d_i-2 – d_i-1 = 0 ou -1, baseado em d_i-2 = 1 ou 0, respectivamente. Essa relação nos dá, para algum k,