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

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

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

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

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

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

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

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

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

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

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

11、基本數(shù)電邏輯。（易于實(shí)現(xiàn)）ECC編碼的實(shí)現(xiàn)方法根據(jù)前述分析。我們有一種ECC的實(shí)現(xiàn)方案：每256字節(jié)原始數(shù)據(jù)生成3字節(jié)ECC校驗(yàn)數(shù)據(jù)，這三字節(jié)共24比特分成兩部分：6比特的列校驗(yàn)和16比特的行校驗(yàn)，多余的兩個(gè)比特置1。以列校驗(yàn)為例子，我們可以按下述算式生成6位的列校驗(yàn)碼。：其中（+）代表異或運(yùn)算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ā)生錯(cuò)誤，其對(duì)應(yīng)的3個(gè)校驗(yàn)位必發(fā)生改變。在

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

13、且，它對(duì)糾錯(cuò)碼的放置位置沒有要求，可以進(jìn)行集中化放置，便于理解，也便于管理。但是，它與我們前面提到的漢明碼相比，對(duì)于ECC碼本身出現(xiàn)1bit錯(cuò)誤的健壯性變低。在這樣的ECC編碼實(shí)現(xiàn)中，一旦ECC編碼本身出現(xiàn)1bit錯(cuò)誤，算法就會(huì)混亂。但是集中化放置可以使得我們采取其他方式保護(hù)ECC碼，例如，使用我們所了解的重復(fù)碼技術(shù)。四、項(xiàng)目的軟件原型實(shí)現(xiàn)對(duì)于我們的課題，由于matlab有很多現(xiàn)成的函數(shù)和功能可用，我們以matlab平臺(tái)為例子進(jìn)行編程?？紤]到編碼和解碼需要復(fù)用，并且邏輯上也是分開的步驟，我們將其提取出來作為兩個(gè)子函數(shù)進(jìn)行編寫，也便于硬件上分開實(shí)現(xiàn)。五、階段性成果展示和分析借助教授的指導(dǎo)，結(jié)合教授提供的資料和我所查閱的資料，我實(shí)現(xiàn)了一個(gè)可以實(shí)現(xiàn)256字節(jié)ECC校驗(yàn)的matlab程序。該程序目前可以做到對(duì)任意256字節(jié)的數(shù)據(jù)進(jìn)行ECC校驗(yàn)以防止1bit錯(cuò)誤破壞數(shù)據(jù)。其計(jì)算時(shí)需要略大于原始數(shù)據(jù)量三倍大小的臨時(shí)空間，但保存時(shí)只比原始數(shù)據(jù)量稍大。根據(jù)matlab的運(yùn)行計(jì)時(shí)，對(duì)示例數(shù)據(jù)可以在0.08s左右完成一次編碼和檢錯(cuò)糾錯(cuò)循環(huán)。如圖所示，我生成了一個(gè)共256項(xiàng)，每項(xiàng)8個(gè)字節(jié)的一串?dāng)?shù)據(jù)作為原始數(shù)據(jù)，計(jì)算出其ECC值，隨后把其中一項(xiàng)（第19項(xiàng)）原值18改成50。（即00010010改成01010010）以此模擬發(fā)生的單bit錯(cuò)誤。結(jié)果