Asymptotic Analysis of Factored LT Codes for Distributed Matrix Multiplication

摘要

This work considers the asymptotic analysis of factored LT (FLT) codes which we proposed previously for distributed matrix multiplication. We show that all nodes in the Tanner graph of a randomly sampled code have a treelike neighborhood with high probability. This ensures that the density evolution analysis gives a reasonable estimate of the average error performance of FLT codes. In addition, using Azuma-Hoeffding inequality, we derive concentration results to show that the error performance of a randomly chosen FLT code is close to the ensemble average. Our simulation results indicate that the error performance concentrates around the ensemble average for moderate values of blocklength.