Lecture 3：知识 - 数制与编码

This note is currently available in Chinese. The original wording, formulas and diagrams are preserved to avoid an unverified technical translation.

描述：本讲包含进制转换、定点机器数以及检验码。做题先固定字长与小数点位置，再讨论原码、反码、补码或移码；若不固定字长，数值范围没有唯一答案。

2.1 进位计数制与转换

2.1.1 为什么使用二进制

只有 0、1 两种状态，能用具有两个稳定状态的物理器件（高低电平、电荷极性等）可靠实现，成本低。
0/1 与逻辑假/真天然对应，便于逻辑判断和逻辑门运算。
编码规则、算术规则简单，适合由门电路实现。

定义：#基数与位权

$r$ 进制的基数为可用数码数，共有 $0,1,\ldots,r-1$；十进制的基数为 10。
第 $i$ 位的位权为 $r^i$。一个混合数的值是各数码按位权展开之和：

$$ (K_n\cdots K_0.K_{-1}\cdots K_{-m})r=\sum{i=-m}^{n}K_i r^i $$

进制	数码	与二进制关系	常用记法
二进制	0、1	位权为 $2^i$	后缀 `B`
八进制	0–7	3 位二进制对应 1 位八进制	后缀 `O`
十进制	0–9	日常表示	后缀 `D` 常省略
十六进制	0–9、A–F	4 位二进制对应 1 位十六进制	后缀 `H` 或前缀 `0x`

2.1.2 进制转换方法

方向	方法	易错点
任意进制 `->` 十进制	按权展开	小数点右第一位权为 $r^{-1}$
十进制整数 `->` $r$ 进制	除基取余	先得低位，余数自下而上读
十进制小数 `->` $r$ 进制	乘基取整	先得高位，整数部分自上而下读
二进制 `<->` 八/十六进制	每 3 位/4 位分组	必须从小数点向两侧分组，不足位补 0
八进制 `<->` 十六进制	先转二进制再转目标进制	不直接按“位数”硬换

原 PDF 的分组图例：

(1111000010.01101)₂
= (001 111 000 010 . 011 010)₂
= (1702.32)₈

整数侧从小数点向左分组，最左边补 0；小数侧从小数点向右分组，最右边补 0。补位不改变原数的值。

例：

$$ (11011.1)_2=1\times2^4+1\times2^3+0\times2^2+1\times2^1+1\times2^0+1\times2^{-1}=27.5 $$

整数部分在二进制中可连续表示；但十进制小数不一定可用有限位二进制精确表示，例如 $0.1_{10}$ 会无限循环。
反过来，有限二进制小数一定能精确写成十进制分数。例如 $(1.01)2=1+2^{-2}=1.25{10}$。
原 PDF 的除基取余例：$123\div2=61\text{ 余 }1$，$61\div2=30\text{ 余 }1$，$30\div2=15\text{ 余 }0$，$15\div2=7\text{ 余 }1$，$7\div2=3\text{ 余 }1$，$3\div2=1\text{ 余 }1$，$1\div2=0\text{ 余 }1$。余数倒序读得 $123_{10}=1111011_2$。
原 PDF 的乘基取整例：$0.6875\times2=1.375$ 取 1；$0.375\times2=0.75$ 取 0；$0.75\times2=1.5$ 取 1；$0.5\times2=1.0$ 取 1。整数位顺序读得 $0.6875_{10}=0.1011_2$。

2.2 定点数与机器数

2.2.1 真值、定点整数和定点小数

带正负号、按人类习惯书写的数称真值；机器内保存的二进制编码称机器数。
定点小数约定小数点在符号位之后、数值部分之前；它是纯小数。
定点整数约定小数点在数值部分最低位之后；它是纯整数。
408 常用：整数用补码；浮点尾数常按原码小数理解；浮点阶码常用移码。

2.2.2 原码、反码、补码、移码

以下均以 $n$ 位机器字为例，最高位为符号位，数值位有 $n-1$ 位。

编码	正数	负数	零与范围	重要性质
原码	符号 0 + 绝对值	符号 1 + 绝对值	有 $+0/-0$；$-(2^{n-1}-1)\le x\le2^{n-1}-1$	直观，乘除较方便；加减需比较绝对值和处理符号
反码	与原码相同	原码数值位按位取反	也有 $+0/-0$，范围同原码	负数反码末位比补码小 1
补码	与原码相同	对应原码数值位取反加 1（即反码加 1）	零唯一；$-2^{n-1}\le x\le2^{n-1}-1$	加减统一为加法，最小负数没有相反数
移码	真值加偏置	真值加偏置	零唯一，范围同补码	用于阶码，大小顺序与真值一致

