Digital Logic Structures Chapter 3 Digital Logic Structures

Contents Bottom Up !!! Transistor  Logic Gates  Logic Circuits  ? Combinational Logic Circuits (조합 논리 회로) Sequential Logic Circuits (순차 논리 회로) – Memory !!! Memory !!! Finite State Machine (FSM) State Diagram

Transistor: Building Block of Computers 마이크로 프로세서는 수백만 개 이상의 트랜지스터를 포함 Intel Pentium 4 (2000): 4800만개 IBM PowerPC 750FX (2002): 3800만개 IBM/Apple PowerPC G5 (2003): 5800만개 각 트랜지스터는 논리적으로 하나의 스위치 같이 동작 트랜지스터 조합으로 논리 함수 구현 AND, OR, NOT 논리 함수 조합으로 상위 계층 구조 구현 가산기(Adder), 다중화기(multiplexer), decoder, register, … 이들의 조합으로 프로세서를 구현 LC-3 Intel and Pentium are trademarks of Intel Corporation. IBM and PowerPC are trademarks of International Business Machines Corporation. Apple is a trademark of Apple Computer, Inc.

Simple Switch Circuit 스위치 개방 : 스위치 닫음 : 스위치 기반 회로는 두 개 상태로 간단히 표현됨 회로에 전류 흐르지 않음, 전등은 OFF Vout = +2.9V 스위치 닫음 : 회로에 전류 흐름, 전등 ON Vout = 0V 스위치 기반 회로는 두 개 상태로 간단히 표현됨 On/Off, Open/Closed, 전압 있음/전압 없음

n-type MOS Transistor Gate = 1 Gate = 0 MOS = Metal Oxide Semiconductor (금속 산화막 반도체) n-type과 p-type의 두 가지 형태가 있음 n-type Gate에 전압이 있으면 #1과 #2 사이의 스위치 닫힘. Gate에 전압이 없으면 #1과 #2 사이의 스위치 개방. Gate = 1 Gate = 0 #2 단자는 GND (0V)에 연결되어야 함

p-type MOS Transistor Gate = 1 Gate = 0 p-type #1 단자는 2.9V에 연결되어야 함 n-type과 반대의 특성 Gate에 전압이 있으면 #1과 #2 사이의 스위치 개방. Gate에 전압이 없으면 #1과 #2 사이의 스위치 닫힘. Gate = 1 Gate = 0 #1 단자는 2.9V에 연결되어야 함

Logic Gates MOS 트랜지스터의 동작 특성을 이용하여 논리 함수 구현 : AND, OR, NOT Digital symbols: 각 디지털 값에 대응하여 아날로그 전압 값 구간을 결정 트랜지스터의 전기적 특성에 따라 전압 값 구간 결정 “1”을 위한 전압 값으로 일반적으로 쓰이는 값들 : +5V, +3.3V, +2.9V 본 강의의 교재에서는 +2.9V를 사용

CMOS Circuit Complementary MOS (상보성 금속 산화막 반도체) Uses both n-type and p-type MOS transistors p-type 양(+) 전압에 연결 입력이 0인 경우 출력 전압을 UP n-type GND에 연결 입력이 1인 경우 출력 전압을 DOWN 모든 입력에 대해 출력은 GND 또는 (+) 둘 중의 하나로 연결, 두 가지 모두에 연결되어서는 안됨

Inverter (NOT Gate) Truth table In Out 0 V 2.9 V In Out 1

NOR Gate A B C 1 참고 : 직렬 구조가 상단, 병렬 구조가 하단

OR Gate A B C 1 NOR에 Inverter를 추가

NAND Gate (AND-NOT) A B C 1 참고: 병렬 구조가 상단, 직렬 구조가 하단

AND Gate A B C 1 NAND에 Inverter를 추가

Basic Logic Gates

DeMorgan's Law AND를 OR로 (OR를 AND로) 변경하기 위해 입력과 출력에 NOT 적용 A+B와 동일 AND로 (NOT와 연계하여) OR 실현 AND를 OR로 (OR를 AND로) 변경하기 위해 입력과 출력에 NOT 적용 A B 1 If there's time, perhaps discuss how all gates can be implemented with NAND (or NOR). Therefore, you can implement any truth table using only NAND (or NOR) gates. A+B와 동일

More than 2 Inputs? AND/OR 는 여러 개의 입력을 가질 수 있음 NAND/NOR도 비슷함. 여러 개의 2-입력 게이트 또는 하나의 CMOS 회로로 구현 가능 NAND and NOR are not associative. Jim Conrad’s example: NAND(NAND(0,0), 1) = NAND(1, 1) = 0 NAND(0, NAND(0,1)) = NAND(0, 0) = 1

