Selected Topics in Information and Coding Theory

CONTENTS......Page 14
Preface......Page 8
Contributors......Page 16
Part 1: Applications of Coding Theory to Computational Complexity\r......Page 20
1.1. Introduction......Page 22
1.2. Background......Page 24
1.3. The Berlekamp–Massey Algorithm......Page 25
1.4. The Expected Value of the Linear Complexity Profile......Page 27
1.5.1. Explicit Non-linear Pseudorandom Numbers......Page 30
1.5.2. Recursive Non-linear Pseudorandom Numbers......Page 33
1.5.3. Legendre Sequence and Related Bit Sequences......Page 37
1.5.4. Elliptic Curve Generators......Page 41
1.6.1. Lattice Test......Page 44
1.6.2. k-Error Linear Complexity......Page 45
1.6.4. Autocorrelation and Related Distribution Measures for Binary Sequences......Page 47
1.6.5. Discrepancy......Page 49
1.7. Thoughts for Practitioners......Page 50
1.10. Questions......Page 51
1.11. Keywords......Page 53
References......Page 55
2.1. Introduction......Page 60
2.2.1. Codes......Page 61
2.2.2. Lattices......Page 62
2.2.2.1. The Sphere Packing Problem......Page 66
2.3. The Channel Coding Problem......Page 68
2.4. Trellis Diagram and Label Code of Lattices......Page 71
2.5.1. Construction A......Page 75
2.5.2. Constructions B and C......Page 78
2.5.3. Construction D......Page 79
2.5.4. Construction D......Page 83
2.6. Conclusions and Future Research......Page 88
2.8. Answers......Page 89
2.9. Keywords......Page 92
References......Page 94
3.1. Introduction......Page 96
3.1.2. Abbreviations......Page 99
3.2. Background......Page 100
3.3. Multi-Group ML Decodable STBCs for Point to Point MIMO Systems......Page 105
3.4.1. Coherent Case Without CSI at Relays......Page 111
3.4.1.1. Four group ML decodable DSTBCs......Page 115
3.4.1.2. Single complex symbol ML decodable DSTBCs......Page 120
3.4.2. Coherent Case with Partial CSI at Relays......Page 124
3.5. Thoughts for Practitioners......Page 126
3.7. Directions for Future Research......Page 127
3.8. Keywords......Page 128
3.9. Exercise......Page 129
3.10. Sample Solutions to Exercise Problems......Page 130
References......Page 132
Part 2: Methods of Algebraic Combinatorics in Coding Theory/Codes Construction and Existence......Page 138
4.1. Introduction......Page 140
4.2. Background......Page 141
4.3.1. Introduction to Finite Projective Planes and Combinatorial Designs......Page 144
4.3.2. Basic Connections Between Codes and Combinatorial Designs......Page 151
4.3.3. Perfect Codes and Designs......Page 154
4.3.4. The Assmus-Mattson Theorem and Analogues......Page 156
4.3.5. Codes and Finite Geometries......Page 161
4.3.6. Golay Codes, Mathieu–Witt Designs, and Mathieu Groups......Page 162
4.3.7. Golay Codes, Leech Lattice, Kissing Numbers, and Sphere Packings......Page 163
4.3.8. Codes and Association Schemes......Page 165
4.4. Directions for Further Research......Page 166
4.6. Exercises......Page 167
4.7. Solutions......Page 168
References......Page 170
5.1. Introduction......Page 178
5.2. Algebraic Background......Page 179
5.2.1. Examples......Page 180
5.2.3. Subrings and Ideals......Page 181
5.2.5.1. Examples of Algebras......Page 182
5.2.5.2. Subalgebras of Matrices......Page 183
5.2.6.1. Examples......Page 184
5.2.7.1. Zero-Divisor Example......Page 185
5.2.8. Group Rings and Matrices......Page 186
5.2.9. Examples of RG Matrices......Page 187
5.2.10. Element Properties......Page 188
5.3. Codes from Group Rings......Page 189
5.3.1. Codes from Units......Page 190
5.3.1.1. Generator and Check Matrices......Page 191
5.3.1.2. Constructing Unit-Derived Codes......Page 192
5.3.1.4. Dual and Orthogonal Codes......Page 193
5.3.2. Codes from Zero-Divisors......Page 194
5.3.2.1. Equivalent Codes in Rn......Page 196
5.3.2.2. Check Elements and Matrices......Page 198
5.3.2.3. Dual Codes......Page 201
5.3.3. Relationship with Cyclic Codes......Page 202
5.3.4. When are They Ideals?......Page 203
5.4. Dihedral Codes......Page 206
5.5. Self-Dual Codes......Page 207
5.6.1. Exercises......Page 209
References......Page 212
6.1. Introduction......Page 214
6.2. LDPC Codes......Page 216
6.2.1. How to Avoid Short Cycles Algebraically......Page 218
6.2.3. Cyclic Differences......Page 219
6.2.4. Collection of Differences of a Group Ring Element......Page 220
6.2.6. Special Cases......Page 221
6.3.1. Introduction......Page 222
6.3.3. Convolutional Codes from Units......Page 224
6.3.4. General Construction......Page 225
6.3.5. Polynomial Case......Page 226
6.3.7. Group Ring Convolutional Codes......Page 227
6.3.9. Convolutional Codes from Nilpotent Elements......Page 228
6.3.10.1. Example 1......Page 229
6.3.11. Direct Products: Turbo-Effect......Page 230
6.3.12. (2,1) Codes......Page 231
6.3.12.1. From Cyclic Codes to Convolutional Codes......Page 233
6.3.12.2. (2m, 1) Codes......Page 236
6.3.13. Higher Rate Convolutional Codes......Page 237
6.3.14. Examples......Page 238
6.3.15. Polynomial Generator and Control Matrices......Page 239
6.3.16.1. Example......Page 241
6.3.17.1. Example......Page 242
6.3.18.1. Idempotents in Group Rings......Page 243
6.3.18.3. Cyclic......Page 244
6.3.18.4. Symmetric Group......Page 245
6.3.19.1. Examples in Characteristic 3......Page 247
6.3.19.3. A General Result for Characteristic 3......Page 248
6.3.20. Nilpotent Type......Page 249
6.3.21. Hamming Type......Page 250
6.4.1.1. LDPC and Collections of Di.erences......Page 251
6.4.1.2. Convolutional Exercises......Page 252
6.4.2.1. LDPC Related......Page 254
References......Page 255
7.1. Introduction and Basic Definitions......Page 258
7.1.1. Main Problem of Coding Theory......Page 264
7.2.1. Some Elementary Constructions......Page 265
7.2.2. Some Bounds on Codes......Page 266
7.3. Some Background in Abstract Algebra......Page 267
7.3.1. Polynomials......Page 268
7.3.2. Field Extensions......Page 269
7.3.3. Structure of Finite Fields......Page 271
7.3.4. Roots of Irreducible Polynomials......Page 272
7.3.5. Roots of Unity......Page 273
7.3.6. Factorization of xn - 1......Page 274
7.4.1. Cyclic Codes......Page 275
7.4.2. BCH Codes......Page 277
7.4.3. Reed Solomon Codes......Page 278
7.4.4. Hamming Codes......Page 279
7.4.5. Quadratic Residue Codes......Page 280
7.5.1. Constacyclic Codes......Page 281
7.5.2. Factorization of xn - a and a BCH bound......Page 282
7.5.3. BCH Bound for Constacyclic Codes......Page 284
7.5.5. Structure of 1-Generator QT Codes......Page 285
7.6.1. Computing Minimum Distance of a Linear Code......Page 288
7.6.1.1. The Brouwer–Zimmermann Algorithm for Linear Codes......Page 289
7.7.1. Codes Over Z4......Page 290
7.7.2. A Database of Z4 Codes......Page 291
7.8.1. QCT Codes......Page 292
7.8.2. Algebraic Properties of QCT Codes......Page 293
7.8.3. Open Problems......Page 295
7.10. Key Concepts in the Chapter......Page 296
7.11. Solution to Exercises......Page 297
References......Page 300
Part 3: Source Coding/Channel Capacity/ Network Coding......Page 306
8.1. Introduction......Page 308
8.2.1. Estimation and Prediction for I.I.D. Sources......Page 309
8.2.2. Consistent Estimations and On-line Predictors for Markov’s and Stationary Ergodic Processes......Page 316
8.2.3. Hypothesis Testing......Page 320
8.2.4. Codes......Page 321
8.3.1. The Estimation of (Limiting) Probabilities......Page 323
8.3.2. Prediction......Page 325
8.3.3. Problems with Side Information......Page 326
8.3.4. The Case of Several Independent Samples......Page 327
8.4.2. Testing for Serial Independence......Page 330
8.5.1. Density Estimation and Its Application......Page 331
8.5.2. Hypothesis Testing......Page 335
8.7. Problems for Chapter......Page 336
8.8. Solutions to Problems......Page 338
8.9. Keywords......Page 352
References......Page 354
9.1. Introduction......Page 358
9.2. Background......Page 360
9.2.1. Digital Communication Networks......Page 362
9.3.1. Separation of Network Coding and Channel Coding, and Network Coding on Noisy Networks......Page 366
9.3.2. Wireless Networks and Networks with Broadcast Nodes......Page 367
9.3.3. Other Communication Scenarios......Page 368
9.4. How to Encode......Page 369
9.5. Random Network Coding......Page 374
9.5.2. Decoding Complexity......Page 375
9.6. Deterministic linear network coding: Efficient Algorithms......Page 376
9.6.1.1. Maintaining the full rank invariant......Page 382
9.7. Many Networks are Cyclic......Page 383
9.8. Networks with Cycles in the Flow......Page 385
9.9. On the Alphabet Size, and an Efficient Algorithm to Encode Over the Binary Field......Page 394
9.9.1. Further Remarks......Page 397
9.9.2. The LIFE* Algorithm......Page 399
9.9.2.1. The flow acyclic parts of the network......Page 403
9.9.2.2. Dealing with flow cycles......Page 404
9.9.2.3. The simple flow cycle case......Page 405
9.9.2.4. The knot case......Page 407
9.9.3. Notes......Page 409
9.9.3.2. Complexity......Page 410
9.10.1. Example 1......Page 411
9.10.2. Example 2......Page 415
9.10.3. Example 4......Page 416
9.10.4. Example 5......Page 418
9.10.5. Example 6......Page 426
9.12.1. Review Questions......Page 432
9.12.2. Review Answers......Page 434
References......Page 436
10.1. Introduction......Page 442
10.2. Background......Page 444
10.3. Transmission of Correlated Sources Over an MAC......Page 446
10.3.1. Extension to Multiple Sources......Page 449
10.3.2. Example......Page 450
10.4.2. Lossy MAC......Page 451
10.4.5. Correlated Sources with Lossless Transmission Over Multi-User Channels with Receiver Side Information......Page 452
10.5. Discrete Alphabet Sources Over GMAC......Page 453
10.5.1. A Coding Scheme......Page 455
10.5.2. Example......Page 458
10.6. Source-Channel Coding for Gaussian Sources Over GMAC......Page 459
10.6.1. Amplify and Forward Scheme......Page 460
10.6.3. Lapidoth–Tinguely Scheme......Page 461
10.6.4. Asymptotic Performance of the Three Schemes......Page 463
10.6.5. Continuous Sources Over a GMAC......Page 464
10.7.1. Transmission of Correlated Sources Over Orthogonal Channels......Page 465
10.7.2. Gaussian Sources and Orthogonal Gaussian Channels......Page 466
10.7.3. Side Information......Page 468
10.7.3.2. SB with Side Information......Page 469
10.7.3.3. Comparison of AF and SB with Side Information......Page 470
10.8. MAC with Feedback......Page 471
10.9. MAC with Fading......Page 472
10.9.1. CSI at Receiver Only......Page 473
10.9.2. CSI at Both Transmitter and Receiver......Page 474
10.10. Thoughts for Practitioners......Page 475
10.11. Directions for Future Research......Page 477
10.13. Problems......Page 478
10.14. Keywords......Page 480
References......Page 481
Part 4: Other Selected Topics in Information and Coding Theory......Page 488
11.1.2. Overview of this Chapter......Page 490
11.2. Tanner Graph......Page 491
11.3.1. Algebraic Construction......Page 492
11.3.2. Standard Random Construction......Page 493
11.3.3. Random Constructions Based on Graph Lifts......Page 494
11.4.1. Factor Graphs......Page 495
11.4.2. Message-Passing Algorithm for Tree-Structured Factor Graphs......Page 497
11.4.3. Loopy Propagation......Page 500
11.5. LDPC Decoding by Loopy Propagation......Page 501
11.6.1. Concentration Theorem......Page 505
11.6.2. Density Evolution for BIAWGN Channels......Page 506
11.6.3. Density Evolution for BECs......Page 507
11.7. Finite-Length Analysis......Page 508
11.8. Problems......Page 511
11.9. Problem Solution......Page 514
11.10. Thoughts for Practitioners......Page 517
11.13. Keywords......Page 518
References......Page 520
12.1. Introduction......Page 524
12.2. Background......Page 526
12.3. Thoughts for Practitioners......Page 528
12.4. Definitions and Notation......Page 532
12.5. Basic Properties of Codes......Page 535
12.6. Optimal Prefix Codes......Page 540
12.6.1. Exercises......Page 551
12.7. Prefix Codes for Integers......Page 553
12.7.1. Exercises......Page 558
12.8. Encoders and Decoders......Page 559
12.9. Codes for Constrained Channels......Page 564
12.10. Codes for Constrained Sources......Page 573
12.11. Bifix Codes......Page 578
12.11.1. Exercises......Page 584
12.12. Synchronizing Words......Page 585
12.13. Directions for Future Research......Page 588
12.14. Conclusion......Page 589
12.15. Solutions to Exercises......Page 590
12.16. Questions and Answers......Page 592
12.17. Keywords......Page 596
References......Page 600
13.1. Introduction......Page 604
13.2.1. Gr¨obner Bases in Polynomial System Solving......Page 605
13.2.2. Notation......Page 608
13.3.1. Cooper’s Philosophy and Its Development......Page 609
13.3.2. Newton Identities Based Method......Page 616
13.4.1. Decoding Affine Variety Codes......Page 621
13.4.2. The Method of Quadratic Equations......Page 625
13.6. Directions for Future Research......Page 633
13.8. Questions......Page 634
13.9. Answers......Page 635
13.10. Keywords......Page 636
References......Page 638
14.1. Introduction......Page 642
14.2. Background......Page 645
14.3. Amplify-and-Forward Relaying......Page 649
14.4. Decode-and-Forward Relaying......Page 656
14.5. Thoughts for Practitioners......Page 661
14.6. Directions for Future Work......Page 664
14.7. Conclusions......Page 666
14.8. Questions......Page 667
14.9. Key Answers......Page 669
14.10. Keywords......Page 671
VIII. Exercise......Page 672
Key Answers......Page 675
References......Page 677
15.1. Introduction......Page 682
15.2.1. Coding Theory......Page 684
15.2.2. Goppa codes......Page 685
15.2.3. Computational Complexity Theory......Page 686
15.3. The Syndrome Decoding Problem......Page 688
15.4. Algorithms for the SD Problem......Page 689
15.5. A Pseudo-Random Generator......Page 692
15.6.1. Introduction......Page 694
15.6.2. The G-SD Scheme......Page 695
15.6.3. Security and Performances......Page 697
15.7. The McEliece’s Public Key Cryptosystem......Page 698
15.7.1. Cryptanalysis......Page 699
15.7.1.1. A structural attack......Page 700
15.7.1.2. A generic attack......Page 701
15.7.2. Niederreiter’s Variant......Page 702
15.8. The CFS Signature Scheme......Page 703
15.8.2. Security and Performances......Page 704
15.9. Secret Sharing Schemes......Page 706
15.10.1. Regular Words......Page 708
15.10.2. Quasi-Cyclic Codes......Page 709
15.11.1. Code-based Hash Function......Page 711
15.11.2. Rank Distance Codes......Page 712
15.11.3. An Identity-based Identification Scheme......Page 714
15.12. Conclusions......Page 715
15.13. Questions......Page 716
15.14. Keywords......Page 719
References......Page 721