CODEWITHSUNDEEP
cpu-architecturelogical-operatorsnand2tetris
Gabi_Ma
Gabi_Ma

Reputation: 31

Intuition for implementing logic gates

I've been asked to implement logic gates in semi-HDL language for an exercise. The problem is that I'm lack of intuition regarding the implementations and can't see a method or algorithm for "turning" a truth-table into logic gates, even the more simple one (like XOR); how can one "transform" an operator into the form of several logic gates? Until now the exercise feels like "trying all possible combinations of logic gates" and I guess that it souldn't be like that.

Upvotes: 2

Views: 713

Answers (2)

z2e3r40o
z2e3r40o

Reputation: 56

Since the original question is tagged with nand2tetris I think a different answer is in order.

If you're working through the book or the coursera course, then you should have the information already available to work through this yourself. However, I also struggled with this because it was new to me so maybe I understand what you're going through and can help. The coursera course should cover the implementation of Xor in Week 1. The book covers Xor in Chapter 1. I will walk through my understanding of the book's explanation here.

The authors have asked folks not to provide answers to the problems on the internet. However, the answer for Xor is worked through and provided by the authors in the book, you can find it on page 16. Given this, I'm going to go ahead and provide my own explanation here.

In order to implement Xor, you need to understand the following bits of what the authors say:

  1. "... every Boolean function can be expressed using at least one Boolean expression called the canonical representation", page 9
  2. "Starting with the function’s truth table, we focus on all the rows in which the function has value 1. For each such row, we construct a term created by And-ing together literals(variables or their negations) that fix the values of all the row’s inputs.", page 9
  3. "Now, if we Or-together all these terms (for all the rows where the function has value1), we get a Boolean expression that is equivalent to the given truth table.", page 9
  4. "This ... leads to an important conclusion: Every Boolean function, no matter how complex, can be expressed using three Boolean operators only: And, Or, and Not", page9

Therefore, if you're trying to implement a boolean logic gate (as Xor is), you can do so by writing down its truth table, writing down the canonical representation of that truth table, and then implementing the boolean logic gate in HDL using a combination of And, Or, and Not gates as specified by the canonical representation.

Here's how it works for Xor:

  1. Write down the truth table for Xor:
a  b   out 
0  0 |  0  
0  1 |  1  
1  0 |  1  
1  1 |  0
  1. Write down the canonical representation for the Xor truth table:
(!a && b) || (a && !b)
  1. Implement the canonical representation in HDL:
CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
    // !a && b
    Not(in=a, out=nota);
    And(a=nota, b=b, out=lhs);
    // a && !b
    Not(in=b, out=notb);
    And(a=a, b=notb, out=rhs);

    // (!a && b) || (a && !b)
    Or(a=lhs, b=rhs, out=out);
}

And that's it.

Specifically, I think the technique you probably need to learn to solve this problem on your own is how to write down the canonical representation of a truth table. Therefore, try and work out how I got from step 1 to step 2 and if you have questions ask them here. Remember that the book and coursera course both go over exactly how to do this and I've quoted the most relevant bits from the book above.

I hope this leads to the intuition you're looking for. Best of luck.

Upvotes: 3

ajit
ajit

Reputation: 418

Since you talked about going from truth table to its implementation, I am giving you an alternate way to realize or visualize a digital circuit. This is nowadays more prevalent, hence every digital circuit designer should be aware of it.

Digital circuits are nowadays usually implemented in FPGA's or CPLD's (containing an array of LUT(Look Up Table) and flip-flops), instead of using individual basic gates like (AND,OR and NOT) or NAND or NOR. LUT are used to implement any combinational circuits.

Put simply a LUT is a multiplexer. Relating it with truth table (TT), output of TT (0's and 1's) is connected to input of multiplexer. Select lines of multiplexer is input of TT.

And alternate way to view LUT is a memory, which store output of a TT. Use input of TT as an address to get the value at the specific location.

E.g., A half adder can be implemented using Two 4-to-1 multiplexer. 4 inputs for Sum multiplexer will be 0,1,1,0 and 4 inputs for Carry multiplexer would be 0,0,0,1. There will 2 select lines in each multiplexer, the input A and B.

Another E.g., A full adder can be implemented using Two 8-to-1 multiplexer. 8 inputs for Sum multiplexer will be 0,1,1,0,1,0,0,1 and 8 inputs for Carry multiplexer would be 0,0,0,1,0,1,1,1. There will 3 select lines in each multiplexer, the input A and B and Cin.

Upvotes: 2

Related Questions