Try   HackMD

Chapter 1

Digital System

  • Boolean Algebra, 表示邏輯運算, 如 A AND B = AB
  • Logic Gates, 如 AND, OR, NOT
  • 組合邏輯, 沒有記憶功能, 輸出依賴當前輸入
  • 時序邏輯, 有記憶功能, 如 counter, register

Number Base Conversions

r-base to Decimal

假設是n位整數, m位小數
整數部分: 每個數字乘上 r^n ~ r^0 次
小數部分: 每個數字乘上 r^-1 ~ r^-m 次

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Decimal to r-base

整數部分: num / r, 直到num=0為止, 反著取餘數
小數部分: num * r, 直到num=0為止, 正著取整數

  • code
int num;
string s;
while(num) {
   s = to_string(num % r) + s;
   num /= r;
}
cout << s << "\n";
  • to binary
    Image Not Showing Possible Reasons
    • The image was uploaded to a note which you don't have access to
    • The note which the image was originally uploaded to has been deleted
    Learn More →

    Image Not Showing Possible Reasons
    • The image was uploaded to a note which you don't have access to
    • The note which the image was originally uploaded to has been deleted
    Learn More →
  • to octal
    Image Not Showing Possible Reasons
    • The image was uploaded to a note which you don't have access to
    • The note which the image was originally uploaded to has been deleted
    Learn More →

Octal To Hex

octal -> binary
binary -> hex

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Complements of Numbers

(number N, in base r, having n digits)

radix complement

r's complement = r^n - N

每個數字用(r-1)減掉, + 1

  • 十進位(10補數) (每位數: 用9減掉, + 1)
  • 二進位(2補數) (每位數: NOT, + 1)

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

diminished radix complement

(r-1)'s complement = (r^n - 1) - N

每個數字用(r-1)減掉

  • 十進位(9補數) (每位數: 用9減掉) (k = 9 - k)
  • 二進位(1補數) (每位數: NOT) (k = 1 - k)

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

補數相減

如果要計算M - N in base r

先算 K = M + N的r補數 = M + (r^n - N)

  • 如果 M >= N, r^n 可以省略
    ex.
    M = 725, N = 316, r = 10
    N的10補數 = 10^3 - 316 = 684
    M + N的10補數 = 725 + 684 = 1409, 捨去r^n (進位的1)

  • 如果 M < N, 取r補數, 再加負號
    ex.
    M = 316, N = 725, r = 10
    N的10補數 = 10^3 - 725 = 275
    M + N的10補數 = 316 + 275 = 591,
    取10補數 = 409, 加上負號 = -409

二補數減法 vs 一補數減法

如果一補數減法時, 有end carry, 要加1。
ex. X = 1010100, Y = 1000011

  • 2's
    X - Y -> X + Y的2補數 = 1010100 + 0111101 = 10010001, 捨棄 = 0010001
    Y - X -> Y + X的2補數 = 1000011 + 0101100 = 1101111, 取負2's -> -0010001
  • 1's
    X - Y -> X + Y的1補數 = 1010100 + 0111100 = 10010000, 把end carry加回 = 0010001
    Y - X -> Y + X的1補數 = 1000011 + 0101011 = 1101110, 取負1's -> -0010001

二補數加法

如果要計算x + y in base 2
先算x + y的2補數 = x + (2^n - y)

  • 如果 x > y, 2^n 可以省略
    x + (2^n - y) = 2^n + (x - y) -> x - y

  • 如果 x = y, 0
    x + (2^n - y) = 2^n + (x - y) -> x - y -> 0

  • 如果 x < y, 為 -(y-x)
    x + (2^n -y) = 2^n - (y - x) -> 就是了

Signed Binary Numbers

最大位表示正負號

image

二補數變號

取一次二補數
ex. 6 (0110) -> -6 (1001 + 1 = 1010)

加法

  • signed magnitude:

    • 同號: 兩數的數值部分: 加起來, 正負號部分: 用原本的正負號
    • 異號: 兩數的數值部分: 大數-小數, 正負號部分: 用大數的號

  • 2's complement:
    兩數binary直接加起來, 進位捨棄

減法

  • 2's complement:
    (±A) - (+B) = (±A) + (-B)
    (±A) - (-B) = (±A) + (+B)

Binary Codes

BCD

把每位數用0000 ~ 1001 表示。

k位數的decimal需要4k bits的BCD

ex.

185 = 0001 1000 0101

Chapter 2

Algebraic Properties

Axioms of algebra

  • Commutative Law
    a + b = b + a, a x b = b x a

  • Associative Law
    (a + b) + c = a + (b + c)
    (a x b) x c = a x (b x c)

Equivalent relation

  • Reflexive
    For any element a, it satisfies a = a.

  • Symmetric
    if a = b then b = a must also hold.

  • Transitive
    if a = b and b = c then a = c must also hold.

