Some new binary codes with improved minimum distances

Abstract: adfas

2010 MSC: 94B05, 94B65

Keywords: binary linear codes, quasi-cyclic codes, algorithms

1. Introduction

A binary linear [n, k, d] code is a k-dimensional subspace of GF(2)\(^n\), where n is the block
length, k the dimension of the code, and d is the minimum distance between any two codewords.
The minimum distance determines the error-correcting or error-detecting capability. Therefore, for a given block length n and dimension k, it is desired to have an [n, k, d] code with the minimum distance as large as possible. One of the most fundamental problems in coding theory is to construct codes with the best possible minimum distances. ** **

Grassl [11] maintains online code tables of linear codes for small block length n, code dimension k over small finite fields. The code tables contain both the lower bounds and upper bounds on the minimum distance. A code with a minimum distance meeting the upper bound is said to be optimal, while a code with a minimum distance meeting the lower bound is called best-known. The problem to construct codes with the best possible minimum distances is very difficult. For small code dimension k and short block length, it is possible to do computer exhaustive search for optimal or good codes. But when both the code dimension k and block length increase, it becomes intractable. The researchers turn to some promising subclasses of linear codes with rich mathematical structures to reduce the time complexity. During the last decades, the class of quasi-cyclic (QC) codes and quasi-twisted codes has been proved to contain a lot of good codes. With the help of modern computers, a lot of record-breaking QC codes have been constructed [ ].

2. Quasi-cyclic codes