數位電路設計––單智君

回目錄

第二章 Boolean Algebra and Logic Gates

• Sum of Minterns
• Product of Masxterms

2. Standard Forms (two level implementsation 兩層電路) -> maybe faster

• Canonical forms
• Standard forms
• Nonstandard form -> maybe cheaper

3. Other logic operations

• all possible functons of n binary variables:
  n binary varibles -> 2^n distinct minterms -> 2²n possible functions

4. 16 functions subdivided 3 categories
   1. 2 functions
   2. 4 functions
   3. 10 functions
5. Digital Logic Gates

• Boolean expression (AND, OR, NOT)

• Others type

  • feasibility and economy
  • possibility of extending the gate to more than two inputs
  • basic properties
    ex.交換律、結合律…
  • alone or conjunction

• Gate:

  • 0, 1 -> unnecessary
  • Transfer, Complement -> y
  • Inhibition, Implication -> oppo of upon -> unnecessary
  • AND, OR, NAND, NOR, XOR
  • NAND and NOR are far more popular than AND and OR
    

• Extension to multiple inputs

• AND, OR: commutative and associative

• NAND, NOR: commutative but not associative
  [(ABC)'*(DE)']' = ABC+DE ≠ (ABCDE)' = A'+B'+C'+D'+E'

• XOR, Equivalence: commutative and associative

  • XOR: odd function -> 輸入奇數個 1 時，輸出爲 1
  • Equivalence: even function -> 輸入偶數個 1 時，輸出爲 1

• Positive Logic (H = 1) && Negative Logic (H = 0)
  同一電路，正負邏輯會使邏輯閘代表意義互補(dual) eg.AND->OR