Boolean Algebra

(a) Element 0 is an identity element with respect to +;
x + 0 = 0 + x = x.
(b) Element 1 is an identity element with respect to •;
x • 1 = 1 • x = x.

Two-valued Boolean Algebra

Binary Operator

  • AND
    F = x * y
x y F
0 0 0
0 1 0
1 0 0
1 1 1
  • OR
    F = x + y
x y F
0 0 0
0 1 1
1 0 1
1 1 1

Unary Operator

  • NOT
    F = x'
x F
0 1
1 0

Basic Theores and Properties of Boolean Algebra

  • Idempotent Law
    x + x = x
    x * x = x
  • Domination Law
    x + 1 = 1
    x * 0 = 0
  • Involution Law
    (x')' = x
  • Associativity Law
    x + (y + z) = (x + y) + z
    x(yz) = (xy)z
  • DeMorgan's Theorem
    (x+y)' = x'y'
    (xy)' = x' + y'
  • Absorption Law
    x + xy = x
    x(x + y) = x
  • Identity Law
    x + 0 = x
    x * 1 = x
  • Complement Law
    x + x' = 1
    x * x' = 0
  • Commutative Law
    x + y = y + x
    xy = yx
  • Distribution Law
    x(y + z) = xy + xz
    x + yz = (x+y)(x+z)

Operator Priority

  • Parentheses: ()
  • NOT
  • AND
  • OR

Boolean Functions

是一個代數式, formed with:

  • Binary variables
  • Binary operators: AND and OR
  • Unary operator: NOT
  • Parentheses: ()

ex.
F = x + y' z

可以用真值表表示, 有2^n row。(n個binary var)
有無限個代數式能表示一個Boolean Function, 能找到最簡的 (cost)
任何Boolean function都可以用AND, OR, NOT表示

Literal (字面量)

Ex.
F = x'y'z + x'yz + xy'

  • 8 literals
  • 1 OR term
  • 3 AND term

complement

The complement of any function F is F'

Ex.
F = x'y'z + x'yz + xy'
F' = (x'y'z + x'yz + xy')' = (x + y + z')(x + y' + z')(x' + y)

Algebraic Manipulation

  • Minimize the numbers of literaals and terms
  • No specific rules to guarantee the optimal results.

Canonical and Standard Form

Minterm, Maxterm

  • Minterm (mi)
    AND
    ex. x, y , minterms are x'y', x'y, xy', xy

  • Maxterm (Mi)
    OR
    ex. x, y , maxterms are x + y, x + y', x' + y, x' + y'

Mi = mi'

image

x y z F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1

Canonical Form (正規形式)

SOM = POM

Sum of Minterm (SOM) (積之和)

取1

F = x'y'z + xy'z' + x'y'z'
= m1 + m4 + m7
= ∑m (1, 4, 7)

Product of Maxterm (POM) (和之積)

取0

F' = (x + y + z)(x + y' + z)(x + y' + z')(x' + y + z')(x' + y' + z)
= M0 * M2 * M3 * M5 * M6
= ∏M (0, 2, 3, 5, 6)

Standard Forms

Sum of Products (SOP)

  • 每個項目都是AND組合
  • 多個AND之間用OR連接

ex. F = y' + zy+ x'yz'

Product of Sums (POS)

  • 每個項目都是OR組合
  • 多個OR之間用AND連接

