Deep code: representation and learning algorithms for neural networks & their applications to communication codes
Ashok Vardhan Makkuva
Abstract
Codes are the backbone of modern information age.Codes, composed of encoder and decoder pairs, are the basic mathematical objects that enable reliable communication.Landmark codes include convolutional, Reed-Muller, turbo, LDPC, and polar: each is linear and represents a mathematical breakthrough.Their impact on humanity is huge; each of these codes has been used in global communication standards over the past six decades.On the other hand, designing codes is a challenging task, mostly driven by human ingenuity.Befittingly, historically, the progress in discovery of codes has been sporadic.In this thesis, we present a new paradigm to invent codes via harnessing tools from deep-learning.Our major result is the invention of KO codes, a computationally efficient family of deep-learning driven codes that outperform the state-of-the-art RM and polar codes, in the challenging short-to-medium block length regime.The key technical innovation behind KO codes is the design of a novel family of neural architectures inspired by the computation tree of the Kronecker Operation (KO) central to RM and polar codes.These architectures pave the way for discovery of a much richer class of hitherto unexplored non-linear codes.This design technique can be viewed as an instantiation of the classical neural augmentation principle.In the process, we also study a popular neural network model called Mixture-of-Experts (MoE) that realizes this principle.We provide the first set of consistent and efficient algorithms with global learning guarantees for learning the parameters in a MoE which has been an open problem for more than two decades.B.1 Comparison of SGD on our losses (L 4 , L log ) vs. ℓ 2 and the EM algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . .106 C.2 KO code achieves a significant gain over the Polar(64, 7) code in BLER when trained on AWGN channel.KO decoder also matches the optimal MAP decoder. . . . . . . . . . . . .108 xii C.6 KO(6, 1) code.Left: KO(6, 1) code achieves significant gain over RM(6, 1) code (with Dumer) when trained on AWGN channel.Right: Under the optimal MAP decoding, KO(6, 1) and RM(6, 1) codes achieve the same performance.Error rates for a random Gaussian codebook are also plotted as a baseline. . . . . . . . . . . . . . . . . . . . . . . . . . . .120 C.1 Plotkin trees for the Polar(64, 7) encoder and our neural KO encoder counterpart.Both codes have dimension k = 7 and blocklength n = 64. . . . . . . . . . . . . . . . . . . . . .121 C.3 The same KO(8,2) encoder and decoder as those used in Figure 4.4 achieve a significant gain (without any retraining or fine-tuning) when list decoding is used together with the KO decoder.The magnitude of the gain is comparable to the gain achieved by the same list decoding technique on the successive cancellation decoder of the RM(8,2) code.We used the list decoding from [1] but without the permutation technique. . . . . . . . . . . . . . . . . . . . . . . . . . . . .122 C.4 Plotkin trees for RM(8,2) and KO(8,2) encoders.Leaves are highlighted in green.Both codes have dimension k = 37 and blocklength n = 256. . . . . . . . . . . . . . . . . . . . . .123 C.5 Plotkin trees for the RM(8, 2) and KO(8, 2) decoders.Red arrows indicate the bit decoding order. . . . . . . .