# 第一章：数制与编码学习笔记

本章讨论位置计数制、有限字长下的数值表示与算术运算，以及常用信息编码和奇偶校验。主要参考《CHAPTER1 数制与编码》课件，页码均采用原课件页序。相关概念的适用条件与表述辨析见第14节；详细讲解见[第一章](/数字电路/数制与编码/)。

## 1. 位串的解释规则

数字电路可以可靠地区分两种状态，约定记成 0、1。位串的整数、负数或字符等意义由相应的解释规则确定。

同一个八位串 `10010110`：

- 按无符号自然二进制解释：128+16+4+2=150。
- 按八位补码解释：150−256=−106。
- 按 8421 BCD 分组为 `1001 0110`：表示十进制 96。

分析位串时，须明确编码方式、总位数、符号约定、二进制点位置与精度处理方式。不同约定可能产生不同的解读结果。

## 2. 基数、数码与位权

来源：课件第 2–18 页。

基数为 b，合法数码的数值为 0 到 b−1；进位规律是“逢 b 进一”。小数点左边第一位位号为 0，右边第一位位号为 −1，位权为 b 的相应整数次幂。

`(aₖ…a₁a₀.a₋₁…a₋ₘ)ᵦ = Σ aᵢbⁱ`。

例如 `10110.101₂`：

```text
位号：  4  3  2  1  0  .  −1    −2    −3
位权： 16  8  4  2  1  .  1/2   1/4   1/8
数码：  1  0  1  1  0  .   1     0     1
贡献： 16  0  4  2  0  .  0.5    0    0.125
```

总值为 22.625。位权由位置决定，与该位数码是否为零无关。

| 进制 | 基数 | 合法数码 | 例子 |
|---|---:|---|---|
| 二进制 | 2 | 0、1 | 101.1₂=5.5₁₀ |
| 八进制 | 8 | 0–7 | 75.6₈=61.75₁₀ |
| 十进制 | 10 | 0–9 | 34.12₁₀ |
| 十六进制 | 16 | 0–9、A–F | 2A.C₁₆=42.75₁₀ |

十六进制中 A、B、C、D、E、F 分别代表 10、11、12、13、14、15，每个仍只占一个数码位置。

n 位无符号整数共有 bⁿ 种状态，取值从 0 到 bⁿ−1。四位八进制最大为 `7777₈=4095₁₀`，而非 4096；4096 要写为五位的 `10000₈`。

注意事项：`102₂`、`89₈` 不是合法表示；“n 位最大值 bⁿ−1”只适用于无符号整数，不能直接套给有符号数或有小数位的数。

## 3. 进制转换方法与精度

来源：课件第 19–35 页。

### 3.1 任意进制到十进制：按权展开

`2A.C₁₆ = 2×16 + 10 + 12/16 = 42.75₁₀`。

步骤：确认数码合法 → 标位权 → 逐位乘权 → 求和。完成后检查量级；例如五位二进制整数必在 0–31 之间。

### 3.2 十进制整数到 b 进制：除基数取余，倒序读

理由：`N=bq+r`，余数 r 为个位数码，商 q 对应其余高位部分。

把 37 转为二进制：

```text
37 ÷ 2 = 18 … 1  ← 最低位
18 ÷ 2 =  9 … 0
 9 ÷ 2 =  4 … 1
 4 ÷ 2 =  2 … 0
 2 ÷ 2 =  1 … 0
 1 ÷ 2 =  0 … 1  ← 最高位
```

从下往上读得 `100101₂`。若要求八位无符号表示，左补零得 `00100101`。复核：32+4+1=37。

### 3.3 十进制小数到 b 进制：乘基数取整，顺序读

理由：若 `f=a₋₁b⁻¹+a₋₂b⁻²+…`，则 `bf=a₋₁+剩余小数`。每乘一次基数，下一位被移到整数位置。

把 0.6875 转为二进制：

```text
0.6875 × 2 = 1.375  → 1，保留0.375
0.375  × 2 = 0.75   → 0，保留0.75
0.75   × 2 = 1.5    → 1，保留0.5
0.5    × 2 = 1.0    → 1，结束
```

