Take the 2-minute tour ×
Electrical Engineering Stack Exchange is a question and answer site for electronics and electrical engineering professionals, students, and enthusiasts. It's 100% free, no registration required.

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.

share|improve this question
4  
it doesn't sound like you're stuck really - more like you're unsatisfied :) –  vicatcu Aug 30 '10 at 16:25
5  
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. –  W5VO Aug 30 '10 at 20:20

5 Answers 5

up vote 9 down vote accepted

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.

share|improve this answer
    
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.) –  Paul A. Clayton May 31 at 1:31
    
There might also be ways to partially fold the latency of zero detection into the addition latency. –  Paul A. Clayton May 31 at 1:37

The logic function is the NOR gate. That is the simplest logic function that exists.

share|improve this answer

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.

share|improve this answer
1  
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. –  Kevin Vermeer Aug 29 '10 at 1:46
    
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. –  Rick_2047 Aug 29 '10 at 6:37
    
@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. –  JustJeff Aug 29 '10 at 14:03
    
not exactly an FPGA but an HDL and hardware simulator. –  Rick_2047 Aug 31 '10 at 4:58

Some CPUs, MIPS for example, have a register that always contains zero, making testing another register for zero very fast.

share|improve this answer
    
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 –  Rick_2047 Aug 28 '10 at 19:22
1  
a comparator... which degenerates to a glorified NOR gate... –  vicatcu Aug 30 '10 at 16:24
    
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. –  jpc Aug 30 '10 at 17:03
    
@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. –  JustJeff Aug 30 '10 at 22:20
    
but ultimately i would need to use as many gates as I have input bits or at least as many transistors. –  Rick_2047 Aug 31 '10 at 5:43

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.