开篇：课程公告与上周回顾#

• 课程公告 (Announcements):
  • 第二周将会有辅导课（Tutorials）。
• 上周内容回顾 (Last Week Review):
  • 模拟 vs. 数字 (Analog vs. Digital): 了解两者信号形式的根本区别。
  • 比特 (Bits): 学习了二进制数字（Binary digits）的概念，以及逻辑电平（Logic Levels）和数字波形（Digital Waveforms）的表示。
  • 基本逻辑功能 (Basic logic functions): 掌握了三种最基本的逻辑运算：非（NOT）、与（AND）、或（OR）。
  • 组合与时序逻辑功能 (Combinational & sequential logic functions): 初步接触了更复杂的逻辑单元，如比较器、加法器、编码/解码器、多路复用器、触发器、寄存器和计数器。
  • 集成电路 (IC): 了解了可编程电路与固定功能电路的区别。
    • 封装 (Package): 表面贴装（Surface-mounted）和通孔（Through-hole）两种形式。
    • 可编程 (Programmable): PLD（SPLD, CPLD）和FPGA。
    • 固定功能 (Fixed-function): SSI/MSI/VLSI/ULSI 等不同集成规模的芯片。

1.1 什么是数字系统 (Number Systems)?#

数字系统是一种用来表达数字的书写体系。

• 日常生活中: 我们最常用的是十进制（逢十进一），比如时间中的12小时制和60分钟制也是一种数字系统。
• 计算机系统中: 计算机内部使用的是二进制（逢二进一）。为了方便表示和读写，程序员和工程师也频繁使用八进制和十六进制。

1.2 十进制数字 (Decimal Numbers)#

我们最熟悉的十进制是**基数-10（Base-10）**的数字系统。

• 基数 (Base): 10
• 数字 (Digit): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
• 权重 (Weight): 每一位都有一个基于10的幂次的权重，例如个位是10⁰, 十位是10¹, 百位是10²。

例如，数字 5374 可以被分解为： 5374₁₀ = 5 × 10³ + 3 × 10² + 7 × 10¹ + 4 × 10⁰

• 5个“千”（thousands）
• 3个“百”（hundreds）
• 7个“十”（tens）
• 4个“一”（ones）

1.3 通用的 R 进制数字系统 (Base-R Number System)#

所有位置化数字系统（Positional Number System）都遵循相同的规则。我们可以用一个通用的 R 进制来描述它们。

• 基数 (Base): R (R ≥ 2)，代表这个系统有多少个不同的数字符号。
• 数字 (Digit): 范围从 [0, R-1]。例如，十进制的数字是，二进制的数字是。
• 权重 (Weight): 每一位的权重都是 R 的幂次方，即 Rˣ。

一个通用的R进制数 (N)R 可以表示为： (N)R = ... a₂a₁a₀ . a₋₁a₋₂ ... 其值等于： ... + a₂ × R² + a₁ × R¹ + a₀ × R⁰ + a₋₁ × R⁻¹ + a₋₂ × R⁻² + ...

核心概念:

• 十进制 (Decimal): 基数 = 10
• 二进制 (Binary): 基数 = 2
• 八进制 (Octal): 基数 = 8
• 十六进制 (Hexadecimal): 基数 = 16

2.1 二进制数字系统 (Binary Number System)#

计算机内部处理信息的基础。

• 基数 (Base): 2
• 数字 (Digit): 0, 1
• 权重 (Weight): …2², 2¹, 2⁰ . 2⁻¹, 2⁻², 2⁻³…
• 小数点在二进制中被称为二进制点 (binary point)。

二进制到十进制的转换 (Binary-to-Decimal Conversion): 将二进制数的每一位乘以其对应的权重（2的幂），然后相加。

示例: 转换 (10.101)₂ 为十进制 (10.101)₂ = (1 × 2¹) + (0 × 2⁰) + (1 × 2⁻¹) + (0 × 2⁻²) + (1 × 2⁻³) = (1 × 2) + (0 × 1) + (1 × 0.5) + (0 × 0.25) + (1 × 0.125) = 2 + 0 + 0.5 + 0 + 0.125 = (2.625)₁₀

