Logic Design

1 Verilog HDL 1.1 Verilog 簡介 一套硬體描述語言 輔助設計數位系統 描述電路的行為 電子自動化工具 類似C語言的硬體描述語言 易學、容易接受 高階行為描述 切勿使用軟體思維(循序)撰寫(硬體描述語言多是並行的) 支援多種硬體層級的描述方式 從低階到高階模式 依照不同的方法設計 支援階層式的設計方法 樹狀式的設計結構 由繁化簡 1.2 Verilog 的模型 1.2.1 電晶體層級 Transistor Level 或低階交換層次模型(Switch Level Model) Verilog 最低階的層次模型 電路是由開關與電晶體所組成 一般不會採取低階的層級來進行設計 1.2.2 邏輯閘層級 Gate Level 使用基本的邏輯閘元件 AND、OR、NOT 邏輯電路圖 1.2.3 資料流層級 Data Flow Level 描述電路中資料的處理方式 資料如何在電路中運算及傳送 輸入持續驅動輸出 運算式 如：out = a + b + c 1.2.4 行為模型 Behavior Level Verilog 最高階的層次模型 不需考慮硬體元件的特型，只需放在模組的功能描述 很像 C 語言 合成軟體工具 1.2.5 結構式模型 Structure Level 引用硬體模組的模式 類似邏輯閘層次模型 支援階層式設計法 將複雜電路分為層狀結構 架構上類似樹狀結構 Bottom-up：元件→子模組→設計目標 Top-Down：設計目標→子模組→元件 Mixed：設計目標→子模組←元件(常用於大型複雜系統) \( \boxed{\text{Full Adder}} \begin{cases} \boxed{\text{Half Adder}} \begin{cases} \boxed{\text{XOR}}\\ \boxed{\text{AND}} \end{cases}\\ \boxed{\text{Half Adder}} \begin{cases} \boxed{\text{XOR}}\\ \boxed{\text{AND}} \end{cases}\\ \boxed{\text{OR}} \end{cases}\\ \text{設計目標}\qquad\qquad\text{子模組}\qquad\text{元件} \) 1.3 Verilog 語法詞彙 由一連串的標記(token)所組成 識別字(identifiers) 關鍵字(keywords) 字串(strings) 註解(comments) 空白(whitespace) 數值(numbers) 1.3.1 識別字(identifiers) 描述電路行為所使用的自訂物件 不違反命名規則，工程師自行定義的物件名稱 命名規則 字母、數字、底線_或是錢字號$所組合而成。 開頭只能使用字母或底線。 識別字是有大小寫之分的。 舉例 Shift_reg_b (Valid) _bus123 (Valid) $error_condition (Invalid) NT$899 (Valid) 3_bit_data (Invalid) 1.3.2 關鍵字(keywords) 描述電路語法所保留的一組特殊名稱的標記 定義語言的結構來描述電路 輸入(input)、輸出(output) 資料型態、電路行為 所有關鍵字都必須使用小寫表示 不可當作識別字使用 常見關鍵字 \(\begin{array}{|l|l|l|l|l|l|}\hline \text{always}&\text{and}&\text{assign}&\text{begin}&\text{buf}&\text{bufif0}\\\hline \text{bufif1}&\text{case}&\text{casex}&\text{casez}&\text{cmos}&\text{default}\\\hline \text{defparam}&\text{else}&\text{end}&\text{endcase}&\text{endfunction}&\text{endmodule}\\\hline \text{endtask}&\text{event}&\text{for}&\text{forever}&\text{fork}&\text{function}\\\hline \text{highz0}&\text{highz1}&\text{if}&\text{initial}&\text{inout}&\text{input}\\\hline \text{integer}&\text{join}&\text{module}&\text{nand}&\text{negedge}&\text{nmos}\\\hline \text{nor}&\text{not}&\text{notif0}&\text{notif1}&\text{or}&\text{output}\\\hline \text{parameter}&\text{pmos}&\text{posedge}&\text{pull0}&\text{pull1}&\text{pulldown}\\\hline \text{pullup}&\text{rcmos}&\text{real}&\text{realtime}&\text{reg}&\text{repeat}\\\hline \text{rnmos}&\text{rpmos}&\text{rtran}&\text{rtranif0}&\text{rtranif1}&\text{strong0}\\\hline \text{string1}&\text{supply0}&\text{supply1}&\text{task}&\text{time}&\text{tran}\\\hline \text{tranif0}&\text{tranif1}&\text{tri}&\text{tri0}&\text{tri1}&\text{triand}\\\hline \text{trior}&\text{trireg}&\text{wait}&\text{wand}&\text{weak0}&\text{weak1}\\\hline \text{while}&\text{wire}&\text{wor}&\text{xnor}&\text{xor}\\\hline \end{array}\) 1.3.3 字串(strings) 一連串字元(character)組成的單一個體 可含有字母、數字、及一些特殊字元 字串的所有字元必須在同一行上，並在雙引號之間 1.3.4 註解(comments) 程式碼中加入說明文字 可讀性(readability) 文件化(documentation) 版權宣告(license declaration) 以//開頭的單行註解(one-line comment) 以/*為開頭，並以*/為結尾的多行註解(multiple-line comment) 多行註解不支援巢狀結構 1.3.5 空白(whitespace) 區隔不同物件 空格(blank spaces，\b) 欄位(tabs，\t) 換行(newlines，\n) 除字串內空白，註解與空白在編譯與合成時會被忽略 1.3.6 數值(numbers) Verilog 有兩種數值表示法 固定長度(sized): 定義位元寬度 <size>'<bsase format><number> <size>：十進位來表示此數的位元數(bits) <base format>：定義進制 'H|'h：十六進制 'D|'d：十進制 'O|'p：八進制 'B|'b：二進制 <number>：用<base format>來表示數值 若為負號，將-放在<size>前面 舉例： 18'h47CB：18 bits 的十六進位數 47CB 13'h47CB：13 bits 的十六進位數(因未給定高位元自動補0) 7CB 12'd1023：12 bits 的十進位數 1023 9'o723：9 bits 的八進位數 723 5'b11101：5bits 的二進位數 11101 5'b1xx01：含有 unknown values 的表示法 不定長度(unsized): 未定義位元寬度 ‘<base format><number 不使用<size>規定位元長度 使用 HDL 編譯器內定的長度(32bit的寬度) 沒有寫明<base format>，則內定為十進制 舉例： 'h47CB：32 bits 的十六進位數 47CB 1023：32 bits 的十進位數 1023 'o723：32 bits 的八進位數 723 'b11101：32 bits 的二進位數 11101 Verilog 有四種數值位準(value level) \(\begin{array}{|c|l|}\hline \text{數值位準}&\text{實際電路狀態}\\\hline \text{0}&\text{邏輯0，假(false)，接地}\\\hline \text{1}&\text{邏輯1，真(true)，接壓電源}\\\hline \text{x}&\text{不確定值(unknown value)}\\\hline \text{z}&\text{高阻抗(high impedance)，浮接狀態(floating state)}\\\hline \end{array} \) 1.4 Verilog 資料物件與型態 資料物件(data objects) 描述行為過程中所使用的訊號載具 一個物件經過處理再傳到另一個物件 資料型態(data type) 定義資料物件的類型 接線、暫存器、參數等 1.4.1 接線(Nets) 接線(nets)是連接實體元件的連接線 要被驅動才能改變其內部的值 最主要的關鍵字是 wire 一個位元的純量(scalar) 多位元長度的向量(vector) 內定值為 z(高阻抗、浮接) 宣告方式 wire w; // 宣告一條接線，命名為w，內定預設值為z wire x = 1'b0; // 宣告一條接線，命名為x，並指定x為邏輯0 wire a, b, c // 宣告三條接線，命名為a, b, c 1.4.2 暫存器(Registers) 抽象的資料儲存物件(有別於實體暫存器 D flip-flop) 保留一個數值直到下一次指定新值為止 觀念類似 C 語言中的變數 主要的關鍵字是 reg 一個位元的純量(scalar) 多位元長度的向量(vector) 內定值為 x(未知) \(\begin{array}{|l|l|}\hline \text{reg}&\text{可變動位元寬度的無號整數(unsigned integer variable)}\\\hline \text{integer}&\text{32位元寬度的有號整數(signed 32-bit integer variable)，}\\ &\text{算術運算產生2補數結果(2’s complement results))}\\\hline \text{real}&\text{雙倍精確度之有號浮點數}\\ &\text{(signed floating-point variable with double precision)}\\\hline \text{time}&\text{64位元寬度的無號整數(unsigned 64-bit integer variable)}\\\hline \end{array}\) 設計電路請以reg為主，其他類型合成器可能不支援。 宣告方式 reg a; // 宣告 1 個 1 位元暫存器為 a，定位值為 1 位元的 x reg x, y; // 宣告 2 個宣存器，命名為 x, y integer count; // 宣告 1 個整數為 count，值可以為正負 real fraction; // 宣告 1 個浮點數為 fraction，值含小數點 1.4.3 純量與向量(scalar and vector) 純量(scalar) 一個位元的物件 向量(vector) 多個位元的物件 接線(ex. wire) 與 reg 內定一位元 [大數字:小數字]、[小數字:大數字]→[MSB:LSB] 宣告方式 wire a; // 宣告 1 個 1-bits 接線 wire [4:0] x; // 宣告 1 個 5-bits 接線 reg b; // 宣告 1 個 1-bits 暫存器 reg [0:7] y; // 宣告 1 個 8-bits 暫存器 reg [31:0] z; // 宣告 1 個 32-bits 暫存器 1.4.4 陣列(Array) 多個暫存器、接線的聚合體 索引值(index)定義聚合體中的個別物件 支援多維度的陣列 記憶體(memory)、暫存器檔案(register file) 陣列中暫存器、接線的個數 [大數字:小數字]、[小數字:大數字] 宣告方式 // mem_block 是一個包含 128 個暫存器的陣列， // 每個暫存器皆為 32 位元寬 reg [31:0] mem_block [127:0]; // mem_2D 是一個 2 維 4x64 的暫存器陣列， // 每個暫存器皆為 8 位元寬 reg [7:0] mem_2D [3:0][63:0]; 1.4.5 參數(parameter) 定義編譯合成電路時的常數 每次編譯合成前更改，編譯合成器會根據參數值產生相對應的電路 重複使用 關鍵字 parameter 宣告方式 parameter width = 4; wire [width-1:0] a, b; // 接線 a 和 b 的位元寬度，會隨著參數值的改變而變動 reg [width-1:0] y; // 暫存器 y 的位元寬度，會隨著參數值的改變而變動 1.5 模組(Module)、埠(Port) 1.5.1 模組(Module) 一個電路區塊、可以由其他模組組成 連接模組時 考慮模組的輸入與輸出介面 不需要考慮模組內部的詳細電路 電路設計時 只修改模組內部電路 不會改變電路外部及周遭的模組 模組內部的電路描述可包含 訊號資料型態宣告 引用其他模組(邏輯閘) assign 資料處理模型之描述 always 行為模型之描述 函數(function) 與 任務(task) 除訊號宣告需先描述，其他部分撰寫的順序，不影響電路行為 模組宣告 以關鍵字 module 為開頭，在其後加一個識別用的模組名稱(module name) 再來是輸入與輸出埠列(module terminal list)和埠列宣告，接著是模組內部關於電路的描述 以關鍵字 endmodule 做為模組結尾 支援階層`式的設計概念 module module_name(terminal_list) port_declaration(...) param_declaration(optional) data_type_declaration(wire, reg) other_module(logic_gate) assign data_flow_model always behavior_model function, task endmodule 1.5.2 埠(port) 終端點、模組與外界溝通的介面接點(門) 一個模組通常是經由一串的輸入輸出埠稱為埠列(terminal list)來與外界溝通 若模組與外界不需要溝通，則埠列也就不存在(封閉系統) 測試環境(test bench) 埠的宣告 埠的宣告可分為輸入埠(input)、輸出埠(output)、雙向埠(inout)三種。 埠的宣告型態內定為接線(net)的 wire，若需要將訊號儲存起來則埠號型態須宣告成暫存器 reg。 輸入埠和雙向埠只能是接線(net)，不可宣告成暫存器。 輸出埠可以宣告成接線(net)或暫存器。 module full_adder(a, b, carry, sum); // 埠列 input [3:0] a, b; // 輸入埠(4位元向量) input carry // 輸入埠(1位元純量) output [4:0] sum; // 輸出埠(5位元向量) reg [4:0] sum; // 因輸出sum需儲存資料，故宣告成暫存器 ... endmodule 1.6 邏輯閘層次模型 利用關鍵字即可引用基本的邏輯閘元件 基本的邏輯閘關鍵字 and nand or nor not xor xnor 1.6.1 多個輸入邏輯閘(Multiple-Input Gates) and、nand、or、nor、xor、xnor 具有多個純量(scalar)的輸入，但是只有一個純量的輸出 多個輸入邏輯閘的輸出總是放在埠列(post list)的第一個位置，而輸入則是跟在輸出的後面 輸出必須透過接線(wire)連接，輸入無規定 多個輸入邏輯閘的別名可以加或是不加 使用方法 gate_type instance(out, in_1, in_2, in_3, ..., in_n); gate_type inst_1(out_1, in1_1, in1_2, in1_3, ..., in1_n), inst_2(out_2, in2_1, in2_2, in2_3, ..., in2_n), inst_3(out_3, in3_1, in3_2, in3_3, ..., in3_n), ... inst_m(out_m, in_m1, in_m2, in_m3, ..., in_mn); \(\begin{array}{ccc} \underbrace{\text{a, b, c, d}}_{\text{輸入}} \rightarrow \boxed{\text{Multiple-Input Gate}} \rightarrow \underbrace{\text{e}} _{\text{輸出}} \end{array} \) \(\text{and\quad a1(} \underbrace{\text{e}}_{\text{輸出}} \text{, } \underbrace{\text{a, b, c, d}} _{\text{輸入}} \text{);} \) 1.6.2 多個輸出邏輯閘(Multiple-Output Gates) not、buf ...

