论文标题
极性编码计算：缩放指数的作用
Polar Coded Computing: The Role of the Scaling Exponent
论文作者
论文摘要
我们考虑使用极地代码进行编码的分布式计算问题。编码计算系统的平均执行时间与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. The scaling exponent has emerged as a central object in the finite-length characterization of polar codes, and it captures 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.
