当前位置：首页 > article >正文

2024年11月1日Day2第一部分（最详细简单有趣味的介绍2

article 2024/11/2 21:16:00

1.CRC编解码练习

要计算CRC（循环冗余校验）码并验证及纠正接收到的数据，我们需要按照以下步骤进行：

步骤 1: 计算CRC校验码

信息字段代码: x=1001
生成多项式: G(x)=x3+x2+1，即 G(x)=1101（注意：这里的最高次项系数默认为1，不写出来）
多项式公式对于CRC标准除数，一般使用多项式（或二项式）公式表示，如下图中除数11011（poly值为0x1b）的二项式为G(X)=X4+X3+X+1，X的指数就代表了该bit位上的数据为1,（最低位为0）。

计算步骤：

在信息字段后添加生成多项式位数-1个0：
- 信息字段 x=1001
- 生成多项式 G(x) 为3次多项式，所以添加2个0：
  100100
用生成多项式 G(x) 对扩展后的信息字段进行模2除法：
- 被除数：100100
- 除数：1101
模2除法过程：
- 从左到右，1001除以1101不够除，记0；
- 把下一个0带上，10010除以1101不够除，记0；
- 把下一个0带上，100100除以1101：
  - 1101（减去1101得00100）
  - 余数00100，继续除以1101：
    - 0000（减去0000得100）
    - 余数100，不够再除，记下100作为余数。
结果：
- 商：001（这个在CRC中通常不需要）
- 余数：100
余数就是CRC校验码：
- CRC校验码：100

所以，发送的完整数据（信息字段+CRC校验码）为：1001100

步骤 2: 验证并纠正接收到的数据

假设接收到的数据为：x′=1101

验证步骤：

同样在信息字段后添加生成多项式位数-1个0：
- 信息字段（去掉CRC部分）：110（因为发送的是1001100，去掉CRC部分100）
- 添加2个0：11000
用生成多项式 G(x) 对扩展后的信息字段进行模2除法：
- 被除数：11000
- 除数：1101
模2除法过程：
- 从左到右，1100除以1101不够除，记0；
- 把下一个0带上，11000除以1101：
  - 1101（减去1101得0000）
  - 余数0000
结果：
- 商：10（这个在CRC中通常不需要）
- 余数：000
验证接收的数据是否正确：
- 如果余数为0，则数据正确；
- 如果余数不为0，则数据错误，且余数指示错误位置（从右向左数，从1开始）。

在本例中，余数为000，说明接收到的数据（不考虑CRC部分）本身是正确的，但显然由于某种原因（可能是传输错误），CRC部分被改变了。

纠正错误：

由于我们知道发送的完整数据应为 1001100，而接收到的数据为 1101，可以推断出错误发生在第2位（从右向左数，第2位从1开始计数）。

发送数据：1001100
接收数据：1101（错误）

将接收到的数据第2位纠正为正确的值：

原数据：1101
纠正后：1001（与发送数据的信息字段部分相同）

然后，我们可以重新加上已知的CRC校验码100，得到正确的完整数据：

纠正后的完整数据：1001100

这样，我们就验证了接收到的数据并纠正了错误。

步骤 3:图文教程

CRC检验演示

先提一下异或运算，相同得0，相异的1

只要是CRC算法就离不开多项式算术，使用多项式算术是为了在进行二进制计算时无需考虑进位问题

第一步，展开多项式得到CRC除数

CRC中用到的除数，正是由多项式的各项系数组成，所以为了得到除数，我们只需观察简写式列出的项即可。

第二步，我们要在原数据串末端加“0”，0的数量由多项式决定，所以多项式的阶数是多少就加几个0，假设数据穿为1101011011，那么处理后的数据串就是1101011011000000

数据串：1101011011000000

除数： 1010111

第三步，从左往右，按位异或

当异或最后结果有效位数较少时，最后拼接校验和的时候，不要漏掉前面的0，具体来说，所拼接的校验和长度应与之前加0的个数相等（或者等于除数长度-1）

CRC检验的直观计算过程

2.计算机组成原理题目集

1.比较大小

(9)[2014]foat 型数据通常用IEE754单精度浮点格式表示。假定两个foat型变量x和y分别存放在 32位寄存器日和中，若(f1)=CC90 0000H，(f2)=B0C00000H，则x和y之间的关系为 A.x<y且符号相同 C.x>y且符号相同 B.x<y且符号不同 D.x>y且符号不同

