Chap 2) Combinational Logic Design

<Chap2 에서 다루는 내용>

   1. >> Boolean Equation  -> SOP/POS
    2. >> Boolean Algebra  -> 기본 논리식, 정리, 논리식의 간소화 방법
    3. >> 논리식을 논리회로로 구현하는 방법
    4. >> 하드웨어 레벨 관점에서 논리회로 설계
    5. >> Unknown(X)와 Floating(Z : High Impedance) 에 대해
    6. >> 카르노맵 사용법
    7. >> 대표적인 Combinational Building Block을 살펴봄(Multiplexer, Decoder)
    8. >> Timing : 입력과 출력의 시간상 변화를 분석
              -> Propagation Delay, Contamination Delay, Glitch

 

 

[2. Combinational Logic Design]

2.1 Introduction

      임의의 회로를 보통 Black Box라고 둔다. 이 Black Box는 4가지로 분석한다.

      input/ output/ fuctional spec / timing spec

 

      디지털 회로는 combinational / sequential로 나눤다.

      1)Combinational

      Combinational 회로의 output은 현재 input의 값에 달려있다. 즉, input값을 계산된 output과 결합시키는 것

      Logic Gate는 Combinational Circuit이라 볼 수 있다.

      조합회로는 메모리를 가지고 있지 않다.

      

      Combinational 회로는 그 회로를 이루는 상호 연결된 요소들이 그 자체로 Combinational 이다.

      또한 모든 노드는 최소한 한번은 거쳐야한다. 

      Combinational 회로의 function spec은 보통 Boolean equation 혹은 Truth Table로 표현된다. 

 

 

      2)Sequential

      Sequential 회로의 output은 이전의 input과 현재의 input 둘 다에 의해 정해진다. 즉, input sequence에 영향을 받는다.

      순차 회로는 메모리를 가지고 있다.

 

 

2.2 Boolean Equations

      1)Terminology

        * Literal : A, !A : 변수 또는 그것의 보수 

        * A  : True Form

        * !A : Complementary Form(보수)

 

        * Product (Implicant) : The AND of one or more literals. and라는 것은 곱이다.

                                             그래서 sum of product 는 곱의 합이다. 

 

        *Minterm(최소항) : 모든 입력 변수를 포함하는 AND항

                                        ex): ABC ... AB!C ....

 

        *Maxterm(최대항) : 모든 입력변수를 포함하는 OR항. maxterm은 A=1이면  A의 보수를 이용하여 식을 구성한다.

                                         ex): A+B+C ... A+B+!C ....

 

 

      2)Sum Of Products Form (SOP)

        We can write a Boolean Equation for any truth table by summing each of the minterms for which the output.

        진리표에서 Y가 True인 명제의 minterm의 합으로 Y를 표현할 수 있다.

        Y= !AB +AB 또는 F(A,B) = Sigma(m1,m3)

     

      3)Product of Sums Form (POS)

        Boolean 함수를 표현하는 방식의 대안으로는 POS가 있다. Y가 False인 진리표의 Maxterm을 이용하는 방식이다.

        Y= (A+B)( !A+B) 또는 F(A,B) = Pi(M0,M2)

       

 

      +)POS는 왜 A=0을 True Form으로 정의 하는가 

                

                 *minterm 

                 m1 : a'b'

                 m2 : ab'
                 m3 : a'b

                 m4 : ab

 

                 *maxterm 

                 M1: a + b

                 M2: a + b'
                 M3: a' + b

                 M4: a' + b'

 

                 m1과 M1은 서로 드모르간의 정리로 연결되는 Dual(쌍대)이다. 따라서 (minterm)' = maxterm 

                 SOP : m2+m4는 POS : M1*M3와 같아야한다.

                 m2+m4 = M1*M3에서 시작한다.

                 m2+m4 = m1' * m3' = ab'+ab= ab*ab' = ab + a'b

                 SOP= POS 성립

 

 

2.3 Boolean Algebra

      1)Axioms

      2)Theorems of one Variable

 

      3)Theorems of Several Variable

         T11에서 CD는 전체 논리 식에 영향을 주지 않기 때문에 소거한다.

         T12는 드모르간의 정리이다.

 

 

      4)The Truth Behind It All

      5)Simplifying Equations

       간소화한 식에서의 Implicants를 Prime Implicants라고 부른다. 

       식을 간소화하기 위해서는 같은 literal로 묶거나 위에서 본 정리들을 이용하여 식을 변형해야한다.

       

 

 

2.4 From Logic To Gates

