Month: August 2016

Sage Project Log

In order to help plan better, work in a more structured fashion and have a record of the work we did during the GSoC 2016 in Sage, we maintained a daily project log. This was institutionalised starting with Week 4 and we reproduce the log below.

Week 12:

16th, 17th August:

  1. Made all the remaining changes, and pushed the changes to the Gabidulin Ticket. Added the code to the catalog files. There are a couple of issues that need to be resolved based on feedback and then the changes can be made. Commit can be found here.
  2. Started writing documentation for the ARMC class. Will push everything I have on that on 18th.
  3. Created three new tickets for the stuff left over from the original 13215 ticket and pushed all the relevant code.
  4. Started preparing presentation for Sage Days 75. Will share the first draft of outline and ideas on 18th.

15th August:

  1. Finished writing documentation and tests for #20970. Finished channel class for the code. After one final pass, will push everything on 16th. There are two tiny issues. One is given a matrix in Sage, how to find a specific non-trivial solution for it. I.e. for matrix A, find non-trivial x_0 s.t. A*x_0 = 0. Currently, the parity evaluation points method is failing because of this. This also causes the channel to fail at times. And the second is suggestions for better names in a couple of places.
  2. Created the second ticket from the leftover stuff from #13215. Will push karatsuba and centering tickets on 16th and the last one as well if possible. Otherwise, this will be done by 17th.
  3. Updates to the ARMC class. Specifically, adding documentation and tests, and fixing some bugs that were causing incompatibility issues with the Gabidulin Code class.

11th, 12th August:

  1. Made changes to 21131. It is open for review.
  2. Made changes to finite field ticket. It is open for review. 21088
  3. Solved some pickling errors and other comments by Travis. The remaining ones are due to Frobenius it seems. Once it’s decided, whether or not to add experimental decorator, I will update it. Almost open for review.
  4. Gabidulin, channel class ready. After one final pass, that ticket will be ready to be done.
  5. Prepared Tickets C and D. Will create them and push after one final pass.
  6. Weight enumerator and additional methods in ARMC.

9th, 10th August:

  1. Created rank_metric.py. Deleted methods according to discussions based on recommended schema. Verified docstrings of inherited methods. Worked on rank support and weight enumerator. Started testing a little. Stuff is not working correctly. Hence the delay in pushing.
  2. Gabidulin inherits from this. Removed rank related methods from there. Made that compatible with this.
  3. 21088 – finite fields ticket. nearly done. Will push that tomorrow.
  4. Made changes to 21131 as per discussion
  5. Created Ticket C (karatsuba stuff).

Week 11:

8th August:

  1. Further fixes to 13215. (1.5 hrs)
  2. Worked on the channel class. But in order to use that in the way David mentioned, I need random element. So I figured it would be better to have a few methods of the ARMC class implemented first. Added new file, inherits from ALC. Basic getter methods, moved matrix to vector and vice versa from Gab. Random element. And Gab inherits from ARMC. (6hrs)
  3. Worked on the 21131 ticket. That’s now open for review. (4hrs)

4th August:

  1. Wrote channel class for Gabidulin code. Testing continued. Added some checks. Started adding final documentation for every method. (~5hrs)
  2. Moved MPE to skew poly. Continued with MVP and interpolation based on comments on trac. (~2.5hrs)

3rd August:

  1. Made changes based on comments by Jeroen on Ticket #13215 (~4.5hrs)
  2. Fixed Gao Decoder. Edited the construction of Gabidulin Codes to include twist homomorphism. (~3hrs)
  3. Made changes to #21131 based on latest comments. (~2hrs)

Week 10:

28th, 29th July:

  1. Worked on Ticket #21088. Commits can be found here.
  2. Worked on Ticket #21131. Commits can be found here.

27th July:

  1. Worked on the comments and discussions on Ticket 13215. (~6hrs)
  2. Rewrote and am testing ticket 21088. (~2hrs)

26th July:

  1. Fixed documentation build errors from 13215. (~3hrs)
  2. Added documentation for interpolation, MSP and MPE. Added documentation for Gao decoder in Gabidulin Codes. (~1.5hrs)
  3. Worked on additional polishing of Ticket 13215 based these comments. (~3hrs)