首先，我们需要将给定的十六进制数转换为IEEE 754单精度浮点数的二进制表示，然后分析它们的符号和数值大小。

解析(f1) = CC90 0000H：
- 符号位：最高位是1，表示负数。
- 阶码：接下来的8位是C9（即二进制11001001），转换为十进制是201。由于IEEE 754使用偏移量127，所以实际的阶码是201 - 127 = 74。
- 尾数：剩下的23位是0000 0000 0000 0000 0000，由于IEEE 754规格化数的尾数隐含了一个最左边的1，所以实际的尾数是1.0（但这里尾数的其余部分都是0，表示精度很低）。
- 结合起来，这个数表示的是-1.0 * 2^74（但由于尾数的精度问题，实际上它只是一个近似值，但在这个问题中我们可以忽略这种精度损失）。
解析(f2) = B0C0 0000H：
- 符号位：最高位是1，也表示负数。
- 阶码：接下来的8位是0C（即二进制00001100），转换为十进制是12。实际的阶码是12 - 127 = -115。
- 尾数：和(f1)一样，是0000 0000 0000 0000 0000，表示的是1.0（近似值）。
- 结合起来，这个数表示的是-1.0 * 2^-115（同样忽略了精度损失）。

现在，我们来比较x和y：

符号：x和y的符号位都是1，所以它们的符号相同，都是负数。
数值大小：由于x的阶码（74）大于y的阶码（-115），而阶码决定了浮点数的大小（在符号相同的情况下），所以x的绝对值大于y的绝对值。但因为它们都是负数，所以数值上x < y（在数轴上，更小的绝对值实际上表示更靠左的位置，即更小的数）。

综上所述，x和y之间的关系是x < y且符号相同。

正确答案是A：x < y且符号相同。

3.运算方法和运算器

1.基本概念

二. 原码, 反码, 补码的基础概念和计算方法.

在探求为何机器要使用补码之前, 让我们先了解原码, 反码和补码的概念.对于一个数, 计算机要使用一定的编码方式进行存储. 原码, 反码, 补码是机器存储一个具体数字的编码方式.

1. 原码

原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值. 比如如果是8位二进制:

[+1]原 = 0000 0001

[-1]原 = 1000 0001

第一位是符号位. 因为第一位是符号位, 所以8位二进制数的取值范围就是:

[1111 1111 , 0111 1111]

即

[-127 , 127]

原码是人脑最容易理解和计算的表示方式.

2. 反码

反码的表示方法是:

正数的反码是其本身

负数的反码是在其原码的基础上, 符号位不变，其余各个位取反.

[+1] = [00000001]原 = [00000001]反

[-1] = [10000001]原 = [11111110]反

可见如果一个反码表示的是负数, 人脑无法直观的看出来它的数值. 通常要将其转换成原码再计算.

3. 补码

补码的表示方法是:

正数的补码就是其本身

负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)

[+1] = [00000001]原 = [00000001]反 = [00000001]补

[-1] = [10000001]原 = [11111110]反 = [11111111]补

对于负数, 补码表示方式也是人脑无法直观看出其数值的. 通常也需要转换成原码在计算其数值.

2.基本方法

1.求补码

要找出X=−55的8位二进制补码，我们可以按照以下步骤进行：

转换55为二进制：
首先，我们需要将55转换为二进制。
5510=1101112
求55的二进制原码：
由于是正数，其原码就是其二进制表示，前面加上一个0作为符号位（表示正数）。
原码：001101112
求55的二进制反码：
正数的反码与原码相同。
反码：001101112
求55的二进制补码：
对于负数，补码是原码取反后加1。但在这里，我们有一个更简单的方法：直接对正数的二进制表示（不包括符号位）取反加1，然后前面加上1作为符号位（表示负数）。
对1101112取反得到0010002，再加1得到0010012。
所以，-55的8位二进制补码是：100100112

综上所述，X=−55的8位二进制补码是100100112。

2.判断溢出

1. 已知 X=+0.1010，Y=+0.1001，用变形补码求 X+Y，并判定是否产生溢出？

变形补码（也称为偏移二进制码或偏置二进制码）通常用于浮点数的尾数部分，以确保加法运算的正确性。对于小数，变形补码通常是将数值范围偏移一个固定的量（如 2n 的一半，其中 n 是小数部分的位数），以便能够表示 −1 到 1−2−n 范围内的数。但在这里，我们简化处理，只考虑8位二进制数（包括1位符号位和7位数值位）来表示这两个小数，并使用一种简化的变形补码方法。

