计算机中数据的表示

最近开课计算机组成原理，由于疫情原因，老师推荐的华中科技大学的秦磊华老师讲的MOOC上的课程。感觉学习难度比较大，因为基础薄弱，所以来总结一下学习的知识，加以巩固。

机器数及其特点

首先要了解计算机内部的数据到底是怎么表示的。学习过模电我们都应该知道，计算机内的数据是以二进制形式存储的，因为二进制只包含两个状态，更好表示。如果我们能在二进制的基础上更好的组织数据，则计算机的运算就能更加高效。

数据表示有以下考虑因素：

1. 计算机支持的数据类型
2. 计算机能表示的数据范围
3. 计算机能表示的数据精度
4. 存储和处理的代价
5. 是否有利于软件的移植等…

在这些基础上我们来对数据进行处理。

真值

首先，在实际运算中，拿到一个数，我们把它转换成二进制数时，+ - 就是符号位。变成二进制数还是用+ - 来表示。这样的带符号的二进制。

比如 $-5$−5 真值就是$-101$−101； $+5$+5 的真值就是 $+101$+101

这种表示方法很直观，人眼一下就能知道是正数负数。但是计算机怎么办呢？让它去识别加号吗？只有0 1 两种状态，怎么搞个加号进去？所有就有了符号数值化。有了一个新的表示方法：

原码

我看老师的课件上给的定义是这样的

