디지털 회로 개론 퀴즈 2 대비

역시 수업을 또 안들음. 퀴즈가 너무 자주 있는거 아니에요? 그래도 이러지 않으면 공부를 안하기에.. 나쁘지 않은 것 같음.

게이트에 관한 간단한 고찰..

우리가 그냥 추상적으로 AND다, OR다, 0이다 1이다 하고 있는데, 도대체 그 0과 1이 물리적으로 무엇이냐. 사실 딱 떨어지는 무언가가 아니라, 값의 범위임. 그럼 대체 무엇의 범위냐?? 전압의 범위입니다. 전압을 0이라고 해석할 범위, 1이라고 해석할 범위가 있음. 0 범위는 V_L(min) ~ V_L(max)로 표현하고, 1 범위는 V_H(min) ~ V_H(max)라고 함. 0과 1이라고 부르는 그게, 전기 단위로 들어가면 Low / High라는 개념으로 이해됨. 전압이 높으면 high고 낮으면 low인거죠 그걸 0과 1로 추상화하고 게이트를 연산자로 추상화해서 미친 짓 하는거고.

이 범위들은 게이트마다 다르고, 게이트도 각 입출력마다 다름. 입력의 LOW/HIGH 해석 범위는 V_IL(min) ~ V_IL(max) 이런 식으로 Input - Low 범위라는 뜻의 IL 첨자를 사용해 나타낸다. Output이면 OL OH이 됨. 일반적으로 게이트 제조사는 스펙시트에 IL(max), IH(min) (이하 '쓸거면 입력 전압 똑바로 잡아라'), 그리고 OL(max), OH(min) (이하 '써주신다면 출력 전압 똑바로 잡겠습니다') 을 명시함.

OL(max) < IL(max) < IH(min) < OH(min)인데, 입력이 출력보다 여유롭다. 만약에 5V급 전압을 사용하는 CMOS 게이트를 A, B, C 순서로 연결해두었다고 하자. 일반적으로는 V_IL가 0 ~ 1.5에 V_OL이 0 ~ 0.4다. 내 뒤에 어떤 게이트가 올지 모르니까, 규격 내 정상 동작을 보장하기 위해 전압을 확실히 낮추는 식이다. HIGH에서는 V_IH가 3.5 ~ 5.0인데 3.8 ~ 5.0이다. 게이트들은 다들 배려심이 좋아서, 흔들리고 애매한 입력을 받아도 출력은 확실하게 보장한다. 착한 게이트들. 이런걸 Noise Margin이라고 하는데, 아래쪽 마진은 Low-level noise margin(V_IL(max) - V_IH(max)), 반대는 High-level noise margin이다.

0과 1이 아무리 추상화 되어도 전기는 전기고 전하는 전하

AND 게이트 다음에 NOT 게이트가 붙어있다고 하자. AND 게이트를 통과한 전하가 NOT 게이트의 밥그릇에 쌓여서 트랜지스터 안의 전하를 당기거나 밀어낼 것이고, NOT 게이트의 출력으로 통하는 길이 바뀔 것이다. 잘 동작 할 것이다. AND 게이트 다음에 NOT 게이트가 백만개 붙어있다고 하자. AND 게이트를 통과한 전하가.. 백만개의 NOT 게이트로 갈라진다. 단위 시간동안 NOT 게이트의 밥그릇에 쌓이는 전하량이 백만분의일이 될 것이고, NOT 게이트가 전하 흐름에 비토권을 행사하는데에는 백만배의 시간이 소요될 것이다(물론 비유가 그렇다는 것이고.. NOT의 사양 및 구현에 따라 다를 것.). 한 출력에 여러 게이트가 연결되어서 작동에 오랜 시간이 걸리거나 오작동하는 현상을 Fan-out이라고 하고, 게이트 제조사들은 감당 가능한 팬아웃(이 게이트가 입력을 다른 게이트랑 얼마나 나눠먹을 수 있나요? 이 게이트의 출력을 다른 게이트가 얼마나 나눠먹을 수 있나요?)을 명시해두고 있음. 팬아웃을 덜고 싶으면 Buffer(이름부터가 완충재)같은 증폭기를 쓸 수 있음요.

전압은 퀀텀점프하지 않음.

전자는 원자모형의 궤도 껍질에서 다른 껍질에서 퀀텀점프하지만, 아쉽게도 전압은 그러지 못한다(거시적 관점에서 본다 우리는 사람이니까.). 입력 전압도 0에서 1로 뿅!하고 변하는게 아니라 서서히 변하며, 서서히 변한 입력은 게이트를 또 서서히 작동시키고, 서서히 작동한 게이트는 또 출력 전압을 서서히 바꾸고.. 느리다. 게이트가 여러개 붙을 수록 더 느려진다. 이 현상을 Propagation Delays라고 한다. 특히 게이트는 출력이 바뀔 때 바뀌는 방향에 따라서 지연 시간이 달라지기도 한다. 올라오는 지연시간을 t_pLH(Time for Propagation from Low to High)라고 하고, 내려가는 지연시간을 t_pHL라고 한다. 일반적으로는 둘이 달라서, 둘을 평균내서 t_pd(Time for Progagation Delay)라고 한다.