从上往下读得 `0.1011₂`，复核 1/2+1/8+1/16=0.6875。带整数与小数时分别转换再拼接，例如 `37.6875₁₀=100101.1011₂`。

### 3.4 有限精度：截断与舍入

约分后的有理数 p/q 能在 b 进制中有限终止，当且仅当 q 的所有质因子都包含在 b 的质因子中。二进制只能有限表示分母为 2 的幂的有理数；十进制 0.1=1/10 含有分母质因子 5，转二进制会循环。

保留 m 位 b 进制小数时，格点间隔为 `Δ=b⁻ᵐ`：

- 向零截断：绝对误差 `<Δ`。对正数，截断值不大于原值。
- 取最近值：绝对误差 `≤Δ/2`；恰好中点时还需约定取舍规则。
- 二进制保留 m 位并按最近值舍入，可再算第 m+1 位：0 舍、1 进；本章中点采用远离零的舍入约定。

例：0.323 连乘 2 的前五位为 `01010`。保留四位、按最近值舍入为 `0.0101₂=0.3125`，绝对误差 0.0105。应写 `≈`，不能写精确等号。

例：将 0.71 截断为小于原数且误差小于 0.005 的二进制小数，最少多少位？

```text
7位：floor(0.71×128)/128 = 90/128 = 0.703125
误差：0.006875，不合格。
8位：floor(0.71×256)/256 = 181/256 = 0.70703125
位串：0.10110101；误差：0.00296875，合格。
```

所以最少八位。条件 `2⁻ᵐ<ε` 是对任意输入的充分保证；求指定输入的最少位数，还要检查其实际误差。

### 3.5 二、八、十六进制分组互转

因为 `8=2³`、`16=2⁴`，三个二进制位对应一个八进制位，四个二进制位对应一个十六进制位。

以小数点为界向左右分组；整数侧最左边缺位补零，小数侧最右边缺位补零。

```text
11100101.01₂
→ 011 | 100 | 101 . 010  → 345.2₈
→ 1110 | 0101 . 0100     → E5.4₁₆

5A.B₁₆
→ 0101 1010.1011₂
→ 001 | 011 | 010 . 101 | 100
→ 132.54₈
```

二进制的三位分组法对应八进制，不能直接用于十进制转换；该方法依赖基数之间的整幂关系。

## 4. 二进制算术

来源：课件第 36–39 页。

加法逢二进一，减法借一当二。算术运算中 `1+1=10₂`，有低位进位时 `1+1+1=11₂`。第二章的逻辑“或”中，`1+1=1`，两者不能混用。

取 A=`11001₂`=25，B=`101₂`=5：

| 运算 | 二进制结果 | 十进制复核 |
|---|---|---|
| A+B | `11001+00101=11110` | 30 |
| A−B | `11001−00101=10100` | 20 |
| A×B | `11001+1100100=1111101` | 125 |
| A÷B | `101`，余0 | 5 |

乘数为 1 的位对应一个移位后的被乘数，最终相加得到积。因此，乘法可分解为移位和加法。对不丢位的无符号数，左移一位等于乘 2；若位宽固定、发生截位，这个等价关系可能失效。

例：四位无符号 `1011+0110=1 0001`。精确和为 17，但四位寄存器保留低四位 0001；最高位进位为 1。若原操作数按补码解释，则是 −5+6=1，无有符号溢出。必须结合解释方式判断。

## 5. 三种带符号编码

来源：课件第 40–50 页。以下 n 始终表示包含最高位的总位数，先讨论整数。

### 5.1 编码规则

| 编码 | 正数 | 负数 −a | 零 |
|---|---|---|---|
| 原码 | 最高位0，低n−1位写绝对值 | 最高位1，低n−1位写绝对值 | 正零和负零 |
| 反码 | 与原码相同 | 对+a的n位正数全部按位取反 | 正零全0，负零全1 |
| 补码 | 与原码相同 | 对+a的n位正数全部按位取反，再在最低位加1 | 零唯一 |

