[From Nand to Tetris] 모듈 1. Boolean Functions and Gate Logic

Key concepts

• Boolean algebra
• Boolean functions
• gate logic
• elementary logic gates
• Hardware Description Language(HDL)
• hardware simulation

---

1.1 Boolean Logic

the reason that computer only have 0s and 1s is because that's what they can get away with.

It's simplest to have only two possible values that you need to maintain.

And that's going to be enough as we will see today.

We're starting with actual, the completely theoretical logical kind of analysis of how to deal wiwth 0s and 1s. 

And later in this later in unit three we'll actually talk about how these abstract 0 and 1 signals directly are implemented as chips inside a computer.

 

what can we do with kind with if we only have 0s and 1s? 

some kind of basic operations on them.

The really nice things about Boolean values is the fact there are only a finite number of possible inputs and we can actually list each one of them.

 

Different from functions from integer through integer, then there are infinitely many integers.

So you can never write down the function in a complete specification of all the possible values.

x,y,z를 0,0,1로 치환해서 완전히 같게 만들 수 있음

 

분배, 교환 등 기본 법칙 성립

 

how to manipulate logical value에 대해 배웠다.

How can we construct a function from basic oprations?

How does that, this is exactly the kind of thing we will need to do when constructing hardware.

We know what it wants to do, but we'll have to actually construct it from Boolean operations.

 

 

---

1.2 Boolean Function Synthesis

 

지금까지 이야기 한 것: boolean functions, boolean values, boolean algebra, boolean formulas

지금부터 이야기 할 것: how we can construct boolean functions from more primitive operations.

 

given truth table을 가지고, come up with a formula that computes the same boolean function.

 

1인 줄을 찾고, write an expression that basically gets a value of 1 only at this row.

 how do you actually find the shortest of most efficient formula that's equivalent to the one we've just derived? 

Well, that's not an easy problem in general. It's not easy for humans, nor is there any algorithm that can do that efficiently.

In fact his is an NP-hard problem to actully find the shortest expression that's equivalent to a given one, or even to verify if the expression that you're given is just a constant 0 or 1.

 

Boolean function , it doesn't really matter on how many variables and what the boolean function is, can be represented in an expression using only the operations AND,OR, and NOT.

 

Integer functions not every function and integer numbers can represented just by arithmetic operation. Yet, because of the finite world that we're living in, the Boolean algebra, ever Boolean function can just be repreesented with ANDs, ORs, and NOTs.And that is what exactly gives us the basic power to actually construct computers only with these possible gates, only with these possible operations, AND, OR< NOT.

 

사실 OR도 필요 없다. ANDs and NOTs 만 가지고 construct any Boolean function을 할 수 있다.

If you have a NAND gate, you can compute everything.

---

1.3 Logic Gates

how we actually implement these Boolean functions using hardware.

하드웨어를 사용해 이전시간에 배운 이론적인 불리안 함수들을 어떻게 실행하는지에 관해.

 

Logic Gate?

• Elementary: simple chip or elementary chip which is designed to deliver a well-defined functionality.(Nand같은 것) bool연산을 수행하는 단순한 칩이라고 보면 된다.
• Composite: 좀 더 복잡한 로직 게이트(Mux나 Adder에 사용되는)

 

Elementary Logic Gate

두개의 인풋을 넣으면 하나의 값이 도출되는 Elementary Logic Gate들

how this thing is actually working에 대해서 말하지 않았고,

we just describe what kind of functionality we can expect it to deliver

 

Composite gates

Elementary 두개 합쳐서 Composite 만든 모습

 

Interface vs Implementation

• gate interface = gate obstruction, 즉 gate가 what인지에 대한 설명일 뿐, 어떻게 작동하는지 이해하려면 another level of detail에 접근해야 한다.
• one obstruction, many different implementations
  • some implementation may be more elegant, they may use less energy, they maybe less or more expensive, and so on
  • This is very typical in computer science, whenever you build a large system, you have this duality

한가지 동작을 실행하는 데 다양한 방법이 있을 수 있고 이것은 컴퓨터 과학에서 흔하다.

 

And는 둘다 스위치가 눌려야 전구가 켜지고, Or은 두 개 중 하나만 눌려도 켜진다. / 3개 짜리

 

회로를 실제로 구성해보는 건 생략. 전자기학 수업아님.

 

Nand Gate로 시작해서, going to piece them together in some clever ways in order to generate and produce the required functionality.

 

 

---

1.4 Hardware Description Language

how we can actually build and implement the logic gates using formalism called Hardware Description Language(HDL)

로직 게이트를 기계어로 어떻게 실행시키는 지에 관하여

 

우선 필요한 것,

complete description of the desired gate's behavior (very simple truth table과 같은 것)

truth table을 가지고 HDLfile을 쓰기 시작.

 

when we use chips, we always wear two different hats.

• hat of the programmer whe uses the chip: chip interface
• hat of the chips builder: how we actually build this chip from scratch

builder라고 생각하고 NAND 게이트를 우선 먼저 만들어 보자!

truth table을 가지고 inspect 한 뒤에 gate를 만들자!

 

draw the boundary of the chip diagram = user's view of this gate 즉, gate interface

a에 관해 다양한 destination 이 존재하는데, 

when you write HDL code, you are allowed to take any signal. And distribute as many copies as you want of this signal into as many destinations as you want.

 

빨간 부분: connect the different chip parts together하기 위함

