Back to Search
Start Over
An Upgrading Algorithm With Optimal Power Law.
- Source :
-
IEEE Transactions on Information Theory . Dec2021, Vol. 67 Issue 12, p7822-7836. 15p. - Publication Year :
- 2021
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 67
- Issue :
- 12
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 153731606
- Full Text :
- https://doi.org/10.1109/TIT.2021.3114375