CIF: Small: Channels with Memory -- Universal-Compression-Based Modeling Principles for Computing and Optimizing Information Rates

University Of Hawaii, Honolulu

Investigators

Abstract

ABSTRACT The behavior of most physical communication channels depends on the past usage of the channel -- namely, many physical communication channels exhibit "memory". The challenge then is to construct tools that optimally take advantage of the channel memory. In addition, usual information theoretic analysis methods are ill equipped to even compute the capacity, i.e., how much information can be reliably sent through such channels with long memory. This research attacks these problems using recent developments in the fields of source coding and statistics and augments existing computational tools specifically for channels with memory. In the context of communication channels, an adequate model is the simplest fit to the channel input/output observations that enables sufficiently accurate evaluation (estimation) of the channel capacity. The investigators are extending universal compression principles, particularly those developed for the undersampled regime, to information transmission problems. The practical thrust of the research includes the development of algorithms for model based capacity computations. The starting point is the efficient implementation of the Baum-Welch/BCJR algorithm as a computational kernel in a range of approximations to the generalized Blahut-Arimoto method. Specifically, techniques that adaptively control the number of processed states are exploited, trading off the time per iteration and accuracy of computations. While the theoretical thrust reduces the state space by fitting a simpler model, the algorithm design component adds another dimension to complexity reduction by utilizing Markov chain Monte Carlo techniques for navigating complex state spaces, i.e., by transversing only high probability states.