정규분포 정규 분포는 가우시안 분포라고도 불리는 유명한 분포입니다. 어떤 확률 변수 $X$가 평균이 $\mu$이고, 분산이 $\sigma^2$인 정규 분포를 따른다면 다음과 같이 나타냅니다. $X \sim N(\mu, \sigma^2) \ \ (-\infty < \mu < \infty, \ \sigma^2 \ge 0)$ 정규분포의 성질들 $X \sim N(\mu, \sigma^2)$ 라고 할때 $X$의 p.d.f. $f(x) = \frac{1}{\sqrt{2\pi} \sigma} e^{- \frac{(x-\mu)^2}{2\sigma^2}}$ $X$의 m.g.f. $\psi(t) = e^{\mu t + \frac{1}{2} \sigma^2 t^2}$ m.g.f를 통해 $E(X) = \mu$ 이고, $Var..

밀리머신 밀리머신은 출력이 현재 상태와 입력에 모두 관련되는 경우입니다. 현재 상태가 무엇이고, 그때의 특정 입력이 무엇이냐에 따라 출력이 화살표에 표시됩니다. 직렬 덧셈기 회로 직렬 덧셈기는 두개의 n비트 2진수 $X$, $Y$를 더하는 회로입니다. 병렬 덧셈기와의 차이점은 입력이 순차적으로 들어오고, 그에 따른 출력도 순차적으로 나간다는 점입니다. 상태는 덧셈의 결과로 생성되는 1비트의 캐리 값으로 잡으면, 필요한 FF의 개수는 1개임을 알 수 있습니다. 또한 덧셈을 할 수 있는 Full Adder와 함께 구성해보겠습니다. 우선 진리표 먼저 구성해보겠습니다. 상태를 다음과 같이 구성하고, 상태도를 그려보겠습니다. $S_0 : C_{i+1} = 0$ $S_1 : C_{i+1} = 1$ 이에 따른 다음 ..

상태도 상태도(State Diagram)는 다음 요소를 이용하여 그래프의 형태로 나타냅니다. 원은 상태를 나타냅니다. 화살표는 현재 상태에서 다음 상태로의 전이(Transition)를 의미합니다. 각 화살표위의 라벨은 상태 전이를 일으키는 입력을 의미합니다. 무어머신 무어머신의 상태도는 다음의 특징이 있습니다. 원 내부의 라벨에는 "상태 / 출력" 형태로 표시됩니다. 화살표에는 입력이 표시됩니다. 무어머신은 상태(State)만 출력하며(즉, 최종 출력에는 사용자의 입력은 관여하지 않습니다.) 입력은 상태만 바꿀 뿐, 출력에 영향을 주지 않습니다. 입력에 따라 상태가 바뀌면, 최종 출력에 관여하니까 입력도 상관있는거 아니야? 아예 상관 없다고 할 수는 없지만, 입력이 출력에 직접적으로 관여하지 않는것이 무..

카운터 일정한 순서의 값을 순환하는 회로를 카운터라고 합니다. Shift Reg의 출력의 반전된 출력을 reg의 첫번째 FF과 피드백으로 연결해주면 존슨 카운터를 만들 수 있습니다. 위 카운터는 두개의 루프가 존재합니다. 1. 000 -> 100 -> 110 -> 111 -> 011 -> 001 -> 000 2. 010 -> 101 -> 010 카운터의 종류 - 동기형 카운터 1.FF들의 동작이 공통 클럭에 맞춰서 동작하며 2.FF들의 상태변화가 동시에 일어난다. 즉 클럭입력에 따라 모든 FF들의 상태가 변화된다고 할 수 있습니다. - 비동기형 카운터 리플 카운터라고도 불리며, 한 개의 FF 상태변화가 다른 FF 상태를 변경하는 트리거 역할을 하는 회로입니다. T-FF을 이용한 3비트 이진 카운터 설계 ..

