Resource-constrained Coding for Communication and Computation Applications
Chin-Jen Pang · Deep Blue (University of Michigan) · 2023
Coding for data transmission has been extensively studied since the publication of Shannon’s seminal work in 1948. The research in coding theory has seen significant advances, including the invention of Reed-Solomon codes, convolutional code, LDPC codes, and Polar codes, over the past seven decades. However, many modern applications from disciplines such as wireless communications, machine learning, and quantum information transmission give rise to new challenges for which the coding theory is a framework that can offer novel solutions. Driven by such challenges, in this dissertation, we consider four coding theory problems with constraints on various aspects of the codes. In the first part, we model the problem of crowdsourced labeling, where labels for target items are retrieved through queries from a crowd of workers, as a coding problem where the generator matrices must be sparse. Leveraging prior results for codes with sparse representation, we propose querying schemes with almost optimal number of queries, each of which involving only a constant or a relatively small number of labels, for the reliable and unreliable query response scenarios, respectively. We further consider clustering the items based on two correlated classification criteria. Motivated by the utility of codes with sparse generator matrices in the first problem, in the second part, we study the design of codes with a certain constraint on the weights of all the columns in the generator matrix (GM). In particular, we propose polar-based coding schemes to construct capacity-achieving codes, referred to as polar-DRS and polar-ADRS codes, for BEC and BMS channels respectively. We make significant contributions by demonstrating several properties of the codes including low encoding and decoding complexity, fast decay in error rate, and state-of-the-art upper bounds on the weights of the GM columns. Next, we consider the critical problem of finding channel codes with large minimum distance. The large-minimum distance regime is of both theoretical and practical interests, as the transmission of information in many extreme conditions requires coding schemes that are highly robust with small or moderate rate. We present two novel construction of BCH-like cyclic codes and lower bounds on the maximal size of codes in the targeted regime. We also give asymptotic upper bounds that are stricter than all prior known bounds, which is proved by combining a new approach to bound the maximal eigenvalues of adjacency matrix induced by a Hamming ball with harmonic analysis on the Hamming cube as a group. We then study the one-shot channel coding problem over classical and classical-quantum channels, where the underlying codes are constrained to be group codes. In the achievability part, we introduce a new distribution that incorporates the encoding homomorphism and the underlying channel law. Using a random coding argument, we characterize the performance in terms of a single-letter relative-entropy type quantity. In the converse part, we establish bounds by leveraging a hypothesis testing-based approach.