分布式二元編解碼研究.pdf

1、相比傳統(tǒng)的副本技術(shù)，在分布式存儲系統(tǒng)中使用網(wǎng)絡(luò)編碼技術(shù)能以相同的冗余度提供更高的可靠性并消耗更少的存儲空間。分布式存儲系統(tǒng)通常采用具有MDS性質(zhì)的網(wǎng)絡(luò)編碼，它將原數(shù)據(jù)等分為k個數(shù)據(jù)塊后編碼得到n個編碼數(shù)據(jù)塊，并分別存儲于n個節(jié)點(diǎn)之中，使用任意k個節(jié)點(diǎn)中存儲的數(shù)據(jù)即可恢復(fù)原數(shù)據(jù)。
　　Zigzag-decodable編碼具有最優(yōu)的編解碼復(fù)雜度，解碼時不需要求解矩陣的逆，并且編解碼過程僅使用移位與異或運(yùn)算，具有較高的編解碼效率，同時該

2、編碼具有MDS性質(zhì)。但是受移位操作影響，Zigzag-decodable編碼得到的校驗(yàn)序列長度都遠(yuǎn)遠(yuǎn)大于原數(shù)據(jù)序列。本文設(shè)計了一種編碼矩陣，實(shí)現(xiàn)了對稱的Zigzag-decodable編碼。與之前的編碼方案不同，本文的編碼矩陣中各元素的指數(shù)形成了一個循環(huán)矩陣，得到的各校驗(yàn)序列增加的長度相同，使得其校驗(yàn)序列長度小于已知的構(gòu)造。
　　由于Zigzag-decodable編碼的校驗(yàn)序列長度大于原數(shù)據(jù)序列，解碼時幫助節(jié)點(diǎn)向Data Col

3、lector傳輸?shù)臄?shù)據(jù)量大于原數(shù)據(jù)大小。Fu等人提出的In-place解碼方案解決了該問題，但它僅適用于編碼矩陣具有increasing-difference性質(zhì)的編碼。本文證明了在Zigzag decoding算法運(yùn)行過程中，一旦所有原數(shù)據(jù)序列被恢復(fù)的比特數(shù)大于0，那么可以按照一定的順序迭代訪問校驗(yàn)序列，所有原數(shù)據(jù)序列在每一輪訪問中都可以恢復(fù)一個未知比特，直到原數(shù)據(jù)序列被完整恢復(fù)。結(jié)合Zigzag decoding算法，本文得到了一種