Home >  Results  >  Linear codes  > 

Computing Codes Covering

One of the main problems in the field of digital technologies is related to the protection of information. Coding aims to protect information on communication channels and when it is stored on different media. A key parameter for error-correction and error-detection code is its covering radius. It provides information about whether the code is suitable for use in data compression and anti-noise coding algorithms. It is also used in linear code generation and classification algorithms. The task of finding a covering radius is NP-complete, which makes it suitable for parallel implementation using high-performance systems (HPC). The main task of the current project is the development of a parallel implementation of an algorithm for calculating the covering radius of linear codes. The task consists of two basic components: learning methods for finding the covering radius and efficient use of modern high-performance computing techniques. One approach to finding the covering radius uses the column vectors of the code's parity-check matrix. The main computational resource for this method implements operations on vectors over finite fields. This makes it suitable for parallelization via extended vector registers that are available in modern CPUs. The developed HPC algorithms can be used to determine optimal codes with good covering radius. The main goals of the project are:


Results

We have developed three implementations of algorithm for computation of covering radius of a linear codes and the weight distribution of the coset leaders: for shared memory systems using the Open Multi-Processing (OpenMP) application programming interface, for distributed memory systems using Message Passing Interface (MPI) and a hybrid version. All implementations also use extended vector registers with AVX2 instruction set that give additional speedup. We compare the execution times of these implementations on two different hardware platforms. The developed parallel implementation are used to compute the covering radius of strongly optimal self-orthogonal linear codes over GF(3) and a length of up to 30.
We have also implemented a optimized and vectorized algorithm for computing the coverig radius of linear codes using the generator matrix of its dual code. Using this algorithm we computed the covering radius of [13,5,8] NMDS codes over GF(7).



Acknowledgments:

This work is funded by the European Union - NextGen- erationEU under contract BG-RRP-2.015-0001-C01.

Acknowledgments Acknowledgments