A Deterministic Algorithm for the Capacity of Finite-State Channels

DOI10.1109/TIT.2021.3132675zbMATH Open1495.94035arXiv1901.02678OpenAlexW2911101083MaRDI QIDQ5080004FDOQ5080004

Chengyu Wu, Guangyue Han, Venkat Anantharam, Brian Marcus

Publication date: 30 May 2022

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We propose two modified versions of the classical gradient ascent method to compute the capacity of finite-state channels with Markovian inputs. For the case that the channel mutual information is strongly concave in a parameter taking values in a compact convex subset of some Euclidean space, our first algorithm proves to achieve polynomial accuracy in polynomial time and, moreover, for some special families of finite-state channels our algorithm can achieve exponential accuracy in polynomial time under some technical conditions. For the case that the channel mutual information may not be strongly concave, our second algorithm proves to be at least locally convergent.

Full work available at URL: https://arxiv.org/abs/1901.02678

Recommendations

• A Randomized Algorithm for the Capacity of Finite-State Channels
• Computable Upper Bounds on the Capacity of Finite-State Channels
• The compound channel capacity of a class of finite-state channels
• The capacity of finite-state channels in the high-noise regime
• On the Capacity of Indecomposable Finite-State Channels With Feedback
• Tighter Bounds on the Capacity of Finite-State Channels Via Markov Set-Chains
• An Algebraic, Analytic, and Algorithmic Investigation on the Capacity and Capacity-Achieving Input Probability Distributions of Finite-Input– Finite-Output Discrete Memoryless Channels
• scientific article
• Capacity of a Class of Deterministic Relay Channels
• Capacity, mutual information, and coding for finite-state Markov channels

zbMATH Keywords

capacity of finite-state channels with Markovian inputsmodified gradient ascent method

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Channel models (including quantum) in information and communication theory (94A40)

Cited In (1)

• Tighter Bounds on the Capacity of Finite-State Channels Via Markov Set-Chains

This page was built for publication: A Deterministic Algorithm for the Capacity of Finite-State Channels

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5080004)