Forem: Ritobrata Ghosh

Creating Any Boolean Function with Elementary Logic Gates

Ritobrata Ghosh — Mon, 14 Jun 2021 08:11:14 +0000

Introduction

Digital electronics is probably the most impactful and widespread technology now. It forms the basis of all of the chips- from ARM microcontrollers to processors in cellphones, all the way to uberpowerful AMD Threadrippers. In all these cases, digital electronics reign supreme.

It is very useful to learn not only about basic principles but also how these principles and the components of Digital Electronics exactly form the basis of the modern world, i.e., how do we go from basic logic gates to fully functional computers.

Elements of Computing Systems

Digital Electronics is not only important because it is the base of the modern technology that literally governs our lives, but it makes us better as programmers, and computer scientists.

Whether we are self-taught programmers or a person with a 4-year CS degree, we were never taught how we go from basic logic gates to CPUs.

A book that I have come across- The Elements of Computing Systems by By Noam Nisan and Shimon Schocken does just that. It teaches you how the basic building blocks of modern computers actually create the computers.

[Although it shows the new 2nd edition, I am reading the first one]

It promises to teach you, actively, how we can start from nothing but a NAND gate and go all the way to a full-fledged computer with an operating system, and a general-purpose programming language that runs on it, which can be used to create anything. The book is also known as nand2tetris.

I have started reading this book and working through it every Sunday, and I have almost finished a chapter.

Building Gates from Elementary Gates

People who have taken a Digital Architecture class or a Digital Electronics class will know that NAND (NOT AND) gates are called "universal gates" because some combination of them are able to create any other gates. So, when you have a NAND gate with you, you can create a general-purpose computer with it. And the book makes you do that. It makes you create many logic gates starting from AND, NOT, and OR with nothing but a pre-implemented NAND gate.

So, a NAND gate is already implemented and supplied. You first have to create AND, OR, and NOT gates. Then you go on to further create XOR gates, Multiplexors (MUX), Demultiplexors (D-MUX), and multi-bit versions of these gates and basic gates with what you have built previously, viz. AND, OR, NOT, and NAND gates.

This is a fascinating task in itself, and very intellectually stimulating.

This is where the core of the post comes in.

I will show you how to implement any Boolean function with nothing but three logic gates. This is a trick worth knowing.

Let's start.

Implementing a Boolean Function

Design a Boolean Function

Let's say we need a Boolean function that behaves in such a way-

A	B	C	Y
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

This truth table tells you that we need such a Boolean function that outputs 1 iff-

A, B, and C, three Boolean variables, are all 0
only A is 1, B and C are 0
A and C are 1, B is 0
A and B are 1, C is 0

Now, in some situations, you might need to define a Boolean function that behaves as you expect. Do not worry about what this function is doing. Let's focus on the implementation part.

Boolean Expression

I am assuming that you already know about the basic gates, and how they function.

So, in the first step to build a Boolean function, you must create the Boolean expression. Just like a Boolean variable can have two values (0, 1), and a Boolean function can only output two values (0, 1, duh!), a Boolean expression always evaluates to either 0 or 1.

How to actually do it?

You should just note in which cases the function outputs a 1. Focus just on those.
Note which variables are on (1) and which are off (0).
Keep the variables unchanged which are 1 in this case, and take a negation of those which are off (in electronics, you would put them through NOT).
Multiply them together.
For these products for each 1 in the output, just add them together.

That's it. You have got your Boolean expression.

Let me go through it step by step.

In the first occurrence of 1 in the output, we see that all the input variables are off. So, we get a*, b*, and c*, where a, b, and c are the variables representing inputs A, B, and C, respectively, and x* is the negation of x. We multiply them together, and we get a*b*c*.

In the second occurrence of 1, in a similar manner, we get- ab*c*.

For the third and fourth occurrences of 1, we get ab*c, and abc*, respectively.

We have to add them. And doing so, we get-

[You are required to write cases in the proper order. The first of three variable has these values row-wise- 0-0-0-0-1-1-1-1, the second one varies- 0-0-1-1-0-0-1-1, and the third one- 0-1-0-1-0-1-0-1.]

Implementation

You might be already aware that negation is passing through a NOT gate, multiplying is just passing through an AND gate, and adding is just an OR gate.

The first component a*b*c* can be obtained in this way-

And here are the second, third, and fourth components-

And,

Now, we have to add them all together, i.e. put these components through an OR gate. The output of the OR gate will be our final output.

Our final output.

HDL: Implement and Test

Now, if you have ICs lying around, you can quickly test this with a power supply or a 5V cell, and some wires. You will also need a multimeter or LED bulbs to check your output.

But, remember, we are building a computer from scratch when following this book. Using thousands of ICs to build a computer is not slightly practical unless you happen to have a contract with TSMC!

Something called HDL (Hardware Description Language) is used. It is an intuitive, high-level, special-purpose programming language that you use to design and test chips, and use previously created chips.

It is implemented in Java, but you do not have to worry about its implementation, you just need to use it. A GUI program is also supplied to do load and test chips.

