Iterative Quantization Based On Low-density Generator Matrix Codes

Quantization, in particular mean-square error (MSE) quantization, is not only essen-tial in lossy source coding problems, but can also assume in channel coding problems thekey role of shaping the transmitted signal to have a near-optimal distribution, which isnecessary for approaching capacity. Being dual to the low-density parity-check (LDPC)codes commonly used in channel coding, low-density generation matrix (LDGM) codes arewell-suited to such quantization problems, but its iterative quantization algorithm basedon belief propagation (BP) can only converge after the introduction of extra decimationsteps, preventing direct application of conventional density evolution (DE) methods foranalysis. Proper analysis of this iterative quantization algorithm and optimization of theLDGM degree distribution are essential to achieving near-ideal quantization performance,yet they remain unsolved so far.In this thesis, the use of LDGM-based iteration quantization in MSE quantization,and more generally, symmetric source coding problems over a fnite abelian group is an-alyzed, and parameters such as the degree distribution are optimized accordingly. AsDE methods cannot accommodate the necessary decimation steps, the proposed analysismethod instead considers each decimation step separately, and shows the dependence ofquantization performance on the accuracy of the BP-derived extrinsic information used bydecimation step. Through the use of scrambling codes and other techniques, it is provedthat the BP messages and the extrinsic information have symmetric densities and satisfydegradation relationships; in this way, the error in the extrinsic information can be bound-ed, and sufcient or necessary conditions for the error to vanish when the block lengthand the iteration count go to infnity have been derived, all in terms of DE results of thedegree distribution. Using these conditions as the optimization criteria, degree distribu-tion optimization is carried out by frst applying linear programming to obtain an initialoptimization result under erasure approximation (EA), then iteratively using DE resultsto correct EA errors, ultimately allowing the optimal degree distribution under an inf-nite iteration count to be obtained with high accuracy. The above work is frst carriedout for binary codebooks, and then extended to2K-ary codebooks formed by applying a modulation mapping on binary LDGM codewords.In practice, the number of iterations is necessarily fnite, so some error will alwaysremain in the BP extrinsic information, leading to decimation errors that can negativelyafect subsequent iterations. This efect is analyzed by generalizing the observations frombinary erasure quantization (BEQ), and a recovery algorithm for BEQ as well as binaryand non-binary MSE quantization has been proposed that reduces the efect of decimationerrors on subsequent iterations by adjusting the BP priors, thus achieving signifcantlylower quantization errors. In addition, such analysis also enables an empirical formulato be found relating the quantization error and the number of iterations, the pace ofdecimation, as well as the code rate, and further optimization of these parameters as wellas the degree distribution are then cariied out. Simulation results show that the proposediterative quantization algorithm can indeed achieve near-ideal quantization error in MSEquantization, with the gap to the theoretical limit reduced to as low as0.012dB, which isfar beyond the performance achievable with other methods, including TCQ or polar codes,at a comparable block length and computational complexity.The LDGM codebook is fnally generalized into a nested LDGM-LDPC codebook, andits use in Gaussian dirty-paper coding has been investigated using the binary case as anexample, mostly regarding the design of the quantization algorithm and the optimization ofthe degree distribution. Simulation results verify that such a codebook can indeed achievetransmission rates fairly close to capacity, thanks to the near-ideal shaping performance.