LogicDesigns

數位系統與開關電路 在現實世界中，資訊是以類比(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) ...

準備中

準備中