數位系統與開關電路 在現實世界中，資訊是以類比(Analog)的方式傳遞的，換言之，資訊是連續的 在電腦世界中，資訊是以數位(Digital)的方式傳遞的，也就是開與關或是0或1。 A/D <-> DSP(digital signal processor) <-> D/A Switching Circuit 可分為三個層級： System: 模組Modules、算術運算單元 ALU(Arithmetic logic unit)、記憶體 Memory Logic：邏輯閘(gates) Circuit：電晶體(transistors) 經由 switching network 的設計，可將輸入轉成合乎 spec 的輸出。其中 switching network 的種類包含： Combinational network 輸出是輸入的函數，且表達當下的值。 Sequential network 輸出是輸入的函數，可以表達當下的值或是過去的值。 具有記憶體的行為 Switches 由電晶體來實現 transistor level, gate level, module level… 數字系統與轉換 在現實世界中，最普遍使用的數字系統為十進制(Decimal) 然而在電腦世界中，因為只有代表開與關的 0 與 1，故使用的數字系統是以二進制(Binary)為基礎。 \(N=(a_2a_1a_0)_R=a_2\times R^2+a_1\times R^1+a_0\times R^0\) 負數 N 正數表示 -N 正數加負號 1的補數 2的補數 +0 0000 -0 1000 1111 N/A +1 0001 -1 1001 1110 1111 +2 0010 -2 1010 1101 1110 +3 0011 -3 1011 1100 1101 +4 0100 -4 1100 1011 1100 +5 0101 -5 1101 1010 1011 +6 0110 -6 1110 1001 1010 +7 0111 -7 1111 1000 1001 +8 N/A -8 N/A N/A 1000 二進制算數 當兩數相加或兩數相減時，超過可用bits數時會發生overflow， 例如-3+-4=-4是OK的 但-5+-6=-11會產生溢位 二進制的表達方式 Binary codes Decimal Digit 8421 Code(BCD) 6311 Code Excess-3 Code 2-out-of-5 Code Gray Code 0 0000 0000 0011 00011 0000 1 0001 0001 0100 00101 0001 2 0010 0011 0101 00110 0011 3 0011 0100 0110 01001 0010 4 0100 0101 0111 01010 0110 5 0101 0111 1000 01100 1110 6 0110 1000 1001 10001 1010 7 0111 1001 1010 10010 1011 8 1000 1011 1011 10100 1001 9 1001 1100 1100 11000 1000 Weighted Codes 8421 Code 與 6311 都是 Weighted Code，代表每4個bit，各自代表的數字， 例：1011 for 8421 = 8 + 0 + 2 + 1 = 11 例：1011 for 6311 = 6 + 0 + 1 + 1 = 8 Excess-3 Codes Excess-3 是以 8421 Code 為基礎下，額外加 3。 使得 i 與 10-i 互為 1 的補數， 0 與 9 為補數。(0011 與 1100) 1 與 8 為補數。(0100 與 1011) 2 與 7 為補數。(0101 與 1010) 3 與 6 為補數。(0110 與 1001) 4 與 5 為補數。(0111 與 1000) Gray Codes 兩相鄰的數只會相差一個 bit 又名 Reflected Binary Codes(RBC)、Unit distance code、Minimum error code 可以減少 switching operation 如何轉換 Gray Code? 參考Leetcode no.89 ASCII table ...