레지스터 레지스터(이하 Reg)는 다수비트의 데이터를 저장하는 목적으로 사용하는 소자입니다. 1. 공통 클럭을 갖는 다수의 FF을 묶어서 만듭니다. 2. 이진데이터를 저장하기 위해 사용합니다. 4비트 D-FF으로 구성한 Reg 위 ClrN은 Clear입력이 NOT 게이트를 거쳐서 들어간다는 뜻입니다. Load를 1로 만들어준 상태에서 클럭입력이 하강에지가 되면, D-FF의 출력에 입력이 나타나게 됩니다. 하지만 위와같이 구성된 reg를 사용하게 되면, 게이트를 통과하면서 생기는 시간 지연으로 모든 FF에서 동시에 값의 저장이 일어나지 않을 수 있습니다. 또한 클럭입력의 에지에서 값의 변화가 일어날 수도 있지만, Load신호에 의해서도 FF 출력에 변화가 일어날 수 있습니다. 여기서 클럭활성화(Clock ..

플립플롭 플립플롭(이후 FF)은 단일클럭을 사용하는 순차회로에서 정확히 동작하도록 설계된 저장회로입니다. FF의 특성은 다음과 같습니다. 1. FF에서 출력이 변경되기 전에 입력에서 출력으로 가는 경로를 끊어줍니다. 2. FF은 자신의 출력 변화를 볼 수 없습니다. 3. FF의 다음 상태는 바로 직전 상태에만 의존합니다.(즉, 다수의 상태 변경이 일어나지 않습니다.) 앞으로 설명하는 모든 FF은 에지-트리거형 FF입니다. 클럭 입력의 상승이나 하강 에지에서만 변경되기 때문에 사실 에지-트리거형이라고 묶어놓는 것은 의미가 없습니다. 다만 상승 에지-트리거냐 하강 에지-트리거냐가 중요합니다. D-FF D-FF은 데이터 D와 클럭 Ck 두개의 입력을 갖습니다. 심볼의 삼각형 모양이 클럭 모양입니다. 출력이 클..

순차회로 입력에만 의존했던 조합회로와는 달리 순차회로는 현재 입력과 입력들의 과거 값들의 순서에 의존합니다. 따라서 순차회로는 현재의 출력을 발생시키기 위해, 과거에 대한 무언가를 기억해야합니다. 이때 Latch(이하 래치)와 Flip-Flop(이하 플립플롭)이 기억소자로 사용됩니다. 래치와 플립플롭은 기억소자들로 1. 두 개의 안정된 출력 상태 중에 한 개를 가질 수 있으며 2. 출력 상태를 바꿀 수 있는 입력을 한 개 이상 가질 수 있습니다. 이때 클럭 입력이 없는 기억소자를 래치라고 부릅니다. 피드백 위와같이 게이트 출력중의 일부가 게이트의 다른 입력에 연결되어 폐회로를 만드는 경우, 피드백 회로라고 부릅니다. 저장장치는 피드백 회로의 지연시간으로 구현될 수 있습니다. 즉, 출력으로 나간 값이 다시..

ROM ROM은 Read only memory의 줄임말로 말 그대로 읽기만 가능한 메모리입니다. 따라서 변경이 불가능합니다. 이진 데이터 배열을 저장하는 것이 목적이며, 이를 위해 반도체 소자의 연결로 구성되어 있습니다. ROM은 n개의 입력 라인과 m개의 출력 라인을 갖습니다. n개의 입력라인이므로 총 $2^n$개의 입력을 만들 수 있고 각각의 입력에 대응되는 m비트의 배열을 워드라고 불립니다. 이때 m비트를 워드의 길이라고 합니다. $2^n \times m$비트 ROM은 $2^n$개의 행과 m개의 열을 갖는 진리표를 저장할 수 있기 때문에 n변수의 m개의 함수를 구현할 수 있게됩니다. ROM의 기본적인 구조 ROM은 디코더와 메모리 배열로 구성됩니다. 길이가 n인 입력이 디코더에 들어오면, $2^n$..

MUX MUX는 Multiplexer의 약자로 다수의 입력 + 다수의 제어입력을 갖습니다. MUX에 제어 입력을 넣으면 다수의 입력중 하나를 선택하여 출력에 연결할 수 있게됩니다. 이때 입력은 $2^n$개가 가능하며, 꼭 하나의 입력에 대해 하나의 데이터를 물려놓지 않아도 됩니다. 즉, 총 4개의 입력이 가능하다고 할때, 0에는 A라는 데이터 1에는 B라는 2~3에는 C라는 데이터를 물려놓을 수 있습니다. 중요한 것은 이중 0~3중 하나만을 제어입력을 통해 선택하여 출력해야 한다는 것입니다. 입력의 개수를 $IC$라고 하면, $IC = 2^n$개가 가능하므로 제어입력은 $log_2^{IC} = n$개가 있어야합니다. 이때 입력의 개수에 따라 MUX의 이름을 달리 부르게 되는데, 만약 4개의 입력을 가진다..

기본적인 내용은 건너뛰겠습니다. 2-3 트리를 포함한 2-3-4 트리 혹은 Multi-way 탐색 트리 까지 공통점이 있습니다.한 노드에 들어갈 수 있는 자식 노드의 개수가 m개라고 하겠습니다. 1. 루트 노드는 적어도 2개의 자식 노드가 있어야 합니다.2. 모든 leaf 노드는 같은 높이에 위치해야합니다. 즉, 항상 균형잡힌 형태를 유지해야합니다.3. 루트 노드를 제외한 모든 노드는 $\lceil \frac{m}{2} \rceil$ 개의 자식 노드들이 있어야합니다. 이번에 소개할 내용은 2-3 트리이며, m이 3인 트리중 하나라고 할 수 있습니다. 위 공통점에 해당하는 내용을 잘 생각하고 읽어주세요. 아래 예시로 드는 모든 2-3 트리들의 그림은 다음과 같은 공통점이 있습니다. 박스가 하나인 경우 --..