디지털 회로 개론 퀴즈 대비
다 아는 내용이구만 .. 하고 수업 안들었다가 큰일 났군요
그냥 알고 넘어감
- 디지털: 유한 자릿수의 순자 나열로 표현됨(digit-al). 이산적임. 동일성이 검증 가능해서 품질 저하 없이 복사가 가능함.
- 아날로그: 연속된 무언가임.. 앰프의 볼륨 다이얼이 얼마나 돌아갔는지 유한 자릿수로 나타낼 수는 없으나 그 만큼 알아서 증폭되는 것 처럼 연속적임. 원리적으로 '동일함'이라는게 불가능하고 압축이랑 조작이 쉽지 않음.
음수 표현
(r은 진법체계, l은 자릿수를 나타냄)
r의 보수란 무엇인가? 숫자 N의 r의 보수를 구한다고 하면.. 공식은 r의_보수(N) = r ** l - N이다.
-9(10)을 2진수에서 r의 보수로 표현하려면(l = 8), r ** l = 100000000(2)이고, r ** l - N = 11110111(2)이다(걍 bit flip하고 하나 더하는거 생각하면 좋을듯?)
arithmetic modulo r**l라고는 하는데 무슨 소리인지
r의 보수 좋은 점: 일단 표현만 잘 해두면 연산할 때 복잡하지 않음! A - B같은거 계산하려면 걍 A + (-B) 하면 됨 그냥 digit level addition만 잘 하면 됨. 아까 9를 2진수로 나타내면 00001001(2)이고 -9는 11110111(2)였는데 걍 이거 두개 더하면 00000000(2) 됨. 당연함 A - A임.. 정확히는 A + (-A)
r의 보수 말고는요
걍 sign magitude를 하기도 함. 00001001에 마이너스 붙히면 LSB만 1로 바꿔서 10001001로 하기도.. 근데 이건 단순한 adder를 통과를 못함 그래서 r의 보수가 좋은거.. adder로 뺄셈까지 할 수 있기
r의 보수는 완벽함 근데 물론 깨지는 때가 있음 overflow라고, 양수 양수 더했는데 음수 나오거나 음수 음수 더했는데 양수 나오면 오버플로우. 나올 수 없는 부호가 나오면 오버플로우라고 보면 될듯.
r-1의 보수도 있음
r ** l - r**(-m) - N이라는 공식으로 표현되긴 하는데 정수에서는 m이 0이라서 사실상 r**l - N - 1인듯. 얘는 2진수에서는 걍 bit flip이세요.
00001001 -> 11110110
연산은 그냥 하면 되는데, 얘는 carry bit를 MSB에 더해주면 됨. 사실 잘 쓸 이유가 없음 연산 구현하기엔 r의 보수가 짱편해서..
(l = 6)
11010 - 00111을 한다고 해보자. 10진수로는 26 - 7이다.
011010 - 000111
011010 + (-000111)
011010 + 111000
011010
+ 111000
---
1010010
Carry bit가 생겼으나 MSB에 더해준다
010011
10진수로 읽으면 19다. 답이 잘 나왔다.
r-1의 보수 좋은 점
- 보수 계산하기 짱편하다(걍 뒤집기)
이거 말곤 딱히 없음.
코드란 무엇인가
코딩이란 예로 부터 입력을 고유한 식별자로 변환하는걸 말했음.. 그걸 인코딩, 식별자를 다시 원본 입력으로 돌려두는걸 디코딩, 왕복에 손실이 생기면 손실, 아니면 무손실이라 하고, 이 규칙을 Codec..이라고 부름. 입력은 message, 식별자는 codeword. Codec은 복원 가능해야 하니까 당연히 1:1함수여야 하고, 아니라면 해시함수..라고 부르는게 맞을 것 같음.
코덱은 코드워드가 노이즈 내성을 가지도록 강건하게 싸매게 만든다. 만약 통신에 혼선이 생겨도 어떤 글자가 달라진건지, 또는 몇글자가 달라진건지를 알 수 있으면 좋음. 인코딩 함수는 어떻게든 버티게 페이로드를 사매고, 디코딩 함수는 처참하게 더러워져도 복원할 수 있게(또는 얼마나 달라졌는지 알 수 있게)하는게 목표.
Detection / Correction
Detection은 Codeword가 얼마나 달라졌는지를 추출하는 일을, Correction은 실제 달라진 글자를 원본으로 정정하는 일을 말함. 올바르게 Detect / Correct할 수 있는 양은 코드북 내 코드워드의 거리에 따라 달라지는데, 코드워드가 너무 촘촘하게 차있다면.. 잡음이 조금만 들어와도 신호를 모조리 섞어놓는다. 그래서 코드북 내 코드워드 사이 거리의 최소값을 dist라고 하면, 최대 dist - 1개 만큼의 오류가 발생했을 때 확신있게 detect할 수 있고, 최대 (dist - 1) / 2개의 오류가 발생했을 때 correct할 수 있다. corr + det = dist - 1이라는데 이건 뭔지 모르겠당.
Parity Check
전체 비트에서 1이 홀수개인지 짝수개인지를 1과 0으로 나타내서 비트열 맨 뒤에 붙힘. 오류가 최대 하나 발생할 수 있다면 det 가능하고, corr는 불가능하다. 그래서 dist가 2임.
해밍
약간 똑똑한 방법이라고 생각함. 일단 패리티 비트가 몇 개 필요한 지 부터 구해야 하는데, 다음의 공식을 만족하면 됨: 2 ** p < d + p + 1. 입력 비트 길이가 4면, 2 ** p >= 4 + p + 1인데, p가 2이면 4 >= 4 + 7라서 안되고, 이면 8 >= 8이라서 딱 맞음. 패리티 비트를 3개 쓸거임.
일단 d + p만큼 공간을 만들어보자
7 6 5 4 3 2 1
---------------------
여기에 2**n 자리마다 패리티 비트를 배치한다
7 6 5 4 3 2 1
---------------------
P3 P2 P1
나머지 자리에는 원래 데이터를 채운다. 1110이였다고 가정하자.
7 6 5 4 3 2 1
---------------------
1 1 1 P3 0 P2 P1
Pn은, 각 자릿수를 2진수로 표현했을 때 n번째 자릿수가 1인 인덱스를 모두 XOR 한 결과가 0이 되도록 맞춘다. 자신을 제외하고 XOR해서 나온 값을 담는다고 생각해도 됨.
001
010
011
100
101
110
111
P3은 여기서 3번째 자리수(4의 자리 수)가 1인 [4, 5, 6, 7]번째 비트를 XOR했을 때 0이 나와야 하는데, 각각의 값은 [P3 1 1 1]이다. 그래서 P3은 1이 됨.
P2는 2의 자리 수가 1인 [2, 3, 6, 7]을 XOR 했을 때 0이 되어야 함. XOR(P2, 0, 1, 1)이 0이 되어야 해서 P2는 0이다. 동일하게 P1을 수행하면 0이다.
M: 1111000
그렇게 인코딩은 잘 했는데 실수로 우주방사선을 맞아서 비트 하나가 틀어졌다. 다행히도 최대 하나만 오류를 내는 착한 우주방사선임이 증명되어 있다.
M': 1011000
다행히도 수신기지는 에잇 백제 다 망했네 하고 도자기를 부수지 않고, 해밍코드를 사용해서 오류를 교정할 수 있을 것이다. 거꾸로 다시 계산해보면 된다.
b4 b3 b2 p3 b1 p2 p1
7 6 5 4 3 2 1
---------------------
1 0 1 1 0 0 0
각 패리티비트를 XOR했을 때 0이 나오도록 보장되어 있다는걸 기억하자.
| 7 6 5 4 3 2 1 |
| ---------------------|
| 1 0 1 1 0 0 0 |
| ---------------------| XOR
p1 | 1 1 0 0 | 0
p2 | 1 0 0 0 | 1
p3 | 1 0 1 1 | 1
p3와 p2가 뭔가 이상하다. p1은 정상이다. p1에는 관여하지 않고 p2와 p3에만 영향을 주는 비트는 6번이다. 6번이 flip되면 모든 XOR 검사 결과가 정상이 된다.
해밍코드 덕분에 다행히도 수신소는 '1111000'이라는 신호를 정상적으로 이해할 수 있었을 것이다.
부울대수
호떡집에 부울..이 날거에요..
Duality
참인 식을 And를 Or로 바꾸고 0과 1을 flip해도 여전히 참이라고 함..
만약에 내가 (x*x) + (!x*!x) = 1을 증명해냈다면, (x + x) * (!x + !x) = 0 또한 참인 것..
증명해보기
x + 1은 왜 1일까?
x + 1
= 1 * (x + 1)
= (x + !x) * (x + 1)
= x + (!x * 1)
= x + !x
= 1
x + 1 = 1임을 증명했으면 duality에 의해 x * 0 = 0임도 자동 증명됨
x + x는 왜 x일까?
x + x
= 1 * (x + x)
= (x + !x) * (x + x)
= x!x + x
= 0 + x
= x
duality에 의해 뭐시기.. xx = x도..
x + xy는 왜 x일까?
x + xy
= (x*1) + xy
= x * (y + 1)
= x * 1
= x
duality에 의해.. x * (x + y) = x 또한 참
드모르간 법칙
!(x + y) = !x*!y라는건데.. 증명을 위해서는 한 변을 flip하고 더해서 1이 됨을 보여주면 된다
(x + y) + !x*!y
= (x + y + !x) * (x + y + !y)
= (y + (x + !x)) * (x + (y + !y))
= (y + 1)(x + 1)
= 1 * 1
= 1
표현을 잘 해야 합니다
Normal Forms
f(w, x, y, z) = !x + w!y + !(wy)z
라는 함수가 있다고 하자.
- Literal은 식에서 각 문자..또는 각 문자의 Complement..쯤으로 보면 되고. 예)
!x,w등 - Product Term은 Literal 그 자체와, Literal들의 곱을 말한다. 예)
!x,w!y등.. - Disjuctive normal form은 Product Term의 합으로 기술된(단항도 가능) 식임. 위
f의 평가식은 Disjuctive Normal Form임.
f(w, x, y, z) = z(x + !y)(w + !x + !y)
반면 이건 Conjuctive Normal Form임.
- Sum term은 Literal들의 합으로 계산된 항(단항도 가능)
- Sum Term의 곱으로 나타내지면 Conjuctive Normal Form입니다.
진리표에서 수식 만들기
i | x y z | f
|----------
0 | 0 0 0 | 0
1 | 0 0 1 | 1
2 | 0 1 0 | 0
3 | 0 1 1 | 1
4 | 1 0 0 | 1
5 | 1 0 1 | 0
6 | 1 1 0 | 0
7 | 1 1 1 | 0
로 되어 있으면 간단하게 Disjusctive Normal Form으로 바꿀 수 있음. f가 1인 조합들만 골라보면
i | x y z
| ------
1 | 0 0 1 | 1
3 | 0 1 1 | 1
4 | 1 0 0 | 1
인데, 각 입력해서만 1을 내는 논리식은 각각 !x!yz, !xyz, x!y!z로 나타낼 수 있다. 걍 이걸 더하면 됨. '정확히 내가 담당하는 패턴일 때만 1'의 합이 된다.
f(x, y, z) = !x!yz + !xyz + x!y!z
또는 i 인덱스만 따와서
f(x, y, z)
= m1 + m3 + m4
= Sum(m(1, 3, 4))
로 표현 가능. 이게 Minterm입니다.
반대로 0인 항들만 모아오면
i | x y z | f
|----------
0 | 0 0 0 | 0
2 | 0 1 0 | 0
5 | 1 0 1 | 0
6 | 1 1 0 | 0
7 | 1 1 1 | 0
개많아서 다 쓸 엄두가 안남
f(x, y, z)
= (x + y + z) * (!x + y + !z) * (x + !y + z) * (!x + !y + z) * (!x + !y + !z)
= M0 * M2 * M5 * M6 * M7
= prod(M(0, 2, 5, 6, 7))
대충 어떤 원리냐.. 각 항들은 '정확히 내가 담당하는 패턴 조합일 때만'0을 뱉고, 나머지는 1을 뱉음. 그래서 모든 Conjunctive Term이 '내 패턴 아닌데..?'라고 하면 모든 비토권자를 통과하고 만장 일치로 1이 되는 것.
Expansion
부울 함수식에서 특정 인자를 기준으로 식을 Expansion할 수 있음.
f(x, y, z) = xy + x'z + xy'
위 식을 x에 대해서 팽창한다면 첫 번째 형태는 합의 형태이다. 일단 x의 입력에 따라 출력이 어떻게 달라지는 지를 보면
f(0, y, z) = z
f(1, y, z) = y + y' = 1
그리고 각 경우를 x의 입력에 매칭해주면
f(x, y, z)
= x * f(1, y, z) + !x * f(0, y, z)
= x + !xz
이게 합의 형태로 나타낸 팽창
곱의 형태도 유사하다
f(x, y, z)
= (!x + f(1, y, z)) * (x + f(0, y, z))
= (!x + 1) * (x + z)
= (1) * (x + z)
= x + z
여기서는 각 Prod Term이 자기가 담당해야 하는 입력 조건이 아닐 때는 걍 passthrough(1)해서 유효항의 평가결과를 사용하도록 한다고 이해했다.
Shannon's Reduction
당연한 말..이지만 짚고 넘어가랜다
xi * f(x1, ..., xi, ...) = xi * f(x1, ..., 1, ...)
xi + f(x1, ..., xi, ...) = xi + f(x1, ..., 0, ...)
!xi * f(x1, ..., xi, ...) = !xi * f(x1, ..., 0, ...)
!xi + f(x1, ..., xi, ...) = !xi + f(x1, ..., 1, ...)
당연한 말을 활용하면 기가 막힌 Simplify를 할 수 있는데
f(w, x, y, z) = x + !x!y + !w!x(w + z)(y + !wz) # 1항에서 x가 1일 때를 처리했으니 나머지는 0일 때로 가정
= x + !y + !w(w + z)(y + !wz) # 2항에서 y가 0일 때를 처리했으니 1로 이후에 계산
= x + !y + !w(w + z)!wz # 중복되는 !w항 제거
= x + !y + !wz(w + z) # 3/1항에서 w가 0, z가 1이여야 이후 항이 의미가 있음
= x + !y + !wz(0 + 1) # 상수항
= x + !y + !wz
기가 막힌다
게이트를 지어봅시다
어떤 입력이 주어지는 지에 따라 유형이 둘로 나뉘는데
- Double Rail: 인자와 인자의 inversion이 모두 입력으로 주어짐
- Single Rail: 인자만 입력으로 주어짐
Universal Gate라는 멋진게 있는데.. 모든 부울 함수를 구현할 수 있다고 알려진 게이트 집합이 있음. AND/NOT/OR만 구현할 수 있는 집합이라면 Universal Gate임. 나이스하게,
Universal NAND
NAND는 자기 자신 딱 하나만 있어도 Universal Gate임..!! NAND만 5천만개 있으면 튜링 완전한 무언가를 위한 프로세서를 만들 수 있는 것..
NAND는 And의 Inversion인데
NAND(A, B) = !(AB) = !A + !B
로 보통 표현한다.
NOT(A)
= NAND(A, A)
= !A + !A = !A
또는 NAND(A, 1)
AND(A, B)
= NAND(NAND(A, B), NAND(A, B))
= !NAND(A, B) + !NAND(A, B)
= !NAND(A, B)
= !(!A+!B)
= AB
OR(A, B)
= NAND(NAND(A, A), NAND(B, B))
= NAND(!A + !A, !B + !B)
= NAND(!A, !B)
= A + B
미쳤다. SK하이닉스 주신 사야겠다.
Universal NOR
NOR도 홀로 Universal함.
NOT(A, B) = !(A + B)
NOT(A)
= NOR(A, A)
= !(A + A)
= !A
OR(A, B)
= NOR(NOR(A, B), NOR(A, B))
= NOR(!(A + B), !(A + B))
= !(!(A + B) + !(A + B))
= !(!(A + B))
= A + B
AND(A, B)
= NOR(NOR(A, A), NOR(B, B))
= NOR(!(A + A), !(B + B))
= NOR(!A, !B)
= !(!A + !B)
= AB
미쳤다. NOT/OR/AND만 할 수 있으면 다 된다.
NAND-Gate 최적화
NAND로 범용 식을 모두 해결해내는 것도 좋지만 .. NAND로 잘 풀 수 있는 식을 만드는 것도 꽤 의미가 있음 ,,
f(w, x, y, z)
= !wz + w!z(x + !y)
= !(
!(!wz) * !(w!z(x + !y))
)
= !(
!(!w * z) * !(w!z(x + !y))
)
= !(
!(!w * z) * !(
w * !z * !(!xy)
)
)
이렇게 AND와 NOT으로.. 벅벅 만들어놓기
f(a, b, c) = (a + b) * c
이 함수에서 Highest Order Operation은 AND임. 이거 그냥 Negation하면 NAND스러워짐.
!f(a, b, c) = !((a + b) * c)
a + b도 NAND스럽게 바꾸려면 드모르간 써주면 된다
!f(a, b, c) = !(!(!a * !b) * c)
마지막 negation도 NAND인 척 하면서 벗겨줄 수 있다
f(a, b, c)
= !(1 * !(!(!a * !b) * c))
= NAND(1, !(!(!a * !b) * c))
= NAND(1, NAND(!(!a * !b), c))
= NAND(1, NAND(NAND(!a, !b), c))
f(a, b, c, d)
= d + !c + !a * b
= !(!d * c * !(!a * b))
= NAND(!d, c, NAND(!a, b))
연결된 페이지 (Inlinks)
연결된 페이지가 없습니다.