[시작 전에 ]
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')'
여기에서도 알 수 있듯이,
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)
여기에서 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 은 안된다.
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 은 안된다.
