Aims of this page

The materials are ordered in the same way as the reference to them in the book. They can be downloaded by the user and exploited with the PyECC computational system (PyECC refers to the segment of PyM dedicated to error-correcting codes). Since this is work in progress (WiP), please note that a link remains inert if it is not underlined. To facilitate downloading, links to zip files will be provided in due time for chapters and finally for the whole book. Meanwhile we hope that what is currently available will already be useful, particularly to teachers and students of error-correcting codes.

Since the first four chapters of this book are organized as in Block Error-Correcting Codes—A Computational Primer, the materials also cover all the computational aspects of that book.

Index of ecclets

§0.1 In a nutshell

§0.2 The computational environment

• ⋄ 0.1. Coding and decoding Rep(3) [py | nb]
• ⋄ 0.2 Simulations of the BSC and Rep(3) [py | nb]
• ⋄ 0.3 Error-reduction factor for the repetition code Rep(3) (Fig. 1) [py | nb]

• ⋄ 0.4 Capacity of the BSC (Fig. 3): [py | nb]

• ⋄ 0.5 The function \(Q(x)\) (Fig. 4) [py | nb]
• ⋄ 0.6 Bit-error probability versus SNR (Fig. 5) [py | nb]
• ⋄ 0.7 Shannon's limit, Shannon's points and deficits (Fig. 6) [py | nb]
• ⋄ 0.8 Channel rate versus bandwidth (Fig. 7) [py | nb]

§1.1 Basis cocepts

• ⋄ 1.01 A binary code (8,20,3) [py | nb]
• ⋄ 1.02 The Hamming code [7,4,3]: [py | nb]
• ⋄ 1.03 Probability of code error and error-reduction factor [py | nb]
• ⋄ 1.04 Computation of vol_q\((n,r)\) and ub_sphere\((n,d,q)\) [py | nb]
• ⋄ 1.05 Gilbert lower bound [py | nb]

• ⋄ 1.06 Prime powers less than N [py | nb]
• ⋄ 1.07 ISBN check digit [py | nb]
• ⋄ 1.08 Parity completion of a matrix [py | nb]
• ⋄ 1.09 Interpolating decoder for RS codes [py | nb]
• ⋄ 1.10 Weight enumerator of an MDS linear code [py | nb]
• ⋄ 1.11 Example of SLD (syndrome-leader decoding) [py | nb]
• ⋄ 1.12 SLD of a ternary code [py | nb]
• ⋄ 1.13 The Gilbert-Varshamov lower bound [py | nb]
• ⋄ 1.14 Normalized Hamming matrix of condimension r over a finite field F [py | nb]
• ⋄ 1.15 Weight enumerator of the Hamming codes and MacWilliams identities [py | nb]

• ⋄ 1.16 The Hadamard matrices H⁽ⁿ⁾ [py | nb]
• ⋄ 1.17 Tensor or Kronecker product of two matrices [py | nb]
• ⋄ 1.18 Legendre character and the functions QR and NQR [py | nb]
• ⋄ 1.19 Paley matrix of a finite field of characteristic ≠ 2 [py | nb]
• ⋄ 1.20 Hadamard matrix of a finite field with \(q+1\equiv0 \mod4\) [py | nb]
• ⋄ 1.21 Conference matrix of a finite field [py | nb]
• ⋄ 1.22 Hadamard matrix of a finite field [py | nb]
• ⋄ 1.23 Construction of Hadamard codes [py | nb]
• ⋄ 1.24 Error-reduction function of the Mariner code [py | nb]
• ⋄ 1.25 The Hadamard decoder [py | nb]
• ⋄ 1.26 The Paley code of a finite field [py | nb]
• ⋄ 1.27 bdot: Bit-product of integers and Hadamard matrices [py | nb]

• ⋄ 1.28 Griesmer's upper bound and Griesmer's function [py | nb]
• ⋄ 1.29 Plotkin's upper bound [py | nb]
• ⋄ 1.30 Elias' upper bound [py | nb]
• ⋄ 1.31 Johnson's upper bound [py | nb]
• ⋄ 1.32 Krawtchouk's polynomials [py | nb]
• ⋄ 1.33 Linear programming upper bound [py | nb]
• ⋄ 1.34 The entropy function and the asymptotic bounds [py | nb]
• ⋄ 1.35 The Best code [py | nb]

§2.1 \(\mathbb{Z}_n\) and \(\mathbb{F}_p\)

• ⋄ 2.01 Examples of computations in rings \(\mathbb{Z}_n\) [py | nb]
• ⋄ 2.2 Euler's totient function \(\varphi\) [py | nb]

§2.2 Construction of finite fields

• ⋄ 2.03 Cardinal and characteristic of a ring [py | nb]
• ⋄ 2.04 Frobenius automorphisms [py | nb]
• ⋄ 2.05 Examples of the extension constructor [py | nb]
• ⋄ 2.06 Construction of \(F_{16}\) in two steps [py | nb]
• ⋄ 2.07 Construction of \(F_{343}\) [py | nb]
• ⋄ 2.08 Dimension and relative dimension of a finite field [py | nb]
• ⋄ 2.09 Examples of irreducible polynomials [py | nb]
• ⋄ 2.10 Examples of the Möbius \(\mu\) function [py | nb]
• ⋄ 2.11 Counting irreducible polynomials with the Möbius \(\mu\) function [py | nb]
• ⋄ 2.12 Product of the monic irreducible polynomials of degree \(r\) over \(F_q\) [py | nb]
• ⋄ 2.13 Finding irreducible polynomials [py | nb]

§2.3 Structure of the multiplicative group of a finite field