• Integrated Circuits (ICs)

  • Levels (複雜度)

    1. SSI small-scale, <10 gates
    2. MSI medium-scale, 10~100
    3. LSI large-scale, 100~x000
    4. VLSI very large-scale, x000~

  • Families

    1. TTL transistor-transistor logic
    2. ECL emitter-coupled logic (speed)
    3. MOS metal-oxide semiconductor (density)
    4. CMOS complementary MOS (power)
    5. basic ckt: NAND, NOR, inverter

  • important parameters (additional)

    • fan-in (輸入個數)
    • fan-out (輸出個數)
    • noise margin (辨識度範圍)
    • Cost
    • propagation delay (輸入出時差)
    • power dissipation (

  • CAD tools -> Schematic capture tools -> Logic simulator -> Logic synthesizer

第三章 Gate-Level Minimization

1. Introduction and Cost Criteria

• Representation of boolean function (Truth table, Algebraic expression)
• Minimization of boolean function
  • Algebraic manipulation: literal minimization -> difficult and hard to sure minimaze
  • map method: gate-level minization -> more than 4 variable are hard to use
  • Tabular method: Quine-McCluskey method -> systematic producdure
• Cost Criteria
  • Two cost criteria:
    1. Literal cost: the # of literal apperatances in a Boolean expression
    2. …
  • Literal cost:
    • the # of literal appenrances in a Boolean expression
      • e.g. F = AB+C(D+E) -> 5 literals (non-stander)
        F = AB+CD+CE -> 6 literals (stander form)
  • Gate input cost (GIC):
    • the # of inputs to the gates in the implementation
    • good method for conteporary logic implementation
      • e.g. G = ABCD + A'B'C'D' -> GIC = 9
        G = (A'+B)(B'+C)(C'+D)(D'+A) -> GIC = 12
    • For SoP or PoS eqs, GIC = the sum of
      • all literal appearances
      • the # of terms excluding terms that consist only of a single literal
      • the # of distinct complemented single literals operation

2. Map Method

• karnaugh map simplification

​​​​- simple
​​​​- k-map: pictorial form of truth table
​​​​  - n input => 2n squares
​​​​  - minterm of function
​​​​  - adjacent squares differ by only one variable
​​​​- SOP(sum of products) or POS(products of sum)

• Not unique
  • minimum of literals
  • minimum of gates

1. Two-Variable
   - 2 var -> 2n = 4 minterms
   - corresponding minterms have just one var different

• Three-Variable
  • 3 var -> 2n = 8
  • Find possible adjacent 2k squares:
    • each element can used a lot of times
    • the most left ele have a ele left next to it is the most right ele
    • the most down ele can also cycle to top
    • if 12 or 21 are all 1 -> different ele can be eliminate
    • if 2*2 same 1 can also be eliminate
    • if 14 or 41 same
    • used bigger rectangle shape is better

1. Four=Variable Map and Five-Variable Map

• Four
  • try to make a square
  • also can eleminiate by neighbor
  • also can left to right or down to top
  • eleminiate for 2, 4, 8 (and so on for n-variable)
  • used bigger rectangle shape is better
• Prime Implicants
  • Implicant
  • Prime Implicants (PI): the biggest rectangle for every ele
  • Essential Prime Implicants (EPI)
• minterm:
  • essential PI
  • lest PI choose must selected PI
  • deside the minimal cost out of rest of minterms
• Five

• con
  • For upper than 5 var…

1. Product-of-Sum (PoS) Simplification

• using De Morgan's laws after POS of F
• just used POS of F -> 0 and OR
• compare POS and SOP for cheaper

2. Don't-Care Conditions and Quine-McCluskey Method (Tabular Method) (x)

• Don't-Care
  • specify with d() = ∑m()
  • unspecified minterms of a function
  • Incompletely specified function specified function
  • simplification of an incompletely s
• Quine-McCluskey Method
  • finds all PIs and minimum cover of PIs
  • used (xy + xy' = x)
  1. group by number of 1's
  2. compare elements of adjacent groups
  • ex:
    F(A,B,C,D) = sigma m(0,1,2,5,7,8,9,10,14)
    

3. NAND and NOR Implementation

• The lest step
• NOT, NAND, NOR is faster
• use NOT, NAND, NOR to make AND, OR, NOT => easier to think
• roles:
  1. universal property of NAND gate
  2. AND = NAND-NOT
  3. OR = NOT-NOR
  4. AND-NOT = NOT-OR
  5. sop(AND-OR) = NAND-NAND
  6. NAND = NOT-OR
  7. universal property of NOR gate

4. Other Two-Level Implementations

• Wire logic
  • Wired-AND logic: oppen-collector TTL NAND gates
  • Wired-OR logic: ECL NOR gates
• 2-level combinations of gates:
  • AND OR NAND NOR => 16
  • Degenerate forms: 8
    • degenerate to dsingle: 2 -> 1 level
    • AOI (AND->OR->inverst(NOT))
      • F' 的 sum of product
      • AND-NOR
      • NAND-AND
    • OAI (OR->AND->inverst)
      • F' 的 product of sum
      • OR-NAND
      • NOR-OR

5. Exculsive-OR Function

• Exculsive-OR: XOR, ⊕
  • x ⊕ 0 = x
  • x ⊕ 1 = x'
  • x ⊕ x = 0
  • x ⊕ x' = 1
  • x ⊕ x' = x
  • x ⊕ y' = x' ⊕ y = (x ⊕ y)'
• multiple-variable: odd function
• 不相鄰的 2n/2個 1
• 奇數個 input -> output is 1
• 交換率、結合率
• 算 parity bit (b1⊕b2⊕b3⊕…⊕bn = parity bit)
• Exculsive-NOR: XNOR, equivalence
• useful in arithmetic operations and error-detection and correction ckts

6. Multiple-level

• G = ABC + ABD + E + ACF + ADF
  • Sop => GIC = 17
  • implementation: distributive law
  • =>G = AB(C+D) + E + AF(C+D) = A(B+F)(C+D) + E

7. Hardware Description Language (HDL) and Multiple-Level Circuit Optimization

Verilog Model

• Hardware description language (HDL)
• feature
  • comment: / / or /* */
  • file name: .v
  • case sensitive
  • REMEMBER ' ; '
• Synthesizable Modules & Testbench

  • synthesizable modules: describe hardware

  • testbench: check output result of module is correct

  • Sample of synthesizable modules:
    ex:
    module Name_Of_Module(inputA,inputB,inputC, outputD,outputE); // module name, parameters for all input and output
    output outputD, outputE; // describe output
    input inputA, inputB, inputC; // describe input
    wire w1; // describe wire
    /* GATE following, output is always be the first parameters /
    and G1(w1,inputA,inputB); // this is an AND gate, G1 is gate name, w1 is output of gate, inputA and inputB is input
    not G2(E,C); // NOT gate, E output, C input
    or G3(D, w1, E); // OR gate
    / The order of above gate are NOT important */
    endmodule

    • Identifiers: case sensitive, name with number, character, _
    • comment / / and /* */
    • endmodule can without ' ; '

  • Sample of testbench:
    ex:
    module test_bench_name; // no input output
    wire C, D; // output
    reg A, B; // *input

    ​​​​​​​​    //instantiate device under test
    ​​​​​​​​    Name_Of_Module M1(A, B, C, D); // an instantiation of the model to be verified, name of parameters can be difference
    ​​​​​​​​    
    ​​​​​​​​    // apply inputs one at a time
    ​​​​​​​​    initial
    ​​​​​​​​        begin
    ​​​​​​​​            A=1'b0; B=1'b0; C=1'b0;
    ​​​​​​​​            #100 A=1'b1; B=1'b1; C=1'b1;
    ​​​​​​​​        end
    ​​​​​​​​    initial #200 $finish;
    ​​​​​​​​    endmodule
    

    • initial statement
      • executes the statements in its body at the start of simulation
      • should be used only in testbenches for simulator
      • # show as time
    • begin, end

  • Simulation waveforms (show the result)

  • `timescale 1ns/100ps

    • ` for compiler directive
    • #30 -> 30ns delay

  • testbranch

    • initial
    • begin, end
    • $finish
    • reg, wire

  • boolean exprission

    • assign =
    • bitwise: & | ~
    • logical: && || !

第四章 組合電路 Combinational Logic

gate設計流程：從問題轉成gate的方法：

1. Specification：確認需要有多少輸入和輸出，並給定各自的symbol
2. Formulation：確認輸入和輸出的關係，畫truth table
3. Optimization：簡化，使用k-map
4. Technology mapping：畫成電路
5. Verification：測試

binary 加法器：
半加器(half adder)：把2個bit相加
加法器(full adder) ：把3個bit相加（實踐起來會是兩個半加器）

設計方法：

• Hierarchical design:
  • Top-down
  • Bottom-up
• Iterative design

加法器 Binary Ripple Carry Adder (n-bit Parallel Adder) (RCA)

使用Hierarchy & Iterative design，用n個full adder來湊
總共的Propagation-delay是2n+****1個gate-delay
但是速度太慢了，所以現實世界不會使用這種設計方法

加法器加速方法

• Carry lookahead：不要等上級給我carry才來算，直接由輸入算出自己的carry
  [ ] Carry Lookahead Adder (CLA)
  [ ] Gi = Ai Bi: 一定會有carry
  [ ] Pi = Ai +Bi: 傳遞的carry跟傳入的carry相同

總共的Propagation-delay固定為6個gate-delay

binary 減法器：
A - B = A + (1's complement of B) + 1
用一個M來控制加法器的mode
M = 0 => A + B
M = 1 => A + B' + 1

處理overflow

• 對於unsigned number：
  • 最左邊的bit有carry out就有
• 對於signed number：
  • 正加正變負、或負加負變正，就有
  • 或是sign bit的carry in⊕carry out為true就有

十進位加法器：

• BCD加法器
• 先用正常的adder直接加，需要時做的部分只剩下binary sum轉bcd sum的那一塊
• C = K + Z8Z4 + Z8Z2
• BCD sum = binary sum + 0cc0
  

binary 乘法器

• a*b個AND GATE
• b-1個加法器
• 輸出a+b個bits

比較器

編碼器 encoder

• 輸入2^n個不同的狀況作為訊息
• 編碼成n個bit來表示輸入的訊息
• 問題：
  • 輸入只能有一個bit是1
    • 解決方法：priority encoder，決定輸入的優先順序，哪個先編
  • 輸入不能全部是0
    • 解決方法：valid-output indicator，新增一個輸出，代表現在的輸入是否有意義

priority encoder:

優先順序可以任意自訂，這邊的設定為D3優先權最大

解碼器 decoder

• 就解碼
• 輸出只會有一個是1

Line Decoder

• 尾巴加個NOT就可以把minterm轉成maxterm

• active HIGN: minterm

• active LOW: maxterm

• 1-to-2-line decoder
  

• 2-to-4-line decoder
  

• 3-to-8-line decoder
  

enable input

• 新增一個輸入當成enable input
• 當enable input為正確的值(可能是1或0)時，電路才工作
  

Demultiplexer 解多工器（信號分離器）

• 用來選擇哪一條輸出線會收到資料
• 直接使用line-decoder with enable input來做！
• 只要把enable input當作input data，把data當作線路選擇

任何有n個輸入和m個輸出的boolean function都可以用一個n-to-2^n-line decoder配上m個OR來實作

Multiplexer 多工器

• 很多個輸入，選擇使用哪條輸入當作輸出
• multiple-bit selection logic: 多bits資料組的選擇
• 也可以用multiplexer來實作任何boolean function
• 但是multiplexer很貴
• 所以可以用2^n-1的multiplexer來做
• 2^n-2也可以，可是會越來越複雜

three state gate (tri state gate?)

• 一般gate的output不可以直接拉在一起，除非有wire-logic，或是保證任何時間只有一個gate output是通的
• Three state gate有兩個輸入：common input和control input
• 當control input是1時，輸出為common input
• 當control input為0時，輸出為0(disabled, 高阻抗?)
• 可以搭配decoder用來實作multiplexer

組合電路的HDL設計

• 設計規範：

  • 每個模組一個.v檔案，檔名必須和模組名一致
  • output要設為module的第一個port

• 三種設計模式：

  • gate-level
  • dataflow（通常只用在combinational circuit
  • behavioral（主要用來做sequential circuit，但也能用來做combinational circuit

• 兩種設計方法：

  • buttom-up: 先組小電路，用小電路組大電路
  • top-down: 先想大的，需要用到小電路在組小的，大電路較常使用top-down方法

• 系統定義的12個gate:

  • 多input單output:
    • and, nand, or, nor, xor, nxor
  • 單input多output:
    • not, buf
  • 四個three state gate:
    • active high: bufif1, notif1
    • active low: bufif0, notif0

• 4 value system:

  • 各個wire的數值只可能有四種情形
  • 0, 1, x(unknown), z(high impedance)

• output [0: 3] D：D是一個vector，有D[0], D[1], D[2], D[3]四個數，最高的bit(MSB)是D[0]

• 2005後的verilog可以將output, input的keyword直接寫在module的port list內

• tri: 代表那條線路有多個driver（多輸出接在一起的，可能會出現z值）

• **wire, wor, wand, tri, supply1, supply0，**多種線的定義

• dataflow modeling

  • { } concatenation，一次assign多個bits
  • ? : conditional
  • dataflow可以簡化很多東西，在合成的時候會根據你下的參數和函式庫設計自動生成對應電路

• Behavioral modeling

  • always @: 符合條件時不斷執行
    • 裡面的output要設為reg
    • @裡面用or把各個輸入變數串起來
    • 可以寫always @(*)，每個變數改變時都會重新run
    • 每次@裡面的東西改變時，整個block都會重新run一次
    • 設定output值時要用**=**
  • if else
  • case endcase default
    • casex: 有x或z時執行
    • casez: 有z時執行

• 數值表示：N'Bvalue

  • **_**可增加數字可讀性，會被編譯器忽略

• Test Branch

  • 程式進入點：initial always
  • control flow: #(Time) repeat(Count)
  • text的方式顯示結果
    • $display: 會換行的printf
    • $write: 不會換行的printf
    • $monitor: 當變數有改變會自動顯示
    • $time: 顯示時間
    • $finish
    • %d: 前面會有空白, %0d: 沒有
    • reg wire parameter 變數

ch5 Synchronous Sequential Logic

同步電路：有管制改變時間（有閘門）、好設計
非同步電路：沒有管制、速度快、成本低

Latches：非同步，flip-flops的基本
SR Latch

• 由兩個NOR組成
• Active HIGH
• 兩種正常有用狀態：
  • Set: Q = 1, Q' = 0
  • Reset: Q = 0, Q' = 1
• 正常的輸入：S,R不能同時為1
• 功能表：
  S R Q+
  0 0 Q
  0 1 0
  1 0 1
  1 1 不應該發生

S'R' Latch

• 由兩個NAND組成
• Active LOW的SR Latch
• 功能表：
  S R Q+
  1 1 Q
  1 0 0
  0 1 1
  0 0 不應該發生

with control
D Latch

moore model vs mealy model

• moore比較穩定
• mealy反應較快

HDL
新關鍵字：forever: 無限迴圈
always @(posedge wire1, negedge wire2)
<=: none blocking assignment, 所有 <= 會同時做

電路設計
狀態減少直接影響flip-flop數量
化簡方法：

• Row matching method
• Implication chart method

小考