需要记忆的2的幂次方 (Powers of Two): 熟记这些值对于快速进行心算和估算非常有帮助。

• 2⁰ = 1
• 2¹ = 2
• 2² = 4
• 2³ = 8
• 2⁴ = 16
• 2⁵ = 32
• 2⁶ = 64
• 2⁷ = 128
• …
• 2¹⁰ = 1024 (约为 1K)

2.2 二进制计数 (Counting in Binary)#

二进制的计数规则是“逢二进一”。

2.3 十进制到二进制的转换 (Decimal-to-Binary Conversion)#

有两种常用方法可以将十进制整数转换为二进制。

方法一：最大2的幂次方法 (Find the largest power of 2) 不断寻找小于或等于当前十进制数的最大2的幂次方，减去它，然后在对应的二进制位上记为1。

示例: 转换 53₁₀

1. 小于53的最大2的幂是 32 (2⁵)。二进制为 1xxxxx。
   • 53 - 32 = 21
2. 小于21的最大2的幂是 16 (2⁴)。二进制为 11xxxx。
   • 21 - 16 = 5
3. 2³=8, 大于5，所以2³位是0。二进制为 110xxx。
4. 小于5的最大2的幂是 4 (2²)。二进制为 1101xx。
   • 5 - 4 = 1
5. 2¹=2, 大于1, 所以2¹位是0。二进制为 11010x。
6. 等于1的最大2的幂是 1 (2⁰)。二进制为 110101。
   • 1 - 1 = 0 结果: 53₁₀ = 110101₂

方法二：短除法 (Repeatedly divide by 2) 将十进制数反复除以2，记录每次的余数，直到商为0。将所有余数从下往上排列，即得到对应的二进制数。

示例: 转换 53₁₀

• 53 / 2 = 26 … 余数 1 (最低有效位 LSB)
• 26 / 2 = 13 … 余数 0
• 13 / 2 = 6 … 余数 1
• 6 / 2 = 3 … 余数 0
• 3 / 2 = 1 … 余数 1
• 1 / 2 = 0 … 余数 1 (最高有效位 MSB)

将余数从下往上读：110101。 结果: 53₁₀ = 110101₂

2.4 数字的取值范围 (Values and Range)#

• N位十进制数:
  • 可以表示 10ᴺ 个不同的值。
  • 范围是 [0, 10ᴺ - 1]。
  • 例如，3位十进制数可以表示1000个值，范围是。
• N位二进制数 (N-bit):
  • 可以表示 2ᴺ 个不同的值。
  • 范围是 [0, 2ᴺ - 1]。
  • 例如，3位二进制数可以表示8个值，范围是，即从 000₂ 到 111₂。

2.5 八进制和十六进制 (Octal & Hexadecimal)#

这两个进制因为能和二进制进行非常方便的转换，所以在计算机领域被广泛使用。

• 八进制 (Octal): 基数为8，使用数字 0-7。
• 十六进制 (Hexadecimal): 基数为16，使用数字 0-9 和字母 A-F (A=10, B=11, C=12, D=13, E=14, F=15)。

转换到十进制: 方法与二进制转十进制一样，只是基数换成8或16。

示例 (八进制转十进制): 转换 (2374)₈ (2374)₈ = (2 × 8³) + (3 × 8²) + (7 × 8¹) + (4 × 8⁰) = (2 × 512) + (3 × 64) + (7 × 8) + (4 × 1) = 1024 + 192 + 56 + 4 = (1276)₁₀

示例 (十六进制转十进制): 转换 (E5)₁₆ (E5)₁₆ = (E × 16¹) + (5 × 16⁰) = (14 × 16) + (5 × 1) = 224 + 5 = (229)₁₀

十进制转换到八/十六进制: 方法与十进制转二进制的“短除法”类似，只是除数换成8或16。

示例 (十进制转八进制): 转换 359₁₀

• 359 / 8 = 44 … 余数 7
• 44 / 8 = 5 … 余数 4
• 5 / 8 = 0 … 余数 5 结果 (从下往上读): (547)₈

示例 (十进制转十六进制): 转换 650₁₀

• 650 / 16 = 40 … 余数 10 (即 A)
• 40 / 16 = 2 … 余数 8
• 2 / 16 = 0 … 余数 2 结果 (从下往上读): (28A)₁₆

