I'm kind of going down a rabbit hole here. It started off with a simple enough question: "What is the simplest way to test for equality between two sets of bits?" The single-bit truth table of course looks like this:

= 0 1
0 1 0
1 0 1

Which is obviously just the inverse of the XOR gate (ie. the XNOR gate). Chaining them together sequentially turned out to be a bit of a mess, so instead I decided on a much more sane approach: construct larger circuits from 4-bit sub-circuits:



Then I can just connect them together using a single AND gate for each stage. Like this:



Looks pretty good to me. I can compare two N-bit numbers with just 2N logic gates. I wonder though, could it have been made with even less components?

My second question is a little more complicated. Can I use a similar approach to build less-than and less-than-or-equal circuits? Consider a single-bit less-than circuit:

< 0 1
0 0 1
1 0 0

So basically AND the right-hand-side bit with the inverse (NOT) of the left-hand-bit. But when I tried chaining those together in a bunch of different ways I kept getting stuck. The two-bit version is almost the OR of two one-bit circuits, except for one particular case. Unfortunately, "fixing" that made things so convoluted that the idea of adding more of these together to make, say, 16-bit less-than circuits seemed completely ridiculous. Can anyone point me in the right direction?

 

Which way is "simple" depends on the constraints.

The approach you have is purely combinational and is able to check all of the bits all at once. But, as you can see, it takes a lot of gates.

If you have the option of feeding the two sets of bits into the circuit sequentially, then the circuit can be much smaller, but needs a clock and has the associated delays.

For your two-bit subcircuit, keep the first layer at XNOR gates (which can be the same speed and size as XOR gates) and then use NAND gates for the second and third layers. This will reduce the transistor count a bit and improve the speed by about one gate delay.

For the inequality gate, you really only need a less-than (or a greater-than) circuit, since you already have an equal-to circuit. The output of those two can be trivially combined to generate the six possible relational outcomes.

Here's a hint on how to tackle the generalized magnitude comparison (the assumption is that both sets of bits represent an unsigned weighted binary number -- if the values are signed, then some modification is needed, but it's actually pretty tame.

Let's say that I have two N-bit numbers, X and Y, that I want to compare them to answer the question X<Y. I can partition them into sub-numbers as follows:

X = AB
Y = CD

B and D are the least-significant bits (B is the same width as D) and A and B are the most-significant bits (which will then also be the same width, which may or may not be the same width as B and D).

To determine the relationship between X and Y, I first look at A and C. If A is less than C, I 'm done and the result is T, while if A is greater than C, I'm also done and the result if F. But, if they are equal, then I must turn my attention to B and D and the same thing applies.

Approach it just like a ripple-carry adder, except instead of information flowing from lsb to msb, it flows from msb to lsb. You even have the same notion of a "half-comparator" and a "full-comparator". You'll see that the logic is quite tame.

 

I'm kind of going down a rabbit hole here. It started off with a simple enough question: "What is the simplest way to test for equality between two sets of bits?" The single-bit truth table of course looks like this:

= 0 1
0 1 0
1 0 1

Which is obviously just the inverse of the XOR gate (ie. the XNOR gate). Chaining them together sequentially turned out to be a bit of a mess, so instead I decided on a much more sane approach: construct larger circuits from 4-bit sub-circuits:

View attachment 357320

Then I can just connect them together using a single AND gate for each stage. Like this:

View attachment 357321

Looks pretty good to me. I can compare two N-bit numbers with just 2N logic gates. I wonder though, could it have been made with even less components?

My second question is a little more complicated. Can I use a similar approach to build less-than and less-than-or-equal circuits? Consider a single-bit less-than circuit:

< 0 1
0 0 1
1 0 0

So basically AND the right-hand-side bit with the inverse (NOT) of the left-hand-bit. But when I tried chaining those together in a bunch of different ways I kept getting stuck. The two-bit version is almost the OR of two one-bit circuits, except for one particular case. Unfortunately, "fixing" that made things so convoluted that the idea of adding more of these together to make, say, 16-bit less-than circuits seemed completely ridiculous. Can anyone point me in the right direction?

Hi,

It seems like this would take a LOT of discrete logic to get the functions you need. You also have to consider the propagation delays and the unwanted glitches they can produce. For a 16 bit unit that does all three functions I an guessing you'll need to use a whole PCB just for that, combined with connector(s). That's pre-1980's technology.

Now enter the TTL 7485 (or LS version or other version). That does less than, greater than, and equals, all in one chip, and has methods for expansion to more than 4 bits. I think you can do 16 bits with just 4 chips. You still have to consider gate delays though that's still very important.
I've included a functional diagram in the attachment. It's from an old data sheet they probably have other TTL and CMOS versions now.
I think the 74885 is an 8 bit version but check that out.

