Applications of Coding Theory to Massive Multiple Access and Big Data Problems

The broad theme of this dissertation is design of schemes that admit iterative algorithms with low computational complexity to some new problems arising in massive multiple access and big data. Although bipartite Tanner graphs and low-complexity iterative algorithms such as peeling and message passing decoders are very popular in the channel coding literature they are not as widely used in the respective areas of study and this dissertation serves as an important step in that direction to bridge that gap. The contributions of this dissertation can be categorized into the following three parts. In the first part of this dissertation, a timely and interesting multiple access problem for a massive number of uncoordinated devices is considered wherein the base station is interested only in recovering the list of messages without regard to the identity of the respective sources. A coding scheme with polynomial encoding and decoding complexities is proposed for this problem, the two main features of which are (i) design of a close-to-optimal coding scheme for the T-user Gaussian multiple access channel and (ii) successive interference cancellation decoder. The proposed coding scheme not only improves on the performance of the previously best known coding scheme by ≈ 13 dB but is only ≈ 6 dB away from the random Gaussian coding information rate. In the second part construction-D lattices are constructed where the underlying linear codes are nested binary spatially-coupled low-density parity-check codes (SCLDPC) codes with uniform left and right degrees. It is shown that the proposed lattices achieve the Poltyrev limit under multistage belief propagation decoding. Leveraging this result lattice codes constructed from these lattices are applied to the three user symmetric interference channel. For channel gains within 0.39 dB from the very strong interference regime, the proposed lattice coding scheme with the iterative belief propagation decoder, for target error rates of ≈ 10^-5, is only 2:6 dB away the Shannon limit. The third part focuses on support recovery in compressed sensing and the nonadaptive group testing (GT) problems. Prior to this work, sensing schemes based on left-regular sparse bipartite graphs and iterative recovery algorithms based on peeling decoder were proposed for the above problems. These schemes require O(K logN) and Ω(K logK logN) measurements respectively to recover the sparse signal with high probability (w.h.p), where N, K denote the dimension and sparsity of the signal respectively (K (double backward arrow) N). Also the number of measurements required to recover at least (1 - €) fraction of defective items w.h.p (approximate GT) is shown to be cv€_K logN/K. In this dissertation, instead of the left-regular bipartite graphs, left-and- right regular bipartite graph based sensing schemes are analyzed. It is shown that this design strategy enables to achieve superior and sharper results. For the support recovery problem, the number of measurements is reduced to the optimal lower bound of Ω (K log N/K). Similarly for the approximate GT, proposed scheme only requires c€_K log N/ K measurements. For the probabilistic GT, proposed scheme requires (K logK log vN/ K) measurements which is only log K factor away from the best known lower bound of Ω (K log N/ K). Apart from the asymptotic regime, the proposed schemes also demonstrate significant improvement in the required number of measurements for finite values of K, N