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

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

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

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

4、如果給定一組數(shù)據(jù)位中1的個數(shù)是偶數(shù)，那么奇校驗位就置為1，使得總的1的個數(shù)是奇數(shù)。優(yōu)勢：算法簡單，易于實現(xiàn)劣勢：無法指明錯誤發(fā)生的位置，也無糾錯能力。另外，若一串?dāng)?shù)據(jù)中出現(xiàn)偶數(shù)個bit位的錯誤，那么奇偶校驗就無法檢出。3.檢驗和（checksum）檢驗和(checksum)，在數(shù)據(jù)處理和數(shù)據(jù)通信領(lǐng)域中，用于校驗?zāi)康牡匾唤M數(shù)據(jù)項的和。它通常是以十六進制為數(shù)制表示的形式。如果校驗和的數(shù)值超過十六進制的FF,也就是255. 就要求其補碼作為校驗和。4.循環(huán)冗余檢查（CRC）循環(huán)冗余檢查是一種數(shù)據(jù)傳輸檢錯功能，對數(shù)據(jù)進行多項式計算，并將得到的結(jié)果附在幀的后面，接收設(shè)備也執(zhí)行類似的算法，以保證數(shù)據(jù)傳輸?shù)?/p>

5、正確性和完整性。5.散列函數(shù)（hash函數(shù)）傳輸或存儲信息時，同時傳輸或存儲原信息和其哈希值（算法事前約定）。在讀取時，計算原信息的哈希值并和接收到的哈希值比較。實際上，檢驗和法和循環(huán)冗余檢查法，甚至是奇偶校驗位法都可以視作是特殊的散列函數(shù)法，但它們的散列沖突幾率很高。設(shè)計優(yōu)秀的散列函數(shù)可以盡可能避免散列沖突。優(yōu)勢：散列函數(shù)類型的糾錯碼原理都利于理解，其中奇偶校驗、檢驗和與循環(huán)冗余檢查實現(xiàn)上比較方便，但是帶來了比較嚴(yán)重的散列沖突。精心設(shè)計一個散列沖突低，散列值變化幅度大的散列函數(shù)可以幫助我們避免散列沖突導(dǎo)致的誤判，但是會帶來實現(xiàn)難度的上升，并導(dǎo)致更多的性能開銷。劣勢：由于散列函數(shù)一般有單向性，

6、難以根據(jù)散列函數(shù)值計算輸入值。因此這幾種方法一般用于錯誤檢查，難以定位錯誤具體位置。也無法用于糾錯。關(guān)于錯誤檢測算法的總結(jié)：常見的錯誤檢測算法主要是考慮到減少性能開銷和降低實現(xiàn)的復(fù)雜度。它們在數(shù)據(jù)存儲的錯誤檢查上效果非常顯著。因此在生活中也有很多應(yīng)用：例如，身份證上的校驗碼、數(shù)字證書與簽名系統(tǒng)、下載時的MD5值等等。但是，數(shù)據(jù)存儲不僅要求能檢查出存儲的數(shù)據(jù)是否出錯，很多時候，我們還希望能夠恢復(fù)已經(jīng)出錯的數(shù)據(jù)。因此，人們除了對算法的檢查性能有要求以外，還希望算法有著定位錯誤位置、修正小錯誤的能力，這就需要我們研究糾錯算法。常見的糾錯方法重傳、重讀（后向糾錯）通過接收方請求發(fā)送方重傳出錯的數(shù)據(jù)來恢

7、復(fù)數(shù)據(jù)的方法叫后向糾錯。優(yōu)勢：后向糾錯易于理解，并且當(dāng)誤碼率低時開銷比較小。劣勢：后向糾錯要求接收方與發(fā)送方可以即時通信請求重傳。對于不方便通信的場合，或者是數(shù)據(jù)存儲這種接收方和發(fā)送方時間上分離的場合無法應(yīng)用。前向糾錯編碼前向糾錯（英語：Forward error correction,縮寫FEC）是一種在單向通信系統(tǒng)中控制傳輸錯誤的技術(shù)，通過連同數(shù)據(jù)發(fā)送額外的信息進行錯誤恢復(fù)，以降低誤碼率（bit error rate, BER）。優(yōu)勢：前向糾錯在信道誤碼率較小時，可以只憑收到的信息還原出原值，無需聯(lián)系發(fā)送方，這使它能應(yīng)用于數(shù)據(jù)存儲等場合。劣勢：增大了開銷，增加系統(tǒng)實現(xiàn)的復(fù)雜度。混合使用前向

