skyjump's blog

combinational circuit
input, logic gates, output으로 구성되어 있다.

analysis
회로도 분석해서 logic function, truth table 구하기

디자인
combinational circuit 만드는 절차.
1. 입력갯수, 출력갯수 몇개인지 정확히 파악한다.
2. truth table을 만든다.
3.boolean functions를 간략화한다. (카르노맵 이용)
4.그린다.

Half adder
비트2개 더하기. 입력 2개, 출력 2개. 출력은 합(S)과 자리올림값(C).
S = x'y + xy'
C = xy

Full adder
비트3개 더하기. 입력 3개. 출력 2개(S,C).
입력 2개는 더하는 수, 나머지 하나는 이전 자리수에서 발생한 carry로 본다.
Half adder 2개와 OR gate 하나로 만들 수 있다.

Binary adder
Full adder로 n-bit 끼리 더하기를 할 수 있다.
각 자리의 Carry값들이 동시에 나오지 않고 낮은 자리부터 전파되어서 연속으로 나온다.
Carry Lookahead Generator : 케리들이 같이 나오게 하는 방법.

Binary subtractor
A-B면 B의 각 bit에 보수를 해서 더해주고 처음 carry 값 C0에 1을 넣어준다.

overflow
binary adder, subtractor에서 overflow가 발생할 수 있다. 4bit adder subtractor가 있을 때 더하는 수가 unsigned면 C4 가 1이면 overflow. signed면 C3나 C4중 둘 중하나가 1이면 overflow다. signed일때 C3가 1이 될 경우는 큰 양수 2개(A+B)를 더했을 때 sign bit 전의 bit 합(A3+B3)이 2가 넘어 자리 올림이 발생한다. 이 때 C3가 1이 되어 sign bit로 가고 sign bit가 1이 되어 버린다. 그리고 C4가 1이 되는 경우는 큰 음수 2개를 더했을 때 sign bit값이 더해져서 sign bit가 0이 되어 버린다.

BCD Adder
binary sum과 BCD Sum을 관찰해보면 10부터 BCD값이 binary 값에 6을 더한 값으로 표시된다. 이를 회로로 나타내기 위해 10이상을 나타내는 규칙을 찾아 6을 더하는 회로를 만들면 된다.

Binary multiplier
보통 손으로 곱하기 하는 것과 똑같은 방식. K bit 곱하기 J bit는 J*K개의 AND gate와 J-1개의 K-bit adder로 그릴 수 있다. 결과는 J+K bit이다.

Magnitude comparator
A, B의 크기 비교.
A, B가 같으면 각 비트가 모두 같은 것이다. 따라서 xi = (AiBi + Ai'Bi') 구해서 모두 AND 게이트에 연결시키면 된다.
A >B이면 가장 큰 자리부터 A가 1이고 B가 0 인지 비교하면 된다. 4자리면 A3B3' + x3A2B2' + x3x2A1B1' + x3x2x1A0B0' (xi의 의미는 '같고'이다.)
A<B도 A>B이랑 비슷한 방식으로 하면 된다.

Decoders
n bit의 입력을 통해서 2^n 개의 결과 중 하나만 1이 나오도록 하는 회로. 여러개 입력하고 출력은 하나만 1이 나온다.
n-to-2^n line decoder라고 적는다.

decorder로 boolean function 표현할 수 있다.
boolean function은 sum of minterms로 표시할 수 있다. minterm들은 decorder의 출력으로 표현할 수 있다. 그리고 logical sum역할을 하는 외부 OR gate가 있으면 minterms의 합을 표현할 수 있다.

Encoders
디코더의 반대. 입력 2^n개, 출력 n개.
입력 2^n개 중에 하나가 1이 된다. 
OR gates로 출력 n을 표현할 수 있다.

priority encoder
2개 이상의 input이 동시에 1일 때 가장 높은 우선순위의 input이 우선권을 가지는 encoder.

Multiplexers
input 중에 하나를 선택하고 그 값이 output에 연결되는 것.
입력라인, OR gate 없애면 decoder랑 똑같다.
따라서 multiplexer로도 boolean function 만들 수 있다.
효과적으로 boolean function을 표현할 수 있는 방법: n variable boolean function을 n-1 selection input을 가지는 멀티플렉서로 표현 할 수 있다.

 

카르노맵 - Boolean function을 최소화 하기 위해 사용하는 방식
카르노맵 만드는 법
http://blog.naver.com/PostView.nhn?blogId=nsesibong&logNo=60028521258&viewDate=&currentPage=1&listtype=0

카르노맵 특징
2의 지수승으로 묶는다.
묶는 방법에 따라 식이 여러개 나온다.
서로 인접하도록 만든다. ( 00, 01, 10, 11 이런식으로 비트가 하나만 바뀌도록)
항이 4개일때는 칸이 16X16인 맵이 2개 나온다. 두개를 따로 묶는 것으로 끝나지 않고 두 개가 겹쳤을 때 인접한지도 고려한다.

카르노맵을 Sum of product 방식으로 나타내었는데
product of sum의 방식으로 나타내려면 맵에서 0인 것을 묶으면 F'이 구해지고 이것을 complement를 해준다.

Don't care conditions
0이 되던지 1이 되던지 상관없는 minterms. 예를 들면 4bit binary code에서 0에서 9까지 표현하려고 하면 16개 중에서 6개는 필요가 없다. 얘네들을 이용해서 boolean function을 더 최소화할 수 있다. 1이라고 생각해도 되고 0이라고 생각해도 된다. 어차피 얘네들 output은 안쓰이니까 말이다. 최소화할 때 박스 더 크게 만들 수 있도록 도와준다.