$[X]_{\mathbb{原}}=\left\{\begin{array}{l} X \space \space \space \space\space \space\space \space\space \space\space \space0 \leq X \leq 2^n\\ 2^{n}-X \space \space \space 2^{-n} \leq X \leq 0 \end{array}\right.$[X]原​={X            0≤X≤2n2n−X   2−n≤X≤0​

原码就是在真值的基础上，把符号位用0 1表示。一般规定0表示正数，1表示负数。这有点违背我们的常理，我搜了好久也没找到这样规定是出于什么原因，但好像计算机里面表示数N是$(-1)^SN$(−1)SN，S = 0 时就是1， 为正数。反之亦然。S就是那个符号位对应的0或1。

所以举个例子来说：$-5$−5 的原码就是 $1101$1101; $+5$+5 的原码就是 $0101$0101

OK，问题解决了，就用原码表示吧。接下来开始运算。

先算个 $5+5$5+5 吧。假设字长是八位

$\space \space \space \space 00000101 \\ + 00000101 \\ =00001010$    00000101+00000101=00001010

没问题，的得到的是 $+10$+10.

再来算算 $5 - 5$5−5

$\space \space \space \space 00000101 \\ - 00000101 \\ =00000000$    00000101−00000101=00000000

那么 $(-5) + 5$(−5)+5 呢

$\space \space \space \space 10000101 \\ + 00000101 \\ =10000000$    10000101+00000101=10000000
欸，0 出现了两种表示方法。不行，会给以后的运算造成麻烦。

接着改，于是设计出了反码。

反码

$[X]_{\mathbb{反}}=\left\{\begin{array}{l} X \space \space \space \space\space \space\space \space\space \space\space \space \space\space \space \space\space \space \space\space \space \space0 \leq X \leq 2^n\\ 2^{n+1}+X-1 \space \space \space 2^{-n} \leq X \leq 0 \end{array}\right.$[X]反​={X                      0≤X≤2n2n+1+X−1   2−n≤X≤0​

简单来说就是正数的反码就是原码，负数的反码就是符号位不变，其余各位按位取反。举个例子 ：$-5$−5 的反码就是 $1101$1101; $+5$+5 的反码就是 $0010$0010

通过计算，发现0还是有两种表示方法，并且出现了一个问题就是有的直接加是不对的，还得有判断加两次。比如算 $x=1101 , y= -1010, x + y$x=1101,y=−1010,x+y. 这个例子你自己验证一下不再赘述，这样会发现第一次加完，得把符号位的进位位去掉再用加法加在第一次计算结果上，得到的才是正确答案。所以，又有了补码。

补码

$[X]_{\mathbb{补}}=\left\{\begin{array}{l} X \space \space\space \space \space\space \space \space\space \space \space\space \space \space0 \leq X \leq 2^n\\ 2^{n+1}+X \space \space \space 2^{-n} \leq X \leq 0 \end{array}\right. mod \space 2^{n+1}$[X]补​={X              0≤X≤2n2n+1+X   2−n≤X≤0​mod 2n+1

同样，正数的补码等于正数的原码，负数的补码等于反码 + 1.

比如 $-5$−5 的补码就是 $1110$1110; $+5$+5 的补码就是 $0010$0010

这样在计算0的表示方法就是单一的了。并且不难发现，计算减法的时候也可以用加法来代替了，不需要判断符号绝对值等的问题了。这样很方便只需要设计加法器就行了。

移码

前面说了半天，都是定点数，而要表示浮点数（就是小数点不固定的数）的接吗就要用移码的形式。
$[X]_移=2^n + X \space \space -2^n < X \leq 2^n$[X]移​=2n+X  −2n<X≤2n
实现起来就是数值与X数值位相同，但是符号位取反。

比如 $-5$−5 的补码就是 $0110$0110; $+5$+5 的补码就是 $1010$1010

在这里就不再深究这些表示方法是怎么来的了，若想知道自行百度。

定点与浮点数据表示

定点数：就是小数点固定的数，如果小数点固定再最后，就叫定点整数，再其他位置就是定点小数。

定点数的一个缺陷就是表示的数据范围不足。这一点很好理解。如果把小数点固定在某个位置，根据计算机的字长是固定的，所以，小数点后面的位数也是固定的，要想表示精确度很高（实际数据小数点后位数大于固定小数点后剩余的位数）的数，就没法表示。所以就有了不固定小数点的数据形式。

浮点数： 小数点的位置不固定的数。

浮点数表示

一般表示方法为 $N=2^E \times M$N=2E×M 其实就像十进制里的科学计数法一样。

其中，E就是阶码，E的位数决定数据的范围。这个参考十进制的科学计数法就不难理解，像是指数。 M是位数，决定数的精度，就是小数点后面有几位，是3.14啊还是3.1415926535啊等。

那在计算机里又是怎么表示的呢？计算机没法表示次方和称号呀。所以我们就把它省略掉。不能表示就不表示嘛。省掉之后就剩下EM。那2怎么也没了？当然，既然大家都是二进制数，不可能是别的进制，所以2就不用表示了。所以表示起来就是
$E_1E_2\cdots E_n M_1 M_2 M_3 \cdots M_k$E1​E2​⋯En​M1​M2​M3​⋯Mk​
举个例子：将$x=2^{-01}\times (-0.1110)$x=2−01×(−0.1110)表示成机器形式。假定用8位表示该数，阶码3位，位数5位（且均包含一位符号位）， 假定阶码和尾数均采用补码。 $-0.1110$−0.1110的原码是$1.1110$1.1110, 小数点前面那个是0，移位之后跟没有一样，所以省掉了。 反码是$10001$10001。补码是 $10010$10010

所以，表示成机器形式就是 $111 \space 10010$111 10010。

上面这个例子会了，再来一个问题： 将$x=2^{-101}\times (-0.1111110)$x=2−101×(−0.1111110)表示成机器形式。假定阶码和尾数均采用补码。

咦，着怎么知道呢，阶码和尾数分别为几位呀？小明告诉你，阶码四位。你写出来后我按照我的方法给还原成数，发现错了和原数不一样，我的答案是按照阶码是五位来写的。那。。。这就不行。不可移植。

所以就得有个统一的标准：IEEE 754格式（读作I triple E 754）

S	偏移指数	有效位数	精度
S	8	23	单精度
S	11	52	双精度

指数用的是偏移值。单精度的偏移值为127，双精度的为1023（不深究为什么，这是规定）。偏移的好处就是把负数变成了正数。对于浮点数的排序和比较会更方便。

IEEE 754的尾数形式是 1.XXXXX, 因为如果前面有0的话，可以把0给省掉，比如 0.01， 可以写成 $2^{-2}\times 1.0$2−2×1.0。总之第一位就1. 既然所有的开头都是1，那又可以省了。M中只保存XXXXXX就行了。这样又多了一位可以保存。数据精度又能提高了。

下面我们来举个例子吧。计算 -27.5 的32位IEEE 754编码。

$(-27.5)_{10}=(-11011.1)_2=(-1.10111^{100})_2$(−27.5)10​=(−11011.1)2​=(−1.10111100)2​

S = 1, e = 4, E = 100+01111111=10000011, M = 10111

IEEE: 1100 0001 1101 1100 0000 0000 0000 0000

其中+01111111就是对阶码的偏移。（32位偏移值127）

特殊的浮点数表示

$N=(-1)^S \times 2^{E-127} \times 1.M$N=(−1)S×2E−127×1.M

1. $E=0,M=0$E=0,M=0 : 机器零
2. $E=0, M \neq 0$E=0,M​=0 : 非规格化的浮点数
3. $1 \leq E \leq 254$1≤E≤254 ：规格化的浮点数
4. $E=255, M=0$E=255,M=0 ：无穷大的数，对应$\frac{x}{0}(x \neq 0)$0x​(x​=0)
5. $E=255, M \neq 0$E=255,M​=0：N=NaN，表示非数值，对应 $\frac{0}{0}$00​

这些特殊表示我也不太理解，感觉记住就行了。

数据校验

为什么要对数据进行校验呢？因为在数据传输或者存储的过程中，会收到外界的干扰（电路故障或者噪音等），有可能导致某位或多位错误。所以校验是非常必要的。

基本原理

要想校验数据，光有本来的数据是不够的，没办法进行校验，所以得在添加额外的冗余码，也称校验位。

所以发送出来的信息就是 $有效信息（K位）+校验信息（r位）$有效信息（K位）+校验信息（r位）

对整个发出来的信息进行特定格式T编码后，会得到特定的数。然后接收方也用特定的格式T进行编码，如果得到预期的数，一般来说就是没错，得不到预期，就是有错。但是这么说还是不太严谨的，因为有时候即使出错了编码也是对的。这在后面会讲解到。

码距

进行编码的一个很重要的知识就是码距。什么是码距呢？编码之间的距离？不不不，码距与二进制位有关，是任意两个合法编码二进制位之间不同二进制位数的最小值。

比如一套编码 0011 0000 1111， 第一个和第二个数最后两位二进制位不同，所以对于前两个数来说码距是2。同理最后两个数之间的码距也是2。那对于第一个和第三个数，码距就是4。但是注意：码距是最小值， 所以这套编码的码距就是2。

码距的检查：就拿上面那套编码来说，本来编码出来是0000，但是传输过程中有了一位错误，编码变成了0001，一看编码里面没有这种编码，所以就是无效的编码，就知道有一位错了。

码距为1时无法识别1位错误。因为任何一种错误都是有效编码。

码距检错与纠错能力的关系

首先我们得知道三个基本的关系：

1. 码距$\geq e + 1:$≥e+1: 可以检测出e个错误
2. 码距$\geq 2t + 1:$≥2t+1: 可以纠正t个错误
3. 码距$\geq e + t + 1:$≥e+t+1: 可以纠正t个错误，同时检测e个错误 ($e\geq t$e≥t)

刚开始看很懵，这什么玩意儿，又是规定的吗？？？仔细想想，其实不是规定，算是一种属性吧。一个一个来看。

1. 第一个比较好理解，假如编码有0000，码距是3，则下一个有效的编码就可能是0111，1110，1101，1011其中的一个。如果0000有一位发生错误，则产生无效编码，同理，二位也是。但是当发生三个错误的时候，0000就只可能是0111，1110，1101，1011其中的一个。这些不都是有效编码吗？那就检测不出来了呗。所以第一条成立。
2. 我们以码距为3的三位编码举例。有一个前提规律是错误码少的概率大于错误码多的概率（这是一个规律我也不知道为什么）。如果000错了一位得到001， 010， 100这些非法编码，根据上面的规律可以得知，正确的是000。如果两位错误，则会误纠错为111。你可以自己再尝试其他的位数的编码。只有错误比码距的一半要小的时候才能纠错。此时第二条也成立。
3. 根据前两个式子和第三个式子的约束条件，可得到 $2e+ 1\geq e+t+1\geq 2t+1$2e+1≥e+t+1≥2t+1， $e+t+1 \geq e+1$e+t+1≥e+1，所以，最多能纠正t个错误。那还有$e+1$e+1位，由性质1可知，能检测出e个错误。

根据这些，得到一张常用码距和纠错检错能力表

码距	检错	纠错
1	0	0
2	1	0
3	2	或1
4	2	加1
5	2	加2
6	3	加2
7	3	加3

根据以上所讲可总结出，码距越大，抗干扰能力越强，纠错能力越强，数据冗余越大，编码效率低，电路也相对复杂。

所以选择码距时要考虑信息发生差错的概率和系统能容许的最小差错率。

奇偶校验

基本原理

采用增加1位校验位的方法。再添加一位校验位后，使得整个数据中，1的个数呈现奇偶性。这不废话吗，1的个数非奇即偶。其实不然，奇偶校验其实是奇校验和偶校验的合称。（为啥非得是1的个数，0的个数行不？行啊，理论上是没错的，只不过就你自己内部用，不跟大家统一，软件不能移植，保密，而且不便于理解）

奇校验

奇校验 ：要求添上校验位后，数据中1的个数为奇数。

如何计算出校验位呢？

那就先判断前面有效信息的1的个数。假设有偶数个1，进行异或运算后，得到的结果必定是0，奇数个1得到的结果必定是1。而0不管有偶数个还是奇数个，异或出来都是0。

奇数个1和任意个0异或之后结果一定是1。若原有效信息位已经有了奇数个1，则校验位得是0，是所有位数异或之后取反得到的；偶数个1和任意个0异或后结果一定是0。若原有效信息只有偶数个0，则需要在校验位添上个1，是所有位数异或之后取反得到的。

所以得出奇校验的公式 $P=\overline{D_{1} \oplus D_{2} \oplus D_{3} \oplus D_{4} \oplus \cdots \oplus D_n}$P=D1​⊕D2​⊕D3​⊕D4​⊕⋯⊕Dn​​

$D_1,D_2\cdots$D1​,D2​⋯ 是有效息信息的$1, 2, \cdots$1,2,⋯ 位。

发送方编好编码后，接收方收到编码之后如何检验呢？

因为奇校验编码中1的个数为奇数个，所以，所有位异或结果是1。但是，奇校验的检错码是 $G=\overline{C \oplus X_1 \oplus X_2 \oplus \cdots \oplus X_n}$G=C⊕X1​⊕X2​⊕⋯⊕Xn​​ 。当 G=0时表示数据正常。否则表示出错。

这个给出的图是6位有效信息的计算，其他的位数同上就行。

偶校验

偶校验 ：要求添加上校验位后，数据中1的个数为偶数。

计算的方法同上，可知最后一位是所有每一位异或的结果，所以偶校验的公式 $P={D_{1} \oplus D_{2} \oplus D_{3} \oplus D_{4} \oplus \cdots \oplus D_n}$P=D1​⊕D2​⊕D3​⊕D4​⊕⋯⊕Dn​

$D_1,D_2\cdots$D1​,D2​⋯ 是有效息信息的$1, 2, \cdots$1,2,⋯ 位。

检验的方法也类似上边，偶校验的检错码是 $G={C \oplus X_1 \oplus X_2 \oplus \cdots \oplus X_n}$G=C⊕X1​⊕X2​⊕⋯⊕Xn​ 。当 G=0时表示数据正常。否则表示出错。

该图还是六位有效信息的时候。

奇偶校验的特点

大概有如下四个特点：

1. 编码与检测简单（对，是要进行异或运算就行了）

2. 编码效率高（也是只异或，所以效率高）

3. 不能检测偶数位错误，无错结论不可靠，是一种错误检测码。

   这是因为，如果有偶数个位都发生了变话的话，1的个数必定变化了偶数个，可以自己试试。变化了偶数个后不会改变1的个数的奇偶性。1的个数奇偶性不变，编码后的结果还是没变化。

4. 不能定位错误。不具备纠错能力。

奇偶校验的码距

有效信息	奇校验编码	偶校验编码
10001	100011	100010
10000	100000	100001

根据上表可知，当有效信息只有一位不同时，编码是两位的不同。所以奇偶校验的码距是2。查码距能力表可知，码距2无纠错能力。

改进版奇偶校验

那要是我就是想让奇偶校验能纠错呢，怎么办？有一个非常妙的方法就是进行双向校验。

双向就是说，不传输单一行的数据了，传出多行的，让它变成一个数据块，横向纵向都有校验位。大概长这样：

0110100	1
1011010	0
0010110	1
1110101	1
1001011	0
1000110	1

最后一行是列的校验码，右边是行的校验码。

这样当有一个数据传输错误的时候，就能定位行列坐标了。

0110100	1
1011010	0
0010111	1
1110101	1
1001011	0
1000110	1

并且特殊的偶数错误也能检验了。

0110100	1
1011010	0
0110100	1
1110101	1
1001011	0
1000110	1

大部分情况下都是可以检错的，但是有一种特殊，当错误在四角上时，没法确定错误。

1110101	1
1011010	0
0010110	1
1110101	1
1001011	0
0000111	1

因为不管是在行还是列，都是偶数个错误，所以都没法检测出来。

所以总结一下改进版的功能

• 可纠正1位错误
• 可检测出某行（列）上的奇数位
• 可检测出一部分偶数位错误
• 不能检测出错码分布在矩形四个顶点上时的错误

CRC校验

基本原理

和之前的校验一样，也是增加冗余码，r位校验位。但是这次不再是1位了，而满足一个这样的关系：$N=k+r \leq 2^r -1$N=k+r≤2r−1

这个式子的意思是说，有r位校验位，r位就能产生$2^r$2r种状态。因为每一位都有0 1两种状态，又r位，所以就是$2^r$2r种。但是还得有一种序列对应是没错的。就是指编码正确。所以错误编码数量就是$2^r-1$2r−1。这些数量得大于或等于生成后的编码的所有位的个数，因为每一位都有出错的可能，就得生成编码的每一位错都得有一种无效编码与之对应。

检验的过程当然也是依据某种规则对数据进行处理，看是否得到预期结果。这个规则就是：收发双方约定一个（r+1）位的二进制数（统称生成多项式G(X)），发送方利用G(X)对信息多项式做模2除运算（后面会讲解这个）后，生成校验码。接收方也用G(X)对收到的编码做模2除运算来检测错误定位错误。

至于G(x)是怎么选取的依据什么条件，在后面会讲解。先给出一个产检的生成多项式的表格，先使用着，回头再讲咋回事。

N	K	码距d	G(x)多项式	G(x)
7	4	3	$x^3+x+1$x3+x+1	1001
7	4	3	$x^3+x^2+1$x3+x2+1	1101
7	3	4	$x^4+x^3+x^2+1$x4+x3+x2+1	11101
7	3	4	$x^4+x^3+x+1$x4+x3+x+1	10111
15	11	3	$x^4+x+1$x4+x+1	10011
15	7	5	$x^8+x^7+x^6+x^4+1$x8+x7+x6+x4+1	111010001
31	26	3	$x^5+x^2+1$x5+x2+1	100101
31	21	5	$x^{10}+x^9+x^8+x^6+x^5+x^3+1$x10+x9+x8+x6+x5+x3+1	1101101001
63	57	3	$x^6+x+1$x6+x+1	1000011
63	51	5	$x^{12}+x^{10}+x^5+x^4+x^2+1$x12+x10+x5+x4+x2+1	1010000110101

模2除运算

来说一说crc里面最重要的一个运算吧，这不仅是发送方也是接收方编码的重要规则。具体的规则如下：

加减运算 ：就是异或运算，加不进位减不借位

​ $0 \pm 0 = 0, 0 \pm 1= 1, 1 \pm 0 = 1, 1 \pm 1 = 1$0±0=0,0±1=1,1±0=1,1±1=1

模2除法 ： 除的时候呢按照上面减法的规则除，减的时候不借位，并且求部分余数。

上商 ：当部分余数首位为1时，商为1，减除数； 当部分余数首位为0时，商为0，减0； 当部分余数的位数小与除数的位数时，该余数即为最后的余数。

从这个上商的规则里面可以知道为什么当时选r+1位的多项式了。

这啰嗦了半天，还是看不懂，直接上一张图吧。

其实这个跟除法还是差不多的，比较之后发现规则很像。但是这个除法再crc里很重要，务必要掌握，得会自己进行运算。

编码方法

主要有五个步骤：

1. 现根据公式 $N=k+r \leq 2^r -1$N=k+r≤2r−1 确定校验位的数量。k表示有效信息位数。假如有效信息时1100，k=4位，则需要r=3位校验位（代如公式算就行了）。

2. 根据多项式的选择原则（这里先不管是怎么选的），选择一个r+1位的生成多项式。这里针对例子我们选择$G(X)=1011$G(X)=1011（主要目的是熟悉流程，后面讲怎么选）

3. 先把校验位用0补满，也就是把有效数据逻辑上向左移动r位。

4. 对补好的数据，进行模2运算法则。除数就是G(X)，被除数就是补好的数据。

5. 除好之后到最后会得到一个r位的余数，这个余数就是校验位。

这里把校验位用余数替换就相当于是把补好的数据再加上余数得到最终的数据。原先除的时候多了个余数，把余数加上后，再除就是0了。注意这不是突通的除法，普通的除法中被除数需要加上（除数-余数）才能再次除完之后变成0。而这个是模2的除法，所以加上余数之后就变成0了。

CRC检验与纠错

由上可知，加上余数后，再除余数就是０了，所以，当数据传输正确的时候，接收方拿相同的G(X)除完之后还得是0。

如果有错的时候，余数就不为0了。

具体来讲讲有错的时候。这个就比较有意思，有个规律。就是错的位数不一样，得到的余数也不一样。这个证明的话就用两张表格，拿数据说话。

$A_1$A1​ ~ $A_7$A7​	余数	出错位
1100010	000	无
1100011	001	7
1100000	010	6
1100110	100	5
1101010	011	4
1110010	110	3
1000010	111	2
0100010	101	1

这张表是G(X)=1011的时候

$A_1$A1​ ~ $A_7$A7​	余数	出错位
1100101	000	无
1100100	001	7
1100111	010	6
1100001	100	5
1101101	101	4
1110101	111	3
1000101	011	2
0100101	110	1

这张表是G(X)=1101的时候的。

有了这个规律我们不就可以定位错误了吗？对。

现在这个校验方法还有一个神奇的规律，就是如果出错位数由第n位变成第n-1位，则相当于是第n位出错时得到的余数补上一个零再除以G(X)等于第n-1位出错时得到的余数。这个你可以自己去验证，我给你举个具体的数（G(X)=1011, 第n位出错：1100110，第n-1位出错：1101010）。这种规律起个名字就是循环性。所以为什么叫CRC（Cyclic Redundancy Check）。

那有了这个规律我们可以做什么呢？

对，纠错。怎么纠错呢？有一种简单的办法，既然知道哪位错了，直接再那位进行异或运算修正过来就好了嘛。

但是想想，这样的话，是不是每一位都得设置一个引脚？数据量少了还好说，要是大了呢，电路就变的复杂起来，这样成本也增加了不少。所以，能不能只在一个位置设置一个引脚呢？

能。就利用循环的特性。

我们在第一位设置引脚，让出错的数据到达第一位。怎么到达？就是让数据循环滚动，让数据滚动到第一位。这个我之前一直不太理解。到底是怎么滚动的。我来举个例子，加入数据是11100，最后一位是错的，那么滚动一次的意思就是变成这样：11001。在滚动一次就是10011。不知道能不能看懂。

那么具体滚动几次呢？

参照第一张图，假如错的数据在第4位，1101101，余数是101。根据循环性，我们给余数补零再做模2除运算，会得到出错位再第三位的余数。要想得到出错位再1时的余数，需要补0模2除3次。再看实际错的第四位要是滚动到第一位也得滚动3次。

所以，我们边补0模2除，边滚动，知道发现余数等于出错位为第一位的时候的余数时，就是已经把出错位滚动到第一位了。

这时候再对第一位进行异或运算。修正第一位。

修正完咋回去呢？

回去也是同样的原理，接着补0模2除，直到得到了当时第一次进行模2除时得到的余数时即停止滚动，数据回位。

G(X)满足条件

知道了流程之后，对G(X)的满足条件就更好理解了。满足四个条件：

1. 最高位和最低为必须为1
2. 当被传送信息任何一位发生错误时，被生成多项式除后余数不能为0
3. 不同位发生错误，模2除运算后余数不同
4. 对不为0余数补0模2除应使余数循环