8、糾錯與后向糾錯有的場合，發(fā)送方和接收方既便于聯(lián)系又不存在嚴(yán)格的性能與復(fù)雜度限制，這時可以混合采用前向糾錯與后向糾錯技術(shù)，以便于利用兩種方法的優(yōu)勢。比如在Internet上的數(shù)據(jù)傳輸和存儲，前向糾錯和后向糾錯就混合使用。在TCP等協(xié)議的作用下，錯誤的數(shù)據(jù)可以被重傳。在某些傳輸設(shè)備和應(yīng)用層的部分應(yīng)用中，也存在前向糾錯編碼的設(shè)計以保護數(shù)據(jù)。三、對糾錯算法需求的分析和方案設(shè)計糾錯算法需要滿足的要求結(jié)合前面所了解的資料和課題的情況，我們對糾錯算法有如下要求：1.具有檢查出1bit錯誤和定位錯誤bit的基本功能。2.盡可能有一定健壯性，因為糾錯碼本身也是需要存儲的數(shù)據(jù)，需要防止1bit錯誤出現(xiàn)在糾錯碼中導(dǎo)

9、致無法檢查確定數(shù)據(jù)的正確性。3.盡可能使用數(shù)電上的常見邏輯，便利硬件實現(xiàn)。預(yù)期成果：我的畢設(shè)項目是一個軟硬件結(jié)合項目。在項目的進行過程中，我需要對糾錯編碼的編解碼原理進行學(xué)習(xí)和掌握，并且根據(jù)自己的理解進行算法的設(shè)計和實現(xiàn)。因此，我的成果將體現(xiàn)在兩個方面：1.利用軟件對算法進行模擬仿真，驗證其可行性與性能。2.利用FPGA的設(shè)計軟件，設(shè)計仿真編解碼模塊。檢錯糾錯流程圖：寫入時： 檢查與糾錯時：開始計算ECC校驗碼，寫入數(shù)據(jù)流中結(jié)束 開始提取原始信息，重算ECC。 原始ECC是否等于重 算值？是否原始數(shù)據(jù)無誤計算錯誤bit位置，反轉(zhuǎn)錯誤bit結(jié)束檢查與定位錯誤bit的方案：現(xiàn)在的存儲軟硬件實現(xiàn)上，

10、我們很多時候使用的是二維的數(shù)據(jù)結(jié)構(gòu)。因此，我們可以想到，我們可以按二維數(shù)據(jù)的行和列分別放置和計算校驗碼，這樣根據(jù)行和列的校驗碼的變化，就能唯一確定發(fā)生了1bit錯誤的錯誤位。并且這樣的設(shè)計便于理解，也容易進行軟件和硬件上的實現(xiàn)。同時，這也有助于提高算法的健壯性，因為某一位信息位出錯必然同時引起兩方面校驗碼的改變，有利于防止校驗碼發(fā)生1bit錯誤時引起的麻煩。校驗碼的計算：計算機中使用二進制表達數(shù)據(jù)，對于二進制有種特殊算符為按位異或，它具有幾個特殊的性質(zhì)：1.異或運算的數(shù)學(xué)性質(zhì)：可以被認(rèn)為是不進位的加法。這可以保證變換前后數(shù)據(jù)的位數(shù)不變。2.異或運算的效果與奇偶校驗等同。（易于理解）3.異或是種

11、基本數(shù)電邏輯。（易于實現(xiàn)）ECC編碼的實現(xiàn)方法根據(jù)前述分析。我們有一種ECC的實現(xiàn)方案：每256字節(jié)原始數(shù)據(jù)生成3字節(jié)ECC校驗數(shù)據(jù)，這三字節(jié)共24比特分成兩部分：6比特的列校驗和16比特的行校驗，多余的兩個比特置1。以列校驗為例子，我們可以按下述算式生成6位的列校驗碼。：其中（+）代表異或運算P3=D7(+)D6(+)D5(+)D4P3=D3(+)D2(+)D1(+)D0P2=D7(+)D6(+)D3(+)D2P2=D5(+)D4(+)D1(+)D0P1=D7(+)D5(+)D3(+)D1P1=D6(+)D4(+)D2(+)D0容易看出，無論是哪一位發(fā)生錯誤，其對應(yīng)的3個校驗位必發(fā)生改變。在

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

13、且，它對糾錯碼的放置位置沒有要求，可以進行集中化放置，便于理解，也便于管理。但是，它與我們前面提到的漢明碼相比，對于ECC碼本身出現(xiàn)1bit錯誤的健壯性變低。在這樣的ECC編碼實現(xiàn)中，一旦ECC編碼本身出現(xiàn)1bit錯誤，算法就會混亂。但是集中化放置可以使得我們采取其他方式保護ECC碼，例如，使用我們所了解的重復(fù)碼技術(shù)。四、項目的軟件原型實現(xiàn)對于我們的課題，由于matlab有很多現(xiàn)成的函數(shù)和功能可用，我們以matlab平臺為例子進行編程?？紤]到編碼和解碼需要復(fù)用，并且邏輯上也是分開的步驟，我們將其提取出來作為兩個子函數(shù)進行編寫，也便于硬件上分開實現(xiàn)。五、階段性成果展示和分析借助教授的指導(dǎo)，結(jié)合教授提供的資料和我所查閱的資料，我實現(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é)的一串?dāng)?shù)據(jù)作為原始數(shù)據(jù)，計算出其ECC值，隨后把其中一項（第19項）原值18改成50。（即00010010改成01010010）以此模擬發(fā)生的單bit錯誤。結(jié)果