• ⋄ 2.14 Order of field elements [py | nb]
• ⋄ 2.15 Primitive elements of a finite field [py | nb]
• ⋄ 2.16 Example of a primitive polynomial [py | nb]
• ⋄ 2.17 The function period\((f,q)\) [py | nb]
• ⋄ 2.18 Computation of products by means of an index table [py | nb]
• ⋄ 2.19 Example of Lidl-Niedereiter [py | nb]
• ⋄ 2.20 The function coarse_period\((f,q)\) [py | nb]

• ⋄ 2.21 Examples of minimum polynomials [py | nb]
• ⋄ 2.22 Examples of conjugates [py | nb]
• ⋄ 2.23 Isomorphism between two representations of \(F_8\) [py | nb]
• ⋄ 2.24 Trace examples [py | nb]
• ⋄ 2.25 Norm examples [py | nb]

§3.1 Generalities

• ⋄ 3.01 Vectors to polynomials and conversely [py | nb]
• ⋄ 3.02 Cyclic reduction of polynomials and cyclic product [py | nb]
• ⋄ 3.03 Cyclic generating matriX [py | nb]
• ⋄ 3.04 Cyclic normalized generating and control matrices [py | nb]
• ⋄ 3.5 Cyclic control matrix [py | nb]
• ⋄ 3.6 The ternary Golay codes \([11,6,5]_3\) and \([12,6,5]_3\) [py | nb]

• ⋄ 3.07 Examples of factorization [py | nb]
• ⋄ 3.08 Examples of order(q,n) [py | nb]
• ⋄ 3.09 Cyclotomic classes [py | nb]
• ⋄ 3.10 Factoring \(X^n-1\) over \(K\) by cyclotomic splitting [py | nb]
• ⋄ 3.11 Cyclotomic polynomials [py | nb]
• ⋄ 3.12 Computation of the set \(M(n,q)\) [py | nb]
• ⋄ 3.13 Computation of cyclotomic polynomials [py | nb]

• ⋄ 3.14 The binary Golay code [23,12,7] [py | nb]

• ⋄ 3.15 The Meggitt table of the binary Golay code \([23,12,7]\) [py | nb]
• ⋄ 3.16 The Meggitt table of the ternary Golay code \([11,6,5]\) [py | nb]
• ⋄ 3.17 The Meggitt decoder [py | nb]

§4.1 Definitions and examples

• ⋄ 4.01 Constructing alternating matrices [py | nb]
• ⋄ 4.02 Constructing alternant codes [py | nb]
• ⋄ 4.03 Computing the dimension of an alternant code: An example [py | nb]
• ⋄ 4.04 Reed--Solomon codes: Construction and examples [py | nb]
• ⋄ 4.05 Generalized RS codes: Construction and examples [py | nb]
• ⋄ 4.06 BCH codes: Contruction and examples [py | nb]
• ⋄ 4.07 Construction of primitive RS codes [py | nb]
• ⋄ 4.08 The function next_q(r,t) concerning PRS codes [py | nb]
• ⋄ 4.09 A generating matrix of a PRS code [py | nb]
• ⋄ 4.10 The Matson--Solomon matrix [py | nb]
• ⋄ 4.11 Constructing classical Goppa codes [py | nb]

§4.2 Error-location, error-evaluation, and the key equation

• ⋄ 4.12 Sugiyama's variation of the Euclidean algorithm [py | nb]
• ⋄ 4.13 Example of a call to bezout [py | nb]

§4.3 The Berlekamp-Massey-Sugiyama algorithm

• ⋄ 4.14 Auxiliary functions: zero_positions and flip [py | nb]
• ⋄ 4.15 The function BMS=AD = alternant_decoder [py | nb]
• ⋄ 4.16 Example: A BCH code that corrects up to 2 errors [py | nb]
• ⋄ 4.17 Example: A Goppa code that corrects up to 3 errors [py | nb]
• ⋄ 4.18 Choosing elements of a set at random (rd_choice) [py | nb]
• ⋄ 4.19 Choosing a random element or a random list of elements of a finite field [py | nb]
• ⋄ 4.20 Generating random error patterns [py | nb]
• ⋄ 4.21 Generating random linear combinations [py | nb]
• ⋄ 4.22 A checker for the alternant decoder [py | nb]
• ⋄ 4.23 Example: RS[12,6,7] [py | nb]
• ⋄ 4.24 Example: RS[26,16,11] [py | nb]
• ⋄ 4.25 Example: RS[80,60,21] [py | nb]
• ⋄ 4.26 Example: A Goppa code \([24,9,\ge 11]\) [py | nb]

§4.4 The Peterson-Gorentein-Zierler algotithm

• ⋄ 4.27 The PGZ decoder [py | nb]
• ⋄ 4.28 The PGZm decoder [py | nb]
• ⋄ 4.29 The special Gauss-Jordan funtion GJ [py | nb]
• ⋄ 4.30 Example illustrating the action of PGZ, PGZm and BMS [py | nb]

• ⋄ 5.01 Random pemutation matrix [py | nb]
• ⋄ 5.02 The functions rd_insert(A,r) and rd_extend(A). [py | nb]
• ⋄ 5.03 The function rd_GL(k,L) [py | nb]
• ⋄ 5.04 An illustration of the McEliece system, step by step [py | nb]

Chapter 7. Convolutional Codes

Appendix A. Probability, entropy and information

Appendix B. The PyM/PyECC System

• ⋄ Minimal values of \(\varphi(n)/n\) [py | nb]
• ⋄ Modular arithmetic [py | nb]
• ⋄ Construction of rings and fields [py | nb]
• ⋄ Vectors and matrices [py | nb]
• ⋄ Example of blow and prune [py | nb]
• ⋄ Example of a Goppa code [py | nb]