数据表示与运算

1. 数值编码

1.1 原码

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

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

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

1.2 反码

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

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

1.3 补码

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

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

关键性质：

• 补码 = 反码 + 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：

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

${ϵ}_{\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÷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\ge 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)$ 因子时）
• 所有奇数个比特错误
• 所有长度 $\le r$ 的突发错误

5.4 校验码对比