Design of Optimal Short-Length LT Codes Using Evolution Strategies

Abstract

Luby Transform (LT) and its companion Raptor codes are the most popular implementations of digital fountain codes. Performance of these rateless forward erasure correction codes is determined mainly by the degree distributions of their encoded symbols. Although the asymptotic behaviors of LT codes with large (>10(5)) symbol blocks have been deduced analytically, a proficient method for finding the optimal degree distributions of short length (<10(3)) LT codes is still absent. In this paper, we propose a practical approach to employ evolution strategies in finding the degree distributions of optimal short-length LT codes for different applications. Our approach begins with the development of a new performance model for LT codes based on three measurements: coding overhead epsilon, failure ratio r and failure occurrence probability p. Three evolution strategies (DE, CMA-ES and NES) were then employed to minimize these performance measurements separately with careful design of fitness functions and necessary transformations of decision variables. Throughout the evolution process, the performance of individual LT code in the population was evaluated with numerical simulations. Our experiments showed that the optimal degree distributions can be found using all three evolution strategies but with different convergence rates and the (r, p, epsilon) values of these optimized codes are all distributed on a smooth concave surface.