“软件设计师精讲 校验码概述”的版本间的差异

来自姬鸿昌的知识库
跳到导航 跳到搜索
（建立内容为“https://www.bilibili.com/video/BV13U4y1E7oA/?p=8”的新页面）
 
 
（未显示同一用户的34个中间版本）
第1行： 第1行：
 
https://www.bilibili.com/video/BV13U4y1E7oA/?p=8
 
https://www.bilibili.com/video/BV13U4y1E7oA/?p=8
 +
 +
=== 校验码 ===
 +
考点1：奇偶校验码
 +
 +
考点2：CRC循环冗余校验码
 +
 +
考点3：海明校验码
 +
 +
 +
https://www.bilibili.com/video/BV13U4y1E7oA/?p=9
 +
 +
==== 校验码-校验码基础知识 ====
 +
码距：任何一种编码都由许多码字构成，任意两个码字之间最少变化的二进制位数就称为数据校验码的码距。
 +
 +
例如：用4位二进制表示16种状态，则有16个不同的码字，此时码距为1。如 0000 和 0001。
 +
 +
 +
 +
==== 校验码-奇偶校验 ====
 +
奇偶校验码的编码方法是：由若干位有效信息（如一个字节），再加上一个二进制位（校验位）组成校验码。
 +
 +
 +
奇校验：整个校验码（有效信息位和校验位）中“1”的个数为奇数。
 +
 +
假如：最开始传递信息的时候，“男”用1位二进制 "0" 来表示，“女”用二进制“1”来表示，传递信息的过程当中，1位二进制不好区分对错，如果接收方接收到1个“1”的话，如果要确定有没有错误，就不能确定，因为仍然在合法的码字当中，可以通过扩大码距所谓的校验一般都是通过扩大码距来进行校验、解决问题的。
 +
 +
例：如果采用奇校验的方式，信息位拼接上校验位之后，里面“1”的个数是奇数，拼接过程当中，信息位+校验位，“男”的“0”就变成“01”（后面加“1”，保持奇数个“1”），女的“1”就变成“10”（后面加“0”，保持奇数个“1”），接收方在接收后首先就是检查有多少个“1”，此时如果接收方收到了“00”或者“11”就可以确认传输数据有错（偶数个“1”不满足奇校验）。
 +
 +
偶校验：整个校验码（有效信息位和校验位）中“1”的个数为偶数。
 +
 +
 +
注意：其实如果发送“11”，收到了“00”，奇偶校验就不能确认数据有错（同时存在多位错误），所以奇偶校验是有局限性的，只能检错部分情况，且并不能确定是哪个位置出错，所以奇偶校验只能进行检错，不能纠错。
 +
 +
'''<big>奇偶校验，可检查1位（奇数位）的错误，不可纠错。</big>'''
 +
 +
=== 例题讲解 ===
 +
以下关于采用一位奇校验方法的叙述中，正确的是（C）。
 +
 +
A、若所有奇数位出错，则可以检测出该错误但无法纠正错误
 +
 +
B、若所有偶数位出错，则可以检测出该错误并加以纠正
 +
 +
C、若有奇数个数据位出错，则可以检测出该错误但无法纠正错误
 +
 +
D、若有偶数个数据位出错，则可以检测出该错误并加以纠正
 +
 +
 +
https://www.bilibili.com/video/BV13U4y1E7oA/?p=10
 +
 +
=== CRC循环冗余校验码 ===
 +
CRC校验，'''<big>可检错，不可纠错</big>'''。
 +
 +
CRC的编码方法是：<u>在k位信息码之后拼接r位校验码</u>。应用CRC码的关键是如何从k位信息位简便地得到r位校验位（编码），以及如何从k+r位信息码判断是否出错。
 +
 +
 +
把接收到的CRC码用约定的生成多项式G（X）去'''<big>除（模二除法）</big>'''，<u>如果正确，则余数为0；如果某一位出错，则余数不为0</u>。不同的位数出错其余数不同，余数和出错位序号之间有惟一的对应关系。
 +
 +
=== 例题讲解 ===
 +
在（D）校验方法中，采用模2运算来构造校验位。
 +
 +
