--- tags: digital-design, logic-design --- [TOC] # Logic and Computer Design Fundamentals (3rd Edition) M. Morris Mano, Charles R. Kime; Person Prentice Hall, 2003 ## Chapter/section list to study ::: spoiler **Study list** - [ ] Chapter 5 - [ ] until 5-4 - Chapter 2 // to known how to implement a [implementer](https://hackmd.io/ilvRD7ObSDOy4ytSnAAjGQ?view#TODO-complemeter-circuit) introduced in Chapter 5 - [x] 2-3 Standard Forms: Sum of Products / Products of Sums - [x] 2-4 Two-Level Circuit Optimization: K-map - [x] :small_red_triangle: 2-5 Map Mauipluation ::: ## Index `literal`: defined in [Minterms](https://hackmd.io/ilvRD7ObSDOy4ytSnAAjGQ?both#Minterms) ## Chapter 5 / Arithmetic functions and circuit ==§5.3 Binary Substration== ### signed-magnitude addition and substration algorithm 此節先從`unsigned number addition and substration`開始介紹，因為`unsigned number arithmetic`在計算上和計算機硬體設計上仍扮演著重要的角色；用於`floating-point units`, **signed-magnitude addition and substration algorithm**, 和`extending the precision of fixed-point numbers`. 於§1.3 Arithmetic Operations，介紹substration of two binary numbers的部份；其中一個「被減數(Minuend)」的值比「減數(Subtrahend)」小的例子： :notes: 此例的numbers皆為unsigned且有簡化成4-bit。 ``` Borrows into: *1(2->1)* 1(2) 0 0 // The borrow `1` should // be treated as 2 units, // shown in (). Minuend: 0 0 1 1 [3] // The number in backets `[]` is Subtrahend: - 1 1 1 0 [14] // corresponding Decimal number. -------------- Difference: 0 1 0 1 [5] ``` > > 由上例，若用小的值減去大的值，得到的結果不如預期的結果，-(11)；**問題是出在most significant position發生borrow，與超出可表示的bit借了2的單位的值** > > 目前已將`borrow`改稱為`EXCHANGE`, `EXCHANGE`當作名詞的其中一個解釋如下： > > > > 2. the changing of money to its equivalent in the currency of another country. > > --> 中文解釋是：「換匯」 > > > > 在減法的應用上，可以解釋成「將欲被借位的一個值兌換成使用的number system的單位（此例為binary，故為`2`）給借位的位元使用」 > > > ref. [Subtraction (Decomposition method) – Sheet 1](https://currieprimary.files.wordpress.com/2015/01/subtraction1.pdf) > [name=asahsieh] [color=red] 比較簡單的減法運算是，減數與被減數互換，計算的結果再加上負號；改用此方法套用到上述例子的結果如下： ``` Borrows into: 0011 Minuend: 1110 Subtrahend: 0011 ---- Correct Difference: -(1011) [-11] ``` 在most significant position發生借位的情況，計算結果可表示為: $M - N + 2^n$ 其中額外加上的$2^n$為借位到most significant position的值。接著，我們想要的數量(magnitude)是$N-M$；可以透過$2^n$減掉上式得到： $2^n - (M-N+2^n) = N-M$ > :thinking_face: 上式是不是很面熟？ > 回憶在此補充的開頭, 提到[可用一個圓來表示可表示的值](https://hackmd.io/kKdARrp2RaGL6vIjqifwjw?both#Figure-21-depicts-the-assignment-of-values-to-bit-patterns-for-a-4-bit-signed-magnitude-format): > > 如[^first]於§2.4 TWO's- AND 1'S-COMPLEMENT NUMBERS的附圖 Fig. 2.5: ![](https://hackmd.io/_uploads/SkQqxClDq.jpg) :star: 小結兩個n-digit numbers的減法的步驟如下： :::success $M-N$, in base *2* can be done as follows: 1. Subtract the subtrahead $N$ from the minuend $M$ 2. **If no end borrow occurs**, $M \geq N$, and the result is nonnegtive and correct 3. **If an end borrow occurs**, then $N > M$, and difference, $M - N + 2^n$, is substracted from $2^n$, and a minus sign different to the result > $2^n - (M-N+2^n) = N - M \rightarrow -(N - M)$ ::: :thinking_face: 此方法硬體如何實作呢？ 需要一個減法器(subtractor)來做初始的減法；此外，當最高位發生借位時，為了更正數量(利用$N-M$)，需要再次使用減法器，或是另外提供一個2's complemeter circuit。 介紹至此(thus far), 實作**加法**和**減法**, 我們會需要一個減法器(subtractor), 一個加法器(adder)，可能還需要一個2's complementer。對應的block diagram如下： ![](https://hackmd.io/_uploads/By-yx1ZP9.jpg) 從上圖；值得一提的是inputs A與B是一起應用在adder及substractor，所以兩個運算可以同時進行。最後再透過multiplexer來決定要用哪邊的輸出。 - :::info 此circuit是否有機會可以再簡化呢？可以的。我們想要共用同一個logic來實現addr及substrator，==可以利用`complement`的想法(notion)==，讓我們繼續看下去。 > 參考節 [Subtraction with Complements](https://hackmd.io/ilvRD7ObSDOy4ytSnAAjGQ?view#Subtraction-with-Complements) 的說明 ::: --- ==**Complements**== > 理論的部份可參考閱讀Jserv老師的[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation#tip1) > 此筆記列出老師沒提及的部份或補充，主要著重在如何用硬體實作`complements` There are two types of complements for each base-*r* system: - the *radix complement*, which we saw earlier for base 2, is referred to *r's complment*; and - the *diminished* radix complement, as the *(r-1)'s complement* > diminished: *to make something smaller or less* ### 1's complement - ++Definition++: given a number *N* in binary having n digits, the *1's complement of N* is defined as $(2^n - 1) - N$ - :thinking_face: (recall) representation of the 1's complement is −(2^N−1^ − 1) to (2^N−1^ − 1) > 其中正數與負數各`-1`的部份是用來表示`+0`和`-0` - 於[^first] §2.4 TWO's- AND 1'S-COMPLEMENT NUMBERS，另一個用圓表示1's complement的附圖 Fig. 2.6: ![](https://i.imgur.com/ebBx9eb.jpg) > 從該分隔線可以觀察到正負兩邊的補數相加的值為(2^n - 1), > 例如： $-0 + 0 = 1111 + 0000 = 1111$；故`-0`的補數為$1111 - 1111 = 0000 = 0$。 - ++Hardware implementation++ 承上述，因為(2^n^ - 1)為一個*n*個1組成的二進數；對欲計算補數的二進數*N*做bitwise減法，每個位元值計算是$1 - 0 = 1$或$1 - 1 = 0$，也就是將原來的bit從`1`變成`0`或從`0`變成`1`。 --> 可應用**NOT 或 compelement 運算**來實作 **2's complement** - ++Definition++: given an *n*-digit number N in binary, the 2's complement of N is defined as $2^n - N\ for\ N\neq0\ and\ 0\ for\ N= 0$. > repost: Fig. 2.5 A 4-bit, 2's-complement number representation system for integers in [^first] > ![](https://hackmd.io/_uploads/SkQqxClDq.jpg) > > 除了`0`(唯一且無補數)，從該分隔線可以觀察到正負兩邊的補數相加的值為(2^n), > > 例如： $1 + (-1) = 0001 + 1為$10000 - 0001 = 1111 = (-1)$。 - ++The reason for the special case of N = 0++ is that the result must have n bits, and subtraction of 0 from 2^n^ gives an (*n* + 1)-bit result, 100...0. > 以4-bit為例，$2^n - 0 = 1_0000 - 0_0000 = 1_0000$ 此special case可以用一個*n*-bit subtractor或是drop掉超出範圍的`1`。 - Comparing with the 1's complement 2's complement can be obtained by *adding 1 to the 1's complement value*, since $2^n - N = {[(2^n - 1) - N] + 1}$, noting that `[(2^n - 1) - N]` is 1's complement of *N*。 - 上述觀念在其他bases上亦適用，更可用於簡化2's complement及減法的硬體 - 有另一個方式亦可求出2's complement 從最低位往最高位，找到第一個1的所在位元；該位元與比它低位的0's(least significant 0's)都不需變動，而比該位元高的位元(all other higher significant bits)，做位元反轉。如下例: ``` N: 1101*1*00 2's complement of N: 0010 1 00 ``` - [ ] How to prove this method? --- ### Subtraction with Complements :goal_net: 在節[signed-magnitude addition and substration algorithm](https://hackmd.io/ilvRD7ObSDOy4ytSnAAjGQ?both#signed-magnitude-addition-and-substration-algorithm)的最後，我們欲達成的目標： :::info 此circuit是否有機會可以再簡化呢？可以的。我們想要共用同一個logic來實現addr及substrator，==可以利用complement的想法(notion)==，讓我們繼續看下去。 ::: 加上了complemnts, 我們可以定義一個binary subtraction的步驟。The subtraction of two n-digit unsigned numbers, $M-N$, in binary can be done as follows: :::info 1. Add the 2's complement of the subtrahend N to the minuend M. This performs $M + (2^n - N) = M - N + 2^n$. > 以下兩個步驟分別是，這步驟(1.)計算完後可能會出現的結果，兩者其一。 2. If M ≥ N, ++the sum produces an *end carry*, $2^n$++. Discard the end carry, leaving result $M-N$. 3. If M < N, the sum does not produce an end carry since it is equal to $2^n-(N-M)$. the 2's complement of $N - M$. Perform a correction, taking the `2's complement` of the sum and placing a minus sign in front to obtain the result, $-(N-M)$. > :notes: why doesn't the sum $2^n-(N-M)$ produce an end carry? > Because of $M < N$, then all of substractions in the formula are large numbers minus smaller numbers, no end carry may be produced ::: There are two examples to demonstrating the Unsigned Binary Subtraction; by 2's Complement Addition and 1's Complment Addition, respectively. 1. Given the two binary number $X = 1010100$ and $Y = 1000011$, perform the subtraction $X-Y$ and $Y-X$ using 2's complement operations. We have > :notes: $X > Y$ ``` X = 1010100 2's complement of Y = 0111101 // 反轉最低位為1的以上位元 Sum = *1* 0010001 scard end carry 2^7 = -*1* 0000000 ----------- Answer: X - Y = 00010001 Y = 1000011 2's complement of X = 0101100 // 反轉最低位為1的以上位元 ------- Sum = 1101111 *There is no end carry* Answer: Y - X = -(2's complement of 1101111) = -0010001 ``` > :star: by the absence of the end carry, that the answer must be change to a negative number 2. Repeat the previous example using 1's complement operation. Here we have > :thinking_face: Remember that the 1's complement is *one less than the 2's complement*. > > --> Discarding the end carry and adding one to the sum > > is referred to as an *end-around carry* ``` X - Y = 1010100 - 1000011 X = 1010100 1's complement of Y = + 0111100 // 反轉所有位元 Sum = *1*0010000 | End-around carry = |--> +1 ----------- Answer: X - Y = 0010001 Y = 1000011 1's complement of X = + 0101011 ------- Sum = 1101110 *There is no end carry* Answer: Y - X = -(1's complement of 1101110) = -0010001 ``` --- ==§5.4 Binary Adder-Subtractors== ### Binary Adder-Subtractor circuit - Adder-Subtractor Circuit - [x] complemeter circuit > reference: [Design a four-bit combinational circuit 2’s complementer. (The output generates the 2’s](https://www.youtube.com/watch?v=WdH1IpN26lg&t=187s) - [x] Do further study on [Chapter 2 / Combinational logic circuits](https://hackmd.io/ilvRD7ObSDOy4ytSnAAjGQ?both#Chapter-2--Combinational-logic-circuits) to known review ==*K-map*== :+1: continue TO-STUDY ## Chapter 2 / Combinational logic circuits ### 2-2 Boolean Algrebra（布林代數） - 得到**簡化的表式** 根據布林代數的規則，對布林表式做操作，相同的函數有機會得到較簡化的表示。表式的內容可以簡化兩個項目： 1. 電路中“閘”的數量 2. 各“閘”的“輸入”的數量 #### Basic Identities of Boolean Algebra ![](https://i.imgur.com/urWtNh1.jpg) :notes: DeMorgan's theorem > 若將complement(NOT operator)帶入到各變數，則變換原operation成另一個operation, AND或OR。 ### 2-3 Standard Forms ==Forword== - A Boolean function expressed algebraically can be written in a variety of ways. - A specific way, **the standard forms**, ++facilitate the simplification procedures for Boolean expressions and frequently result in more desirable logic circuits++ ==What== - categories - product terms e.g. $X\overline{Y}Z$ - sum terms e.g. $X + Y + \overline{Z}$ :notes: The word “product” and “sum” do not imply arithmetic operation in Boolean algebra; instead, they specify the logical operation *AND* and *OR*, respectively. ==Minterms and Maxterms== :::info :spiral_note_pad: Notes literal - a complemented variable symbol $m_j$ The list of minterms for any given $n$ variables: $2^n - 1$ Sum term Where the term ::: :star: Conclusion first: **where the the terms “minterm” and “maxterm” come from:** - A `minterm`: is a function, not equal to `0`, having the **minimum** number of 1's in its truth table; - A `maxterm`: is a function, not equal to `1`, having the **maximum** of 1's in its truth table. ### Minterms Relation between Truth table, Boolean function, and algebraic expression: - *Truth table* defines a *Boolean function*, and an *algebraic expression* is used as medium to make the relation between them. > :notes: from 2-2 Boolean Algebra > - A *Boolean expression* > is an ++algebraic expression++ formed by using binary variables, the constant 0 and 1, the logic operation symbols, and parentheses. > - A *Boolean function* > can be described by a Boolean equation consisting of a binary variable identifying the function followed by an equal sign and a Boolean expression. > > i.e. `A Boolean function (F) = A Boolean expression (B)` > The top-down graph of the *relation* is shown as follows: ```graphviz digraph ER{ rankdir=BT node[shape=box]; Truth_table; Algebraic_expression; Boolean_function; {rank=same;Truth_table;Algebraic_expression;Boolean_function} Truth_table->Algebraic_expression [dir="back"]; Algebraic_expression->Boolean_function; } ``` ++**Definition of `Minterms`**++ ~~- the minimum number of product terms, the logical sum of them for which the function assumes the binary value `1`~~ ![](https://i.imgur.com/0XYxGKd.jpg) From the aboved table, - columns from left to right are: - `Three variables` (denoted by `literal`) - A `literal` is a complemented variable if the *corresponding bit* of the related binary combination is `0` and is an uncomplemented variable if it is `1` As the following capture; the *red* rectangle for `0` and the *blue* rectangle for `1`, respectively: ![](https://i.imgur.com/YN7sidQ.jpg) - `Product Term`: all the variables appear exactly once, either complemented or uncomplemented, is called $minterm$. - *Its ++characteristic property++ is that it represents **exactly one combination of the binary variables in a truth table*** > 每個$minterm$表示的二元變數的組合都是唯一的 - It has the value `1` for that combination and `0` for all others i.e. | X | Y | Z | Product Term | ... | m~0~ | m~1~ | m~2~ | m~3~ | m~4~ | m~5~ | m~6~ | m~7~ | |:---:|:---:|:---:|:--------------------------------------:|:---:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:| | 0 | 0 | 0 | $\overline{X}\overline{Y}\overline{Z}$ | ... | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | $X = 0, Y = 0, Z = 0 \rightarrow m_0 = \overline{X}\overline{Y}\overline{Z}$ $\rightarrow F = m_0 = 1$ - `Symbol` $m_j$: 用來表示各個$minterm$；subscript $j$為一個十進位的值，對應其$minterm$的值為1的時的二進位組合 > e.g. $m_1$ > $\rightarrow\overline{X}\overline{Y}{Z} = 1$ > $X = 0, Y = 0, Z = 1; 001_2= 1_{10}$ - `Truth table` for each minterm: $m_0\ to\ m_7$: These truth tables clearly show that *each minterm is `1` for the corresponding binary combination and `0` for all other combinations*. ![](https://i.imgur.com/q0qmddy.jpg) - *There are $2^n$ distinct minterms for $n$ variable* > the range is similar from a list of the binary numbers ++from 0 through 2^n - 1++ [color=blue] ### Maxterms The ++concept++ is the same as *minterm*, that is: - An algebraic expression representing the function is derived from the table by finding the logical sum of all ~~product terms~~ for which the function assumes the binary value ~~1~~. > Different parts on the *Maxterm* are striked out and replaced as follows: > > - Product terms $\rightarrow$ `Sum terms` > > - 1 $\rightarrow$ `0` > > [color=red] **Maxterms for Three Variables** ![](https://i.imgur.com/zDKGO8J.jpg) - :notes: Note that the value of *the max term* is `0` for the corresponding combination and `1` for all other combinations :notes: Note from Table 2.6 and Table 2.7, ==$M_j = \overline{m_j}$== --- **How to use ++minterms++ and ++maxterms++?** :::spoiler TODO list - [x] Read the stuff - [x] Create note ::: ### Sum of minterms - A Boolean function can be represented algebraically from a given truth table by forming the logical sum of all the minterms. #### :star: *Conclusion first*: Summary of the most important properties of `minterms`: :::info 1. There are 2^n^ minterms for n Boolean variables. These minterms can be evaluated from the binary numbers from 0 to 2^n^ - 1. 2. Any Boolean function can be expressed as a logical sum of minterms 3. The complement of a function contains those minterms not included in the original function. 4. A function that includes all the 2^n^ minterms is equal to logic 1. > 第一個特性已在前面的[Minterms](https://hackmd.io/ilvRD7ObSDOy4ytSnAAjGQ?both#Minterms)節介紹過, 剩下三個特性會在解釋以下範例時提及 > （利用:bulb:來標注）。 ::: Consider the Boolean function *F* in Table 2-8(a) ![Table 2-8(a)](https://hackmd.io/_uploads/SkkS9HPDq.png =200x200) The function is equal to 1 for each of the following binary combinations of the variables X, Y, and Z: 000, 010, 101 and 111. > as the items in the *red circules* $F = \bar{X}\bar{Y}\bar{Z} + \bar{X}Y\bar{Z} + X\bar{Y}Z + XYZ = m_0 + m_2 + m_5 + m_7$ > some possible inputs are listed as follows: > - only one item is equal to 1 > $i.e.\ \bar{X}\bar{Y}\bar{Z} = 1,\ \bar{X}Y\bar{Z} = 1, etc.$ The values of $F$ are: > $F = 1 + 0 + 0 + 0 = 1,\ F = 0 + 1 + 0 + 0 = 1, etc.$ :notes: This can be further abbreviated by only the decimal subscripts of the minterms and bracketed with the symbol Σ: - $F(X,Y,Z) = \Sigma m(0,2,5,7)$ - The symbol `Σ` stands for the *logic sum* (Boolean OR) of the minterms :bulb: 3. The complement of a function contains those minterms not included in the original function. - As the items in the *yellow circules*, - $\bar{F} = m_1 + m_3 + m_4 + m_6 \\ \rightarrow \bar{F}(X,Y,Z) = \Sigma m(1,3,4,6)$ We now take the complement of $\bar{F}$ to obtain $F$: - $F = \overline{m_1+m_3+m_4+m_6}$ $\ \ \ \rightarrow$ Apply the `DeMorgan's theorem` mentioned in [2-2 Boolean Algrebra](https://hackmd.io/ilvRD7ObSDOy4ytSnAAjGQ?view#2-2-Boolean-Algrebra) $F = \bar{m_1}\cdot\bar{m_3}\cdot\bar{m_4}\cdot\bar{m_6}$ $\ \ \ \rightarrow$ From the second :notes: in [Maxterms](https://hackmd.io/ilvRD7ObSDOy4ytSnAAjGQ?view#Maxterms), ==$\overline{m_j} = M_j$== $\begin{split} F &= \bar{M_1}\cdot\bar{M_3}\cdot\bar{M_4}\cdot\bar{M_6}\\ &= ({X}+{Y}+\bar{Z})(X+\bar{Y}+\bar{Z})(\bar{X}+Y+Z)(\bar{X}+\bar{Y}+Z) \end{split}$ - Examples of values of $F$ are (reference TABLE 2-7): - $F = m_0 = 1\cdot1\cdot1\cdot1 = 1$ - $F = m_1 = 0\cdot1\cdot1\cdot1 = 0$ - $F = m_2 = 1\cdot1\cdot1\cdot1 = 1$ - ... --> the above inputs match to value of $F$ in TABLE 2-8 - :notes: This shows the procedure for expressing a Boolean function as a `product of maxterms`. :notes: the $F$ is also can be further abbreviated by only the decimal subscripts of the ++maxterms++ and bracketed with the symbol Π(capital of pi): - $F(X,Y,Z) = \Pi M(1,3,4,6)$ - The symbol `Π` stands for the *logic product* (Boolean AND) of the ++maxterms++ :notes: `Maxterms` are *seldom* used directly when dealing with Boolean functions, as we can *always* replace them with the ==minterm list of $F$== > 通常都使用minterms來表達布林函數 :bulb: 2. Any Boolean function can be expressed as a logical sum of minterms - A function that is not in the sum-of-minterms form can be converted to that form by means of truth table, *since the truth table always specifies the minterms of the function*. - Consider, for example, the Boolean function $E = \bar{Y} + \bar{X}\bar{Z}$ > The expression is not in sum-of-minterms form. because each term does not contain all three variables X, Y, and Z. The truth table for this function is listed in Table 2-8(b) as follows. > ![Table 2-8(b)](https://hackmd.io/_uploads/S1N2qrPP9.png =200x200) From the table, :notes: the values of $E$ are still evaluated from all the $2^n$ minterms, we obtain - the minterms of the function: $E(X,Y,Z) = \Sigma m(0,1,2,4,5)$ - The minterms for complement of $E$ are given by > Note that the total number fo minterms in $E$ and $\bar{E}$ is equal to 2^n (=8) $Remove\ minterms\ list\ of\ \textbf{E}\ from\ Set\ of\ minterms, then$ $\rightarrow E(X,Y,Z) = \Sigma m(3,6,7)$ :bulb: 4. A function that includes all the 2^n^ minterms is equal to logic 1. - An example of two variables, there will be 4 minterms, a function that includes all the minterm is - $G(X,Y) = \Sigma m(0,1,2,3) = \bar{X}\bar{Y} + \bar{X}Y + X\bar{Y} + XY$ - all possible inputs are: - $G(0,0) = 1 + 0 + 0 + 0 = 1$ - $G(0,1) = 0 + 1 + 0 + 0 = 1$ - $G(1,0) = 0 + 0 + 1 + 0 = 1$ - $G(1,1) = 0 + 0 + 0 + 1 = 1$ - ==it's always equal to logic 1== [^first]: _Computer Arithmetic: Algorithms and Hardware Designs_, B. Parhami; Oxford University Press, 2001 ### Sum of Products / Product of Sums :::info **Points of the sections** - To simplify `sum-of-minterms` form, called **Sum of Products** - Two-level implementation or two-level circuit - If a expression is not in sum-of-products forms - If a function is not in sum-of-products-forms - The decision as to whether to use a two-level or multiple-level implementation is complex - The concept of Product of Sums is the inversion of gates in circuit of Sum of Product ::: #### To simplify `sum-of-minterms` form The sum-of-minterms form is a standard algebraic expression, the expression so obtained contains the maximum number of literals in each term and > usually has more product terms than necessary > > by definition, each minterm must include ++all the variables++ of the function The next step is to try to simplify the expression to see whether is possible to ++reduce the number of product terms++ and ++the number of literals in the terms++. The result is a simplified expression in sum-of-products form. This is an *alternative standard form* of expression that ++contains product terms with one, two, or any number of literals++. An example of a Boolean function expressed as a sum of products is: - $F= \bar{Y}+ \bar{X}Y\bar{Z}+ XY$ #### Two-level implementation or two-level circuit Continued from the example in the previous point, the `logic diagram` for a sum-of-products form consists of ++a group of AND gates followed by a single OR gate++, as shown in Figure 2-5. > :notes: Each product term requires an AND gate, except for a term with a single literal ![Figure 2-5](https://hackmd.io/_uploads/SkaX2twD5.jpg) > the circuit configuration is referred to as a **two-level implementation or two-level circuit** > > as the numbers marked on the top of *Figure 2-5* #### If a expression is not in sum-of-products forms If an expression is not in sum-of-products-form, it can be converted to the standard form by means of ++*the distributive laws*++ (reference [Basic-Identities-of-Boolean-Algebra](https://hackmd.io/ilvRD7ObSDOy4ytSnAAjGQ?view#Basic-Identities-of-Boolean-Algebra)) in [2-2-Boolean-Algrebra](https://hackmd.io/ilvRD7ObSDOy4ytSnAAjGQ?view#2-2-Boolean-Algrebra) section). Consider the expression - $F = AB + C(D + E)$ This is not in sum-of-products form, ++because the term `D + E` is part of a product, but is not a single literal++. The converted expression is as follows: - $F = AB + C(D + E) = AB + CD + CE$ The function F is implemented in a nonstandard form in Figure 2-6(a). This requires two AND gates and two OR gates. There are three levels of gating in the circuit. F is implemented in sum-of-products form in Figure 2-6(b). ![Figure 2-6](https://hackmd.io/_uploads/SyJW5cDP5.jpg =500x400) #### The decision as to whether to use a two-level or multiple-level implementation is complex :notes: multiple-level: **three** levels or more Among the issue involved are: - the number of gates - number of gate inputs and - the amount of delay between the time the input values are set and the time the resulting output values appear > :question: the delay is to say the `set-up time` and the [`propagation time`](https://en.wikipedia.org/wiki/Signal_propagation_delay)? > > further reading on [Cost Criteria]() in section 2-4 :notes: Two-level implementations are the *natural form* for certain implementation technologies, as we will see in [Chapter 4](). #### :bookmark_tabs: The concept of Product of Sums is the inversion of gates in circuit of Sum of Product Use a expression as an example: - $F = X(\bar{Y} + Z)(X + Y + \bar{Z})$ - The gate structure of the product-of-sums expression consists of a group of OR gates for the sum term, followed by an AND gate. ![FIGURE 2-7](https://hackmd.io/_uploads/B1a95cDPc.jpg =400x300) ### 2-4 Two-Level Circuit Optimization: K-map :::spoiler **閱讀速記** - 簡化的過程太複雜(awkward) - 缺乏明確的規則來預測接下來的動作 - 不易決定表示式是否已最簡化 - by k-map - 用圖解的方式列出該函式用標準形式(standard form)表達的所有可能 - 使用方式 - 效果 - 最佳化表示式的形式 - SOP or POS - 所以 maps 用於 two-level implementations的最佳化 ::: :::spoiler **本節大綱** :question: 如何最佳化 2-level circuit - :thinking_face: (recall) 如何表示一個電路 - 用`布林表示式`表示後，如何最佳化 - 最佳化的方法為何 - 該法的使用限制 ::: --- - :thinking_face: (recall) 如何表示一個電路 實作一個`布林函數`所用之`數位邏輯閘`的複雜度直接相關於該函數的`代數表式`。雖然一個函數的`真值表`中的值是唯一的，但用代數表示後，可以用*許多不同的形式*表示(如：不同的代數組合)。 - 用`布林表示式`表示後，如何最佳化 `布林表示式`有機會可以利用代數的操作來*簡化*，如 §Section 2-2 中討論的。但簡化的過程太複雜(awkward): - 缺乏明確的規則來預測接下來的動作 - 不易決定表示式是否已最簡化 - 最佳化的方法為何 利用`map` - 方法直覺且可簡化最多到*四個變數*的布林函數 > 5, 6個變數的使用效率不高 - 此*map*的方法亦稱做`Karnaugh map`, 或是`K-map` - K-map - 簡述使用方式 - 此map的圖是由*正方形*所組成，每個正方形代表該函式的一個`minterm`, 如下圖: ![](https://hackmd.io/_uploads/BJpqv8Zs5.png) - :thinking_face: ([recall](https://hackmd.io/ilvRD7ObSDOy4ytSnAAjGQ?both#-Conclusion-first-Summary-of-the-most-important-properties-of-minterms)) 因為任何布林函數都可以用`sum of minterms`來表示, 所以一個布林函數可以由*map*(上圖)得知該函數是由哪些 `minterms` 所組成 :notes: `map` 可以圖示該函式用標準形式(standard form)表達的所有可能；使用者再從中選擇最簡化的形式 - 該法的使用限制 `K-map` 產生的最佳化表示式會是 `sum-of-products` 或是 `product-of-sums` 的形式, 故 `map` 方法只能處理 two-level implementation，無法直接應用在 :question: 一般*三層*或以上的電路 #### Cost Criteria :::spoiler 本節大綱 - *前言*: 如何量化一個電路的成本 - 有哪些*成本量化*的準則 - 準則的介紹 - 根據準則，計算的成本 - 分析準則 - 最簡化的表示式並非唯一，於下節會介紹++這些表示式是否滿足此節介紹的成本量化的觀點++ ::: --- - *前言* 最佳化需要先知道如何量化一個電路的成本，故此節介紹++成本量化的準則(cost criteria)++。引述前幾節 [2-2 Boolean Algrebra（布林代數)](https://hackmd.io/ilvRD7ObSDOy4ytSnAAjGQ?both#2-2-Boolean-Algrebra-%EF%BC%88%E5%B8%83%E6%9E%97%E4%BB%A3%E6%95%B8%EF%BC%89)的*前言* 及 上節中的段落，[The-decision-as-to-whether-to-use-a-two-level-or-multiple-level-implementation-is-complex](https://hackmd.io/ilvRD7ObSDOy4ytSnAAjGQ?both#The-decision-as-to-whether-to-use-a-two-level-or-multiple-level-implementation-is-complex)，提到需要考慮的項目： 計算形式中“字符”和“項目”的數量是量測邏輯電路簡化程度的一個方法；以下介紹++兩個準則++來形式化(formalize)這個觀念。 - 有哪些*成本量化*的準則 1. `literal cost` --> 出現的字符的數目 (counting literal appearances) 例如：上節最後的範例，Figure 2-6；對應的布林表式為： $F = AB + C(D+E)$ 和 $F = AB + CD + CE$ > literal cost 分別是：*5* (A, B, C, D, E) 及 *6* (A, B, C, D, C, E) 此準則的好處是非常簡單，但無法準確地反映所有電路的複雜度；即使是在++相同函數，不同實作方式++的比較。如以下兩個實作函數 `G` 的兩個布林方程: $G = ABCD + \bar{A}\bar{B}\bar{C}\bar{D}$ 及 $G = (\bar{A}+B)(\bar{B}+C)(\bar{C}+D)(\bar{D}+A)$ > literal cost 都為 *8* > > 但若改由兩個方程的`項`來表示`成本`，第一個布林方程有較低的`成本` (2個項 < 4個項) :notes: 為了量測上述方程的不同，這邊定義另一個準則，`gate input cost` 2. `gate input cost` - 定義 - *number of inputs to the gates in the implementation* corresponding exactly to the given equation or equations > 給定的方程對應的實作中，閘的輸入的數量 - 計算方式 - 直接數`邏輯圖`的所有閘的輸入的數量, 或 - 由`sum-of-products`或`product-of-sums`，並計算以下項目的總和: 1. all literal appearances, > 所有字符出現的次數, 即`literal cost` > > 對應於`邏輯圖`上，電路最外層的閘的輸入的數量 2. the number of terms excluding terms that consist only of a single literal, and optionally, > 項的數目，排除只有一個字符的項[因為多個輸入是來自同一個來源(source)，所以不須重複計算成本？] > > 電路內部的閘的輸入的數量 3. the number of distinct complemented single literals. > (非必需的) 各別 complemented 單一字符的數目 > > `反向器 (inverter)` 的數量 - 由上例函數`G`, 兩個布林方程的*gate input cost*分別為： --> $8 + 2 + (4)$, $8 + 4 + (4)$ > 所以函數`G`的第一個方程有較低`gate input cost`，即使`literal cost`一致 - "Gate input cost is currently ++a good measure for contemporary logic implementation++ since it is proportional to the number of *transistors* and *wires* used in implementing a logic circuit" `Gate input cost` 對現今的邏輯實作是一個好的評估成本的方式 > - [ ] 確認是否已有更佳的方法 [name=asahsieh] - ++等比於++實作一個邏輯電路所用到的`電晶體`及`導線`的數目 > 等比於: proportional - 對評估++大於兩層++的電路的成本顯得特別重要 - 當階層增加，`literal cost`佔整體成本的比例會變小；因為輸入會漸漸從外部轉為內部。 > literal cost與層數成反比 - "Later, in Figure 2-29, we introduce complex gate types for which evaluation of the gate input cost from an equation is invalid" 一個 `complex gate` 可能由多個AND, OR和NOT operations所組成；除此之外，方程式的形式比`sum-of-product`和`product-of-sum`還來的複雜，無法用*卡諾圖*($karnaugh\ map$)對該方程式做簡化： > `gate input count` 必須由直接由實作來決定 如下圖*Figure 2-29*；complex gate types 對應的布林方程： - `XOR`, `XNOR`: AND/OR/NOT operation已隱含在該閘中 - 其餘的閘：方程式皆非`sum-of-product`和`product-of-sum` ![Figure 2-29](https://hackmd.io/_uploads/S1f5w_zic.jpg) #### Two-Variable Map - [ ] status ## 中英對照 - Boolean function: 布林函數 - Digital logic gates: 數位邏輯閘 - Algebraic expression: 代數表式 ###### tags: `note` `logic-design`