The Elements of Computing Systems: 01-Boolean Logic
The Elements of computing systems also known as nand2tetris is a book that focus on how computers are build from scratch and how they work, and the projects implemented with the book let readers gradually build a basic hardware platform and a modern software hierarchy from the ground up. In the process, the students gain hands-on knowledge of hardware architecture, operating systems, programming languages, compilers, data structures, algorithms, and software engineering, the book is authored by Shimon Schocken ( founding dean of the Efi Arazi School of Computer Science) and Noam Nisan ( dean of the School of CSE of the Hebrew University of Jerusalem). The book is also taught as a course series on coursera and the purpose of the book is to provide software developers and engineers to get a good grasp at the Computer Science fundamentals & knowledge.
This series of articles will summarize the course content for readers and along with the project implementations to get maximum out of the book content in shortest of time.This article is the first of the series and will focus on the first chapter and project of the book i.e, Boolean Logic
Boolean Algebra
Boolean algebra deals with Boolean values(also called binary) that are typically labeled true/false, 1/0. A Boolean function is a function that operates on binary inputs and returns binary outputs.
Gate Logic
A gate is a physical device that implements a Boolean function. If a Boolean function f operates on n variables and returns m binary results (in all our examples so far, m was 1), the gate that implements f will have n input pins and m output pins. When we put some values v1 … vn in the gate’s input pins, the gate’s ‘‘logic’’ — its internal structure — should compute and output fðv1 … vnÞ. And just like complex Boolean functions can be expressed in terms of simpler functions, complex gates are composed from more elementary gates. Today, most gates are implemented as transistors etched in silicon, packaged as chips.
Basic Logic Gates
-Nand Gate ` Not (x And y) , we will implement all our other logic gates for the project series using Nand gate and those gates that are subsequently build on composite gates created using Nand Gate.
a | b | Nand(a,b)
0 | 0 | 1
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
Chip name: Nand
Inputs: a, b
Outputs: out Function: If a=b=1 then out=0 else out=1
Not (’): A single input gate complements the input value and returns it as output.
a | Not(a)
0 | 1
1 | 0
Chip name: Not
Inputs: in
Outputs: out
Function: If in=0 then out=1 else out=0
-And (.) gate
a | b | And(a,b)
0 | 0 | 0
0 | 1 | 0
1 | 0 | 0
1 | 1 | 1
Chip name: And
Inputs: a, b
Outputs: out
Function: If a=b=1 then out=1 else out=0.
-Or Gate(+)
a | b | Or(a,b)
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 1
Chip name: Or
Inputs: a, b
Outputs: out
Function: If a=b=0 then out=0 else out=1.
-Xor gate
a | b | Xor(a,b)
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
Chip name: Xor
Inputs: a, b
Outputs: out Function: If a=/b then out=1 else out=0.
-Multiplexer
sel | out
0 | a
1 | b
Chip name: Mux
Inputs: a, b, sel
Outputs: out Function: If sel=0 then out=a else out=b.
-DeMultiplexer
sel| a | b
0 | in| 0
1 | 0 | in
Chip name: DMux
Inputs: in, sel Outputs: a, b
Function: If sel=0 then {a=in, b=0} else {a=0, b=in}.
Truth Table Representation
The simplest way to specify a Boolean function is to enumerate all the possible values of the function’s input variables, along with the function’s output for each set of inputs. This is called the truth table representation of the function
f(x,y,z)=(x+y). z’ (z’ is Not z or complement of z)
Truth Table:-
x y z | f(x,y,z)
0 0 0 | 0
0 0 1 | 0
0 1 0 | 1
0 1 1 | 0
1 0 0 | 1
1 0 1 | 0
1 1 0 | 1
1 1 1 | 0
Canonical Representation
f(x,y,z)=x’yz’+xy’z’+xyz’
to form the canonical form check the truth table and if the result is 1 then we will do an And operation on x, y & z if the value of x =1 the statement will contain x , else if x=0 then x’ (Not x will be used).
Boolean Identities
Commutative Law
• (x And y) = (y And x)
• (x Or y) = (y Or x)
Associative Laws
• (x And (y And z)) = ((x And y) And z)
- (x Or (y Or z)) = ((x Or y) Or z)
Distributive Laws
• (x And (y Or z)) = (x And y) Or (x And z)
• (x Or (y And z)) = (x Or y) And (x Or z)
De Morgan laws
• Not(x And y) = Not(x) Or Not(y)
- Not(x Or y) = Not(x) And Not(y)
Hardware Description Language (HDL)
Hardware Description Language is used to design chip architecture, a hardware simulator takes the HDL program as input and provide image of modeled chip in memory and the test can be implemented on the HDL program to check the correctness of the logic implemented.
Since Hardware Description Language is a hardware construction language, the process of writing and debugging HDL programs is quite similar to software development. The main difference is that instead of writing code in a language like Java, we write it in HDL, and instead of using a compiler to translate and test the code, we use a hardware simulator. The hardware simulator is a computer program that knows how to parse and interpret HDL code, turn it into an executable representation, and test it according to the specifications of a given test script.
HDL implementation of a Xor gate
Project Implementation Code ( https://github.com/yadavanuj1996/nand2tetris/tree/master/PROJECTS/01-boolean-logic)