計算機硬件相關基礎知識--校驗碼

校驗碼(熟悉)

碼距：兩個碼字的碼距是一個編碼系統中任意兩個合法編碼之間不同的二進制位數

一般我們描述碼距是指兩個碼字之間的距離，就單個碼字而言，其碼距為1，因為只需要改變一位就會變成另一個編碼

而兩個碼字之間，從A碼到B碼轉換所需要改變的位數就稱為碼距

例1：A:00要轉換為B:11，其第一位不同，第二位也不同，碼距為2

例2：A:00要轉換為B:01，其第一位相同，第二位不同，碼距為1

碼距越大，越利于糾錯和檢錯

奇偶校驗碼(重點)

奇偶校驗碼：在編碼中增加一位校驗位來使編碼中1的個數為奇數或偶數，從而使碼距變為2

奇校驗：編碼中含有奇數個1，發送方發送編碼給接收方，接收方收到后，計算收到的編碼中1的個數，如果是奇數則校驗通過，是偶數則校驗失敗。

偶校驗：編碼中含有偶數個1，發送方發送編碼給接收方，接收方收到后，計算收到的編碼中1的個數，如果是偶數則校驗通過，是奇數則校驗失敗。

例1(奇校驗流程)：原碼：1011100

1. 發送方首先判斷原碼是奇數還是偶數，此原碼為偶數，則增加一位110111001
2. 發送給接收方
3. 接收方收到編碼后，按照奇校驗規則，檢測編碼中1的個數是否為奇數
   假設接收方收到的是10111001，則1的個數為5，通過校驗
   假設接收方收到的事10110001，則1的個數為4，校驗失敗

例2(偶校驗流程)：原碼：1011100

1. 發送方首先判斷原碼是奇數還是偶數，此原碼為偶數，則增加一位0
   10111000
2. 發送給接收方
3. 接收方收到編碼后，按照偶校驗規則，檢測編碼中1的個數是否為偶數
   假設接收方收到的是10111000，則1的個數為4，通過校驗
   假設接收方收到的是10100000，則1的個數為2，通過校驗
   假設接收方收到的是10111001，則1的個數為5，校驗失敗

注意：奇偶校驗只能檢1位錯，即原碼和增加后的編碼僅有1位不同的校驗才會有效，其他情況并不能確定編碼是否為原碼，并且奇偶校驗無法糾錯

CRC校驗碼(重點)

CRC只能檢錯，不能糾錯。使用CRC編碼需要先約定一個生成多項式G(x)，生成多項式的最高位和最低位必須是1。

假設原始信息有m位，則對應多項式M(x)。簡而言之：生成校驗碼思想就是在原始信息位后面追加若干校驗位，使得追加的信息能被G(x)整除。接收方接收到帶校驗位的信息，然后用G(x)整除。余數為0則沒有錯誤，否則校驗失敗

CRC校驗碼流程：

1. 在原始信息位后面添0，假設生成多項式的階是r，則在原始信息位后添加r個0
2. 由多項式得到除數，除數的位數為多項式x的最高次冪加一，多項中x的冪指數存在的位置值為1，不存在的位置值為0
3. 生成CRC校驗碼，將前兩步得出的除數和被除數進行模2除法運算，即異或運算(同0非1)；得到余數后，如果余數不足r個，則在余數左邊用0補齊
4. 將余數添加到原始信息后，即可生成最終發送信息串
5. 接收方接收到帶校驗和的幀后，用多項式G(x)來除，余數為0則校驗通過，余數不為0則校驗失敗

注意事項

• 收發雙向需要使用相同的生成多項式
• 除數和被除數相除之后的結果必然小于等于r，不可能大于r，如果大于r就要檢查自己是否算錯了

例1：原始信息串：10110，CRC的生成多項式為：，求校驗碼：

1. G(x)的階為4，則在原始信息串后加4個0，得到的新串：101100000(被除數)
2. G(x)的階為4，則除數的位數為4+1=5，G(x)中x的冪指數為0,1,4的變量都存在，而冪指數為2,3的不存在，則得到串：10011(除數)
3. 使用除數和被除數進行模2除法運算，得到余數1111
4. 將余數添加到原始信息串后面，得到最終發送信息串：101101111
5. 接收方使用多項式G(x)得到的除數10011來除，得到最后的余數，余數為0則校驗通過，否則校驗失敗