Number Systems

Digital Number Systems (Radix- $r$ System)

Decimal (十进制)

Binary (二进制):

Octal (八进制): 00, 05, 013.

Hexadecimal (十六进制): 0x0, 0x9A, 0xCB.

Complements 补码

Diminished Radix Complement (反码): $(r - 1)$ ’s Complement

For Decimal System, DRC of $12$ can be $87$ , $987$ …
For Binary System, it’s just a bitwise not (按位取反).

Radix Complement (补码): $r$ ’s Complement

For Decimal System, RC of $12$ can be $88$ , $988$ …
For Binary System, equals to DRC $+ 1$ .

Subtraction with Complements: $M - N = M + (\text{RC of }N)$

$M \ge N$ : 丢弃高位进位
$M < N$ : 加上负号

Binary Codes

BCD Code:

e.g., Decimal $396$ is represented by $0011 ~ 1001 ~ 0110$ .
Addition: 大于 $9$ 时多加个 $6$ 。
Subtraction: Use $10$ ’s Complement

Gray Code:

相邻数字只有一位二进制数的区别。

ASCII Code

Error-Detecting Code:

为了检测数据通信和处理中的错误，有时会在 ASCII 字符中添加一个额外的位（本例中为第八位）来指示其奇偶校验。奇偶校验位（校验位）是消息中包含的额外位，用于使 1 的总数为偶数或奇数。

Binary Logic

AND: $z = x \cdot y = xy$ .

OR: $z = x + y$ .

NOT: $x' = \overline{x}$ .

Logic Gates:

其中：

AND、OR、XOR、Equivalence 有交换律、结合律。
NAND 和 NOR 有交换律，无结合律。

Boolean Algebra

Boolean Axioms and Theorems:

\begin{aligned} (x + y)(x + z) &= xx + xy + xz + yz \\ &= x + xy + xz + yz \\ &= x (1 + y + z) + yz \\ &= x + yz \end{aligned}

Boolean Functions:

e.g., $A'B'C + A'BC +AB'$ has $8$ literals, $3$ product terms; $(A+B'+C)(A'+C)$ has $5$ literals, $2$ sum terms.
Simplication: Minimize literals.

Minterms and Maxterms:

Minterm: an AND term consists of all literals in their normal form or in their complement form. $n$ variables can be combined to form $2^n$ minterm.
Maxterm: an OR term of single variables. $2^n$ maxterms, each is the complement of a minterm.

Canonical Forms:

Sum of Minterms (SOM): Sum of all $1$ terms.
Product of Maxterms (POM): Product of all $0$ terms.
Conversion Between SOM and POM: $\sum(1, 3, 6, 7) = \prod(0, 2, 4, 5)$ .

Standard Forms: terms may have fewer literals than minterms / maxterms.

