數(shù)據(jù)存儲中的錯誤檢查和糾正算法設計

1、數(shù)據(jù)存儲中的錯誤檢查和糾正算法設計,00111129,學生：鄂元哲,指導老師：羅明,一、課題背景,?,數(shù)據(jù)存儲的概念,數(shù)據(jù)存儲是數(shù)據(jù)流在加工過程中產生的臨時文件或加工過程中需要查找的信息。,數(shù)據(jù)以某種格式記錄在計算機內部或外部存儲介質上。,?,常見的存儲介質,1.,硬盤：在平整的磁性表面存儲和檢索數(shù)據(jù),2.,閃存：一般指電子式可清除程序化非易失存儲器,3.,光盤：用激光掃描的記錄和讀出方式保存信息的一種介質,二、國內外研究方向,數(shù)據(jù)存儲中的錯誤檢查與糾正算法是計算機、通信、網絡等方面的熱點技術，從,上個世紀計算機發(fā)明、無線通信應用以來，人們就一直在糾錯算法的理論和實現(xiàn),等方向進行研究工作。并且

2、還極大促進了信息論、編碼理論等相關學科的發(fā)展。,如今糾錯算法中已經有了大量的成熟高效的算法和其軟硬件實現(xiàn)方案，下面我們,將從錯誤檢查技術、糾錯技術、現(xiàn)有的部分實現(xiàn)方案等方面回顧前人的成果。同,時，通過總結現(xiàn)有方案的優(yōu)劣來確定我們的思考方向和實現(xiàn)思路。,數(shù)據(jù)存儲錯誤的特性,數(shù)據(jù)存儲與傳輸中，有時會發(fā)生隨機的寫入錯誤。,由于介質的物理特性，在數(shù)據(jù)保存過程中，由于外界環(huán)境影響，可能造成少量數(shù),據(jù)在存儲過程中發(fā)生改變。但是在正常使用時，錯誤的發(fā)生率極低，且分布隨機。,實踐中數(shù)據(jù)一般按小區(qū)塊存儲。這樣，在每個小區(qū)塊中，一般只可能發(fā)生隨機,1bit,錯誤。本課題主要研究隨機,1bit,錯誤的錯誤檢查與糾錯

3、算法實現(xiàn)。,常見的錯誤檢查方法,錯誤檢查和糾錯的原理：,數(shù)據(jù)存儲中隨機發(fā)生的錯誤就像是數(shù)字通信中遇到的隨機噪聲。根據(jù)香農定理，,只要為存儲的數(shù)據(jù)增加冗余度，數(shù)學上就存在一種編碼方式，可以無差錯地傳輸,和存儲信息。,在通信學中，這種增加冗余度來校驗和糾錯的技術叫做冗余校驗。,1.,重復碼,通過在發(fā)送時重復發(fā)送同樣的比特流來進行錯誤檢查與糾錯。,優(yōu)勢：邏輯簡單，有很好的糾錯能力,劣勢：帶寬或者存儲空間利用率極低，設想某一系統(tǒng)發(fā)送信息時重復三次比,特流，那么帶寬利用率僅,1/3,。,2.,奇偶校驗法,奇偶校驗位是一個表示給定位數(shù)的二進制數(shù)中,1,的個數(shù)是奇數(shù)還是偶數(shù)的二進,制數(shù)。奇偶校驗位有兩種類型

4、：偶校驗位與奇校驗位。如果一組給定數(shù)據(jù)位,中,1,的個數(shù)是奇數(shù)，那么偶校驗位就置為,1,，從而使得總的,1,的個數(shù)是偶數(shù)。如,果給定一組數(shù)據(jù)位中,1,的個數(shù)是偶數(shù)，那么奇校驗位就置為,1,，使得總的,1,的個,數(shù)是奇數(shù)。,優(yōu)勢：算法簡單，易于實現(xiàn),劣勢：無法指明錯誤發(fā)生的位置，也無糾錯能力。另外，若一串數(shù)據(jù)中出現(xiàn),偶數(shù)個,bit,位的錯誤，那么奇偶校驗就無法檢出。,3.,檢驗和（,checksum,）,檢驗和,(checksum),，在數(shù)據(jù)處理和數(shù)據(jù)通信領域中，用于校驗目的地一組數(shù),據(jù)項的和。它通常是以十六進制為數(shù)制表示的形式。如果校驗和的數(shù)值超過,十六進制的,FF,也就是,255.,就要求其

5、補碼作為校驗和。,4.,循環(huán)冗余檢查（,CRC,）,循環(huán)冗余檢查是一種數(shù)據(jù)傳輸檢錯功能，對數(shù)據(jù)進行多項式計算，并將得到,的結果附在幀的后面，接收設備也執(zhí)行類似的算法，以保證數(shù)據(jù)傳輸?shù)恼_,性和完整性。,5.,散列函數(shù)（,hash,函數(shù)）,傳輸或存儲信息時，同時傳輸或存儲原信息和其哈希值（算法事前約定）。,在讀取時，計算原信息的哈希值并和接收到的哈希值比較。實際上，檢驗和,法和循環(huán)冗余檢查法，甚至是奇偶校驗位法都可以視作是特殊的散列函數(shù)法，,但它們的散列沖突幾率很高。設計優(yōu)秀的散列函數(shù)可以盡可能避免散列沖突。,優(yōu)勢：散列函數(shù)類型的糾錯碼原理都利于理解，其中奇偶校驗、檢驗和與循,環(huán)冗余檢查實現(xiàn)上比