Way back when I used XNOR or XOR gates for getting the equals function for a home made video game. If I had to do the same thing today and still use TTL (or CMOS) logic, I'd use the 7485 or a derivative, or another comparator chip if there are any (I haven't checked for this in a very long time now).

 

Agree with Al. There are fully-integrated, 4-bit and 8-bit magnitude comparators in several logic families. These have three control lines so they can be strung together to any word width without a bunch of external gating.

ak

 

I have used them and I think that they are still available, four bit magnitude comparator ICs. Three outputs: Less than, equal to, greater than. They were used for command decoding and counter sensing. Quite a bit of logic inside the IC, but a rapid four bit comparison,

 

I could be wrong, but the impression that I had was that @xox was focused on learning about the magic under the hood and not thinking about actually implementing this unless it was for the purpose of a demonstration (to himself or others).

 

I looked at post #1 again and as I see it, the example makes no sense at all. myself and others have presented known solutions. The answer has been delivered. DONE!!!!

 

I could be wrong, but the impression that I had was that @xox was focused on learning about the magic under the hood and not thinking about actually implementing this unless it was for the purpose of a demonstration (to himself or others).

Hi,

That could be the case. I went back and read the first post too and I see that there were actually two different questions. One was about the simplest way to do this, and the other was about digging deeper into the implementation I think.

I guess we'll have to wait for another reply from the member 'xox' to be sure. I guess it could also be the search for both types of solutions.

 

Well after dozens of failed design attempts I finally figured it out. But first I had to learn how Karnaugh maps work! I mapped out all of the possible input/output values for each stage and then simplified the expression (thanks to @WBahn for the insight about breaking the bits into groups). It turned out that it actually made more sense to produce two outputs because each internal stage needed them anyway in order to ripple the results forward. What I ended up with was a generic two-bit comparator.



So you just choose which output you want basically. As a bonus, with the simple addition of one or two external logic gates the comparator can provide EQU, GTE, LTE functions. Pretty neat, eh?

To test things out I put three of them together to make 4-bit comparators.



That way I could reuse the form-factor expected by the simulation I already had in place. (Of course I had to link them together with a few extra 2-bit comparators.)



Overall I'm pretty happy with the result. Granted, there are probably too many logic gates in the design (I'm open to any suggestions).

So yes, this was just an exercise. I do understand that there are pre-existing solutions which would be a much better choice for real-world projects. It's just something I had never tried before and felt like it would be an interesting challenge. (And to be honest, I had no idea it was going to be as hard as it turned out to be.)

Thanks to everyone for all of the recommendations and advice. Cheers!

 

if it is for academic exercise or grade, student may be expected to come up with the glue logic using just gates rather than more complex ICs like comparators. one option is to replace pair of NOR and one AND with a single 4-input NOR (SN7423, 7425...CD4002...).

 

if it is for academic exercise or grade, student may be expected to come up with the glue logic using just gates rather than more complex ICs like comparators. one option is to replace pair of NOR and one AND with a single 4-input NOR (SN7423, 7425...CD4002...).

I'm a little confused. Right now I'm only using AND, OR, and NOT gates. I get that an AND gate with inverted inputs would make a NOR gate, but I don't see where any such substitutions could be made in the current design. Could you please clarify?

And just for the record, no, I'm not in school. Just learning new things in my spare time.

Another question I had was the matter of timing (as pointed out by @MrAl). Out of curiosity I put together a 32-bit comparator.



Originally I wanted to try a 128-bit module, but after wiring up the 32-bit version I decided against it.



For one thing it was extremely tedious running all of those wires! But more importantly the simulation was just too sluggish, so I ruled the idea out.

Now it does seem to run correctly in the simulator. I have the timestep set to microsecond increments. But is that really good enough? How do the pros handle timing issues under real-world conditions? Presumably it would depend on what particular parts were being used and hence just a matter of looking at the datasheets (or maybe even sending test signals through each component).

 

I'm a little confused. Right now I'm only using AND, OR, and NOT gates. I get that an AND gate with inverted inputs would make a NOR gate, but I don't see where any such substitutions could be made in the current design. Could you please clarify?

have you thought of this... one IC could be the 4 XOR gates. and 1/2 of another IC could be the NOR gate.
if any pair of bits is not matched, that XOR gate will have 1 for output. in that case (regardless what other bits look like) NOR will invert the state to 0 (no match). the only time you get the match is when all XOR gates have outputs FALSE.

De Morgan's laws explains equivalency or transforms when doing substitutions.