For example, given a NAND gate, you will design an AND gate this way.

As you can see, it is very intuitive, and you can pick it up in 20 minutes.

And, this is how you'd test this:

To write our custom function in HDL, we would do-

// Custom.hdl
// this is a part of Hashnode blog Convoluted demo

CHIP Custom {
    IN a, b, c;
    OUT out;

    PARTS:
    Not(in=a, out=nota);
    Not(in=b, out=notb);
    Not(in=c, out=notc);
    And(a=nota, b=notb, out=notanotb);
    And(a=notanotb, b=notc, out=w1);
    And(a=a, b=notb, out=anotb);
    And(a=anotb, b=notc, out=w2);
    And(a=anotb, b=c, out=w3);
    And(a=a, b=b, out=ab);
    And(a=ab, b=notc, out=w4);
    Or8Way(in[0]=w1, in[1]=w2, in[2]=w3, in[3]=w4, out=out);
}

And as this is a custom chip, the .tst test file, and .cmp compare file are not supplied. So, for testing this chip, I wrote my own.

Here is the test (.tst) file-

// Custom.tst
// test file for testing custom chip
// could be found at- https://gist.github.com/ghosh-r/c4e6f5ceb1e7ea2e3ba3601c9de121be

// test file for a custom chip in Convoluted, a Hashnode blog

load Custom.hdl,
output-file Custom.out,
compare-to Custom.cmp,
output-list a%B3.1.3 b%B3.1.3 c%B3.1.3 out%B3.1.3;

set a 0,
set b 0,
set c 0,
eval,
output;

set a 0,
set b 0,
set c 1,
eval,
output;

set a 0,
set b 1,
set c 0,
eval,
output;

set a 0,
set b 1,
set c 1,
eval,
output; 

set a 1,
set b 0,
set c 0,
eval,
output;

set a 1,
set b 0,
set c 1,
eval,
output;

set a 1,
set b 1,
set c 0,
eval,
output;

set a 1,
set b 1,
set c 1,
eval,
output;

And here is the compare (.cmp) file. It contains the truth table that we expect.

// Custom.cmp
// compare file for chip Custom.hdl
// found at- https://gist.github.com/ghosh-r/c4e6f5ceb1e7ea2e3ba3601c9de121be
// test file at- https://gist.github.com/ghosh-r/cef52b9f6ac017e00d64460b025a53fe

|   a   |   b   |   c   |  out  |
|   0   |   0   |   0   |   1   |
|   0   |   0   |   1   |   0   |
|   0   |   1   |   0   |   0   |
|   0   |   1   |   1   |   0   |
|   1   |   0   |   0   |   1   |
|   1   |   0   |   1   |   1   |
|   1   |   1   |   0   |   1   |
|   1   |   1   |   1   |   0   |

Note that the text in Compare files is not robust to whitespaces.

It will be compared with the output file generated by the simulator.

Here's how the successful run looks like-

Another Example: XOR Gate

Suppose you want to implement a XOR gate from basic gates. And the truth-table would be-

A	B	Y
0	0	0
0	1	1
1	0	1
1	1	0

This will be your Boolean expression-

And this will be your HDL implementation.

// Xor.hdl

CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
    Not(in=a, out=nota);
    Not(in=b, out=notb);
    And(a=a, b=notb, out=w1);
    And(a=nota, b=b, out=w2);
    Or(a=w1, b=w2, out=out);
}

Conclusion

I showed you how to implement any Boolean function with nothing but three elementary logic gates. However, you should keep in mind that this approach is impractical when there are more variables, and the chip you want is more complicated.

Ritobrata Ghosh is a Physics undergrad, and a Deep Learning Consultant focused on Computer Vision. I am interested in ML in embedded devices, Private AI (federated learning), Deep RL, and GANs. I am also interested in Maths, problem-solving, and programming in general.

Follow me to get more similar posts.

Follow me on Twitter or connect with me on LinkedIn.

The Best 5 + 1 Podcasts for ML Learners and Practitioners

Ritobrata Ghosh — Thu, 18 Feb 2021 06:39:51 +0000

Introduction

Podcasts are a great way to learn about novel fields and tools, as well as keeping yourself updated with the fields that you care about.

I also believe that podcasts which are mainly centered around interviews are a great way to learn about the rockstars and superheroes of the AI world. You get a glimpse of how they think, what are they working on, and they solved a particular problem.

I would also argue that the content you get access to by listening to podcasts is very unique, and you cannot access them somewhere else.

In this post, I am not going into the details of why I think podcasts are great and Machine Learning learners and practitioners should listen to them.

The List

Here are the podcasts that I highly recommend for ML learners and professionals-

1. Gradient Dissent

from Weights and Biases, hosted by Lukas Biewald

It is a Machine Learning podcast that focuses on "Stories from machine learning experts solving real world problems".

Lukas hosts his podcasts in his own style. He asks really meaningful questions and is well-informed on the topics. The podcast episodes are very informative and engaging.