25th July:

  1. Resolved single and double backtick inconsistencies from the various files of ticket 13215. Replaced method _cmp_ with _richcmp_ based on recommendations from mentors. removed some latex imports. Commits can be found here. (~3hrs)
  2. Worked on adding minimum subspace polynomial, multi-point evaluation and interpolation methods for Ticket 21088. Fixed the various bugs and incompatibility errors. Commit can be found here. (~4hrs)
  3. Added documentation and tests for the Gabidulin Code class. Will proceed with the verification of Gao decoder implementation once MPE, MSP and Interpolation are resolved. (~1hr)

Week 9:

20th, 21st, 22nd July:

  1. Several threads of discussion regarding the Ticket A were discussed and worked upon. These changes which included removing double imports and unused classes and methods, adding a section in the index file for documentation, improved module description and definition, across various files and finally documentation, tests and code clean up. The commits can be found here.
  2. Created ticket B based on past discussions and pushed changes. Added documentation, tests, fixed doctests and removed unused methods. The ticket can be found here.
  3. Worked on the Gao Formulation decoder for the Gabidulin Code class.

19th July:

  1. Noted down comments from the review of Ticket #13215 and implemented most of the changes. Once the doubts are clarified tomorrow, I’ll submit the edits. (~4hrs)
  2. Started working on Ticket B and comparing with its “polynomial” equivalent to identify the problem areas. (~2hrs)

18th July:

  1. Fixed final documentation, tests and errors. Cleaned up code and pushed changes. (~5hrs)
  2. Edited Gabidulin Codes to adapt to the updated 13215 ticket. Pending: edit minimum subspace polynomial and multi-point evaluation.(~2hrs)
  3. Started preparing creation of Ticket B. (~1hr)

Week 8:

16th July:

  1. Picked up from the pending work from Friday (yesterday). Added all remaining documentation to the skew_polynomial_element.pyx file. Added all missing tests. (~2.5hrs)
  2. Fixed errors in implementation of a couple of methods (is_gen, section). (0.5hrs)
    Phased out side from the _pow_ function. (~1hr)
  3. Added small tests and fixes to skew_polynomial_ring_constructor.py. (~1hr) [Only documentation and a couple of tiny methods remain to be added for the Class SkewPolynomialRing_general. Should not take more than an hour or two. Will try and finish this on Sunday. If not, first thing on Monday.]

15th July:

  1. Went through the skew_polynomial_element.pyx, skew_polynomial_ring.py and skew_polynomial_ring_constructor.py file to identify the remaining tasks so as to reach the “needs review” state. (~2hrs)
  2. Added missing methods in skew_polynomial_element.pyx based on discussions. (~2hrs)
  3. Added documentation for some private methods. (~1hr)

14th July:

  1. Cleaned up code, refactored and added some tests and documentation in the skew_polynomial_element.pyx file. (~2hrs)
  2. Removed def gcd, xgcd, quo_rem and monic. Renamed lgcd as left_gcd and respectively for all other methods. (~2hrs)
  3. Phased out “side” arguments. (~1hr)
  4. Solved some bugs that had come up because of the edits and deletions made above. (~1hr)
  5. Went through “polynomial_element.pyx” to compare which methods were missing in the skew_polynomial_element.pyx file. Added some. (~2hrs)

13th July:

  1. Cleaned up, refactored and added some tests and documentation in the skew_polynomial_element.pyx file. (~2hrs)
  2. Implemented a special case of the is_unit method for skew polynomials. General case requires support for finding the order of automorphisms. (~1hr)
  3. Fixed the final remaining doctests. (~1hr)
  4. Finished setting up Sage in Emacs and Sage Notebook. Learning how to use them… (~2hrs)
  5. Started phasing out side.py in 13215. (~1hr)

12th July:

  1. Sorted out cherry pick and pushed changes here. (~1hr)
  2. Decided on the most primary cuts to form Ticket A (as per discussions). Pushed changes here. Other files such as side.py are kept for now and will be phased out during refactoring.(~2hrs)
  3. Fixed NotImplementedError and other standalone failing doctests from skew_polynomial_element.pyx. See commit here. 127 doctests remain. All of them are caused by some invalid homomorphism problem. Started looking into that. (~3.5hr)
  4. Started setting up sage-mode in Emacs and started acquainting myself with it. (~1hr)
    Cleaning up skew_polynomial_element.pyx. (~1 hr)

