Cálculo da raiz quadrada do número binário de 8 bits

14

Eu estava procurando uma maneira de calcular a raiz quadrada de um determinado número de 8 bits usando apenas combinação digital ou lógica seqüencial. Isso é possível?

Uma maneira pode ser usar apenas uma tabela de consulta, pois não estou considerando partes fracionárias (então ), mas deve haver uma maneira melhor do que isso. Alguém pode me indicar isso?103

Rick_2047
fonte
4
Eu usaria uma tabela de pesquisa simples com intervalos. Número mínimo e máximo para cada saída e você apenas verifica.
Kortuk
6
Uma pesquisa parece bastante simples. Afinal, existem apenas 16 respostas possíveis para a raiz quadrada de um número de 8 bits.
amigos estão dizendo
3
hmm .. as únicas respostas são 0000 a 1111; somente as entradas 64 ou mais terão o bit mais alto definido na resposta, portanto, esse é apenas um OR dos dois bits mais altos da entrada. Agora você só tem três funções de 8 bits para reduzir ..
JustJeff

Respostas:

9

As tabelas de pesquisa foram mencionadas nos comentários. Existem duas abordagens.

Rápido
Crie uma tabela com 256 bytes de comprimento, com cada próximo valor a raiz quadrada do índice correspondente. Isso é rápido, pois você usa o argumento como índice para acessar diretamente o valor correto. A desvantagem é que ele precisa de uma tabela longa, com muitos valores duplicados.

Compacto
Como dito, um número inteiro de 8 bits pode ter apenas valores de 0 a 255 e as raízes quadradas correspondentes são de 0 a 16 (arredondadas). Construa uma tabela de 16 entradas (com base em zero) com a n-ésima entrada o valor máximo para o argumento para o qual a raiz quadrada é n. A tabela ficaria assim:

 0  
 2  
 6  
12  
20
etc.

Você percorre a tabela e para quando encontra um valor maior ou igual ao seu argumento. Exemplo: raiz quadrada de 18

set index to 0
value[0] = 0, is less than 18, go to the next entry  
value[1] = 2, is less than 18, go to the next entry  
value[2] = 6, is less than 18, go to the next entry  
value[3] = 12, is less than 18, go to the next entry
value[4] = 20, is greater than or equal to 18, so sqrt(18) = 4

Embora a tabela de pesquisa rápida tenha um tempo de execução fixo (apenas uma pesquisa), aqui o tempo de execução é mais longo para argumentos de valor mais alto.

Para os dois métodos, ao escolher valores diferentes para a tabela, você pode selecionar entre um valor arredondado ou um truncado para a raiz quadrada.

stevenvh
fonte
2
Se você ativar essa mesa de cabeça para baixo você vai precisar de menos iterações, em média
Federico Russo
Uma pesquisa binária na tabela mais curta pode acelerar o algoritmo, em média. Você começa na metade da tabela de pesquisa (posição 8) e decide se o valor encontrado é muito alto ou muito baixo e sobe ou desce 4 posições. Repita até terminar.
jippie
7

Trabalhando em 8 bits, você está basicamente restrito a soluções inteiras. Se você precisa da raiz quadrada de X, o mais próximo que conseguir é o maior número inteiro cujo quadrado é menor ou igual a X. Por exemplo, para sqrt (50), você obteria 7, pois 8 * 8 seria maior que 50

Então, aqui está um truque para fazer isso: conte quantos números ímpares, começando com 1, você pode subtrair do X. Você poderia fazer isso com a lógica da seguinte maneira: um registrador de 8 bits R1 mantém o valor de trabalho, um contador de 7 bits R2 mantém (a maior parte) o número ímpar e um contador de 4 bits R3 mantém o resultado. Na redefinição, R1 é carregado com o valor de X, R2 é zerado e R3 é zerado. Um circuito subtrator de 8 bits é alimentado com R1 para a entrada 'A' e o valor de R2 combinado com um LSB fixo em '1' (via pull-up) para a entrada 'B'. O subtrator gera uma diferença de 8 bits AB e um bit de empréstimo. A cada relógio, se o bit de empréstimo for limpo, R1 será carregado com a saída do subtrator, R2 será incrementado e R3 será incrementado. Se o bit de empréstimo for definido, R1 não será carregado e R2, R3 não serão incrementados, porque o resultado está pronto em R3.

ALTERNATIVAMENTE

