dou-s5計(jì)算思維之自我糾正

第五講

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

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

數(shù)據(jù)在計(jì)算機(jī)內(nèi)部計(jì)算、存取和傳送的過程中，由于元器件故障或噪音干擾等原因會(huì)出現(xiàn)差錯(cuò)。為了減少和避免這些錯(cuò)誤，應(yīng)該：

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

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

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

①?zèng)]有檢測(cè)到錯(cuò)誤，得到的數(shù)據(jù)位直接傳送出去。②檢測(cè)到差錯(cuò)，并可以糾錯(cuò)。數(shù)據(jù)位和比較結(jié)果一起送入糾錯(cuò)器，然后將產(chǎn)生的正確的數(shù)據(jù)位傳送出去。③

檢測(cè)到錯(cuò)誤，但無法確認(rèn)哪位出錯(cuò)，因而不能進(jìn)行糾錯(cuò)處理，此時(shí)，報(bào)告出錯(cuò)情況。什么叫碼距？

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

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

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

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

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

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

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

假定P在終部件接受到的值為P’’，則P*=P’⊕P”①若P*=1，則表示終部件接受的數(shù)據(jù)有奇數(shù)位錯(cuò)。②若P*=0，則表示終部件接受的數(shù)據(jù)正確或有偶數(shù)個(gè)錯(cuò)。奇偶校驗(yàn)碼

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

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

2K≥1+n+k，

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

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

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

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

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

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

據(jù)規(guī)則1，故障字為0000時(shí)，表示無錯(cuò)，因此沒有和位置號(hào)0000對(duì)應(yīng)的出錯(cuò)情況，所以位置號(hào)從0001開始。

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

M8M7M6M5P4M4M3M2P3M1P2P1

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

分組完成后，就可對(duì)每組采用相應(yīng)的奇（偶）校驗(yàn)，以得到相應(yīng)的一個(gè)校驗(yàn)位。假定采用偶校驗(yàn)(即取校驗(yàn)位Pi，使對(duì)應(yīng)組中有偶數(shù)個(gè)1)，則得到校驗(yàn)位與數(shù)據(jù)位之間存在如下關(guān)系：

P1=M1⊕M2⊕M4⊕M5⊕M7

P2=M1⊕M3⊕M4⊕M6⊕M7

P3=M2⊕M3⊕M4⊕M8

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

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)讀出后的結(jié)果是:(1)數(shù)據(jù)位M’=M=01101010，校驗(yàn)位P’’=P=0011(2)數(shù)據(jù)位M’=01111010，校驗(yàn)位P’’=P=0011(3)數(shù)據(jù)位M’=M=01101010，校驗(yàn)位P’’=1011要求分別考察每種情況的故障字。海明碼舉例說明(1)數(shù)據(jù)位M’=M=01101010，校驗(yàn)位P’’=P=0011，即：所有位都無錯(cuò)。

這種情況下，因?yàn)镸’=M，所以P’=P，因此,S=P’’⊕P’=P⊕P=0000。(2)數(shù)據(jù)位M’=01111010，校驗(yàn)位P’’=P=0011，即：數(shù)據(jù)位第5位(M5)錯(cuò)。

這種情況下，對(duì)M’生成新的校驗(yàn)位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為