Part I Generator Matrix
1 Generator Matrix Approach to Linear Block Codes .............. 3
1.1 Additive n × n Linear Transformation
of a Binary Sequence ......................................... 3
1.2 Generator Matrix G of a Linear Block Code ............... 5
1.3 Polynomial Description of the Generator Matrix
in a Linear Block Code ................................. 10
1.4 Properties of a Linear Block Code Derived
from the Structural Characteristics of g(x) ............ 15
1.5 Systematic Encoder Circuit ............................. 19
1.6 Code Concatenation: Effects on G Matrix ................ 21
1.7 Code Puncturation: Effects on G Matrix ................. 28
1.8 Cyclic Block Codes ..................................... 33
1.9 Enumeration of all the Possible Cyclic Codes of
Length N ............................................... 37
1.10 Shortened Cyclic (SC) Codes ............................ 44
1.11 Lengthened Cyclic (LC) Codes ........................... 47
1.12 Subcode of an s.s. Time-Invariant Polynomial Code ...... 56
1.13 Modified Lengthened Cyclic (MLC) Codes ................. 58
1.14 State Diagrams ......................................... 61
1.15 Direct Product Codes ................................... 68
1.16 Generator Matrix of a Direct Product Code .............. 73
1.17 Direct Product Codes as MLC Codes ...................... 75
1.18 Interpretation of Particular Direct Product Codes
by Means of GPC Codes .................................. 76
1.19 Cyclic and Pseudo-Cyclic Codes in a Non-binary
Alphabet ............................................... 79
1.20 Q-ary State Diagrams ................................... 83
1.21 Main Families of Non-binary Block Codes ................ 85
1.22 Reed-Solomon Codes and Other MDS Non-binary Codes ...... 89
1.23 Trellis for an s.s. Time-Invariant Block Code Obtained
from Its Generator Matrix .............................. 95
References .................................................. 98
2 Wide-Sense Time-Invariant Block Codes in Their
Generator Matrix ........................................... 101
2.1 Periodically Time-Varying Generator Matrix ............ 101
2.2 Quasi-Cyclic Codes (QC) as a Widening in the Concept
of Cyclic Codes ....................................... 105
2.3 Quasi-Cyclic Codes with Distributed Control Symbols
Described with Their G Matrix ......................... 112
2.4 Representation of Known Block Codes as QC Codes
with Distributed Control Symbols ...................... 117
2.5 Relation Between Some Binary QC-Codes and Cyclic
or Pseudo-Cyclic Codes in a Q-Ary Alphabet ............ 119
2.6 Encoder Circuits Based on the G Matrix for a QC Code . 121
2.7 Shortened Quasi-Cyclic (SQC) Codes .................... 125
2.8 Lengthened Quasi-Cyclic (LQC) Codes ................... 130
2.9 Subcode of a w.s. Time-Invariant Polynomial Code ...... 136
2.10 Modified Lengthened Quasi-Cyclic (MLQC) Codes ......... 138
2.11 Trellis for a w.s. Time-Invariant Block Code Obtained
from Its Generator Matrix ............................. 143
References ................................................. 147
3 Generator Matrix Approach to s.s. Time-Invariant
Convolutional Codes ........................................ 149
3.1 Traditional View of Non-systematic s.s.
Time-Invariant Convolutional Codes .................... 149
3.2 State Diagram and Minimum Distance .................... 154
3.3 Systematic Convolutional Codes ........................ 162
3.4 Low-Rate Convolutional Codes .......................... 166
3.5 High-Rate Punctured Convolutional Codes ............... 172
3.6 Recursive Systematic Convolutional (RSC) Codes ........ 176
3.7 Equivalence Between MLC Codes and s.s. Time-Invariant
Convolutional Codes ................................... 180
3.8 Strict-Sense Time-Invariant High-Rate Convolutional
(MLC) Codes ........................................... 183
3.9 A First Bridge Between Cyclic Block Codes and s.s.
Time-Invariant Convolutional Codes .................... 190
3.10 Tail-Biting s.s. Time-Invariant Convolutional Codes ... 195
3.11 Trellis of an s.s. Time-Invariant Convolutional
Code Obtained from Its Generator Matrix ............... 199
References ................................................. 203
4 Wide-Sense Time-Invariant Convolutional Codes
in Their Generator Matrix .................................. 205
4.1 Periodically Time-Varying Generator Matrix of
a Convolutional Code .................................. 205
4.2 Traditional Approach to w.s. Time-Invariant
Convolutional Codes in Their G Matrix ................. 206
4.3 Existence of the Inverse Linear Transformation ........ 215
4.4 RSC Version of a w.s. Time-Invariant Convolutional
Code .................................................. 218
4.5 Equivalence Between MLQC Codes and a Certain Class
of w.s. Time-Invariant Convolutional Codes ............ 222
4.6 Practical Importance of Punctured Convolutional
Codes ................................................. 225
4.7 Tail-Biting w.s. Time-Invariant Convolutional Codes ... 226
4.8 Unwrapping QC Block Codes and Reordered Versions of
Convolutional Codes ................................... 231
4.9 A First Bridge Between Quasi-cyclic Block Codes
and w.s. Time-Invariant Convolutional Codes ........... 238
4.10 Trellis of a w.s. Time-Invariant Convolutional Code
Obtained from Its Generator Matrix .................... 240
References ................................................. 242
Part II Parity Check Matrix
5 Parity Check Matrix Approach to Linear Block Codes ..........245
5.1 Parity Check Matrix of a Linear Block Code ............ 245
5.2 Parity Check Matrix and Hard-Decision Decoding ........ 249
5.3 Relations Between the Parity Check Matrix
and the Generator Matrix .............................. 255
5.4 Polynomial Description of the Parity Check Matrix
in a Linear Block Code ................................ 258
5.5 Encoder Circuit Based on the Parity Check Polynomial
and Its State Diagram ................................. 260
5.6 Code Concatenation: Effects on H Matrix ............... 266
5.7 Code Puncturation: Effects on H Matrix ................ 269
5.8 Shortening Cyclic Codes: Effects on H Matrix .......... 272
5.9 Lengthening Cyclic Codes: Effects on H Matrix ......... 274
5.10 MLC Codes (s.s. Time-Invariant Convolutional Codes in
G) and Their H Matrix ................................. 276
5.11 Some Further Considerations About H Matrix in
Polynomial Codes ...................................... 278
5.12 Two Types of Rows in Polynomial Code H Matrix ......... 284
5.13 H-Extended Cyclic (НЕС) Codes ......................... 286
5.14 Discussion About Dual Polynomial Codes ................ 292
5.15 Modified H-Extended Cyclic (MHEC) Codes ............... 297
5.16 Direct Product Codes: Structure of Their H Matrix ..... 301
5.17 Composite Codes Based on GPC Codes .................... 304
5.18 H Matrix for Non-binary Block Codes ................... 312
5.19 Trellis of an s.s. Time-Invariant Block Code
Obtained from Its Parity Check Matrix ................. 315
References ................................................. 319
6 Wide-Sense Time-Invariant Block Codes in Their Parity
Check Matrix ........................................... 321
6.1 Periodically Time-Varying Parity Check Matrix ......... 321
6.2 Parity Check Matrix of a Quasi-Cyclic Code ............ 324
6.3 Quasi-Cyclic Codes with Distributed Control Symbols
Described with Their H Matrix ......................... 329
6.4 Encoder Circuit Based on the H Matrix in a QC Code .... 332
6.5 Shortened Quasi-Cyclic (SQC) Codes and Their H
Matrix ................................................ 335
6.6 Lengthened Quasi-Cyclic (LQC) Codes and Their H
Matrix ................................................ 338
6.7 Punctured QC Codes .................................... 341
6.8 H-Extended Quasi-Cyclic (HEQC) Codes .................. 343
6.9 Modified Lengthened Quasi-Cyclic (MLQC) Codes
and Their H Matrix .................................... 346
6.10 Modified H-Extended Quasi-Cyclic (MHEQC) Codes
and Their H Matrix .................................... 347
6.11 Trellis of a w.s. Time-Invariant Block Code Obtained
from Its Parity Check Matrix .......................... 352
References ................................................. 353
7 Strict-Sense Time-Invariant Convolutional Codes
in Their Parity Check Matrix ............................... 355
7.1 Syndrome Former Sub-matrix ............................ 355
7.2 Construction of the Syndrome Former Sub-matrix
for Low-Rate Convolutional Codes ...................... 360
7.3 Extension of the Procedure for Obtaining the Syndrome
Former Sub-matrix to High-Rate Convolutional Codes ......... 366
7.4 Different Types of Not Well Designed Convolutional
Codes ................................................. 372
7.5 Interpretation of Direct Product Codes as Particular
Not Well Designed Convolutional Codes ................. 381
7.6 Various Situations for Well Designed and Not Well
Designed Convolutional Codes Regarding Their Parity
Check Matrix .......................................... 385
7.7 Systematic Encoder Circuit Based on a Unique
Non-periodic Parity Check Polynomial .................. 393
7.8 Another Type of Systematic Encoder Circuit for s.s.
Time-Invariant Convolutional Codes in Their H Matrix .. 398
7.9 Tail-Biting Convolutional Codes s.s. Time-Invariant
in H .................................................. 403
7.10 Decoding Computational Complexity in the Trellis
for s.s. Time-Invariant Convolutional Codes
in Their H Matrix ..................................... 408
7.11 A Second Bridge Between Cyclic Block Codes
and s.s. Time-Invariant Convolutional Codes ........... 412
References ................................................. 417
8 Wide-Sense Time-Invariant Convolutional Codes in Their
Parity Check Matrix ........................................ 419
8.1 Traditional Obtainment of a Symbolic Parity Check
Matrix in a w.s. Time-Invariant Convolutional Code .... 419
8.2 Null ex-OR Sum of Clusters of Syndromes for
Obtaining G and Column Construction of H .............. 427
8.3 Encoder Circuits Based on Different Parity Check
Polynomials ........................................... 430
8.4 Punctured Convolutional Codes and Their H Matrix ...... 432
8.5 Tail-Biting w.s. Time-Invariant Convolutional
Codes and Their H Matrix .............................. 434
8.6 Unwrapping QC Codes Described by Their H Matrix ....... 436
8.7 Reordered Versions of a w.s. Time-Invariant
Convolutional Code .................................... 438
8.8 Introductory Treatment of Array Codes ................. 443
8.9 Generator Matrix of Improper Array Codes .............. 448
8.10 A Second Bridge Between Quasi-Cyclic Codes
and w.s. Time-Invariant Convolutional Codes ........... 454
8.11 Unwrapping the Tail-Biting Convolutional Form
of Improper Array Codes ............................... 462
8.12 Further Considerations on Direct Product Codes
Related to QC Array Codes ............................. 465
References ................................................. 468
Part III Modern Coding
9 Turbo Codes ................................................ 473
9.1 The Basic Idea of Turbo Codes ......................... 473
9.2 Some Particular Aspects of RSC Codes .................. 479
9.3 Statistical Prediction of Turbo Code Performance ...... 482
9.4 G Matrix of a Turbo Code and Correct
Frame Termination ..................................... 483
9.5 Outline of the Decoding Algorithm ..................... 488
9.6 Turbo Codes in Serial Concatenation ................... 491
9.7 Turbo-Product Codes ................................... 493
9.8 Parity Check Matrix of Turbo Codes .................... 498
References ................................................. 501
10 Low Density Parity Check Codes ............................. 503
10.1 Tanner Graph and Message Passing Decoding
Algorithms Constructed on It .......................... 503
10.2 Short Cycles and the Row-Column Constraint ............ 506
10.3 Main Families of LDPC Codes ........................... 512
10.4 Masking and Row or Column Splitting ................... 517
10.5 LDPC Codes Obtained from Superimposition .............. 521
10.6 Procedures for Obtaining LDPC Codes from Known
Non-LDPC Codes ........................................ 523
10.7 Computer Based Design of Irregular LDPC Codes ......... 528
10.8 Outline of the Sum-Product Algorithm, Its
Computational Complexity and Points of Weakness ....... 530
10.9 Statistical Analysis of the Asymptotic Behaviour
of Regular and Irregular LDPC Codes ................... 533
10.10 A First Approach to LDPC Convolutional Codes ......... 536
References ................................................. 541
11 Binomial Product Generator LDPC Block Codes ................ 545
11.1 Cyclic Version of a Composite Code Based on GPC
Codes ................................................. 545
11.2 Generator Polynomial for a Parallelepiped
Concatenation of GPC Codes ............................ 549
11.3 Evaluation of the Minimum Distance in BPG Block
Codes ................................................. 553
11.4 Effects of Combined Equalities and of Independent
Equalities ............................................ 558
11.5 Main Results on DC-GPC Codes and Direct Products
of DC-GPC Codes ....................................... 562
11.6 Improper Array LDPC Codes ............................. 567
11.7 Generalized Array LDPC Codes .......................... 569
11.8 Some Variants of Improper Array Codes ................. 572
11.9 Single-Layer Parity Check Matrix QC Codes ............. 576
References ................................................. 580
12 LDPC Convolutional Codes ................................... 581
12.1 General Considerations ................................ 581
12.2 Modified H-Extended Codes from BPG Block Codes ........ 585
12.3 Convolutional LDPC Codes Obtained by Reordering
and Unwrapping BPG Block Codes ........................ 590
12.4 The Best Performance of LDPC Convolutional
Codes up to Now ....................................... 595
12.5 1/2-Rate LDPC Regular Convolutional Codes Directly
Designed .............................................. 598
12.6 High-Rate LDPC Regular Convolutional Codes Directly
Designed .............................................. 603
12.7 High-Rate Irregular LDPC Convolutional Codes
Directly Designed ..................................... 609
12.8 Low-Rate LDPC Convolutional Codes Directly Designed ... 612
12.9 LDPC Convolutional Codes with Period Length and
Number of Information Symbols Per Period not
Co-prime .............................................. 617
12.10 Final Comments ....................................... 619
References ................................................. 621
Appendix A: Matrix Algebra in a Binary Finite Field ........... 623
Appendix B: Polynomial Representation of Binary Sequences ..... 643
Appendix C: Electronic Circuits for Multiplication or
Division in Polynomial Representation of
Binary Sequences .................................. 679
Appendix D: Survey on the Main Performance of Error
Correcting Codes .................................. 691
Index ......................................................... 729
|