八位的 +26 与 −26：

```text
真值    原码        反码        补码
+26     00011010    00011010    00011010
−26     10011010    11100101    11100110
```

例：六位 −9。+9=`001001`，原码=`101001`，反码=`110110`，补码=`110111`。

“从负数原码只取反数值位、符号位不变”也能生成通常负数的反码；再加一得到补码。但最小负补码没有同位宽原码，模运算定义可统一处理这类边界情况。

### 5.2 取值范围

| 表示 | n位范围 | 四位范围 |
|---|---|---|
| 无符号 | 0 至 2ⁿ−1 | 0…15 |
| 原码、反码 | −(2ⁿ⁻¹−1) 至 +(2ⁿ⁻¹−1) | −7…+7，零有双编码 |
| 补码 | −2ⁿ⁻¹ 至 +(2ⁿ⁻¹−1) | −8…+7，零唯一 |

反码加法在不溢出的条件下，可先直接相加，再把最高进位循环加到最低位。例如五位反码计算 14−5：`01110+11010=1 01000`，回加进位 1 得 `01001`=9。补码不做循环回加，而是直接丢弃最高位以外的进位。

## 6. 补码的本质与加减运算

来源：课件第 43–57 页；相关运算可由模运算统一推导。

### 6.1 编码和解码

令 `M=2ⁿ`。n 位补码存储的是 `U=x mod M`：

- x≥0 时，U=x。
- x<0 时，U=M+x。
- 解码时，若 U<M/2，x=U；否则 x=U−M。

按位权直接解码也可以：最高位权是 `−2ⁿ⁻¹`，其余位仍是正的二进制位权。

例：四位 `1011` 的无符号值为 11，补码值为 11−16=−5；负位权法为 −8+2+1=−5。不能把最高位当负号、低位当绝对值，否则会错读为 −3。

取反加一的推导：对正整数 a 的 n 位串取反得到 `M−1−a`，再加一即得 `M−a`，和 −a 相差 M。因此二者在保留低 n 位时等价。

### 6.2 加减步骤

1. 统一总位数和二进制点位置，检查操作数本身可表示。
2. 将操作数编码为补码。
3. 加法直接相加；减法 A−B 用 `A+按位取反(B)+1`。
4. 只保留低 n 位，最高位以外的进位丢弃。
5. 判断有符号溢出；无溢出时，解码即为真实结果。

四位计算：

```text
2−5：0010 + 1011 = 1101；13−16=−3。
5−2：0101 + 1110 = 1 0011；丢弃最高进位后为3。
```

两次运算一个无最高进位、一个有最高进位，但都没有有符号溢出。

四位补码的最小负数 `1000` 表示 −8。它的相反数 +8 不可在四位补码中表示，故对 `1000` 取反加一仍得到 `1000`，这体现取负溢出，不能解释为 −8=+8。可直接利用无符号值减模数的方法解码，即 8−16=−8；若要写其原码，至少扩为五位。

### 6.3 定点小数与符号扩展

若总 n 位中低 f 位代表小数，则先按整数补码解码，再乘 `2⁻ᶠ`。范围为：

`−2ⁿ⁻¹⁻ᶠ ≤ x ≤ 2ⁿ⁻¹⁻ᶠ−2⁻ᶠ`，最小间隔为 `2⁻ᶠ`。

例：总五位、两位小数表示 −2.75：缩放为整数 −11，五位补码值 `32−11=21`，位串 `10101`，写点形式 `101.01`。按位权为 −4+1+0.25=−2.75。取反加一在最后一位加 1，所代表的数值增量是 0.25，不能在个位加 1。

扩大补码整数位宽，要复制最高符号位：四位 −3=`1101` → 八位 `11111101`。负数左补0会改变数值。若增加小数精度，在最右边补0；运算前需先对齐二进制点。

## 7. 进位 C 与有符号溢出 V

来源：课件第 55–58 页。

有符号溢出的定义：真实数学结果超出当前补码范围。最高进位只描述二进制加法是否跨过模数，不能独自决定有符号结果是否正确。