A、水平奇偶
 +
 +
B、垂直奇偶
 +
 +
C、海明码
 +
 +
D、循环冗余
 +
 +
 +
https://www.bilibili.com/video/BV13U4y1E7oA/?p=11
 +
 +
=== 海明校验码 ===
 +
'''海明校验，可检错，也可纠错。'''
 +
 +
海明校验码的原理是：在有效信息位中加入几个校验位形成海明码，使码距比较均匀地拉大，
 +
 +
并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，
 +
 +
这不但可以发现错误，还能指出错误的位置，为自动纠错提供了依据。
 +
 +
<u>'''校验位求取公式：2<sup>r</sup>≥m+r+1，也可以写成：2<sup>r</sup>-1≥m+r，r是最小值，m是信息位的个数'''</u>。
 +
 +
比如：要传递16位信息，那这16位信息在编码的过程当中，要2<sup>r</sup>≥16+r+1，r=4时，2<sup>r</sup>=16，2<sup>r</sup>≥16+r+1不成立；
 +
 +
r>=5，才满足2<sup>r</sup>≥16+r+1，所以海明校验位是5位。
 +
 +
要求能够通过信息位将校验码位数求出来。
 +
 +
具体校验位放在哪里呢？5个校验码分别放在 2<sup>0</sup>,2<sup>1</sup>,2<sup>2</sup>,2<sup>3</sup>,2<sup>4</sup>。
 +
 +
也就是放在1，2，4，8，16位上，其它位置放上信息位
 +
{| class="wikitable"
 +
|+
 +
!
 +
!校验码位数
 +
!校验码位置
 +
!检错
 +
!纠错
 +
!校验方式
 +
|-
 +
|奇偶校验
 +
|1
 +
|一般拼接在头部
 +
|可检奇数位错
 +
|不可纠错
 +
|奇校验：最终1的个数是奇数个；
 +
偶校验：最终1的个数是偶数个；
 +
|-
 +
|CRC循环冗余校验
 +
|生成多项式最高次幂决定
 +
|拼接在信息位尾部
 +
|可检错
 +
|不可纠错
 +
|模二除法求余数，拼接作为校验位
 +
|-
 +
|海明校验
 +
|2<sup>r</sup>≥m+r+1
 +
|插入在信息位中间
 +
|可检错
 +
|可纠错
 +
|分组奇偶校验
 +
|}
 +
 +
=== 例题讲解 ===
 +
以下关于海明码的叙述中，正确的是（A）。
 +
 +
A、海明码利用奇偶性进行检错和纠错
 +
 +
B、海明码的码距为1
 +
 +
C、海明码可以检错但不能纠错
 +
 +
D、海明码中数据位的长度和校验位的长度必须相同
 +
 +
 +
 +
海明码是一种纠错码，其方法是为需要校验的数据位增加若干校验位，使得校验位的值决定于被校位的数据，当被校数据出错时，可根据校验位的值的变化找到出错位，从而纠正错误。
 +
 +
对于32位的数据，至少需要增加（）个校验位才能构成海明码。
 +
 +
以10位数据为例，其海明码表示 D<sub>9</sub>D<sub>8</sub>D<sub>7</sub>D<sub>6</sub>D<sub>5</sub>D<sub>4</sub>P<sub>4</sub>D<sub>3</sub>D<sub>2</sub>D<sub>1</sub>P<sub>3</sub>D<sub>0</sub>P<sub>2</sub>P<sub>1</sub> 中,其中 D<sub>i</sub>（0≤i≤9）表示数据位，P<sub>j</sub>（1≤j≤4）表示校验位，数据位D<sub>9</sub>由P<sub>4</sub>、P<sub>3</sub>和P<sub>2</sub>进行校验（从右至左D<sub>9</sub>的位序为14，即等于8+4+2，
 +
 +
因此用第8位的P<sub>4</sub>、第4位的P<sub>3</sub>和第2位的P<sub>2</sub>校验），数据位D<sub>5</sub>由（）进行校验。
 +
 +