2.6 二、八、十六进制的快速转换#

这是八进制和十六进制被广泛使用的核心原因：它们和二进制的转换非常简单。

• 因为 8 = 2³，所以每1位八进制数 恰好对应 3位二进制数。
• 因为 16 = 2⁴，所以每1位十六进制数 恰好对应 4位二进制数。

八/十六进制 → 二进制: 将每一位八/十六进制数直接替换成对应的3/4位二进制数。

示例 (八进制转二进制): 7526₈

• 7 → 111
• 5 → 101
• 2 → 010
• 6 → 110 结果: 111101010110₂

示例 (十六进制转二进制): CF8E₁₆

• C (12) → 1100
• F (15) → 1111
• 8 → 1000
• E (14) → 1110 结果: 1100111110001110₂

二进制 → 八/十六进制: 从二进制数的**右侧（小数点处）开始，将二进制数按每3位（转八进制）或4位（转十六进制）**进行分组，不足的在左侧补0，然后将每组替换成对应的八/十六进制数。

示例 (二进制转八进制): 100110011010₂

• 分组: 100 110 011 010
• 转换: 4 6 3 2 结果: 4632₈

示例 (二进制转十六进制): 1100101001010111₂

• 分组: 1100 1010 0101 0111
• 转换: C A 5 7 结果: CA57₁₆

3.1 基本术语#

• 位 (Bit): 一个二进制数字，是计算机中信息的最小单位。
• 半字节 (Nibble): 4个bit。
• 字节 (Byte): 8个bit，是计算机中最常用的数据单位。

关键关系:

• 1个十六进制数字 = 1个半字节 (4 bits)
• 2个十六进制数字 = 1个字节 (8 bits)

最高/最低有效位/字节 (Most/Least Significant Bit/Byte) 在一个二进制数中，最左边的位是 最高有效位 (MSB)，它的权重最大。最右边的位是 最低有效位 (LSB)，权重最小。这个概念同样适用于字节。

3.2 大的2的幂次方估算#

在计算机科学中，我们常用K, M, G, T等前缀来表示大的数量。它们是基于2的幂次的。

• Kilo (K): 2¹⁰ = 1,024 ≈ 10³ (千)
• Mega (M): 2²⁰ = 1,048,576 ≈ 10⁶ (兆)
• Giga (G): 2³⁰ = 1,073,741,824 ≈ 10⁹ (吉)
• Tera (T): 2⁴⁰ ≈ 10¹² (太)
• Peta (P): 2⁵⁰ ≈ 10¹⁵ (拍)
• Exa (E): 2⁶⁰ ≈ 10¹⁸ (艾)

估算练习:

• 2²⁴ 的值是多少?
  • 2²⁴ = 2⁴ × 2²⁰ = 16 × 1 Mega (1M) = 16M (16,777,216)
• 一个32位的整数变量可以表示多大的值?
  • 它可以表示 2³² 个值。
  • 2³² = 2² × 2³⁰ = 4 × 1 Giga (1G) = 4G (约40亿)

4.1 二进制加法 (Addition)#

规则:

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 0，并向高位进1 (carry 1)。(即 1+1=10₂)

示例: 1011₂ + 0011₂ (即 11 + 3)

1
  11   (进位)
2
  1011
3
+ 0011
4
-------
5
  1110   (结果是 14)

4.2 溢出 (Overflow)#

数字系统（如计算机）通常在固定位数 (fixed number of bits)下进行运算。当运算结果超出了这个固定位数所能表示的最大范围时，就会发生溢出。

示例: 4-bit系统计算 11 + 6

• 11₁₀ = 1011₂
• 6₁₀ = 0110₂

1
  111  (进位)
2
  1011
3
+ 0110
4
-------
5
 10001

结果是 10001₂，这是一个5位数。在4-bit系统中，最高位的“1”会丢失，导致结果变成 0001₂ (即1)，这是一个错误的结果。

4.3 减法、乘法和除法#

• 减法 (Subtraction):
  • 规则：10 - 1 = 1 (向高位借1)。
  • 示例：101₂ - 011₂ (5 - 3)

  1
    (借位)
  2
    101
  3
  - 011
  4
  -----
  5
    010 (结果是 2)
  

