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...

I've gone back to the problem and reread it entirely.
I noticed that it says "The module inputs are A[3..0] and B[3..0]."

We've only been implementing A1A0 and BlB0.
If I were to add two more modules to the left of the two that I've already created, would I have to make any changed to the logic or anything else?

(Two more boxes to the left/right of these for A2A3 and B2B3 ?)

 

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?

Also one more, thing. I'm sorry. I'm still trying to figure out how to use the truth table. You said that the table refers to the comparison of one pair of bits. And you gave me the example of {A1A0, B1B0} = {01 and 00}.

How exactly do we apply the truth table to this pair?
Do we use the inputs gi, li, Ai, Bi to represent A1, A0, B1, B0 ??

 

It is important to understand that with the first solution method, we don't need to worry about the length (in bits) of our compared numbers. Our circuit is broken down to smaller modules or "blocks" that solve a part of the problem at a time. The outputs of these blocks goes through another block and so on. We can expand this "chain" of blocks infinitely. The only tradeoff we will pay is that we have to wait for longer to get a valid result at the final/"output" block.

Consequently, the above truth table describes a single block. It would be unreasonable to try to implement another bit comparison in the same block. If you want to compare more bits, just prolong the chain by adding blocks at the end of the existing chain (at the g1,l1 side).


Now, about the second implementation. This solution is valid for 2 bit numbers. However it is important to understand it before we move on the 4 bits. Please read more carefully:

Therefore, the MUXs will have (G1 OR L1) as a select signal. The MUXs inputs will be G0 and G1 and L0 and L1.

OR is the logic function of +.

The reason we OR the G and L signals is to translate the expression "if one number is clearly bigger or smaller from the MSB, then use their result. If not, use the LSB result"

Try to draw the whole circuit withn 2 bits in its hierarchical approach.

 

Alright, I drew a module for a hierarchical approach.
I redid the truth table based on these inequalities:
G=1 if A>B
L=1 if A<B
G=L=0 if A=B
G=L=1 NEVER








Is my approach correct?

 

actually I just reanalyzed what I've done, and it seems wrong.
Did I have to redo the truth original table from the first problem? Or is my hierarchical approach module incorrect?
I think I can possibly do the hierarchical approach without the lowercase g's and l's, with only inputs A0B0A1B1 and Outputs G & L. Can I do this or is g & l necessary through all the variations of the entire problem?

I'm thinking something more along the lines like this, with each cell containing the same logic:

I tried the logic diagram with different cases of bit comparisons, and it actually works. However, this may be inefficient or incorrect labeling...
How would you implement this problem?

 

I think post #24 is very misleading and I will completely disregard it.

The spine of this problem, as I see it, is first to come up with a circuit that will serve as a 1-bit comparator. This is the box we built in post #13. It has Ai,Bi,gi,li as inputs and Gi,Li as outputs. I will call that box Module A from now on. This is your basic building block. Remember: It compares only one pair of bits.

The essense of the 3 questions is to use this block in different ways to solve the same problem with different implementations.

In the first question we connected all the Modules A serially and took the result from the last Module A of the queue.

In the second question, your job is to compare all the bit pairs at the same time. if your numbers have 4 bits, you will use 4 Modules A, but this time all the {gi,li} inputs will be {0,0} because you compare the pairs independently from each other. What you must do in this exercise is to find a way to manipulate all those 4 results you have to get the final one.

Let's think about what we should do if we had only 2 results (from 2-bit numbers) and then we 'll scale up.
We have the comparison results {G1,L1} from the MSB pair, and the result {G0,L0} from the LSB pair.
What do we want our result to be? If {G1,L1} is {1,0} or {0,1} then use {G1,L1} as the result of the comparison, by definition. Otherwise, use {G0,L0}. Think about this a while. Do you understand why is that?

Now, doesn't that expression ring any bells? Isn't that what the Module A does if we connect in the inputs {Ai,Bi,gi,li} the results {G0,L0,G1,L1} in the exact same order? Take some time to understand why this works.

Therefore, a complete 2-bit hierarchical comparator would look like that:

All the boxes above are duplicates of Module A.

Is that clear?

Can you expand the above to compare 4-bit numbers?
Hint: You will need twice the aboce circuit, plus another Module A.

 

So basically, I will be using the same truth table, same functions, and same logic diagram as I used in 1.1?

By convention on LogicWorks 5, I need to label all inputs and outputs to create a module. I know that the boxes are all duplicates of the module A as you said, but for this box circled in red, what would I label its inputs?

 

What does it matter? Does the name of a variable makes a difference?

 

Thank you very much. I am now near completing the entire problem.
Could you please help me with part 3?
This page shows an example of iteration in time.
http://www-ee.eng.hawaii.edu/~tep/EE260/Notes/Partition/comp_time0.html

So I know I will have to use Module A once again.
For iteration in time, I know that this is just a time multiplex of one cell over each of the bits. (i.e. the cell is used over and over again). Then I will need to use registers ("shift registers") that will take the least significant bit for each clock cycle from right to left.

I'm looking at the example in the above link, and I guess I will need a 74194 device and a DFF. The steps are:
- Implement module A
- Implement state register
- Implement counter
- Implement state registers

An example from the equality compare is:

I'm feeling lost. How would I go about creating a controller for this? And how would I connect everything?

 

for the propagation delay of this circuit:

I checked the datasheets:

For 7410: t_pLH = 22ns; t_pHL = 15ns
For 7404: t_pLH = 22ns; t_pHL = 15ns
For 7400: t_pLH = 22ns; t_pHL = 15ns

Do I simply just add up these times corresponding to each gate?
Such as:
7404: 4(15) = 60
7410: 2(15) = 30
7400: 2(22) + 2(15) = 74
Total: 60 + 30 + 74 = 164ns

I don't know. That number is big. Is it right?

 

In order to calculate a logic circuit's propagation delay, you count the longest possible single route from the input to the output. Parallel paths don't add to the total time. As a result the propagation time for Module A will be 22ns+22ns+22ns (NOT,NAND,NAND) (The last OR with inverted inputs is equivalent to a NAND).
The DFF datasheet says that its propagation delay is 35ns maximum.
In total in order to get a correct result at pins G,L, the route the signal must take is {G,L}->DFF->Module A->{G,L}. Do you understand why? Can you calculate the total propatation delay? Can you calculate the maximum clock frequency that this circuit allows?

Some notes: The shift registers are governed by a clok too. Read here http://www.allaboutcircuits.com/vol_4/chpt_12/1.html if you need a quick reminder on their operation.

Some tutorial questions:
Our Module A has 4 inputs and 2 outputs. Can you modify the schematic to accomodate the extra pins?
Can you describe how the shift register is operated? What signals do we need to feed it in order to accomplish the various tasks it does?
Can you describe with words, exactly what you want your circuit to do? Describe its operation from the input of the START signal until the output of the READY signal. You will see, as we will discuss about it, that you need little more than a ready-made counter.

 

Is this correct?

Some tutorial questions:
Our Module A has 4 inputs and 2 outputs. Can you modify the schematic to accomodate the extra pins?
- not really sure how to do this. Would I have to change the logic? Or output functions?
Can you describe how the shift register is operated? What signals do we need to feed it in order to accomplish the various tasks it does?
- The shift register has 7 inputs. I need to add three more inputs for CLK, Serial Left, and Serial Right.
Can you describe with words, exactly what you want your circuit to do?
- I would like my circuit to be implemented by an iteration in time approach which is the same idea as a ripple adder.
Describe its operation from the input of the START signal until the output of the READY signal. You will see, as we will discuss about it, that you need little more than a ready-made counter.

I'm still so lost and frustrated. I am hoping to get it done by tomorrow's due date. Could you please give me some hints to get me started?

 

Your schematic looks good. I wanted to show you exactly that you need antother D-FF.

I suggest you use the 74193 as counter and the 74166 as register. I hope you know how to find and read a datasheet.