问题1
 +
{| class="wikitable"
 +
|+问题1
 +
!A、3
 +
!B、4
 +
!C、5
 +
!D、6
 +
|}
 +
{| class="wikitable"
 +
|+问题2
 +
!A、P<sub>4</sub>P<sub>1</sub>
 +
!B、P<sub>4</sub>P<sub>2</sub>
 +
!C、P<sub>4</sub>P<sub>3</sub>P<sub>1</sub>
 +
!D、P<sub>3</sub>P<sub>2</sub>P<sub>1</sub>
 +
|}
 +
 +
解析：
 +
 +
问题1
 +
 +
因为 2<sup>r</sup>≥n+r+1，所以 2<sup>r</sup>≥32+r+1、2<sup>r</sup>≥33+r，r为6时满足，所以答案是D。
 +
 +
问题2
 +
{| class="wikitable"
 +
|+
 +
!位序
 +
!14
 +
!13
 +
!12
 +
!11
 +
!10
 +
!9
 +
!8
 +
!7
 +
!6
 +
!5
 +
!4
 +
!3
 +
!2
 +
!1
 +
|-
 +
!数据位
 +
|D<sub>9</sub>
 +
|D<sub>8</sub>
 +
|D<sub>7</sub>
 +
|D<sub>6</sub>
 +
|D<sub>5</sub>
 +
|D<sub>4</sub>
 +
|P<sub>4</sub>
 +
|D<sub>3</sub>
 +
|D<sub>2</sub>
 +
|D<sub>1</sub>
 +
|P<sub>3</sub>
 +
|D<sub>0</sub>
 +
|P<sub>2</sub>
 +
|P<sub>1</sub>
 +
|}
 +
 +
位序14 是 8+4+2，D<sub>5</sub> 的位序是10，是 8+2，是用第 8 位的 P<sub>4</sub> 和第 2 位的 P<sub>2</sub> 校验，所以答案是B。
 +
 +
 +
 +
 +
 +
 +
=== 什么是码距？ ===

2024年4月14日 (日) 04:11的最新版本

https://www.bilibili.com/video/BV13U4y1E7oA/?p=8

校验码

考点1：奇偶校验码

考点2：CRC循环冗余校验码

考点3：海明校验码


https://www.bilibili.com/video/BV13U4y1E7oA/?p=9

校验码-校验码基础知识

码距：任何一种编码都由许多码字构成，任意两个码字之间最少变化的二进制位数就称为数据校验码的码距。

例如：用4位二进制表示16种状态，则有16个不同的码字，此时码距为1。如 0000 和 0001。


校验码-奇偶校验

奇偶校验码的编码方法是：由若干位有效信息（如一个字节），再加上一个二进制位（校验位）组成校验码。


奇校验：整个校验码（有效信息位和校验位）中“1”的个数为奇数。

假如：最开始传递信息的时候，“男”用1位二进制 "0" 来表示，“女”用二进制“1”来表示，传递信息的过程当中，1位二进制不好区分对错，如果接收方接收到1个“1”的话，如果要确定有没有错误，就不能确定，因为仍然在合法的码字当中，可以通过扩大码距所谓的校验一般都是通过扩大码距来进行校验、解决问题的。

例：如果采用奇校验的方式，信息位拼接上校验位之后，里面“1”的个数是奇数，拼接过程当中，信息位+校验位，“男”的“0”就变成“01”（后面加“1”，保持奇数个“1”），女的“1”就变成“10”（后面加“0”，保持奇数个“1”），接收方在接收后首先就是检查有多少个“1”，此时如果接收方收到了“00”或者“11”就可以确认传输数据有错（偶数个“1”不满足奇校验）。

偶校验：整个校验码（有效信息位和校验位）中“1”的个数为偶数。


注意：其实如果发送“11”，收到了“00”，奇偶校验就不能确认数据有错（同时存在多位错误），所以奇偶校验是有局限性的，只能检错部分情况，且并不能确定是哪个位置出错，所以奇偶校验只能进行检错，不能纠错。

奇偶校验，可检查1位（奇数位）的错误，不可纠错。

例题讲解

以下关于采用一位奇校验方法的叙述中，正确的是（C）。

