论文标题
具有最佳功率法的升级算法
An Upgrading Algorithm with Optimal Power Law
论文作者
论文摘要
考虑一个通道$ W $以及给定的输入分发$ P_X $。在某些设置（例如在极地代码的构建中），$ W $的输出字母为“太大”，因此我们用$ w $替换为$ Q $，其输出字母较小。我们说，如果通过处理其输出从$ Q $获得$ W $，则$ Q $相对于$ W $升级。在这种情况下，$ w $的输入和输出之间的共同信息$ i（p_x，w）$由$ i（p_x，q）$在$ q $的输入和输出之间的互相信息限制。在本文中，我们提出了一种算法，该算法从$ w $中产生升级的通道$ q $，该函数的函数为$ p_x $，所需的输出字母大小为$ q $，表示为$ l $。我们表明，相互信息的差异是“小”。也就是说，它是$ o（l^{ - 2/（| \ Mathcal {x} | -1）}）$，其中$ | \ Mathcal {x} | $是输入字母的大小。 $ L $的权力定律是最佳的。我们通过数值实验来补充我们的分析，这些实验表明，在非反应设置中，现有的最新算法也可以改善开发的算法。
Consider a channel $W$ along with a given input distribution $P_X$. In certain settings, such as in the construction of polar codes, the output alphabet of $W$ is `too large', and hence we replace $W$ by a channel $Q$ having a smaller output alphabet. We say that $Q$ is upgraded with respect to $W$ if $W$ is obtained from $Q$ by processing its output. In this case, the mutual information $I(P_X,W)$ between the input and output of $W$ is upper-bounded by the mutual information $I(P_X,Q)$ between the input and output of $Q$. In this paper, we present an algorithm that produces an upgraded channel $Q$ from $W$, as a function of $P_X$ and the required output alphabet size of $Q$, denoted $L$. We show that the difference in mutual informations is `small'. Namely, it is $O(L^{-2/(|\mathcal{X}|-1)})$, where $|\mathcal{X}|$ is the size of the input alphabet. This power law of $L$ is optimal. We complement our analysis with numerical experiments which show that the developed algorithm improves upon the existing state-of-the-art algorithms also in non-asymptotic setups.