11th July:

  1. Prepared notes on the five-way split of the original 13215 ticket and discussed with mentors. (~3hrs)
  2. Set up sage notebook. It was giving some error with openssl and required it to be switched off. (~1hr)
  3. Using cherry-pick to add commits from public branch test_13215_interactive (not merging properly. it is giving some weird error with the test.sheet file. (~1hr)
    Running doctests on skew_polynomial_element file after the aforementioned commits gives 334 errors. Fixed some very simple basic ones just to see how I can proceed here. (~1hr).
  4. Started cutting away portions of 13215_original to form Ticket A. (~2 hrs)

10th July:

  1. Got an overview of the classes of the ticket and the dependencies between them.
  2. Noted down purpose of each. (~2hrs)
  3. Wrote down observations about what seems redundant and what needs work in every class. Also made a list of all the classes and methods and functions that have missing docstrings and doctests. (~2.5hrs)
  4. Started adding the missing tests and docs for the skew_polynomial_ring.py file. (~1hr)

Week 7:

9th July:

  1. Made final edits to the rank-metric conversion and properties. Wrote documentation and tests. Pushed commit here. (~1.5 hr)
  2. Removed some of the compile errors from the unencode_nocheck method and supporting methods. Finished writing multi_point_evaluation method. I was using the zero element of Fqm to initialize while I was actually supposed to use the zero element of the message_space (skew polynomial ring). Apart from the main error in #13215, the rest of these methods seem to have no errors. Will confirm once resolved. Pushed commit here (~3 hrs)
  3. Made final edits to the documentation and tests of the skew_polynomial_ring_constructor.py file from #13215. Ready to commit. (~1 hr)

8th July:

  1. Edited gabidulin.py based on comments.
  2. Continued writing interpolation of skew_polynomials.

7th July:

  1. Fixed one more of the two remaining errors in #13215. It seems that the ‘Left’ object has not been implemented in a lot of places in the skew polynomial ticket.
  2. Completed reading relevant sections of the paper mentioned below. Started writing code. Placing it in gabidulin.py for now.

6th July:

  1. Wrote conversion for matrix form back into vector form. Added support for computing rank-distance, rank-weight.
  2. Started reading this for how to interpolate a skew polynomial for the unencode and (future) decode methods.

5th July:

  1. Fixed the tiny compile errors that were induced in the Skew Poly ticket due to Sage upgrade.
  2. Testing of code that was written last Friday and Monday that had gone unchecked. Fixed errors.
  3. Wrote conversion into matrix form from vector form of a Gabidulin codeword. Takes a basis as argument.

4th July:

  1. Added support for generator matrix, dual code and parity check matrix of Gabidulin Code.

Week 6:

1st July:

  1. Continued porting to inheritance from SageObject.

30th June:

  1. Fixed bugs in the evaluation_points, encode, message_space and operator evaluation method for skew polynomials (this bit still needs more work).
  2. Based on discussions, removed inheritance of Gabidulin Code class from AbstractLinearCode class. Now moving towards a stand-alone class that inherits from SageObject.

29th June:

  1. Added support for the default option from below.
  2. Created a method for the “ext” function from Lemma 2.1 (of the PhD thesis) on Mapping to Ground Field.

28th June:

  1. Started adding some tests for the various methods.
  2. Added support for an optional argument that can be supplied to the constructor for the code. This allows them to provide a set of linearly independent elements of F_{q^m} over F_q if they choose. Need to add support for default option.

27th June:

  1. Continued working on constructing a codeword.
  2. Trying different input arguments to see which is most convenient to use and still allows flexibility for user.

Week 5:

24th June:

  1. Evaluated linearized polynomials (sample examples) at various random points.
  2. Called relative finite field extension ticket for the vectorial representation of big field in small field in an attempt to form a codeword. This is not working properly. But I think I should have something to present on Monday.

23rd June:

  1. Tested construction of linearized polynomials from skew polynomials. By putting in a zero derivation and a Frobenius endomorphism (for a finite field, Frobenius endomorphism is a Frobenius automorphism and hence this is a linearized polynomial ring), it seems to be constructing a ring. Will have to test addition and multiplication once the doctests are solved.

22nd June:

  1. Submitted Midterm Evaluation. Prepared blog post. Nearly ready to put it up.
  2. Read relevant sections of the following papers: Coding with Skew Polynomial Rings, Welch-Berlekamp Like Decoding Algorithm for Gabidulin Codes, Fast Encoding of Gabidulin Codes
    Started designing basic outline of gabidulin.py. Prepared classes for the Code, Encoder and Decoder. I will have a several more details in a design document by tomorrow.

21st June:

  1. Continued to fix errors. And pushed recent commits to Ticket 13215. Down to final 2 types of errors.

19th June:

  1. Caught a bug. Came down with a flu. Stuck in bed all day.

Week 4:

17th June:

  1. Continued fixing doctest errors. Relatively slow day, managed to get about 70 solved today. Still about 330 to go. Starting to get the hang of this now. I think.
  2. Started drawing up design document for Gabidulin codes. The aim is to try and get all the errors resolved by this weekend and scrub the patch and get it accepted by Monday.

16th June:

  1. Continued fixing doctest errors. Managed to get about 200 solved today. Still 400 to go.

15th June:

  1. Continued fixing doctest errors in the Skew Polynomial patch. Reported no_attribute_found errors in richcmp, init_cache, and other ValueErrors.
  2. Read the Skew Polynomials patch to try and understand what can be used and how for the construction of Gabidulin codes.

14th June:

  1. Began fixing doctest errors in the Skew Polynomial patch. There were about 650 errors to begin with.
  2. Solved some very simple errors such as Deprecation warnings, errors with “interrupt.pxi” etc. About 600 more to go.

13th June:

  1. Fixed Cython function declaration compile errors from Skew Polynomials patch.
  2. Pushed changes to Ticket #13215

12th June:

  1. Successfully merged Skew Polynomials patch on local system
  2. Fixed deprecated PY_NEW_SAME_TYPE and PY_TYPE_CHECK_EXACT

 

Project Linear Rank Metric Codes in Sage – GSoC 2016

 

Introduction:

This document is meant to be a reference for people who want to understand the work done on implementing Skew Polynomials and Rank Metric Codes in Sage as a part of this GSoC 2016 project. My mentors for this project are Johan Rosenkilde and David Lucas. This post provides a brief mathematical background, summary and status of the tickets related to the project and further links to detailed discussions and the code. It is assumed that the reader is familiar with the basic concepts of abstract algebra, coding theory and Sage itself.

Background:

A Skew Polynomial is given by the equation:

        F(X) = a_{n} \times X^{n} + ... + a_0

where the coefficients a_i \in R and X is a formal variable. Let R be a commutative ring equipped with an automorphism \sigma. Addition between two skew polynomials is defined by the usual addition operation and the modified multiplication is defined by the rule X \times a = \sigma(a) \times X for all a in R. Skew polynomials are thus non-commutative and the degree of a product is equal to the sum of the degrees of the factors. Then the ring of skew polynomials can be written as R[X, \sigma].

Linear Rank Metric Codes are linear error correcting codes over the rank-metric and not the Hamming metric. The distance between two matrices is defined as the rank of the difference between them. And this forms a metric. They are a way to build codes that can detect and correct multiple random rank errors. Gabidulin Codes are an example of linear rank metric codes.

A Gabidulin Code Gab[n, k] over \mathbb{F}_{q^m} of length n (at most m) and dimension k (at most n) is the set of all codewords, that are the evaluation of a skew polynomial f(x) belonging to the skew polynomial constructed over the base ring \mathbb{F}_{q^m} and the twisting automorphism \sigma.

        \text{Gab[n, k]} = \big\{ (f(g_0) f(g_1) ... f(g_{n-1})) = f(\textbf{g}) : \text{deg}(f(x)) < k \big\}

where the fixed evaluation points g_0, g_1,..., g_{n-1} are linearly independent over \mathbb{F}_{q}. These codes are the rank-metric equivalent of Reed Solomon Codes.

Implementation:

During the community bonding period, we started with a small fix to the wtdist_gap method from the module linear_code.py. This involved improving its documentation, changing to a better name and making the method private. We also opened a ticket for a new abstract class for Golay Codes. However, there was not enough time to finish this ticket since the coding period started. 

David had already implemented a class to manage representation of elements of a field extension into a smaller field. We went through the review checklist in Sage. This has now been merged into Sage.

Xavier Caruso had authored a ticket on Skew Polynomials about four years ago. This was not reviewed at the time. And the category framework in Sage underwent massive restructuring and change since then. As a result, this ticket was very incompatible. We first started by resolving the several hundred doctest errors some of which were due to deprecated syntax errors while others were more technical. This ticket was the most difficult and complicated module and it took a lot longer than originally anticipated. Debugging the code ended up breaking Sage several times before all originally present doctest errors were resolved. Once the ticket started working, a lot of the methods and classes still did not have proper documentation and/or tests and we added those. Since this was a huge ticket, we then decided to break it up into five smaller tickets based on the content and dependencies to make the work more manageable. We majorly refactored the code in the first ticket to make it cleaner and then added methods such as operator evaluation, interpolation, minimum vanishing polynomial, etc to the appropriate various classes. For the purposes of the other targets for the GSoC project, we practically needed only the first of the five tickets (mentioned above) which dealt with the basic implementation of skew polynomials and skew polynomial rings. So the primary focus has been to get that merged. The second ticket based on skew polynomials over finite fields has also been worked upon. The remaining three tickets were more or less lifted directly from the original skew polynomial ticket and no effort has been made yet to accommodate for changes to these.

We then created a new abstract base class for Gabidulin Codes and implemented Generator Matrix based and Skew Polynomial Evaluation based encoders for it. This module also included a Gao Decoder for the Gabidulin Code and a Channel class to introduce random rank errors. Along with all of this, basic getter methods and methods to compute some basic combinatorial properties were also implemented. 

Lastly, we worked on a new base class called AbstractLinearRankMetricCode that inherits from the AbstractLinearCode class and from which Gabidulin Code inherits. This class provides methods that are common to any Linear Rank Metric Code so as to facilitate the creation of other such codes. It also deletes those methods from the general linear code class that are not valid in the case of rank metric codes.

Current Status: The tickets related to skew polynomials, Gabidulin Codes and AbstractLinearRankMetricCode are currently still open. We believe that the skew polynomial ticket is almost ready to be merged into Sage. It has been well tested and we believe it is in stable condition. The Gabidulin Code ticket is not as rigorously tested and the Gao decoder in particular needs to be examined further. The completion of this ticket depends on the AbstractLinearRankMetricCode class which requires also requires some work.

I am currently attending Sage Days 75 in Paris to which I was invited by my mentors. We have coding sprints all week long and we aim to wrap up all of the starred tickets (see below) this week. The next section provides links to more elaborate details about the work done during the project.

Code:

All relevant tickets, bug reports and code commits can be found below:

  1. #20565 – Fix LinearCode.wtdist_gap method (enhancement)
  2. #20787* – A class to manage Golay Codes (new)
  3. #20284 – A class to manage representations of elements of field extensions (review)
  4. #13215* – Skew polynomials (enhancement)
  5. #21088* – A class for skew polynomials over finite fields (enhancement)
  6. #21131* – Interpolation/evaluation methods for skew polynomials (content)
  7. #21259* – Karatsuba-based methods for skew polynomials (content)
  8. #21262* – Center-related content for skew polynomials (content)
  9. #21264* – Factoring/irreducibility methods for skew polynomials (content)
  10. #20970* – A class for Gabidulin codes (feature)
  11. #21226* – An abstract class for rank-metric codes (feature)

Tickets in green represent merged code, tickets in blue represent mature code and the ones in brown represent immature tickets.

The daily project progress log that provides further details about the project can be found at the following link:

https://arpitdm.wordpress.com/sage-project-log/

The blog posts related to Sage can be found here:

https://arpitdm.wordpress.com/category/open-source/sage/