第二章数据的表示、运算与校验 #

目录 #

1. 数制转换 #

1.1. 十进制转二进制 #

整数部分：除积其余法

$(116)_{10} = (1110100)_2$

$116 / 2 = 58 ... 0, x_0 = 0$

$58 / 2 = 29 ... 0, x_1 = 0$

$29 / 2 = 14 ... 1, x_2 = 1$

$14 / 2 = 7 ... 0, x_3 = 0$

$7 / 2 = 3 ... 1, x_4 = 1$

$3 / 2 = 1 ... 1, x_5 = 1$

$1 / 2 = 1 ... 1, x_6 = 1$

小数部分：乘基取余法

$(0.625)_{10} = (0.101)_2$

$0.625 \times 2 = 1.25, x_0 = 1$

$0.25 \times 2 = 0.5, x_1 = 0$

$0.5 \times 2 = 1, x_2 = 1$

整数表示为 $x_n \cdots x_0$ ，小数表示为 $x_0 \cdots x_n$

1.2. 二进制转十进制 #

整数部分

逐次乘基相加法，从高位向低位

$(1011)_2 = (11)_{10}$

$1 \times 2+0=2$

$2 \times 2+1=5$

$5 \times 2+1=11$

小数部分

逐次除基相加法，从低位向高位

$(0.1011)_2=(0.685)_{10}$

$1/2=0.5$

$(1+0.5)/2=0.75$

$(0+0.75)/2=0.375$

$(1+0.375)/2=0.6875$

2. 原码、补码与反码 #

原码

1位符号位+二进制数

补码

方便运算，可由原码按位取反后加1计算补码，重复步骤将补码可以转回原码。

反码

原码按位取反，相对于补码少了加1运算。

移码

移码通常用来表示浮点数的阶码。它只能表示整数。

移码就是在真值 $X$ 上加上一个常数（偏置量），通常这个常数取 $2^n$ ，相当于 $X$ 在数轴上向正方向偏移了若干单位，这就是”移码“ 一词的由来。移码定义为

$x_{移} = 2^n + x (2^n > x \ge -2^n)$

其中机器字长为 $n + 1$

例如，若正数 $x_1 = +10101$ ， $x_2 = -10101$ ，字长为8位，则其移码表示为 $[x_1]_移 = 2^7 + 10101 = 1, 0010101$ ， $[x_2]_移 = 2^7 + (-10101) = 0, 1101011$

移码具有以下特点：

移码中零的表示唯一

3. 数制转换 #

3.1. 二进制转八进制和十六进制 #

3.2. 任意进制转为十进制 #

3.3. 十进制转换为任意进制 #

示例：将十进制数 $123.6875$ 转换为二进制数。

3.3.1. 除基取余法(整数部分的转换)#

整数部分除基取余，最先取得的余数为数的最低位，最后取得的余数为数的最高位（即除基取余，先余为低，后余为高），商为0时结束。

$123 / 2 = 61 \cdots 1$ 最低位为 $1$

$61 / 2 = 30\cdots 1$

$30 / 2 = 15\cdots 0$

$15 / 2 = 7 \cdots 1$

$7 / 2 = 3 \cdots 1$

$3 / 2 = 1 \cdots 1$

$1 / 2 = 0 \cdots 1$ 最高位为 $1$

3.3.2. 乘基取余法(小数部分的转换)#

小数部分乘基取整，最先取得的整数为数的最高位，最后取得的整数为数的最低位（即乘基取整，先整为高，后整为低），乘积为 $1.0$ （或满足精度要求）时结束。

$0.6875 \times 2 = 1.3750$ 取整为 $1$ 最高位为 $1$

$0.3750 \times 2 = 1.7500$ 取整为 $0$

$0.7500 \times 2 = 1.5000$ 取整为 $1$

$0.5000 \times 2 = 1.0000$ 取整为 $1$ 最低位为 $1$

因此小数部分 $0.6875 = (0.1011)_2$ ，所以 $123.6875 = (1111011.1011)_2$

4. 运算方法 #

4.1. 定点加减运算 #

4.2. 溢出的判断与移位 #

4.3. 定点乘法运算 #

4.4. 定点除法运算 #

4.5. 浮点四则运算 #

5. 校验码 #

5.1. 奇偶校验码 #

奇校验：整个校验码（包含有效信息位和校验位）中 $1$ 的个数为奇数

偶校验：整个校验码（包含有效信息位和校验位）中 $1$ 的个数为偶数

5.2. 海明校验码 #

求 $1010$ 的海明码

5.2.1. 确定海明码的位数 #

设 $n$ 为有效信息的位数， $k$ 为校验位的位数，则信息位 $n$ 和校验位 $k$ 应满足

$n + k \le 2^k - 1$

$1010$ 中 $n = 4$ ，则 $k = 3$ 可满足要求。

5.2.2. 确定校验位的分布 #

规定校验位 $P_i$ 在海明位号为 $2^{i-1}$ 的位置上，其余各位为信息位。

$P_1$ 的海明号位为 $1$

