Finite-length analysis of BATS codes

In this paper, performance of finite-length batched sparse (BATS) codes with belief propagation (BP) decoding is analyzed. For fixed number of input symbols and fixed number of batches, a recursive formula is obtained to calculate the exact probability distribution of the stopping time of the BP decoder. When the number of batches follows a Poisson distribution, a recursive formula with lower computational complexity is derived. Inactivation decoding can be applied to reduce the receiving overhead of the BP decoder, where the number of inactive symbols determines the extra computation cost of inactivation decoding. Two more recursive formulas are derived to calculate the expected number of inactive symbols for fixed number of batches and for Poisson distributed number of batches, respectively. Since LT/Raptor codes are BATS codes with unit batch size, our results also provide new analytical tools for LT/Raptor codes.