6、較方便，但是帶來了比較嚴重的散列沖突。精心設計一,個散列沖突低，散列值變化幅度大的散列函數(shù)可以幫助我們避免散列沖突導,致的誤判，但是會帶來實現(xiàn)難度的上升，并導致更多的性能開銷。,劣勢：由于散列函數(shù)一般有單向性，難以根據(jù)散列函數(shù)值計算輸入值。因此,這幾種方法一般用于錯誤檢查，難以定位錯誤具體位置。也無法用于糾錯。,關于錯誤檢測算法的總結：,常見的錯誤檢測算法主要是考慮到減少性能開銷和降低實現(xiàn)的復雜度。它們,在數(shù)據(jù)存儲的錯誤檢查上效果非常顯著。因此在生活中也有很多應用：例如，,身份證上的校驗碼、數(shù)字證書與簽名系統(tǒng)、下載時的,MD5,值等等。但是，數(shù),據(jù)存儲不僅要求能檢查出存儲的數(shù)據(jù)是否出錯，很多時

7、候，我們還希望能夠,恢復已經出錯的數(shù)據(jù)。因此，人們除了對算法的檢查性能有要求以外，還希,望算法有著定位錯誤位置、修正小錯誤的能力，這就需要我們研究糾錯算法。,常見的糾錯方法,?,重傳、重讀（后向糾錯）,通過接收方請求發(fā)送方重傳出錯的數(shù)據(jù)來恢復數(shù)據(jù)的方法叫后向糾錯。,優(yōu)勢：后向糾錯易于理解，并且當誤碼率低時開銷比較小。,劣勢：后向糾錯要求接收方與發(fā)送方可以即時通信請求重傳。對于不方便通信的場合，,或者是數(shù)據(jù)存儲這種接收方和發(fā)送方時間上分離的場合無法應用。,?,前向糾錯編碼,前向糾錯（英語：,Forward error correction,縮寫,FEC,）是一種在單向通信系,統(tǒng)中控制傳輸錯誤的技

8、術，通過連同數(shù)據(jù)發(fā)送額外的信息進行錯誤恢復，以,降低誤碼率（,bit error rate, BER,）。,優(yōu)勢：前向糾錯在信道誤碼率較小時，可以只憑收到的信息還原出原值，無,需聯(lián)系發(fā)送方，這使它能應用于數(shù)據(jù)存儲等場合。,劣勢：增大了開銷，增加系統(tǒng)實現(xiàn)的復雜度。,?,混合使用前向糾錯與后向糾錯,有的場合，發(fā)送方和接收方既便于聯(lián)系又不存在嚴格的性能與復雜度限制，,這時可以混合采用前向糾錯與后向糾錯技術，以便于利用兩種方法的優(yōu)勢。,比如在,Internet,上的數(shù)據(jù)傳輸和存儲，前向糾錯和后向糾錯就混合使用。在,TCP,等協(xié)議的作用下，錯誤的數(shù)據(jù)可以被重傳。在某些傳輸設備和應用層的,部分應用中，也存

9、在前向糾錯編碼的設計以保護數(shù)據(jù)。,三、對糾錯算法需求的分析和方案設計,糾錯算法需要滿足的要求,結合前面所了解的資料和課題的情況，我們對糾錯算法有如下要求：,1.,具有檢查出,1bit,錯誤和定位錯誤,bit,的基本功能。,2.,盡可能有一定健壯性，因為糾錯碼本身也是需要存儲的數(shù)據(jù)，需要防止,1bit,錯誤出現(xiàn)在,糾錯碼中導致無法檢查確定數(shù)據(jù)的正確性。,3.,盡可能使用數(shù)電上的常見邏輯，便利硬件實現(xiàn)。,預期成果：,我的畢設項目是一個軟硬件結合項目。在項目的進行過程中，我需要對糾錯編碼,的編解碼原理進行學習和掌握，并且根據(jù)自己的理解進行算法的設計和實現(xiàn)。因,此，我的成果將體現(xiàn)在兩個方面：,1.,利

10、用軟件對算法進行模擬仿真，驗證其可行性與性能。,2.,利用,FPGA,的設計軟件，設計仿真編解碼模塊。,檢錯糾錯流程圖：,寫入時：,開始,是,計算,ECC,校驗碼，,寫入數(shù)據(jù)流中,原始數(shù)據(jù),無誤,結束,開始,檢查與糾錯時：,提取原始信息，,重算,ECC,。,否,原始,ECC,是否等于重,算值？,計算錯誤,bit,位置，反轉,錯誤,bit,結束,檢查與定位錯誤,bit,的方案：,現(xiàn)在的存儲軟硬件實現(xiàn)上，我們很多時候使用的是二維的數(shù)據(jù)結構。因此，我們,可以想到，我們可以按二維數(shù)據(jù)的行和列分別放置和計算校驗碼，這樣根據(jù)行和,列的校驗碼的變化，就能唯一確定發(fā)生了,1bit,錯誤的錯誤位。并且這樣的設計