요약 MOS 트랜지스터는 논리 함수 구현을 위한 스위치로 쓰임 기본 게이트: NOT, NOR, NAND n-type: GND에 연결, 0의 출력을 얻기 위해 1을 입력 p-type: +2.9V에 연결, 1의 출력을 얻기 위해 1을 입력 기본 게이트: NOT, NOR, NAND 논리 함수는 일반적으로 AND, OR, 그리고 NOT 게이트 사용 DeMorgan's Law 입력과 출력에 NOT를 적용하여 값을 뒤집으면 AND를 OR로 (OR를 AND로) 변경할 수 있음.

Building Functions from Logic Gates 조합 논리 회로 (Combinational Logic Circuit) 현재 입력에 의해서만 출력이 결정되는 회로 Stateless : 내부적으로 상태 정보를 유지하지 않음 순차 논리 회로 (Sequential Logic Circuit) 현재 입력 뿐 아니라 이전 입력도 출력에 영향을 미치는 회로 이전 입력에 의한 상태 정보를 유지  정보 저장이 가능 먼저 몇 가지 유용한 조합 논리 회로를 살펴 본 후 순차 논리 회로를 이용하여 정보를 저장하는 방법을 보일 예정

Decoder 2-bit decoder 𝒏 inputs, 𝟐 𝒏 outputs 𝟐 𝒏 개의 출력 중 오직 하나의 출력만 1의 값을 가짐, 𝟐 𝒏 개의 입력 패턴마다 하나의 출력이 대응. 2-bit decoder Uses of decoder: convert memory/register address to a control line that selects that location convert an opcode to one of n control lines

Multiplexer (MUX) 4-to-1 MUX 𝒏-bit selector와 𝟐 𝒏 개의 입력, 하나의 출력 Another view: decode S, and AND each output with one of the MUX inputs. Also explain multi-bit inputs. Uses of multiplexer: select which input to use for function select which computed value to pass to next stage (or to place on bus) 4-to-1 MUX

Full Adder 각 1 bit인 A와 B의 2개 입력과 입력 자리올림 Cin을 더해 1 bit의 덧셈 결과 S와 자리올림 Cout을 출력하는 가산기 Half Adder는 carry-in이 없는 것 A B Cin S Cout 1 A half-adder is one that doesn't take a carry-in. Sum is one when 1 or 3 inputs are one. Carry-out is one when 2 or 3 inputs are one.

Four-bit Adder This is called a "ripple-carry" adder. The sum becomes valid as the carry ripples its way from the low bit to the high bit. How many gate delays until the output is settled?

Logical Completeness – 논리적 완결성 AND, OR, NOT으로 임의의 진리표(Truth Table) 구현이 가능 A B C D 1 진리표에서 “1”을 결과로 가지는 입력 값 조합들에 대해 AND 게이트 구성 위 AND 게이트의 출력을 OR Note the use of the bubbles (NOT) in the input.

조합 논리 회로 vs. 순차 논리 회로 Combinational Circuit Sequential Circuit 주어진 입력 조합에 대해 항상 동일한 출력 값 예: 가산기는 이전 입력에 무관하게 현재 입력에 대한 합과 자리올림 값 출력 Sequential Circuit 정보를 저장 출력은 입력 뿐 아니라 저장된 정보(상태)에 의해 결정 따라서 입력 값이 같아도 저장된 정보에 따라 다른 출력이 가능함 예: 번호 발급기 버튼을 누를 때 마다 번호를 하나 증가 출력 번호는 저장된 상태 값에 따라 달라짐 메모리나 상태 기계(“state machine”)를 만드는데 적합

R-S Latch - Simple Storage Element S : “set” – 저장(또는 상태, 출력 a) 값을 1로 만듦 R : “reset” 또는 “clear” – 저장 값을 0으로 만듦 R과 S가 모두 1인 경우 이전 상태 값을 그대로 유지하는 휴면(“Quiescent”) 상태 유지하는 상태 값은? 1 또는 0 – 이전 값에 의해 결정 어떤 경우든 a와 b는 다른 값을 가짐, a=1 b=0, a=0  b=1 1 1 1 1 1 1 1 1 1

다시 R=1 설정하여 휴면 상태로 들어가 현재 값 0을 유지(저장) Clearing the R-S latch 우선 현재 출력 a=1인 상태에서 R을 0으로 바꾸면 1 1 1 1 출력이 0으로 바뀜. 1 1 1 1 Setting R to zero forces b (and B) to 1, which forces a (and A) to zero. This is a stable state, because R=0 and A=0 means b=1. Bring R back to one then keeps the output at zero. What is the result if we start with a=0? 1 다시 R=1 설정하여 휴면 상태로 들어가 현재 값 0을 유지(저장)