基本邏輯運算 Logic Gates Not Gates Symbol Truth Table \( \def\arraystrecth{1.5}\begin{array}{|c|c|}\hline \text{X}&\overline{\text{X}}\text{or}\text{X’}\\\hline 0&1\\\hline 1&0\\\hline \end{array} \) And Gates Symbol Truth Table \( \def\arraystrecth{1.5}\begin{array}{|c|c|c|}\hline \text{X}&\text{Y}&\text{Z=X}\cdot\text{Y}\\\hline 0&0&0\\\hline 0&1&0\\\hline 1&0&0\\\hline 1&1&1\\\hline \end{array} \) Or Gates Symbol Truth Table \( \def\arraystrecth{1.5}\begin{array}{|c|c|c|}\hline \text{X}&\text{Y}&\text{Z=X+Y}\\\hline 0&0&0\\\hline 0&1&1\\\hline 1&0&1\\\hline 1&1&1\\\hline \end{array} \) 布林表達式與真值表(Boolean Expression and Truth Table) Boolean expression 用 ' 代表 NOT 用 + 代表 OR 用 . 代表 AND 將輸入用上面的運算子表示成算式，如：\((A+C)(B’+C)\) Truth Table \( \def\arraystrecth{1.5}\begin{array}{ccc|cccccc} A&B&C&B’&AB’&AB’+C&A+C&B’+C&(A+C)(B’+C)\\\hline 0&0&0&1&0&0&0&1&0\\ 0&0&1&1&0&1&1&1&1\\ 0&1&0&0&0&0&0&0&0\\ 0&1&1&0&0&1&1&1&1\\ 1&0&0&1&1&1&1&1&1\\ 1&0&1&1&1&1&1&1&1\\ 1&1&0&0&0&0&1&0&0\\ 1&1&1&0&0&1&1&1&1\\ \end{array} \) 基本運算定理 NOT gate 的基本運算定理 \( \boxed{ \def\arraystretch{1.5}\begin{array}{ccc} (x’)’&=&x \end{array} } \) ...

