Estou tentando criar um somador de prefixo paralelo para um somador baseado em negabinário. Negabinary é base vez do familiar binário base . Cada somador de 1 bit gera uma soma e duas (em vez de uma em binário) carregam que vão para o próximo somador.
Para tornar o somador mais rápido, quero usar uma estrutura de prefixo paralelo, como a estrutura de Ladner-Fischer apresentada abaixo. Estou familiarizado com a funcionalidade da célula roxa no sistema binário, mas não tenho certeza de como poderia obter a mesma funcionalidade no sistema negabinário.
A razão pela qual estou fazendo isso é apenas por diversão, ainda não encontrei nenhum uso para negabinário.
Fórmulas para calcular a soma e os valores:
Ladner-fischer carrega a estrutura da árvore:
Se algo não estiver claro, não hesite em perguntar.
fonte
Respostas:
Provavelmente gastei mais tempo com essa questão do que deveria, mas aqui estão minhas descobertas.
Não consigo encontrar nenhum exemplo de um somador de prefixo paralelo "puro" para números negativos. Eu também acho que é um problema em aberto, pois não vi nenhuma prova de que isso não seja possível.
O mais próximo que posso chegar é de um acréscimo negativo negativo de duas etapas (nnba comumente abreviado na literatura). É baseado na seguinte propriedade:
Seja e g ( x ) = x n - 1 ¯ x n - 2 . . . x 1 ¯ x 0 . Estas são basicamente uma operação XOR com e respectivamente. Você pode provar quef(x)=xn−1¯¯¯¯¯¯¯¯¯¯xn−2...x1¯¯¯¯¯x0 g(x)=xn−1xn−2¯¯¯¯¯¯¯¯¯¯...x1x0¯¯¯¯¯
0xAA...AA
0x55...55
Onde o lado esquerdo é a soma negabinária , enquanto o + no lado direito é uma soma binária normal.+nb +
A soma negativa pode ser simplesmente invertida usando a mesma propriedade, mas com um operando zero:
Portanto, para encontrar a soma usando somadores de prefixo paralelos, você pode:
0xAA...AB
Na verdade, tentei encontrar um somador de prefixo paralelo "puro", mas considerei muito complexo o tempo que estava disposto a gastar nele. Aqui está o porquê:
fonte