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

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

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

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