数据表示与运算

1. 数值编码

1.1 原码

最高位为符号位（0正1负），其余位为绝对值：

$[X]_{\text{原}} = \begin{cases} X & 0 \leq X < 2^{n-1} \\ 2^{n-1} + |X| & -2^{n-1} < X \leq 0 \end{cases}$

8 位原码范围：$-127 \sim +127$，0 有两种表示（+0 和 -0）。

1.2 反码

正数与原码相同，负数符号位为1，数值位按位取反：

$[X]_{\text{反}} = \begin{cases} X & X \geq 0 \\ 2^n - 1 + X & X < 0 \end{cases}$

1.3 补码

计算机中最常用的整数表示法：

$[X]_{\text{补}} = \begin{cases} X & X \geq 0 \\ 2^n + X & X < 0 \end{cases}$

关键性质：

• 补码 = 反码 + 1（负数）
• 0 的补码唯一
• $n$ 位补码范围：$-2^{n-1} \sim 2^{n-1}-1$
• 补码加减法统一为加法

快速求补码：从最低位到第一个1保持不变，其余位取反。

1.4 移码

补码的符号位取反，用于浮点数的阶码表示：

$[X]_{\text{移}} = 2^{n-1} + X$

移码保持了数值的大小顺序，便于比较大小。

2. 定点运算

2.1 补码加法

$[X+Y]_{\text{补}} = [X]_{\text{补}} + [Y]_{\text{补}}$

符号位参与运算，进位自然丢弃。

2.2 补码减法

$[X-Y]_{\text{补}} = [X]_{\text{补}} + [-Y]_{\text{补}}$

其中 $[-Y]_{\text{补}}$ 为 $[Y]_{\text{补}}$ 的各位取反加1。

2.3 溢出检测

单符号位法：

$V = A_s \oplus B_s \oplus S_s$

• $V = 0$：无溢出
• $V = 1$：溢出

双符号位法（变形补码）：

• $S_{s1}S_{s2} = 00$：结果为正，无溢出
• $S_{s1}S_{s2} = 01$：正溢出
• $S_{s1}S_{s2} = 10$：负溢出
• $S_{s1}S_{s2} = 11$：结果为负，无溢出

2.4 定点乘法

原码一位乘法：

• 符号位单独处理：$P_s = A_s \oplus B_s$
• 数值部分：被乘数加或不加（根据乘数位），然后右移

补码一位乘法（Booth 算法）：

根据乘数末两位的差值决定操作：

3. 浮点数表示

3.1 IEEE 754 标准

浮点数格式：

$(-1)^S \times 1.M \times 2^{E-\text{bias}}$

3.2 特殊值

3.3 非规格化数

当阶码全0、尾数非零时，表示非规格化数：

$(-1)^S \times 0.M \times 2^{1-\text{bias}}$

非规格化数填补了0和最小规格化数之间的间隙，实现渐进下溢。

3.4 浮点精度

单精度有效位数约 7 位十进制，双精度约 15~16 位十进制。

机器 epsilon：

$\epsilon_{\text{single}} = 2^{-23} \approx 1.19 \times 10^{-7}$

$\epsilon_{\text{double}} = 2^{-52} \approx 2.22 \times 10^{-16}$

4. 浮点运算

4.1 浮点加减法

1. 对阶：小阶向大阶看齐，尾数右移
2. 尾数加减：对阶后的尾数相加减
3. 规格化：左规或右规使尾数满足 $1.M$ 格式
4. 舍入：按舍入模式处理超出位
5. 溢出判断：检查阶码是否溢出

4.2 舍入模式

就近舍入的”银行家舍入”规则：当恰好在中间时，舍入到偶数。

4.3 浮点乘除法

乘法：

$(-1)^{S_1 \oplus S_2} \times (1.M_1 \times 1.M_2) \times 2^{(E_1+E_2-\text{bias})}$

除法：

$(-1)^{S_1 \oplus S_2} \times (1.M_1 \div 1.M_2) \times 2^{(E_1-E_2+\text{bias})}$

5. 校验码

5.1 奇偶校验

在数据位后添加1位校验位，使1的个数为奇数（奇校验）或偶数（偶校验）。

• 只能检测奇数个错误
• 不能纠正错误
• 检错率：$1 - 2^{-n}$（对于 $n$ 位数据）

5.2 海明码（Hamming Code）

在数据位之间插入 $r$ 个校验位，满足：

$2^r \geq m + r + 1$

其中 $m$ 为数据位数，$r$ 为校验位数。

校验位位置：放在 $2^i$ 的位置（第1、2、4、8…位）。

编码步骤：

1. 确定校验位数 $r$
2. 将数据位填入非 $2^i$ 位置
3. 每个校验位覆盖其位置二进制表示中对应位为1的所有位
4. 计算各校验位的值

纠错能力：SEC-DED（单纠错双检错）

5.3 CRC 循环冗余校验

将数据视为多项式，用生成多项式除取余数作为校验码。

编码过程：

1. 数据 $M(x)$ 左移 $r$ 位（$r$ 为生成多项式阶数）
2. 用生成多项式 $G(x)$ 模2除法取余数 $R(x)$
3. 发送 $M(x) \cdot x^r + R(x)$

检错能力：

• 所有单比特错误
• 所有双比特错误（生成多项式包含 $(x+1)$ 因子时）
• 所有奇数个比特错误
• 所有长度 $\leq r$ 的突发错误

5.4 校验码对比