'컴퓨터 과학!/Digital Logic'에 해당되는 글 5건

  1. 2005.08.06 Flip-Flop (2)
  2. 2004.10.11 2. Two-Level Combinational Logic (2)
  3. 2004.10.11 1. Introduction
  4. 2004.10.10 Progrmmable and Steering Logic
  5. 2004.10.09 Multi-Level Combinational Logic (3)
내게 플립플랍은 논리회로이다. 그런데, 보니까 끈쌘달을 플립플랍이라고 부르는 것이다. 그래서 찾아봤다.

flip-flop〔│〕 n.
1 《미·구어》 (동향·소신·태도·방침 등의) 급변, 전환
do a flip-flop 급하게 변경하다
2 역공중제비
3 퍼덕퍼덕하는 소리
4 [pl.] 고무 슬리퍼[샌들]
5【전자】 플립플롭 회로(= crcuit) 《교호(交互) 접속식 회로》
━ vi. (~ped;~·ping) 퍼덕퍼덕[덜컥덜컥]하다;역공중제비를 하다;달각달각 움직이다
━ ad. 퍼덕퍼덕하며, 덜컥덜컥하며

<출쳐: 네이버 영어 사전>


sequential logic은 현재 입력+상태로 출력값이 정해진다.
따라서, sequential logic은 회로 내부에 값(상태)들을 기억하기 위한 메모리 소자들을 가지게 되며, 일반적으로 많이 사용되는 메모리 소자가 flip-flop이다.

플립플랍은 1비트의 정보(0또는1)를 저장할 수 있는 메모리 소자이며,
논리 게이트들을 연결하는 방법에 따라 latch, SR/JK/D/T(제어신호와 클럭신호를 입력으로 갖는다.) 플리플랍이 있다.
Posted by 스니
1. Logic Functions and Switches
⊙ Axioms of Boolean Algebra
1. B contains at least two elements, a, b, such that a≠b
2. Closure a,b in B,
(i) a + b in B
(ii) a •b in B
3. Commutative Laws: a,b in B,
(i) a + b = b + a
(ii) a •b = b •a
4. Associative Laws: a,b in B,
(i) (a + b) + c = a + (b + c) = a + b + c
(ii) (a • b) • c = a • (b • c) = a • b • c
5. Identities: 0, 1 in B
(i) a + 0 = a
(ii) a •1 = a
6. Distributive Laws:
(i) a + (b •c) = (a + b) •(a + c)
(ii) a •(b + c) = a • b + a •c
7. Complement:
(i) a + a' = 1
(ii) a •a' = 0

⊙ Thm : truth tabel로 표현되는 Boolean function은 Boolean Algebra로 표현될 수 있다.
⊙ NAND, NOR gate는 AND, OR 보다 더 효과적이라, 많이 사용되고, 어떤 Boolean expression도 NAND, NOR, NOT 만으로 구현될 수 있다. 사실, NOT 역시, NAND나 NOR의 input을 묶어 같이 넣어주면 구현가능하다.
⊙ Literal : Boolean expression 에서 한 문자는 하나의 literal 이며, 이는 나중에 wire 개수에 해당한다. literal이 적을 수록 wire가 적게 필요해서 좋다.
(예) Z = AB'C + A'B + A'BC' + B'C : 3 variables, 10 literals

⊙ XOR, XNOR. (내가 초반에 젤 헷갈렸던 것.)
XOR : X or Y but not both ("inequality", "difference")
XNOR : X and Y are the same ("equality", "coincidence")

XOR and XNOR




