#軟考##計算機##程序員##中級軟考#

校驗碼

• 碼距

1. 兩個編碼中，A碼變為B碼所需要改變的位數。
2. 如10101和00110，第一、四、五位都不同，則碼距為5。

• 三種基本校驗方式：奇偶校驗碼、循環冗餘校驗碼、海明校驗碼。

奇偶校驗

• 奇校驗：校驗編碼中是否有奇數個1。
• 偶校驗：校驗編碼中是否有偶數個1。

循環冗餘校驗碼CRC

• CRC隻能檢錯，不能糾錯。
• 一個能整除某個多項式的編碼。
• 将原始報文除以指定多項式，将所得餘數作為校驗位加在原始報文之後，再作為發送數據發給接收方。
• 形式為：|←數據位→|←校驗位→|

1）特點

• 校驗碼由信息碼産生
• 校驗碼位數越長，校驗能力越強

2）校驗方法

（1）先将多項式轉為二進制表示，規則為：根據多項式幂指數看第n位有沒有x的n-1次方，有則為1，無則為0。

• 例如多項式：x^4＋x^3＋x＋1，第1位x^0＝1，有；第2位x^1，有；第3位x^2，無；第4第5同理。則此多項式為11011。

（2）在原始報文後面加上多項式最高幂指數個0（以上例則為4個0）。

（3）原始報文與多項式二進制數進行模2運算。

（4）将最後的餘數作為校驗碼，與原始報文拼接，再發送出去。

（5）接收方将收到的數據與多項式二進制數進行模2運算，若餘數為0，則校驗正确，數據傳輸正确。

• 試題1（2017年上半年試題14）

循環冗餘校驗碼（Cyclic Redundancy Check，CRC）是數據通信領域中最常用的一種差錯校驗碼，該校驗方法中，使用多項式除法（模2除法）運算後的餘數為校驗字段。若數據信息為n位，則将其左移k位後，被長度為k＋1位的生成多項式相除，所得的k位餘數即構成k個校驗位，構成n＋k位編碼。若數據信息為1100，生成多項式為X^3＋X＋1（即1011），則CRC編碼是（）。

A.1100010

B.1011010

C.1100011

D.1011110

解：（1）題目已給二進制表示

（2）多項式最高幂指數為3，則原始報文後加3個0：1100000

（3）模2運算結果商為111，餘數為10

（4）因為餘數必須為k-1位，k=3。所以餘數應為010，所以發送出去的報文為1100010。

海明校驗碼

1）性質

在數據位之間的确定位置插入K個校驗位，通過擴大碼距實現檢錯和糾錯。

校驗碼位數：2^r - 1 >= n k（n是信息碼位數，k是校驗碼位數）。

2）生成過程

設信息位1011：

（1）由2^r - 1 >= n k得K＝3，校驗碼為3位，占位是1，2，4位。

（2）将信息位拆分成二進制表示。即

7＝4＋2＋1

6 = 4 2

5 = 4 1

3 = 2 1

展開的二進制表示：第7位的信息位由第4、2、1位的校驗碼共同校驗，其它同理。

（3）找出每個校驗位有關聯的信息位，進行異或求值。如校驗位4關聯的信息位是7、6、5，異式得0；校驗位2同理，得0；校驗位1同理，得1。

（4）最終發送的海明碼為1010101。

3）檢錯

（1）接收到海明碼後，将每一位校驗位與其關聯的信息位進行異或。如上例則為第4位校驗位與

第7、6、5位信息位進行異或。

r2異或i4異或i3異或i2→0

r1異或i4異或i3異或i1→0

r0異或i4異或i2異或i1→0

（2）如果是偶校驗則為0，奇校驗則為1。

4）糾錯

假設上例接收出錯，為1011101，并且是偶校驗，則糾錯過程為：

（1）

r2異或i4異或i3異或i2 = 1異或1異或0異或1 = 1

r1異或i4異或i3異或i1 = 0異或1異或0異或1 = 0

r0異或i4異或i2異或i1 = 1異或1異或1異或1 = 0

（2）将檢錯結果排列為二進制：100，這個100就是指出錯的位置，即第4位。

（3）糾錯方法就是将出錯位取反。

以上知識點來源于我看完《軟件設計師教程》第五版的相關知識點做的彙總，關注我，後續将會持續追更筆記。望各位軟考順利上岸~

圖片版：

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!