A New Zigzag-Decodable Code with Efficient Repair in Wireless Distributed Storage

A code is said to possess the combination property if k source packets are mapped into n \geq k packets and any k out of these n packets are able to recover the information of the original k packets. While the class of maximum-distance-separable codes are well known to have this property, its decoding complexity is generally high. For this reason, a new class of codes which can be decoded by the zigzag-decoding algorithm is considered. It has a lower decoding complexity at the expense of extra storage overhead in each parity packet. In this work, a new construction of a zigzag decodable code is proposed. The novelty of this new construction lies in the careful selection of the amount of bit-shift of each source packet in obtaining each parity packet. Besides, an efficient on-the-air repair scheme based on physical-layer network coding is designed.