Research On Sawtooth Decoding In Distributed Storage And Wireless Communication

Zigzag Decoding(ZD)is a way of decoding by repeating the process of backward substitution.As the decoding process operates in the binary field,this measure is widely adopted in distributed storage(DS)and wireless communication.In storage system,the combination property(CP)is defined as if k source packets are encoded into n packets,where n ?k,and any out of these n packets are able to recover the information of the original k packets.Maximum distance separable(MDS)codes have this property,and are widely adopted by distributed storage systems to provide data reliability in an efficient manner.However,its decoding complexity is high.Therefore,a new storage code with CP and ZD(CP-ZD)property is designed.The code possesses the following properties: operation within binary filed,low decoding complexity,and with some storage overhead.To implement such a code,each of the original packets is shifted by several bits and then adding them over binary field in bit-wise manner.The number of bits shifted is represented by a matrix,which is carefully designed.The matrix can be obtained from a specially constructed triangle by taking its maximal sub-matrix.Corresponding analysis shows that the storage overhead is reduced significantly in most scenarios when compared with existing storage codes.In wireless communication,the traditional random access(RA)protocol has a weak anticollision capability,and the random linear network coding(RLNC)technology can solve this collision problem.However,the RLNC has high computational complexity.Therefore a new random access framework,named as zigzag-division multiple access(ZDMA),is proposed for wireless networks.This framework allows the collision problem to be improved and can significantly improve system throughput.The key technique is to allow simultaneous transmissions at the transmitters and employ zigzag decoding at the receiver.Three new random access protocols are proposed based on ZD.Extensive numerical studies show that compared with two reference protocols,including slotted ALOHA and tree splitting,their counterparts that incorporate ZDMA achieve significantly larger system throughput.Besides,the third protocol,named as greedy scheduling with zigzag-division multiple access(GS-ZDMA)achieves the highest system throughput.