Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Task: Design a 2 bit comparator.

Input: 2x 2 bit (I take it as 2 2-bit values, let them be unsigned for simplicity) Output: 1 if result input1>input2 is true, 0 otherwise

Develop truth table and derive circuits.

The problem: I'm completely new to this so I have not even a idea where where to look for the lighthouse.

The question: I'M NOT LOOKING FOR COMPLETE SOLUTION, instead I'm looking for a guidance through topics/materials which I should check to be able to solve it myself.

Done so far: I started with understanding logical gates and those seem to be pretty straight forward.

P.S.: Purpose of posting this question is to boost the speed with which I will get to the actual solution.

SOLUTION: f(A,B,C,D) = !AB!C!D + A!C + ABC!D. (! - used for negation or NOR, ABC notations means A AND B AND C). I had three adjacent rectangles two of which were of unit cell size and one of 4 cells size (one cell was actually far away, but there's this toroidally connection property, not sure about terminology). A and B are MSD and LSD of the first number respectfully and B and C are same for second number. As for the circuit image: sorry folks my hand drawing requires strong mental stability.

share|improve this question
2  
Do you know what a truth table is? Also, curious of how you are doing a reasonably advanced problem when you had to start from understanding what logic gates are? –  Paresh Feb 9 '13 at 20:06
    
@Paresh, well I'm not completely completely new :-). Surely I know what truth table is. Just devoured Karnaugh map article and ready to move on. –  Denys S. Feb 9 '13 at 20:17
    
Aah, that should make things easier. In that case, where exactly are you having trouble? For example, did you form the truth table? If yes, did you manage to get a boolean expression from it? –  Paresh Feb 9 '13 at 20:21
    
@Paresh, I went straight to Karnaugh map and got next: f(ABCD)=!AB!C!D + A!C + ABC!D. (! - used for negation or NOR, ABC notations means A AND B AND C). I had three adjusent rectangles two of which were of unit cell size and one of 4 cells size (one cell was actually far away, but there's this toroidally connection property, not sure about terminology). A and B are MSD and LSD of the first number respectfully and B and C are same for second number. This problem seems to be almost the same as here: en.wikipedia.org/wiki/Karnaugh_map#Example –  Denys S. Feb 9 '13 at 20:43
    
Well, your expression is correct (assuming AB is input1 and CD is input2, and A and C are both the most significant bits). Which means you are almost done! You might want to go through some of the links I provided, but it seems to me that you are already well set - and definitely not new as your question suggests! :) –  Paresh Feb 9 '13 at 20:53
show 3 more comments

2 Answers 2

up vote 3 down vote accepted

Well, as the problem asks you to make a truth table, you should first make one (this is generally a good idea even if not asked explicitly). For your question, you can say assign two bits to input1, say $a$ and $b$, and two bits to the input2, say $x$ and $y$. Then you might say that if $a = 1$ and $b = 0$, input 1 is $2$.

Once you have the truth table (4 inputs, one output), you can get the corresponding boolean expression from the truth table in "sum-of-products" form. Basically, suppose for every entry where the output is 1, you form a "min-term" of the inputs. For example, say for 2 inputs $p$ and $q$, if output is $1$ when $p=1$ and $q = 0$, the min-term would be $p\bar{q}$. Get these min-terms for all inputs where the output is 1, and add them/OR-them together. This is because the output is 1 if and only if any one min-terms is true. You can read more here or here or here.

Now, once you have the boolean expression, you might want to minimize it - implement the logic using fewer gates. This is not asked in your question, but you might want to do it anyways. Karnaugh map technique, which you seem to already have read, is one technique. There is another called the Quine-McCluskey algorithm.

Once you have the boolean expression, you can generate the corresponding circuit mechanically. So, for each min-term, implement it using AND gates, and NOT gates. Connect all these to the input of a OR gate. For example, for something like $p\bar{q} + \bar{p}q$, $p\bar{q}$ means $p$ AND (NOT $q$). Do the same for the other min-term, and give them to the input of an OR gate. The above links also provide information and examples about this.

As for speed, you'll get faster with practice!

share|improve this answer
add comment

There is a methodology for implementing logical Combinational circuit

suppose your Boolean function is $f(x_1,x_2,...,x_n)=(y_1,y_2,...,y_m)$ in which $x_i,y_i \in \{0,1\}$

1) First make a Truth Table

2) Then write each $y_j$ base on $(x_1, x_2,..., x_n)$ using CNF or DNF

3) Then use Quine-McCluskey for function minimization.

share|improve this answer
add comment

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.