Parallel Implementations for Computing the Minimum Distance of a Random Linear Code on Multicomputers
Preprint
Abstract
The minimum distance of a linear code is a key concept in information theory. Therefore, the time required by its computation is very important to many problems in this area. In this paper, we introduce a family of implementations of the Brouwer-Zimmermann algorithm for distributed-memory architectures for computing the minimum distance of a random linear code over F2. Both current commercial and public-domain software only work on either unicore architectures or shared-memory architectures, which are limited in the number of cores/processors employed in the computation. Our implementations focus on distributed-memory architectures, thus being able to employ hundreds or even thousands of cores in the computation of the minimum distance. Our experimental results show that our implementations are much faster, even up to several orders of magnitude, than current implementations widely used nowadays.Keywords
All Related Versions
This publication has 3 references indexed in Scilit:
- Relative Generalized Hamming Weights of One-Point Algebraic Geometric CodesIEEE Transactions on Information Theory, 2014
- Compression of binary sources with side information at the decoder using LDPC codesIEEE Communications Letters, 2002
- The intractability of computing the minimum distance of a codeIEEE Transactions on Information Theory, 1997