Selected Topics in Information and Coding Theory (Coding Theory and Cryptology)

The last few years have witnessed rapid advancements in information and coding theory research and applications. This book provides a comprehensive guide to selected topics, both ongoing and emerging, in information and coding theory. Consisting of contributions from well-known and high-profile researchers in their respective specialties, topics that are covered include source coding; channel capacity; linear complexity; code construction, existence and analysis; bounds on codes and designs; space-time coding; LDPC codes; and codes and cryptography. All of the chapters are integrated in a manner that renders the book as a supplementary reference volume or textbook for use in both undergraduate and graduate courses on information and coding theory. As such, it will be a valuable text for students at both undergraduate and graduate levels as well as instructors, researchers, engineers, and practitioners in these fields. CONTENTS......Page 14 Preface......Page 8 Contributors......Page 16 Part 1: Applications of Coding Theory to Computational Complexity ......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 Pt. 1. Applications of coding theory to computational complexity. ch. 1. Linear complexity and related complexity measures / Arne Winterhof. ch. 2. Lattice and construction of high coding gain lattices from codes / Mohammd-Reza Sadeghi. ch. 3. Distributed space-time codes with low ML decoding complexity / G. Susinder Rajan and B. Sundar Rajan -- pt. 2. Methods of algebraic combinatorics in coding theory/codes construction and existence. ch. 4. Coding theory and algebraic combinatorics / Michael Huber. ch. 5. Block codes from matrix and group rings / Paul Hurley and Ted Hurley. ch. 6. LDPC and convolutional codes from matrix and group rings / Paul Hurley and Ted Hurley. ch. 7. Search for good linear codes in the class of quasi-cyclic and related codes / Nuh Aydin and Tsvetan Asamov -- pt. 3. Source coding/channel capacity/network coding. ch. 8. Applications of universal source coding to statistical analysis of time series / Boris Ryabko. ch. 9. Introduction to network coding for acyclic and cyclic networks / Ángela I. Barbero and Øyvind Ytrehus. ch. 10. Distributed joint source-channel coding on a multiple access channel / Vinod Sharma and R. Rajesh -- pt. 4. Other selected topics in information and coding theory. ch. 11. Low-density parity-check codes and the related performance analysis methods / Xudong Ma. ch. 12. Variable length codes and finite automata / Marie-Pierre Béal [und weitere]. ch. 13. Decoding and finding the minimum distance with Gröbner Bases : history and new insights / Stanislav Bulygin and Ruud Pellikaan. ch. 14. Cooperative diversity systems for wireless communication / Murat Uysal and Muhammad Mehboob Fareed. ch. 15. Public key cryptography and coding theory / Pascal Véron Linear complexity and related complexity measures / Arne Winterhof -- Lattice and construction of high coding gain lattices from codes / Mohammd-Reza Sadeghi -- Distributed space-time codes with low ML decoding complexity / G. Susinder Rajan and B. Sundar Rajan -- Coding theory and algebraic combinatorics / Michael Huber -- Block codes from matrix and group rings / Paul Hurley and Ted Hurley -- LDPC and convolutional codes from matrix and group rings / Paul Hurley and Ted Hurley -- Search for goo linear codes in the class of quasi-cyclic and related codes / Nuh Aydin and Tsvetan Asamov -- Applications of universal source coding to statistical analysis of time series / Boris Ryabko -- Introduction to network coding for acyclic and cyclic networks / Ángela I. Barbero and Øyvind Ytrehus -- Distributed joint source-channel coding on a multiple access channel / Vinod Sharma and R. Rajesh -- Low-density parity-check codes and the related performance analysis methods / Xudong Ma -- Variable length codes and finite automata / Marie-Pierre Béal ... [et al.] -- Decoding and finding the minimum distance with Gröbner bases : history and new insights / Stanislav Bulygin and Ruud Pellikaan -- Cooperative diversity systems for wireless communication / Murat Uysal and Muhammad Mehboob Fareed -- Public key cryptography and coding theory / Pascal Véron The last few years have witnessed rapid advancements in information and coding theory research and applications. This book provides a comprehensive guide to selected topics, both ongoing and emerging, in information and coding theory. Consisting of contributions from well-known and high-profile researchers in their respective specialties, topics that are covered include source coding; channel capacity; linear complexity; code construction, existence and analysis; bounds on codes and designs; space-time coding; LDPC codes; and codes and cryptography.All of the chapters are integrated in a manner that renders the book as a supplementary reference volume or textbook for use in both undergraduate and graduate courses on information and coding theory. As such, it will be a valuable text for students at both undergraduate and graduate levels as well as instructors, researchers, engineers, and practitioners in these fields.Supporting Powerpoint Slides are available upon request for all instructors who adopt this book as a course text.