그리고 모든 회로에 이름을 붙여둬야해 . 그것은 우리의 역할이고 self-descriptive하지

그리고 HDL로 작성해야 할 내용들.

• describe only the chip's interface: contract that we actually have to implement
• describes the chip along with all its connections 등

하지만, HDL diagram은 nothing more than a textual description of the gate diagram일 뿐!

same interface can be implemented in typically in many different ways

interface is unique and implementation varies

 

HDL 작성시 유의사항

• 다른 언어들 처럼 good descriptive name
• readabiltiy가 중요하다

HDL만의 특징

• functional or declarative language / no procedure going on, 즉 static dexcription of the gate diagram일 뿐!, procedual part는 not part of HDL code. external to the HDL code

이상해보일 수 있는 convention을 적용해 HDL을 앞으로 사용할 것

유명한 HDL에는 VHDL, Verilog같은 것이 있음!

 

HDL design을 가지고 hardware simulator의 context 작성할 예정

 

---

1.5 Hardware Simulation

우리가 작성한 HDL 코드가 제대로 작동하는지 알 수 없다.

 

verify to the best of our ability that the program or the HDL file deliver the inteded functionality of the underlying chip.

 

https://nand2tetris.github.io/web-ide/chip/

NAND2Tetris

interatively test and simulate HDL file을 해볼 수 있는 온라인사이트

script-based simulation

 

code가 acutally correct 한지 알 수 없다.

we have to tell the simulator to evaluate the chip's logic on the supplied inputs

we can also inspect the current values of the internal pins.

 

interactive simulation은 지루할 수 있다. lots of bugs in your design하거나 each time you have to 라면

하드웨어 시뮬레이터 어떻게 사용하는지 대강의 영상

resulting output file and convinced ourself that the HDL file is actually correct

이것이 privilege of looking at an output file m 

 

어떤 이가 성공한 output file을 compare file로 받아 다시 simulation 시킴

 

makes some decision about how to break this overall behavior into a set of smaller chips if you will or sort of lower-level chips.

example of divide and conquer

• get a stub file that contains the documentation of the chip that you have to build, along with its interface
• get a test script
• get a compare file
• understand interface
• understand what the chip is supposed to do
• how we are going to test it
• you have to do is write the missing implementation

---

1.6 Multi-Bit Buses

a bunch of bits together that are manipulated together and have one meaning are sometimes called buses.

 

our chips has 32 wires feeding intto it, and 16 wires going out of it, but still it's convenient to think about it as two numbers feeding in and one number feeding out.

 

take a bunch of bits in the bus and just converge them and mash them together into a single value. we call this multiway chip

multiway chip 3개 input 인 chip과 4개 input인 chip

 

technical conveniences , break a bus into sub-buses.

예를 들어 16bit bus를 두개의 8bit bus called lsb(least significant byte)와 msb(more significant byte)로 나누는 것이다.

그리고 plug 해가는 것!

 

ovelap을 허용한다.

0~5까지의 6bits그리고 다시 3~7의 6bits

so simply ouputting the same bus in multiple ways that may be overlapping sub-bused. we allow that

 

---

1.7 Project 1 Overview

프로젝트 개요

Nand를 가지고 만들어야 할 16가지의 Gate

Nand gate줄 테니 컴퓨터 만들어와! 어떻게요? 한번에 한 단계씩 찬찬히

 

 

 

A. Elementary logic gates - MultiPlexor와 DemultiPlexor

 

Elementary chips 중 가장 복잡한 두 개

 

1) MultiPlexor

input: a, b, sel

sel = 0 이면 a를 추출, sel = 1이면 b를 추출

3개의 input 8가지 의 경우의 수

 

 

Programmable Gate

can act either as an And gate or as an Or gate

if the select bit 0 = And gate

select bit 1 = Or Gate

 

2) DemultiPlexor

inverse of a multiplexor

 

it recieves a single input, and based on the selection bit, it either channel the input to an a output, or to a b ouput.

kind of distributor of a value into one several possible channel

 

3)how multiplexing 과 demultiplexing이 play in the context of communication networks

 

음악, 영화 등 다양한 신호가 들어와서 single communication line으로 send over되어야 하는 경우를 생각해봐. 그리고 다시 multiple message를 다시 내뿜어야 하는 상황 등 말이지.

이건 asynchronous하게 실행된다.

 

B. 16-bit variant - And16

16bit의 And연산을 하는 것

 

C. Muti-way variants -Mux4Way16

 

프로젝트 수행법!

diagram, HDL file, compare file, contract 다 받아서 나의 HDL 파일을 만들면 됌.

https://nand2tetris.github.io/web-ide/chip/

NAND2Tetris

여기서 Project1 선택후 실행

https://www.nand2tetris.org/software

Software | nand2tetris

 

프로젝트 Tips

 

in general and just like we always do in computer science, strive to use as few parts as possible, try to create an implementation which is elegant, readable, and well done.

 

---

1.8 Perspectives(Q&A)

different aspeects of building hardware and software systems.

 

Q. NAND gate가 아닌 걸로도 HACK 만들 수 있잖아?

 

However, it turns out that NAND gates are very popular in physical implementations of hardware systems. Because there are many integrated circuit technologies in which it is quite cheap or relatively cheap to build NAND gates.

 

you use the usual tools of computer science modularity and abstraction. You break a complex problem into simpler parts, and the simpler parts are simpler to optimize and to construct.