『计算机组成原理』数制与编码（校验码，CRC，汉明码详解）

@[toc]

一、考纲

1. 数制与编码

进位计数制及其相互转换
真值和机器数
BCD 码
字符与字符串
校验码（汉明码，CRC 校验等）

2.定点数的表示和运算

定点数的表示（无符号数的表示，有符号数的表示）
定点数的运算
- 定点数的移位运算
- 原码定点数的加/减运算
- 补码定点数的加/减运算
- 定点数的乘/除运算，
- 溢出的概念和判别方法。

3.浮点数的表示和运算

1.浮点数的表示（IEEE 754 标准）

2.浮点数的加/减运算

4.算术逻辑单元(ALU)

1.串行加法器和并行加法器

2.算术逻辑单元的功能和结构

正文👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇

二、数制与编码

1.进制及其转换：

常见数制类型及表示方法

十进制（Decimal）
数码：0 1 2 3 4 5 6 7 8 9
书写方式： 1. 123456 2. $(123456)_{10}$
二进制（Binary）
数码：0 1
书写方式： 1. 101011B 2. $( 101011)_{8}$
八进制（Octal）
数码：0 1 2 3 4 5 6 7
书写方式： 1. 123456Q 2. $(123456)_{8}$
十六进制（Hexadecimal）
数码：0 1 2 3 4 5 6 7 8 9 A B C D E F
书写方式：
1. 1234A56CH
2. $(1234A56C)_{16}$
3. 0x1234A56C

1.非十进制数转换成十进制数

前置概念—-权值：
权值”是指对应数值位的进制幂次方数，如二进制整数中第 0 位（最低位，也就是整数最右边的那位）的权值是 2 的 0 次方，第 1 位的权值是 2 的 1 次方，以此类推；同理在八进制整数中第 0 位的权值是 8 的 0 次方，第 1 位的权值是 8 的 1 次方……，以此类推。

二进制转换为十进制
各位值乘以位权值相加即可。
例：
$10110_2–>12^4+02^3+12^2+12^1+0*2^0$
八进制转换为十进制
与二进制类似（将底数 2 改为 8 即可）
十六进制转换位十进制
　与二进制类似（将底数 2 改为 16 即可）

2.十进制数转换成非十进制数

十进制整数转换为二进制
　除 2 取余（先出来的余数是二进制的低位）

在这里插入图片描述 2. 十进制小数数转换为二进制
　乘 2 取整（先出来的是高位）
　
要记住的一些特殊数字

|十进制分数|十进制小数|二进制|
|--|--|--|
| $\frac{1}{2}$ |0.5| 0.1
| $\frac{1}{4}$	|0.25 |0.01
| $\frac{1}{8}$	|0.125| 0.001
| $\frac{1}{2^n}$	|......| 0.00.....n个0....1

十进制转换为八进制，十进制转换为十六进制都与二进制类似，跳过。

3. 　八进制数、二进制数互转

八进制数转换成二进制数
每一位 8 进制数换成对应的 3 位 2 进制数表示即可
例
在这里插入图片描述
　二进制转换为八进制数

3. 　十六进制数、二进制数互转

十六进制数转换成二进制数
　　类似于八进制数转换为二进制数（将 3 位改为 4 位即可）

二进制数转换为十六进制数
　类似于二进制数转换为十六进制数（将 3 位改为 4 位即可）

2.真值和机器数的互换

用“+”、“-”号加绝对值来表示数值的大小，用这种形式表示的数值在计算机中称为“真值”
符号数码化后，二进制数的最高位“0”表示正号，“1”表示负号，用这种形式表示的数值在计算机中称为“机器数”

注：在计算机编程中

1
2
3

int a;  //申请了一个32内存空间，这个空间的地址叫a;
		//也告诉了计算机把这个数当作有符号的数来看待，计算机会把它当作补码使用。
a=-5;  //计算机会存储 1011 即补码

原码，补码，反码，移码