2. Gate Logic
Duality : AND ↔ OR, 0s ↔ 1s, literal은 그대로.
참이 expression은, 그 dual도 참이다.
(앞의 Boolean Algebra의 Axiom에서 빠진 내용만 보자.)
Simplification Theorems:
9. X •Y + X •Y' = X 9D. (X + Y) • (X + Y') = X
10. X + X •Y = X 10D. X •(X + Y) = X
11. (X + Y') •Y = X •Y 11D. (X •Y') + Y = X + Y
DeMorgan's Law: AND ≡ NOR, OR ≡ NAND, AND/OR ≡ OR/AND
12. (X + Y + Z + ...)' = X' •Y' •Z' •... 12D. (X •Y •Z •...) ' = X' + Y' + Z' + ...
13. {F(X1,X2,...,Xn,0,1,+, •}' = {F(X1',X2',...,Xn',1,0, •,+)}
Duality:
14. (X + Y + Z + ...) = X •Y •Z •... 14D. (X •Y •Z •...) = X + Y + Z + ...
15. {F(X1,X2,...,Xn,0,1,+, •} = {F(X1,X2,...,Xn,1,0, •,+)}
Theorems for Multiplying and Factoring:
16. (X + Y) •(X' + Z) = X •Z + X' •Y
16D. X •Y + X' •Z = (X + Z) •(X' + Y)

Consensus Theorem:
17. (X •Y) + (Y •Z) + (X' •Z) = X •Y + X' •Z
17D. (X + Y) •(Y + Z) •(X' + Z) = (X + Y) •(X' + Z)



⊙ Truth table은 Boolean function의 unique signature이다. 따라서, expression은 여러가지일지라도, truth table은 하나이다.
► Canonical form : Boolean expression의 표준 형식.
(truth table을 그대로 boolean function으로 나타내면 된다.)
► Sum of Product form = minterm (1:A, 0:A')
F = [F 값이 1인 것들의 product를 sum]
F' = [F 값이 0인 것들의 product를 sum]
► Product of Sum = maxterm (1:A', 0:A)
F = [F 값이 0인 것들의 sum을 product]
F' = [F 값이 1인 것들의 sum을 product]

DeMorgan's Law에 의해





3. Two-Level Simplification
⊙ 여기에서의 핵심은, The Uniting Theorem 이다.
A(B'+B) = A
① Boolean Cubes : 4 demensions 이상은 그리기 힘들다.
② Karnaugh Map Method : ~6 demensions
③ CAD Tools : 6 demensions 이상.
(Quine-McCluskey Method)
④ Esspresso Method ( skip )
Posted by 스니
몇 가지 1장에 있던 내용을 정리해 본다.

Combinational logic : no feedback among inputs and outputs
Sequential logic : inputs and outputs overlap

Synchronous systems : clock에 의해서 signal이 변한다.
Asysnchronous systems : 아무 때나 입력이 주어지면 state 변한다.

◎ Multiple representation of a digital desing
Switches

Truth tables
Boolean Algebra
Gates

Waveforms
Blocks

Behaviors : 이건 안배운거고, 나머진 다 알지? ( '')
Posted by 스니
[시작 전에]
더 적은 components와 wires로 Boolean functions를 구현할 수 있는 좀 더 customizable 하고 복잡한 building block들을 배운다.
Design with structured circuit implementation styles based on programmable array logic and memories.
PALs/PLAs, ROMs : general-purpose digital building blocks 만드는 데 유용하다.
(특정 함수를 구현하는데 customized되고, 더 적은 공간을 차지한다.)
PAL : programmable array logic
PLA : programmable logic array

Design with logic building blocks that are different from traditional logic gates.
Switch Logic
Multiplexers/Selecters and Decoders : 종종 switch 처럼 truth table이나 logic gate보다 Boolean function을 보여주기 더 쉽다.
Tri-State Gates/Open Collector Gates : output이 항상 0이나 1이 아닌 logic들.

▪ Combinational Logic Design Problems
Seven Segment Display Decoder
Process Line Controller
Logical Function Unit
Barrel Shifter


1. Programmable Arrays of Logic Gates
(1) PALs and PLAs
Pre-fabricated building block of many AND/OR gates (or NOR, NAND) "Personalized" by making or breaking connectins among the gates
(*) Product term 을 공유하는 것이라 보면 된다.
F0 = A + B' C'
F1 = A C' + A B
F2 = B' C' + A B
F3 = B' C + A
⇒ A, B'C', AC', AB, B'C' 이렇게 5개의 term만 있으면 된다.

필요 없는 연결은 blow~



간단한 표현 (모든 wire그릴 필요 없다.)



(2) PAL PLA 차이점
⊙ PLA : generalized topologies in AND and OR planes.
즉, AND, OR subarray가 디자이너가 원하는대로 personalized 될 수 있다.
((장점)) product term들 공유

⊙ PAL : implemented by Monolithic Memories.
AND array는 programmable 하지만, product term들간의 연결과 OR gate는 고정되어있다. OR gate로 들어가는 product term input은 2,4,8,16개로 제한되어있다.
((장점)) pre-defined hardwired connection을 사용하기 때문에 빠르다.

(3) Design Examples
◎ BCD-to-Gray-Code Converter
Gray-code : 1 bit 씩만 다른 코드들.
shared product term 없으므로, PAL이 적당하다!

BCD-to-Gray-Code Converter (PAL, AND gate가 총 6개 낭비됨.)



◎ Two-bit Magnitude Comparator
shzred product term 2개 -> PLA 사용.

Two-bit Magnitude Comparator (PLA)

Posted by 스니
[시작 전에 ]
In general, multi-level implementations are more gate efficient than two-level implementations but have worse propagation delay.
Factored form 으로 바꾸면, 훨씬 적은 수의 gate와 wire로 회로를 구성할 수 있다. 그러나, level 이 증가하므로, 그에 따른 delay가 증가한다. (어디에나 있는, trade-off!)


1. Multi-level logic을 NAND/NAND 와 NOR/NOR로 바꿔보자.
DeMorgan's Law와 Pushing Bubbles 이용.
(1) DeMortan's Law
(A + B)' = A'B' -> A + B = (A'B')'
(AB)' = A'+B' -> AB = (A'+B')'

input과 output에 bubble을 적용



AND/OR는 NAND/NAND로의 변환이 쉽다.


여기에서도 알 수 있듯이,
AND/OR 즉, Sum of Product 는 NAND/NAND 로,
OR/AND, Product of Sum 은 NOR/NOR 로 바꾸는 것이 쉽다.
왜냐하면, 이런 변환에서는 두 gate 사이에 buuble이 쑝쑝 들어가기만 하기 때문이다. 그러나, SOP를 NOR/NOR로, POS를 NAND/NAND로 바꾸려면, input 단자와 output 단자에도 bubble을 달아줘야하기 때문이다.

(*) 위의 그림은 two-level 이다. multi-level 에서는 다음을 주의한다.
1. Any internal signal wires that undergo an odd number of inversions must have an additional inverter inserted in the path.
2. NAND-only network로 변환하려면, odd levels에 AND gate를, even levels에 OR gate를 둔다.
3. NOR-only netwrok로 변환하려면, odd levels에 OR gate를, even levels에 AND gate를 둔다.

2. AND-OR-Invert Blok (AOI)
AOI function : AND, OR, Invert의 세 stage. 하나의 circuit block 으로 "packaged"된 multiple gate 이다. (OAI : OR-AND-Invert)

출력에 buuble 있음!


여기에서 stack은 AND의 개수.
AOI 의 장점은, 이 것을 하나의 gate로 count한다는 것!
Even if the use of the AOI blocks represents no savings in circuit area, the transition away from discrete logic offers a considerable advantage in reducing wiring complexity.


3. Multi-level Optimization (called synthesis)
(1) Factor out common sublogic (reduce fan-in, increase gate levels), subject to timing constraints
(2) Map factored form onto library of gates
(3) Minimize number of literals (correlates with number of wires)

(*) factored form : SOP의 연속이다. 즉, AND/OR/AND/OR/....
two-level expression들의 연속이라고도 할 수 있다.


① Decomposition
F = ABC + ABD + A'C'D' + B'C'D' (12 literals)
⇒ F = XY + X'Y' (4 literals)
X = AB
Y = C + D

② Extraction
F = (A+B)CD + E
G = (A+B)E'
H = CDE
⇒ F = XY + E
G = XE'
H = YE
X = A+B
Y = CD (A+B, CD 는 primary divisor 이다.- kernel, cube)

③ Factoring
F = AC + AC + BC + BD + E
⇒F = (A+B)(C+D) +E

④ Substitution
F = A + BC
G = A + B
⇒F = G(A+C)

⑤ Collapsing
F = G(A+C)
= (A+B)(A+C)
= AA + AC + AB + BC
= A + BC


4. Time Response in Combinational Networks
: 좋게 사용될 수도 있고, glitch처럼 부정확한 회로 오작동 유발도 한다.

Gate delay : input -> output 딜레이 시간
Rise time : output 이 low->high voltage로 변화는 시간
Fall time : output 이 high->low voltage로 변하는 시간

glitch : transient(일시적인) output changes.
-> A logic circuit is said to have a hazard if it has the potential for these glitches.

(1) Hazards/Glitches and How to Avoid Them
방법 : 신호가 stable할 때 까지 기다리기. 절~~~대 asynchronous input 사용은 안됨. hazard-free 회로 만들기

(2) Hazard의 종류
Static hazard : 2-level 회로에서. 한 번 glitch
Dynamic hazard : multi-level 회로에서. 두 번 이상 glitch

(3) Hazard free network 만들기 (two-level 에서)
When the initial and final inputs are covered by the sameprime implicant, no glitch is possible. But when the input change spans prime implicants, a glitch can happen.
A strategy for eliminating the hazard is to add redundant prime implicants to guarantee that all single-bit input changes are covered by one such implicant.
① static 1-hazard 제거
F의 SOP (1's 묶기. 1을 A로) 만들어서 여분의 implicant 추가.

② static 0-hazard 제거
F의 POS (0's 묶기. 0을 A로) 만들어서 여분의 implicant 추가.
⇒ ② 를 SOP로 바꾸면 ①과 같은 식이 나온다. 따라서, shorcut으로 다음과 같은 방법을 사용할 수 있다.
static 1-hazard free expression의 complement를 만들어서, 그것이 K-map에서 0's 를 다 cover 하는지 확인한다. (필요하면 add)

(4) Multilevel Networks에서 Static Hazard free 만들기
: transient output function (multi -> 2-level)으로 mapping 한다. 여기에서는 X와 X'는 독립적 변수이다. (XX'=0, X+X'=1 사용 못한다.) XX'는 static 0-hazards를, X+X'는 static 1-hazards를 일으킨다. 따라서, static 1-hazards를 제거할 때는, XX'를 고려할 필요가 없고, static 0-hazards를 제거할 때는 X+X'를 고려할 필요가 없다.
(예) F = ABC + (A+D)(A'+C')
F1 = ABC + AA' + AC' + A'C + C'D (transient output function)
F2 = AC' + A'D + C'D + AB + BD ( AA'는 1-hazards랑 무관, AB가 ABC cover)
F' = (ABC + (A+C)(A'+C'))'
= A'D' + AB'C
F3 = (A+D)(A'+B+C')(B+C'+D) // F'에 B'CD'추가.

F3을 SOP로 바꾸면 F2가 나온다. 따라서, 둘 다 static 0-과 1-hazards에 free 하다.

(5) 결론, static-hazard-free circuits 디자인 방법!
: transient output function이 K-map 에서 인접한 모든 1을 커버하는 term을 가지게 하고, term이 A와 A'를 모두 가질 수는 없게 한다. 즉, AA' 이런 term 은 안된다.
Posted by 스니