Now consider the following:
The FFs, the counter and the registers all have control pins that tell them when they are allowed to operate freely. Usually, you can control those pins with nothing more than an SR-latch.
You can also preset the FFs, the registers and the counter manually before you start the iterations of the circuit. That way you can simplify the design greatly.

Assume that you have connected all your IC's to a pulsing clock, but their operation is hindered by the appropriate signals on the right pins. You want your counter to count 4 times. Let's see how you can utilize the outputs of the counter to control your circuit.

In the beginning, the FF must be reset to zero, the counter must be held on clear and the registers must load their contents paralelly. This can be done by the afforementioned SR latch.
Once you release the SR latch, the counter is free to count, the FF to take input values and the register to shift. On count numbers 0,1,2 and 3, the register will have displayed all of its content on its output. This is when you want to stop shifting it. You can design a logic circuit to recognise the 11 output of the counter and inhibit the register from shifting anymore. This control signal can be ORed with the Clock Inhibit signal in order to work parallely to it. If the register stops shifting, then the Module A's output will be stabilized too.

Tutorial Questions:
Design an SR-Latch.
Describe how you can control the operation of the D-FF (7474), counter (74193) and registers (74166).
Design a circuit that recognizes the binary output 0011 (note: you only need to look at the last 2 LSBs).

The overall connections are:
From the SR-Latch to the counter, FF and registers.
From the counter to the 11-recognizer.
From the recognizer to the registers.

If you are sure you can answer the tutorial questions, don't bother posting the anwers. Otherwise, post them just to be sure.
Post a schematic for the wire connections, even a crude one.
Determine the correct connection pins on each IC.

 

On count numbers 0,1,2 and 3, the register will have displayed all of its content on its output. This is when you want to stop shifting it. You can design a logic circuit to recognise the 11 output of the counter and inhibit the register from shifting anymore. This control signal can be ORed with the Clock Inhibit signal in order to work parallely to it. If the register stops shifting, then the Module A's output will be stabilized too.

Where is the control signal?
I know the clock inhibit comes from the register... so where the output of this OR go to?

Here's my circuit. I tried my best, and I don't know where I should connect the binary probes (displays with 0 & 1 logic)?
Not sure when's the next time you'll be online, but could you please give me feedback asap? I really appreciate all the help you've given me.

 

Read the datasheet of the 74166 register more carefully. Notice that pin 6 is the Clock Inhibit pin and it is a passive pin. It doesn't emmit anything; it receives. When it gets LOW, it lets the device operate properly. When it gets HIGH, it freezes the register.

What I called control signal is the output of the circuit that will recognize the number 3 (0011) in the counter.

Initially I had another register in mind so let me make a correction: The manual control of the SR-Latch will go to the Shift/Load pin (15) and the control signal from the counter will be driven to pin 6. No OR gate is needed.
Sorry for the mixup.

I post below a quick shematic with some pin numbers. Don't forget to add the clock to all the circuits that need it.

That stray 14 on the lower left is the Clear pin of the Counter, where the SR-Signal goes.

Module B is the circuit that recognizes number 3 (11 binary).

 

Thank you so much for the schematic.

Module B is the circuit that recognizes number 3 (11 binary).

What circuit will this be?

 

You have gone that far and you can't make a truth table of 2 bits to recognise the input 11?

Make your truth table, turn it to Sum of Products and build your circuit.

Hint: It's (Qa AND Qb)

 

Is my circuit correct now? I'm so unsure if all my inputs to the registers were labeled correctly?

 

On what basis did you input the gi and li values in every other pin in the registers. These are the values you want to get, you aren't supposed to know them from before. Just input A0-A3 and B0-B3 to the pins 2-5.

Corrections to be made:
In the 7474 the PR pins will be activated when LOW (notice the little dot next to the pin). You don't want it to be activated so connect it to HIGH.

Same goes for the 74166 for the Clear pins.

For the 74193 to count upwards you need to connect pin 5 to HIGH and pin 4 to the clock.

Do be a dear and read the datasheets!!! All the above wouldn't be needed if you read the datasheet correctly.

I don't see anything else but I may be wrong. Simulate the circuit with some software to be sure.