Working with combinational logic

1. Simplification

1-1. two-level simplication

<Definition of terms for two level simplification>

Implicant : subcube를 이루는 on-set이나 dc-set을 칭하는 말.

Prime implicant : 더 큰 subcube로 묶을 수 없는 implicant

Essential prime implicant : prime implicant 중에 다른 prime implicant로 포함되지 않는 on-set을 가진 것

 

목표 : implicant를 prime implicant로 만들기

on-set을 적은 수의 prime implicant로 커버하기

 

Algorithm : K-map으로 가장 적은 term의 SoP 만들기

 

1. On-set의 엘리먼트 선택

2. 해당 on-set의 가장 큰 그루핑하기 : prime implicant로 만들기

3. on-set들을 방문하며 essential하다면 꼭 포함시키기

4. 가장 적은 수를 가진 term 조합으로 선택

 

SoP는 편하게 NAND gate로 이뤄진 회로로 바꿀 수 있음

 

SoP NAND로만 구성하기

마찬가지로 PoS를 NOR로만 구성하기도 쉽다.

 

1-2. Multi-level logic

 

input에 가능한 literal 개수가 정해져있을 때, 사용된다.

 

<이득>

회로가 작아질 수 있다.

게이트들이 적은 fan-in(# of input literals)

회로가 더 빨라질 수 있다.

 

<불이득>

디자인하기가 힘들다

optimization skill이 two-level에서 가장 좋음

분석이 더 복잡하다.

 

 

2-3. AOI gates(AND-OR-invert gates)

 

AOI의 개념적 회로도와 실제 구현

실제 구현을 보면 트렌지스터가 8개 밖에 들지 않는다!(NAND, NOR이 각각 4개)

 

A XOR B = A'B + AB' => (A'B' + AB)' => AOI gate로 표현 가능!

 

3x2 AOI => 3개의 input literals를 가진 2개의 and stack을 가진 AOI

2. Time behavior of combinational networks

combination 회로에 시간 정보를 확인하는 법 = Waveform

 

 이에 고려해야하는 사항들

 

gate delay = input의 변화가 output의 변화로 되는데 걸리는 시간

rise time = output의 변화가 low에서 high로 가는데 걸리는 시간

fall time = output의 변화가 high에서 low로 가는데 걸리는 시간

pulse width = high나 low에서 신호가 유지되는데 걸리는 시간

 

이를 이용한 회로!

pulse shaping circuits

 

pulse shaping circuits

pulse 모양으로 waveform이 나타나게 된다, => A가 D로 가는 동안 걸리는 delay를 활용한 회로

 

이를 좀 더 이용하면 Oscilatory behavior로 나타낼 수 있다. => 반복적인 파도 모양의 회로가 만들어짐

 

3. Hardware Description Languages

Hardware Description Language = 여러가지 종류가 있지만 우리는 Verilog를 사용할 예정

 

Verilog는 원래 simulation만을 위한 언어였지만 synthesis에서도 사용 되고 있다.

 

Verilog를 작성하는 방법은

 

1) Structural

=> 모듈 내에서 모듈이 어떻게 구성되어 있는지를 나타내는 디자인법

 

2) Behavioral

=> 논리식이 어떻게 이루어지는지를 알려주는 디자인법

 

우리는 Behavioral를 주로 사용할 예정

 

3-1. always block

 

always @(a or b) begin

      #6 out = a ^ b;

end

 

@( ~~~ ) : sensitivity list라고 하며 안에 있는 변수가 변할 때마다 수행된다.

@(*) : 모든 변수가 안에 있는 것을 말한다.

always block 내에서는 코드가 순차적으로 수행된다.

always block에서 assign 해주는 변수는 항상 reg나 integer로 선언해야 한다.

 

3-2. case

: 항상 always block 안에서만 수행된다.(casex, for, if 등 마찬가지)

: combination logic은 항상 모든 인풋이 always의 sensitivity list에 들어있어야 한다.

 

3-3. casex

: dont care set을 x로 선언 가능

 

3-4. assign

 

always 없이

assign을 할 때는 wire type으로 선언해줘야 한다.

 

hardware는 병렬적으로 동작한다. => 이러한 특성을 살려 디자인 해줘야 함.

 

4. Adder for lab

:

Full Adder는 두개의 Half Adder로 만들어줄 수 있다.

두개의 Half Adder로 Full Adder를 구현

 

Multi bit adder를 구현하는 두가지 방법

 

4-1. Ripple carry adder

 

Ripple Carry Adder

병렬적이지 못함. 캐리가 전달될 때까지 수행을 기다려야 함.

 

4-2. Carry Select Adder

 

Carry가 1일 때, 0일 때의 결과를 각각 수행해두고 mux로 이를 선택하는 방식

 

Mux : n개의 control inputs로 2^n개의 data input 중 하나를 선택하는 device

 

 

 

5. Quine-McCluskey Method

 

알고리즘적으로 적당히 좋은 minimized term을 선택하는 방법

 

1. Find all prime implicants

 

1) Implication Table에 term 개수로 column를 나눈다.

column 안에서는 1의 개수별로 나눠서 적는다(인접한 implicant를 찾기 쉽기 때문)

 

2) 그 다음 한 번도 묶이지 않은 implicant를 별표 쳐준다,(prime implicant)

 

implication table

 

2. find smallest set of prime implicants that cover the ON-set

 

1) 이후에는 prime implicant chart를 만들어서 cover된 minterm을 체크해준다.

=> cover해야하는 minterm에 아까 찾은 Prime implicant를 넣어서 cover하는 것들을 체크 해줌.

 

2) minterm 중 하나의 prime implicant에만 cover 되는 것이 essential prime implicant가 됨

=> 밑의 예시의 경우 4, 15가 하나의 prime implicant로만 cover됨.

 

3) 이 이후에는 전체 다 순회하며 minimized term을 구해줘야 함.

 

Prime implicant chart

 

전체 prime implicant를 다 구하지 않고 적당히 구하는 것이 Espresso 방법

 

Expand와 Reduce를 iteration하면서 좋은 답을 구해간다.