Anytime Information Theory by Anant Sahai B.S., University of California at Berkeley(1994) S.M., Massachusetts Institute of Technology (1996) Submitted to the Department of Electrical Engineering and Computer Science in partial fulfillment of the requirements for the degree of BARKER Doctor of Philosophy MASSACHUSETTS INSTITUTE OF TECHNOLOGY at the APR 2 4 2001 MASSACHUSETTS INSTITUTE OF TECHNOLOGY LIBRARIES February 2001 @ Massachusetts Institute of Technology 2001. All rights reserved. A u th o r ......... ................. .................. .................... ............. Department of Electrical Engineering and Computer Science November 30, 2000 Certified by ......... ........ .. ....... Sanjoy K. Mitter Professor Thesis Supervisor A ccepted by ...................... ........ ............. ................ Arthur C. Smith Chairman, Department Committee on Graduate Students I Mo p-Tw, 9 -, -.- "I I W."Mm I Anytime Information Theory by Anant Sahai Submitted to the Department of Electrical Engineering and Computer Science on November 30, 2000, in partial fulfillment of the requirements for the degree of Doctor of Philosophy Abstract We study the reliable communication of delay-sensitive bit streams through noisy channels. To bring the issues into sharp focus, we will focus on the specific problem of communicating the values of an unstable real-valued discrete-time Markov random process through a finite- capacity noisy channel so as to have finite average squared error from end-to-end. On the source side, we give a coding theorem for such unstable processes that shows that we can achieve the rate-distortion bound even in the infinite horizon case if we are willing to tolerate bounded delays in encoding and decoding. On the channel side, we define a new parametric notion of capacity called anytime capacity that corresponds to a sense of reliable transmission that is stronger than the traditional Shannon capacity sense but is less demanding than the sense underlying zero-error capacity. We show that anytime capacity exists for memoryless channels without feedback and is connected to standard random coding error exponents. The main result of the thesis is a new source/channel separation theorem that encompasses unstable processes and establishes that the stronger notion of anytime capacity is required to be able to deal with delay-sensitive bit streams. This theorem is then applied in the control systems context to show that anytime capacity is also required to evaluate channels if we intend to use them as part of a feedback link from sensing to actuation. Finally, the theorem is used to shed light on the concept of "quality of service requirements" by examining a toy mathematical example for which we prove the absolute necessity of differentiated service without appealing to human preferences. Thesis Supervisor: Sanjoy K. Mitter Title: Professor 2 Acknowledgments I thank my advisor Professor Sanjoy Mitter for being such an inspiring role model as a researcher. Not only did his ideas and insights help shape this work, but watching his aesthetic sense and intuition in action taught me what good research is truly about. He was also very supportive and patient with the time and twists that this research program has taken. I would also like to thank Professors Robert Gallager, John Tsitsiklis, and Dave Forney for their helpful comments and guidance as members of my committee. I also appreciate the many interactions I had with Professor Vivek Borkar. It was some of our work with him that helped prompt me to revisit the whole idea of capacity and take a fresh look. More recently, the discussions I have had with Professors Venkat Anantharam, Shlomo Shamai, and Emre Telatar have helped me present the ideas in this thesis in a clearer way. I thank all my fellow students at LIDS and MIT who helped make my time here very enlightening. In particular, I valued my close collaborations with my office-mate Sekhar Tatikonda who not only served as a useful sounding board for ideas, but also was ever helpful with references and pointers into the literature. S.R. Venkatesh has also been a friendly source of different perspectives and interesting discussions. The many people I met through the student organizations Sangam and Asha helped broaden my non-academic interests. The administrative staff of LIDS, the EECS department, and MIT have also been a great help in navigating the system. Last but not least, I want to thank my brother, parents, and the Gods for their constant love and support. This research was partially supported by a DOD/ONR fellowship from the U.S. Gov- ernment and by grants ECS-9873451 from NSF and contracts DAAD19-00-1-0466 and DAAL03-92-G-0115 from the Army Research Office. The flexibility and academic freedom made possible by these sponsors are much appreciated. 3 Contents 1 Introduction 11 1.1 "Streaming" and Why We Study Unstable Processes 13 1.1.1 Adjustable Length Source Codes: Tse . . . . . . 14 1.1.2 Interactive Computation: Schulm an . . . . . . 14 1.2 The Simplest Case: Tracking a Simpl andom Walk. 14 1.2.1 Block-codes are not enough . 15 1.2.2 A Source Code with Memory . . 16 1.2.3 Tracking across Noisy Channels . 16 1.3 General Problem Statement . . . . . . . 18 1.4 M ain Results . . . . . . . . . . . . . . . 20 1.4.1 Source Coding . . . . . . . . . . 21 1.4.2 Delay Sensitivity . . . . . . . . . 21 1.4.3 Anytime Channel Coding . . . . 21 1.4.4 Separation Theorem . . . . . . . 22 2 Background 23 2.1 Sources, Channels, and Codes . . . . . . . . . . 23 2.1.1 Sources . . . . . . . . . . . . . . . . . . 23 2.1.2 Source Codes . . . . . . . . . . . . . . . 23 2.1.3 Noisy Channels . . . . . . . . . . . . . . 24 2.1.4 Channel Codes . . . . . . . . . . . . . . 24 2.2 Reliable Communication of Bits . . . . . . . . . 25 2.2.1 "Streaming" and Delay . . . . . . . .. 25 2.2.2 Classical Notions Of Capacity . . . . . . 27 2.2.3 Example Capacities . . . . . . . . . . . 28 2.2.4 Trading off Delay and Errors . . . . . . 30 2.3 Communicating Sources over Channels . . . . . 31 2.3.1 Source Coding . . . . . . . . . . . . . . 31 2.3.2 The Separation Theorem . . . . . . .. 32 2.4 Trying Classical Ideas with Unstable Sources 32 2.4.1 Zero-Error Capacity . . . . . . . . . . . 32 2.4.2 Shannon Classical Capacity . . . . . .. 33 2.4.3 Binary Erasure Channel With Feedback 33 3 Sensitivity Of Source Coding 35 3.1 The Meaning of "Bits" . . . . . . . . . . . . . . . . 3 5 3.2 Error Accumulation . . . . . . . . . . . . . . . . . 3 6 5 3.3 Scalar Markov Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.3.1 Simple Random Walk . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.3.2 General A> 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4 Source Codes for Unstable Processes 45 4.1 Causal Source Codes... . . . . . ............................... 45 4.2 Performance in the limit of large delays . . . . . . . . . . . . . . . . . . . . 48 4.3 False Starts: Why traditional approaches will not work . . . . . . . . . . . . 49 4.3.1 "Whitening" Is Not Enough . . . . . . . . . . . . . . . . . . . . . . . 49 4.3.2 Predictive Error: Chicken and Egg Problem . . . . . . . . . . . . . . 50 4.3.3 Berger's Technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.4 Variable Rate Technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.4.1 The key transformation . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.4.2 The full story of the "dithering" . . . . . . . . . . . . . . . . . . . . 58 4.4.3 Encoding the offsets . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.4.4 Putting the pieces together . . . . . . . . . . . . . . . . . . . . . . . 64 4.5 From Variable Rate To Fixed Rate . . . . . . . . . . . . . . . . . . . . . . . 66 4.5.1 Buffering and fixed-rate framing at the encoder . . . . . . . . . . . 67 4.5.2 The difficulty with the original code: too much variation . . . . . . . 69 4.5.3 A "less variable" variable rate code . . . . . . . . . . . . . . . . . . . 71 4.5.4 Dealing with the remaining variability . . . . . . . . . . . . . . . . . 72 4.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.6.1 More General Sources and Distortions . . . . . . . . . . . . . . . . . 74 4.6.2 Sensitivity of Near Optimal Codes . . . . . . . . . . . . . . . . . . . 75 4.6.3 The Fixed Rate Case . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5 Reliable Communication of "Weak Bits" 77 5.1 Anytime Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.2 Anytime Capacity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.3 Lower-Bounding Anytime Capacity without Feedback . . . . . . . . . . . . 81 5.3.1 Binary Erasure Channel . . . . . . . . . . . . . . . . . . . . . . . . . 82 5.3.2 Additive White Gaussian Noise Channels . . . . . . . . . . . . . . . 86 5.3.3 The General Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5.4 From Random to Deterministic Codes . . . . . . . . . . . . . . . . . . . . . 92 5.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 5.5.1 Better Estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.5.2 Practical Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.5.3 Incremental Updates and Interconnections . . . . . . . . . . . . . . . 98 5.5.4 Splitting A Channel . . . . . . . . . . . . . . . . . . . . . . . . . . 98 6 An Information Transmission Theorem 99 6.1 Tracking the Simple Random Walk over Noisy Channels . . . . . . . . . . . 99 6.2 The Direct Part . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 6.3 The Converse Part: Simple Case . . . . . . . . . . . . . . . . . . . . . . . . 102 6.3.1 The Encoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 6.3.2 Real Numbers As Strings: Analog to Digital Conversion . . . . . . . 105 6.3.3 The Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 6 6.4 The Converse: More General Driving Noise Distributions 110 6.4.1 "Robust" Joint Source/Channel Encoders . . . . . . . . . . . . . . .111 6.4.2 No Robustness: Exact Simulation . . . . . . . . . . . . . . . . . . .111 6.5 Converse For Performance: Not There Yet . . . . . . . . . . . . . . . . . . . 113 6.5.1 Counterexample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 6.5.2 What We Do Know About Performance . . . . . . . . . . . . . . . . 115 6.6 D iscussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 6.6.1 "Recursive" Formulations of The Direct Part . . . . . . . . . . . . . 115 6.6.2 A Path To A Tighter Converse . . . . . . . . . . . . . . . . . . . . . 115 7 Control and Feedback 117 7.1 Feedback as Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 7.1.1 Control With A Communication Constraint . . . . . . . . . . . . . . 117 7.1.2 What Stability Means . . . . . . . . . . . . . . . . . . . . . . . . . . 119 7.1.3 Equivalence with Estimation . . . . . . . . . . . . . . . . . . . . . . 121 7.1.4 Information Transmission Theorem For Control . . . . . . . . . . . . 125 7.2 Specific Channels With Feedback . . . . . . . . . . . . . . . . . . . . . . . . 126 7.2.1 Erasure Channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 7.2.2 Additive Noise Channels . . . . . . . . . . . . . . . . . . . . . . . . . 129 7.3 D iscussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 8 "Quality of Service" 135 8.1 A Simple Vector Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 8.1.1 Transform Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 8.1.2 Fundamental Requirements . . . . . . . . . . . . . . . . . . . . . . . 138 8.2 Treating All Bits Alike . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 8.3 Differentiated Service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 8.3.1 A Prioritized Channel Code . . . . . . . . . . . . . . . . . . . . . . . 142 8.3.2 Analyzing This Channel Code . . . . . . . . . . . . . . . . . . . . . . 143 8.4 D iscussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 9 Conclusion and Future Work 147 9.1 Source Encoders Without Memory . . . . . . . . . . . . . . . . . . . . . . . 148 9.2 Sequential Refinement For Source Codes . . . . . . . . . . . . . . . . . . . . 148 9.3 Distributed Systems and Multiterminal Information Theory . . . . . . . . . 149 A Streaming Definitions 151 A.1 Streams and Transition Maps . . . . . . . . . . . . . . . . . . . . . . . . . . 151 A.1.1 Pairings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 A.1.2 Stream Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 A.2 Random Sources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 A.2.1 Markov Sources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 A.3 Source Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 A.4 Noisy Channels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 A.4.1 Example Channels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 A.5 Channel Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 A.5.1 Block Channel Codes . . . . . . . . . . . . . . . . . . . . . . . . . . 155 A.5.2 Codes with access to feedback . . . . . . . . . . . . . . . . . . . . . . 156 7 B Convergence To Means 157 B.1 Chebychev inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 B.2 Distributions with Heavy Tails . . . . . . . . . . . . . . . . . .... . . . . . 158 C "Simulating" Random Variables 165 C.1 Definitions and Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 C .2 R esults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 8 List of Figures 1-1 The estimation problem across a noisy channel . . . . . . . . . . . . . . . . 19 2-1 Coding for the erasure channel with noiseless feedback . . . . . . . . . . . . 29 2-2 Simulation of distortion through time for a source code cascaded with a block-length 12 classical channel code. . . . . . . . . . . . . . . . . . . . . . 34 4-1 Causal predictive source code for unstable Markov process . . . . . . . . . . 46 4-2 Berger's strategy achieving R(D) for Wiener processes. . . . . . . . . . . . . 52 4-3 The two-part superblock source encoding strategy for Markov sources and how it is decoded. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4-4 The "block of blocks" approach with a long superblock consisting of M inner blocks of N source samples each. The transformed inner blocks Ykul+i all look identically distributed and independent of each other so that they are suitable for lossy compression via vector quantization. . . . . . . . . . . . . 56 4-5 How the dithered quantization feeds into the variable length lossless code 60 5-1 Anytime encoders and decoders . . . . . . . . . . . . . . . . . . . . . . . . . 78 5-2 A general channel encoder viewed as a tree. . . . . . . . . . . . . . . . . . . 82 6-1 Using a source simulator to constructively prove the converse of the Infor- mation Transmission Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 103 6-2 The Cantor set of possible binary strings when viewed as real numbers on the unit interval using Ei = 0.3. Ei = 0 would correspond to the entire interval106 7-1 The control problem over a noisy channel . . . . . . . . . . . . . . . . . . . 118 7-2 The estimation problem over a noisy channel with access to noiseless feedback120 7-3 Block diagram showing how to construct an estimator from a control system 122 7-4 Block diagram showing how to construct a control system from an estimator 124 7-5 The evolution of the uncertain interval on the erasure channel with noiseless feedback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 8-1 The vector estimation problem over a noisy channel with noiseless feedback and enforced layering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 8-2 Anytime capacity for the erasure channel with e = 0.27 for encoders having access to noiseless feedback . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 8-3 Forcing all the bitstreams to get the same treatment for reliable transmission 140 8-4 Allowing the reliable transmission layer to discriminate between bitstreams 141 8-5 The strict priority queuing strategy for discrimination between bitstreams . 142 9 0-