one of the drawbacks of cascading gates is that propagation times add up which is something one must consider (in most cases). for simple lighting of LED indicator or segment display, this is not an issue, eye will be too slow to catch the glitches. but circuits can...
so clocked logic is invented to allow signal changes in a lockstep.

 

have you thought of this... one IC could be the 4 XOR gates. and 1/2 of another IC could be the NOR gate.
if any pair of bits is not matched, that XOR gate will have 1 for output. in that case (regardless what other bits look like) NOR will invert the state to 0 (no match). the only time you get the match is when all XOR gates have outputs FALSE.

De Morgan's laws explains equivalency or transforms when doing substitutions.

one of the drawbacks of cascading gates is that propagation times add up which is something one must consider (in most cases). for simple lighting of LED indicator or segment display, this is not an issue, eye will be too slow to catch the glitches. but circuits can...
so clocked logic is invented to allow signal changes in a lockstep.

View attachment 357453

Sorry, I thought you were talking about the second circuit! Yeah that would definitely be more efficient. I didn't see the multi-input gate option in my simulator (I'm using Falstad). Correlary question: is it possible to just tie together the output wires and then invert for a sort of "homemade NOR gate", or is there some rule that logic gate outputs can't be connected directly?

 

it depends on IC...
you do not want to do that on CMOS since outputs are complementary. so if one is high and other is low, you have a short circuit.
on TTL this is ok when outputs are open collector, otherwise internal pull up resistors are paralleled (low resistance/high load) and that may be too much for single output to handle. normally one sees that in older logic (obsolete)

 

I'm a little confused. Right now I'm only using AND, OR, and NOT gates. I get that an AND gate with inverted inputs would make a NOR gate, but I don't see where any such substitutions could be made in the current design. Could you please clarify?

The propagation delay, especially if implementing the logic in an IC design (using standard SSI chips is different because delays tend to be dominated by the I/O buffering circuits and not the gates themselves), should be considered. Transistor-based circuits tend to be inherently inverting, so the fastest gates are the NOT, NAND, and NOR. In fact, in CMOS, an AND gate is physically implemented as a NAND gate following by a NOT gate, so AND and OR gates take up more die area than NAND and NOR gates. NANDs are faster than NORs in minimum-geometry gates because NFETs are faster/stronger than the same geometry PFET (because the electron mobility is about twice that of the hole mobility). In a NAND gate, the PFETs are in parallel while the NFETs are in series, which tends to cancel out this effect pretty well when using minimum-geometry transistors. In a NOR gate, the opposite is true, which tends to amplify the difference.

So, where possible, You want to get rid of AND and OR gates and replace them with NAND and NOR gates by moving inversions around and applying DeMorgan's theorems ruthlessly.

Another useful point that can be exploited is that XOR and XNOR, as commonly implemented, have the same propagation delay and transistor count, Inverting any one pin on either gate turns it into the other. Do if you have, say, and AND gate feeding one input of an XOR gate (and the output of the AND gate isn't being used elsewhere), you can replace the AND with a NAND and replace the XOR with an XNOR, thereby removing two transistors (CMOS) and one gate delay along that path.

 

Sorry, I thought you were talking about the second circuit! Yeah that would definitely be more efficient. I didn't see the multi-input gate option in my simulator (I'm using Falstad). Correlary question: is it possible to just tie together the output wires and then invert for a sort of "homemade NOR gate", or is there some rule that logic gate outputs can't be connected directly?

Not unless the output you are using three-state outputs or open-drain outputs. Otherwise, you can (almost certainly will) have gate contention which not only creates undefined logic levels at the output, but can result in enough shoot-through current to physically destroy the gate (ask me how I know).

One of the nice things about CMOS is that you can go to pretty large input widths, such as eight-input gates, pretty easily and even wider with some care and if you can tolerate the speed penalty that can result.

 

I'm kind of going down a rabbit hole here. It started off with a simple enough question: "What is the simplest way to test for equality between two sets of bits?" The single-bit truth table of course looks like this:

= 0 1
0 1 0
1 0 1

Which is obviously just the inverse of the XOR gate (ie. the XNOR gate). Chaining them together sequentially turned out to be a bit of a mess, so instead I decided on a much more sane approach: construct larger circuits from 4-bit sub-circuits:

View attachment 357320

Then I can just connect them together using a single AND gate for each stage. Like this:

View attachment 357321

Looks pretty good to me. I can compare two N-bit numbers with just 2N logic gates. I wonder though, could it have been made with even less components?

My second question is a little more complicated. Can I use a similar approach to build less-than and less-than-or-equal circuits? Consider a single-bit less-than circuit:

< 0 1
0 0 1
1 0 0

