Pacific Institute for the Mathematical Sciences - PIMS

Markov Capacity for Factor Codes with an Unambiguous Symbol

For a noisy channel, the stationary capacity is the supremum of information rates achievable by stationary input processes.
The Markov capacity of a given order is the supremum of information rates achievable by stationary Markov input processes of the given order. Although Markov capacity asymptotically (as the order increases) achieves stationary capacity under mild assumptions, it is believed that the stationary capacity is not achieved by a finite-order stationary Markov process. In this talk, I will focus on input-constrained deterministic channels, which can be characterized as factor codes defined on subshifts. In this case, a sufficient condition for the stationary capacity to be achieved by a finite-order stationary Markov process is the existence of a subshift of finite type in the domain restricted to which the corresponding code is finite-to-one and onto. I will first give a characterization of this stronger condition for standard factor codes defined on a spoke graph. Then, I will introduce our conjecture that for such a code, the finite-to-one and onto property is indeed equivalent to the existence of a finite-order stationary Markov chain that achieves the capacity of the corresponding deterministic channel. Finally, I will give a necessary and sufficient condition for a more general class of codes to admit a subshift of finite type restricted to which the code is one-to-one and onto. Joint work with Guangyue Han and Brian Marcus.

This event is hybrid (if in person, please wear a mask)

Location: ESB 4133

Join Zoom Meeting:

https://ubc.zoom.us/j/66742890307?pwd=ejNYUjlPNkQ3OFRncEdlRzU2a3NNZz09

Meeting ID: 667 4289 0307

Passcode: 137029