11、便,于理解，也容易進行軟件和硬件上的實現(xiàn)。同時，這也有助于提高算法的健壯性，,因為某一位信息位出錯必然同時引起兩方面校驗碼的改變，有利于防止校驗碼發(fā),生,1bit,錯誤時引起的麻煩。,校驗碼的計算：,計算機中使用二進制表達數(shù)據(jù)，對于二進制有種特殊算符為按位異或，它具有幾,個特殊的性質：,1.,異或運算的數(shù)學性質：可以被認為是不進位的加法。這可以保證變換前后數(shù)據(jù),的位數(shù)不變。,2.,異或運算的效果與奇偶校驗等同。（易于理解）,3.,異或是種基本數(shù)電邏輯。（易于實現(xiàn)）,ECC,編碼的實現(xiàn)方法,根據(jù)前述分析。我們有一種,ECC,的實現(xiàn)方案：,每,256,字節(jié)原始數(shù)據(jù)生成,3,字節(jié),ECC,校驗數(shù)據(jù)，

12、這三字節(jié)共,24,比特分成兩部分：,6,比特的列校驗和,16,比特的行校驗，,多余的兩個比特置,1,。,以列校驗為例子，我們可以按下述算式生成,6,位的列校驗碼。：其中（,+,）代表異或運算,P3=D7(+)D6(+)D5(+)D4,P2=D7(+)D6(+)D3(+)D2,P1=D7(+)D5(+)D3(+)D1,P3=D3(+)D2(+)D1(+)D0,P2=D5(+)D4(+)D1(+)D0,P1=D6(+)D4(+)D2(+)D0,容易看出，無論是哪一位發(fā)生錯誤，其對應的,3,個校驗位必發(fā)生改變。在此例,子中，假設,D5,發(fā)生錯誤，那么,P3,，,P2,P1,必然發(fā)生翻轉。,如何解出錯

13、誤位呢？我們通過理論分析和實際測試可以知道，若發(fā)生了單,bit,錯誤，那當我們對原,ECC,值與變化后的,ECC,值按位異或后，每一對校驗碼,（比如,P3,和,P3,）必然不相等（一個為,0,，一個為,1,）。另外，容易看出，由于,編碼時候的規(guī)律性，,5,恰好是二進制的,101,。于是我們很容易看出，我們將,P3P2P1,按順序排列成一二進制數(shù)字。并且將異或后,P3P2P1,的值帶入該數(shù)字，,得出的,101,就是出錯列的列號。行號可以以此為例加以生成。,編碼放置的位置,由前文所述的,ECC,編碼的實現(xiàn)原理可以知道，這樣編碼出的,ECC,碼可以很好地對,原始數(shù)據(jù)進行,1bit,錯誤的檢錯糾錯。而

14、且，它對糾錯碼的放置位置沒有要求，可,以進行集中化放置，便于理解，也便于管理。但是，它與我們前面提到的漢明碼,相比，對于,ECC,碼本身出現(xiàn),1bit,錯誤的健壯性變低。在這樣的,ECC,編碼實現(xiàn)中，,一旦,ECC,編碼本身出現(xiàn),1bit,錯誤，算法就會混亂。但是集中化放置可以使得我們,采取其他方式保護,ECC,碼，例如，使用我們所了解的重復碼技術。,四、項目的軟件原型實現(xiàn),對于我們的課題，由于,matlab,有很多現(xiàn)成的函數(shù)和功能可用，我們以,matlab,平臺,為例子進行編程?？紤]到編碼和解碼需要復用，并且邏輯上也是分開的步驟，我,們將其提取出來作為兩個子函數(shù)進行編寫，也便于硬件上分開實現(xiàn)

15、。,五、階段性成果展示和分析,借助教授的指導，結合教授提供的資料和我所查閱的資料，我實現(xiàn)了一個可以實,現(xiàn),256,字節(jié),ECC,校驗的,matlab,程序。該程序目前可以做到對任意,256,字節(jié)的數(shù)據(jù),進行,ECC,校驗以防止,1bit,錯誤破壞數(shù)據(jù)。其計算時需要略大于原始數(shù)據(jù)量三倍大,小的臨時空間，但保存時只比原始數(shù)據(jù)量稍大。根據(jù),matlab,的運行計時，對示例,數(shù)據(jù)可以在,0.08s,左右完成一次編碼和檢錯糾錯循環(huán)。,如圖所示，我生成了一個共,256,項，每項,8,個字節(jié)的一串數(shù)據(jù)作為原始數(shù)據(jù)，,計算出其,ECC,值，隨后把其中一項（第,19,項）原值,18,改成,50,。（即,00010010,改成,01010010,）以此模擬發(fā)生的單,bit,錯誤。