由于 X 和 Y 都是正数，我们可以直接忽略符号位（假设它总是0），并将它们视为纯二进制小数进行加法运算。但需要注意的是，这种表示方法是有局限性的，因为它不能准确地表示所有小数（特别是当它们接近1时）。

步骤：

将 X 和 Y 的二进制小数部分对齐。
执行二进制加法运算。
检查是否发生溢出（即结果是否超出了7位二进制小数能表示的范围）。

计算：

X=0.1010（二进制小数）
Y=0.1001（二进制小数）

对齐后相加：

0.1010

0.1001

0.10111 （注意这里产生了8位结果，但我们只保留7位有效小数）

由于我们只保留了7位有效小数（即 0.10111），因此结果没有溢出7位二进制小数能表示的范围（即 0 到 1−2−7）。但需要注意的是，这种表示方法是有误差的，因为真实的和应该是 0.1010+0.1001=0.2011（二进制），而我们只能表示到小数点后7位。

然而，在这个特定的问题中，我们并没有真正的“溢出”问题，因为我们的结果仍然是一个有效的7位二进制小数（尽管它是有误差的）。如果我们考虑的是8位二进制数（包括符号位），并且结果超出了这个范围（比如变成了 1.xxxxxxx 或 −0.xxxxxxx），那么我们就可以说发生了溢出。但在这个例子中，并没有发生这种情况。

结论：

X+Y=0.10111（二进制小数，有误差），没有发生溢出。

3. 已知 X=−55，Y=−90，用变形补码求 X+Y、X+Y/2，并判定是否产生溢出？

对于整数，变形补码通常就是普通的二进制补码，只是我们可能需要对结果进行偏移或调整以适应特定的表示范围。但在这里，我们直接使用二进制补码进行计算。

步骤：

将 X 和 Y 转换为8位二进制补码表示（假设是8位机）。
执行二进制补码加法运算求 X+Y。
检查是否发生溢出。
计算 X+Y/2（注意这里的除法是先对 Y 进行除法运算，然后再与 X 相加；但在这个问题中，我们可以先求 X+Y，然后再将结果除以2，因为加法和除法的顺序在这个特定的问题中不影响最终的结果是否溢出）。
再次检查是否发生溢出。

计算：

X=−55，8位二进制补码是 10110101。
Y=−90，8位二进制补码是 11011010。

求 X+Y：

10110101

11011010

110100001 （9位结果，最高位是溢出位）

由于我们使用的是8位二进制补码表示，因此最高位的1是溢出位。忽略这个溢出位后，我们得到的结果是 01000001，但这是错误的，因为我们应该考虑溢出的情况。正确的做法是识别到溢出并确定它是正溢出还是负溢出。在这个例子中，由于两个负数相加得到了一个看似正数的结果（如果我们忽略溢出位的话），因此发生了负溢出。

然而，为了符合题目的要求并继续计算 X+Y/2，我们可以先不考虑溢出地计算 X+Y 的8位结果（即只保留低8位）：01000001（这是一个错误的、未考虑溢出的结果）。然后我们将这个结果除以2（在二进制中通过右移一位来实现，注意这里我们不考虑算术右移和逻辑右移的区别，只是简单地右移一位并丢弃最低位）：

01000001 >> 1 = 00100000

这个结果 00100000 是正确的8位二进制表示（如果我们不考虑之前的溢出的话），它等于十进制的32。但需要注意的是，这个结果是基于我们之前未考虑溢出的错误计算。

正确的做法：

由于 X+Y 发生了负溢出，我们应该识别这一点，并意识到在8位二进制补码表示下，我们不能准确地表示这个结果。对于 X+Y/2，我们应该先正确地计算 Y/2（即 −90/2=−45），然后将其转换为8位二进制补码（即 11001011），再与 X 的补码相加。但在这个特定的问题中，我们只需要知道 X+Y 发生了溢出，并且 X+Y/2 的计算也会受到之前溢出错误的影响。

结论：

X+Y 发生了负溢出。

X+Y/2 的计算受到之前溢出错误的影响，因此其结果也是不正确的（尽管在这个例子中我们给出了一个基于未考虑溢出的8位二进制结果）。

注意：在实际应用中，当检测到溢出时，通常会采取一些措施来处理它（比如抛出一个异常、使用更大的数据类型来表示结果等）。在这个例子中，我们只是简单地识别了溢出的发生。

5.下一周的预习