• 乘法 (Multiplication):
  • 规则：0×0=0, 0×1=0, 1×0=0, 1×1=1。
  • 方法：与十进制乘法类似，通过部分积（Partial products）相加得到结果。

  1
      111   (7)
  2
    x 101   (5)
  3
    -----
  4
      111   (111 * 1)
  5
     000    (111 * 0, 左移一位)
  6
    111     (111 * 1, 左移两位)
  7
    -----
  8
   100011   (结果是 35)
  

• 除法 (Division): 方法与十进制长除法类似。

5.1 符号/数值表示法 (Sign/Magnitude)#

这是一种最直观的表示法。

• 用N位中的最高位 (MSB) 作为符号位 (sign bit)。
  • 0 代表 正数 (+)
  • 1 代表 负数 (-)
• 剩下的 N-1 位表示数的绝对值 (magnitude)。

示例 (4-bit):

• +6 = 0110 (符号位0, 数值110=6)
• -6 = 1110 (符号位1, 数值110=6)

问题:

1. 加法运算复杂: 直接用二进制加法规则会出错。例如 -6 + 6： 1110 + 0110 = 10100 (结果错误)
2. “0”有两种表示:
   • +0 = 0000
   • -0 = 1000 这给比较和运算带来了不便和冗余。

5.2 二进制补码 (Two’s Complement)#

为了解决符号/数值表示法的问题，计算机普遍采用二进制补码来表示有符号数。

• 优点:
  • 加法运算规则统一，可以直接用于正负数相加。
  • “0”只有一种表示 (0000...)。

表示规则:

• 正数：表示方法与无符号数和符号/数值法完全相同。最高位为0。
• 负数：
  • 最高位 (MSB) 的权重是负的，即 -2ᴺ⁻¹。
  • 其他位的权重仍然是正的。

公式: 一个N位补码数A的值为： A = aₙ₋₁ × (-2ᴺ⁻¹) + aₙ₋₂ × (2ᴺ⁻²) + ... + a₀ × (2⁰)

示例 (4-bit):

• 最正数: 0111₂ = 7
• 最负数: 1000₂ = 1×(-8) + 0×4 + 0×2 + 0×1 = -8
• 范围: N位补码数的范围是 [-2ᴺ⁻¹, 2ᴺ⁻¹ - 1]。例如4位补码的范围是[-8, 7]。

5.3 补码的运算：求相反数 (Reverse the Sign)#

如何找到一个补码数对应的相反数？（例如，如何由+3得到-3） 方法：“取反加一”

1. 取反 (Invert): 将所有位0变1，1变0。
2. 加一 (Add 1): 在最低位上加1。

示例: 求 3₁₀ (0011₂) 的相反数 (-3)

1. 取反: 0011 → 1100
2. 加一: 1100 + 1 = 1101 所以 -3 的4位补码表示是 1101₂。 我们可以验证一下：1101₂ = 1×(-8) + 1×4 + 0×2 + 1×1 = -8 + 4 + 1 = -3。

示例: 1001₂ 的十进制值是多少？ 这是一个负数（MSB=1）。要求它的绝对值，可以再次应用“取反加一”。

1. 取反: 1001 → 0110
2. 加一: 0110 + 1 = 0111 0111₂ = 7。所以原数 1001₂ 的值是 -7。

5.4 补码加法 (Two’s Complement Addition)#

补码系统的最大优势在于，无论正负，都可以直接使用二进制加法规则进行运算，符号位也参与运算。 规则:

1. 将十进制数转为补码形式。
2. 直接进行二进制加法。
3. 如果最高位有进位，直接舍弃。

示例1: 7 + (-4)

• 7 -> 0111
• -4 -> (0100 -> 1011 -> 1100)

1
  0111
2
+ 1100
3
------
4
  10011

舍弃最高位的进位，结果是 0011₂ (即3)。正确。

补码加法的溢出: 当两个同符号的数相加，结果的符号却与它们相反时，就发生了溢出。

• 正数 + 正数 = 负数 → 溢出
• 负数 + 负数 = 正数 → 溢出

