Research On Encoding Methods Of Zigzag-Decodable Forward Erasure Codes

With the rapid development of network technology, the number of netizens has experienced an explosive growth, and networked multimedia applications have become more and more popular. The rapidly increasing network traffic and diversified service bring up higher requirements to the communication system. As we know, many factors, such as network congestion, channel fading and so on, result in the packet loss problem in the network. Forward erasure coding is one of effective approaches to cope with the packet loss problem. For a practical forward erasure code, a good trade-off should be achieved between the coding complexity and the erasure performance. In 2013, a Zigzag-decodable erasure code is first proposed, and it has very low coding complexity and maximum distance separate (MDS) property. But the length of the parity packets is slightly longer than that of the original packets in order that the Zigzag decoding method can be used to recover the original packets. This thesis studies new code construction methods for the Zigzag-decodable forward erasure codes.In this thesis, we propose a new code construction of the Zigzag-decodable MDS code based on Cauchy matrix over GF(qp) (q is a prime number, p≥1), and prove that encoded packets are Zigzag-decodable. In the proposed code construction, we first construct a Cauchy matrix over GF(qp). Then, the elements in the Cauchy matrix are expressed by the generator over GF(qp). As the generator is regarded as the coded offset symbol, a Zigzag-decodable coded coefficient matrix is formed. In this code construction, the packet-oriented multiplication and summation operations over high order finite field are tactfully converted into shift and exclusive-OR operations in GF(2). And the proposed Zigzag-decodable code has the MDS property and low overhead. Simulation results show that, compared with the existing Zigzag-deocodable code constructions, the overhead of the proposed code construction is less for the same the number of parity packets.For the time-varying erasure channels, we propose a new code construction of Zigzag-decodable rateless code based on the property of Zigzag-decodable erasure codes. At the encoder, coded packets can be generated endlessly by choosing coded offset randomly and XORing the original packets. Simulation results show that the probability of generating MDS coded packets is about 99.6% when the maximum selection coded offset is 254bits.Due to the property of MDS and low coding complexity, Zigzag-decodable erasure codes have a widespread prospect in many applications, such as networked video streaming, distributed storage system and so on.