Research On Encoding And Decoding Of Distributed Binary Codes

In contrast to replication,network coding in distributed storage system is able to offer higher reliability and less storage space consuming with,the same redundancy.Usually,network coding employed should have MDS property,where k source blocks are encoded to n coded blocks,and any k blocks out of the n coded blocks can reconstruct the original data.Zigzag-decodable code is a class of MDS codes with the optimal encoding complexity,and it can be decoded without complicated matrix solving.In particular,their encoding and decoding are shift-based and xor-based.However,Zigzag-decodable codes' parity block is larger than source block as a result of shif operation,which causes great overhead especially when k is large.In this thesis,we design a generation matrix,which achieves a symmetric Zigzag-decodable code.Different from the coding schemes before,the parity blocks in our schem increase at the same length and thus save the overhead.Since the parity block of Zigzag-decodable code is larger than source block,more data need to be transmitted when recovering original data among distributed storage system.In-place recovery scheme is a solution to this problem,but the original In-place recovery scheme only suits for whose coding matrix owns increasing-difference property.In this thesis,we prove that when all the original blocks start recovering during the execution of Zigzag decoding algorithm,we can visit parity blocks with an unchanged order during iteration and all original blocks can recovery an unknowned bit during a visit.Acording to this,we improve the In-place recovery scheme such that the improved scheme is feasible to all Zigzag-decodable codes.The simulations prove that our symmetric Zigzag-decodable code and the improved In-place recovery scheme have the same efficiency compared with the known schems.