錯誤檢驗與糾錯確實是計算機在處理、存儲和傳輸信息時非常重要的一部分。 就算計算機再強大，處理的數據都是錯誤的，那又有何用? 就算你再努力，方向是錯的，到頭來還不是一場空 就算是人算，也難免會出錯。想起一個遙遠的故事，那個算錯了小數點而自殺提前去天堂占座的數學家,,,,,,不過似乎自殺的話去不了天堂?不太懂,,,,,, 所謂錯誤，就是對於計算機中的用1和0表示的二進制數據來說，某個或某些位在某種影響下改變了，比如原本的“0001”的第二位受到了某種神秘的影響，導致數據變成了“0011”，自然是很大的錯誤。 某種神秘的影響包括
電磁干擾，輻射，震動,,,,,, 設備的老化、損壞,,,,,,
奇偶校驗碼
分析一個問題最常見的思維就是從最簡單的情況入手 奇偶檢驗碼的原理：
多設置一個位(檢驗位)來記錄一個二進制數據也就是一串01裡面所包含的1的個數的奇偶性 根據不同的實現方式，分為奇檢驗和偶檢驗 奇檢驗Odd Parity
檢驗位為1，表示數據(不包含檢驗位)中1的個數為偶數個，加上檢驗位的話也就是由“奇數”個，正所謂奇檢驗 檢驗位為0，表示數據(不包含檢驗位)中1的個數為奇數個，本來就已經是奇數了，那就不需要檢驗位的幫忙了，檢驗位取0就好 偶檢驗Even Parity
和奇檢驗相對稱。 怎麼算?還記得神奇的異或運算嗎?
兩個數做異或運算
相同為0 不同為1 而n個數做異或運算
如果n個數中有奇數個1，則結果為1 如果n個數中有偶數個1，則結果為0 異或大法好，一下就可以得出奇偶性了。 為啥這樣規定?
直覺上我們想，奇檢驗的檢驗位為1，1表示真，也就是數據中“真的有奇數個1” 但是實際在編碼的時候，檢驗位也屬於數據啊!所以奇檢驗的檢驗位為1所表示的“真”的含義，就是所有的數據位包括檢驗位中1的個數為奇數個。 這樣也方便計算機實現，而不需要單獨把檢驗位挑出來，只需要事先規定好我們用的是奇檢驗還是偶檢驗就可以。
對於奇檢驗，我們把所有的數據包括檢驗位一起做XOR運算，如果結果為1則認為數據沒出錯，否則認為數據有誤。 對於偶檢驗，一起做XOR的結果應當為0才認為數據沒有出錯。 然而奇偶檢驗只能發現“奇數個數據位的錯誤”，因為“奇數”才能影響原本的奇偶性 不過因為實現起來很簡單，而且實際上占不小比例的錯誤都只是一個位的出錯，所以奇偶檢驗應用很廣泛
海明碼
但畢竟奇偶檢驗的檢驗能力太低，而且只能“檢驗”而不能“糾錯”，在數據的准確性要求更高的領域裡，奇偶檢驗顯然就不足以支撐台面了
格雷(Marcel Golay)於1949年、海明(Richar Hamming)於1950年分別獨立設計了一種具備糾錯能力的編碼。後來被人們稱為海明碼。
基於信息編碼理論的最小碼距的概念，海明碼的最小碼距為3，具有檢查並糾正一位錯誤，檢測兩位錯誤的能力。
最小碼距：在一套編碼系統中，任意一個合法的編碼變成另外一個合法的編碼所必須改變的最少的二進制位數。 如奇偶檢驗的最小碼距為2，這是因為最少需要改變兩個位就可以不改變原本1的個數的奇偶性，從而通過了奇偶檢驗。
細說海明碼
海明碼具有多個檢驗位，具體多少個還得根據原本數據的長度來算。
而且這多個檢驗位是和數據位混雜在一起的，不過也有規律可循就是了
編碼位設置編號從1開始，分別記為B1、B2、B3……的話
檢驗位：所有編號為2^n的位為檢驗位，即B1、B2、B4、B8……為檢驗位，我們把檢驗位再單獨排序稱為C1、C2、C3、C4……
則有：Ci = B(2^i-1) 數據位：存放實際的數據，除檢驗位之外依次存放，單獨編碼為D1、D2、D3、D4….. 由於是二進制，實際上這種編碼的方案在二進制下有更為顯然的規律 看表。我尤其喜歡MarkDown的語法，尤其是表格編碼位B1B2B3B4B5B6B7B8…
二進制編號00010010001101000101011001111000…
對應含義P1P2D1P3D2D3D4P4…
檢驗位P1P2
P3
P4…
數據位
D1
D2D3D4
…
很有美感的規律
檢驗位 Pi 對應的編碼位為 Bj ，則有 j 的二進制編碼有且僅有第i位為1
P1，對應2^0=1，對應B1，即“0001”僅有第1位為1 P2，對應2^1=2，對應B2，即“0010”僅有第2為為1 P3，對應2^2=4，對應B4，即“0100”僅有第3位為1 P4，對應2^3=8，對應B8，即“1000”僅有第4位為1
海明碼的編碼方法
具體的編碼方法
數據位D1、D2、D3、D4……即存放原始的數據 下面講檢驗位要如何得到：
每個檢驗位所負責的數據位
P1：B1、B3、B5、B7…… P2：B2、B3、B6、B7…… P3：B4、B5、B6、B7…… P4：B8、B9、B10、B11…… 看上面的大概是很難看出什麼規律，不過我們把 Bj 的 j 寫成二進制的話，那就有一個很美的規律了
P1：B0001、B0011、B0101、B0111…… P2：B0010、B0011、B0110、B0111…… P3：B0100、B0101、B0110、B0111…… P4：B1000、B1001、B1010、B1011…… 當當當，規律就是
Pi 所負責的所有的 Bj，其 j 的二進制編碼的第 i 位都是1 也就是對於任意一個 Bj，如果 j 的二進制編碼的第 i 位為1，則 Bj 就會由 Pi 負責。 顯然，一個 Bj 有可能會有多位為1，那麼這一位 Bj 自然也就對應著多個負責的檢驗位
對於檢驗位，由於檢驗位對應的 Bj 的 j 的二進制有且只有一位為1，所以檢驗位實際上必然只對自己負責 對於數據位，由於對應的 Bj 的 j 的二進制必然有2位以上為1(因為只有1位為1的必然是檢驗位)，所以一個數據位至少被兩個檢驗位所負責 規定好了每個檢驗位所負責的編碼位了之後，那麼檢驗位如何求呢?很簡單，那就是奇偶檢驗編碼位B1B2B3B4B5B6B7B8…
二進制編號00010010001101000101011001111000…
對應含義P1P2D1P3D2D3D4P4…
負責關系P1P1
D1
D2
D4
…
負責關系P2
P2D1
D3D4
…
負責關系P3
P3D2D3D4
…
負責關系P4
P4…
海明碼的使用方法
那麼我們如何來看待這種美感規律之下的編碼呢?即這種編碼方案下如何檢驗錯誤與糾錯呢?
我們說海明碼具有1位的檢驗與糾錯能力，和2位的檢驗能力 對於1位的出錯
若為檢驗位，則該檢驗位所對應的一個負責關系將通不過奇偶檢驗 若為數據位，則該數據位對應的多個負責關系將通不過奇偶檢驗 那麼對於所有的負責關系，我們按照其負責的檢驗位的順序來生成一個二進制數字，即如果 Pi 所在的負責關系通不過奇偶檢驗，則該生成的二進制數字的第 i 位記為1，否則記為0 神奇的事發生了。我們最後得出來的數字，剛剛好就是出錯的那一位
如果是檢驗位出錯，而我們規定檢驗位 Pi 的位置是 B(2^i-1)，即 Pi 所在的位置 Bj ，其 j 的二進制編碼有且僅有第 i 位為1，也就是說 Pi 出了錯，而 Pi 的位置剛好是“二進制編碼有且僅有第 i 位為1”的位置。對應關系豈不妙哉 如果是數據位出錯，而我們發現數據位的編碼位 Bj，其 j總是含有多個為1的位，對於每一個第 i 位為1都對應了一個 Pi，那麼在檢驗的時候，必然導致這多個負責關系 Pi 通不過奇偶檢驗，進而生成的二進制數字的編碼則如同“光路可逆”一般，正好講每一個第 i 位都設置成了1，也就剛好得出了出錯的數據位的位置。更妙更妙。 就此而言，海明碼是我所見過的對二進制規則運用最妙的結構之一。 對於2位出錯，仍按上述規則來生成最後的數字，但是此時無法判斷出是哪一位出錯，但生成是數字總不是0。
反證法。如果兩位出錯而生成的數字為0。記Bx和By出錯 1、若 Bx 為檢驗位，設 Bx 對應的檢驗位為 Pi，由於最後的數字為0，這就要求負責關系 Pi 能通過奇偶檢驗，而奇偶檢驗的最小碼距為2，Pi 本身已經出錯了，所以負責關系 Pi 中必然還有一個編碼為要出錯，而這一位只可能是數據位，即By只能為數據位。By若為數據位，則 By 必然對應兩個以上的負責關系，除了負責關系Pi 外，設第二個為負責關系 Pj，則負責關系 Pj 有且只有 By 對應的數據位出錯，所以負責關系 Pj 必然通不過奇偶檢驗，所以生成的數字必然不是0。矛盾。 2、若 Bx 和 By 均為檢驗位，由1的分析可知不可能。如果假設Bx和By均為檢驗位的話，那麼分別對應了兩個負責關系 Pi 和 Pj，則生成的數字必然不是0。 3、若 Bx 和 By 均為數據位，則 Bx 和 By 必然分別對應著兩個以上的負責關系。由於每個負責關系均為奇偶檢驗，最小碼距為2，這也就要求所有被 Bx 和 By 涉及到的負責關系都需要同時包含 Bx 和 By 才能保證通過奇偶檢驗，所以 Bx 和 By 就必然是同一個編碼位。矛盾。 對於3位以上的出錯，生成的數字就有可能是0了。這和數據無誤的最後生成的數字相同。如B3、B5和B6。也就是說我們最少需要改變三位，就可以得到另一個在海明碼規則下合法的編碼了。所以最小碼距為3。 實際使用的時候
對於常見的1位出錯，如果我們發現的是檢驗位出錯，但實際是檢驗位出錯並不會影響數據位，也就是說實際的數據無誤，則實際上並不影響數據的傳輸，可以無須糾正。 對於2位出錯，我們只能判斷“出錯了”。然而實際上我們也無法確定這究竟是一位的出錯還是兩位的出錯。
如果對精度要求不是那麼高的話，一般會默認出錯都是1位出錯，並根據是否是檢驗位來判斷是否需要糾正。 如果要求高的話，那麼“一旦出錯”，則會要求重新發送數據。 對於3位及以上的錯，部分是可以被檢驗出出錯來的，只有較少數情況下，而且這種情況發生的概率也是十分小的，才會“混過了海明碼檢驗”。
循環冗余校驗碼
CRC碼。Cyclic Redundancy Check。 數據通信領域中最常用的一種查錯校驗碼 信息字段和校驗字段的長度可以任意選定，相對於海明碼那種硬性的結構規定，因為運用了更為靈活的數學知識，所以CRC在長度方面極具靈活性 因為不在考試范圍之內，雖然我也憑著興趣研究了一番，然而在過程中極為痛苦，雖然用到了很多數學名詞，然而並沒有讓我感受到數學的美，所以也就不打算在這裡講來讓大家看得痛苦了讓我自己也難受了…… 有興趣的可以自行谷歌百度。
Internet Checksum
查詢相關內容的時候又發現的一種編碼。 不做介紹只記錄下來有這樣一種方法就成 以後如果翻到這篇筆記的話，若仍有興致，可自行谷歌百度
感覺這篇博客有點水,,,,,,不過我主要是想講海明碼，而又沒有合適的配套講的東西 之後我想整理一下編碼，如ASCII、Unicode、UFT，，，這又不只是課本上的一兩頁了。。。比較麻煩而且考試還不考，，不過個人很感興趣就是了。 之後會講內容比較多的處理器，以及指令流的概念、優化、調度算法等等，怕是超出了計算機組成原理的范圍，因為我也想講講計算機體系結構裡的內容，尤其是指令的動態調度算法。