| 四位运算 | 留下位串 | 补码解码 | 最高进位C | 溢出V |
|---|---|---:|---:|---:|
| 5+7=12 | 1100 | −4 | 0 | 1 |
| −3+2=−1 | 1111 | −1 | 0 | 0 |
| −3−1=−4 | 1100 | −4 | 1 | 0 |
| −7−2=−9 | 0111 | 7 | 1 | 1 |

可靠判据：

- 范围：真实结果在 `−2ⁿ⁻¹…2ⁿ⁻¹−1` 以外即溢出。
- 加法：同号相加、结果异号即溢出；异号相加不溢出。
- 减法：A、B异号且 A−B 的结果符号与 A 不同即溢出；同号相减不溢出。
- 电路：符号位进位输入与输出不同即溢出，`V=C_in⊕C_out`。

例：四位 5+7，低三位 `101+111=1100`，进入符号位的进位1；最高位 `0+0+1` 没有向外进位，输出0，所以 V=1。

反例：−3+2 得到 `0 1111`，最终进位0而符号位1不同，但没有溢出。因此不能无条件用“最终进位与结果符号位比较”代替正确判据。

## 8. 自然二进制与反射格雷码

来源：课件第 59–67 页。

自然二进制方便按位权算数，但相邻整数可能多位一起改变，例如 7=`0111` 到 8=`1000`。本章采用的反射格雷码中，按序相邻的两个码字仅有一位不同，首尾也只差一位。不同位的数量称为汉明距离。

两位格雷顺序：`00、01、11、10`。三位顺序：`000、001、011、010、110、111、101、100`。这将用于卡诺图的行列排序。

反射构造：原序列按顺序排列并添加前缀0，再将原序列逆序排列并添加前缀1。

转换公式：

```text
二进制B→格雷G：最高位保持不变，gᵢ=bᵢ₊₁⊕bᵢ。
格雷G→二进制B：最高位保持不变，bᵢ=bᵢ₊₁⊕gᵢ。
⊕表示异或：相同为0，不同为1。
```

例：`1011₂→1110_G`。反向从最高位1开始：1⊕1=0，0⊕1=1，1⊕0=1，恢复1011。

注意前向使用原二进制相邻两位，反向使用已经恢复的上一位二进制。不能对格雷码直接做自然二进制加一，也不能按8421权求值；相邻只改一位不意味着任意两码都差一位，或自动拥有纠错能力。

## 9. 8421 BCD 的表示与算术

来源：课件第 68–80 页。

BCD 是逐个十进制数字编码。8421 BCD 用四位 `0000…1001` 表示0…9，其余六种 `1010…1111` 不使用。

```text
59₁₀的自然二进制：111011。
59₁₀的8421 BCD：0101 1001。
205.7₁₀的8421 BCD：0010 0000 0101 . 0111。
```

解码前先按四位分组，检查是否含非法码。`1001 0011` 解码为93，不能把整串按自然二进制读为147。

### 9.1 加法：条件满足才加6

原始四位和大于9，或该四位加法向外产生进位，就加 `0110` 修正。原因是二进制四位按16进位，十进制需要按10进位，两者差6。

例5+8：`0101+1000=1101`，大于9；加6得到 `1 0011` → BCD `0001 0011`=13。

例8+9：`1000+1001=1 0001`，即使低四位小于10，已有原始进位，仍要对低四位加6得 `0111` → BCD `0001 0111`=17。

多位例712+989：

1. 个位2+9=11，修正得1，进1。
2. 十位1+8+1=10，修正得0，进1。
3. 百位7+9+1=17，修正得7，进1。
4. 结果1701，BCD为 `0001 0111 0000 0001`。

修正时产生的十进制进位，不构成对同一码组无条件再次加6的依据。应逐个十进制位处理并传递进位，明确每一位的修正条件。

### 9.2 减法：借位后减6

四位二进制借一个高位相当于借16，十进制应借10，因此发生借位的码组需减6。

例255−098：

