Magnitude compare module

Thread Starter

tquiva

Joined Oct 19, 2010
176
Hi could someone please help me with the following problem:

In class we have looked at the design of an equality compare module. For this problem you should design a magnitude compare module for 4 bit unsigned binary numbers. The module inputs are A[3..0] and B[3..0]. The two outputs are G and L, such that G is true iff A is greater than B; L is true iff A is less than B. (Thus if A == B, G and L are both false, and GL = 11 should never occur).
  1. Design and implement this compare module iteratively in space, by designing a cell with inputs Ai and Bi and gi and li, and outputs Gi and Li. How long will this comparison take?
  2. Design and implement the compare module using a hierarchical approach. How long will this comparison take?
  3. Using one instance of the cell from 1), design and implement the 4-bit compare module using an iteration in time technique. Show your complete design, including the data path and controller for this approach.
The equality compare module looks like this:

Where e means all stages to the right are equal, & E means this stage and all stages to the right are equal.



I figure the magnitude compare module must look similar with two compare blocks as above, but instead with four bit inputs.
My first block would have inputs A3, A2, A1, A0 and my second block would have inputs B3, B2, B1, B0.
The spec says there are two outputs G & L. So would each block contain both outputs or each block would contains one of each?
i.e. block one: G & L; block two: G & L
or block one: G; block two: L
???

I really am lost. I don't know exactly how a magnitude compare module differs from an equality compare module.
I first began this problem with a truth table.

After this, I got stuck and now I have no idea where to go from here.
Could someone please guide me with steps on what to do and how to implement this problem?

Any help will be greatly appreciated...
 
Last edited:

Georacer

Joined Nov 25, 2009
5,182
You could always use the schematic of a commercial magnitude comparator, such as the 7485: http://www.datasheetcatalog.org/datasheets2/15/159699_1.pdf
The datasheet has a schematic, some pages deep. Just use L,L,H for the >,<,= inputs for the desired results.

However, I don't think this is what your tutor wants. I don't understand what "iteration in space" and "iteration in time" mean, but it seems like a modular solution is desired.

Look at the four yellow blocks in your question. I guess this is what your tutor wants the solution to look like. Each block will have an E, G and L output.
Starting from the MSB:
In order to judge if the number A is G or L you first need to look at their MSB. If E3<>0 then you can have your answer right away, with one comparison. You must inhibit any other results of comparisons in less significant bits to appear.
If E3=0 then you must examine Bit2 with the same rules and still keep in mind to inhibit less significant bit comparison results.
The process keep going until Bit0.

In general we could say that our steps are:

  • Starting from the MSB,
  • We check Ei
  • IF Ei<>1 G and L are equal to Gi and Li
  • If Ei=1 we check the next significant bit
  • If E0=1 then E=1
I think this approach responds to question #2.

Please clarify questions #1 and #3.
 

Thread Starter

tquiva

Joined Oct 19, 2010
176
Thank you so much, I'll try that approach for #2. I think I know how to do #1 but am still unsure about it.
I redid my truth table, created K-Maps to obtain the equations for the outputs, and implemented these into logic circuits on logicworks.






With each compare box looking like this internally:


As you can see in my circuit, I am not getting any values (they are X's) in the outputs. Was my approach correct or wrong??
 

Georacer

Joined Nov 25, 2009
5,182
Your approach has many logic errors and is inefficient as a concept.

If I understand correctly, you start comparing from the Least Significant Bit. There is no reason you would want to do that. If the MSB's of two numbers differ, then the answer of which one is bigger is before your eyes. You don't need to compare the rest of the bits.
That also means that you will spread the g and l signals towards less significant bits and not vice versa.

You also have some errors in your current approach. For example, in the truth table, row #4 (input 0100) you are in the situation where two less signifiant bits are unequal and the current pair of bits is equal. In that case the two numbers are unequal and not equal (GL=00) as you have written on the right.
 

Thread Starter

tquiva

Joined Oct 19, 2010
176
Ok I think I see where you're coming. But how would you go about doing this?

Should I change the order of naming the inputs on the truth table?
Like instead of gi, li, Ai, Bi, I would instead put Ai, Bi, gi, li?
 

Georacer

Joined Nov 25, 2009
5,182
Order is not a problem. The contents of the table are. Keep in mind that if you follow my recomendation, li and gi are coming from the More significant level and Gi and Li are fed to the less significant level.
 

Thread Starter

tquiva

Joined Oct 19, 2010
176
I'm still a bit confused.
So if I am to start from the MSB, should I put

1000 instead of 0001 on the truth table?
Is this what you mean?
 

Georacer

Joined Nov 25, 2009
5,182
No. The truth table describes a single cell of your comparator and has the correct variables and data in the first 4 columns.

What I am say is that you must keep in mind that the first cell that is previous to the one examined is more significant and the one that G and L are given to is less significant.

You need to correct the last two columns of the truth table.

For example, when g and l are 0 and 1, that means that so far, by examining more significant bits, number A is lower than number B. No matter what the current and next, less significant bits are, number A will always be Lower than B. Therefore G=0 and L=1 regardless of Ai and Bi.

If gi=0 and li=0, we haven't been able to decide on the inequality, because the more significant bits have been the same so far. Thus, if Ai=1 and Bi=0 we want Gi=1 and Li=0. If Ai=1 and Bi=1 we still can't tell which number is greater and we output Gi=0 and Li=0.

Is that clear?
 

Thread Starter

tquiva

Joined Oct 19, 2010
176
I think I kind of get it. But still a bit confused:
So we have the the truth table:



You said that for g=0 & l=1, A < B no matter the next or current LSB (?)

This part I'm confused on.

Let's say you're referring to row #5 of 0100.
g = 0 & l=1. A=0 & B=0. How is A<B ?

I'm also kind of lost on what you meant the next or current LSB. Would that be the prior row to row #5?
 

Georacer

Joined Nov 25, 2009
5,182
This truth table refers to the comparison of only one pair of bits. Say we want to compare {A1A0, B1B0} = {01 and 00}.

First we will apply our truth table to the MSB which are {0,0}, with default input {g1,l1}={0,0}. We see that the bits are equal (A1=B1) and previously no bit was bigger than the other ({g1,l1}={0,0}). Therefore this module will output an "equality" output of {G1,L1}={0,0}.
Examining the less significant pair of bits, we see that {A0,B0}={1,0}, therefore A0>B0. Taking into account that previously no inequality was discovered, we will take this result into account: {G0,L0}={1,0}. This will be our final result: A<B

Another example: A=10 and B=01
g1=0, l1=0 (by default), and A1>B1. Therefore G1=1 and L1=0
g0=1, l0=0 (input from the previous step) and A0<B0. A0 might me smaller than B0 but a result from a previous step (g0,l0) has shown that a more significant bit of A was bigger than the corresponding bit of B. Therefore, despite of the fact that A0<B0, {G0,L0} will be {1,0}, and the final result will be A>B.

Your truth table should be like this:


Do you understand why?
 

Attachments

Thread Starter

tquiva

Joined Oct 19, 2010
176
thank you so much. It is much clearer now.
So now, do I just put these two functions (Gi & Li) into a K-Map and draw a logic diagram for it?
 

Thread Starter

tquiva

Joined Oct 19, 2010
176
Okay, here's what I've done:






(This is how the compare module looks internally below)




Did I do everything correctly?
 
Last edited:

Thread Starter

tquiva

Joined Oct 19, 2010
176
For #2 of the problem, it says to take a hierarchical approach.
Hierarchical partitioning means to break up an n-bit problem into two n/2 bit problems.

Since this problem is 4-bits, I need two problems of 2 bits.

I drew out the compare module of the first problem:

One box represents 4-bits, so now I want to put A & B on on one box and g & l on one box. However, I'm not sure what to output from each of these two boxes? I know that the final box would contain outputs G & L.

So maybe perhaps, it looks like this?


Is my idea correct? I didn't know what to label the question marks with.
I know you already helped me out a lot and I appreciate it, but could you please help me with this part also?
 

Georacer

Joined Nov 25, 2009
5,182
What I have in my mind looks like your first image. You got it right in the previous post, but did it wrong again here. It seems that you still don't understand that the LSB pair must be examined last.

For two 2-bit numbers A1A0 and B1B0 (notice the names of the MSBs) the schematic would look like this:


The output of the circuit is always on {G0,L0}.


As for your next problem, I guess you could do the same thing, but breaking your string of numbers in half. You examine the two first halves and the two second halves in the same time. In the end you give priority to the result of the first half. If this gives equality you output the result of the second half.

Can you fill in the blanks?
 

Attachments

Last edited:

Thread Starter

tquiva

Joined Oct 19, 2010
176
This truth table refers to the comparison of only one pair of bits. Say we want to compare {A1A0, B1B0} = {01 and 00}.

First we will apply our truth table to the MSB which are {0,0}, with default input {g1,l1}={0,0}. We see that the bits are equal (A1=B1) and previously no bit was bigger than the other ({g1,l1}={0,0}). Therefore this module will output an "equality" output of {G1,L1}={0,0}.
Examining the less significant pair of bits, we see that {A0,B0}={1,0}, therefore A0>B0. Taking into account that previously no inequality was discovered, we will take this result into account: {G0,L0}={1,0}. This will be our final result: A<B

Another example: A=10 and B=01
g1=0, l1=0 (by default), and A1>B1. Therefore G1=1 and L1=0
g0=1, l0=0 (input from the previous step) and A0<B0. A0 might me smaller than B0 but a result from a previous step (g0,l0) has shown that a more significant bit of A was bigger than the corresponding bit of B. Therefore, despite of the fact that A0<B0, {G0,L0} will be {1,0}, and the final result will be A>B.

Your truth table should be like this:


Do you understand why?
Honestly, I've become lost again so I'm trying to understand this and trace this comparison with the above truth table.

You said that {g1,l1}={0,0} is a default input. Why is that? Does this mean that for all comparisons these values will always be 0?
 

Georacer

Joined Nov 25, 2009
5,182
We use {gmax,lmax}={0,0} because there is no information in front of the MSB pair. However our module requires a {gi,li} data to operate. Doesn't it make sense to use {0,0} as input as if zeros preceded the significant figures of our numbers?
 

Thread Starter

tquiva

Joined Oct 19, 2010
176
What I have in my mind looks like your first image. You got it right in the previous post, but did it wrong again here. It seems that you still don't understand that the LSB pair must be examined last.

For two 2-bit numbers A1A0 and B1B0 (notice the names of the MSBs) the schematic would look like this:


The output of the circuit is always on {G0,L0}.


As for your next problem, I guess you could do the same thing, but breaking your string of numbers in half. You examine the two first halves and the two second halves in the same time. In the end you give priority to the result of the first half. If this gives equality you output the result of the second half.

Can you fill in the blanks?
I'm lost on the second part of the problem. How would I go about breaking my string of numbers in half? Do you mean the truth table? Was my picture correct?

 

Georacer

Joined Nov 25, 2009
5,182
Ok, let's recap.

First of all I would use the same building unit. The 1-bit comparator with A,B,g,l inputs and G,L outputs.

Compare {A1,B1} and {A0,B0} independently. Your results will be {G1,L1} and {G0,L0}. What you have to do next is to look at {G1,L1} and judge whether you must use this result or the {G0,L0} result. The logic is the same as previously. If {G1,L1} denotes a clear "victory" of one of the two numbers, we will use it as a result. If there is a "tie" we will use {G0,L0} to define the winner.

This can be done with two 2-to-1 MUXs. Keep in mind that the only combination of {G1,L1} we want to ignore is {0,0}. Therefore, the MUXs will have (G1 OR L1) as a select signal. The MUXs inputs will be G0 and G1 and L0 and L1.

Is that clear?
 

Thread Starter

tquiva

Joined Oct 19, 2010
176
Ok, let's recap.

First of all I would use the same building unit. The 1-bit comparator with A,B,g,l inputs and G,L outputs.

Compare {A1,B1} and {A0,B0} independently. Your results will be {G1,L1} and {G0,L0}. What you have to do next is to look at {G1,L1} and judge whether you must use this result or the {G0,L0} result. The logic is the same as previously. If {G1,L1} denotes a clear "victory" of one of the two numbers, we will use it as a result. If there is a "tie" we will use {G0,L0} to define the winner.

This can be done with two 2-to-1 MUXs. Keep in mind that the only combination of {G1,L1} we want to ignore is {0,0}. Therefore, the MUXs will have (G1 OR L1) as a select signal. The MUXs inputs will be G0 and G1 and L0 and L1.

Is that clear?
So I would still use this module?



Not sure what you mean by "use the same building unit" ?

Because this module contains 4 inputs and I need to have two modules with 2 inputs ?

For the MUXs, why are the desired outputs made as inputs (G0, G1, L0, L1) ?

I tried it, and is this what you mean? Not sure how the outputs would be though...
 
Last edited:
Top