A Construction of Binary Punctured Linear Codes and A Supporting Method for Best Code Search

Takuya OHARA
Makoto TAKITA
Masakatu MORII

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E105-A    No.3    pp.372-380
Publication Date: 2022/03/01
Publicized: 2021/09/14
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2021TAP0007
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Coding Theory
Keyword: 
best code,  modified code,  linear code,  weight distribution,  minimum distance,  

Full Text: FreePDF

Summary: 
Reduction of redundancy and improvement of error-correcting capability are essential research themes in the coding theory. The best known codes constructed in various ways are recorded in a database maintained by Markus Grassl. In this paper, we propose an algorithm to construct the best code using punctured codes and a supporting method for constructing the best codes. First, we define a new evaluation function to determine deletion bits and propose an algorithm for constructing punctured linear codes. 27 new best codes were constructed in the proposed algorithm, and 112 new best codes were constructed by further modifying those best codes. Secondly, we evaluate the possibility of increasing the minimum distance based on the relationship between code length, information length, and minimum distance. We narrowed down the target (n, k) code to try the best code search based on the evaluation and found 28 new best codes. We also propose a method to rapidly derive the minimum weight of the modified cyclic codes. A cyclic code loses its cyclic structure when it is modified, so we extend the k-sparse algorithm to use it for modified cyclic codes as well. The extended k-sparse algorithm is used to verify our newly constructed best code.