- 个位5−8，四位模减得13，减6得7，向高位借1。
- 十位5−9−1，四位模减得11，减6得5，向高位借1。
- 百位2−0−1=1，不修正。
- 结果157，BCD为 `0001 0101 0111`。

此例结果非负。处理负BCD结果时要另行约定符号或十进制补码，不能直接当二进制补码读。

## 10. 2421 码与余3码

来源：课件第 69–73、81–84 页。

| 十进制数字 | 8421 | Aiken 2421 | 余3 |
|---:|---|---|---|
| 0 | 0000 | 0000 | 0011 |
| 1 | 0001 | 0001 | 0100 |
| 2 | 0010 | 0010 | 0101 |
| 3 | 0011 | 0011 | 0110 |
| 4 | 0100 | 0100 | 0111 |
| 5 | 0101 | 1011 | 1000 |
| 6 | 0110 | 1100 | 1001 |
| 7 | 0111 | 1101 | 1010 |
| 8 | 1000 | 1110 | 1011 |
| 9 | 1001 | 1111 | 1100 |

### 10.1 Aiken 2421

权为2、4、2、1，但仅列位权不能唯一确定编码，因为重复权使某些数字有多种加权组合。课件采用上表的Aiken映射，`0101…1010` 不使用。

自补性质：数字d的码按位取反，得到9−d的码。例如7码1101取反为0010，表示2。这是十进制逐位的9补关系，不能和“带符号二进制补码”混同。

2421不能不加条件地用普通二进制加法直接运算。反例2+3：`0010+0011=0101` 是非法码；正确5码应为1011。4+6恰好得 `1 0000`，并不能证明所有情况都无需修正。

### 10.2 余3码

将每一位十进制数字d加3，再写成四位自然二进制。解码时把码组读成无符号数后减3；合法范围0011…1100。

自补推导：对d+3的四位取反得到 `15−(d+3)=12−d`，恰好等于 `(9−d)+3`，即数字9−d的余3码。

加法修正：两个码组原始相加多带了6。

- 无四位进位：原始和减3。
- 有四位进位：低四位加3；进位按十进制的普通进位1送入高位运算。

例2+3：`0101+0110=1011`，无进位，减0011得到1000，表示5。

例8+3：`1011+0110=1 0001`，有进位，低四位加0011得0100，表示个位1。若写成完整的两位余3编码，十位1也要编码为0100，结果是 `0100 0100`，不是 `0001 0100`。

## 11. ASCII：字符编号不等于数值

来源：课件第 85–86 页。

ASCII用七位表示128种字符，含数字字符、字母、标点和控制符。字符'5'的编号53，不等于数值5。

| 字符 | 十进制编号 | 十六进制 | 七位ASCII |
|---|---:|---|---|
| 空格 | 32 | 20 | 0100000 |
| '0' | 48 | 30 | 0110000 |
| '5' | 53 | 35 | 0110101 |
| '9' | 57 | 39 | 0111001 |
| 'A' | 65 | 41 | 1000001 |
| 'K' | 75 | 4B | 1001011 |
| 'a' | 97 | 61 | 1100001 |

文本“59”是两个字符，若每个ASCII码左补0放入一个字节，则为 `00110101 00111001`，与数值59的自然二进制和BCD都不同。

ASCII数字字符连续，验证字符是'0'…'9'后，可以用编号减48得到数值。七位ASCII放进八位时，最高位可按协议作为校验位，也可仅补0，并非天然固定为校验位。ASCII不能直接表示汉字。

## 12. 奇偶校验：能发现任意奇数位翻转

来源：课件第 87–90 页。

在信息位之外增加一个校验位，使所有发送位中1的个数满足约定：

- 偶校验：总个数为偶数；`p=d₀⊕d₁⊕…`，全部位异或为0。
- 奇校验：总个数为奇数；`p=1⊕d₀⊕d₁⊕…`，全部位异或为1。

例信息1011001有4个1，校验位放左边：偶校验发送 `01011001`，奇校验发送 `11011001`。

每翻转一位，总体奇偶性就改变一次。因此：