다시 S=1 바꾸면 휴면 상태로 들어가 현재 값 1을 유지 (저장) Setting the R-S Latch 현재 출력 a = 0인 상태에서 S를 0으로 바꾸면 1 1 1 출력은 1로 바뀜. 1 1 Setting S to zero forces a (and A) to 1, which forces b (and B) to zero. This is a stable state, because S=0 and B=0 means a=1. Bring S back to one then keeps the output at one. What is the result if we start with a=1? 1 1 다시 S=1 바꾸면 휴면 상태로 들어가 현재 값 1을 유지 (저장)

R-S Latch Summary R = S = 1 S = 0, R=1 R = 0, S = 1 R = S = 0 현재 값을 유지 1로 변경 R = 0, S = 1 0으로 변경 R = S = 0 두 출력 값 모두 1 최종 값은 게이트의 전기적 특성에 의해 결정 Don’t do it!

Gated D-Latch 2 inputs: D (data)와 WE (write enable) WE = 1인 경우 latch의 결과 값은 입력 D의 값을 가짐 S = NOT(D), R = D WE = 0인 경우 latch는 이전 값을 유지 S = R = 1 The D-latch is used to store a single data bit. The latch is set to the value of D whenever WE=1; when WE=0, the current value is stored, no matter what D becomes. Using D and not(D) to control S and R makes it easier to ensure that S and R are never zero at the same time. WE allows us to control when a new value is written to the latch.

Register 레지스터 : Multiple-bits를 저장 공통의 WE 값으로 제어되는 D-latch들의 집합으로 구성 가능 WE=1 일 때 𝑛 bits의 길이 값이 레지스터에 저장 됨

Representing Multi-bit Values 구간 표시 - D[l:r], l 비트부터 r 비트까지 [ ] 대신 <>사용하는 경우도 있음 15 A = 0101001101010101 A[14:9] = 101001 A[2:0] = 101

Memory 주소 공간(Address Space): Bits를 저장하는 방법을 알았으니 Memory를 만들 수 있음 Memory - 𝐾×𝑀 크기의 bits를 가지는 논리적 배열 • 주소 공간(Address Space): number of locations (usually a power of 2) k = 2n locations Addressability: number of bits per location (예: byte-addressable, 주소 마다 1 Byte) m bits

22 x 3 Memory word WE word select input bits address write enable Decoder asserts one of the word select lines, based on address. Word select activates one of the output AND gates, which drives the selected data to the output OR gate. (For a read, this is basically a MUX -- decoder ANDed with signals, results ORed together.) When writing, the only WE bits for the proper word are asserted (based on decoder again). address decoder output bits

More Memory Details 실제 메모리 물리적 구현 방법이 이와 같은 것은 아님 그러나 논리적 구조는 매우 유사함 훨씬 밀집되어 있는 보다 적은 수의 트랜지스터를 사용, 전기적 특성이 큰 영향을 미침 그러나 논리적 구조는 매우 유사함 address decoder, word select line, word write enable 두 가지 기본 RAM (Random Access Memory) 종류 Static RAM (SRAM) 빠름, 전력이 공급되는 한 데이터를 유지 Dynamic RAM (DRAM) 느리지만 밀집도를 높일 수 있음. 시간이 흐르면 bit storage decay, 주기적으로 값을 refresh하여야 함 비휘발성(Non-Volatile, 전력 없이도 값을 유지하는) 메모리 ROM(Read-Only Memory), PROM (Programmable ROM), flash, … 삼성의 메모리 - http://samsungsemiconstory.com/403

State Machine Inputs Outputs 순차 논리 회로의 일종 State Machine Combinational 조합 논리 회로와 정보 저장소 (Storage Element)를 결합한 것 상태 값을 기억하며 입력 값과 현재 상태 값을 바탕으로 출력 값과 상태 값을 변경 State Machine Inputs Outputs Combinational Logic Circuit Storage Elements

Combinational vs. Sequential 암호가 수의 조합인 두 가지 형태의 자물쇠 30 15 5 10 20 25 4 1 8 Combinational 자물쇠 풀기의 성공 여부는 값(Value) 에 의해 결정 해당 값을 어떤 순서로 정했는지는 중요하지 않음 Sequential 자물쇠 풀기의 성공 여부는 값 뿐 아니라 값을 입력하는 순서(Sequence)에 의함 (예: 오른쪽으로 13 [R-13], 왼쪽으로 22 [L-22], 오른쪽으로 [R-3] )

The Concept of State “상태(State)”라는 개념은 컴퓨터 엔지니어링에서 매우 중요 시스템의 상태란 상태 포착이 이루어진 그 순간의 시스템의 모든 관련 요소들의 상태를 의미 The state of a system is a snapshot of all the relevant elements of the system at the moment the snapshot is taken. 예 야구 경기의 상태는 “스코어보드”로 표현 가능 Tic-tac-toe 게임의 상태는 보드에 O/X를 배치하여 표현 가능

