dou-s5計算思維之自我糾正

第五講

計算思維之自我糾正提綱數據、信息與媒體數據的檢/糾錯方法計算機處理對象數值、文字、圖像、聲音、視頻…文件、圖、表、身陣列、隊列、鏈表、棧、向量、串、實數、整數、布爾數、字符串…≠直接用硬件實現（只有幾種基本類型，其他的軟件實現=數據結構）1數據、信息與媒體數據國際標準化組織(ISO)對數據所下的定義：

數據是對事實、概念或指令的一種特殊表達形式，這種特殊的表達形式可以用人工的方式或者用自動化的裝置進行通信、翻譯轉換或者進行加工處理。計算機內部由硬件實現的基本數據：數值型數據+非數值型數據計算機中的數據表示采用二進制表示方法信息的概念信息信息是對人的行為與決策有用的數據。信息處理是計算機進行數據處理的過程，本質是數據處理目標：獲取有用的信息數據和信息的區(qū)別媒體的分類：感覺媒體：使人類聽覺、視覺、嗅覺、味覺和觸覺器官直接產生感覺的一類媒體，如聲音、文字、圖畫、氣味等。表示媒體：為了使計算機能有效加工、處理、傳輸感覺媒體而在計算機內部采用的特殊表示形式，即聲、文、圖、活動圖像的二進制編碼表示。存儲媒體（介質）：用于存放表示媒體以便計算機隨時加工處理的物理實體，如磁盤、光盤、半導體存儲器等。表現媒體：用于把感覺媒體轉換成表示媒體、表示媒體轉換為感覺媒體的物理設備，前者是計算機的輸入設備，如鍵盤、掃描儀、話筒等，后者是計算機的輸出設備，如顯示器、打印機、音箱等。傳輸媒體：用來將表示媒體從一臺計算機傳送到另一臺計算機的通信載體，如同軸電纜、光纖、電話線等媒體：承載信息的載體2數據的檢/糾錯為什么要進行數據的錯誤檢測與校正？

數據在計算機內部計算、存取和傳送的過程中，由于元器件故障或噪音干擾等原因會出現差錯。為了減少和避免這些錯誤，應該：

(1)從計算機硬件本身的可靠性入手，在電路、電源、布線等各方面采取必要的措施，提高計算機的抗干擾能力；

(2)采取相應的數據檢錯和校正措施，自動地發(fā)現并糾正錯誤。數據的檢/糾錯的基本原理如何進行錯誤檢測與校正？大多采用“冗余校驗”思想，即除原數據信息外，還增加若干位編碼，這些新增的代碼被稱為校驗位。處理過程圖示：存儲器或傳輸線路ff比較糾正器MPM’P”P’M出錯信號數據輸出數據輸入數據的檢/糾錯過程數據檢/校過程：

當數據被存入存儲器或從源部件傳輸時，對數據M進行某種運算（用函數f來表示），以產生相應的代碼P=f(M)，這里P就是校驗位。這樣原數據信息和相應的校驗位一起被存儲或傳送。當數據被讀出或傳送到終部件時，和數據信息一起被存儲或傳送的校驗位也被得到，用于檢錯和糾錯。假定讀出后的數據為M’，通過同樣的運算f對M’也得到一個新的校驗位P’=f(M’)，假定原來被存儲的校驗位P取出后其值為P’’，將校驗位P’’與新生成的校驗位P’進行某種比較，根據其比較結果確定是否發(fā)生了差錯。比較的結果為以下三種情況之一：

①沒有檢測到錯誤，得到的數據位直接傳送出去。②檢測到差錯，并可以糾錯。數據位和比較結果一起送入糾錯器，然后將產生的正確的數據位傳送出去。③

檢測到錯誤，但無法確認哪位出錯，因而不能進行糾錯處理，此時，報告出錯情況。什么叫碼距？

為了判斷一種碼制的冗余程度，并估價它的查錯和糾錯能力，引入了“碼距”的概念。由若干位代碼組成的一個字叫“碼字”，將兩個碼字逐位比較，具有不同代碼的位的個數叫做這兩個碼字間的“距離”。一種碼制可能有若干個碼字，而且，其中任意兩個碼字之間的距離可能不同，我們將各碼字間的最小距離稱為“碼距”，它就是這個碼制的距離。例如“8421”編碼中，2（0010）和3（0011）之間距離為1，所以“8421”碼制的碼距為1，記作d=1。

在數據校驗碼中，一個碼字是指數據位和校驗位按照某種規(guī)律排列得到的代碼。碼距與檢錯、糾錯能力的關系①如果碼距d為奇數，則能發(fā)現d-1位錯，或者能糾正(d-1)/2位錯。②如果碼距d為偶數，則能發(fā)現d/2位錯，并能糾正(d/2-1)位錯。常用的數據校驗碼有：

