| dc.description.abstract | The setting of the transmission of information over noisy, binary-input, memoryless channels is today well-understood, owing to the work of several information theorists, beginning with Claude Shannon. It is known that it is impossible to transmit information reliably over such channels at rates larger than the fundamental limit that is the capacity of the channel. Moreover, progress made in the last three decades has led to the construction of explicit, practically-implementable coding schemes that achieve rates arbitrarily close to the capacities of such channels. Now, suppose that the inputs of the memoryless channel are required to obey an additional constraint, which stems from physical limitations of the medium over which transmission or storage occurs. What then can be said about the fundamental limits of information transmission over such input-constrained channels, with and without decoder feedback? Is it possible to design good constrained coding schemes of high rate over these channels? If the channel introduces errors adversarially, instead of randomly, how much information can then be sent through, reliably? This dissertation explores answers to such questions.
We first derive computable lower bounds on the capacities of runlength limited (RLL) input-constrained memoryless channels, such as the binary symmetric and binary erasure channels (BSC and BEC, respectively), by considering random Markov input distributions that respect the constraint. These bounds unify well-known approaches in the literature, and extend them to the so-called input-driven finite-state channels (FSCs). For the special case of the BEC with a no-consecutive-ones input constraint, we discuss an iterative stochastic approximation algorithm that numerically computes achievable rates that are very close to known upper bounds on the capacity of the channel. We also derive improved analytical lower bounds, for this specific channel.
Next, we consider the special case of the $(d,\infty)$-runlength limited (RLL) constraint, which mandates that any pair of successive $1$s be separated by at least $d$ $0$s. We design explicit coding schemes, derived from Reed-Muller (RM) codes, for transmission over binary-input memoryless symmetric (BMS) channels, whose inputs respect the constraint. In particular, we provide constructions using constrained subcodes of RM codes, analytically compute their rates, and derive converse upper bounds on the rates of the largest constrained subcodes of RM codes. We also provide a Fourier-theoretic perspective on the problem of counting arbitrarily-constrained codewords in general linear codes, which can help estimate the rates achievable by using linear codes over input-constrained BMS channels. We illustrate the utility of our method using the somewhat surprising observation that for different constraints of interest, the Fourier transforms of the indicator functions of the constraints are efficiently computable.
We then shift our attention to the setting of the $(d,\infty)$-RLL input-constrained BEC in the presence of noiseless feedback from the decoder. We demonstrate a simple, labelling-based, zero-error feedback coding scheme, which we prove to be feedback capacity-achieving, and, as a by-product, obtain an explicit characterization of the feedback capacity. The feedback capacity thus computed is an upper bound on the non-feedback capacity of such a channel. Numerical comparisons made with upper bounds on the non-feedback capacity then reveal that that feedback increases the capacity of such a channel, at least for select values of $d$.
Finally, we consider the setting of an input-constrained adversarial channel, where there is an upper bound on the number of bit-flip errors that the channel can introduce, and we seek to design codes that can be recovered with zero error. We present numerical upper bounds on the sizes of the largest such codes, via a version of Delsarte’s linear program. We observe that for different constraints of interest, our upper bounds beat the “generalized sphere packing bounds” that are the state-of-the-art. | en_US |
