冗余備份機制是安全存儲系統(tǒng)提高系統(tǒng)可靠性和容災容錯能力的一個重要方法。糾錯碼及糾刪碼技術(shù)是冗余備份機制的一個重要方法。與其他技術(shù)相比,糾刪碼技術(shù)在節(jié)省存儲空間,提高容錯容災能力,提高數(shù)據(jù)的可靠性方面有著明顯的優(yōu)勢。本文在學習和掌握已有的糾刪碼技術(shù)的基礎上,本文的主要貢獻在兩個方面: 本文構(gòu)建了求解最優(yōu)柯西矩陣的數(shù)學模型,并且提出了求解該問題的近似算法。通過分析柯西RS碼的編碼方式,柯西RS碼在編碼過程中柯西矩陣對編碼效率有著極大的影響。本文提出來的局部貪婪算法在復雜度均好于Plant提出的求解最優(yōu)柯西矩陣的算法,并且得到的最優(yōu)矩陣的近似解與Plant提出的算法得到的結(jié)果相同。 本文提出了LDPC碼校驗矩陣構(gòu)造算法Progressive Weight-Growth(PWG),該算法通過迭代增加校驗矩陣的行重和列重,構(gòu)造高碼率的LDPC碼。和現(xiàn)有構(gòu)造算法(MacKay構(gòu)造算法,比特填充算法)相比,LDPC碼能夠比它們構(gòu)造更高碼率的碼,同時PWG算法構(gòu)造的LDPC碼能夠提高碼中各個節(jié)點的圍長分布,并且與一些已知好碼有著相同的性能。

【文章頁數(shù)】：57 頁

【學位級別】：碩士

【部分圖文】：

圖3-7：LGA算法Fig.3-7:LGAalgorithm根據(jù)該算法，在域3GF(2)構(gòu)造一個G×的柯西矩陣，如圖3-8所示：

由于在每個步驟中，該算法總是選取重量最小的元素，所以該算法稱為局部貪婪算法(LocalizeGreedyAlgorithm,LGA)，該算法在每一個步驟中保證得到是最小重量的元素，但是不能保證最終得到是最優(yōu)解。圖3-7是該算法的具體描

圖3-10：4GF(2)上LGA與RC算法比較

方面對三種方法進行了比較。RC和LGA生成的柯西矩陣性能比較在這個比較過程中，參數(shù)分別為n=3,L=4,而m從3到13變化.在圖3-10中，m∈[3,13]時，點線表示LGA生成的矩陣的平均重量，實線表示RC生成的矩陣的平均重量(是一個定值)。

圖3-11：8GF(2)上LGA與RC算法比較

8GF(2)圖3-11中的平面是RC矩陣的平均重量，曲面則是LGA的平均重量。在這9×245=2205個矩陣中，矩陣平均重量的增益達到:210,224618.6%2205RCLGARCGGnmGWWW≤≤≤≤∑=LGA與PX的比較在PX和LGA的比較....

圖3-12：LGA與PX比較

×，兩種算法構(gòu)造出來的柯西矩陣的平均重量如圖3-12所示,從圖3-12中可以看出，LGA和PX得到的柯西矩陣的平均重量相差無幾。直線為L變化時的RC方法得到的柯西矩陣的平均重量。

本文編號：3957954