（計算機(jī)軟件與理論專業(yè)論文）erasurecode在網(wǎng)絡(luò)存儲系統(tǒng)中的研究與實現(xiàn).pdf

哈爾濱工程大學(xué)碩士學(xué)位論文 摘要 隨著電子商務(wù)時代的到來，存儲信息成爆炸性增長。企業(yè)信息數(shù)據(jù)的安 全、可靠存儲問題是存儲系統(tǒng)穩(wěn)定運(yùn)行的關(guān)鍵所在，也是數(shù)字化信息存儲發(fā) 展所要解決的首要問題。網(wǎng)絡(luò)存儲因為其具有結(jié)構(gòu)靈活、性能較好、可擴(kuò)展 性強(qiáng)等優(yōu)勢，在存儲舞臺上所發(fā)揮的作用日益增大。但是人為的錯誤操作、 數(shù)據(jù)服務(wù)器受病毒的侵害，物理存儲介質(zhì)的意外損壞等原因，經(jīng)常使存儲的 信息丟失，造成巨大的經(jīng)濟(jì)損失，所以存儲信息的安全性、完整性成為網(wǎng)絡(luò) 存儲領(lǐng)域的研究重點。 e r a s u r e c o d e 是數(shù)字通信領(lǐng)域用于糾正數(shù)據(jù)傳輸過程中所發(fā)生錯誤的代 數(shù)編碼理論。本文首先闡述了e r a s u r e c o d e 的基本理論，并重點介紹了一種 具有糾錯能力的e r a s u r e c o d e r e e d s o l o m o n 碼。在詳細(xì)分析了其編碼算 法與譯碼算法的基礎(chǔ)上，將r e e d s o l o m o n 碼的糾錯能力與局域網(wǎng)絡(luò)存儲技術(shù) 相結(jié)合，設(shè)計出允許多個存儲數(shù)據(jù)服務(wù)器失效的局域網(wǎng)絡(luò)存儲系統(tǒng)。并針對 譯碼算法運(yùn)行時間較長的缺陷提出了改進(jìn)方案。由于在此局域網(wǎng)絡(luò)存儲系統(tǒng) 中，r e e d s o l o m o n 碼算法使用頻率較高，并且始終保持不變，所以本文采用 f p g a 技術(shù)設(shè)計了r e e d s o l o m o n 編譯碼器，使之硬件化，從而提高了運(yùn)行速 度。 關(guān)鍵詞：網(wǎng)絡(luò)存儲；e r a s u r e c o d e ；r e e d s o l o m o n 碼；f p g a 設(shè)計 哈爾濱工程大學(xué)碩士學(xué)位論文 i i ；魯i i i 暑每i i i ；宣；葺暑i i 暑i ；i i ；i ；i i i ；i | i ii 墨 a b s t r a c t 、礬t ht h ea r r i v a lo ft h ee r ao fe - c o m m e r c e ，t h es t o r a g ei n f o r m a t i o nh a s i n c r e a s e de x p l o a i v e l y t h es e c u r i t ya n dr e l i a b i l i t yo fe n t e r p r i s ei n f o r m a t i o n s t o r a g en o to n l yi st h ek e yt os t a b i l i t yo fs t o r a g es y s t e m ，b u ti ti sa l s oa l li s s u eo f p a r a m o u n ti m p o r t a n c et ot h ed e v e l o p m e n to fd i g i t a li n f o r m a t i o ns t o r a g e b e c a u s e o ft h ef l e x i b l es t r u c t u r e ，s u p e r i o rp e r f o r m a n c ea n dg o o de x p a n d a b i l i t y , n e t w o r k s t o r a g e i s p l a y i n ga l li n c r e a s i n g l yi m p o r t a n tr o l e i nt h ef i e l do fi n f o r m a t i o n s t o r a g e h o w e v e r ，t h em a i l m a d em i s o p e r a t i o n ，t h ev i r u s i n v a d e dd a t as e r v e ra n d t h ea c c i d e n t a l l yd a m a g e dp h y s i c a l s t o r a g em e d i u mo f t e nm a k et h es t o r a g e i n f o r m a t i o nl o s ea n dc a u s eh u g ee c o n o m i cl o s s e s t h e r e f o r e ，t h es e c u r i t ya n dt h e i n t e g r i t yo fs t o r a g ei n f o r m a t i o nh a sb e c o m ea r e s e a r c hh o t s p o ti nt h ef i e l do f n e t w o r ks t o r a g e 。 e r a s u r e c o d ei sak i n do fa l g e b r a i cc o d i n gt h e o r yi nt h ef i e l do fd i g i t a l c o m m u n i c a t i o n , w h i c hi su s e dt oc o r r e c tt h ee r r o r si np r o c e s so f d a t at r a n s m i s s i o n t h et h e s i si se l a b o r a t e dt h ef u n d a m e n t a lt h e o r yo fe r a s u r e c o d e ，e s p e c i a l l ys t a t e d r e e d s o l o m o nc o d ew h i c hi sak i n d o fe r a s u r e c o d e 、i t l le r r o rc o r r e c t i n g c a p a b i l i t i e s b a s e d o nt h e a n a l y z e o fr e e d s o l o m o nc o d i n ga n dd e c o d i n g a l g o r i t h m ，t h et h e s i si sd e s i g n e da l o c a la r e an e t w o r ks y s t e mu s i n gr e e d s o l o m o n c o d ea n dl a ns t o r a g et e c h n o l o g i e s t h es y s t e mc a nr u ns m o o t h l yw h e nm u l t i d a t as t o r a g es e r v e rf a i l u r ea to n et i m e i na d d i t i o n ，i no r d e rt oo v e r c o m et h el o n g r u n n i n gt i m eo fd e c o d i n ga l g o r i t h m ，a i li m p r o v e dp r o g r a mi sp r o p o s e d i nr e s p e c t t h a tt h er e e d s o l o m o nc o d ea l g o r i t h mi su s e df r e q u e n t l ya n dr e m a i n su n c h a n g e d i nt h el o c a la r e an e t w o r ks y s t e m ，r e e d s o l o m o nc o d i n ga l g o r i t h mi si m p l e m e n t e d u s i n gf p g at e c h n o l o g ya n ds o l i d i f i e di nh a r d w a r e ，w h i c hi m p r o v e st h er u n n i n g s p e e do ft h ea l g o r i t h mg r e a t l y k e y w o r d s ：n e t w o r ks t o r a g e ；e r a s u r e - c o d e ；r e e d - s o l o m o nc o d e ；f p g a 哈爾濱工程大學(xué) 學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：本論文的所有工作，是在導(dǎo)師的指導(dǎo) 下，由作者本人獨立完成的。有關(guān)觀點、方法、數(shù)據(jù)和文 獻(xiàn)的引用己在文中指出，并與參考文獻(xiàn)相對應(yīng)。除文中己 注明引用的內(nèi)容外，本論文不包含任何其他個人或集體已 經(jīng)公開發(fā)表的作品成果。對本文的研究做出重要貢獻(xiàn)的個 人和集體，均已在文中以明確方式標(biāo)明。本人完全意識到 本聲明的法律結(jié)果由本人承擔(dān)。 作者( 簽字) ：圭氬 一，：7 日期：) p 口綽弓月i 多e t 哈爾濱工程大學(xué)碩士學(xué)位論文 1 1 研究背景和意義 第1 章緒論 隨著計算機(jī)和網(wǎng)絡(luò)技術(shù)的發(fā)展，社會信息化程度不斷提高，按照m o o r e s l a w ，計算機(jī)的性能每1 8 個月增長一倍，各種數(shù)據(jù)信息，包含各種空間數(shù)據(jù)、 報表統(tǒng)計數(shù)據(jù)、文字、聲音、圖像、超文本等，以難以置信的速度急劇增加。 一方面，在網(wǎng)上流動的數(shù)據(jù)量以前所未有的速度增加，包括來自分布式數(shù)據(jù) 庫、文件服務(wù)器、w e b 服務(wù)器等網(wǎng)上數(shù)據(jù)源，尤以i n t e r n e t 文件的數(shù)據(jù)量最 大，基于數(shù)據(jù)安全和使用方便的目的，人們通常對這些數(shù)據(jù)一再進(jìn)行備份， 因而耗費(fèi)的存儲空間也非常之多。另一方面，科學(xué)計算和仿真，飛行動力學(xué)、 核爆炸仿真、虛擬現(xiàn)實以及醫(yī)療影像數(shù)據(jù)等，所需的存儲容量更是大到驚人 的程度。人們對存儲產(chǎn)品及服務(wù)的迫切需求無疑對服務(wù)質(zhì)量和存儲系統(tǒng)性能 提出了更高的要求，這也就推動了各種存儲技術(shù)和存儲結(jié)構(gòu)的飛速發(fā)展。 信息的存儲技術(shù)和計算機(jī)網(wǎng)絡(luò)技術(shù)的結(jié)合越來越緊密，使互聯(lián)網(wǎng)中出現(xiàn) 了網(wǎng)絡(luò)存儲技術(shù)。有了這種網(wǎng)絡(luò)存儲技術(shù)以后，可以把用戶的文件保存在互 聯(lián)網(wǎng)上，并且存儲容量不受限制，文件訪問方便、快捷，文件共享高效、智 能，文件存儲可靠、安全。它的這些優(yōu)越的性能使其自發(fā)布之日起便受到市 場的關(guān)注與青睞。人們對存儲產(chǎn)品及服務(wù)的迫切需求，無疑對服務(wù)質(zhì)量和存 儲系統(tǒng)性能提出了更高的要求。美國9 1 1 事件警示了世界的同時，也警示了 信息存儲界，從中汲取了不少重要的教訓(xùn)和經(jīng)驗。數(shù)據(jù)信息能安全可靠的使 用和迅速的恢復(fù)，是亟待解決的關(guān)鍵技術(shù)，成為當(dāng)下存儲界研究的熱點問題。 目前，在數(shù)據(jù)的容錯恢復(fù)方面，網(wǎng)絡(luò)存儲系統(tǒng)，為了取得較高的數(shù)據(jù)持 續(xù)性和可靠性，通常使用兩種冗余容錯方法，它們是完全的數(shù)據(jù)復(fù)制和磁盤 冗余陣列( r e d u n d a n ta r r a yo fi n d e p e n d e n td i s k s ，r a i d ) 技術(shù)。 完全復(fù)制就是通過將文件的多個副本分別存儲在系統(tǒng)中的不同節(jié)點，實 現(xiàn)冗余容錯，只要這些節(jié)點中有一個可以被訪問，就可以取得文件數(shù)據(jù)。文 件副本越多，數(shù)據(jù)的可用性越好，可靠性越高。完全復(fù)制的方法不涉及編碼 運(yùn)算，文件的創(chuàng)建和讀取不需要編譯碼操作。但是完全復(fù)制方法數(shù)據(jù)冗余度 哈爾濱工程大學(xué)碩士學(xué)位論文 較大，要想提高文件的容錯性能，只能通過增加文件副本的數(shù)據(jù)來實現(xiàn)。完 全復(fù)制也會帶來相當(dāng)高的帶寬和存儲空間，很難滿足網(wǎng)絡(luò)存儲系統(tǒng)的容錯性 能的要求。 r a i d 技術(shù)其原理是通過資源冗余來提供服務(wù)質(zhì)量，它將多個獨立的磁 盤組織成一個邏輯盤，提供更大的存儲容量，通過保存冗余的數(shù)據(jù)、校驗信 息來提高存儲系統(tǒng)的可靠性。應(yīng)用最廣泛的是r a i d 5 技術(shù)，但r a i d 5 技術(shù) 使用簡單的奇偶檢驗碼技術(shù)來保障數(shù)據(jù)的可靠性，至多只能容許一個磁盤出 現(xiàn)故障，并需要知道是哪個盤才能恢復(fù)，若兩塊及兩塊以上盤出錯就會面臨 存儲系統(tǒng)癱瘓的局面。當(dāng)系統(tǒng)規(guī)模較大時，同時發(fā)生多個磁盤失效的概率比 較高，存儲系統(tǒng)的可靠性迅速降低。在容錯恢復(fù)機(jī)制中，只能恢復(fù)一個已知 錯，不能滿足存儲信息高安全性、高可靠性系統(tǒng)的需要。近年來，許多研究 者開始探討將e r a s u r e c o d e 編碼技術(shù)作為網(wǎng)絡(luò)存儲系統(tǒng)中的一種冗余機(jī)制來 提高數(shù)據(jù)的可靠性。將e r a s u r e c o d e 原理應(yīng)用于網(wǎng)絡(luò)存儲系統(tǒng)，利用其強(qiáng)大 的糾錯能力，可實現(xiàn)多盤容錯并恢復(fù)，有效增加容錯能力。因此，如何運(yùn)用 e r a s u r e c o d e 在網(wǎng)絡(luò)存儲系統(tǒng)中，以及其設(shè)計構(gòu)架和策略的分析是很值得研 究的。 1 2 網(wǎng)絡(luò)存儲備份技術(shù)概況 隨著信息化建設(shè)的不斷深入，尤其是因特網(wǎng)和電子商務(wù)的發(fā)展使計算機(jī) 用戶的信息容量迅猛增長，需要保存的重要數(shù)據(jù)總量和增量非常大，制定有 效的存儲備份策略是各種計算機(jī)行業(yè)面臨的重大問題，也是網(wǎng)絡(luò)存儲技術(shù)所 要解決的一個重大課題。 現(xiàn)今，主要的網(wǎng)絡(luò)儲存有三種形式：直接網(wǎng)絡(luò)存儲( d i r e c ta t t a c h e d s t o r a g e ，d a s ) 、網(wǎng)絡(luò)附加存儲( n e ta t t a c h e ds t o r a g e ，n a s ) 以及存儲區(qū) 域網(wǎng)絡(luò)口1 ( s t o r a g ea r e an e t w o r k ，s a n ) 。 在網(wǎng)絡(luò)存儲備份h 1 方面，按技術(shù)分類，主要分為各份軟件技術(shù)和備份硬 件技術(shù)。備份軟件技術(shù)可分為通用備份軟件技術(shù)( 由操作系統(tǒng)所提供的各份 功能) 和專用的備份軟件技術(shù)。為了提高存儲備份效率，大型企業(yè)通常選擇 那些專業(yè)的備份軟件，如e m c 公司的s y m m e t r i x 技術(shù)和h p 公司的o m n i b a c k 技術(shù)。 2 哈爾濱工程大學(xué)碩士學(xué)位論文 備份硬件技術(shù)主要是指磁盤陣列、磁帶機(jī)與磁帶庫等硬件備份。企業(yè)通 ?？紤]到存儲設(shè)備的容量和成本造價來進(jìn)行選擇硬件存儲備份設(shè)備。其中的 r a i d 是一種高效、快速的被廣泛應(yīng)用在網(wǎng)絡(luò)系統(tǒng)中海量數(shù)據(jù)即時存取的網(wǎng) 絡(luò)存儲備份設(shè)備。這些數(shù)據(jù)備份技術(shù)，多是針對于大型企業(yè)，成本費(fèi)用比較 昂貴，小型企業(yè)很難支付得起這種巨大投資，所以研發(fā)低附加成本的、面向 小型企業(yè)的局域網(wǎng)絡(luò)存儲備份系統(tǒng)是很有應(yīng)用價值的。 1 3 國內(nèi)外研究現(xiàn)狀和發(fā)展趨勢 在國內(nèi)，網(wǎng)絡(luò)存儲的備份方面，已經(jīng)有幾家研究機(jī)構(gòu)取得了一定的進(jìn)展。 清華大學(xué)高性能計算技術(shù)研究所網(wǎng)絡(luò)存儲實驗室是國內(nèi)較早開展海量信 息存儲技術(shù)研究的課題組。該研究所的研究內(nèi)容主要包括：海量信息的多層 存儲體系結(jié)構(gòu)、海量信息的快速i o 技術(shù)、存儲容災(zāi)技術(shù)、存儲智能管理技術(shù)、 存儲高可用技術(shù)、存儲安全技術(shù)、分布式信息服務(wù)技術(shù)、面向互聯(lián)網(wǎng)服務(wù)的 海量信息存儲技術(shù)等。 華中科技大學(xué)正在進(jìn)行網(wǎng)絡(luò)存儲系統(tǒng)中虛擬化存儲技術(shù)的研究。通過虛 擬化網(wǎng)絡(luò)磁盤陣列，將分布在網(wǎng)絡(luò)中的空閑資源收集起來構(gòu)建公共存儲池， 實現(xiàn)基本的j b o d 4 5 以及0 級和l 級磁盤陣列。同時還在研究如何構(gòu)建和管理公 共存儲池以及如何定制底層通信協(xié)議。j b o d 技術(shù)支持熱插拔磁盤驅(qū)動器，即 可以在不影響數(shù)據(jù)存儲和服務(wù)器操作的同時增加或者替換磁盤，擁有一定的 容錯能力。 目前國際上i b m 、惠普及i n t e l 等公司都是采用r a i d 技術(shù)實現(xiàn)數(shù)據(jù)的容 錯恢復(fù)的。r a i d 技術(shù)是為了防止存儲系統(tǒng)因為磁盤故障而丟失數(shù)據(jù)而研發(fā)出 來的。r a i d 是一種把多個獨立的硬盤( 物理硬盤) 按不同方式組合起來形成一 個硬盤組( 邏輯硬盤) 從而提供了比一個硬盤更高的存儲性能并提供數(shù)據(jù)的冗 余技術(shù)。r a i d 是利用冗余信息解決恢復(fù)損壞的數(shù)據(jù)。r a i d 中的磁盤陣列可 以保證其中的任何一個磁盤出現(xiàn)了故障都不會導(dǎo)致用戶數(shù)據(jù)的丟失和中斷。 快照是當(dāng)今流行的另一種數(shù)據(jù)恢復(fù)技術(shù)。s n i a ( 存儲網(wǎng)絡(luò)行業(yè)協(xié)會) 對 快照( s n a p s h o t ) 的定義是：關(guān)于指定數(shù)據(jù)集合的一個完全可用拷貝，該拷 貝包括相應(yīng)數(shù)據(jù)在某個時間點( 拷貝開始的時間點) 的映像?？煺湛梢允瞧?哈爾濱工程大學(xué)碩士學(xué)位論文 昌-i ii ii 一一 t 葺葺宣葺i 肓 所表示的數(shù)據(jù)的一個復(fù)制品。與r a i d 技術(shù)相比，快照具有備份和恢復(fù)窗口短、 性能損失小、容量利用率高等優(yōu)點，更適合保護(hù)因人為失誤等軟故障造成的 數(shù)據(jù)損失。它可以高效地管理一個數(shù)據(jù)源的多個存儲快照，并提供快照的讀 寫、，創(chuàng)建、回收等功能。另外針對快照技術(shù)物理容錯性差的缺點，通常把快 照技術(shù)與鏡像技術(shù)相結(jié)合起來，這樣較好地解決了存儲網(wǎng)絡(luò)軟、硬故障時數(shù) 據(jù)的保護(hù)。 e r a s u r e c o d e 編碼技術(shù)呻1 主要應(yīng)用在數(shù)字通信系統(tǒng)中，應(yīng)用于傳輸信道 或其他噪聲的存在引起的數(shù)據(jù)傳輸及交換過程產(chǎn)生的錯誤，尤其是遠(yuǎn)程、高 速傳輸，它可以有效地避免隨機(jī)錯和突發(fā)錯。研究分析表明，這種糾錯能力 也適用于存儲系統(tǒng)中，美國加州b e r k e l e y 大學(xué)研發(fā)的o c e a n s t o r e 系統(tǒng)口1 ，是 正在研發(fā)的面向整個互聯(lián)網(wǎng)的網(wǎng)絡(luò)存儲系統(tǒng)，在該系統(tǒng)中就是采用 e r a s u r e c o d e 編碼技術(shù)實現(xiàn)存儲數(shù)據(jù)的容錯與恢復(fù)。 1 4 主要內(nèi)容和章節(jié)安排 本文根據(jù)相關(guān)網(wǎng)絡(luò)存儲中數(shù)據(jù)容錯恢復(fù)的發(fā)展趨勢，詳細(xì)設(shè)計了一種簡 單且無附加成本的局域網(wǎng)存儲數(shù)據(jù)恢復(fù)系統(tǒng)。本文所選取的r e e d s o l o m o n 編譯碼是e r a s u r e c o d e 中的一種b c h 循環(huán)碼，其編譯碼算法較易于實現(xiàn)，并 且已經(jīng)在數(shù)據(jù)通訊領(lǐng)域的數(shù)據(jù)傳輸糾錯中得到了廣泛的應(yīng)用，體現(xiàn)了其巨大 的使用價值。本文在數(shù)據(jù)存儲系統(tǒng)中利用r e e d s o l o m o n 編譯碼簡單易行的糾 錯能力，來實現(xiàn)存儲信息的容錯恢復(fù)能力，通過對r e e d s o l o m o n 編譯碼機(jī)制 的數(shù)學(xué)原理研究，重點分析了它在網(wǎng)絡(luò)存儲中的應(yīng)用，設(shè)計出一個基于該編 譯碼算法局域網(wǎng)絡(luò)存儲容錯恢復(fù)系統(tǒng)，并利用f p g a 技術(shù)實現(xiàn)了該編譯碼算 法的硬件設(shè)計。 論文共分五章，組織結(jié)構(gòu)如下： 第l 章緒論。簡單介紹了本論文的背景、意義以及與網(wǎng)絡(luò)存儲技術(shù)和網(wǎng) 絡(luò)存儲備份相關(guān)的國內(nèi)外研究現(xiàn)狀和發(fā)展趨勢。 第2 章e r a s u r e - c o d e 基本理論。介紹了e r a s u r e - c o d e 基本原理。首先介 紹了e r a s u r e c o d e 的相關(guān)知識，然后著重介紹了r e e d s o l o m o n 編譯碼理論。 4 哈爾濱工程大學(xué)碩士學(xué)位論文 第3 章局域網(wǎng)絡(luò)存儲系統(tǒng)中r s 碼軟件實現(xiàn)。運(yùn)用r e e d s o l o m o n 編譯碼 原理進(jìn)行設(shè)計局域網(wǎng)絡(luò)存儲系統(tǒng)，并對譯碼算法進(jìn)行了改進(jìn)。 第4 章r s 編譯碼的f p g a 設(shè)計與實現(xiàn)。介紹了r e e d s o l o m o n 編譯碼算 法的硬件設(shè)計與實現(xiàn)。 第5 章基于r s 編譯碼的局域網(wǎng)絡(luò)存儲系統(tǒng)性能分析。首先對基于 r e e d s o l o m o n 編譯碼的局域網(wǎng)絡(luò)存儲系統(tǒng)可靠性與r a i d 5 系統(tǒng)的可靠性進(jìn)行 了對比分析，然后驗證了改進(jìn)的譯碼算法的優(yōu)越性，最后進(jìn)行了r s 碼算法軟 件與硬件的對比分析。 結(jié)論部分作為全文的總結(jié)，概括了論文的設(shè)計思想和主要貢獻(xiàn)，并給出 了后續(xù)工作的展望。 5 哈爾濱工程大學(xué)碩士學(xué)位論文 第2 章e r a s u r e c o d e 基本理論 e r a s u r e c o d e 是本文設(shè)計和實現(xiàn)高可靠網(wǎng)絡(luò)存儲系統(tǒng)的基礎(chǔ)，因此，本 章主要對于e r a s u r e c o d e 的基礎(chǔ)理論加以介紹。 2 1e r a s u r e - c o d e 概述 e r a s u r e c o d e 原來是無線通信中有噪信道編碼的一種，也叫糾刪碼。后 來由k a m i n 提出的密鑰共享n 町以及m 0 r a b i n 提出i d a 主要( i n f o r m a t i o n d i s p e r s a la l g o r i t h m ) 算法，將其引入到計算機(jī)應(yīng)用中，發(fā)展到現(xiàn)在，已有數(shù) 十種編碼，主要包括r e e d s o l o m o n 碼和t o r n a d o 碼，最常用的是 r e e d s o l o m o n 碼，這兩種編譯碼的主要區(qū)別是r e e d s o l o m o n 碼適合于編碼 參數(shù)較小的情況下編譯碼性能較好。本文主要針對的是局域網(wǎng)絡(luò)存儲，考慮 其編碼參數(shù)較小，故主要研究r e e d s o l o m o n 碼。 2 2 有限域基本概念 有限域n l 垤1 是1 8 3 2 年g a l o i s 弓i 進(jìn)的，g a l o i s 為了探討一元高次方程能否用 四則運(yùn)算和開方求解，創(chuàng)造了著名的g a l o i s 理論，在這一理論中他引進(jìn)了群 和域這兩個概念，人們也因此把有限域稱為g a l o i s 域。由于有限域運(yùn)算的無 進(jìn)位、固定字長等特性，因而在信息學(xué)領(lǐng)域得到了廣泛的應(yīng)用，在現(xiàn)代編碼 理論中占有重要的地位。 域是編碼理論中一個重要的概念，它是具有兩種運(yùn)算的代數(shù)系統(tǒng)。 定義2 1 對于非空元素集合f ，若在f 中定義了在其上的二元代數(shù)運(yùn)算 加和乘，若滿足下述公理： 1 ) f 關(guān)于加法構(gòu)成阿貝爾群，其加法的恒等元記為0 ( 又叫零元) ； 2 ) f 非o 元素的全體在乘法運(yùn)算下構(gòu)成阿貝爾群，其恒等元( 單位元) 記為l ； 3 ) 加法運(yùn)算和乘法運(yùn)算之間滿足如下分配率： a ( b + c ) = a b + a c 6 哈爾濱工程大學(xué)碩士學(xué)位論文 和 ( b + c ) 口= b a + 則稱f 為一個域( f i e l d ) 。 其中，包含有限個元素的域就是有限域或叫作( g a l o i s ) 域，元素的個 數(shù)稱為域的階。元素個數(shù)為q 階有限域用g f ( q ) 表示。如果q 為一個素數(shù)， 則集合 o ，1 ，2 ，q 一1 ) 在模加法和乘法下，構(gòu)成一個q 階有限域g f ( q ) 。有 限域在編碼理論中具有重要的地位，下面給出g a l o i s 域的幾個基本概念和重 要結(jié)論n 3 。 定義2 2 以q 為特征的域是g f ( q ) ，m = 1 ，2 ，稱g f ( q ) 是g f ( q ”) 的 基域，g f ( q ”) 為g f ( q ) 的擴(kuò)域。 域中一切非零元素的特征都等于域的特征，且域的特征一定為素數(shù)。非 零元素構(gòu)成的乘法群的階定義為域中該元素的級。若a 為域g f ( q ) 中的1 1 級 元素，則稱口為n 次單位原根。若某一元素口的級為q 1 ，則稱口為本原域 元素。域的特征表明了域中加法運(yùn)算的循環(huán)性，而域的級則表明了域中乘法 運(yùn)算的循環(huán)性。 有限域g f ( q ) 中的q 一1 個非零元素構(gòu)成一個循環(huán)群，它其中至少有一個 本原元，它的其它元素分別為這個本原元的j 次冪構(gòu)成，j = 0 ，1 一，q - 2 。 每一個非0 元素都滿足等式：x p l 一l = 0 。在特征為q 的域中，恒有 o 一口) = 妒一口一，式中，口是域中的任一元素。任一元素的級均不是q 的倍 數(shù)。特別地，本原域元素的級是q ”一1 ，而其它所有元素的級必為口“一1 的因 子。 對g f ( q “) 上任何元素，恒有c o q “= c o 。它就是著名的費(fèi)爾馬( f e r m a t ) 定理。因此，在q 特征域中，元素為域整數(shù)的充要條件是，該元素是方程 x q x = 0 的根。 定義2 3 有限域g f ( q ) 上的n 次多項式為： 廠( x ) = f n x ”+ z l z ”- 1 + + z 工+ f o ， ( 2 1 ) z g f ( p )涪o ，1 ，2 ，l 媯一未知元 對于有限域來說，研究最多的是g f ( 2 ) = o ，1 ) 以及它的擴(kuò)展域g f ( 2 “) 。 因為g f ( 2 ”) 上每個元素都可表示為多項式的形式，并且多項式的系數(shù)在 g f ( 2 ) = 0 ，l 上。 哈爾溟工程大學(xué)碩士學(xué)位論文 給定任意兩個多項式廠( 石) ，g ( x ) 為g f ( q ) 上魄多項式，一定存在有唯一 的多項式q ( x ) 和r ( x ) 使： 廠( x ) = 口( 工) g ( x ) + ，( x ) 0 o o ，( 石) o ) 次首一多項式( 工) 在域g f ( q ) 既約，則由模f ( x ) 所組成的多項 式剩余類環(huán)是一個有礦個元素的有限域g f ( q ”) 。若q 特征域的的元素是 方程廠( x ) = 0 的根，則對于一切自然數(shù)n 、c o 一也必是廠( 功的根。 若國g f ( q “) ，且為g f ( q ) 上多項式f ( x ) 的根，則“= 國，故 旗礦，礦2 ，礦“必為廠( 工) 的m 個互不相同的根，這m 個互不相同的根稱 為的共扼根系。 在q 特征有限域中的每一個元素國，皆存在有唯一的最小多項式，記為 朋( x ) ，則它具有如下性質(zhì)： ( 1 ) 腳( x ) 在g f ( q ) 域上既約； ( 2 ) 若f ( x ) 也是c o ，c o p ，0 9 ，礦”1 上的多項式，且f ( c o ) = 0 ，則 聊( z ) 廠( 工) 。 若c o 為q 特征有限域g f ( q ”) 中的1 1 級元素，而m 是q 關(guān)于模n 的方次 m - i 數(shù)，則0 9 的最小多項式m ( x ) 是m 次多項式，且m ( x ) = 丌( 石一) = i 定義2 4 系數(shù)取自g f ( q ) 上的以g f ( q 1 ) 中本原域元素為根的最小多項 式，稱為本原多項式。若緲是q 特征有限域f 上的m 次域元素，則g f ( q ) 上 的次數(shù)小于m 的、緲的多項式的全體構(gòu)成域f 上的q ”階子域。 因為有限域的階一定是其特征的冪，而有限域的特征必是素數(shù)q 的冪 q “。因此，若有一素數(shù)q ，則一定可以從g f ( q ) 的多項式中選出一個m 次既 約多項式p ( x ) ，以它構(gòu)造出一個q 4 階有限域g f ( q “) 。并且該域包含了g f ( q ) 哈爾溟工程大學(xué)碩士學(xué)位論文 上所有m 次既約多項式的全部根。 如果把p ( x ) 的一個根稱為口，則可把q “階有限域中的每一個元素，表示 成系數(shù)在g f ( g ) 上且次數(shù)低于1 1 1 的口多項式。而g ，( g ) 上次數(shù)小于m 的多項 式與g f ( q ) 的m 重同構(gòu)。因此，m 重、多項式剩余類環(huán)以及口多項式之間均 同構(gòu)，都可以用來表示g ”階有限域。 在擴(kuò)展域g f ( q 胛) 中的g ”一1 個非零元素，都能用本原多項式的根口的多 項式表示，此時 1 ，口，口”1 ) 就是域的一組自然基底或本原基底也稱多項式 基底( 也稱多項式基) 。若口為g f ( q “) 中的本原域元素，則 缸，口p ，口p 2 ，口，“) 為g f ( q ”) 域的正規(guī)基底。正規(guī)基底其實就是以口為根的 本原多項式廠( x ) 的共扼根系。 在域的運(yùn)算和研究中，跡是非常有用的分析工具。 定義2 5 、若口g f ( q “) ，則它在g f ( q ) 上的跡為： z ( 倪) = 口+ 口g + + 口9 4 一( 2 4 ) 其中q 為素數(shù)或素數(shù)冪。 對于所有口，g f ( q ”) ，跡具有如下性質(zhì)： z 幢) g f ( q ) z ( a + ) = i ( a ) + i ( ) r r ( 旯a ) = a z ( 口) ，a g f ( q ) z ( a 9 ) = 乃 ) 因此跡是可以把g f ( q ”) 中元素映射到g f ( q ) 中。當(dāng)且僅當(dāng)有一個元素 夕g f ( q ”) ，使口= 一9 ，則z ( 口) = 0 。 與g f ( q “) 的基底b = ( , a o ，層，成一。) 相對應(yīng)，若 z ( 層乃) = ：二i 二 ( 2 5 ) 成立，則稱g f ( q “) 的基底b = ( ，乃，一。) 是b 的對偶基，如果 b = b ，則稱b 為自對偶基。 9 哈爾濱工程大學(xué)碩士學(xué)位論文 2 3 循環(huán)碼與b c h 碼 循環(huán)碼是一類重要的線性碼。由于具有以下性質(zhì)： ( 1 ) 循環(huán)碼具有嚴(yán)格的代數(shù)結(jié)構(gòu)，其性能易于分析； ( 2 ) 并且循環(huán)碼具有循環(huán)特性，其編譯碼電路，特別是編碼電路易于實現(xiàn)。 基于這些特征，循環(huán)碼特別引入注目，對它的研究和應(yīng)用也比較深入和系統(tǒng)。 定義2 6 設(shè)有一個n 重的k 維子空間圪。k ，若對其中任意一個 y = ( 以糾，口川，a o ) 圪i ，恒有巧= ( a n - l - i ，口柚小，a o ，a 剃) 圪，t ，則稱k i 為 循環(huán)子空間或循環(huán)碼。 域g f ( q ) 上的多項式和它上的n 重之間是一一對應(yīng)的，在( n ，k ) 循環(huán)碼中， 碼字( a n - 1a 川，a 。) 的多項式表示為： 盤( 對= a n _ i x “- 1 + a n _ 2 x ”2 + + q x + ，a f g f ( q ) ( 2 6 ) 它的循環(huán)移位一次后所得的碼字多項式為： a i ( x ) = a n _ 2 x ”1 + 口 一3 x 4 2 + + 口。工+ - l 相當(dāng)于乘以x 后，用，一1 取模： x a ( x ) = a n _ i x ”+ a n 一2 x “一14 - + a l x 24 - a o x = a n 一2 x “4 - + x + 以。一i ( n l o d 石4 1 ) 即循環(huán)碼可以用模x ”一1 的多項式表示。 在域g f ( q ) ( q 為素數(shù)或素數(shù)的冪) 上的( n ，k ) 循環(huán)碼中，存在有唯一的n - k 次首一多項式： g ( x ) = x “一+ g - k _ l x “一一4 - + g l 工+ g o ( 2 7 ) ， 使得域中的每一個碼多項式都是g ( x ) 的倍式，且每一個次數(shù)小于等于 ( n 1 ) 次的g ( x ) 的倍式一定是碼多項式。 因此g ( x ) 稱為碼的生成多項式，它是( n ，k ) 循環(huán)碼中唯一的n k 次多項式， g ( 石) 一定是x “一1 的因式。因此一個k 維循環(huán)碼，其最重要的是一個能除盡 ，一1 的n k 次首一多項式g ( x ) ，并由此多項式生成該循環(huán)碼。 因為每一個碼多項式都是的g ( x ) 倍式，因此g ( x ) 的根必是所有碼字多項 式的根。 ， g ( x ) 在擴(kuò)域g f ( q “) 上完全分解： g ( 工) = ( 石一o f l ) ( x 一口2 ) ( x o f r ) q 口，f ，= 1 ，2 ， ( 2 8 ) 1 0 哈爾濱工程大學(xué)碩士學(xué)位論文 其中g(shù) f ( q ”) ，= 一k 。因此每一個碼多項式c ( x ) 也必以 q ，a 2 ，q 為根。 1 9 5 9 年h o c q u e n g h e m 以及1 9 6 0 年的b o s e 和c h a u d h u r i 發(fā)明了b c h 碼， b c h 碼糾錯能力強(qiáng)，構(gòu)造方便，編譯碼簡單，有快速的譯碼算法。這類碼具 有嚴(yán)格的代數(shù)結(jié)構(gòu)，在編碼的理論和實際中都起著重要的作用，也是迄今為 止研究得最為詳盡、分析得最為透徹和成果最為豐富的碼類n 鍆。 b c h 碼n 1 1 是能糾正多個隨機(jī)錯誤的循環(huán)碼。這種碼是目前所發(fā)現(xiàn)的一類 很好的線性糾錯碼類，它的糾錯能力很強(qiáng)，特別是在短和中等碼長下，其性 能接近理論值，并且構(gòu)造方便，編碼簡單。特別是它具有嚴(yán)格的代數(shù)結(jié)構(gòu)， 因此它在編碼理論中起著重要的作用。 1 9 6 0 年彼得遜伊( p e t e r s o n ) 從理論上解決了二進(jìn)制b c h 碼的譯碼算法， 奠定了b c h 碼譯碼的理論基礎(chǔ)。稍后，格林斯坦( g o r e n s t e n ) 和齊勒爾 ( z i e r l e r ) 把它推廣到多進(jìn)制。伯利坎譜( b e r l e k a m p ) 利用迭代法譯碼b c h 碼，從而大大地提高了譯碼速度，從實際上解決了b c h 碼的譯碼問題。 定義2 7 給定任一有限域g f ( q ) 及其擴(kuò)域g f ( q ”) ，其中q 為素數(shù)或素 數(shù)的冪，m 為某一正整數(shù)。若碼元取自g f ( q ) 上的一循環(huán)碼，它的生成多項 式g ( x ) 的根集合r 中含有以下萬一1 個連續(xù)根： r2 口j ，l o ，口+ i ，口w - 2 時，則由g ( x ) 生成的循環(huán)碼稱為q 進(jìn)制b c h 碼。 其中口g f ( q ”) 是域中的n 級元素a 帕“g f ( q “) ( 0 f 艿一2 ) m o 是 任意正整數(shù)。如果生成多項式g ( x ) 的根中，有一個g f ( q “) 域中的本原域元 素，則刀= g “一1 ，稱這種碼長玎= q 用一1 的b c h 碼為本原b c h 碼；否則， 稱為非本原b c h 碼。g f ( q ”) 中元素的級一定是q “一l 的因子。 2 4r s 碼 2 4 1r s 碼的簡介 r e e d - s o l o m o n 碼5 川1 是一類有很強(qiáng)的糾錯能力的碼n ，是二進(jìn)制b c h 碼 “ 哈爾濱工程大學(xué)碩十學(xué)位論文 的多進(jìn)制推廣，也是一種典型的代數(shù)幾何碼，它首先由里得( r e e d ) 和索洛 蒙( s o l o m o n ) 應(yīng)用m s 多項式于1 9 6 0 年構(gòu)造出來的，所以稱為r e e d ，s o l o m o n 碼，簡稱r s 碼。 定義2 8g f ( q ) ( q 2 ) 上，碼長n = g 一1 的本愿b c h 碼稱為r s 碼。 r s 碼是符號域和根域相一致的b c h 碼。 長為n = q 一1 ，設(shè)計距離為萬的r s 碼，生成多項式： g ( x ) = ( x - - 口) ( x - - a + 1 ) ( x - - t z + 2 ) ( 2 9 ) 其中是任意正整數(shù)，口為g f ( q ) 上的本原域元素。由此生成了一個q 進(jìn)制的【g 一1 ，g 一翻r s 碼，有最小距離萬。碼最小距離等于校驗元的個數(shù)加， 所以也稱r s 碼為極大最小距離可分碼，簡稱m d s 碼。在給定每個碼字所具 有多少冗余量的情況下，r s 碼能夠產(chǎn)生極大的最小距離。換句話說，r s 碼 的最小距離d 、信息長度k 以及碼字長度n 滿足s i n g l e t o n 極限，即d = n k + 1 。 除此以外，i 峪碼是一種具有糾正多個錯誤能力的非二元碼，任何一個g f ( q ) 上的( n , k ) r s 碼，對任何k 個符號位置，將只有一個與這個位置內(nèi)g 種符號 組合之一相對應(yīng)的碼字。r s 碼的另外一個性質(zhì)是，碼字所使用的符號和譯碼 過程中所使用的符號是一致的，從而使得在譯碼過程中所進(jìn)行的運(yùn)算就是碼 符號之間的運(yùn)算n 。 2 4 2r s 碼的編碼 因為r s 碼是循環(huán)碼的一種，每個碼字都是生成多項式的倍數(shù)，在實際 中，常用到的是系統(tǒng)碼n 引，信息碼元以不變的形式在碼字的任意k 位( 通常 是在最前面的k 位) 中出現(xiàn)的碼稱為系統(tǒng)碼n 3 。 設(shè)g f ( 2 ”) 上，系統(tǒng)碼的矢量為： c = ( g 一。g 一：c o ) 用多項式可表示為： c ( x ) = c k l x - 1 + c 七一2 石- 2 + + c ：j + c o ) ( 2 1 0 ) 能糾正t 個碼元錯誤的r s 碼的生成多項式為： g ( x ) = ( x + 口) ( x + 口2 ) ( x + 口2 ) 2 t = 兀( 工+ 口) 哈爾濱工程大學(xué)碩士學(xué)位論文 所以編碼可用除法運(yùn)算，即將k 1 次的多項式e ( x ) 左移r = 2 t 位( 校驗 位) 并用g ( x ) 來除，再將除得的余式與x 2 c ( x ) 相加，即 d ( x ) = x 2 t c ( x ) + c ( x ) m o d g ( x ) 】。 ( 2 1 1 ) 采用系統(tǒng)碼編碼，所以 d = ( c ，r ) = ( g 一，g 一：c o ，磚一。r 一：r ) ( 2 1 2 ) 其中r 表示校驗碼組。 每組碼字都是定義在它的特定域上的，并且它的符號取自有限域 g f ( 2 ”) ，不同的域都有其相應(yīng)的域生成多項式，用于計算生成域中的各元素。 多項式的乘除法運(yùn)算與普通的代數(shù)多項式乘除法是相同，多項式的加減法運(yùn) 算則以2 為模的運(yùn)算，與邏輯異或相一致。 編碼具體方法為用待存儲的信息碼，( z ) 除以生成多項式，將最后的余數(shù) 作為r s 校驗碼。步驟如下： ( 1 ) 設(shè)待存儲的數(shù)據(jù)信息為k 碼元，需糾t 個錯，則在k 碼元后添加2 t ( 最p 蚧碼元，發(fā)送的數(shù)據(jù)信息為k + 2 t 碼元，對應(yīng)的多項式為x r f ( x ) 。 ( 2 ) 用生成多項式g ( x ) 去除，i ( x ) ，求得的余數(shù)為r - l 階的多項式，此多 項式即為經(jīng)過生成多項式編碼的r s 碼的校驗碼。 ( 3 ) 用，( x ) 以2 為模的方式加上余式多項式，得到的多項式即為存儲的 碼字。 2 4 3r s 碼的譯碼 r s 譯碼又稱解碼，主要分成3 步： 第一步由讀取的存儲碼組計算出伴隨式； 第二步由伴隨式求解出錯誤圖樣； 最后由錯誤圖樣和接收碼組計算出可能存儲的碼字n 劓。 譯碼算法主要有時域譯碼算法和頻域譯碼算法，因為該譯碼算法和其它 算法比較有很多優(yōu)點：首先，時域譯碼算法實現(xiàn)比較簡單，易于用計算機(jī)完 成譯碼。其次，利用時域譯碼算法不需要進(jìn)行傅立葉變換和逆傅立葉變換n 9 l ， 比起頻域譯碼算法要簡潔得多，減少了很多運(yùn)算。所以本文采用基于時域的 譯碼算法。 r s 碼的譯碼算法的復(fù)雜性主要歸結(jié)為關(guān)鍵方程的求解，即錯誤位置多項 哈爾濱工程大學(xué)碩七學(xué)位論文 式的求法。時域譯碼算法應(yīng)用較為普遍是b m 迭代算法，極大地加快了求錯 誤位置多項式仃( x ) 的速度，使譯碼速度能滿足多數(shù)應(yīng)用的需要n 引。 假設(shè)所要存儲的碼字為： c = ( c n l ，巳一2 ，c 1 ，c o ) 1 用多項式可以表示為： c ( x ) = q l x ”1 + c n 一2 x ”1 + + q x + c o ) ( 2 1 3 ) 由于存儲過程中出現(xiàn)故障，使讀取的碼字為： r = ( 一l ，一2 ，r l , t o ) 其多項式表示為： r ( x ) = ，：i l 石4 1 + ，：i 一2 x 卜1 + 、+ f i x + t o ) ( 2 1 4 ) 所以錯誤圖樣e = ( 巳中乞彩，e l ，e o ) 與存儲碼字和讀取碼字具有下面的 對應(yīng)關(guān)系： r=c+e(2-15) r s 譯碼算法比起編碼算法要復(fù)雜得多。譯碼算法是對讀取到的碼字進(jìn)行 運(yùn)算來確定信息碼域校驗碼是否符合編碼規(guī)則，從而利用所觀察到的情況進(jìn) 行判斷并盡可能的對出現(xiàn)的錯誤加以糾正。 r s 譯碼第一步是接收序列r ( x ) 計算伴隨式，伴隨式又稱校正子，一個 糾t 重錯的r s 碼，伴隨式是2 t 重，即s = ( s ，是，是，) ，其中s = r ( a ) 。 伴隨式完全由錯誤樣圖e 決定，它能夠反映出讀取到的碼字的差錯情況。 然后是求解出錯誤位置c r ( x ) ，為了能糾正出錯誤的碼字，必須要確定錯 誤碼字的位置。 在求得出錯誤位置后，再求出相應(yīng)錯誤位置的錯誤取值，最后將得到的 錯誤值修改并加到相應(yīng)的錯誤位置上。r s 碼譯碼具體步驟如圖2 1 所示。 1 4 哈爾濱工程大學(xué)碩士學(xué)位論文 2 5 本章小結(jié) ( 開始 ) 讀取存儲數(shù)據(jù)碼元 根據(jù)存儲數(shù)據(jù)碼元來計算伴隨式 + 確定錯誤位置多項式 解出錯誤位置多項式的根 計算錯誤值 對求出的錯誤位置與錯誤值進(jìn)行糾正 對糾正過的碼再進(jìn)行伴隨式計算 結(jié)果為0 ，糾正 結(jié)果不為0 ，表明 成功 超出t 個錯 ( 結(jié)束 ) 圖2 1r s 譯碼過程 本章介紹了e r a s u r e c o d e 的基本概念與原理，闡述了有限域的概念和在 有限域里的一些重要定義、性質(zhì)以及運(yùn)算規(guī)則，并著重介紹一類糾錯能力很 強(qiáng)的多進(jìn)制b c h 碼r e e d s o l o m o n 碼。本章為論文后續(xù)具有數(shù)據(jù)容錯恢 復(fù)的局域網(wǎng)絡(luò)存儲系統(tǒng)的設(shè)計打下了理論基礎(chǔ)。 哈爾濱丁程大學(xué)碩士學(xué)位論文 第3 章局域網(wǎng)絡(luò)存儲系統(tǒng)中r s 碼軟件實現(xiàn) 當(dāng)前，企業(yè)信息化程度的提高，自動化辦公能里的提升，計算機(jī)幾乎已 經(jīng)遍及到了技術(shù)人員的辦公桌上，使得企業(yè)所要存儲的數(shù)據(jù)信息也相對猛烈 迅速的增長。小型公司往往承擔(dān)不起巨額的數(shù)據(jù)信息存儲備份系統(tǒng)的硬件購 買費(fèi)用，所以設(shè)計出針對局域網(wǎng)絡(luò)存儲的容錯備份軟件系統(tǒng)是很有價值的。 3 1r s 碼選取 r s 碼對于多重的錯誤具有相當(dāng)高的檢測和糾正能力，其主要參數(shù)t ，表 示能糾正到的錯誤數(shù)據(jù)個數(shù)，同時也能檢測到2 t 個未知錯誤數(shù)據(jù)。為了能夠 達(dá)到糾正t 個錯誤數(shù)據(jù)的能力，需要增加2 t 個冗余數(shù)據(jù)洶1 。 通常在諸如學(xué)校的實驗室，公司的辦公室以及小型的企業(yè)網(wǎng)絡(luò)都采用簡 單的局域網(wǎng)絡(luò)連接其內(nèi)部計算機(jī)，計算機(jī)的數(shù)量大體在幾臺到十幾臺之間。 由于r s 碼是( n = q ，k , d = n - k + 1 ) 的線性碼，對于每一組q 與k ，都能實現(xiàn)一組 r s 碼的實現(xiàn)。每個r s 碼的碼字是一組有限域的符號，其中每一個符號都是 伽羅華域的元素，r s ( n ，k ，d ) 碼參數(shù)具體介紹如下： m ：每個符號比特數(shù)； 1 1 ：碼長挖= 2 ”一l ： t ：糾錯符號個數(shù)； d ：碼距d = 2 t + 1 ： k ：信息符號個數(shù)； 也因為在1 5 = 2 4 1 ，容易在g f ( 2 ”) m = 4 上實現(xiàn)，該碼的編譯碼過程所 以本文的系