- 任意奇数个不同位置发生翻转，都能检测到，包括校验位自身错误。
- 偶数个不同位置翻转不能由单个奇偶校验发现。
- 只能判断约束是否满足，不能确定哪一位错，因而没有一般纠错能力。
- 检查通过不证明数据正确；同一位置翻两次会恢复，应按最终改变的位置数分析。

例偶校验发送01011001：收到01011000为一位错误，1变成3个，检查失败；收到01011010为两位错误，仍有4个1，检查通过但数据有错。

## 13. 练习与解析

各题参考解析列于题目之后。

### 题1：45.375₁₀转二、八、十六进制

45=32+8+4+1，整数为101101；0.375=1/4+1/8，小数为.011。结果 `101101.011₂=55.3₈=2D.6₁₆`，都是精确表示。

### 题2：0.1₁₀保留四位二进制小数，分别截断、取最近值

格点间隔1/16。0.1×16=1.6，截断取1/16=`0.0001₂`=0.0625，误差0.0375；最近值取2/16=`0.0010₂`=0.125，误差0.025。

### 题3：六位补码19+17和−20−15

六位范围−32…31。19=`010011`，17=`010001`，和 `100100` 解码为−28，但真实和36，溢出。−20=`101100`，−15=`110001`，和 `1 011101`，保留后解码为29，真实和−35，溢出。七位足以容纳这两题结果。

### 题4：求六位、两位小数的补码111010所表示的真值

先按六位补码整数解码：58−64=−6，再除4得−1.5。扩到八位且保持两位小数应为 `11111010`，解码 `(250−256)/4=−1.5`。

### 题5：二进制0101转格雷码；比较下一个状态

0101→0111。下一个自然二进制0110→0101，两个格雷码0111、0101只差一位。

### 题6：8421 BCD计算68+57，再将结果转余3码

个位8+7=15，留5进1；十位6+5+1=12，留2进1，得到125。BCD为 `0001 0010 0101`；余3逐位得到 `0100 0101 1000`。

### 题7：求十进制48的2421码、余3码及余3码按位取反后的真值

Aiken 2421为 `0100 1110`；余3为 `0111 1011`；余3按位取反为 `1000 0100`，解码51=99−48。

### 题8：求字符K的八位偶校验编码，校验位位于最高位

原串有4个1，校验位为0，发送 `01001011`。若三位发生翻转，包括校验位，也一定改变奇偶性而被发现；无法仅凭校验失败定位这三位。

## 14. 来源页段与课件表述辨析

参考课件：[CHAPTER1 数制与编码](/数字电路/数制与编码/)。各部分内容对应页段如下。

| 内容 | PDF页段 |
|---|---|
| 基数、位权、常用进制 | 2–18 |
| 整数、小数转换及精度 | 19–30 |
| 二、八、十六进制互转 | 31–35 |
| 二进制算术 | 36–39 |
| 原码、反码、补码与运算 | 40–54 |
| 溢出与数值约定 | 55–58 |
| 编码、自然二进制与格雷码 | 59–67 |
| BCD与8421算术 | 68–80 |
| 2421及余3 | 81–84 |
| ASCII | 85–86 |
| 可靠性编码、奇偶校验 | 87–90 |

需要带条件理解的表述：

1. 第46页最小负补码不是只能“人为定义”；用负位权或模运算可直接得到。它没有同位宽原码，是因为原码的范围更小。
2. 第57页不能普遍用最终进位与结果符号位比较判溢出；应比较符号位的进位输入与输出，或用范围、操作数符号判据。
3. 第81页Aiken 2421的普通二进制加法并非总是不需修正；2+3即是反例。
4. 第85页七位ASCII加校验位是协议选择，不是所有八位ASCII存储的必然规则。
5. 第90页“能发现单错、不能发现双错”应扩为任意奇数位翻转可检出、偶数位翻转会漏检。

本章学习要求：能够依据表示约定解读位串，解释补码加减法的模运算原理，区分最高进位与有符号溢出，推导BCD加6修正规则，并说明奇偶校验的检错范围与局限。