定义：#补码

补码可理解为模 $2^n$ 运算的编码。对负数 $x$，有 $[x]_{补}=2^n+x=2^n-|x|$；也可记为“正数不变，负数按位取反加 1”。

$[+0]{补}=[-0]{补}=00\cdots0$；$[-1]_{补}=11\cdots1$。
最小负数的补码为 $100\cdots0$，代表 $-2^{n-1}$；最大正数为 $011\cdots1$。
已知某数补码为 $Y$，其相反数补码可由 $Y$ 逐位取反再加 1得到；最小负数取反加一仍为自己，表示溢出语义。

定义：#移码

移码是把真值整体向正轴偏移一个偏置，$[x]_{移}=2^{n-1}+x$。在这里的 $n$ 位整数编码中，移码等于补码的符号位取反，数值位不变。这一定义采用偏置 $2^{n-1}$；IEEE 754 阶码字段采用的偏置是 $2^{k-1}-1$（单精度 $k=8$ 时为 127），不能直接套用“翻转补码符号位”的规则。

移码全 0 表示最小真值，移码全 1 表示最大真值；所以可直接按无符号数比较大小。
正数的原码、反码、补码相同。对在三种编码中都可表示的非零真值，它们的符号位也相同；但双零和最小负数是边界例外，不能脱离字长机械套用。对同一真值的同字长补码与移码，二者仅最高位相反。
原码与反码在数轴上对称，均有双零；补码和移码零唯一，并各比原码/反码多表示一个负数。

定义：#变形补码

变形补码使用双符号位（模 4 补码），00 表示正、11 表示负，常用于 ALU 运算以便判断溢出。结果的两个符号位不同时意味着发生溢出。

若数值位为 $m$ 位，变形补码另设 2 位符号位，总位数为 $m+2$；其可表示的真值仍为 $-2^m\le x\le2^m-1$。非负数直接写成 00 加 $m$ 位数值；负数按模 $2^{m+2}$ 编码为 $2^{m+2}+x$，正常结果以 11 开头。运算后出现 01 或 10 时，双符号位不一致，说明结果越出了这 $m$ 位数值所对应的范围。

题型：#机器数转换

第一部分：解题方法

先写清“字长”和“定点整数/定点小数”，不要把符号位也当普通数值位。
负真值转补码：写原码 -> 数值位取反 -> 加 1；转移码：在补码基础上翻转符号位。
例如 $x=-10101_2$（8 位字长，1 位符号、7 位数值）：原码 1,0010101，反码 1,1101010，补码 1,1101011，移码 0,1101011。

第二部分：常见陷阱

负数补码不能按无符号数直接比较。负数数值位越小，绝对值反而越大。
补码比原码多表示的数是最小负数，不是最大正数。
移码只表示整数，通常用于浮点数阶码，不用于表示浮点尾数。

2.3 常用检验码

定义：#码距

码距是任意两合法码字的最小不同位数。若最小码距为 $d_{min}$，最多可检测 $d_{min}-1$ 个比特错误，最多可纠正 $\left\lfloor(d_{min}-1)/2\right\rfloor$ 个比特错误；因此 $d_{min}\ge2$ 才开始具有检错能力。

校验码	基本做法	能力/用途
奇偶校验码	添加 1 位，使整串 `1` 的个数为奇数或偶数	能发现奇数个比特翻转，不能发现偶数个比特翻转；常用于简单检查
汉明码	在指定位置设置多个校验位	在满足码距条件时可定位并纠正单比特错误
CRC 循环冗余校验	用生成多项式进行模 2 除，附加余数	常用于数据链路层，适合大块数据传输校验

普通汉明码的最小码距通常为 3，可纠正 1 位错误；再增加一个全局奇偶校验位可构成 SECDED，使系统能够“纠正 1 位、检测 2 位”。

2.4 本节复盘

进制转换：按权展开、除基取余、乘基取整；二八十六进制互转以二进制分组为桥。
定点小数的小数点在符号位后，定点整数的小数点在最低数值位后；所有机器数题都先固定字长。
补码零唯一、加减统一、范围为 $[-2^{n-1},2^{n-1}-1]$；移码是补码符号位取反并保持数值排序。
检错纠错能力取决于码距；奇偶校验、汉明码、CRC 的用途和能力不可混淆。