From the NAND gate to a general-purpose computer

Elements of Computing Systems-1

Introduction to the course
Dr. Jyothish Lal G, Assistant Professor (Sr. Gr)

Department of AI / Center for Computational Engineering and Networking (CEN)

Amrita School of AI, Coimbatore
Acknowledgment: Prof. Noam Nisan, Prof. Shimon Schocken and Dr. D. Govind
The Road Ahead…………

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 2

 Abstraction: The higher level !

● Computer may not understand this language

● Characters in the text files are “dead characters” unless
they are parsed
EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 3
How these letters perform intended action?

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 4

How is this done?

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 5

● We do not worry about the “ How “

● Why? Implementation

● Because it is enough to know about “What”

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 6
 Is it a scam?
● Don’t worry about “How”
Implementation
● Who will worry ?
– Someone else
– You, may be later
● Separation of concerns

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 7

 Holistic Picture of the Course
Human Application for Systems Design
Thought
Abstract Interface
Software Logic
Compiler
High Level /Hierarchy
Language & OS

Abstract Interface
Virtual Machine Translator
Virtual Machine
Abstract Interface
Assembly
Language
Assembler

Abstract Interface Architecture

Hardware Logic
Machine /Hierarchy
Language Gate Logic Electrical Engineering
Abstract Interface
Hardware Abstract Interface
Platform Chips and Logic Physics
Gates
EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 8
Elements of Computing Systems: Course In a Nutshell
From the NAND gate

How do we build a computer

CPU
ROM RAM

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 9

Course Syllabus

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 10

 Course Objectives

● Course Objectives
– The course will expose the students to basics of Boolean algebra, and it
will further help them to understand the workings of a modern computer.
– Students will be trained to build a computing system using elementary
logic gates such as NAND, AND, OR etc. through simulation software

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 11

 Course Outcomes
After completing this course, students will be able to
CO1 Realize the concept of Boolean Algebra and Digital Logic
CO2 Implement different combinational and sequential digital logic systems
CO3 Design the hardware hierarchy of general-purpose computing systems
CO4 Build a general-purpose computer capable of running stored programs
written in the machine language

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 12

 Reference
● Text Book: The Elements of Computing Systems, By Noam
Nisan and Shimon Schocken

https://www.nand2tetris.org/course

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 13

 Related Subjects

– Introduction to Electrical and Electronics Engineering

• Electronics circuits for logic gate implementations
– Data Structures & Algorithms
• For writing the parsers for assemblers, VM translators and compilers
– Object Oriented Programming in Java
• Jack high level programming is almost similar to JAVA programming

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 14

Evaluation Pattern

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 15

 Pre-requisite Knowledge
● None !
● All the necessary know-how will be learned in
this course

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 16

 The fundamentals
● Number systems

● Boolean algebra and Karnaugh Maps

● Logic gates

● Realization of basic gates using universal gates

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 17

 Number System
● Decimal Number System
– Number system with base 10
– Uses 10 numbers (0, 1 ,2 ,3 , 4 , 5 ,6 ,7 ,8, 9)
● Binary Number system
– Number system with base 2
– Uses 2 numbers (0 and 1)
● Hexadecimal Number System
– Number system uses 16 numbers
– 0 1 2 3 4 5 6 7 8 9AB C DE F
● Octal Number system
– Number system uses 8 numbers
– 0, 1, 2, 3, 4, 5, 6, 7

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 18

 Boolean Logic
● Truth Table Representation of Boolean Function

● x, y and z are the Boolean variables

● All possible values of Boolean variables and corresponding
function outputs are represented in the truth table

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 19

 Boolean Expression
● Canonical representation of Boolean functions: Sum of products or
product of sums representation

● Wherever the Boolean function output is 1 (in the truth table can be
expressed in the canonical form

● From the table: f(x,y,z)=x’yz’+xy’z’+xyz’

● Every Boolean expression no matter how complex can be expressed

using Boolean operators such as AND, OR and NOT

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 20

 Simplifying Boolean Expressions

Two methods for simplifying

● Algebraic method (use Boolean algebra
theorems)
● Karnaugh mapping method (systematic, step-by-
step approach)
EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 21
 Logic Gates
● A gate (Physical device) implements a Boolean function

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 22

 Logic Design for Derived Gates: XOR

❑ Boolean Expression of Xor

❑ Xor(a,b)=Or(And(a,Not(b))+And(Not(a),b)))

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 23

How do we build a chip?

We use Hardware Simulators

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 24

 Implementation in the Hardware Platform
● Hack Platform

● Simulation of different logic gates, Boolean logic, registers,

ALUs are done through the Hardware Description Language
(HDL) in the hack platform

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 25

 Hardware Platform

● Registers
● Memory Units Logic Gates
● ALU

• In this course the hardware units are built using NAND

gates (Basic chipset)

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 26

Example 1

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 27

Building a logic gate

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 28

 Steps
● Design the gate architecture
● Specify the architecture in HDL
● Test the chip in a hardware simulator
● Optimize the design

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 29

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 30
 Chip diagram

Design

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 31

Specify the chip diagram using HDL program

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 32

Hardware Implementation

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 33

Hardware simulation in a nutshell

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 34

 v

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 35

Chip Design: Computational Exercises

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 36

Example 2
Will be discussed later

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 37

BCD to seven segment decoder

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 38

 K-Map
Simplification

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 39

Draw logic design using gates

HDL Implementation
EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 40
Implementation: HDL

1000 8

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 41

Thank You

EOC-1|B.TECH CSE (AI)|CEN|Dr. Jyothish 42