Correctness checks for classical ECCs

[Krastanov]

@Fe-r-oz , I see you have contributed quite a few different classes of classical ECCs. E.g. in:

• [2ᵐ + 1 - 3, k, 2ᵐ ⁺ ¹ - 3 - k] shortenedMDS code #254
• Convolutional code #256
• Adding classical Bose–Chaudhuri–Hocquenghem code to ECC module #263
• Goppa code #266

These are quite valuable contributions, but it will take me some time to review them. My chief difficulty in reviewing them would be figuring out some selfconsistency checks. What I mean by this is that the following would NOT be a good way to review:

I read the papers, then read your code and check whether your code follows the algorithms in the papers. You have already basically done the same, and me redoing it is not very valuable because then the contribution and the review would be susceptible to the exact same type of mistakes. Rereading some code is simply not a good way to review.

Instead, we need to figure out some self-correcting method. There are a few such self-correcting checks done for the quantum codes for instance. Checking that they have valid tableaux, checking ranks, verifying that encoding circuits work as expected, etc.

In order to merge all of these classical code contributions of yours, we need to figure out similar self-correctness checks. I do not have a lot of good ideas for that right now (hence this issue, so we can discuss), but a couple of options include:

• checking the rank of the binary matrices and verifying we do not have redundant rows
• checking that each column of a binary matrix has at least one non-zero entry
• finding some code database and comparing the binary matrices generated here to the matrices from the database (probably one of the most valuable options, although it also has potential complications if the database uses different bit order conventions)
• similarly to the database option, finding another piece of software that also generates these codes and running comparisons between the two

Do you know of such databases or alternative pieces of software?

[Fe-r-oz]

I acknowledge the distinction between the perspective of reviewing a pull request and executing its implementation.

In the test files for the BCH, Reed-Solomon, Goppa, I have included the thorough tests similar compared to the first 2 options that can ease the difficulty when reviewing. Some of these are attached below. I recommend to please have a look at the test files especially.

My frame of reference:

I have tested their binary check matrices for almost of the instance of the codes for varying n, k, etc.t with thorough tests. As we are dealing with finite field, we check their degree, their gcd, their mod, their irreducibility of generator polynomial (if required), their designed distance of parity check matrices, their rank, the structure of their field matrices and how they are generated. We check how is each field element expressed as m-tuple as well.

For example:
In the case of reed solomon codes, the minimum hamming distance d should be at least >= 2 ^ (r + 1) - 3 - k whereris the degree of the finite field, s is the 3 level quantization (symbol) and k is the code size. This test passes for all the instances of the code, ensuring self-consistency of the binary check matrices of the expanded matrices. This agrees with the Shortened and expanded MDS RS code [[2 ^ (m) + 1 - s, k, 2 ^ (m + 1) - s - k]]. Also, I compared the constructions down to the field matrices that are constructed in between as well from the literature.

Some Examples of some tests taken from each test files:

Goppa
 @test is_irreducible(gx) == true # the generator polynomial must be irreducible
 @test degree(gx) == t || degree(gx) == t - 1   
 @test gcd(b - L[t], gx) == 1  #the gcd must be 1 
 @test designed_distance(parity_checks(Goppa(n, t)), t) == true 

BCH
 @test mod(x^n - 1, gx) == 0 #the mod must be zero
 @test designed_distance(H) >= 2 * t + 1 || designed_distance(H) == 2 * t

Reed Solomon:
 @test rank(parity_checks(ReedSolomon(n, k))) == r * k #rank must equal n - k
 @test designed_distance(parity_checks(ReedSolomon(n, k)), k, n, r) == true
 @test degree(poly) == n - k

In some cases, I don't think running comparisons will work in some cases of codes when working with Finite Fields. For instance, in the case of the Goppa code, the main developer of Nemo told me that Nemo generates irreducible polynomial with a probability of 1/n. So, every time, we run the Goppa code, a distinct irreducible Goppa polynomial is generate. Since we construct the support list L from by checking that whether gx (Goppa Polynomial) is evaluated to != 0, every time, the representation of parity check matrix is different because the distinct irreducible polynomial. But properties and the method such as minimum distance are followed.

I don't know any such databases or software at the moment.

I would suggest to please review the in the following order: BCH, Reed-Solmon and Goppa. This is because the order of complexity of implementation increases in this order.

After each review, please let me know your comments so that we can discuss further.

[Fe-r-oz]

Do you know of such databases or alternative pieces of software?

sagemath is a precursor to OSCAR. It's a python based computer algebra system. When developing the Goppa code for quantum goppa code, I discussed with Nemo folks the differences between the two. In sage, they were hardcoding the irreducible goppa polynomial for particular degree instead of generating it randomly based on the input parameters. In Nemo, we can generate a random irreducible polynomial for a given degree with probability of 1/n so using iteration, we increase the success probability.

Example in sage:

F = GF(2^6)
R.<x> = F[]
g = x^9 + 1 # hardcoding the irreducible polynomial
L = [a for a in F.list() if g(a) != 0]
C = codes.GoppaCode(g, L)
C
E = codes.encoders.GoppaCodeEncoder(C)
E
Encoder for [55, 16] Goppa code over GF(2)

In addition, they also have hardcoded the binary golay codes instead of designing algorithm for generating it. Instead, there is a neat way of generating golay code's bordered reverse circulant matrix A from first principles that was given in Huffman and Pless book on Fundamentals of Error Correction (Page 31-33). It turned out to be quite helpful to have sagemath and books as references, along with useful discussions with Nemo folks that helps to combine the best of both worlds. For self-consistency, comparing whether the matrices generated are canonically equivalent and running comparisons between the two is helpful.

For encoding and decoding, we can use the already built encoders and decoders. Maybe we can prepare a feature issue which is about exploring the encoders and decoders and integrating them in the package. sagemath has a lot of python based encoders and decoders. Performance wise, maybe benchmarks between sagemath and Nemo in terms of code generation could be helpful as well.

Most of other pieces of software that may have codes functionality are proprietary. At the moment, I am not aware whether Maple, Mathematica, or Matlab has some of these codes, though I have seen Decoder Blocks for codes in Matlab.

[Fe-r-oz]

Also, sage/sagemath for coding theory: https://doc.sagemath.org/html/en/reference/coding/index.html

[Fe-r-oz]

Also,

• RPTU database for many types of LDPC codes: https://rptu.de/channel-codes/channel-codes-database
• GAP System: https://docs.gap-system.org/pkg/guava/doc/chap5.html#X87EB64ED831CCE99
• MAGMA computer algebra system(proprietary software): http://magma.maths.usyd.edu.au/magma/

[Fe-r-oz]

The GAP system(second bullet) is actually documentation for GUAVA(GAP): https://github.com/gap-packages/guava. They don't have many tests on codes though and package seems unstable with no CI and less test coverage.