I was implementing the ALU from the specs given in my The Elements of Computing systems book. I am stuck on only one problem. How do I find if a given number is zero or not. One thing I can do is or every bit in the bus, and then apply a not gate on that. But there has to be some other elegant solution.
\$\begingroup\$
\$\endgroup\$
3
-
8\$\begingroup\$ it doesn't sound like you're stuck really - more like you're unsatisfied :) \$\endgroup\$– vicatcuAug 30, 2010 at 16:25
-
7\$\begingroup\$ a X input NOR is the elegant solution. In order to determine if the register contains zero, every bit must be examined to see if it contains a logical 0. You specified that you need a single bit output. Therefore you need some function with X inputs, and one output, like a NOR. \$\endgroup\$– W5VOAug 30, 2010 at 20:20
-
\$\begingroup\$ If speed is of little concern you could use a shift register, an or gate and a flip-flop and use a serial operation. The same logic could be used to add etc. Some 8-bit processors actually did this. \$\endgroup\$– Spehro PefhanyJul 7, 2020 at 19:56
Add a comment
|
7 Answers
\$\begingroup\$
\$\endgroup\$
3
There's simply no way around ORing all the bits, as unsatisfying as that may seem. However, you are not restricted to two input gates in silicon either. You can build a 4-input NOR gate in CMOS logic by putting 4 series p-type transistors in the pullup network and 4 parallel n-type transistors in the pulldown network. That reduces the depth of your tree topology and therefore your propagation delay. You can only take that theory so far though before the cumulative voltage drop across the series transistors makes the pull-up not pull-up enough to be a "1"... four is a good rule of thumb if I remember correctly.
-
\$\begingroup\$ For a larger number of bits would using alternating NOR and NAND gates make sense? E.g., with fan-in of 4 gates, a 64-bit zero test could use 16 NOR gates feeding a result of 1 if the 4 bits are zero to 4 NAND gates which feed a result of 0 if all 4 bits are 1 (all 16 original bits were 0), these four results would then be sent to a final NOR gate. (I am not an EE, but that would seem to be better than using intermediate inverters—to get the all-zero result back to 0—and using only NOR gates.) \$\endgroup\$– user15426May 31, 2014 at 1:31
-
\$\begingroup\$ There might also be ways to partially fold the latency of zero detection into the addition latency. \$\endgroup\$– user15426May 31, 2014 at 1:37
-
\$\begingroup\$ What about using NMOS: One pull-up resistor and X transistors to bring the level down to 0 if any input is 1? \$\endgroup\$ Feb 17, 2017 at 22:07
\$\begingroup\$
\$\endgroup\$
The logic function is the NOR gate. That is the simplest logic function that exists.
\$\begingroup\$
\$\endgroup\$
4
The typical solution with 8 bit machines was that the ALU would produce a number of 'flag' bits that would represent the outcome of the most recent operation. While it would be possible to have any number of flag bits around (i.e., you could have a 'Z' flag for every register in your CPU), it's usually the thing you've just computed that you're most interesting in, so it makes a certain degree of sense to do it that way.
Some of those old CPUs would automatically set flag bits for almost every data move, while others would require you to stick a specific 'compare' instruction in your code if you just suddenly need to know if a certain register was zero. And whether you provide a zero check for every register or just for what's just been computed, there really is no simpler way to check for "is this word zero" than to just OR all the bits together.
-
1\$\begingroup\$ This is also typical of the 32-bit ARM chips, and may be typical of most architectures. For the ARM, the APSR (Application Program Status Register) holds N, Z, C, V and Q bits (Negative, Zero, Carry, oVerflow, saturateQ) bits to provide other functions in addition to the zero bit you're looking for. These may or may not be useful to your machine. \$\endgroup\$ Aug 29, 2010 at 1:46
-
\$\begingroup\$ I got the or solution alright, but it bugs me I have to use so much of logic to get just one bit. There has to be some elegant solution. \$\endgroup\$ Aug 29, 2010 at 6:37
-
\$\begingroup\$ @Rick_2047 - you didn't mention what you're implementing this with, but I'm guessing an FPGA? It would bug me too, to have to tie up whatever number of logic blocks just to do a high fan-in gate. That's a good reason to only put in only one of them. \$\endgroup\$– JustJeffAug 29, 2010 at 14:03
-
\$\begingroup\$ not exactly an FPGA but an HDL and hardware simulator. \$\endgroup\$ Aug 31, 2010 at 4:58
\$\begingroup\$
\$\endgroup\$
5
Some CPUs, MIPS for example, have a register that always contains zero, making testing another register for zero very fast.
answered Aug 28, 2010 at 19:12
-
\$\begingroup\$ How do I check the number if I have a register containing zero? Also I want to generate just one bit which is true or false depending upon if the bus of 16 bits is zero or not \$\endgroup\$ Aug 28, 2010 at 19:22
-
1\$\begingroup\$ a comparator... which degenerates to a glorified NOR gate... \$\endgroup\$– vicatcuAug 30, 2010 at 16:24
-
\$\begingroup\$ He might gain something this way if the registers are cheap (they are in an SRAM block in an FPGA) and he needs a register compare instruction for other reasons anyway. \$\endgroup\$– jpcAug 30, 2010 at 17:03
-
\$\begingroup\$ @vicatu - actually if you want to compare two N bit numbers, you'd need N 2-input XOR gates. The OR/NOR thing is only good for zero tests. \$\endgroup\$– JustJeffAug 30, 2010 at 22:20
-
\$\begingroup\$ but ultimately i would need to use as many gates as I have input bits or at least as many transistors. \$\endgroup\$ Aug 31, 2010 at 5:43
\$\begingroup\$
\$\endgroup\$
I am a big fan of or_reduce - most synthesis tools will optimize it to the best implementation since they know exactly what you are doing.
\$\begingroup\$
\$\endgroup\$
I found this post for the same reason as the OP - trying to implement zr for the ALU in The Elements of Computing course. zr is 1 if the ALU output is 0, 0 otherwise
The course provides a hardware simulator and a range of built-in predefined chips.
One of the built-in chips is an 8-way OR gate. An 8-way NOR gate is not provided. The ALU is 16-bit. I split the 16-bit signal into two 8-bit buses using a multiplexer. Each of these go to a separate 8-way Or gate. The outputs from each of the 8-way Or gates goes to a separate Not gate. The outputs from the two Not gates goes to an And gate. The output of the And gate is the function zr.
I tested this using the course Hardware Simulator v2.5.
\$\begingroup\$
\$\endgroup\$
4
We need to check if our output Array contains only 0 bits. If number that Array is representing is 0 then it's not Negative nor Positive in a math sense. So you can check last bit of output Array if it's equal to 0. Because in 2's compliment all negative numbers will have 1 as a last MSB if MSB==0 then it's not negative.
To check if it's not positive either we can NEGATE output Array and ADD it to itself that will get us array full of 1's. Now we will add output Array to this full of 1's array. If output Array did contain any 1 bit it will generate carry that eventually will cause overflow and set MSB of the result to 0. If output Array did contain only 0's result will remain array full of 1's. And MSB will remain 1 too.
So now we
AND (NOT(output Array[MSB]), ADD[MSB](output Array, ADD(output Array,NEGATE(output Array)))
Do that to check if number represented by output Array is nor positive nor negative. Mb tho to use multiway OR for all 16 bits is easier and better.
-
\$\begingroup\$ What is the sign of a two's-complement zero if "it's not Negative nor Positive"? What does "Mb tho to or all" mean? \$\endgroup\$ Jun 11, 2022 at 10:33
-
\$\begingroup\$ @ElliotAlderson I thought that 0 is unsigned, because positive and negative numbers are defined in relation to 0. To OR all - I mean to apply multiway OR gate to whole output Array so it will return 1 if at least one bit in the array is 1 - that would mean that it is not zero. As the marked as right answer suggests. It may be less costly because all this adding and negation that I did propose is not free after all. I'm going trough the same course as OP -The Elements of Computing systems book. That was my solution. It works but I don't know what is the most efficient yet. \$\endgroup\$ Jun 11, 2022 at 23:59
-
\$\begingroup\$ Numbers are defined to be unsigned or signed regardless of their value. If you use a typical processor then the conditional branching operations will consider zero to be positive. In 2's-complement arithmetic, "positive" means greater than or equal to zero. On the other hand, floating-point numbers and sign-magnitude representations have both positive zero and negative zero. \$\endgroup\$ Jun 12, 2022 at 0:35
-
\$\begingroup\$ @ElliotAlderson Thank you for explanation! I've edited my answer hope it looks better now. \$\endgroup\$ Jun 12, 2022 at 1:13