Algorithms for Computing the Capacity of Finite State MarkovChannels

Abstract

Capacity Computation of Finite State Markov Channels Using Regenerative Methods

Abstract Introduction Information-theoretic aspects are fundamental to communication systems. With recent advances in wireless communication, determining the capacity of wireless channels has become increasingly important. The finite state Markov (FSM) model is particularly suitable for modeling wireless fading channels and has been studied extensively. However, explicit formulae or algorithms to compute channel capacity are available only under restrictive assumptions.

This thesis focuses on FSM channels and provides algorithms to compute the single-user capacity and lower bounds under more realistic scenarios.

Methodology and Contributions

Regenerative Approach

Developed a regenerative framework to compute the capacity of FSM channels.

Derived new entropy and mutual information rate formulae for regenerative stochastic processes.

These formulae are useful for simulation-based estimation of entropy and mutual information rates.

Markov Channels without Feedback

Applied regenerative techniques to Markov channels.

Generalized existing results on FSM channel capacity without feedback.

Extended analysis to channels with inter-symbol interference (ISI).

Proposed computationally efficient algorithms to obtain tighter lower bounds on capacity.

Markov Channels with Side Information

Developed algorithms for channels where channel state information at the transmitter (CSIT) is imperfect and channel state information at the receiver (CSIR) is perfect.

Provided algorithms even when single-letter characterizations of capacity are unavailable.

Considered both discrete alphabet channels and AWGN fading channels.

For AWGN fading channels, incorporated an average transmitter power constraint and derived an algorithm to obtain the Optimal Power Allocation (OPA) policy that achieves capacity.

Conclusions Introduced regenerative methods for capacity computation in FSM channels.

Derived entropy and mutual information rate formulae applicable to simulation-based studies.

Generalized capacity results for FSM channels without feedback, including ISI scenarios.

Proposed novel algorithms for Markov channels with side information, addressing cases where no prior algorithms existed.

Provided an OPA policy for AWGN fading channels under power constraints.