Electrical Engineering Stack Exchange is a question and answer site for electronics and electrical engineering professionals, students, and enthusiasts. It only takes a minute to sign up.
Sign up to join this community
I was looking for a way to calculate the square root of a given 8-bit number using only digital combination or sequential logic. Is this possible?
One way may be to just use a look-up table since I'm not considering fractional parts at all (so \$ \sqrt{10} \simeq 3\$), but there has to be a better way than this.
Can someone point me to that?
Lookup tables have been mentioned in comments. There are two approaches.
Fast
Create a 256 bytes long table, with every next value the square root of the corresponding index. This is fast since you use the argument as index to access the right value directly. Drawback is that it needs a long table, with lots of duplicate values.
Compact
As said, an 8-bit integer can only have values 0 through 255, and the corresponding square roots are 0 through 16 (rounded). Construct a 16 entry table (zero-based) with the n-th entry the maximum value for the argument for which the square root is n. Table would look like this:
0
2
6
12
20
etc.
You walk through the table and stop when you encounter a value greater than or equal to your argument. Example: square root of 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
While the fast lookup table has a fixed execution time (just one lookup), here the execution time is longer for higher value arguments.
For both methods goes that, by choosing different values for the table, you can select between a rounded or a truncated value for the square root.
Working in 8 bits, you're basically constrained to integer solutions. If you need the square root of X, the closest you can get is the largest integer whose square is less than or equal to X. For example, for sqrt(50) you'd get 7, since 8*8 would be more than 50.
So here's a trick for doing that: count how many odd numbers, starting with 1, you can subtract from X. You could do it with logic like so: an 8-bit register R1 holds the working value, a 7-bit counter R2 holds (most of) the odd number, and a 4-bit counter R3 holds the result. At reset, R1 is loaded with the value of X, R2 is cleared to zero, and R3 is cleared to zero. An 8-bit subtractor circuit is fed R1 for the 'A' input, and the value of R2 combined with an LSB fixed at '1' (via pull-up) for the 'B' input. The subtractor outputs an 8-bit difference A-B and a borrow bit. At each clock, if the borrow bit is clear, R1 is loaded with the subtractor output, R2 is incremented, and R3 is incremented. If the borrow bit is set, R1 is not loaded and R2, R3 are not incremented, b/c the result is now ready in R3.
ALTERNATIVELY
There are only 16 possible output values, so the answer is a four bit number. Essentially, you have four single-bit functions of the 8 input bits. Now, I can't draw an 8-dimensional Karnaugh map, but in principle you could just come up with a combinatorial circuit for each bit of the answer. Take the outputs of those four combinatorial circuits together and interpret them as the four bit answer. Voila. No clocks, no registers, just a bunch of NAND and NOR would suffice.
case statement and let the synthesis tool do all the work. On the one hand it's kind of like doing a big look-up table in distributed RAM (used as ROM); on the other hand the tool should find optimizations like you mention in your comment.
\$\endgroup\$
Apr 5, 2012 at 15:40
I don't know if this is any help, but there's an ingeniously simple way to calculate a square root:
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;
}
I don't know much about what can and can't be done in sequential logic, but since this algorithm finishes in just 4 loops, you might be able to implement it in 4 stages.
I ran the truth tables for the integer square root from 0-255 through a Quine-McCluskey logic minimizer. The integer square root can be done with just combinatorial logic, but even for such a relatively small input size of \$2^8\$ possible values, the answer isn't for the faint of heart. The following is ordered from MSB A to LSB D of the output, in terms of abcdefgh as inputs, MSB to LSB:
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;
