数据表示及运算

发表于 2023-11-18 更新于 2023-11-22 分类于计算机组织与结构阅读次数：本文字数： 4.1k 阅读时长 ≈ 7 分钟

数据的机器级表示

信息的二进制编码

自信息量：$I(x_i) = -log_2\:p(x_i)$
系统的信息熵：$H(X) = E[I(X)] = -\sum_i p(x_i)log_2p(x_i)$

补码

计算机中普遍使用补码

补码无论同号还是异号都可以直接相加

原码可能会出错

负数的补码等于对应的正数各位取反末位加一

$负数补码 = 模 - 负数绝对值$

浮点数二进制表示

科学计数法：$\pm S \times B^E$

S：尾数
B：基底
E：阶码

规格化数

S	E	M

尾数（S）第一位总是1，不需要存于尾数字段（默认）
- 23位原码表示24位尾数
阶码（E）的真实值加偏移量后再存入阶码字段
- 真实值 -127~128
- 全0和全1表示特殊值
  - 规格化数的阶码范围为0000 0001（-126） ~ 1111 1110（127）

规格化表示：

$\pm 1.bbb…b \times 2^E$
$X = (-1)^S \times M \times 2^E$

规格化数的范围：（~~重要难耐~~）

格式	最小整数	最大整数	最小负数	最大负数
单精度	E = 1, M=0	E = 254, M = $1 - 2^{-23}$	E = 254, M = $1-2^{-23}$	E = 1, M = 0
真值	$1.0 \times 2^{-126}$	$(2-2^{-23}) \times 2^{127})$	$-(2-2^{-23}) \times 2^{127}$	$-1.0 \times 2^{-126}$

阶码的值	尾数的值	表示
0（全0）	0	$\pm 0$
0（全0）	非0	非规格化数
1~254	任意	规格化数
255（全1）	0	$\pm \infty$
255（全1）	非0	NaN

非规格化数

用于处理规格化数中的下溢情况

$(-1)^S \times 0.bbb…b \times 2^{-126}$

自然BCD码（NBCD,8421码）（随便看看得了）

用四个二进制位表示每一个十进制数字

符号：四个最高有效位

正：1100
负：1101

数据校验码

纠错

基本思想：存储额外的信息以进行检错和校正

处理过程：

数据输入：使用函数f在M位数据D上生成K位校验码C
数据输出：使用函数f在M位数据$D’$上生成新的K位校验码$C’’$，并与取出的K位校验码$C’$进行比较
- 没有检测到差错：使用数据$D’$
- 检测到差错并可以校正：校正数据$D’$来生成数据$D’’$，并用数据$D’’$
- 检测到差错但无法纠正：报告

一旦进入Memory，C和D就已经永远消失了

奇偶校验码

增加1位校验码在数据最后面来表示数据中的1的数量是奇数还是偶数

处理过程：

假设数据为$D = D_M \cdots D_2 D_1$

数据输入
- 奇校验：$C = D_M \oplus \cdots D_2 \oplus D_1 \oplus 1$
- 偶校验：$C = D_M \oplus \cdots D_2 \oplus D_1$
数据输出
- 奇校验：$C’’ = D’_M \oplus \cdots D’_2 \oplus D’_1 \oplus 1$
- 偶校验：$C’’ = D’_M \oplus \cdots D’_2 \oplus D’_1$
检错

$S = C’’ \oplus C’$
- S = 0：正确/数据中出错的位数为偶数
- S = 1：数据中出错的位数为奇数

优点：代价低，只需要1位额外数据

缺点：不能发现出错位数为偶数的情形，发现错误后无法校正

海明码

将数据分成几组，对每一组都使用奇偶校验码进行检错

处理过程 ：

将𝑀位数据分成𝐾组

数据输入：
- 为数据𝐷中每组生成1位校验码，合并得到𝐾位校验码𝐶
数据输出：
- 为数据𝐷′中每组生成1位校验码，合并得到新的𝐾位校验码𝐶′′
检错：将校验码𝐶′′和取出的校验码 C’ 按位进行异或，生成𝐾位故障字（syndrome word）

检验码

检验码的长度为 $2^K \geq M + K + 1$，使K成立的最小值就是校验码的位数

数据中有1位出现错误：M
检验码中有1位出现错误：K
没有出现错误：1

每一个检验位都放在二进制串中$2^n(n \in \mathbb{N})$的位置

位置	1	2	3	4	5	6	7	8	9	10	11	12
数据位			$D_1$		$D_2$	$D_3$	$D_4$		$D_5$	$D_6$	$D_7$	$D_8$
校验位	$C_1$	$C_2$		$C_3$				$C_4$

检验位$C_i$负责检验二进制第 i 位为1的位置的检错
- 比如$C_1$负责0011、0101、0111 、1001$\cdots$，也就是第3、5、7、9 $\cdots$位
- 比如$C_2$负责0011、0110、0111、1010 $\cdots$，也就是第3、6、7、10$\cdots$位
检验位$C_i$的值要根据选择的奇/偶校验来决定
- 所有负责的位进行异或（奇检验最后还要异或1）

故障字

每种取值反映一种情形

全0：没有检测到错误
有且仅有1位是1：错误发生在校验码中的某一位，不需要纠正
有多位为1：错误发生在数据中的某一位，将$D’$中对应数据位取反即可纠正

故障字	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100
数据位			$D_1$		$D_2$	$D_3$	$D_4$		$D_5$	$D_6$	$D_7$	$D_8$
校验位	$C_1$	$C_2$		$C_3$				$C_4$

循环冗余检测

模2运算：进行加法和减法都不进位

循环冗余检测CRC计算：假定数据M有k个比特，CRC运算就是在数据M后面添加供差错检测用的n位冗余码，然后构成一个帧发出去，一共发送(k + n)位

n位冗余码获得方式：在M后面加上n个0，得到的(n + k)位的数初一事先商定的(n + 1)位除数P，得出商是Q而余数是R（n位），这个余数R就作为冗余码拼接在数据M后面发送出去,也就是发送(k + n)位的CRC码

这种冗余码称作帧检验序列FCS(Frame Check Sequence)

循环冗余检验的图像结果

接收端把收到的数据进行CRC检验：把收到的每一个帧除以相同的除数P（模2运算），然后检查得到的余数R

R = 0则判定没有差错，接收
R $\ne$ 0则出现差错（无法确定具体位置）

整数运算

加法

溢出表示：

全加器

与门延迟：1ty ，或门延迟：2ty，异或门延迟：3ty
进位延迟：2ty，数据延迟：6ty

串行进位加法器

$S_n = 2 \times(n - 1) + 3 = 2n + 1$
- 在等待C来的时候，已经提前把$X_i$和$Y_i$进行计算
- n=1的时候，计算出来是3，而实际是6
  - 需要 $2 \times (n - 1) \geq 3$ 才行
- $S_1 = 6，S_2 = 6，S_3 = 7$，$S_1$和$S_2$是同时出来的，只要C过去了就行