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:

• adding classical extended-Reed-Solomon-MDS codes to the ECC Module #254
• Adding classical Convolutional code to the ECC module #256
• Adding classical Bose–Chaudhuri–Hocquenghem code to ECC module #263
• Adding classical Goppa codes to the ECC Module #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.