Existem apenas 16 valores de saída possíveis, portanto a resposta é um número de quatro bits. Essencialmente, você tem quatro funções de bit único dos 8 bits de entrada. Agora, não consigo desenhar um mapa de Karnaugh em 8 dimensões, mas, em princípio, você pode simplesmente criar um circuito combinatório para cada parte da resposta. Pegue as saídas desses quatro circuitos combinatórios e interprete-as como a resposta de quatro bits. Voila. Sem relógios, sem registros, apenas um monte de NAND e NOR seriam suficientes.

JustJeff
fonte
Estive pensando nisso a noite toda. O bit 8 na saída é claramente uma função dos dois bits de entrada mais significativos. Da mesma forma, acho que o bit 4 na saída provavelmente é uma função apenas dos 4 principais bits de entrada: 00x1, 001x, 1xx1 e 11x1 parecem configurá-lo. Irá verificar isso mais tarde.
precisa saber
1
Se você estiver fazendo isso em um FPGA, poderá simplesmente fazer uma grande casedeclaração e deixar a ferramenta de síntese fazer todo o trabalho. Por um lado, é como fazer uma grande tabela de pesquisa na RAM distribuída (usada como ROM); por outro lado, a ferramenta deve encontrar otimizações como você menciona no seu comentário.
The Photon
5

Não sei se isso ajuda, mas há uma maneira engenhosamente simples de calcular uma raiz quadrada:

unsigned char sqrt(unsigned char num)
{
    unsigned char op  = num;
    unsigned char res = 0;
    unsigned char one = 0x40;

    while (one > op)
        one >>= 2;

    while (one != 0)
    {
        if (op >= res + one)
        {
            op -= res + one;
            res = (res >> 1) + one;
        }
        else
        {
            res >>= 1;
        }

        one >>= 2;
    }
    return res;
}

Não sei muito sobre o que pode e o que não pode ser feito na lógica sequencial, mas como esse algoritmo termina em apenas 4 loops, você poderá implementá-lo em 4 estágios.

Rocketmagnet
fonte
4

28

    A =     a
     or     b;

    B =     a and     b
     or not b and     c
     or not b and     d;

    C =     a and     b and     c
     or     a and     b and     d
     or     a and not b and not c and not d
     or     a and not c and not d and     e
     or     a and not c and not d and     f
     or not a and     c and     d
     or not a and     c and     e
     or not a and     c and     f
     or not a and not b and not d and     e
     or not a and not b and not d and     f;

     D =     a and     b and     c and     e
     or     a and     b and     c and     f
     or     a and     c and     d
     or     a and not b and not c and not d
     or     a and not b and not d and     e and     f
     or     a and not b and not d and     e and     g
     or     a and not b and not d and     e and     h
     or     a and not c and not d and not e and not f
     or     b and     c and not d and not e and not f and     g
     or     b and     c and not d and not e and not f and     h
     or not a and     b and not c and     d and     e
     or not a and     b and not c and     d and     f
     or not a and     b and not c and     d and     g
     or not a and     b and not c and     d and     h
     or not a and     c and not d and not e and not f
     or not a and     d and     e and     f
     or not a and     d and     e and     g
     or not a and     d and     e and     h
     or not a and not b and     c and not e and not f and     g
     or not a and not b and     c and not e and not f and     h
     or not a and not b and not c and     e and     f
     or not b and     c and     d and     e
     or not b and     c and     d and     f
     or not b and not c and not d and not f and     g
     or not b and not c and not d and not f and     h;
Bitrex
fonte
1
Uau, que software faz isso? Funciona para dimensões arbitrariamente grandes? Como você derivaria o número mínimo de portas para realmente construí-lo a partir dessas formas de POP? Parece que, neste momento, um cpld ou melhor seria definitivamente a maneira mais prática de construí-lo.
Captncraig 06/04/12
@CMP Desculpe pelo atraso na minha resposta. Eu usei o programa disponível aqui: home.roadrunner.com/~ssolver, que pode aceitar tabelas verdadeiras - usei um script Python simples para gerar uma tabela verdade para cada um dos dígitos inteiros da raiz quadrada. Na verdade, os POPs acima estão em sua forma mínima, até os limites de capacidade dos algoritmos que o programa usa para minimizá-los.
Bitrex
1
@CMP Como você disse, seria uma loucura implementar a raiz quadrada inteira dessa maneira, pois é possível usar uma tabela de pesquisa ou codificar um dos algoritmos para a raiz quadrada inteira e permitir que a linguagem de sua escolha HDL a sintetize.
Bitrex