[ Anterior | Índice | Seguinte ]
Definimos wMOF como o resultado do método das janelas deslizantes de largura w da ESQUERDA para DIREITA sobre MOF.
De modo semelhante ao NAF, construímos wMOF aplicando as seguintes conversões, no caso w = 3:
Obs 1: Os casos não englobados na tabela são as janelas que começam por 0. Neste caso, copia-se o 0 e vai para os próximos w dígitos. Se os próximos w dígitos começarem por 0, repete-se o processo até encontrar w dígitos que comecem 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.2, página 09 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 wMOF:
Começando pelo bit mais a esquerda (mais significativo), 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 wMOF e as substituições são feitas. Maiores detalhes deste processo serão vistos adiante, em Algoritmo - Implementação e Análise : wMOF.
Utilizando a tabela de conversão e a Obs 1 acima ou utilizando somente a Obs 2, para o caso w = 3, percorremos a representação MOF do número 345 da ESQUERDA para DIREITA, obtendo assim o wMOF, ou melhor, o 3MOF:
345 = 1 0 1 0 1 1 0 0 1 (Binary representation)
1 -1 1 -1 1 0 -1 0 1 -1 (MOF representation)
0 0 3 -1 1 0 -1 0 1 -1
0 0 3 0 -1 0 -1 0 1 -1
0 0 3 0 -1 0 0 0 -3 -1 (3MOF representation)
Teorema: Todo inteiro d não-negativo tem uma representação wMOF, que é única exceto pelo número de zeros a esquerda.
Demonstração:
Há 3 casos a tratar:
- conversão MOF → wMOF (já visto acima)
- conversão wMOF → MOF (basta percorrer a forma wMOF da ESQUERDA para a DIREITA, aplicando a tabela de conversão da DIREITA para a ESQUERDA, ou seja, o que estiver na coluna da DIREITA vai ser substituído pelo que está na coluna da ESQUERDA. Quando o dígito não nulo da janela w, na forma wMOF, 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.
|
|