示例 (8-bit, 范围 [-128, 127]): 125 + 58 125 -> 01111101 58 -> 00111010 01111101 + 00111010 = 10110111 结果的符号位是1（负数），发生了溢出。10110111 实际上是-73，而不是183。

5.5 补码减法 (Subtraction)#

减法可以转换为加法来完成：A - B = A + (-B) 步骤:

1. 求出 B 的相反数 (-B)（使用“取反加一”）。
2. 计算 A + (-B)。

示例: 7 - 3 = 7 + (-3)

• 7 -> 0111
• -3 -> 1101

1
   0111
2
+  1101
3
-------
4
  10100

舍弃进位，结果是 0100₂ (即4)。正确。

5.6 数字系统表示范围比较 (4-bit)#

6.1 定点数 (Fixed-Point Numbers)#

定点数是一种表示小数的方法，其中小数点的位置是隐含的和固定的。

• 事先约定好总位数、整数部分位数和小数部分位数。
• 例如，用8位表示 6.75，约定4位整数和4位小数。
  • 6 的二进制是 0110
  • 0.75 的二进制是 .11 (0.5 + 0.25)
  • 组合起来就是 0110.1100。在计算机中存储为 01101100。

格式:

• Ua.b: 无符号定点数，a位整数，b位小数。
• Qa.b: 有符号（补码）定点数，a位整数（含符号位），b位小数。

应用: 定点数运算速度快，硬件开销小，常用于对性能和成本要求高的领域，如数字信号处理（DSP）、嵌入式系统和一些机器学习应用。

饱和运算 (Saturating Arithmetic): 定点数运算会产生溢出。在某些应用中（如音频和视频处理），溢出产生的“环绕”效果（比如一个很大的正数变成负数）是不可接受的。饱和运算规定，当运算结果超出范围时，就取其能表示的最大值或最小值，而不是环绕。

6.2 浮点数 (Floating-Point Numbers)#

浮点数类似于科学记数法，可以表示更大范围和更高精度的数字。

• 一个数被表示为：± M × Bᴱ
  • M (Mantissa): 尾数，表示数的有效数字。
  • B (Base): 基数，通常是2。
  • E (Exponent): 指数，决定小数点浮动的位置。

与定点数的比较:

• 浮点数:
  • 优点: 动态范围极大，编程更简单。
  • 缺点: 运算更复杂，硬件开销大，功耗高。
  • 适用: 通用计算，科学计算。
• 定点数:
  • 优点: 性能高，功耗低，硬件成本低。
  • 缺点: 动态范围小，程序员需要自己处理溢出问题。
  • 适用: 信号处理，机器学习，视频处理。

6.3 IEEE 754 浮点数标准#

这是目前最广泛使用的浮点数表示标准。以32位单精度浮点数为例：

• 1位 符号位 (Sign): 0为正，1为负。
• 8位 指数位 (Exponent): 使用偏移指数 (Biased exponent) 表示。
• 23位 分数位 (Fraction): 尾数的小数部分。

表示步骤:

1. 将十进制数转为二进制。
2. 写成二进制的科学记数法形式 1.xxxx... × 2ʸ。
   • 规格化 (Normalized): 尾数的整数部分总是1。因为总是1，所以可以省略不存，这被称为隐含的1 (implicit leading 1)，可以多存一位有效数字。
3. 分数位 (Fraction): 填入 xxxx... 部分，不足补0。
4. 指数位 (Exponent):
   • 为了方便比较大小，指数采用偏移表示。对于32位浮点数，偏移量（bias）是 127。
   • 实际存储的指数 = y + 127。
5. 符号位 (Sign): 根据正负填0或1。

示例: 表示 228₁₀

1. 228₁₀ = 11100100₂
2. 科学记数法: 1.11001 × 2⁷
3. 符号位: 0 (正数)
4. 指数位: 7 + 127 = 134。 134₁₀ = 10000110₂
5. 分数位: 11001 (后面补0) -> 11001000000000000000000

最终存储形式 (十六进制): 0x43640000 0 | 10000110 | 11001000000000000000000

特殊值: IEEE 754还定义了0, 无穷大(∞), NaN (Not a Number) 等特殊值的表示。

7.1 BCD 码 (Binary Coded Decimal)#

