A general method of coding over expansion is proposed,which allows one to reduce the highly non-trivial problems of coding over analog channels and compressing analog sources to a set of much simpler subproblems, coding over discrete channels and compressing discrete sources. More specifically, the focus of this paper is on the additive exponential noise (AEN) channel, and lossy compression of exponential sources. Taking advantage of the essential decomposable property of these channels (sources), the proposed expansion method allows for mapping of these problems to coding over parallel channels (respectively, sources), where each level is modeled as an independent coding problem over discrete alphabets. Any feasible solution to the resulting optimization problem after expansion corresponds to an achievable scheme of the original problem. Utilizing this mapping, even for the cases where the optimal solutions are difficult to characterize, it is shown that the expansion coding scheme still performs well with appropriate choices of parameters. More specifically, theoretical analysis and numerical results reveal that expansion coding achieves the capacity of AEN channel in the high SNR regime. It is also shown that for lossy compression, the achievable rate distortion pair by expansion coding approaches to the Shannon limit in the low distortion region. Remarkably, by using capacity-achieving codes with low encoding and decoding complexity that are originally designed for discrete alphabets, for instance polar codes, the proposed expansion coding scheme allows for designing low-complexity analog channel and source codes.
This paper presents an analysis of spinal codes, a class of rateless codes proposed recently. We prove that spinal codes achieve Shannon capacity for the binary symmetric channel (BSC) and the additive white Gaussian noise (AWGN) channel with an efficient polynomial-time encoder and decoder. They are the first rateless codes with proofs of these properties for BSC and AWGN. The key idea in the spinal code is the sequential application of a hash function over the message bits. The sequential structure of the code turns out to be crucial for efficient decoding. Moreover, counter to the wisdom of having an expander structure in good codes, we show that the spinal code, despite its sequential structure, achieves capacity. The pseudo-randomness provided by a hash function suffices for this purpose. Our proof introduces a variant of Gallager's result characterizing the error exponent of random codes for any memoryless channel. We present a novel application of these error-exponent results within the framework of an efficient sequential code. The application of a hash function over the message bits provides a methodical and effective way to de-randomize Shannon's random codebook construction.  This paper investigates polar coding schemes achieving capacity for the AWGN channel. The approaches using a multiple access channel with a large number of binary-input users and a single-user channel with a large prime-cardinality input are compared with respect to complexity attributes. The problem of finding discrete approximations to the Gaussian input is then investigated, and it is shown that a quantile quantizer achieves a gap to capacity which decreases like 1 q (where q is the number of constellation points), improving on the 1 log(q) decay achieved with a binomial (central limit theorem) quantizer. In this paper, polar codes for the m-user multiple access channel (MAC) with binary inputs are constructed. It is shown that Arikan's polarization technique applied individually to each user transforms independent uses of an m-user binary input MAC into successive uses of extremal MACs. This transformation has a number of desirable properties: 1) the “uniform sum-rate” of the original MAC is preserved, 2) the extremal MACs have uniform rate regions that are not only polymatroids but matroids, and thus, 3) their uniform sum-rate can be reached by each user transmitting either uncoded or fixed bits; in this sense, they are easy to communicate over. A polar code can then be constructed with an encoding and decoding complexity of O(n log n) (where n is the block length), a block error probability of o(exp (- n1 2 - e)), and capable of achieving the uniform sum-rate of any binary input MAC with arbitrary many users. Applications of this polar code construction to channels with a finite field input alphabet and to the additive white Gaussian noise channel are also discussed.