게이트도 전자제품이야

당연하다. 전기를 쓰고, Power Dissipation이라고 부른다. 당연히 전기 사용량은 적으면 좋다. 근데 보통 전기 사용량이 적으면 Propagation Delay가 늘어 난다. 그래서 둘중 타협을 하게 되는데, 일반적인 효율성을 따질 때는 둘을 곱해서 말 한다. Delay랑 Power를 곱해서 걍 계산하면 되고 이름도 단순하게 Delay-Power Product라고 한다. 너무 일반적인 이름이 아닌가 싶을 정도.

Synthesis Procedure

쉽게 말하면 문제를 논리식으로 푸는거.

예시: 숫자의 홀짝을 판단하자!

고상하게 쓰면 이렇고요

f(x in (N & [0, 9])) -> { 0, 1 }

f(x) =
  1 if x in { 1, 3, 5, 7, 9 }
  0 otherwise

우악스럽게 쓰면 이렇다

(a, b, c, d, R are boolean value)

f(a, b, c, d) -> R

N | a b c d | R
---------------
0 | 0 0 0 0 | 0
1 | 0 0 0 1 | 1
2 | 0 0 1 0 | 0
3 | 0 0 1 1 | 1
4 | 0 1 0 0 | 0
5 | 0 1 0 1 | 1
6 | 0 1 1 0 | 0
7 | 0 1 1 1 | 1
8 | 1 0 0 0 | 0
9 | 1 0 0 1 | 1

f(?, ?, ?, d) -> d
R = d

이렇게 우악스럽게 보여주는게 Systnesis Procedure세요.

예시2: 9의 보수를 구하라!

잠깐 (N-1)의 보수가 뭐였죠?

(진수 ** 길이) - 입력값

이죠. 1에서 9의 보수를 구하면 10 - 1 = 9입니다. 입력값을 10에서 빼기..라는 문제임 이 상황에서는.

우아하게 쓰면

f(x in (N & [0, 9])) -> R in (N & [0, 9])
f(x) = 9 - n

우악스럽게 쓰면

(a, b, c, d, o1, o2, o3, o4 are boolean value)

f(a, b, c, d) -> [w x y z]

N | a b c d | R | w x y z
-------------------------
0 | 0 0 0 0 | 9 | 1 0 0 1
1 | 0 0 0 1 | 8 | 1 0 0 0
2 | 0 0 1 0 | 7 | 0 1 1 1
3 | 0 0 1 1 | 6 | 0 1 1 0
4 | 0 1 0 0 | 5 | 0 1 0 1
5 | 0 1 0 1 | 4 | 0 1 0 0
6 | 0 1 1 0 | 3 | 0 0 1 1
7 | 0 1 1 1 | 2 | 0 0 1 0
8 | 1 0 0 0 | 1 | 0 0 0 1
9 | 1 0 0 1 | 0 | 0 0 0 0

w의 Kmap

    | a'b' | a b' | a b  | a'b  |
    -----------------------------
c'd'|  1   |      |      |      |
c d'|      |      |      |      |
c d |      |      |      |      |
c'd |  1   |      |      |      |

w = a'b'c'

x의 Kmap

    | a'b' | a b' | a b  | a'b  |
    -----------------------------
c'd'|      |      |      |  1   |
c d'|  1   |      |      |      |
c d |  1   |      |      |      |
c'd |      |      |      |  1   |

x = a'b'c + a'bc'

y의 Kmap

    | a'b' | a b' | a b  | a'b  |
    -----------------------------
c'd'|      |      |      |      |
c d'|  1   |      |      |  1   |
c d |  1   |      |      |  1   |
c'd |      |      |      |      |

y = a'c

z는 너무 생긴게 'd.

w = a'b'c'
x = a'b'c + a'bc'
y = a'c
z = 'd

핵심은 입출력을 모두 0과 1로 바라보고 게이트로 표현하는 것. '9에서 자연수 빼기'같은 게이트는 기본 게이트에 없잖아여~

수식을 단순화 해보자

논리식에서 중요한것들.. 비용(설계? 유지보수? 제조?), 신뢰성(SPoF 줄이기? 부품이 모두 신뢰할만 한지?), 반응속도(입력 변화에 얼마나 빠르게 출력이 따라오는지?).. 반응속도는 게이트의 조합 깊이와 크게 관련있는데, 사실 모든 논리식은 double rail 입력이라고 할 때 최대 2-depth면 모두 표현할 수 있다고 하긴 하네요(왜지)

비용의 예시:

• Number of gates: (하나 이상의 Literal을 갖고 있는 항의 갯수) + 1
• Number of gate inputs: (수식 내 Literal의 갯수) + (하나 이상의 Literal을 포함하는 항의 수)

위 두 비용이 중요하다면 수식을 단순화하는 것이 좋음. 걍 기본적인 것 부터