식을 위와 같은 회로로 그리려면 몇가지 규칙이 있다.

 

     ▶ 입력은 왼쪽이나 상단에 표시하라.

     ▶출력은 오른쪽이나 하단에 표시하라.

     ▶ 가능하다면 논리 게이트는 왼쪽에서 오른쪽으로 진행하도록 그려라.

     ▶전선은 가능하면 직선으로 그려라. (너무 많이 꺾은 전선은 회로 파악하기 어렵다.

     ▶ 전선은 언제나 T접점에서 연결된다.

     ▶ 전선이 교차하는 곳의 점은 두 전선이 이어져있다는 의미이다.

     ▶ 점이 없이 전선이 교차하는 곳은 전선이 연결되어있지 않다.

 

 

 

*우선 순위 회로

 

 

2.5 Multilevel Combinational Logic

SOP에서의 논리는 Two-Level Logic 이다. OR 논리로 연결된 AND논리이기 때문

 

      1)Hardware Reduction

        we have been using ANDs and ORs,but in CMOS,NANDs and NORs are more efficient.

        하드웨어 단계에서는 Trade Offs 생각해서 논리회로를 짠다.

 

      2)Bubble Pushing

     CMOS 회로는 AND나 OR 보다는 NAND나 NOR로 구성되는 것이 좋다.

     하지만, NAND나 NOR로 이루어진 회로는 읽어서 파악하기에 어렵다.

     Bubble Pushing은 Bubble을 상쇄 시켜서 함수가 더 쉽게 파악되도록 돕는 회로를 재구성하는 방법이다.

     Bubble Pushing은 아래 규칙을 따른다.

 

       ▶ Begin at the output of the circuit and work toward the inputs.

            회로의 출력부 부터 시작해서 입력부로 향하는 방향으로 시행한다.

 

       ▶ 최종 출력부에 있는 어떤 Bubble 이라도 입력방향으로 밀어넣어라.

            !Y말고 출력을 Y로 하는 편이 읽기 좋다.

 

       ▶ Bubble을 Input 방향 쪽으로 계속 밀어넣어라. 이 과정에서 Bubble이 상쇄되도록 한다.

           현재 게이트가 입력 Bubble을 가지고 있다면 이전 게이트를 출력 Bubble이 있도록 그리고.

           현재 게이트가 입력 Bubble을 가지고 있지 않다면 이전 게이트를 출력 Bubble이 없도록 그려라.

 

 

변경 전

 

변경 후

 

            (a) 최종 출력은 보수 안씀.

            (b) 입력-출력 사이에 둘다 보수 쓰면 상쇄 시킴.즉, 버블-버블 혹은 !버블-!버블 구조.

            (c) 버블은 왠만하면 입력 쪽에 넣는다.

            출력 버블을 입력 버블로 바꾸면 논리 게이트가 바뀜 (드모르간 법칙에 의해)

 

(a)는 게이트 종류 바꾸지 않고 인버터 부분만 버블 캔슬 한 것.

(b)는 NAND와 NOR로 구성되도록 설계

 

2.6 X's And Z's, Oh my

Boolean Algebra에서는 0과 1 뿐이지만, 실제 회로에서는 illegal하고 floating values가 있다.

그래서 이를 표현하고자 X와 Z를 사용한다. 

 

      1)Illegal Value : X 

       0 또는 1인 경우인데, Unknown인 것이다.

      2)Floating Value : Z 

       Floating and High Impedance : 0도 1도 아닌 상태 

2.7 Karnaugh Maps

Karnaugh maps (K-maps) are a graphical method for simplifying Boolean equations.

1만 나오는 경우만 모아서 입력값을 표현하는 방법.

최소항(minterm)만을 이용한다.

 

*Don't Care Condition(무관항)

신경쓰지 않아도되는 항으로 0과 1 중 임의의 값으로 설정하여 편한대로 조작하면 된다.

입력이 결과에 영향을 주지 않는 항.

결국, 카르노 맵은 최소항을 더하는 방식이다. 무관항을 아무리 논리식에 더해도 영향을 주지 않기 때문에

카르노 맵에서 무관항을 1로 두어 더하든, 0으로 두어 더하지 않던 논리식의 결과값에 영향을 주지 못한다.

따라서, 무관항은 0과 1중 임의의 값으로 조정해도 된다. 1로 사용하는 경우에는 어차피 결과에 영향을 안주니

식 정리에나 쓸 목적으로 더하자는 마인드이다.

 

*카르노 맵(4변수 이하일 때 보통 사용한다)

 1. 변수의 개수 파악해서 2의 n승 테이블 생성하고

 2. 변수 연산의 값이 0인지 1인지 표현.

 3. 묶을 수 있는 것은 묶는다.(이웃한 항끼리 묶는다)

 4. 묶은 것은 간소화한다. (사각형  형태로 묶어야하고, 크게 묶을 수 있으면 가능한 크게 묶는다.)