1.原码：符号位+绝对值的二进制(方便读取）

2.补码：正数的补码等于原码(方便运算）

           负数：除符号位外，各位取反末位加1

3.反码：正数的反码等于原码（没用）

           负数：除符号位外，各位取反

4.移码：补码符号位取反

5.8421CD 码与余三码

真值	8421BCD	余三码
0	0000	0011
1	0001	0100
2	0010	0101
3	0011	0110
4	0100	0111
5	0101	1000
6	0110	1001
7	0111	1010
8	1000	1011
9	1001	1100

8421BCD 用于表示字符型数据：电话号码、学号等，不用于运算

大小比较：
原码：正数越大值越大，负数越大值越小
移码：看着越大值越大

6.字符与字符串

ASCII 码

如 a 至 z，A 至 Z，=，空格，0 至 9 等等。
字符总数不超过 256，所以可以用 8 个 2 进制表示。
在这里插入图片描述

输入码：音码（汉语拼音) 和形码 (五笔输入法）

区位码

区位码是一个四位的十进制数，前两位叫做区码(01-94)，后两位叫做位码(01-94)。汉字与符号组成一个 94×94 的矩阵。在此方阵中，每一行称为一个“区”，每一列称为一个“位”。
每个区位码都对应着一个唯一的汉字或符号。比如：“2901”输入“健”字，“4582”输入“万”字。

国标码：

区位码是一个四位的十进制数，国标码是一个四位的十六进制数。为了和 ASCII 码兼容，汉字输入区位码与国标码有一个简单的转换关系
方法：
（1）区位码先转换成十六进制数表示
（2）（区位码的十六进制表示）＋ 2020H ＝国标码；
举例：以汉字“大”为例,“大”字的区内码为 2083
1、区号为 20,位号为 83
2、将区位号 2083 转换为十六进制表示为 1453H
3、1453H ＋ 2020H ＝ 3473H,得到国标码 3473H

机内码

汉字或字符在计算机内部的表示就是机内码
国标码＋ 8080H ＝机内码
以汉字“大”为例：
“大”字的区位码为 2083(十进制数)，“区”和“位”分别换算成十六进制是 1453H(20→14H，83→53H)
1453H ＋ 2020H ＝ 3473H，得到“大”字的国标码是 3473H
3473H ＋ 8080H ＝ B4F3H，得到“大”字的机内码是 B4F3H

字体库 (了解即可）

字形码，点阵代码的一种。为了将汉字在显示器或打印机上输出，把汉字按图形符号设计成点阵图，就得到了相应的点阵代码（字形码）。
用于显示的字库叫显示字库。显示一个汉字一般采用 16×16 点阵或 24×24 点阵或 48×48 点阵。已知汉字点阵的大小，可以计算出存储一个汉字所需占用的字节空间。
例：用 16×16 点阵表示一个汉字，就是将每个汉字用 16 行，每行 16 个点表示，一个点需要 1 位二进制代码，16 个点需用 16 位二进制代码（即 2 个字节），共 16 行，所以需要 16 行 ×2 字节/行=32 字节，即 16×16 点阵表示一个汉字，字形码需用 32 字节。
即：字节数=点阵行数 × 点阵列数/8
用于打印的字库叫打印字库，其中的汉字比显示字库多，而且工作时也不像显示字库需调入内存。
全部汉字字形码的集合叫汉字字库。汉字库可分为软字库和硬字库。软字库以文件的形式存放在硬盘上，现多用这种方式，硬字库则将字库固化在一个单独的存储芯片中，再和其它必要的器件组成接口卡，插接在计算机上，通常称为汉卡。
可以这样理解，为在计算机内表示汉字而统一的编码方式形成汉字编码叫内码，内码是惟一的。为方便汉字输入而形成的汉字编码为输入码，属于汉字的外码，输入码因编码方式不同而不同，是多种多样的。为显示和打印输出汉字而形成的汉字编码为字形码，计算机通过汉字内码在字模库中找出汉字的字形码，实现其转换。
————-摘自百度百科

7.校验码

数据再计算机传输过程中会出现错误，错误会引起歧义，所以需要校验码。
码距是指两个码组对应位上数字的不同位数称为码组的距离，又称为汉明距离。==码距为 1 时不具备校验能力。==
通信双方的大工程某种共识：校验方法、校验位数、校验位置

1.奇偶校验码

以奇校验码为例：
最高位为校验位，最高位补 0 或 1 是校验码中 1 的个数为奇数。

数据：01010101
发送方：奇校验  1 01010101（1的个数右奇数个）
接收方：
没错：101010101----01010101（去掉校验位）
1位错:（1） 1 11010101
     （2） 0 01010101（1的个数为偶数了，可以检验到错误）
2位错： 1 10010101（此时1的个数为奇数，不能检验到错误）

优点：简单，传输效率高
缺点：只能发现错误，不能修改错误；只有当奇数个位数出错时才能被发现。

2.Hamming 校验码

发送方：

1.校验位的位数

仅能发现并修正一位错
假设数据位 D（d 位），校验位 R（r 位）
$2^r>=d+r+1$
发现修正一位错，并发现两位错
$2^{r-1}>=d+r$

2.校验位的位置
第一种：仅能发现并修正一位错
海明码的下标为$2^i$的位置上,剩余依次填上数据位即可。
设数据位 d=8，推出 r=4
假设数据串位 10100101

H12	H11	H10	H9	H8	H7	H6	H5	H4	H3	H2	H1
D8	D7	D6	D5	R4	D4	D3	D2	R3	D1	R2	R1
1	0	1	0		0	1	0		1

第二种：发现修正一位错，并发现两位错
海明码的下标为$2^i$的位置上以及最高位,剩余依次填上数据位即可。
设数据位 d=8，推出 r=5

H13	H12	H11	H10	H9	H8	H7	H6	H5	H4	H3	H2	H1
13	12=4+8	11=1+2+8	10=2+8	9=1+8	8	7=1+2+4	6=2+4	5=1+4	4	3=1+2	2	1
	1	0	1	0		0	1	0		1

3.校验位的值

确定校验关系：数据位在海明码中的下标=参与校验的校验位的下标和

H12	H11	H10	H9	H8	H7	H6	H5	H4	H3	H2	H1
D8	D7	D6	D5	R4	D4	D3	D2	R3	D1	R2	R1
12=4+8	11=1+2+8	10=2+8	9=1+8	8	7=1+2+4	6=2+4	5=1+4	4	3=1+2	2	1
1	0	1	0		0	1	0		1

确定校验位的值=它参与校验的数据位的亦或

R1参与的校验：D1  D2 D4 D5 D7
R2参与的校验：D1 D3 D4 D6 D7
R3参与的校验：D2 D3 D4 D8
R4参与的校验：D5 D6 D7 D8
1
2
3
4
R1=D1^D2^D4^D5^D7=1^0^0^0^0=1
R2=D1^D3^D4^D6^D7=1^1^0^1^0=1
R3=D2^D3^D4^D8=0^1^0^1=0
R4=D5^D6^D7^D8=0^1^0^1=0

H12	H11	H10	H9	H8	H7	H6	H5	H4	H3	H2	H1
D8	D7	D6	D5	R4	D4	D3	D2	R3	D1	R2	R1
12=4+8	11=1+2+8	10=2+8	9=1+8	8	7=1+2+4	6=2+4	5=1+4	4	3=1+2	2	1
1	0	1	0	==0==	0	1	0	==0==	1	==1==	==1==

第一种与第二种的区别是是否有 R5，R5 是（所有数据位的异或）异或（不包括 R5 的所有校验位的异或）

1	`R5=R1^R2^R3^R4^D1^D2..^D8=0`

H13	H12	H11	H10	H9	H8	H7	H6	H5	H4	H3	H2	H1
R5	D8	D7	D6	D5	R4	D4	D3	D2	R3	D1	R2	R1
13	12=4+8	11=1+2+8	10=2+8	9=1+8	8	7=1+2+4	6=2+4	5=1+4	4	3=1+2	2	1
==0==	1	0	1	0	==0==	0	1	0	==0==	1	==1==	==1==

接收方：

S1=R1'^（D1'^D2'^D4'^D5'^D7'）
S2=R2'^（D1'^D3'^D4'^D6'^D7'）
S3=R3'^（D2'^D3'^D4'^D8'）
S4=R4'^（D5'^D6'^D7'^D8'）

第一种

没有发生错误 S1=0 S2=0 S3=0 S4=0
发生一位错误：
假设 D1 发生错误，
S1=1
S2=1
S3=0
S4=0
S4 S3 S2 S1=0011 =10 进制的 3 恰巧 D1 的下标就是 3

第二种

S1=R1'^（D1'^D2'^D4'^D5'^D7'）
S2=R2'^（D1'^D3'^D4'^D6'^D7'）
S3=R3'^（D2'^D3'^D4'^D8'）
S4=R4'^（D5'^D6'^D7'^D8'）
//前面一样
S5=R5^（D1^...^D8）（R1^...^R5）

没有错误 S5=0 S4 S3 S2 S1=0000
发生一位错
I.D2 出错 S5 =1 S4S3S2S1=0101=5->H5,即出错位置在汉明码的下标
II. D5 出错 S5 =1 S4S3S2S1=1001
III.校验位 R1 出错 S5 =1 S4S3S2S1=0001
发生两位错：
设数据位 D1 和 D3 出错：S5 =0 S4S3S2S1=0101

==知识点补充（贼 TMD 重要）==
海明码如果要检测出 N 位错误，需要一个海明距为 N+1 的方案，要纠正 D 位错误需要 2N+1 的编码方案。
海明距：某编码长度中码距最小的为海明距
我们给出一个公式： L-1=D+C 其中（L 位海明距，D 为检查出错误位数，C 为纠错位数，且 C 恒 ≤D,因为海明码的纠错能力恒小于检错能力）
假设要纠正 C 位错误，那么 D 最小等于 C 所以有 L-1=C+C L=2*C+1，假设要发现 D 为错误，C 最小等于 0 则有 L-1=D L=D+1，正好是最开始的那句话。

3.CRC 循环冗余校验码

模 2 运算

模 2 加减运算即异或运算
用的时候直接亦或就好了，相同取 0，不同得 1
模 2 除法运算：
依托模 2 减法。根据被除数或者余数的最高位决定是否做模 2 减法，如果最高位 1 则做模 2 减法，否则不做减法

我们没必要管商是多少，只需要知道最后的余数是多少即可。
生成多项式$G(x)=aX^3+bX^2+cX+d$
生成多项式是一串二进制编码，G。
生成多项式和除数是一一对应，事先选定的。
假设数据位为 D(位数为 d)，G 位数为 r+1 位

发送方： 4. 将 D 左移 r 位，低位补 0，形成 d+r 位信息位 M 5. M 模 2 除 G，得到商和 r 位余数 6. 生成 CRC 编码=M+余数
接收方：
CRC 编码模 2 除 G=（M’+余数’）/G
没有错误：余数为 0,M’=M 余数’=余数
（M’+余数’）/G=（M+余数）/G=M/G+余数/G=商+余数/G+余数/G=商+（余数+余数）/G=商
如果出错：根据余数情况修改或者判断错误

示例：

现假设选择的 CRC 生成多项式为$G（X） = X^4 + X^3 + 1$，要求出二进制序列 10110011 的 CRC 校验码。下面是具体的计算过程：
① 将多项式转化为二进制序列，由$G（X） = X^4 + X^3 + 1$可知二进制一种有五位，第 4 位、第三位和第零位分别为 1，则序列为 11001
② 多项式的位数位 5，则在数据帧的后面加上 5-1 位 0，数据帧变为 101100110000，然后使用模 2 除法除以除数 11001，得到余数。
③ 将计算出来的 CRC 校验码添加在原始帧的后面，真正的数据帧为 101100110100，再把这个数据帧发送到接收端。
④ 接收端收到数据帧后，用上面选定的除数，用模 2 除法除去，验证余数是否为 0，如果为 0，则说明数据帧没有出错。

因为太长了，我们分量部分发。
因为太长了，我们分量部分发。
因为太长了，我们分量部分发。
因为太长了，我们分量部分发。
为了你们阅读体验。

计算机组成原理

『计算机组成原理』数制与编码（校验码，CRC，汉明码详解）

https://chiamzhang.github.io/2024/06/29/『计算机组成原理』数制与编码（校验码，CRC，汉明码详解）/

Author

Chiam

Posted on

June 29, 2024

Licensed under

『计算机组成原理』数据的表示及其运算和运算器（附考研题目） Previous

『计算机组成原理』小老板，我学的计算机组成原理告诉我半导体存储器都是断电后丢失的，为什么U盘SSD（固态硬盘）没事呢？ Next

『计算机组成原理』数制与编码（校验码，CRC，汉明码详解）

『计算机组成原理』数制与编码（校验码，CRC，汉明码详解）

一、考纲

1. 数制与编码

2.定点数的表示和运算

3.浮点数的表示和运算

4.算术逻辑单元(ALU)

二、数制与编码

1.进制及其转换：

1.非十进制数转换成十进制数

2.十进制数转换成非十进制数

3. 八进制数、二进制数互转

3. 十六进制数、二进制数互转

2.真值和机器数的互换

原码，补码，反码，移码

1.原码：符号位+绝对值的二进制(方便读取）

2.补码：正数的补码等于原码(方便运算）

3.反码：正数的反码等于原码（没用）

4.移码：补码符号位取反

5.8421CD 码与余三码

6.字符与字符串

ASCII 码

输入码：音码（汉语拼音) 和形码 (五笔输入法）

区位码

国标码：

机内码

字体库 (了解 即可）

7.校验码

1.奇偶校验码

2.Hamming 校验码

发送方：

接收方：

3.CRC 循环冗余校验码

3. 　八进制数、二进制数互转

3. 　十六进制数、二进制数互转

字体库 (了解即可）