A Polynomial Formula for Finite-Length BATS Code Performance

作者：Zhao, Huakai; Yang, Shenghao^*; Dong, Guangliang

来源：IEEE Communications Letters, 2017, 21(2): 222-225.

DOI：10.1109/LCOMM.2016.2619698

• Network coding
• BATS code
• finite-length analysis
• LT code
• belief propagation
• polynomial form

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(K(2)n(2)M), 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(K(2)n ln n). Numerical results demonstrate that the polynomial-form formula can be significantly faster than the previous methods.

• 出版日期2017-2
• 单位香港中文大学（深圳）; 北京跟踪与通信技术研究所