Biblio

A new framework is presented in this paper for proving coding theorems for linear codes, where the systematic bits and the corresponding parity-check bits play different roles. Precisely, the noisy systematic bits are used to limit the list size of typical codewords, while the noisy parity-check bits are used to select from the list the maximum likelihood codeword. This new framework for linear codes allows that the systematic bits and the parity-check bits are transmitted in different ways and over different channels. In particular, this new framework unifies the source coding theorems and the channel coding theorems. With this framework, we prove that the Bernoulli generator matrix codes (BGMCs) are capacity-achieving over binary-input output symmetric (BIOS) channels and also entropy-achieving for Bernoulli sources.

Recently, the δ-mutual information between uncertain variables has been introduced as a generalization of Nair's non-stochastic mutual information functional [1], [2]. Within this framework, we introduce four different notions of capacity and present corresponding coding theorems. Our definitions include an analogue of Shannon's capacity in a non-stochastic setting, and a generalization of the zero-error capacity. The associated coding theorems hold for stationary, memoryless, non-stochastic uncertain channels. These results establish the relationship between the δ-mutual information and our operational definitions, providing a step towards the development of a complete non-stochastic information theory.

This paper is concerned with three ensembles of systematic low density generator matrix (LDGM) codes, all of which were provably capacity-achieving in terms of bit error rate (BER). This, however, does not necessarily imply that they achieve the capacity in terms of frame error rate (FER), as seen from a counterexample constructed in this paper. We then show that the first and second ensembles are capacity-achieving under list decoding over binary-input output symmetric (BIOS) memoryless channels. We point out that, in principle, the equivocation due to list decoding can be removed with negligible rate loss by the use of the concatenated codes. Simulation results show that the considered convolutional (spatially-coupled) LDGM code is capacity-approaching with an iterative belief propagation decoding algorithm.