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.
Multilevel coding is a general coding method designed for analog noise channels with a flavor of expansion @cite_17 . In particular, a lattice partition chain @math is utilized to represent the channel input, and, together with a shaping technique, the reconstructed codeword is transmitted to the channel. It has been shown that optimal lattices achieving Shannon limit exist. However, the encoding and decoding complexity for such codes is high, in general. In the sense of representing the channel input, our scheme is coincident with multilevel coding by choosing @math , , @math , for some @math , where coding of each level is over @math -ary finite field (see Fig. ). The difference in the proposed method is that besides representing the channel input in this way, we also expand'' the channel noise, such that the coding problem for each level is more suitable to solve by adopting existing discrete coding schemes with moderate coding complexity. Moreover, by adapting the underlying codes to channel-dependent variables, such as carries, the Shannon limit is shown to be achievable by expansion coding with moderate number of expanded levels.
@cite_17
2118420528 1512015702 2098653764 1992720861
This thesis proposes two constructive methods of approaching the Shannon limit very closely. Interestingly, these two methods operate in opposite regions, one has a block length of one and the other has a block length approaching infinity. The first approach is based on novel memoryless joint source-channel coding schemes. We first show some examples of sources and channels where no coding is optimal for all values of the signal-to-noise ratio (SNR). When the source bandwidth is greater than the channel bandwidth, joint coding schemes based on space-filling curves and other families of curves are proposed. For uniform sources and modulo channels, our coding scheme based on space-filling curves operates within 1.1 dB of Shannon's rate-distortion bound. For Gaussian sources and additive white Gaussian noise (AWGN) channels, we can achieve within 0.9 dB of the rate-distortion bound. The second scheme is based on low-density parity-check (LDPC) codes. We first demonstrate that we can translate threshold values of an LDPC code between channels accurately using a simple mapping. We develop some models for density evolution from this observation, namely erasure-channel, Gaussian-capacity, and reciprocal-channel approximations. The reciprocal-channel approximation, based on dualizing LDPC codes, provides a very accurate model of density evolution for the AWGN channel. We also develop another approximation method, Gaussian approximation, which enables us to visualize infinite-dimensional density evolution and optimization of LDPC codes. We also develop other tools to better understand density evolution. Using these tools, we design some LDPC codes that approach the Shannon limit extremely closely. For multilevel AWGN channels, we design a rate 1 2 code that has a threshold within 0.0063 dB of the Shannon limit of the noisiest level. For binary-input AWGN channels, our best rate 1 2 LDPC code has a threshold within 0.0045 dB of the Shannon limit. Simulation results show that we can achieve within 0.04 dB of the Shannon limit at a bit error rate of 10−6 using a block length of 10 7. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.) We address an open question, regarding whether a lattice code with lattice decoding (as opposed to maximum-likelihood (ML) decoding) can achieve the additive white Gaussian noise (AWGN) channel capacity. We first demonstrate how minimum mean-square error (MMSE) scaling along with dithering (lattice randomization) techniques can transform the power-constrained AWGN channel into a modulo-lattice additive noise channel, whose effective noise is reduced by a factor of spl radic (1+SNR SNR). For the resulting channel, a uniform input maximizes mutual information, which in the limit of large lattice dimension becomes 1 2 log (1+SNR), i.e., the full capacity of the original power constrained AWGN channel. We then show that capacity may also be achieved using nested lattice codes, the coarse lattice serving for shaping via the modulo-lattice transformation, the fine lattice for channel coding. We show that such pairs exist for any desired nesting ratio, i.e., for any signal-to-noise ratio (SNR). Furthermore, for the modulo-lattice additive noise channel lattice decoding is optimal. Finally, we show that the error exponent of the proposed scheme is lower bounded by the Poltyrev exponent. In this paper, we propose a new class of lattices constructed from polar codes, namely polar lattices, to achieve the capacity @math of the additive white Gaussian-noise (AWGN) channel for any signal-to-noise ratio (SNR). Our construction follows the multilevel approach of , where on each level we construct a capacity-achieving polar code. The component polar codes are naturally nested, thereby fulfilling the requirement of the multilevel lattice construction. We prove that polar lattices are AWGN-good, in the sense that the error probability (for infinite lattice decoding) vanishes for any fixed volume-to-noise ratio (VNR) greater than @math . Furthermore, using the technique of source polarization, we propose discrete Gaussian shaping over the polar lattice to satisfy the power constraint. The proposed polar lattices permit low-complexity multistage successive cancellation decoding. Both the construction and shaping are explicit, and the overall complexity of encoding and decoding is @math for any fixed target error probability. This paper considers the problem of variable-length coding over a discrete memoryless channel with noiseless feedback. This paper provides a stochastic control view of the problem whose solution is analyzed via a newly proposed symmetrized divergence, termed extrinsic Jensen–Shannon (EJS) divergence. It is shown that strictly positive lower bounds on EJS divergence provide nonasymptotic upper bounds on the expected code length. This paper presents strictly positive lower bounds on EJS divergence, and hence nonasymptotic upper bounds on the expected code length, for the following two coding schemes: 1) variable-length posterior matching and 2) MaxEJS coding scheme that is based on a greedy maximization of the EJS divergence. As an asymptotic corollary of the main results, this paper also provides a rate–reliability test. Variable-length coding schemes that satisfy the condition(s) of the test for parameters @math and @math are guaranteed to achieve a rate @math and an error exponent @math . The results are specialized for posterior matching and MaxEJS to obtain deterministic one-phase coding schemes achieving capacity and optimal error exponent. For the special case of symmetric binary-input channels, simpler deterministic schemes of optimal performance are proposed and analyzed.