布林表達式的轉換 將文字敘述轉換成布林表達式： \( \def\arraystrecth{1.5}\begin{array}{l} \underbrace{\text{The alarm will ring}}_ {Z} \text{ iff } \underbrace{\text{the power of alarm is on}} _{A} \text{ and } \underbrace{\text{the door is not closed}} _{B’} \\ \text{ or } \underbrace{\text{it is after 6 p.m.}} _{C} \text{ and } \underbrace{\text{the window is not closed}} _{D’} \end{array} \) \(Z=AB’+CD’\) 由真值表開始建構邏輯電路 Truth Table: \( \boxed{ \def\arraystretch{1}\begin{array}{ccc|c|c} A&B&C&f&f’\\\hline 0&0&0&0&1\\ 0&0&1&0&1\\ 0&1&0&0&1\\ 0&1&1&1&0\\ 1&0&0&1&0\\ 1&0&1&1&0\\ 1&1&0&1&0\\ 1&1&1&1&0 \end{array} } \) 利用 1’s 的函數 \(f=A’ BC+AB’ C’+AB’ C+ABC’+ABC\) \(=A’ BC+AB’+AB\) \(=A’ BC+A\) \(=A+BC\) 利用 0’s 的函數 \(f=(A+B+C)(A+B+C’)(A+B’+C)\) \(=(A+B)(A+B’+C)\) \(=A+B(B’+C)\) \(=A+BC\) Minterm 與 maxterm 展開 以 \(F=A’ BC+A\) 為範例 \( \boxed{ \def\arraystretch{1}\begin{array}{c|ccc|c|c|cc} \text{Row No.}&A&B&C&\text{Minterns}&\text{Maxterms}&f&f’\\\hline 0&0&0&0&\text{A’B’C’}=\text{m}_0&\text{A+B+C}=\text{M}_0&0&1\\ 1&0&0&1&\text{A’B’C}=\text{m}_1&\text{A+B+C’}=\text{M}_1&0&1\\ 2&0&1&0&\text{A’BC’}=\text{m}_2&\text{A+B’+C}=\text{M}_2&0&1\\ 3&0&1&1&\text{A’BC}=\text{m}_3&\text{A+B’+C’}=\text{M}_3&1&0\\ 4&1&0&0&\text{AB’C’}=\text{m}_4&\text{A’+B+C}=\text{M}_4&1&0\\ 5&1&0&1&\text{AB’C}=\text{m}_5&\text{A’+B+C’}=\text{M}_5&1&0\\ 6&1&1&0&\text{ABC’}=\text{m}_6&\text{A’+B’+C}=\text{M}_6&1&0\\ 7&1&1&1&\text{ABC}=\text{m}_7&\text{A’+B’+C’}=\text{M}_7&1&0\\ \end{array} } \) ...