• 目的: 用二进制来表示十进制数，方便与人类交互（如在数码管上显示数字）。
• 规则: 用4位二进制数来表示每一位十进制数字 (0-9)。
• 编码:
  • 0 -> 0000, 1 -> 0001, …, 9 -> 1001
  • 1010 到 1111 是无效的BCD码。

示例: 170₁₀ 的BCD码

• 1 -> 0001
• 7 -> 0111
• 0 -> 0000 结果: 0001 0111 0000

BCD加法:

1. 按二进制相加。
2. 如果结果小于等于9 (1001)，则结果有效。
3. 如果结果大于9，或者产生了进位，需要 加6 (0110) 进行修正。
   • 为什么加6？: 因为BCD码跳过了6个无效编码（10-15），所以需要加上这个差值来修正进位。

7.2 格雷码 (Gray Code)#

• 特性: 任意两个相邻的码字之间，只有一位 (one bit) 发生变化。
• 优点: 在物理设备（如旋转编码器）中，可以避免因多位同时变化而导致的中间状态误读。
• 应用: 数字通信、位置传感器等。

二进制转格雷码:

1. 最高位不变。
2. 从左到右，下一位格雷码 = 当前位二进制码 异或(XOR) 上一位二进制码。

格雷码转二进制:

1. 最高位不变。
2. 从左到右，下一位二进制码 = 当前位格雷码 异或(XOR) 上一位二进制码。

7.3 ASCII 码 (American Standard Code for Information Interchange)#

• 目的: 为英文字母、数字、标点符号和控制字符提供一个标准的二进制编码。
• 标准: 7位编码，可以表示128个不同的字符。

7.4 错误检测码#

在数据传输和存储过程中，可能会因为噪声等原因导致数据出错（0变1或1变0）。错误检测码可以帮助我们发现这些错误。

• 奇偶校验位 (Parity Bit):
  • 在一段数据后附加一个校验位，使得整段数据中“1”的个数为奇数（奇校验）或偶数（偶校验）。
  • 接收方重新计算“1”的个数，若不符合约定，则说明发生了错误。
  • 缺点: 只能检测出奇数个位的错误，无法检测偶数个位的错误，也无法纠正错误。
• 循环冗余校验 (Cyclic Redundancy Check - CRC):
  • 一种更强大的错误检测方法，可以检测出多位错误和突发错误。
  • 原理：将数据块看作一个多项式，除以一个预定义的“生成多项式”，将得到的**余数（校验和）**附加到数据末尾一起发送。
  • 接收方用接收到的数据（包含校验和）再次除以同一个生成多项式，若余数为0，则认为数据无误。

8.1 本章回顾 (Chapter Review)#

• R进制数字系统
• 十进制、二进制、八进制、十六进制
• 不同进制间的转换
• 二进制算术运算（加、减、乘、除、溢出）
• 有符号数（符号/数值法 vs. 二进制补码）
• 小数表示（定点数 vs. 浮点数）
• BCD码和格雷码
• 错误检测码（奇偶校验，CRC）

8.2 自测练习 (True/False Quiz)#

1. 八进制是一个有8个数字的加权系统。 (√ True)
2. 二进制是一个有2个数字的加权系统。 (√ True)
3. MSB 代表最高有效位。 (√ True)
4. 在十六进制中，9 + 1 = A。 (× False). 9 + 1 = 10，在十六进制中表示为 A。所以 9₁₆ + 1₁₆ = A₁₆。如果题目问9+1=10这个等式本身，那么在十六进制中是不成立的，因为 10₁₆ 代表十进制的16。这个表述有歧义，但通常理解为9后面是A。
5. 二进制数 1111 的2的补码是 0000。 (× False). 对 1111 取反加一：0000 + 1 = 0001。
6. 在一个有符号二进制数中，最右边的位是符号位。 (× False). 是最左边的位 (MSB)。
7. 十六进制系统有16个字符，其中6个是字母。 (√ True) (A, B, C, D, E, F)
8. BCD 代表二进制编码的十进制。 (√ True)
9. 通过验证奇偶校验位可以检测出给定代码中的错误。 (√ True) (可以检测出奇数个错误)
10. CRC 代表循环冗余校验。 (√ True)