Sum of Products (SOP): $F_1(x, y, z) = y' + xy + x'yz'$ .
Product of Sums (POS): $F_2(x, y, z) = x (y' + z) (x' + y + z')$ .
Standard forms are not unique.

Simplification

Karnaugh Map (K-Map, 卡诺图) (SOP Simplification):

Two-Variable Map: e.g., $m_1 + m_2 + m_3 = A + B$ .
Three-Variable Map: Minterms are arranged in the Gray-code sequence. e.g., $m_0 + m_2 + m_5 + m_7 = AC + A'C'$ .
Four-Variable Map: e.g., $ABCD + AB'C'D' + AB'C + AB = AB + AC + AD'$ .

POS Simplification: Simplified SOP -> De Morgan’s Theorem -> Simplified POS

Don’t Care Conditions: 不知道的项，是否在组内无关紧要。

Standard Components

One-Hot Representation

Decoders

Binary Code to One-Hot Code.

1-to-2-Line Decoder, 2-to-4 Line Decoder, 3-to-8-Line Decoder, etc.

Decoder with Enable Input:

Multiplexers

取长为 $2^n$ 长度数组中第 $s$ 位的值。

MUX = Decoder + OR gate.

Encoders

One-Hot Code to Binary Code.

Priority Encoder:

Logic Circuits

Combinational Circuits 组合电路

输出在任何时刻都直接且仅由当前的输入组合决定的逻辑电路。

Analysis Procedure:

Derive the truth table.
Determine the function, e.g., using K-Map.
Explain if necessary.

Design Procedure:

Specification: Determine inputs, outputs, and their symbols.
Formulation: Derive the truth table.
Optimization: Derive the simplfied boolean function for each output.
Logic Diagram (optional)

Sequential Circuits 时序电路

Two Categories:

Synchronous Sequential Circuits (同步时序电路): 电路中有一个全局的时钟信号（Clock, clk），它像节拍器一样，产生一连串规律的脉冲。所有的存储元件（比如“触发器” Flip-Flop）都连接到这个时钟上。只有在时钟的特定边缘（通常是上升沿（posedge），即信号从0跳到1的瞬间），触发器才会“睁开眼睛”看一下输入信号，并更新自己的状态。在时钟的其他时间里，即使输入信号变来变去，触发器也“视而不见”，保持原来的状态不变。
Asynchronous Sequential Circuits (异步时序电路): 没时钟。

Storage Elements:

SR Latch: Asynchronous Sequential Circuit.
- S’R’ Latch:
- Clocked SR Latch:
D Latch / Transparent Latch: Asynchronous Sequential Circuit.
D Flip-Flop (DFF): $Q(t + 1) = D$ .
J-K Flip-Flop: $Q(t + 1) = JQ' + K'Q$ .
T Flip-Flop: $Q(t + 1) = T \oplus Q$ .

Triggers:

Level-Triggered: Latches
Edge-Triggered: Flip-Flops

Analysis Procedure:

Derive input equations for FF inputs
Derive state and output equations
Generate state and output tables
Generate state diagram

Models:

Mealy Model: Output depends on both the state and the input.
Moore Model: Output depends on only the state.

FSM State Minimization:

For an FSM with $m$ states, we need $\log_2 m$ FFs.
Reduction: repeatedly remove one of two equivalent states (who share the same next state and output).

Registers & Counters

Counter: A special register that goes through a predetermined sequence of states upon the application of input pulses.

Shift Registers

Serial-in to Serial-out (SISO):

Serial-in to Parallel-out (SIPO):

Parallel-in to Serial-out (PISO):

shift / load: A switcher that decides whether loading or shifting.

Parallel-in to Parallel-out (PIPO):

with Parallel Load:

Universal Shift Register:

Serial to Parallel Converter:

clk for SIPO is faster.

Sequence Generator with Shift Register:

Use a window (FFs) to slide on …1 0 0 1 1 (1 0 0 1 1) 1 0 0…
To generate a sequence with length $N$ , at least $\lceil\log_2 n\rceil$ FFs are needed.
If a state occurs twice or more, then we need more FFs.

Counters

Asynchronous Counters / Ripple Counters / Serial Counters: The signal is transmitted step by step, like a ripple.

e.g. BCD Ripple Counter:
To design a down counter, just replace negative-edge triggered clock with positive-edge triggered clock in the up counter.

Synchronous Counters:

The higher-order bit will only toggle on the next clock cycle when all the lower-order triggers are set to 1.
e.g. 4-bit Binary Synchronous Counter:

Shift Register Counters:

Ring Counter: 1000 -> 0100 -> 0010 -> 0001 -> 1000…
Johnson Counter / Switch-tail Ring Counter: 0000 -> 1000 -> 1100 -> 1110 -> 1111 -> 0111…
They can be used for decoder.

Design Procedure:

Specification: design description or timing diagram
Formulation: develop state diagram
Generate next-state table in form of count sequence
Choose type of Flip-Flop
Derive simplified excitation equations of FFs
Draw logic diagram

Two Level Implementation

NAND & NOR

何逻辑函数或逻辑门（AND, OR, NOT）都可以仅用 NAND 门或仅用 NOR 门来实现。

SOP -> NAND-NAND Circuit

POS -> NOR-NOR Circuit

XOR & XNOR

Application: Parity Checking:

Generator: 利用 XOR 生成校验位 $P$ 。（偶校验）
Checker: 利用 XOR 检查数据位和校验位， $C = 0$ 表示无错（或偶数个错）， $C = 1$ 表示有错。

Other Two Level Inplementations

AND-OR-Invert (AOI): $F'$ 的 SOP -> 取反

OR-AND-Invert (OAI): $F'$ 的 POS -> 取反

Arithmetic Circuit

Binary Adder

Half-adder: 两个 1 位二进制数相加的电路，输出和（Sum）与进位（Carry），不考虑低位进位。

Full-adder: 考虑有低位进位，相当于三个 1 位二进制数相加的电路。可用两个 Half-adder 实现。

Ripple-Carry Adder: 将多个全加器串联实现多位加法。主要缺点是延迟会随着位数线性增加。

Carry Lookahead Adder (CLA): 为了解决行波进位延迟问题，引入了进位生成（Generate）和进位传播（Propagate）的概念，通过并行计算进位信号来提高速度。

Binary Adder/Subtractor

Use 2’s complement. $A - B = A + B' + 1$ .

Overflow:（有符号） $V = C_n \oplus C_{n - 1}$ 时发生了溢出。

Serial Adder: 利用两个 Shift Register 和一个 Full Adder，逐位（从 LSB 到 MSB）进行串行相加的电路结构和时序。

Decimal Adder (BCD)

进位加 6。

Binary Multiplier

类似于手工乘法，通过生成 Partial Product 并将它们移位后相加来实现。

Other Arithmetic Functions

Design by Contraction: 通过将某些输入固定为 0 或 1，简化通用算术模块来实现特定功能（如将加法器简化为增量器）。

Incrementer / Decrementer: 加 1 / 减 1。

Shift Left / Right: 乘以 / 除以 $2^n$ 。

Zero/Sign Extension: 将低位宽数据转换为高位宽数据（无符号数补 0，有符号数复制符号位）。