Information bit decoding and optimal cascades of discrete memoryless channels.

Abstract

We introduce a class of information-theoretic problems that deal with systems in which information is transmitted through a series of noisy discrete memoryless channels, with limited or no processing between channels. We examine in detail some basic questions that arise in such systems. We deal with the effects of ordering of the channels on overall capacity, focusing particularly on the problem of finding the cascade of a set of channels that maximizes capacity. We establish certain conditions necessary for an ordering to be optimal. We also examine the characteristics that cause channels to have high capacity when cascaded with themselves. In the second part of the thesis we consider the problem of decoding a linear block code used over a binary symmetric channel with crossover probability p when the goal of the decoding is to minimize the probability of an information bit error. In general, there will be several different decoding strategies, each corresponding to the optimal rule over some range of p. Each of these strategies can be implemented by standard array with the appropriate choice of coset leaders that are not in general of minimum weight. We give optimal rules for selecting coset leaders in the regions where p is small and where p is near 1/2 for any linear mapping between information bits and codewords. The determination of the optimal rule has been an open problem for small p. The rule for p near 1/2 is important because for many codes, when p is fixed the optimal rule for any coset corresponds to either the optimal rule for small p, or the optimal rule for p near 1/2. We examine some specific codes, and compare the performance under optimal decoding to the performance of previously suggested strategies.