A Polynomial Formula for Finite-Length BATS Code Performance

摘要

Batched sparse (BATS) codes have been proposed for communication through networks with packet loss. BATS codes include a matrix generalization of fountain codes as the outer code and random linear network coding at the intermediate network nodes as the inner code. BATS codes, however, do not possess a universal degree distribution that achieves the optimal rate for any distribution of the transfer matrix ranks, so that fast performance evaluation of finite-length BATS codes is important for optimizing the degree distribution. The state-of-the-art finite-length performance evaluation method has a computational complexity of O(K2n2M) , where K , n , and M are the number of input symbols, the number of batches, and the batch size, respectively. We propose a polynomial-form formula for finite-length BATS codes performance evaluation with the computational complexity of O(K2nlnn) . Numerical results demonstrate that the polynomial-form formula can be significantly faster than the previous methods.