Low-Complexity List Decoding of Reed-Solomon Coded Pulse Position Modulation

Abstract:
Reed-Solomon coded pulse position modulation — also known as the Kautz-Singleton code — found many applications in multiple access communications, in nonadaptive group testing, and in pooling designs in DNA mapping. Usually an exhaustive search was used to decode these codes which results in an exponential complexity in the code dimension. In this paper, a list decoding algorithm for the Kautz-Singleton codes based on the Guruswami-Sudan and Koetter-Vardy list decoding algorithms is presented. The analysis reveals that the algorithm has only polynomial complexity and is hence very well suited for low-complexity applications as they are desired, e.g., in ultrawideband communications. Index Terms — Ultra-Wideband Communications, Pulse Position Modulation, Reed-Solomon Codes, List Decoding, Disjunctive Channel.