아래 그림을 보면 알겠지만 00 01 11 10에서 01에서 11로 가는 이유는

한 변수만 달라지도록 기입하기 때문이다.

1비트만 달라야 묶을 때 해당하는 변수를 1개씩 삭제할 수 있기 때문.

예시1

 

에시1 묶기

Y=A'B'(C'+C) + C'(AB+AB')+AB'(C'+C)

Y=A'B'+AC'+AB'=B'+AC'

 

카르노 맵은 묶을 때 여러가지 방법으로 묶을 수도 있다.

카르노맵은 위아래, 좌우가 연결되어있다고 볼 수 있다. 예시 1 묶기에서 B'을 보면 된다 .

 

예시2 - Sol

예시3

 

에시3-Sol

4)The Big Picture 

    보통 논리식 최적화할때는 Logic Synthesizer 이용해서 회로를 간략화 한다.

무관항(Don't Care) 있는 경우

    무관항은 필요할 때 임의로 0 혹은 1 넣어서 사용한다. 

    즉, 묶는데 필요한 경우 맘대로 변경.

    무관항은 회로만들때 전혀 쓸모없는 경우의 수 정도로 생각.

2.8 Combinational Building Blocks

    Combinational Logic은 복잡한 논리를 수행하기 위해서 Building Blockd을 만들어서 사용한다. 

    어떻게 보면 함수라고 볼 수 도 있다.

    그 예로 "Full Adder", "Priority Circuits", "Seven Segments Decoder"등을 책에서 다루었다

    이 챕터에서는 멀티플렉서와 디코더라는 Building Block을 다룰 것이다. 

      1)Multiplexers

        멀티플렉서는 입력값 중에서 신호 하나를 고르는 것이다. S 신호를 통해서 D0 혹은 D1을 선택하여 출력값으로 쓴다.

        디폴트로 D0를 선택한다. 단, S=1일때 D1 선택

Case1

Case1 Sol - 카르노맵 이용

 

 

      2)Decoder 

        디코더는 N개의 입력과 2^n개의 출력으로 구성된다. 인코딩한 값을 풀어해치는 역할이다. 

 

 

2.9 Timing

    출력값은 입력값의 변화에 따라서 변화하는데 "시간"이 필요하다. 

    이때 걸리는 딜레이를 보기 위해서 Timing Diagram이라는 것을 본다.

    이 다이아그램은 Transient Response을 표현한 것이다.

    Low에서 High로 변하는 구간은 Rising Edge라고 한다. 

    반대는 Falling Edge.

 

      1)Propagation and Contamination Delay

         Combination Logic은 "Contamination Delay"와  "Propagation Delay" 로 특징잡혀진다.

 

         *Tcd : Contamination Delay (전염 시작)

                 : 입력값이 변할때 출력값의 처음 값에 이 변화가 영향을 주는 데까지 걸리는 최소시간.    

         *Tpd : Propagation Delay. (완전 전파)        

                 : 입력값이 변할때 출력값의 마지막 값에 이 변화가 영향을 주는 데까지 걸리는 최대시간         

     

 

         Propagation 이나 Contamination delay는 신호가 거쳐오는 Path라는 것에 영향을 받는다. 

         이때, Critical Path란 갈 수 있는 Path 중에서 가장 오래 걸리는 길이다.

         

 

 

    Combination Circuit에서 Propagation Delay값은 Critical Path에서 거치는 소자들의 Propagation Delay의 합이다.

    출력값의 마지막 변화값까지 걸리는 최대시간이므로 가장 멀리 돌아가는 길을 보는 것이다. 

    반대로, Contamination Delay는 출력값이 처음으로 영향을 받은 시간이므로 최대한 짧은 Path를 봐야한다. 

    따라서, 짤은 Path의 Contamination Delay의 합이다. 

 

 

 

 

 

 

      2)Glitches

          지금까지 하나의 입력값 변화에 따른 하나의 출력값 변화만을 이야기했다.

          하지만, 하나의 입력값 변화에 따른 여러 출력값 변화 또한 가능하다.

         이를 Glitches / Hazards 라고 한다. Glitches 자체는 보통 문제를 일으키지는 않지만.

          Timing Diagram을 볼 때 Glitches가 존재한다는 것을 인식하는 게 중요하다.

 

 

      Glitch는 다른 Gate를 추가해서 없앨 수 있다.

     A=0, C=1 일때 B가 변하는 구간에서 하나의 항이 켜지기 전에 다른 항이 꺼져버리면 Glitch가 발생한다.

     이를 보완하기 위해서는 항과 항 사이의 구간도 논리식에 포함해야한다.