Best Paper Award

  Error correcting codes realize efficient and reliable communication and storage systems. The theory of error correcting codes is referred to as coding theory.
  The purposes of coding theory are (1) constructing a pair of code and decoder with high decoding performance and low complexity and (2) analyzing or evaluating the performance via mathematical approaches or computer simulations.
  Fountain codes are error correcting codes for the user datagram protocol (UDP), especially for multicasting, in computer networks.
  In the fountain coding system, erased packets are recovered by a packet-oriented erasure correcting code.
  The Raptor code is a fountain code which encodes a message using exclusive OR (XOR) and which can be efficiently decoded by an iterative decoding algorithm. The Raptor code is known to have good decoding performance with linear decoding complexity.
  This paper constructs a fountain code, called the zigzag decodable fountain (ZDF) code and proposes a decoding algorithm for this code.
   The ZDF code encodes a message using XOR and shift operation and is efficiently decoded by an iterative decoding algorithm.
  It is easy to implement the encoder and the decoder for the ZDF codes since they employ only simple operations.
  Simulation results in the paper show that ZDF codes have a higher decoding performance and lower space decoding complexity than Raptor codes.
  Moreover, the paper proves that ZDF codes have a higher decoding performance than Raptor codes with equivalent system parameters.
  Furthermore, the paper clarifies the asymptotic decoding threshold of ZDF codes via an analysis technique called density evolution.
  As mention above, this paper constructs a fountain code called ZDF code, proposes its decoding algorithm, and evaluates its decoding performance in a mathematical approach and computer simulation.
  The resulting coding system has higher decoding performance and lower space complexity than existing coding systems.
  Hence, the coding system proposed in the paper is valuable.
  Moreover, the results of the paper suggest that applying shift operation is useful for constructing packet-oriented erasure correcting schemes.