State of Sequential Lock 앞의 Sequential 자물쇠는 A에서 D까지 다음 4개의 상태를 가진다. 자물쇠는 잠긴 상태이며 어떠한 연관 작업도 이루어지지 않은 상태 자물쇠는 잠긴 상태이며 사용자가 손잡이를 오른쪽으로 돌려 13을 입력한 상태 [R-13] 자물쇠는 잠긴 상태이며 사용자가 손잡이를 오른쪽으로 돌려 13을 입력하고 [R-13] 이어서 손잡이를 왼쪽으로 돌려 22를 입력한 상태 [L-22] 자물쇠가 열린 상태 R-13 -> L-22 -> R-3 한 상태

State Diagram 상태(State)와 상태 천이(Transition)를 유발하는 원인 작용(Action)을 표현

Finite State Machine (유한 상태 기계 - FSM) 시스템을 기술하는 방법, 아래의 요소들을 가짐 유한한 수의 상태 (States) 유한한 수의 외부 입력 (Inputs) 유한한 수의 외부 출력 (Outputs) 모든 상태 천이(State Transition)에 대한 명시적 기술 외부 출력 값(Output Value)에 대한 명시적 기술 주로 State Diagram으로 표현 입력이 상태 천이를 일으킴 출력은 각 상태 또는 각 상태 천이와 연계

The Clock Clock을 이용하여 상태 천이를 일으키는 경우가 자주 있음 각 Clock Cycle의 시작 시점에서 현재 상태 값과 외부 입력 값에 따라 천이 발생 Clock 회로가 항상 필요한 것은 아님. 예를 들어 앞의 자물쇠 예제도 Clock 없이 입력만으로 천이 발생 “1” “0” One Cycle time

유한 상태 기계의 구현 Inputs Outputs 조합 논리 회로 (Combinational Logic Circuit) 출력 및 다음 상태를 결정 정보 저장소 (Storage elements) 상태 정보를 유지 State Machine Inputs Outputs Combinational Logic Circuit Storage Elements Clock

Storage: Master-Slave Flipflop 현재 및 다음 상태를 별도로 저장하기 위한 gated-D latch 쌍 (clock=1)인 1단계 동안, Latch A에 저장되어 있던 상태가 Latch B로 이동하여 현재 상태가 되며 동시에 조합 논리 회로의 입력으로 들어감 (clock=0)인 2단계 동안, 조합 논리 회로에서 계산된 다음 상태를 Latch A에 저장

Storage 각 master-slave flipflop이 하나의 상태 비트를 저장 예: 순서 번호(Sequential) 자물쇠 4개의 상태를 위해 2 비트가 필요 농구 경기 스코어보드 각 점수마다 7 비트, 분의 표시를 위해 5비트, 초의 표시를 위해 6비트, 공 소유 팀 표시를 위해 1비트, 중간 휴식 시간 표시를 위해 1비트, …

DANGER MOVE RIGHT 교통 표지판 예제 다음 순서로 점멸하는 교통 표지판 모든 전구가 꺼진 상태 1, 2번 전구가 켜진 상태 1, 2, 3, 4번 전구가 켜진 상태 1, 2, 3, 4, 5번 전구가 켜진 상태 (전원이 들어와 있는 동안 위 과정을 반복 수행) 3 4 1 5 2 DANGER MOVE RIGHT

교통 표지판 State Diagram Switch on Switch off State bit S1 State bit S0 Outputs 각 Clock 마다 상태 전이

교통 표지판 진리표 출력 (현재 상태(S1, S0)에 따라 결정) 다음 상태: S1’S0’ (현재 상태와 입력에 따라 결정) Switch Lights 1 and 2 Lights 3 and 4 In S1 S0 S1’ S0’ X 1 Light 5 S1 S0 Z Y X 1 Whenever In=0, next state is 00.

Master-slave flipflop 교통 표지판 실현을 위한 논리 회로 Master-slave flipflop

From Logic to Data Path 컴퓨터의 Data Path란 정보 처리를 위해 쓰이는 모든 Logic들을 의미함 다음 Slide의 LC-3의 Data Path 참고 조합 논리 회로 기반 구성 요소 Decoders – 명령어를 제어 신호로 변환 Multiplexers – 입력 및 출력의 선택 ALU (Arithmetic and Logic Unit) – 데이터에 대한 산술 및 논리 연산 순차 논리 회로 기반 구성 요소 State machine – 제어 신호와 데이터 이동의 총괄 조정 Registers and latches – 정보 저장소

LC-3 Data Path Combinational Logic Storage State Machine