Network Information Theory

Contents......Page 8
Preface......Page 18
Organization of the Book......Page 19
Use of the Book in Courses......Page 21
Dependence Graphs......Page 22
Acknowledgments......Page 24
Probability and Random Variables......Page 26
Common Functions......Page 28
Order Notation......Page 29
1.1 NETWORK INFORMATION FLOW PROBLEM......Page 30
1.3 POINT-TO-POINT INFORMATION THEORY......Page 31
1.4 NETWORK INFORMATION THEORY......Page 33
1.4.1 Multiple Sources and Destinations......Page 34
1.4.2 Wireless Networks......Page 37
1.4.3 Interactive Communication......Page 41
1.4.7 Toward a Unified Network Information Theory......Page 43
PART I PRELIMINARIES......Page 44
2.1 ENTROPY......Page 46
2.2 DIFFERENTIAL ENTROPY......Page 48
2.3 MUTUAL INFORMATION......Page 51
2.4 TYPICAL SEQUENCES......Page 54
2.5 JOINTLY TYPICAL SEQUENCES......Page 56
2.5.1 Joint Typicality for a Triple of Random Variables......Page 58
SUMMARY......Page 59
BIBLIOGRAPHIC NOTES......Page 60
PROBLEMS......Page 61
APPENDIX 2A PROOF OF THE CONDITIONAL TYPICALITY LEMMA......Page 66
3.1 CHANNEL CODING......Page 67
3.1.1 Channel Coding Theorem......Page 68
3.1.2 Proof of Achievability......Page 71
3.1.3 Achievability Using Linear Codes......Page 72
3.1.4 Proof of the Converse......Page 73
3.2 PACKING LEMMA......Page 74
3.3 CHANNEL CODING WITH INPUT COST......Page 76
3.4 GAUSSIAN CHANNEL......Page 78
3.4.1 Capacity of the Gaussian Channel......Page 79
3.4.2 Minimum Energy Per Bit......Page 80
3.4.3 Gaussian Product Channel......Page 81
3.5 LOSSLESS SOURCE CODING......Page 83
3.5.2 Proof of Achievability......Page 84
3.6 LOSSY SOURCE CODING......Page 85
3.6.1 Lossy Source Coding Theorem......Page 86
3.6.3 Proof of Achievability......Page 88
3.6.4 Lossless Source Coding Revisited......Page 90
3.7 COVERING LEMMA......Page 91
3.8 QUADRATIC GAUSSIAN SOURCE CODING......Page 93
3.9 JOINT SOURCE–CHANNEL CODING......Page 95
SUMMARY......Page 97
BIBLIOGRAPHIC NOTES......Page 98
PROBLEMS......Page 100
APPENDIX 3A PROOF OF LEMMA 3.2......Page 106
PART II SINGLE-HOP NETWORKS......Page 108
4.1 DISCRETE MEMORYLESS MULTIPLE ACCESS CHANNEL......Page 110
4.2 SIMPLE BOUNDS ON THE CAPACITY REGION......Page 111
4.3* MULTILETTER CHARACTERIZATION OF THE CAPACITY REGION......Page 113
4.4 TIME SHARING......Page 114
4.5 SINGLE-LETTER CHARACTERIZATION OF THE CAPACITY REGION......Page 115
4.5.1 Proof of Achievability......Page 116
4.5.2 Proof of the Converse......Page 118
4.6 GAUSSIAN MULTIPLE ACCESS CHANNEL......Page 122
4.6.1 Capacity Region of the Gaussian MAC......Page 123
4.6.2 Comparison with Point-to-Point Coding Schemes......Page 124
SUMMARY......Page 127
PROBLEMS......Page 128
APPENDIX 4A CARDINALITY BOUND ON Q......Page 132
5.1 DISCRETE MEMORYLESS BROADCAST CHANNEL......Page 133
5.2 SIMPLE BOUNDS ON THE CAPACITY REGION......Page 135
5.3 SUPERPOSITION CODING INNER BOUND......Page 136
5.3.1 Proof of the Superposition Coding Inner Bound......Page 138
5.4 DEGRADED DM-BC......Page 141
5.4.1 Proof of the Converse......Page 142
5.4.2 Capacity Region of the BS-BC......Page 144
5.5 GAUSSIAN BROADCAST CHANNEL......Page 146
5.5.1 Capacity Region of the Gaussian BC......Page 147
5.5.2 Proof of the Converse......Page 148
5.6 LESS NOISY AND MORE CAPABLE BROADCAST CHANNELS......Page 150
5.6.1 Proof of the Converse for the More Capable DM-BC......Page 151
5.7 EXTENSIONS......Page 152
SUMMARY......Page 153
PROBLEMS......Page 154
CHAPTER 6 Interference Channels......Page 160
6.1 DISCRETE MEMORYLESS INTERFERENCE CHANNEL......Page 161
6.2 SIMPLE CODING SCHEMES......Page 162
6.3 STRONG INTERFERENCE......Page 164
6.4 GAUSSIAN INTERFERENCE CHANNEL......Page 166
6.4.1 Inner Bounds......Page 167
6.4.2 Capacity Region of the Gaussian IC with Strong Interference......Page 168
6.4.3 Sum-Capacity of the Gaussian IC with Weak Interference......Page 170
6.5 HAN–KOBAYASHI INNER BOUND......Page 172
6.5.1 Proof of the Han–Kobayashi Inner Bound......Page 173
6.6 INJECTIVE DETERMINISTIC IC......Page 174
6.7.1 Injective Semideterministic IC......Page 177
6.7.2 Half-Bit Theorem for the Gaussian IC......Page 179
6.7.3 Symmetric Degrees of Freedom......Page 180
6.8 DETERMINISTIC APPROXIMATION OF THE GAUSSIAN IC......Page 182
6.8.1* QED-IC Approximation of the Gaussian IC......Page 185
6.9 EXTENSIONS TO MORE THAN TWO USER PAIRS......Page 186
SUMMARY......Page 187
BIBLIOGRAPHIC NOTES......Page 188
PROBLEMS......Page 189
APPENDIX 6A PROOF OF LEMMA 6.2......Page 193
APPENDIX 6B PROOF OF PROPOSITION 6.1......Page 194
CHAPTER 7 Channels with State......Page 197
7.2 COMPOUND CHANNEL......Page 198
7.3* ARBITRARILY VARYING CHANNEL......Page 201
7.4.1 State Information Available at Both the Encoder and the Decoder......Page 202
7.4.2 Extensions to the DM-MAC with State......Page 203
7.5 CAUSAL STATE INFORMATION AVAILABLE AT THE ENCODER......Page 204
7.6 NONCAUSAL STATE INFORMATION AVAILABLE AT THE ENCODER......Page 207
7.6.1 Proof of Achievability......Page 209
7.6.3 Comparison with the Causal Case......Page 211
7.6.4 Extensions to the Degraded DM-BC with State......Page 212
7.7 WRITING ON DIRTY PAPER......Page 213
7.7.1 Writing on Dirty Paper for the Gaussian MAC......Page 216
7.7.2 Writing on Dirty Paper for the Gaussian BC......Page 217
7.8 CODED STATE INFORMATION......Page 218
BIBLIOGRAPHIC NOTES......Page 220
PROBLEMS......Page 221
CHAPTER 8 General Broadcast Channels......Page 226
8.1 DM-BC WITH DEGRADED MESSAGE SETS......Page 227
8.2 THREE-RECEIVER MULTILEVEL DM-BC......Page 228
8.2.1 Proof of Achievability......Page 229
8.2.2 Multilevel Product DM-BC......Page 232
8.3 MARTON’S INNER BOUND......Page 234
8.3.1 Semideterministic DM-BC......Page 235
8.3.2 Achievability of Marton’s Inner Bound......Page 236
8.3.3 Relationship to Gelfand–Pinsker Coding......Page 239
8.4 MARTON’S INNER BOUND WITH COMMON MESSAGE......Page 241
8.5.1 A BSC and A BEC......Page 243
8.5.2 Binary Skew-Symmetric Broadcast Channel......Page 244
8.5.3 Nair–El Gamal Outer Bound......Page 245
8.6 INNER BOUNDS FOR MORE THAN TWO RECEIVERS......Page 246
SUMMARY......Page 248
BIBLIOGRAPHIC NOTES......Page 249
PROBLEMS......Page 250
APPENDIX 8A PROOF OF THE MUTUAL COVERING LEMMA......Page 252
APPENDIX 8B PROOF OF THE NAIR–EL GAMAL OUTER BOUND......Page 254
9.1 GAUSSIAN VECTOR POINT-TO-POINT CHANNEL......Page 256
9.1.2 Reciprocity......Page 259
9.1.3 Alternative Characterization of KX*......Page 260
9.2 GAUSSIAN VECTOR MULTIPLE ACCESS CHANNEL......Page 261
9.3 GAUSSIAN VECTOR BROADCAST CHANNEL......Page 263
9.4 GAUSSIAN PRODUCT BROADCAST CHANNEL......Page 264
9.5 VECTOR WRITING ON DIRTY PAPER......Page 270
9.6 GAUSSIAN VECTOR BC WITH PRIVATE MESSAGES......Page 271
9.6.1 Proof of Achievability......Page 272
9.6.2 Gaussian Vector BC–MAC Duality......Page 273
9.6.3 Proof of the Converse......Page 276
9.6.4 GV-BC with More than Two Receivers......Page 281
BIBLIOGRAPHIC NOTES......Page 282
PROBLEMS......Page 283
APPENDIX 9A PROOF OF THE BC–MAC DUALITY LEMMA......Page 284
APPENDIX 9B UNIQUENESS OF THE SUPPORTING LINE......Page 285
10.1 DISTRIBUTED LOSSLESS SOURCE CODING FOR A 2-DMS......Page 287
10.2 INNER AND OUTER BOUNDS ON THE OPTIMAL RATE REGION......Page 288
10.3 SLEPIAN–WOLF THEOREM......Page 289
10.3.1 Lossless Source Coding via Random Binning......Page 290
10.3.2 Achievability Proof of the Slepian–Wolf Theorem......Page 292
10.4 LOSSLESS SOURCE CODING WITH A HELPER......Page 293
10.4.1 Proof of Achievability......Page 295
10.4.2 Proof of the Converse......Page 296
10.5 EXTENSIONS TO MORE THAN TWO SOURCES......Page 298
BIBLIOGRAPHIC NOTES......Page 299
PROBLEMS......Page 300
CHAPTER 11 Lossy Compression with Side Information......Page 303
11.2 CAUSAL SIDE INFORMATION AVAILABLE AT THE DECODER......Page 304
11.2.1 Proof of Achievability......Page 306
11.2.2 Proof of the Converse......Page 307
11.2.3 Lossless Source Coding with Causal Side Information......Page 308
11.3 NONCAUSAL SIDE INFORMATION AVAILABLE AT THE DECODER......Page 309
11.3.1 Proof of Achievability......Page 311
11.3.3 Source–Channel Coding Dualities......Page 314
11.4 SOURCE CODING WHEN SIDE INFORMATION MAY BE ABSENT......Page 315
BIBLIOGRAPHIC NOTES......Page 317
PROBLEMS......Page 318
APPENDIX 11A PROOF OF LEMMA 11.1......Page 321
CHAPTER 12 Distributed Lossy Compression......Page 323
12.1 BERGER–TUNG INNER BOUND......Page 324
12.1.1 Markov and Mutual Packing Lemmas......Page 325
12.1.2 Proof of the Berger–Tung Inner Bound......Page 326
12.2 BERGER–TUNG OUTER BOUND......Page 328
12.3 QUADRATIC GAUSSIAN DISTRIBUTED SOURCE CODING......Page 329
12.3.1 Proof of Achievability......Page 330
12.3.2 Proof of the Converse......Page 333
12.4 QUADRATIC GAUSSIAN CEO PROBLEM......Page 337
12.4.1 Proof of the Converse......Page 339
12.5* SUBOPTIMALITY OF BERGER–TUNG CODING......Page 341
BIBLIOGRAPHIC NOTES......Page 342
PROBLEMS......Page 343
APPENDIX 12A PROOF OF THE MARKOV LEMMA......Page 344
APPENDIX 12C PROOF OF LEMMA 12.4......Page 346
APPENDIX 12D PROOF OF LEMMA 12.6......Page 347
CHAPTER 13 Multiple Description Coding......Page 349
13.1 MULTIPLE DESCRIPTION CODING FOR A DMS......Page 350
13.2 SIMPLE SPECIAL CASES......Page 351
13.3 EL GAMAL–COVER INNER BOUND......Page 352
13.3.1 Proof of the El Gamal–Cover Inner Bound......Page 354
13.4.1 Proof of Achievability......Page 356
13.4.2 Proof of the Converse......Page 357
13.5 SUCCESSIVE REFINEMENT......Page 359
13.5.1 Successively Refinable Sources......Page 360
13.6 ZHANG–BERGER INNER BOUND......Page 361
BIBLIOGRAPHIC NOTES......Page 363
PROBLEMS......Page 364
14.1 LOSSLESS COMMUNICATION OF A 2-DMS OVER A DM-MAC......Page 365
14.1.1 A Joint Source–Channel Coding Scheme......Page 368
14.1.2 Proof of Theorem 14.1......Page 369
14.1.3 Common Part of a 2-DMS......Page 371
14.1.4 Three-Index Separate Source and Channel Coding Scheme......Page 372
14.1.5 A Joint Source–Channel Coding Scheme with Common Part......Page 373
14.2.1 Gray–Wyner System......Page 374
14.2.2 Common Information......Page 376
14.2.3 A Separate Source–Channel Coding Scheme......Page 377
14.2.4 A Joint Source–Channel Coding Scheme......Page 378
14.2.5 Proof of Theorem 14.4......Page 379
14.3 A GENERAL SINGLE-HOP NETWORK......Page 380
14.3.1 Separate Source and Channel Coding Scheme......Page 381
14.3.2* A Hybrid Source–Channel Coding Scheme......Page 382
BIBLIOGRAPHIC NOTES......Page 384
PROBLEMS......Page 385
APPENDIX 14A PROOF OF LEMMA 14.1......Page 387
PART III MULTIHOP NETWORKS......Page 390
CHAPTER 15 Graphical Networks......Page 392
15.1 GRAPHICAL MULTICAST NETWORK......Page 393
15.2 CAPACITY OF GRAPHICAL UNICAST NETWORK......Page 395
15.3 CAPACITY OF GRAPHICAL MULTICAST NETWORK......Page 397
15.3.1 Linear Network Coding......Page 398
15.3.2 Achievability Proof of the Network Coding Theorem......Page 401
15.4 GRAPHICAL MULTIMESSAGE NETWORK......Page 402
15.4.1 Graphical Multimessage Multicast Network......Page 403
15.4.2 Graphical Multiple-Unicast Network......Page 404
BIBLIOGRAPHIC NOTES......Page 406
PROBLEMS......Page 408
APPENDIX 15A PROOF OF LEMMA 15.1......Page 410
CHAPTER 16 Relay Channels......Page 411
16.1 DISCRETE MEMORYLESS RELAY CHANNEL......Page 412
16.2 CUTSET UPPER BOUND ON THE CAPACITY......Page 413
16.4 DECODE–FORWARD LOWER BOUND......Page 415
16.4.1 Multihop Lower Bound......Page 416
16.4.2 Coherent Multihop Lower Bound......Page 418
16.4.3 Decode–Forward Lower Bound......Page 419
16.4.4 Proof via Backward Decoding......Page 420
16.4.5 Proof via Binning......Page 422
16.5.1 Upper and Lower Bounds on the Capacity of the Gaussian RC......Page 424
16.6 PARTIAL DECODE–FORWARD LOWER BOUND......Page 425
16.6.1 Semideterministic DM-RC......Page 426
16.6.3 SFD Gaussian Relay Channel......Page 427
16.7 COMPRESS–FORWARD LOWER BOUND......Page 428
16.7.1 Proof of the Compress–Forward Lower Bound......Page 429
16.7.2 Compress–Forward for the Gaussian RC......Page 431
16.7.3 Relay Channel with Orthogonal Receiver Components......Page 432
16.8 RFD GAUSSIAN RELAY CHANNEL......Page 435
16.8.1 Linear Relaying for RFD Gaussian RC......Page 436
16.8.3* Linear Relaying Capacity of the RFD Gaussian RC......Page 437
16.9 LOOKAHEAD RELAY CHANNELS......Page 440
16.9.1 Noncausal Relay Channels......Page 441
16.9.2 Causal Relay Channels......Page 443
SUMMARY......Page 445
BIBLIOGRAPHIC NOTES......Page 447
PROBLEMS......Page 448
APPENDIX 16A CUTSET BOUND FOR THE GAUSSIAN RC......Page 452
APPENDIX 16B PARTIAL DECODE–FORWARD FOR THE GAUSSIAN RC......Page 453
APPENDIX 16C EQUIVALENT COMPRESS–FORWARD LOWER BOUND......Page 454
CHAPTER 17 Interactive Channel Coding......Page 456
17.1.1 Schalkwijk–Kailath Coding Scheme for the Gaussian Channel......Page 457
17.1.2* Horstein’s Coding Scheme for the BSC......Page 460
17.1.3 Block Feedback Coding Scheme for the BSC......Page 462
17.2 MULTIPLE ACCESS CHANNEL WITH FEEDBACK......Page 463
17.2.1 Cover–Leung Inner Bound......Page 464
17.2.2 Proof of the Cover–Leung Inner Bound......Page 465
17.2.3 Gaussian MAC with Feedback......Page 467
17.2.4 Achievability Proof of Theorem 17.2......Page 468
17.3 BROADCAST CHANNEL WITH FEEDBACK......Page 472
17.4 RELAY CHANNEL WITH FEEDBACK......Page 473
17.5 TWO-WAY CHANNEL......Page 474
17.5.1 Simple Inner and Outer Bounds......Page 475
17.5.2 Dependence Balance Bound......Page 477
17.6 DIRECTED INFORMATION......Page 478
17.6.1 Multiletter Characterization of the DM-TWC Capacity Region......Page 479
17.6.3 Proof of Achievability......Page 480
SUMMARY......Page 482
BIBLIOGRAPHIC NOTES......Page 483
PROBLEMS......Page 484
APPENDIX 17A PROOF OF LEMMA 17.1......Page 487
18.1 DISCRETE MEMORYLESS MULTICAST NETWORK......Page 488
18.2.1 Sliding Window Decoding for the DM-RC......Page 491
18.2.2 Proof of the Network Decode–Forward Lower Bound......Page 494
18.3 NOISY NETWORK CODING......Page 495
18.3.1 Deterministic Multicast Network......Page 496
18.3.2 Wireless Erasure Multicast Network......Page 498
18.3.3 Noisy Network Coding for the DM-RC......Page 499
18.3.4 Proof of the Noisy Network Coding Lower Bound......Page 502
18.4 DISCRETE MEMORYLESS MULTIMESSAGE NETWORK......Page 506
18.4.1 Noisy Network Coding for the Multimessage Multicast Network......Page 507
18.4.2* Noisy Network Coding for General Multimessage Networks......Page 508
BIBLIOGRAPHIC NOTES......Page 510
PROBLEMS......Page 511
CHAPTER 19 Gaussian Networks......Page 513
19.1 GAUSSIAN MULTIMESSAGE NETWORK......Page 514
19.1.1 Noisy Network Coding Lower Bound......Page 515
19.1.2 Gaussian Two-Way Relay Channel......Page 516
19.1.3 Multimessage Multicast Capacity Region within a Constant Gap......Page 518
19.2 CAPACITY SCALING LAWS......Page 519
19.3 GUPTA–KUMAR RANDOM NETWORK......Page 521
19.3.1 Proof of the Lower Bound......Page 522
19.3.2 Proof of the Upper Bound......Page 525
BIBLIOGRAPHIC NOTES......Page 528
PROBLEMS......Page 529
APPENDIX 19A PROOF OF LEMMA 19.1......Page 530
APPENDIX 19B PROOF OF LEMMA 19.2......Page 531
20.1 DISTRIBUTED LOSSLESS SOURCE–NETWORK CODING......Page 534
20.2 MULTIPLE DESCRIPTION NETWORK CODING......Page 537
20.2.1 Cascade Multiple Description Network......Page 538
20.2.2 Triangular Multiple Description Network......Page 539
20.3 INTERACTIVE SOURCE CODING......Page 541
20.3.1 Two-Way Lossless Source Coding......Page 542
20.3.2 CFO Problem......Page 543
20.3.3 Two-Way Lossy Source Coding......Page 544
SUMMARY......Page 548
PROBLEMS......Page 549
APPENDIX 20A PROOF OF LEMMA 20.1......Page 554
PART IV EXTENSIONS......Page 556
CHAPTER 21 Communication for Computing......Page 558
21.1 CODING FOR COMPUTING WITH SIDE INFORMATION......Page 559
21.1.1 Lossless Coding for Computing......Page 560
21.2 DISTRIBUTED CODING FOR COMPUTING......Page 562
21.2.1 μ-Sum Problem......Page 563
21.2.2 Distributed Lossless Computing......Page 565
21.3 INTERACTIVE CODING FOR COMPUTING......Page 566
21.3.1 Interactive Coding for Lossless Computing......Page 567
21.4 CASCADE CODING FOR COMPUTING......Page 568
21.5 DISTRIBUTED LOSSY AVERAGING......Page 571
21.6 COMPUTING OVER A MAC......Page 573
SUMMARY......Page 574
BIBLIOGRAPHIC NOTES......Page 575
PROBLEMS......Page 576
CHAPTER 22 Information Theoretic Secrecy......Page 578
22.1 WIRETAP CHANNEL......Page 579
22.1.1 Achievability Proof of Theorem 22.1......Page 582
22.1.2 Converse Proof of Theorem 22.1......Page 584
22.1.3 Extensions......Page 585
22.2 CONFIDENTIAL COMMUNICATION VIA SHARED KEY......Page 586
22.3 SECRET KEY AGREEMENT: SOURCE MODEL......Page 588
22.3.1 Secret Key Agreement from One-Way Communication......Page 589
22.3.2 Achievability Proof of Theorem 22.4......Page 591
22.3.3 Lower Bound on the Secret Key Capacity......Page 593
22.3.4 Upper Bound on the Secret Key Capacity......Page 595
22.3.5 Extensions to Multiple Nodes......Page 598
22.4.1 Maurer’s Example......Page 601
22.4.2 Lower and Upper Bounds on the Secret Key Capacity......Page 603
SUMMARY......Page 604
BIBLIOGRAPHIC NOTES......Page 605
PROBLEMS......Page 607
APPENDIX 22A PROOF OF LEMMA 22.1......Page 608
APPENDIX 22B PROOF OF LEMMA 22.2......Page 609
APPENDIX 22C PROOF OF LEMMA 22.3......Page 610
23.1 GAUSSIAN FADING CHANNEL......Page 612
23.2 CODING UNDER FAST FADING......Page 613
23.3.1 Channel Gain Available Only at the Decoder......Page 615
23.3.2 Channel Gain Available at Both the Encoder and the Decoder......Page 616
23.4 GAUSSIAN VECTOR FADING CHANNEL......Page 617
23.5.1 Fast Fading......Page 619
23.5.2 Slow Fading......Page 620
23.7 GAUSSIAN FADING IC......Page 624
SUMMARY......Page 626
BIBLIOGRAPHIC NOTES......Page 627
PROBLEMS......Page 628
CHAPTER 24 Networking and Information Theory......Page 629
24.1 RANDOM DATA ARRIVALS......Page 630
24.2 RANDOM ACCESS CHANNEL......Page 633
24.3 ASYNCHRONOUS MAC......Page 636
24.3.1 Proof of Achievability......Page 638
24.3.2 Proof of the Converse......Page 642
BIBLIOGRAPHIC NOTES......Page 643
PROBLEMS......Page 644
APPENDIX 24A PROOF OF LEMMA 24.1......Page 646
APPENDIX 24B PROOF OF LEMMA 24.2......Page 647
APPENDICES......Page 650
APPENDIX A Convex Sets and Functions......Page 652
Probability Bounds and Limits......Page 654
Functional Representation Lemma......Page 655
Mean Squared Error Estimation......Page 656
Gaussian Random Vectors......Page 658
Convex Cover Method......Page 660
Extension to Multiple Random Variables......Page 662
Perturbation Method......Page 663
APPENDIX D Fourier–Motzkin Elimination......Page 665
APPENDIX E Convex Optimization......Page 669
Bibliography......Page 672
Common Symbols......Page 693
Author Index......Page 695
Subject Index......Page 700