2-bit Magnitude Comparator
23rd December 2024
Some time ago I designed Logic Lab, a circuit that provides 12 logic gates that you can interconnect with patch cables to experiment with a variety of different logic circuits:
Logic Lab allows you to experiment with logic gates by interconnecting them with patch cables.
In fact I've designed two versions: the original one, Logic Lab, used a single AVR128DA48 microcontroller to emulate the logic gates, and the second one, Logic Lab 1G, used discrete logic gate ICs.
To accompany the articles I presented a series of logic problems that you could solve with Logic Lab. One of the ideas I had for a problem was a 2-bit magnitude comparator, without knowing whether it would actually be possible within the limitations of Logic Lab.
This article describes my struggle to implement the 2-bit magnitude comparator, during which I often decided to give up and then resolved to have "just one more go".
Logic Lab facilities
Logic Lab has the following features:
- 12 logic gates: two 2-input AND, two 2-input NAND, two 2-input OR, two 2-input NOR, two 2-input XOR, and two NOT gates (inverters).
- Four switches, S1 to S4, with LEDs to show the status, that can provide logic inputs to the gates.
- Five coloured LEDs, L1 to L5, that can display the state of the output from a logic circuit. The top three are red, orange, and green, allowing simulation of traffic lights. The other two are blue and yellow.
2-bit magnitude comparator
The challenge was to build a 2-bit magnitude comparator with this selection of gates.
This would compare two 2-bit binary numbers: A on S1 and S2, and B on S3 and S4. If the number A is greater than B the red LED L1 should light up; if A is equal to B the orange LED L2 should light up; and if A is less than B the green LED L3 should light up.
Approaching the problem
Published solutions
My first step was to search for "2-bit magnitude comparator" on the web, thinking that I might find a ready-made solution. I found several versions of this circuit:
A widely published solution to the 2-bit magnitude comparator uses too many gates for Logic Lab.
It's pretty much a direct implementation of the truth table. This was a bit discouraging, because it requires:
- Four inverters; Logic Lab only has two.
- Three 2-input AND gates; Logic Lab only has two.
- Four 3-input AND gates. Not available at all.
- Two 3-input OR gates. Logic Lab's are only 2-input.
- Two 2-input XNOR gates; we only have XOR gates.
So I changed my challenge to see what I could achieve out of what I had. I would settle for a partial solution; for example, only providing lights for A>B and A=B.
2-bit comparator
My starting point was the 2-bit equality comparator. This compares two 2-bit binary numbers on S1, S2 and S3, S4. If the two numbers are equal the green LED L3 should light up.
This uses XOR gates to compare each pair of digits. If they are equal the output of each XOR gate is a '0', and we check that they are both '0' with a NOR gate:
This is clearly easily achievable on Logic Lab.
A first attempt
My first attempt was as follows:
A partial solution to the 2-bit magnitude comparator only provides outputs for A>B and A<B.
It provides the outputs for A>B on L1 and A<B on L3. If neither L1 nor L3 is lit then the comparison is A=B.
If only I'd had one more NOR gate I could have connected the L1 and L3 signals to it and used it to create the L2 signal for A=B. However, the circuit has already used all 12 gates available in Logic Lab.
Note that the XOR gate at bottom left is being used as a NOT gate, as I didn't have any other gates available.
A second attempt
I then tried a different approach, starting from the 2-bit comparator circuit to get A=B on L2:
Another partial solution to the 2-bit magnitude comparator only provides outputs for A>B and A=B.
The result we want is represented by the following table, where the colours of the cells correspond to the LEDs we want to light:
The test for A = B gives the orange cells in the above table, and uses the two XOR gates and a NOR gate, connected as for the 2-bit comparator.
To test for A > B, the red cells in the above table, we combine a test for the four magenta cells in the following table with tests for the cyan and yellow cells, using the top OR gate:
Partial solution to 2-bit magnitude comparator.
The four magenta cells correspond to A1 = '1' and B1 = '0'. This is tested by the top AND gate; to save using a NOT gate we test A1 = '1' and B1 ≠ A1, which is equivalent.
To include the cyan cell we add B0 = '0', B1 = '0', and A0 = '1'. Likewise, to include the yellow cell we add A0 = '1', A1 = '1', and B0 = '0'. This is achieved by the bottom row of two NAND gates, two inverters, and the AND gate.
So I had signals for A>B and A=B, but no signal for A<B, so I seemed to be no better off than in my first attempt.
The final solution
However, I realised that in my last attempt I had only used 10 of Logic Lab's 12 gates, and there's a spare NOR gate available.
The final solution could be achieved by using this NOR gate to produce the signal for A<B on L3:
The final solution to the 2-bit magnitude comparator, implemented using the gates in Logic Lab.
So I had finally cracked the problem using just 11 of Logic Lab's 12 gates, with one gate left over.
Further challenges
Prime detector
If you'd like to have a go at solving a logic problem like this, here's another one. This should be possible on Logic Lab although I haven't actually tried it yet:
Treat the number on the four switches as a four-bit binary number, representing the numbers 0 to 15. Light the Green light L3 if the number is prime, and the Red light if it isn't. The prime numbers from 0 to 15 are: 2, 3, 5, 7, 11, and 13.
Logic solver
Another challenge is to write a program that solves a logic problem like this, such as finding a configuration for the 2-bit magnitude comparator subject to the constraints imposed by Logic Lab, using the smallest number of gates. I plan to attempt this when I get some ideas about how to approach it.
blog comments powered by Disqus