奇偶校驗碼、海明校驗碼和循環(huán)冗余校驗碼。檢錯和糾錯的基本概念2.1：奇偶校驗碼奇偶校驗碼（最簡單）

基本思想：通過在原數據信息中增加一位奇校驗位（或偶校驗位），然后將原數據和得到的校驗位一起進行存儲或傳送，對存取后或在傳送的終部件得到的相應數據和校驗位，再進行一次編碼，求出新校驗位，最后根據得到的這個新校驗位的值，確定是否發(fā)生了錯誤。

實現原理：假設將數據B=bn-1bn-2...b1b0從源部件傳送至終部件。在終部件接收到的數據為B’=bn-1’bn-2’...b1’b0’。第一步：在源部件求出奇（偶）校驗位P。

若采用奇校驗，則P=bn-1⊕bn-2⊕...⊕b1⊕b0⊕1。若采用偶校驗，則P=bn-1⊕bn-2⊕...⊕b1⊕b0。第二步：在終部件求出奇（偶）校驗位P’。

若采用奇校驗，則P’=bn-1’⊕bn-2’⊕...⊕b1’⊕b0’⊕1。若采用偶校驗，則P’=bn-1’⊕bn-2’⊕...⊕b1’⊕b0’。第三步：計算最終的校驗位P*，并根據其值判斷有無奇偶錯。

假定P在終部件接受到的值為P’’，則P*=P’⊕P”①若P*=1，則表示終部件接受的數據有奇數位錯。②若P*=0，則表示終部件接受的數據正確或有偶數個錯。奇偶校驗碼

特點：在奇偶校驗碼中，若兩個數據中有奇數位不同，則它們相應的校驗位就不同；若有偶數位不同，則雖校驗位相同，但至少有兩位數據位不同。因而任意兩個碼字之間至少有兩位不同，所以碼距d=2。因而只能發(fā)現奇數位出錯，不能發(fā)現偶數位出錯，而且也不能確定發(fā)生錯誤的位置，因而不具有糾錯能力。

優(yōu)點：開銷小，常被用于存儲器讀寫檢查或按字節(jié)傳輸過程中的數據校驗。因為一字節(jié)長的代碼發(fā)生錯誤時，1位出錯的概率較大，兩位以上出錯則很少，所以奇偶校驗碼用于校驗一字節(jié)長的代碼是有效的。2.2：海明碼海明校驗碼由RichardHamming于1950年提出，目前還被廣泛使用。它主要用于存儲器中數據存取校驗?；舅枷耄呵笆銎媾夹ｒ灤a對整個數據編碼生成一位校驗位。因此這種校驗碼檢錯能力差，并且沒有糾錯能力。如果將整個數據按某種規(guī)律分成若干組，對每組進行相應的奇偶檢測，就能提供多位檢錯信息，從而對錯誤位置進行定位，并將其糾正。海明校驗碼實質上就是一種多重奇偶校驗碼。處理過程：最終進行比較時，按位進行異或操作，根據異或操作的結果，確定是否發(fā)生了差錯。這種異或操作所得到的結果稱為故障字（syndromeword）。顯然，校驗碼和故障字的位數是相同的。海明碼１.校驗碼位數的確定假定數據位數為n，校驗碼為k位，則故障字的位數也為k位。k位故障字所能表示的狀態(tài)最多是2K，每種狀態(tài)可用來說明一種出錯情況。若只有一位錯，則結果可能是數據中某一位錯(n種)、或校驗碼中有一位錯(n種)，加上無錯，則有1+n+k種情況，所以，要能對最多一位錯的所有結果進行正確表示，則n和k必須滿足下列關系：

2K≥1+n+k，

即：2K-1≥n+k有效數據位數和校驗碼位數之間的關系從表中可以看出，當存取的有效數據有8位時，校驗碼和故障字都應有4位。4位的故障字最多可以表示16種狀態(tài)，而單個位出錯情況最多只有12種可能（8個數據位和4個校驗位），再加上無錯的情況，一共有13種。所以，用16種狀態(tài)表示13種情況應是足夠了。校驗碼的位數計算

單糾錯單糾錯/雙檢錯數據位檢查位增加百分率檢查位增加百分率8450562.516531.25637.532618.75721.87564710.94812.512886.2597.0325693.52103.912．分組方式的確定基本思想:

數據位和校驗位按某種方式排列為一個n+k的碼字，將該字中每一位的出錯位置與故障字的數值建立關系，通過故障字的值確定該碼字中哪一位發(fā)生了錯誤，并將其取反來糾正。根據上述基本思想，我們按以下規(guī)則來解釋各故障字的值。(1)如果故障字各位全部是0，則表示沒有發(fā)生錯誤。

(2)如果故障字中有且僅有一位為1，則表示校驗位中有一位出錯，不需要糾正。

(3)如果故障字中多位為1，則表示有一個數據位出錯，其在碼字中的出錯位置由故障字的數值來確定。糾正時只要將出錯位取反即可。

假定一個8位數據M=M8M7M6M5M4M3M2M1，其相應的4位校驗位為P=P4P3P2P1。根據上述規(guī)則將數據M和校驗位P按照一定的規(guī)律排到一個12位的碼字中。

據規(guī)則1，故障字為0000時，表示無錯，因此沒有和位置號0000對應的出錯情況，所以位置號從0001開始。

據規(guī)則2，故障字中有且僅有一位為1時，表示校驗位中有一位出錯，此時，故障字只可能是0001、0010、0100、1000四種情況，我們將這四種狀態(tài)分別代表校驗位中第P1、P2、P3、P4位發(fā)生錯誤的情況，因此，校驗位P1、P2、P3、P4應分別位于碼字的第1、2、4、8位。據規(guī)則3，將其他多位為1的故障字依次表示數據位M1~M8發(fā)生錯誤的情況。因此，數據位M1~M8應分別位于碼字的第0011(3)、0101(5)、0110(6)、0111(7)、1001(9)、1010(10)、1011(11)、1100(12)位。即碼字的排列為：

M8M7M6M5P4M4M3M2P3M1P2P1

這樣，得到故障字S=S4S3S2S1的各個狀態(tài)和出錯情況的對應關系表，可根據這種對應關系對整個數據進行分組。分組原則0001，0010，00110100，0101，0110，01111000，1001,1010,1011,11003校驗位的生成和檢錯、糾錯

分組完成后，就可對每組采用相應的奇（偶）校驗，以得到相應的一個校驗位。假定采用偶校驗(即取校驗位Pi，使對應組中有偶數個1)，則得到校驗位與數據位之間存在如下關系：

P1=M1⊕M2⊕M4⊕M5⊕M7

P2=M1⊕M3⊕M4⊕M6⊕M7

P3=M2⊕M3⊕M4⊕M8

P4=M5⊕M6⊕M7⊕M8根據上面的公式，可以求出每一組對應的校驗位Pi(i=1,2,3,4)。數據M和校驗位P一起被存儲。讀出后的數據M’，通過上述同樣的公式得到新的校驗位P’，然后將讀出后的校驗位P’’與新生成的校驗位P’按位進行異或操作，得到故障字S=S4S3S2S1，根據S的值可以確定沒有發(fā)生錯誤，還是僅校驗位發(fā)生錯誤，還是哪一個數據位發(fā)生了錯誤。2.3一個例子假定一個8位數據M為：M8M7M6M5M4M3M2M1=01101010，根據上述公式求出相應的校驗位為：

P1=M1⊕M2⊕M4⊕M5⊕M7=0⊕1⊕1⊕0⊕1=1

P2=M1⊕M3⊕M4⊕M6⊕M7=0⊕0⊕1⊕1⊕1=1

P3=M2⊕M3⊕M4⊕M8=1⊕0⊕1⊕0=0

P4=M5⊕M6⊕M7⊕M8=0⊕1⊕1⊕0=0假定12位碼字(M8M7M6M5P4M4M3M2P3M1P2P1)讀出后的結果是:(1)數據位M’=M=01101010，校驗位P’’=P=0011(2)數據位M’=01111010，校驗位P’’=P=0011(3)數據位M’=M=01101010，校驗位P’’=1011要求分別考察每種情況的故障字。海明碼舉例說明(1)數據位M’=M=01101010，校驗位P’’=P=0011，即：所有位都無錯。

這種情況下，因為M’=M，所以P’=P，因此,S=P’’⊕P’=P⊕P=0000。(2)數據位M’=01111010，校驗位P’’=P=0011，即：數據位第5位(M5)錯。

這種情況下，對M’生成新的校驗位P’為：

P1’=M1’⊕M2’⊕M4’⊕M5’⊕M7’=0⊕1⊕1⊕1⊕1=0 P2’

=M1’⊕M3’⊕M4’⊕M6’⊕M7’=0⊕0⊕1⊕1⊕1=1 P3’=M2’⊕M3’⊕M4’⊕M8’=1⊕0⊕1⊕0=0 P4’

=M5’⊕M6’⊕M7’⊕M8’=1⊕1⊕1⊕0=1

故障字S為