순서 다음은 multi-level NAND gate circuit을 만드는 과정이다. 1. circuit을 만들기 위해 function을 simpify한다. 2. 1번의 결과로부터 AND와 OR gate로 된 circuit을 만든다. 단 output은 OR gate여야 한다. 3. 2번에서는 AND와 OR가 항상 번갈아 나와야 하고, 같은 종류의 gate가 연달아 나와서는 안된다. 4. 일단 모든 gate를 NAND로 바꾸고, 연결선은 그대로 둔다. 5. output gate를 level 1이라고 했을 때 홀수 level의 gate에 들어가는 literal을 invert해준다. 이러한 과정을 통해 정말로 multi-level NAND gate circuit이 성립되는지 살펴보려면, 2-level씩 끊어서..

AND-OR Forms AND-OR circuit는 3가지의 form으로 변환이 가능하다. Function은 sum-of-products 형태여야 한다. 먼저 기본적으로 F = A + BC' + B'CD 가 주어졌다고 하자. 이 식은 기본적으로 DeMorgan's law를 이용해서 나머지 3가지로 변환이 가능하다. 이러한 식은 곧바로, 위 그림과 같이 구현이 가능하다. AND-OR으로 부터 NAND-NAND, OR-NAND, NOR-OR 꼴로 변형되었다. 잘 살펴보면 알 수 있듯이, 기본적으로 gate나 gate input의 위치는 그대로지만, gate input은 complement가 들어가기도 하고, gate의 종류도 바뀐다. 어찌됐든, 4가지 모두로 결국 같은 function이 구현된다. OR-AN..

개요 지금까지는 AND, OR gate, inverter만 가지고 digitatl logic design을 했다. 여기서는 NAND와 NOR gate에 대해서 소개하고자 한다. Logic designer는 NAND와 NOR gate를 주로 사용하는데, 일반적으로 속도가 빠르고 AND, OR gate를 쓰는 것에 비해 gate를 적게 쓸 수 있기 때문이다. 게다가. NAND gate로만, 혹은 NOR gate로만 회로를 구성하는 것이 가능하다. (이것은 이후의 포스트에서 설명한다.) NAND Gate Bubble이라고 부르는 작은 동그라미가 gate의 output단에 붙어있다. NAND gate는 AND-NOT gate라고 생각하면 된다. (a)와 (b)는 동일한 결과를 갖는다. 살펴보면, AND oper..

개요 Input과 output 사이에 직렬로 연결되는 gate의 최대 개수는 gate의 level의 개수에 따른다. 따라서, sum-of-products 또는 product-of-sums의 형태로 되어있는 function은 곧, 2-level gate circuit로 귀결된다. 일반적으로, gate가 flip-flop output으로 부터 나오는 case에서는 모든 variable과 그의 complement는 circuit input으로 사용할 수 있다. (flip-flop은 이후에 다루게 됨) 이러한 이유 때문에, inverter는 보통 level로 카운트 하지 않는다. 앞으로는 다음의 용어를 사용할 것이다. 1. AND-OR circuit AND gate가 OR gate 다음에 이어지는 2-level..

정의 Random variable X와 Y가 independent random variable일 필요충분조건은 다음과 같다. 이전에 다룬 independent event의 idea를 두 개의 random variable의 관계를 설명하는 과정에서 다시 도입했다. 서로에게 영향을 끼치지 않는 두 개의 random variable을 independent하다고 생각하면 된다. 어떤 joint PDF 또는 joint PMF가 주어지고 그 때의 두 random variable이 independent 한가를 살펴보려면, 먼저 각각의 marginal PDF 또는 marginal PMF를 구한다음 둘을 곱했을 때, joint PDF 또는 joint PMF와 같은지를 살펴보면 된다. 추가 정리 1 만약 두 random ..

개요 이전의 conditional expected value E[X|Y]의 expected value E[E[X|Y]]은 꽤 흥미로운 결과로 마무리 된다. 우리는 E[E[X|Y]]를 두 단계에 걸쳐 얻을 수 있다. 먼저 g(y) = E[X|Y = y]를 계산하고, derived function에 대한 expected value, 즉 E[g(Y)]를 구하는 것이다. 이 두 단계의 과정을 iterated expectation이라고 한다. (Iterate는 '반복되다'라는 뜻이다.) 정리 1 E[E[X|Y]] = E[X] Iterated expectation의 결과는 곧 X의 expected value와 같다. 증명은 아래와 같이 할 수 있다. 먼저 expected value의 정리에 따라서 위와 같이 쓸 수..