Length per episode: usually 30-60 minutes
Favorite episode so far: Peter Norvig, Google’s Director of Research – Singularity is in the eye of the beholder

2. DeepMind: The Podcast

from DeepMind, hosted by Hannah Fry

Hannah Fry is a superb host, as good as any professional podcast host. That sets this podcast apart from the others. Hanna Fry is a Mathematician and has had experience in hosting podcasts. She is passionate and knowledgeable about AI, and passionate about this podcast. This podcast likely has a team working behind it, and the sound effects and the music tells us so. They also make the experience absolutely entertaining.

This podcast focuses on works being done on DeepMind and hosts people working on those problems within DeepMind. The problems and solutions are described in plain words. The host also gives you a big picture view surrounding the problem, and what the future holds. This podcast is really well-structured, well-designed, and is really informative and edifying.

Length per episode: 30 minutes
Favorite episode so far: Episode 2: Go to Zero

3. Lex Fridman Podcast

hosted by Lex Fridman

Lex Fridman is an AI researcher working on autonomous vehicles, and human-robot interaction. He also teaches at MIT. The way he is unique as a podcast host is that he is very focused on long-term goals, and far-reaching implications of the works of the guests. He is interested in deep things such as consciousness and the idea of AGI. He asks deep, fundamental questions and lets us know about the guests' views on these questions.

The topics on his podcast transcend the AI universe. He has had guests like Roger Penrose, Richard Dawkins, and Noam Chomsky. A significant portion of his interviews are on AI. His interviews are generally long, and hence have much more scope to discuss topics in an in-depth, detailed manner. I really like that.

Length per episode: 60-180 minutes
Favorite episode so far: David Silver: AlphaGo, AlphaZero, and Deep Reinforcement Learning | Lex Fridman Podcast #86

4. Chai Time Data Science

hosted by Sanyam Bhutani

Sanyam Bhutani is a community man. Period. As a Data Scientist at h2o.ai, he writes blogs, hosts interviews, and hosts book-reading clubs and other clubs with Machine Learning Tokyo. He is also very active on the fast.ai Communities. And he never monetizes his content! When he is interviewing guests on his podcast, he is not asking questions for the interview, but for learning, too! I like his inquisitive, humble manner of asking questions.

This podcast hosts a lot of Kaggle Competition winners and Grandmasters. He talks about the guests' journey, career, and current research, projects, and interests. And, then there is Kaggle! He often interviews winners of particular competitions and asks about their thinking and approach to those particular competitions. These are really informative for people competing on Kaggle, and/or interested in developing full pipelines for any project. It is very interesting to see the diverse set of people from diverse backgrounds win Kaggle competitions, and talk about their careers and lives on this podcast.

Length per episode: 30-90 minutes
Favorite episode so far: Chris Deotte | Secrets to Becoming 4x Kaggle Grandmaster | Discussions and Notebooks

5. Machine Learning Street Talks

hosted by Yannic Kilcher, Dr. Tim Scarfe, and Keith Dugger

This is the only entry in the list which has multiple hosts. Yannic is famous for his paper-explaining videos, and his sunglasses. Dr. Scarfe and Keith also maintain an online presence and are involved in Deep Learning.

This podcast deliberately maintains a hacker, open-source sort of aura about them. That is evident from their choice of backgrounds, style of presentation, and many more things. They delve deep into research topics and interview the person(s) attached to them. The fact that there is more than one host adds value to the conversations, rather than being a liability. The listeners get to hear from multiple perspectives and get acquainted with multiple views. The guests are also much more likely to shed light on different aspects of the research.

Length per episode: 90-120 minutes
Favorite episode so far: #040 - Adversarial Examples

The +1. Talks at Google, Microsoft Research, and TED/TEDx

Of course, you have noticed that "+1" in the title. I am including these resources together as one, because, all of the content present at the first two resources are not focused on ML or AI. And although TED has a few talks based on this topic and broader topics, it has some really good talks on ML, Data Science, and AI.

If you visit the Microsoft Research YouTube page, you will see many playlists that will kindle your excitement. For example, the AI Distinguished Lecture Series contains many thought-provoking talks in AI. The same goes with Talks at Google.

TED has quite a few talks on Data Science, AI, and its impact. And TED has been covering Data Analysis, AI, etc. years before these fields blew up. I remember listening to a talk- Making data mean more through storytelling | Ben Wellington which was given back in 2015 that highlights how creative, yet simple Data Analysis can reveal many important insights, and how it can make lives better by influencing government policies. There's another talk that I will mention- Daphne Koller: What we're learning from online education. The co-founder of Coursera gives us many deep insights about online education and how data are at the core and crux of it. This is yet another example of data transforming something fundamental like education, and impacting the lives of millions positively.

Length per episode: mixed

Conclusion

Podcasts about and around Machine Learning have seen a boom in recent times. It is important not to get overwhelmed in this overflow. I have listened to many podcasts about ML/Data Science and decided on these as the bests.

If you have any suggestions or questions, please let me know in the comments.