AND, OR 회로는 NAND, NOR 회로로 바꿀 수 있다.
실제로 NAND와 NOR로 전기 컴포넌트를 더 만들기 쉽고, IC digital logic families의 basic gate이다.

NAND-AND 회로는 AND-NOR 회로로 서로 바꿀 수 있고
NOR-OR 회로는 OR-NAND 회로로 서로 바꿀 수 있다.

Exclusive-or function
Odd function이다. 즉, 1인 항이 홀수개이면 함수값이 1이다.
카르노맵을 그려보면 1의 갯수가 홀수개인 minterms만 1이 됨을 볼 수 있다.
이런 성질은 에러체크에 쓰인다. 전송중에 데이터가 손상되었다던지 해서 에러가 발생했을 경우 전송 전 패리티비트(1의 갯수가 홀수냐 짝수냐에 따라 값이 달라지는비트, 홀수패리티비트일때는 1의 갯수가 홀수일 때 1이다.)가 전송 후 패리티비트와 같은지 비교를 통해 에러의 발생여부를 알 수 있다. 
 

Duality
Boolean Algebra의 중요한 속성.
하나를 보여주면 다른 하나도 보여줄 수 있다.
예를 들면 헌팅턴의 공준, 공리에서  x+y = y+x 임을 보이면 x*y = y*x도 성립한다.
즉 binary operators( +, * )나 identity elements(+일 때는 0, *일 때 1)을 바꿈으로써 하나가 성립하면 다른 하나도 성립한다.

Boolean function
Ex) F1 = x + y'z
Truth tables로 값을 찾을 수 있다.
Logic gate로 구현할 수 있다.

Complement of Function.
F'은 F의 값이 0인 경우가 1이다.
드모르간 (DeMorgan) 법칙을 이용해 구할 수 있다.
또는 dual을 구하고 각 문자에 complement를 하면 된다.

Minterms and Maxterms

그림에서 보면 minterms 와 maxterms는 complement 관계에 있다.

Truth table로 부터 함수의 min terms를 구할 수 있다.
그리고 함수 F의 함수값이 0이 되는 부분을 이용하여 F'의 min terms도 구할 수 있고
이 함수를 다시 complement하면 본래의 F로 돌아가지만 max terms으로 표현된다.
따라서 min term을 알면 max terms도 안다. (complement 관계!)

Boolean expressions
52쪽 참고

Digital logic gate
54쪽 참고
 

10진수 소수를 n진수로 변환하는 문제 
http://sunkyu.tistory.com/71338
왜 이렇게 되는지 이해가 안되었는데 시프트 연산을 생각해보면 이해가 되었다.
2진법으로 바꿀때 2로 나눈다는 것은 오른쪽 시프트 연산이다. 이진수의 맨 끝자리를 버리겠단 뜻이다. 그래서 2로 나누었을 때 발생하는 나머지는 2진수로 바꾸었을 때 2^0 자리의 수가 되겠다. 계속 2로 나눠주면서 그 다음 자리 수를 구할 수 있다.
소수일 때는 2를 곱해주는데 이는 왼쪽 시프트 연산이다. 이진수의 맨 앞자리를 버린다. 즉 소수에 2를 곱했을 때 소수점을 넘어가는 숫자가 2^-1의 자리의 수가 된다. 계속 2를 곱해주면 그 다음 자리 숫자를 구할 수 있다.


2의 보수에 대한 알기쉬운 설명
http://maanu.egloos.com/3356542

r-1의 보수와 r의 보수의 차이
r-1의 보수는 0을 표현 하는 방법이 2개 있다. +0, -0
r의 보수는 0을 표현하는 방법이 1개. 0
예를 들면 r이 10이고 자리수가 2개일 때(n=2) +0은 0이고, -0은 99-0 = 99이다.

보수를 이용한 빼기 연산
M - N을 구한다고 할 때

N을 r의 보수로 바꿔주고 더해주면
M + (r^n - N) = M - N + r^n

i) M>=N일 경우
r^n (케리)가 있기 때문에 버리면 M - N 만 남는다.

ii) M<N일 경우
결과는 -(N-M)이 나와야 겠다.
M-N + r^n을 r^n - (N-M) 으로 바꿀 수 있고 이는 N-M의 r의 보수이다.
이 수를 다시 r의 보수를 취하면 N-M을 구할 수 있다. r^n - (r^n - (N-M)) = N-M
이 값에 '-'를 붙여주면 값이 구해진다. -(N-M)

Signed binary numbers가 필요한 이유
컴퓨터에서 -를 표현해야 될 때 컴퓨터는 모든 것을 0과 1로 표현해야 하기 때문에 부호를 나타내는 비트가 하나 필요하다.
그래서 0이면 양수 1이면 음수 이렇게 표현할 수 있다.


코드
소통하기 위해서 사용. BCD, Excess-3, Gray, ASCII 등이 있음.
Gray가 유용할 때는 디지털에서 0111에서 1000으로 바뀔 때 비트가 4개가 바뀌기 때문에 에러가 발생할 가능성이 높다. 그래서 비트를 하나씩만 바꾸면서 그런 경우를 최소화할 수 있다.
코드에 대한 재미있는 이야기 
http://maanu.egloos.com/3262125