布林邏輯式的簡化 卡諾圖(Karnaugh Maps, K-maps)是一種簡單、快速的簡化布林邏輯的方法。 SOP 將布林邏輯化簡成最簡SOP(Minimum Sum of products) \(F=A’ B’ C’+A’ B’ C+A’ BC’+AB’ C+ABC’ +ABC\) \(F=A’ B’+B’ C+BC’+AB\) \(F=A’ B’+BC’+AC\) POS 將布林邏輯化簡成最簡POS(Minimum Product of Sums) \(F=(A+B’+C+D’)(A+B’+C’+D’)(A+B’+C’+D)(A’+B’+C’+D)(A+B+C’+D)(A’+B+C’+D)\) \(F=(A+B’+D’)(A+B’+C’)(B’+C’+D)(B+C’+D)\) \(F=(A+B’+D)(A+B’+C’)(C’+D)\) \(F=(A+B’+D’)(C’+D)\) 2或3個變數的卡諾圖 簡化2個變數的布林邏輯式 \(F=A’ B’+A’ B\) 布林代數： \(F=A’ B’+A’ B=A’(B’+B)=A’\) 卡諾圖： \( \boxed{ \def\arraystretch{1.4}\begin{array}{c|c|c} \downarrow B\rightarrow A&0&1&\\\hline 0&\text{A=0,B=0}&\text{A=1,B=0}\\\hline 1&\text{A=0,B=1}&\text{A=1,B=1}\\ \end{array} } \rightarrow \boxed{ \def\arraystretch{1.4}\begin{array}{c|c|c} &A’&A&\\\hline B’&1&0\\\hline B&1&0\\ \end{array} } \rightarrow A' \) 簡化3個變數的布林邏輯式 \(F=\sum m(2,3,6)=A’ BC’+A’ BC+ABC’\) 布林代數： \(F=A’ BC’+A’ BC+ABC’=A’ B+BC’\) 卡諾圖：*注意相鄰以grey code排列 \( \boxed{ \def\arraystretch{1.4}\begin{array}{c|c|c} \downarrow BC\rightarrow A&0&1&\\\hline 00&m_0(000)&m_4(100)\\\hline 01&m_1(001)&m_5(101)\\\hline 11&m_3(011)&m_7(111)\\\hline 10&m_2(010)&m_6(110)\\ \end{array} } \rightarrow \boxed{ \def\arraystretch{1.4}\begin{array}{c|c|c} &A’&A&\\\hline B’ C’&0&0\\\hline B’ C &0&0\\\hline B C &1&0\\\hline B C’ &1&1\\ \end{array} } \rightarrow A’ B+BC' \) 相鄰(Adjacency)的定義 最上面可以與最下面相接，視為相鄰 最左邊可以與最右邊相接，視為相鄰 \( \boxed{ \def\arraystretch{1.4}\begin{array}{c|c|c} &A’&A&\\\hline B’ C’&0&0\\\hline B’ C &0&0\\\hline B C &1&1\\\hline B C’ &0&0\\ \end{array} } \rightarrow BC \) \( \boxed{ \def\arraystretch{1.4}\begin{array}{c|c|c} &A’&A&\\\hline B’ C’&1&0\\\hline B’ C &0&0\\\hline B C &0&0\\\hline B C’ &1&0\\ \end{array} } \rightarrow A’ C' \) 組合的規則 以組合相鄰且以2為倍數為規則 組合的元素愈多愈好 可以重複選(cover) 等效最簡式 \(\boxed{\def\arraystretch{1.4}\begin{array}{c|c|c} &A’&A&\\\hline B’ C’&1&0\\\hline B’ C &1&1\\\hline B C &0&1\\\hline B C’ &1&1\\ \end{array}} \rightarrow F=A’ B’+BC’+AC=A’ C’+B’C+AB \) 4個變數的卡諾圖 \(F=ACD+A’ B+D’\) 以卡諾圖表示 \(\boxed{\def\arraystretch{1.4}\begin{array}{c|c|c|c|c} &A’ B’&A’ B&AB&AB’\\\hline C’ D’&1&1&1&1\\\hline C’ D & &1& & \\\hline C D & &1&1&1\\\hline C D’ &1&1&1&1\\ \end{array}} \quad \boxed{\def\arraystretch{1.4}\begin{array}{c|c|c|c|c} &00&01&11&10\\\hline 00&m_0&m_4&m_{12}&m_8\\\hline 01&m_1&m_5&m_{13}&m_9\\\hline 11&m_3&m_7&m_{15}&m_{11}\\\hline 10&m_2&m_6&m_{14}&m_{10}\\ \end{array}} \) 以 min-term expression 方式解題 解 \(F(a,b,c,d)=\sum m(1,3,4,5,10,12,13)\) \( \boxed{\def\arraystretch{1.4}\begin{array}{c|c|c|c|c} &00&01&11&10\\\hline 00& &1&1& \\\hline 01&1&1&1& \\\hline 11&1& & & \\\hline 10& & & &1\\ \end{array}} \rightarrow F=bc’+a’ b’ d+ab’ c’d \) 考慮 Don’t care 的情況 解 \(F(a,b,c,d)=\sum m(1,3,5,7,9)+\sum d(6,12,13)\) \( \boxed{\def\arraystretch{1.4}\begin{array}{c|c|c|c|c} &00&01&11&10\\\hline 00& & &X& \\\hline 01&1&1&X&1\\\hline 11&1&1& & \\\hline 10& &X& & \\ \end{array}} \rightarrow F=a’d+c’d \) 以 max-term expression 方式解題 解 \(F(a,b,c,d)=\sum m(0,2,3,4,8,10,11,15)=\prod M(1,5,6,7,9,12,13,14)\) \( \boxed{\def\arraystretch{1.4}\begin{array}{c|c|c|c|c} &00&01&11&10\\\hline 00& & &0& \\\hline 01&0&0&0&0\\\hline 11& &0& & \\\hline 10& &0&0& \\ \end{array}} \) \(\rightarrow F’=c’ d+a’ bc+abd’\) \(\rightarrow F=(c+d)(a+b’+c’)(a’+b’+d)\) 基本質函項(essential prime implicants) 名詞定義 蘊函項(Implicant) 任何可以被組合的單一或群元素(意指為 \(F\)的子集。) 質函項(Prime Implicant) 已不能再被組合更多的函項。(意指最大的、框選最多的子集) 基本質函項(Essential Prime Implicant) 一個帶有只能被單一質函項框選到的元素的質函項 \( \boxed{\def\arraystretch{1.4}\begin{array}{c|c|c|c|c} &00&01&11&10\\\hline 00& & &1& \\\hline 01&1&1&1& \\\hline 11& &1&1&1\\\hline 10& &1& & \\ \end{array}} \) 蘊函項：\(A’ C’ D, ABC’, ACD, A’ BC, BD, m_1, m_5, m_6, m_7…. \) 質函項：\(A’ C’ D, ABC’, ACD, A’ BC, BD \) 基本質函項：\(A’ C’ D,ABC’,A’ BC, ACD\) 簡化原則 因為有可能存在多個等效的最簡式，所以： 盡可能將式子展開成質函項(Prime implicants)。 用盡可能最少的質函項來表式布林函式。 例題 \( \boxed{\def\arraystretch{1.4}\begin{array}{c|c|c|c|c} &00&01&11&10\\\hline 00& &1&1& \\\hline 01&1&1&1& \\\hline 11&1& &1&1\\\hline 10& & &1&1\\ \end{array}} \rightarrow F=A’ B’ D+BC’+AC \) 5個變數的卡諾圖 表示法1 表示法2

概要 當變數愈來愈多時，很難依靠人眼判斷，所以必須計設系統化的簡化過程讓電腦運行。 系統化的簡化過程 輸入：minterm expansion 輸出：minimum SOP 步驟： 找出所有質函項，並試著將和項消除到不能再消，利用\(XY+XY’=X\) 利用質函項圖找出最小解 範例：\(F(a,b,c)=a’ b’ c’ + ab’ c’+ab’ c+ abc\) \( \boxed{ \def\arraystretch{1.4}\begin{array}{c|c|c|c|c} &a’ b’&a’ b&ab&ab’\\\hline c’&1&&&1\\\hline c&&&1&1 \end{array} } \) 所有蘊函項：\(a’ b’ c’, ab’ c’, ab’ c, abc, ab’, b’ c’, ac\) 質函項：\(ab’, b’ c’, ac\) 基本質函項：\(b’ c’, ac\) Min SOP：\(F(a,b,c)=b’ c’+ac\) 決定質函項(prime implicants) 找出所有質函項 將每個 minterm 以二進制表示。 統計每個項的1的數量作為 index 並分群。 將分完群的 minterm 以 index 排列。 從 index 最小開始，往 index + 1 的群，尋找可以用\(XY+XY’=X\)簡化的組合 檢查所有的項都合併成組合，留下來的項即為質函項。 重複步驟 4 到 步驟 5 直到沒有函項可以合併。 被打勾表示不是質函項(prime implicants) 範例：\(f(a,b,c,d)=\sum m(0,1,2,5,6,7,8,9,10,14)\) \(f(a,b,c,d)=P1+P2+P3+P4+P5+P6\) \(f(a,b,c,d)=a’ c’ d+a’ bd+a’ bc+cd’+b’ d’+b’ c’\) \(\boxed{ \def\arraystretch{1.4}\begin{array}{c|cc} &\text{Column I}\\\hline m_0&0000&\checkmark\\\hline m_1&0001&\checkmark\\ m_2&0010&\checkmark\\ m_8&1000&\checkmark\\\hline m_5&0101&\checkmark\\ m_6&0110&\checkmark\\ m_9&1001&\checkmark\\ m_{10}&1010&\checkmark\\\hline m_7&0111&\checkmark\\ m_{14}&1110&\checkmark \end{array} }\) \(\boxed{ \def\arraystretch{1.4}\begin{array}{c|cc} &\text{Column II}\\\hline m_0,m_1&000.&\checkmark\\ m_0,m_2&00.0&\checkmark\\ m_0,m_8&.000&\checkmark\\\hline m_1,m_5&0.01&\text{P1}\\ m_1,m_9&.001&\checkmark\\ m_2,m_6&0.10&\checkmark\\ m_2,m_{10}&.010&\checkmark\\ m_8,m_9&100.&\checkmark\\ m_8,m_{10}&10.0&\checkmark\\\hline m_5,m_7&01.1&\text{P2}\\ m_6,m_7&011.&\text{P3}\\ m_6,m_{14}&.110&\checkmark\\ m_{10},m_{14}&1.10&\checkmark \end{array} }\) \(\boxed{ \def\arraystretch{1.4}\begin{array}{c|cc} &\text{Column III}\\\hline m_0,m_1,m_8,m_9&.00.&\text{P4}\\ m_0,m_2,m_8,m_{10}&.0.0&\text{P5}\\ \sout{m_0,m_8,m_1,m_9}&\sout{.00.}\\ \sout{m_0,m_8,m_2,m_{10}}&\sout{.0.0}\\\hline m_2,m_6,m_{10},m_{14}&..10&\text{P6}\\ \sout{m_2,m_{10},m_6,m_{14}}&\sout{..10}\\ \end{array} } \) 質函項圖(表) 範例 \( \boxed{ \def\arraystretch{1.4}\begin{array}{r|l|c|cccccccccc} & & &0&1&2&5&6&7&8&9&10&14\\\hline 0, 1, 8, 9&b’ c’ &P6&\checkmark&\checkmark&&&&&\checkmark&\oplus\\ 0, 2, 8,10&b’ d’ &P5&\checkmark&&\checkmark&&&&\checkmark&&\checkmark\\ 2, 6,10,14&c d’ &P4&&&\checkmark&&\checkmark&&&&\checkmark&\oplus\\ 1, 5&a’ c’ d&P1&&\checkmark&&\checkmark\\ 5, 7&a’ bd &P2&&&&\checkmark&&\checkmark\\ 6, 7&a’ bc &P3&&&&&\checkmark&\checkmark\\ \end{array} } \) \( \boxed{ \def\arraystretch{1.4}\begin{array}{r|l|c|cccccccccc} &&&5&7\\\hline 1,5&a’ c’d&P1&\checkmark\\ 5,7&a’ bd &P2&\checkmark&\checkmark\\ 6,7&a’ bc &P3&&\checkmark\\ \end{array} } \) 優先選 \(\oplus\)的質函項(只出現過一次，代表是基本質函項)，如範例\(P6與P4\)。 刪除選出的質函項後化簡成更簡化的質函項圖。 選可以同時照顧到最多函項的質函項。 \(\rightarrow f(a,b,c)=P2+P4+P6=a’ bd+cd’+b’ c’\) (若沒有基本質函項時，有可以有多個最佳解) Petrick’s method 用來解出質函項圖的所有 min SOP 解。 在使用 Petrick 法前，需將所有基本質函項與其函蓋的 minterms 從表上劃掉。 範例：\(F=\sum m(0,1,2,5,6,7)\) \( \boxed{ \def\arraystretch{1.4}\begin{array}{r|l|c|cccccc} P1&0,1&a’ b’&\checkmark&\checkmark\\ P2&0,2&a’ c’&\checkmark&&\checkmark\\ P3&1,5&b’ c &&\checkmark&&\checkmark\\ P4&2,6&b c’&&&\checkmark&&\checkmark\\ P5&5,7&a c &&&&\checkmark&&\checkmark\\ P6&6,7&a b &&&&&\checkmark&\checkmark\\ \end{array} } \) \(\def\arraystretch{1.4}\begin{array}{l} 0\rightarrow P1+P2\\ 1\rightarrow P1+P3\\ 2\rightarrow P2+P4\\ 5\rightarrow P3+P5\\ 6\rightarrow P4+P6\\ 7\rightarrow P5+P6\\ \end{array}\) \(P=(P1+P2)(P1+P3)(P2+P4)(P3+P5)(P4+P6)(P5+P6)=1\) \(P=(P1+P2P3)(P4+P2P6)(P5+P3P6)\) \(P=P1P4P5+P1P2P5P6+P2P3P4P5+P2P3P5P6+P1P3P4P6+P1P2P3P6+P2P3P4P6+P2P3P6\) 刪掉含有\(P2P3P6\)的和項 \(P=P1P4P5+P1P2P5P6+P2P3P4P5+P1P3P4P6+P2P3P6\) \(\text{min Sol:}\) \(F=P1+P4+P5=a’ b’+bc’+ac\) \(F=P2+P3+P6=a’ c’+b’ c+ab\) 考慮 Don’t Care 的情形 稍微修改一下 Quine-McClusky 方法 找出所有質函項：將DC視為minterms 建構出質函項表：DC不必列在表頭 範例：\(F(A,B,C,D)=\sum m(2,3,7,9,11,13)+\sum d(1,10,15)\) \(\boxed{\def\arraystretch{1.4}\begin{array}{rrl} 1&0001&\checkmark\\ 2&0010&\checkmark\\\hline 3&0011&\checkmark\\ 9&1001&\checkmark\\ 10&1010&\checkmark\\\hline 7&0111&\checkmark\\ 11&1011&\checkmark\\ 13&1101&\checkmark\\\hline 15&1111&\checkmark \end{array}}\) \(\boxed{\def\arraystretch{1.4}\begin{array}{rrl} 1,3&00.1&\checkmark\\ 1,9&.001&\checkmark\\ 2,3&001.&\checkmark\\ 2,10&.01.&\checkmark\\\hline 3,7&0.11&\checkmark\\ 3,11&.011&\checkmark\\ 9,11&10.1&\checkmark\\ 9,13&1.01&\checkmark\\ 10,11&101.&\checkmark\\\hline 7,15&.111&\checkmark\\ 11,15&1.11&\checkmark\\ 13,15&11.1&\checkmark\\ \end{array}}\) \(\boxed{\def\arraystretch{1.4}\begin{array}{rrl} 1,3,9,11&.0.1\\ 2,3,10,11,&.01.\\ 3,7,11,15&..11\\ 9,11,13,15&1..1\\ \end{array}}\) \(\boxed{\def\arraystretch{1.4}\begin{array}{r|cccccc} &2&3&7&9&11&13\\\hline 1,3,9,11&&\checkmark&&\checkmark&\checkmark\\ *2,3,10,11&\oplus&\checkmark&&&\checkmark\\ *3,7,11,15&&\checkmark&\oplus&&\checkmark\\ *9,11,13,15&&&&\checkmark&\checkmark&\oplus\\ \end{array}}\) \(F=B’ C+CD+AD\) 其中 1 被當作 0，10、15當作1。

Multi-level gate circuits 如何決定 level 數： Gate input number & Delay determine level Factoring to accomplish different level AND-OR: 2-level SOP OR-AND: 2-level POS OR-AND-OR: 3-level circuit of AND and OR → no particular ordering 4 level gates: \(\text{Z=(AB+C)(FG+D+E)+H}\) 3 level gates: (case fan out) \(\text{AB(D+E)+C(D+E)+ABFG+CFG+H}\) Factoring 可變成 4-level \(\text{(AB+C)(D+E+FG)+H}\) level & gate & gate inputs 的關係會隨之變化，可根據電路設計的需求改變 範例： \( \begin{array}{llll} f(a,b,c,d)=\sum(1,5,6,10,13,14)\\ f=(c+d)(a’+b+c)(c’+d’)(a+b+c’)&\text{2 levels}&\text{5 gates}&\text{14 gate inputs}\\ f=[c+d(a’+b)][c’+d’(a+b)]&\text{4 levels}&\text{7 gates}&\text{14 gate inputs}\\ f=(c+a’ d+bd)(c’+ad’+bd’)&\text{3 levels}&\text{7 gates}&\text{16 gate inputs}\\ f=a’ c’ d+bc’ d+bcd’+acd’&\text{2 levels}&\text{5 gates}&\text{16 gate inputs}\\ f=c’ d(a’+b)+cd’(a+b)&\text{3 levels}&\text{5 gates}&\text{12 gate inputs} \end{array} \) \( \boxed{\begin{array}{c|c|c|c|c} &00&01&11&10\\\hline 00&m_0&m_4&m_{12}&m_{8}\\\hline 01&m_1&m_5&m_{13}&m_{9}\\\hline 11&m_3&m_7&m_{15}&m_{11}\\\hline 10&m_2&m_6&m_{14}&m_{10} \end{array}}\rightarrow \boxed{\begin{array}{c|c|c|c|c} &00&01&11&10\\\hline 00&&&&\\\hline 01&1&1&1&\\\hline 11&&&&\\\hline 10&&1&1&1 \end{array}}\) \(\boxed{\begin{array}{c|c|c|c|c} &a’ b’&a’ b&ab&ab’\\\hline c’ d’&&&&\\\hline c’ d&1&1&1&\\\hline cd&&&&\\\hline cd’&&1&1&1 \end{array}}\\ =a’ c’ d+bc’ d+bcd’+acd’=(a’+b)c’ d+(a+b)cd’\\ =(c’ d’+ab’ c’+cd+a’ b’ c)’=(c+d)(a’+b+c)(c’+d’)(a+b+c’)\\ =[c+d(a’+b)][c’+d’(a+b)]=(c+a’ d+bd)(c’+ad’+bd’) \) NAND and NOR gates NAND 符號 真值表 \(\boxed{\begin{array}{cc|cc} A&B&AB&\overline{AB}\\\hline 0&0&0&1\\ 0&1&0&1\\ 1&0&0&1\\ 1&1&1&0 \end{array}} \) 布林表達式： \(F=(ABC)’=A’+B’+C’\) NOR 符號 真值表 \(\boxed{\begin{array}{cc|cc} A&B&AB&\overline{AB}\\\hline 0&0&0&1\\ 0&1&1&0\\ 1&0&1&0\\ 1&1&1&0 \end{array}} \) 布林表達式： \(F=(A+B+C)’=A’ B’ C’\) Functionally Complete Sets of Gates 定義：當所有的布林式皆可以被這組邏輯閘組合而成，則這組邏輯閘為 Functionally Complete \(\lbrace{\text{AND, OR, NOT}}\rbrace\) \(\lbrace{\text{AND, NOT}}\rbrace\rightarrow \text{OR}=X+Y=(X’ Y’)’\) \(\lbrace{\text{OR, NOT}}\rbrace\rightarrow \text{AND}=XY=(X’+Y’)’\) \(\lbrace{\text{NAND}}\rbrace\) \(\lbrace{\text{NOR}}\rbrace\) \(\lbrace{\text{3-input Minority Gate}}\rbrace\) Majority Gate and Minority Gate 真值表 \(\boxed{\begin{array}{ccc|cc} A&B&C&F_M&F_m\\\hline 0&0&0&0&1\\ 0&0&1&0&1\\ 0&1&0&0&1\\ 0&1&1&1&0\\ 1&0&0&0&1\\ 1&0&1&1&0\\ 1&1&0&1&0\\ 1&1&1&1&0 \end{array}}\) \(\text{(0, B, C)}\rightarrow\boxed{\text{Minority Gate}}=\text{NAND}=\text{(BC)’=\text{B’+C’}}\) \(\text{(1, B, C)}\rightarrow\boxed{\text{Minority Gate}}=\text{NOR}=\text{(B+C)’=\text{B’C’}}\) \(\text{(A, A, A)}\rightarrow\boxed{\text{Minority Gate}}=\text{NOT}=\text{A’}\) \(\text{(0, B’, C’)}\rightarrow\boxed{\text{Minority Gate}}=\text{AND}=\text{BC}\) \(\text{(1, B’, C’)}\rightarrow\boxed{\text{Minority Gate}}=\text{OR}=\text{B+C}\) 2-level NAND and NOR gates DeMorgon’s Law 等效邏輯閘： \((A+B)’=A’ B’\) \((AB)’=A’+B’\) \(A+B=(A’ B’)’\) \(AB=(A’+B’)’\) \(\text{Ex1: AND/OR}\rightarrow\text{NAND/NAND}\) \(\text{Ex2: AND/OR}\rightarrow\text{NOR/NOR}\) Multi-level NAND and NOR circuits Multi-level NAND and NOR circuits \(\text{to NAND gate}\) \(\text{to NOR gate}\) Multi-output circuit realization ...

Review 組合電路設計 建構真值表將輸出表示成輸入的函式 \(\text{Inputs}\rightarrow\boxed{\text{MUX}}\rightarrow\text{Outputs}\) 用 K-map, Q-M method 等方法得到簡化的布林表達式 多層、多輸出的電路(Multi-level & Multi-outputs) Mininum SOP 起點 Minimum two-level \(\text{AND-OR, NAND-NAND, OR-NAND, NOR-OR}\) Minimum POS 起點 Minimum two-level \(\text{OR-AND, NOR-NOR, AND-NOR, NAND-AND}\) 限制 fan-in 數的電路設計 Ex1 \(\text{用 3 pin 的 NOR Gate 實現}f(a,b,c,d)=\sum m(0,3,4,5,8,9,10,14,15)\) \(\begin{array}{|c|c|c|c|c|}\hline f &00&01&11&10\\\hline 00& 1& 1& 0& 1\\\hline 01& 0& 1& 0& 1\\\hline 11& 1& 0& 1& 0\\\hline 10& 0& 0& 1& 1\\\hline \end{array}\) 從 POS 開始 \(f’=a’ b’ c’ d+ab’ cd+abc’ + a’ bc+a’ cd’\\ \quad=b’ d(a’ c’+ac)+a’ c(b+d’)+abc’\) Ex2 Multiple-Output \(\text{用 2 pin 的 NAND 與 NOT 實現}\) \(f_1=\sum m(0,2,3,4,5)=b’ c’+ab’ +a’ b\\ f_2=\sum m(0,2,3,4,7)=b’ c’+bc+a’ b\\ f_3=\sum m(1,2,6,7)=a’ b’ c+ab+bc’\) \(\begin{array}{|c|c|c|}\hline f_1&0&1\\\hline 00&1&1\\\hline 01& &1\\\hline 11&1& \\\hline 10&1& \\\hline \end{array}\quad \begin{array}{|c|c|c|}\hline f_1&0&1\\\hline 00&1&1\\\hline 01& & \\\hline 11&1&1 \\\hline 10&1& \\\hline \end{array}\quad \begin{array}{|c|c|c|}\hline f_1&0&1\\\hline 00& & \\\hline 01&1& \\\hline 11& &1\\\hline 10&1&1\\\hline \end{array} \) \(f_1=b’(a+c’)+a’ b\\ f_2=(b’+c)(b+c’)+b’ c’\\ f_3=b(a+c’)+a’ b’ c\) 閘延遲與時序圖 邏輯閘必然存在延遲，固然小，但存在。 組合電路 延遲亦可能來自電線，電線愈長則延遲可能愈久。 Control value \(\text{AND gate}\) 的 control value 是 \(0\) \(\text{OR gate}\) 的 control value 是 \(1\) \(\text{AND=2ns}\\ \text{NOR=3ns}\) 若 X 訊號相反時， Z 要到 5ns 訊號才有意義。 組合邏輯中的 Hazards Hazard 是在切換輸入時，因閘延遲而產生的錯誤訊號。 種類 若相鄰兩個 1 不來自同一個邏輯閘(在 K-map 上沒有被框在一起)則會存在 hazard。 \((A,B,C)=(1,0,1)\rightarrow (1,1,1)\) 可將相鄰的所有蘊函項框在一起，避免「一個bit切換」的 hazard 發生。 邏輯電路的模擬與測試 對模擬邏輯電路來說 有明確的電路元素與連線 決定輸入 觀察輸出 輸入值 有四種，分別為： 0 (low) 1 (high) X (unknown) Z (don’t care, High impedence) \(\text{AND } \& \text{ OR } \text{function for 4-value simulation}\) \(\begin{array}{c|cccc} \text{AND}&0&1&X&Z\\\hline 0&0&0&0&0\\ 1&0&1&X&X\\ X&0&X&X&X\\ Z&0&X&X&X\\ \end{array} \qquad \begin{array}{c|cccc} \text{OR}&0&1&X&Z\\\hline 0&0&1&X&X\\ 1&1&1&1&1\\ X&X&1&X&X\\ Z&X&1&X&X\\ \end{array} \) 驗證(verification)與測試(testing) 邏輯電路的輸出錯誤，可以由下面兩種方式偵錯： 驗證(Verification) 錯誤的電路設計 邏輯閘接線錯誤 輸入訊號錯誤 測試(Testing) 邏輯閘缺陷 金屬接線缺陷 已知 \(A=B=C=D=1時，F=0\)

多工器(Multiplexer, MUX) 一個 \(2^n\text{ to }1\) 多工器，需要有 n 個控制項(選項器) \(\begin{array}{c|c|l} \text{MUX}&\text{sel}&\text{Output}\\\hline \text{2 to 1}&1&A’ I_0+AI_1\\\hline \text{4 to 1}&2&A’ B’ I_0+A’ BI_1+AB’ I_2+ABI_3\\\hline \text{8 to 1}&3&A’ B’ C’ I_0+A’ B’ CI_1+…\\\hline 2^n\text{ to 1}&n&\sum_{k=0}^{2^n-1}m_kI_k \end{array}\) quad multiplexer 多了一個致能(enable, en)來控制多工器 用 4-1 多工器實現三個變數函式 代數展開 \(\begin{array}{rl} F(A,B,C)&=A’ B’+AC\\ &=A’ B’(C+C’)+A(B+B’)C\\ &=A’ B’\cdot1+A’ B\cdot0+AB’ C+ABC \end{array}\) 真值表法 \(\begin{array}{|cccc:cc|}\hline &A&B&C&F\\\hline &0&0&0&1\\ I_0&0&0&1&1&1\\\hline &0&1&0&0\\ I_1&0&1&1&0&0\\\hline &1&0&0&0\\ I_2&1&0&1&1&C\\\hline &1&1&0&0\\ I_3&1&1&1&1&C\\\hline \end{array}\) Verilog 4-to-1 MUX implements 3-var function test bench 三態緩衝器(Three state buffer) ...

準備中