$P_2$ 的海明号位为 $2$

$P_3$ 的海明号位为 $4$

5.2.3. 分组形成校验关系 #

被校验数据位的海明号位等于校验该数据位的各校验位海明位号之和。另外，校验位不需要再被校验。设 $D_i$ 表示第 $i$ 位信息位， $H_i$ 表示第 $i$ 位海明码。 $H_7 H_6 H_5 H_4 H_3 H_2 H_1$ 。

$D_1$ 放在 $H_3$ 上，由 $P_2 P_1$ 校验， $3 = 1 + 2$

$D_2$ 放在 $H_5$ 上，由 $P_3 P_1$ 校验， $5 = 1 + 4$

$D_3$ 放在 $H_6$ 上，由 $P_3 P_2$ 校验， $6 = 2 + 4$

$D_4$ 放在 $H_7$ 上，由 $P_3 P_2 P_1$ 校验， $7 = 1 + 2 + 4$

5.2.4. 校验位取值 #

校验位 $P_i$ 的值为 $i$ 组（由该校验位校验的数据位）所有位求异或。

$P_1 = D_1 \oplus D_2 \oplus D_4 = 0 \oplus 1 \oplus 1 = 0$

$P_2 = D_1 \oplus D_3 \oplus D_4 = 0 \oplus 0 \oplus 1 = 1$

$P_3 = D_2 \oplus D_3 \oplus D_4 = 1 \oplus 0 \oplus 1 = 0$

5.2.5. 海明码的校验原理 #

每个校验组分别利用校验位和参与形成该校验位的信息位进行奇偶校验检查，构成 $k$ 个校验方程。

$S_1 = P_1 \oplus D_1 \oplus D_2 \oplus D_4$

$S_2 = P_2 \oplus D_1 \oplus D_3 \oplus D_4$

$S_3 = P_3 \oplus D_2 \oplus D_3 \oplus D_4$

若 $S_3 S_2 S_1$ 的值为 $000$ ，则说明无错。

否则说明出错，且出错位即为 $S_3 S_2 S_1$ 指示的十进制数。

5.3. 循环冗余校验码（CRC）#

$CRC$ 的基本思想是：在 $K$ 位信息码后再拼接 $R$ 位校验码，整个编码长度位 $N$ 位，因此又被称为 $(N, K)$ 码。

将四位有效信息 $1100$ 编成循环校验码，选择生成多项式 $1011$ 。

$M(x) = x^3 + x^2$ ，即 $1100$ ， $k = 4$ 。

$M(x) \cdot x^r = x^6 + x^5$ ，即 $1100000$ ， $r = 3$ 。 $r$ 表示 $G(x)$ 最高位次数。

生成多项式， $G(x) = x^3 + x + 1$ 表示 $1011$ ， $r + 1 = 4$ ，生成多项式共 $4$ 位。

做模2除运算。即按位异或，结果不向上借位。

$\frac{M(x) \cdot x^3}{G(x)} = \frac{1100000}{1011} = 1110 + \frac{010}{1011}$

5.3.1. 译码和纠错 #

备注	循环码(A7 - A1)	余数	出错位
正确	1100010	000	无
错误	1100011	001	1
错误	1100000	010	2
错误	1100110	100	3
错误	1101010	011	4
错误	1110010	110	5
错误	1000010	111	6
错误	0100010	101	7

我们可以采取一种节省硬件的纠错方法：

只设置余数 $101$ 的译码输出，对应于最高位的出错位置；
如果校验后发现余数不为 $0$ ，一边对余数补 $0$ 继续做模 $2$ 除，同时将被检测码字循环左移一位，假设第 $1$ 位出错，余数为 $001$ ；
当出现余数 $101$ 时，出错位也被移至最高位位置，可用异或门将之变反纠正，或在移位过程中纠正；
继续移满一个循环，即余数 $001$ 再次出现时，码字共移位了 $7$ 次，我们将得到一个纠正后的正确码字。

情况说明	校验码当前情况	运算	余数
发现出错，开始纠错	1100011	1100011与G(X)模二除	001
校验码循环左移，同时余数001补0，成为0010，与G(X) 模二除	1000111	0010与G(X)模二除	010
校验码循环左移，同时余数010补0，成为0100，与G(X) 模二除	0001111	0100与G(X)模二除	100
校验码循环左移，同时余数100补0，成为1000，与G(X) 模二除	0011110	1000与G(X)模二除	011
校验码循环左移，同时余数011补0，成为0110，与G(X) 模二除	0111100	0110与G(X)模二除	110
校验码循环左移，同时余数110补0，成为1100，与G(X) 模二除	1111000	1100与G(X)模二除	111
校验码循环左移，同时余数111补0，成为1110，与G(X) 模二除	1110001	1110与G(X)模二除	101
发现当前余数位101，已知101代表第一位出错，把第一位与1进行异或运算(或取反运算)，纠错	0110001	无运算	无
校验码循环左移，同时余数101补0，成为1010，与G(X) 模二除	1100010	1010与G(X)模二除	001