A、若所有奇数位出错，则可以检测出该错误但无法纠正错误

B、若所有偶数位出错，则可以检测出该错误并加以纠正

C、若有奇数个数据位出错，则可以检测出该错误但无法纠正错误

D、若有偶数个数据位出错，则可以检测出该错误并加以纠正


https://www.bilibili.com/video/BV13U4y1E7oA/?p=10

CRC循环冗余校验码

CRC校验，可检错，不可纠错。

CRC的编码方法是：在k位信息码之后拼接r位校验码。应用CRC码的关键是如何从k位信息位简便地得到r位校验位（编码），以及如何从k+r位信息码判断是否出错。


把接收到的CRC码用约定的生成多项式G（X）去除（模二除法），如果正确，则余数为0；如果某一位出错，则余数不为0。不同的位数出错其余数不同，余数和出错位序号之间有惟一的对应关系。

例题讲解

在（D）校验方法中，采用模2运算来构造校验位。

A、水平奇偶

B、垂直奇偶

C、海明码

D、循环冗余


https://www.bilibili.com/video/BV13U4y1E7oA/?p=11

海明校验码

海明校验，可检错，也可纠错。

海明校验码的原理是：在有效信息位中加入几个校验位形成海明码，使码距比较均匀地拉大，

并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，

这不但可以发现错误，还能指出错误的位置，为自动纠错提供了依据。

校验位求取公式：2r≥m+r+1，也可以写成：2r-1≥m+r，r是最小值，m是信息位的个数。

比如：要传递16位信息，那这16位信息在编码的过程当中，要2r≥16+r+1，r=4时，2r=16，2r≥16+r+1不成立；

r>=5，才满足2r≥16+r+1，所以海明校验位是5位。

要求能够通过信息位将校验码位数求出来。

具体校验位放在哪里呢？5个校验码分别放在 20,21,22,23,24。

也就是放在1，2，4，8，16位上，其它位置放上信息位

校验码位数 校验码位置 检错 纠错 校验方式
奇偶校验 1 一般拼接在头部 可检奇数位错 不可纠错 奇校验：最终1的个数是奇数个；

偶校验：最终1的个数是偶数个；

CRC循环冗余校验 生成多项式最高次幂决定 拼接在信息位尾部 可检错 不可纠错 模二除法求余数，拼接作为校验位
海明校验 2r≥m+r+1 插入在信息位中间 可检错 可纠错 分组奇偶校验

例题讲解

以下关于海明码的叙述中，正确的是（A）。

A、海明码利用奇偶性进行检错和纠错

B、海明码的码距为1

C、海明码可以检错但不能纠错

D、海明码中数据位的长度和校验位的长度必须相同


海明码是一种纠错码，其方法是为需要校验的数据位增加若干校验位，使得校验位的值决定于被校位的数据，当被校数据出错时，可根据校验位的值的变化找到出错位，从而纠正错误。

对于32位的数据，至少需要增加（）个校验位才能构成海明码。

以10位数据为例，其海明码表示 D9D8D7D6D5D4P4D3D2D1P3D0P2P1 中,其中 Di（0≤i≤9）表示数据位，Pj（1≤j≤4）表示校验位，数据位D9由P4、P3和P2进行校验（从右至左D9的位序为14，即等于8+4+2，

因此用第8位的P4、第4位的P3和第2位的P2校验），数据位D5由（）进行校验。

问题1

问题1
A、3 B、4 C、5 D、6
问题2
A、P4P1 B、P4P2 C、P4P3P1 D、P3P2P1

解析：

问题1

因为 2r≥n+r+1，所以 2r≥32+r+1、2r≥33+r，r为6时满足，所以答案是D。

问题2

位序 14 13 12 11 10 9 8 7 6 5 4 3 2 1
数据位 D9 D8 D7 D6 D5 D4 P4 D3 D2 D1 P3 D0 P2 P1

位序14 是 8+4+2，D5 的位序是10，是 8+2，是用第 8 位的 P4 和第 2 位的 P2 校验，所以答案是B。




什么是码距？

取自“https://www.jihongchang.top/index.php?title=软件设计师精讲_校验码概述&oldid=7424”