Polar Coded Computing: The Role of the Scaling Exponent
Polar Coded Computing: The Role of the Scaling Exponent
复制标题
极性编码计算：缩放指数的作用
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Marco Mondelli
中科院分区：
文献类型：
--
作者：
Dorsa Fathollahi;Marco Mondelli
我们考虑使用极化码的编码分布式计算的问题。编码计算系统的平均执行时间与Soleymani，Jamali和Mahdavifar最近的工作中通过二进制擦除信道传输的错误概率有关，其中研究了二进制线性码的性能。在本文中，我们专注于极化码，并揭示了平均执行时间与码族的标度指数μ之间的联系。在极化码的有限长度表征中，标度指数是捕获收敛到容量的速度的关键对象。特别地，我们证明了（i）极化码的归一化平均执行时间与最优MDS码的归一化平均执行时间之间的差距为O（n-1/μ），以及（ii）通过考虑具有大内核的极化码，该上限可以被改进为大致O（n-1/2）。我们推测这些界限可以分别改进为O（n-2/μ）和O（n-1），并提供了一个启发式的论点以及支持这一观点的数值证据。
We consider the problem of coded distributed computing using polar codes. The average execution time of a coded computing system is related to the error probability for transmission over the binary erasure channel in recent work by Soleymani, Jamali and Mahdavifar, where the performance of binary linear codes is investigated. In this paper, we focus on polar codes and unveil a connection between the average execution time and the scaling exponent μ of the family of codes. In the finite-length characterization of polar codes, the scaling exponent is a key object capturing the speed of convergence to capacity. In particular, we show that (i) the gap between the normalized average execution time of polar codes and that of optimal MDS codes is O(n–1/μ), and (ii) this upper bound can be improved to roughly O(n–1/2) by considering polar codes with large kernels. We conjecture that these bounds could be improved to O(n–2/μ) and O(n–1), respectively, and provide a heuristic argument as well as numerical evidence supporting this view.