singun11

Left Shifter Left Shifter 1비트 왼쪽 시프트: Multiplying by 2 바로 연결하거나, MUX로 노가다하듯이 만들거나 Right Shifter 1비트 오르쪽 시프트: Deviding by 2 바로 연결하거나, MUX로 노가다하듯이 만들거나 Multifunction shifter 시프트 없이 그대로 출력, 왼쪽, 오른쪽 → 3가지의 출력 Barrel Shifter 주어진 비트수만큼 시프트 연산을 수행하는 회로 → MUX의 크기를 늘리면 되지 않을까? → 너무 복잡해진다. 선이 너무 많아진다. → 요 Barrel Shifter면 된다! 큰 순서대로 2^N, 2^N-1, ... 4, 2,1 만큼 shift 시켜주는 쉬프터들을 연결해논다. 그리고나서, 옮기려는 숫자(이진수) 자리를 ..

Code Converters 여러 코드 사이에 변환을 수행하는 회로 Ex) BCD-to-7 Segment Display (BCD = Binary Coded Decimal) BCD-to-7 Segment Display Multiple Ouput 회로이다. → Global Optimization vs Local Optimization Equality Comparator 두 입력이 같은지 다른지 비교하는 비교기 N-bit equality Comparator EX) 4-bit equality Comparator a3 = b3, a2 = b2, a1 = b1, a0 = b0 AND, OR, NOT 으로 하면 굉장히 길어짐. XNOR를 활용하자 eq = (a3 XNOR b3) * (a2 XNOR b2) * (a1 ..

Shannon Expansion Theorem MUX를 잘 활용하기 위해서는 Selection Bit를 잘 골라내야 한다. 이걸 또 섀넌이 MUX를 쓸 수 있는 회로로 바꾸기 위해 selection 신호 분리해내기 복잡한 회로를 간단하게 구현하는 방법 Boolean logic function F를 Boolean variable X에 대해 확장하기 이 이론은 MUX를 활용하기 위해서 특정 변수를 셀렉션 비트로 뽑아내기 위한 확장 이론이다. 어떠한 변수에 대해서도 확장이 가능하고 복수의 변수에 대해서도 확장이 가능하다. 솔직히 이 이론은 예시를 봐야 한다. F(a,b,c) = a'bc + ab'c + abc' + abc a에 대해 뽑아내보자. a = 0일때 F = 1bc + 0b'c + 0bc' + 0bc ..

조합 논리 회로 vs 순차 논리 회로 버튼 비교법 버튼를 누르면 모조건 벨이 울린다. → 조합논리회로 버튼을 누르면, 현재 상태에 따라 다르게 벨이 울릴 수도 안 울릴 수도 있다. → 숫차 논리 회로 조합 논리 회로 출력은 현재 입력에 의해서만 결정된다. 메모리가 없다. 즉, 이전 상태를 저장/기억할 방법이 없다. 순차 논리 회로 출력은 현재 입력과 현재 상태(이전의 입력/출력에 의해 결정 된 상태)에 의해 결정된다. 메모리가 필요하다. 왜? 이전의 입력/출력을 기억해야 하니깐 (Multiplexer)MUX N개의 입력 중에서 하나의 출력으로 나갈 입력을 선택할 수 있게 해주는 것 (선택을 위해서 별도의 이진 입력이 있다!) → 가장 중요한 것은 선택에 관련된 것이다라는 것 2 Bit INPUT MUX ..

Half Adder (회로로 덧셈을 하자!) 오직 두 비트의 덧셈을 위한 회로 Addition of Multi-Bit Unsigned Numbers 여러 비트의 숫자를 더해볼까? 진리표를 보면... 너무끔찍하고, 이를 직접적으로 게이트로 나타내면 지수적으로 증가하는 게이트 개수를 볼 수 있다. → 아, 그러면 Half Adder를 계속 붙여서 여러 비트의 덧셈을 구현하자! → 근데, 여러개를 붙이려 하니, Carry가 발생하고, Half Adder로만은 구현이 안된다. Full Adder Carry를 포함해, 3개의 비트의 덧셈을 구현할 수 있다. - Sum = x XOR y XOR ci - Carry = xy + xci + yci 여기서 추가적으로 알 수 있는 내용! → XOR에 여러 개의 입력이 들어..

6-3차시 Tabular Method 아무튼, 요걸 배우는 이유? 카르노 맵은 scalability 문제가 발생하고, 이를 해결할 방법이 필요함. → Tabular Method: Quine-McCluskey!! Tabular Method: Quine-McCluskey 50년대 중반에 발표됨. K-map의 Scalability 문제를 해결한 논리식의 최적화 기법 K-map의 최적화 원리를 이용한 Algorithmic한 체계적 방법 주로 적용하는 핵심 규칙 Uniting theorem ab + ab' = a(b+b') = a*1 = a "참과 거짓이 둘다 포함되어있는 변수를 지운다"라고 생각하면 편하다. Algorithm 단계 모든 prime implicants를 찾는다. 출력이 1인 minterm과 don..