x + 'x = 1

x'x = 0

x + x = 0

xx = x

다 아시는거죠? 그 다음은 Implication.

f_1(x, y, z) = xy + yz
f_2(x, y, z) = xy + yz + 'xz

이런 식이 있으면.. f_1이 참일 때 자동으로 f_2도 참입니다. 당연합니다.. 이 당연한게 Implication임. 물론 곱연산에서도 적용 돼요.

그 다음은 Subsumes. Implcation이랑 비슷한가 하면서도 다른데요

x'y'z

얘는 (x, 'y, 'z) 세개의 Literal로 구성되어 있죠. 이 Literal들을 조합해서 또 다른 Term을 만들 수 있음.

x'y
'y'z
x + 'y
x + 'y + 'z
x + 'z

뭐 이런 것들.. 이걸 두고 "x'y'z subsumes x + 'z"이런 식으로 말함. 난 개인적으로 '낳았다'라고 표현하고 싶은데 좀 이상한 듯.

만약에 Product Term T1이 Sum Term T2를 Subsume하면, T1 -> T2가 Imply됨. 당연함. abc가 참이면 a + b도 참이겠죠? 반대도 있는데, Sum Term T1이 Prod Term T2를 Subsume하면 T2 -> T1가 성립함. ab가 참이면 a + b + c도 참입니당. Prod-Prod, Sum-Sum간도 알아서 잘 생각해보시길. 그래서 이걸 활용하면 재밌는걸 할 수 있는데

(x + y)(x + y + z)

후항이 전항을 Subsume하죠(낳았죠)? 그래서 x + y -> x + y + z가 돼서 후항이 사라짐. 걍 x + y로 정리됨. 못믿겠으면 진리표 그려보삼. 당연히 곱항에서도 되겠죠?

xy + xyz

또 후항이 전항을 낳았음. xyz -> xy가 성립해서, 이번엔 후항만 살아남음. xyz가 되. 이걸 활용하면 재밌는걸 할 수 있는데,

f(xyz) -> 1 if xyz in (000, 001, 010, 011, 101) otherwise 0

이라는 함수가 있는데, 어떤 학부생이 이걸 이렇게 표현했다고 해보자.

f = 'x + x'yz

틀리진 않은 것 같다. 근데 이 식에 'yz를 더해보면 재밌어진다. 'yz = 1일 때도 f를 1로 만드는 유효한 입력이기에 그냥 더해도 된다. 달라지는건 없음.

'x + x'yz + 'yz
'x + (x'yz + 'yz)
'x + 'yz

복잡도가 줄었다. Cost가 낮아졌다. 어찌 이게 가능했을까? 'yz가 f를 Implicate하기에 Sum Term에 잉여항으로 끼워넣을 수 있었다. 근데 마침 x'yz가 subsume하는 prod term이였어서 absorption law로 축약이 가능했다. 그럼 여기서 더 축약할 수 있을까? 이제 남아있는 항은 'x, 'yz 두가지인데, 둘의 subsumed prod term중 f를 implicate할 식은 아쉽게도 없다. 사실 아쉽게도가 아니다. 이렇게 끝까지 남은 항을 'Prime Implicant'라고 하고, 이 과정을 Irredundant DNF라고 함. CNF form도 동일하게 보면 되는데.. 피곤해서 안하겠음.

사실 이걸 하기 좋은 수단이 있는데

카네글자(카르노맵)

진짜 나는 인생에서 카르노맵을 몇 번째 배우고 있는건지 모르겠다 적어도 세번째 같은데 진짜 9변수짜리 갖다줘도 풀 수 있을 것 같으니까 걍 예제만 몇 개 보면

카르노맵 1

f(x, y, z) = sum(min(0 2 4 5 6))

   | 'y'z | 'yz | yz | y'z
'x | 1    |     |    | 1
 x | 1    | 1   |    | 1

f(x, y, z) = 'z + x'y

카르노맵 2

f(w, x, y, z) = sum(min(0 1 5 7 8 10 14 15))

     | 'y'z | 'y z |  y z |  y'z |
'w'x | 1    | 1    |      |      |
'w x |      | 1    |  1   |      |
 w x |      |      |  1   |  1   |
 w'x | 1    |      |      |  1   |

f = 'w'x'y + 'wxz + wxy + w'x'z
f = 'x'y'z + 'w'yz + xyz + wy'z

어떻게 이런 일이 일어났을까?? EPI라는 개념이 필요한데, 지도에서 각 1항들은 자신이 소속될 수 있는 우선되는 큰 영역을 가지고 그걸 EPI라고 부른다. 근데 위 식의 경우에는 모든 1항들이 정확히 넓이가 2인 영역에 속하게 되어서, 우선되는 Prime Implicant가 없음. 그래서 여러 단순화 결과를 볼 수 있게 된 것. EPI가 존재 한다면 먼저 소모하고 나머지를 보면 됨요.

연결된 페이지 (Inlinks)

연결된 페이지가 없습니다.