ex. F = x(y' + z)(x' + y + z' + w)

Other Logic Operations

n binary variables

  • 2^n rows in the truth table
  • 22n functions

image

NAND 與 NOR 容易實現, 比XOR, XNOR更容易用於硬體設計

AND, OR 可擴展多個輸入

任何布林函數都 可以用NAND或NOR實現

  • AND
    F = x * y
x y F
0 0 0
0 1 0
1 0 0
1 1 1
  • OR
    F = x + y
x y F
0 0 0
0 1 1
1 0 1
1 1 1
  • NOT
    F = x'
x F
0 1
1 0
  • Buffer
    F = x
x F
0 0
1 1
  • NAND
    F = (xy)'
x y F
0 0 1
0 1 1
1 0 1
1 1 0
  • NOR
    F = (x + y)'
x y F
0 0 1
0 1 0
1 0 0
1 1 0
  • XOR
    F = xy' + x'y = x ⊕ y
x y F
0 0 0
0 1 1
1 0 1
1 1 0
  • XNOR
    F = xy + x'y' = (x ⊕ y)'
x y F
0 0 1
0 1 0
1 0 0
1 1 1

Chapter 3

一個Function的truth table是unique, 但是algebra expression不unique

最簡的表達式: 最少terms, 越少literals越好。

K-Map

Merging Minterm

如果說某兩行, 有個值與輸出無關
範例: m1, m3

m1: 001 x'y'z, m3: 011 x'yz
因此, m1 + m3 = x'y'z + x'yz = x'z(y' + y) = x'z

x y z F m
0 0 0 0
0 0 1 1 m1
0 1 0 0
0 1 1 1 m3
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 0

Two-Variable Map

image

Three-Variable Map

image
image

Four-Variable Map

image

Implicants

F 是 n 個變數的 Boolean Function

P 是 乘積項

如果使P得到1的所有組合，F也等於1, 則P是F的蘊含項

  • 特性:
    • 涵蓋一個或多個1
    • 每個minterm都是一個implicant

Prime Implicants (PI)

  • 特性:
    • 不能再擴大的implicant (最大可能群組) (符合2的次方)

Essential Prime Implicants (EPI)

  • 特性:
    • 是Prime Implicant
    • 他圈的某些Minterms不被其他Prime Implicants覆蓋
    • 非選不可的Prime Implicant

Ex. F(A,B,C,D) = ∑ (0,2,3,5,7,8,9,10,11,13,15)

image

  1. 找PI
    圈起來的都是PI (CD, B'C, AD, AB', BD, B'D')

  2. 找EPI
    綠色的是EPI (BD, B'D')

    image

  3. 選所有EPI
    有: BD, B'D'

  4. 選最少的PI, 用於覆蓋未被EPI覆蓋的minterm
    至少要: B'C + AB' (不唯一)

所以得到F = BD + B'D' + B'C + AB'

Product of Sums Simplification

image

用 SOP 表示 F'
然後F = (F')'

F' = m0 + m1 = A'B'C'D' + A'B'C'D = A'B'C'
F = (F')' = (A'B'C')' = A + B = C

  1. 用Maxterms

F = (F')' = (m0 + m1)' = M0M1 = (A+B+C+D)(A+B+C+D')=A+B+C

k-map

0: 用SOP表示F'
1: 套用Demorgan, F = (F')' (POS)

ex. F = ∑(0,1,2,5,8,9,10)

image

選0, F' = AB + CD + BD'
F = (F')' = (A'+B')(C'+D')(B'+D)

ex.

image

  • In SOM (選1):
    F = m1 + m3 + m4 + m6 = ∑(1,3,4,6)
  • In POM (選0):
    F' = m0 + m2 + m5 + m7
    F = (F')' = M0M2M5M7 = ∏(0,2,5,7)

ex.

image

  • In SOM (選1):
    F = ∑(1,3,4,6) = m1 + m3 + m4 + m6 = x'z + xz' (SOP)
  • In POM (選0):
    F' = ∑(0,2,5,7) = m0 + m2 + m5 + m7 = xz + x'z'
    F = (F')' = (x'+z')(x+z) (POS)

Don't Care Conditions

可以是0,1的

ex.

F(w,x,y,z) = ∑(1,3,7,11,15)
d(w,x,y,z) = ∑(0,2,5)

-> F可以是 ∑(0,1,2,3,7,11,15), 或是 ∑(1,3,5,7,11,15)

(方便化簡)

期末

3-7 Other Two-level Implementations

AND/NAND/OR/OR 有16種two level form (2^4)

這八種能退化至一個operation
AND-AND -> AND
OR-OR -> OR
AND-NAND -> NAND
OR-NOR -> NOR
NAND-NOR -> AND
NOR-NAND -> OR
NAND-OR -> NAND
NOR-AND -> NOR

這八種不行
AND-OR (SOP)
NAND-NAND (SOP)
OR-AND (POS)
NOR-NOR (POS)
AND-NOR/NAND-AND (AOI)
OR-NAND/NOR-OR (OAI)

建立方法

  • AND-OR
    F = x'y'z' + xyz' (SOP of 1's)

  • NAND-NAND (拿AND-OR 外demorgan)
    F = ((x'y'z')' (xyz')')'

  • OR-NAND (拿NAND-NAND 內demorgan)
    F = ((x+y+z)(x'+y'+z))'

  • NOR-OR (拿OR-NAND 外demorgan)
    F = (x+y+z)' + (x'+y'+z)'

  • OR-AND
    F' = x'y + xy' + z (SOP of 0's)
    F = (F')' = (x + y')(x' + y)z'

  • NOR-NOR (拿OR-AND 外demorgan)
    F = ((x+y’)’ + (x’+y)’ + z)’

  • AND-NOR (F'的NOT)
    F = (F')' = (x'y + xy' +ｚ)’　（AND-NOR)

  • NAND-AND (拿AND-NOR 外demorgan)
    F = (x’y)’(xy’)’(z)’

XOR

x ⊕ y (XOR)
= xy'+x'y (AND-OR-NOT)
= ((xy)’x)’ ((xy)’y)’)’ (NAND)

(x ⊕ y)' (XNOR)
= xy + x'y'

Odd and Even Function

image

Odd : F = A⊕B⊕C
Even: F = (A⊕B⊕C)'

Parity Generation

even-parity:
讓資料跟P 1的數量是偶數

Parity Bit

P = x⊕y⊕z

Parity Check

C = P ⊕ P

C = 1 -> odd number of 1's bit error
C = 0 -> correct or an even number of 1's bit error

image

Chapter 4 - Combination Logic

Combination circuits

ex. Adders, subtracters, comparators, decoders, encoders, multiplexers

Analysis of Combinational Circuits x

Design Procedure x

Binary Adder-Subtractor

半加器 (Binary Half Adder)

將兩個一位元二進制數相加

0 + 0 = 00
0 + 1 = 01
1 + 0 = 01
1 + 1 = 10

S (和)
S = x’y + xy’ = x ⊕ y
C (進位)
C = xy

image

image

全加器 (Binary Full Adder)

將兩個一位元二進制數相加，並根據接收到的低位進位訊號，輸出和、進位輸出

x, y: two significant bits
cin: 低位進位

S = x ⊕ y ⊕ cin
C = x y + y cin + cin x

image

image

用 Half Adder 實作 Full Adder

S = x ⊕ y ⊕ cin
C = z(x ⊕ y) + xy

image

行波進位加法器 (Ripple Carry Adder)

一堆 FA 串一起

image

前瞻進位加法器 (Carry Lookahead Adder) x

Binary Adder/Subtractors

M=0 : addition
M=1 : subtraction

Overflow

兩個正數相加 -> 負數 (超出整數範圍)
兩個負數相加 -> 正數 (超出富庶範圍

V = 1 : overflow
V = 0 : overflow

image

十進位加法器 (Decimal Adder) x

乘法器 (Binary Multiplier) x

Magnitude Comparartor x

Decoders

n input variables -> 2^n outputs

image

  • 1 to 2 line decoder

    D0 = x'
    D1 = x

    image

  • 2 to 4 line decoder

    b0 = a1' a0'
    b1 = a1' a0
    b2 = a1 a0'
    b2 = a1 a0

    image
    image

Enabling

允許訊號傳遞 (用AND)

EN = 0 -> out = 0
EN = 1 -> out = in

out = in * EN

EN in out
0 0 0
0 1 0
1 0 0
1 1 1

Encoders

inverse function of a decoder

image

z = D1 + D3 + D5 + D7
y = D2 + D3 + D6 + D7
x = D4 + D5 + D6 + D7

Priority Encoder (x)

多工器 (Multiplexers)

從多個input中，選取一個input，直接輸出

ex. 4 to 1 multiplexer

function table:

image

boolean expression:
Y = s0' s1' I0 + s0 s1' I1 + s0' s1 I2 + s0 s1 I3

circuit diagram:

image

MUX = Decoder + OR

Boolean Function Implementatiton

Ex. F = Sigma(1,2,6,7)

有兩種做法

  1. n 個 select input ， 2^n 個 data input
  2. n-1 個 select input ， 剩的變數為 data input

select input: x, y
data input: z

image

image

Three-state gates

三種輸出:
0, 1, high-impedance

image

用Three-state gates 實作多工器

image
image

Chapter 5 - Synchronous Sequential Logic

Latches

NOR

S R -> Q
0 0 -> Keep
1 0 -> 1
0 1 -> 0
1 1 -> invalid

image

NAND

S R -> Q
1 1 -> Keep
0 1 -> 1
1 0 -> 0
0 0 -> Invalid

image

D Latch

En D -> Q
0 X -> No Change
1 0 -> 0
1 1 -> 1

image

Flip Flops

負緣觸發 D 型觸發器 (Negative Edge-Triggered D flip-flop)

clk D -> Q（下一狀態）
0 X -> No Change
1 0 -> 0
1 1 -> 1

image

正緣觸發 D 型觸發器 (Positive Edge Triggered D flip-flop)

image

clk D -> Q（下一狀態）
0 X -> No Change
1 0 -> 0
1 1 -> 1

Last changed by 
 
speedcubing
你好! 這裡主要有關於技術, 世貿中心的文件。 如果要開始閱讀，請去Liked Notes(喜歡的文件) 開始。 歡迎閱讀!
0
93

Read more

陳百強

眼淚為你流

Jun 18, 2025
WTC 樓層對照

1

Jun 13, 2025
《91陳百強紫色個體演唱會》

雙星情歌 https://www.bilibili.com/video/BV1wK4y147M3

Jun 8, 2025
(v2ray) v2fly setup

https://github.com/v2fly Docker Compose setup https://github.com/v2fly/docker/ https://hub.docker.com/r/v2fly/v2fly-core v2fly 有提供 official image, 所以... services:

Jun 8, 2025
Read more from speedcubing
Published on HackMD