카르노 맵에서 특수한 경우 Don't care 해당 입력에 대한 출력은 시스템 구현에 전혀 영향이 없음 해당 입력은 벌어지지 않을 일이라 가정하는 것 최적화에 활용할 수 있다. K-map에서는 'X' 로 표기한다. 이건 0 일수도, 1일수도 있다. 그때 그때, The Fewest, The Largest를 만족할 수 있게 사용하면 된다! 최적화에 유리한 방향으로 0 혹은 1로 가정하라는 이야기 Multiple Output Circuits 여러 출력이 필요한 회로 MO 회로를 최적화하는 기본 원리? → 게이트 수를 줄여라!!! 대표적인 예시: Seven Segment Display 다중 출력 K-map 에서 비용 최적화 로컬 최적화 vs 글로벌 최적화 로컬 최적화: 각각의 출력에 최적화함. 글로벌 최적화: ..

카르노 맵 최적화를 체계적으로 배우기 용어부터 정리하자 Literal: 변수가 나타나는 형태 Implicant 리터럴의 곱의 형태 카르노맵에서는 써클로 표현된다. Prime Implicant 더 이상 확장할 수 없는 Implicant 더 이상 확장할 수 없는 Circle(카르노 맵에서!) Essential Prime Implicant 해당 함수를 만족시키기 위해 필요한 Prime Implicant 모든 EPI는 꼭 포함된다. Non-EPI는 포함될 수도, 안 될 수도 있다. 근본은 The Fewst, The Largest 카르노맵에서는, 단 하나의 써클에만 포함되는 1이 있는 PI가 EPI이다. Cover F = 1을 만족시키는 모든 써클의 집합 해당 함수를 구현할 수 있는 방법 Cover는 여러개 있을..

https://www.youtube.com/watch?v=7ecVgs6B62A 공부는 하기 싫어서 유튜브 보고 있었는데, 어느 순간 AND, XOR 게이트부터 반가산기, 가산기를 다루는 걸 보게 되었다..어라라? 이걸 보고 나면, https://www.acmicpc.net/problem/18826 18826번: A+B (MC) 입력은 레버를, 출력은 레드스톤 램프를 통해 이루어집니다. 이들 블록을 포함하여, 모든 블록은 (0, 0, 0)과 (511, 255, 511)를 꼭짓점으로 하는 직육면체 안에 있어야 합니다. 여러분은 월드의 r.0.0.mc www.acmicpc.net 요 문제 풀 수 있음 ^^7 이미 부분점수만 받고 안 풀기로 결심한 문제긴 하지만..(실제로 저 영상에 나온 방법으로는 부분점수밖에..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지 www.acmicpc.net 간단한 DFS 문제, 배열 갱신 타이밍만 잘 잡으면 됨. https://www.acmicpc.net/problem/1806 1806번: 부분..