So basically AND the right-hand-side bit with the inverse (NOT) of the left-hand-bit. But when I tried chaining those together in a bunch of different ways I kept getting stuck. The two-bit version is almost the OR of two one-bit circuits, except for one particular case. Unfortunately, "fixing" that made things so convoluted that the idea of adding more of these together to make, say, 16-bit less-than circuits seemed completely ridiculous. Can anyone point me in the right direction?

They're called identity comparators.

https://www.ti.com/lit/ds/symlink/sn74als688.pdf?ts=1761138816880&ref_url=https%3A%2F%2Fwww.google.com%2F

Alternatively one could use 2 D/A converters and an op amp analog comparator...

 

I'm a little confused. Right now I'm only using AND, OR, and NOT gates. I get that an AND gate with inverted inputs would make a NOR gate, but I don't see where any such substitutions could be made in the current design. Could you please clarify?

And just for the record, no, I'm not in school. Just learning new things in my spare time.

Another question I had was the matter of timing (as pointed out by @MrAl). Out of curiosity I put together a 32-bit comparator.

View attachment 357451

Originally I wanted to try a 128-bit module, but after wiring up the 32-bit version I decided against it.

View attachment 357452

For one thing it was extremely tedious running all of those wires! But more importantly the simulation was just too sluggish, so I ruled the idea out.

Now it does seem to run correctly in the simulator. I have the timestep set to microsecond increments. But is that really good enough? How do the pros handle timing issues under real-world conditions? Presumably it would depend on what particular parts were being used and hence just a matter of looking at the datasheets (or maybe even sending test signals through each component).

Hi,

For the logic delays you consider each input and output, and add up the delays for both L to H and for H to L transitions.

As to the simplification, you could use any method you prefer, but if you write the Boolean expressions for the final outputs, you can then go on to simplify those expressions, then choose the gates that those expressions suggest.

If you do simplify, I think you can reduce to just two gates for any one path. That means that there could be a reduction to just two or three gate delays. This assumes that you can get gates with multiple inputs though, so it may still not be possible although it is still interesting to think about.

The other solution is after reductions you can implement a lot of logic in the form of a ROM memory. The inputs are the address lines. I can imagine that any four-bit function can be reduced to just one 4-bit ROM with 4 address lines. That means less chips per PCB but you still have to figure out the needed expressions which is still an exercise. The programming comes from the Boolean expressions you obtain from the design that you've already figured out.
If you have two inputs both 4 bits, then a ROM with 8 address lines would be required. With 4-bit data you could have GT, LT, and EQ with little effort, and still have one output left for something else. With 8-bit data you could have all sorts of output functions: addition, subtraction, multiplication, etc. You'd need 12 bits to do that and also the comparison functions.
I am not sure how big they make ROM's these days. For example, if you can get one with 16 address lines you could do any operations you like on two 8 bit numbers. GT, LT, and EQ would be cake

Keep in mind though you still have to work out the logic so you can reduce it, so it's still interesting in that way.

 

As to the simplification, you could use any method you prefer, but if you write the Boolean expressions for the final outputs, you can then go on to simplify those expressions, then choose the gates that those expressions suggest.

This is far easier said than done in practice.

For instance, consider the following expression:

\(
Y = \overline{ \left( \overline{ \left( A \cdot \overline{ \left( A \cdot B \right) } \right) } \cdot \overline{ \left( \overline{ \left( A \cdot B \right) } \cdot B \right) } \right) }
\)

What would the simplified expression be and what gates does that simplified expression suggest for the smallest and fastest CMOS circuit?

 

(A*B)' comes out to A'+B'
Combined with the other A we get:
A*(A' or B') => A*B'
(A*B')' => A' or B
(A' or B)' => A*B'
That's the first AAB expression. Took less than 5 minutes.
To get the hole thing, replace the first A in the first step with B and repeat.
If we did that for the ABB expression we'd get a simillar result:
(A*B)'*B => A'*B
(A'*B)' => A or B'
(A or B')' => A'*B

now together:
(A*B'*A'*B)' => A'or B or A or B'

A'or B or A or B' => true

So the logic circuit could be just a wire connected to +Vcc, or the fastest CMOS would be an inverter with the input tied to ground (only a pdelay at power on).

The whole thing took about 10 minutes but I haven't done this in a long time.
These days I would use software though to help avoid mistakes, and also check it before programming a ROM.

I actually had to do this in one project I had done for a company. We were developing a static switch and there were a lot of measurements to check before switching from one input to another. I did it all by hand with pen and paper (yikes) but that was many years ago. Now we have software.
I did use a program to generate the ROM programming though and we sent it to a service that programs the ROM's.

Since this resulted in a static output there would be nothing to program. If it resulted in say just A*B' we would have run through all the combinations with a program (Basic, C, etc.) and the output would be programmed into the associated address location.