A Deterministic Algorithm for the Capacity of Finite-State Channels

DOI10.1109/TIT.2021.3132675MaRDI QIDQ5080004zbMATH OpenOpenAlexFDO

Authors 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)

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

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)

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.

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; zbMATH DE number 4160640
• Capacity of a Class of Deterministic Relay Channels
• Capacity, mutual information, and coding for finite-state Markov channels

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)