A note on reducing the computation time for minimum distance and equivalence check of binary linear codes

Nikolay Yankov, Krassimir Enev

Abstract


In this paper we show the usability of the Gray code with constant weight words for computing linear combinations of codewords.
This can lead to a big improvement of the computation time for finding the minimum distance of a code.

We have also considered the usefulness of combinatorial 2-(t,k,1) designs when there are memory limitations to the number of objects (linear codes in particular) that can be tested for equivalence.


Keywords


Classification; Combinatorial design; Linear code

Full Text:

PDF

References


R.T. Bilous (2006) Enumeration of the binary self-dual codes of length 34, Journal of Combinatorial Mathematics and Combinatorial Computing, 59, 173--211.

R.T. Bilous, G.H.J Van Rees (2002) An enumeration of binary self-dual codes of length 32, Designs, Codes and Cryptography,26, 61--86.

J.R. Bitner, G. Ehrlich, E.M. Reingold (1975) Efficient Generation of the Binary Reflected Gray Code and Its Applications, Commun. ACM, 19(9), 517--521.

I. Bouyukliev, M. Dzhumalieva-Stoeva, V. Monev (2015) Classification of Binary Self-Dual Codes of Length 40, IEEE Transactions on Information Theory, 61(8), 4253--4258.

S. Bouyuklieva, I. Bouyukliev (2012) An Algorithm for Classification of Binary Self-Dual Codes, IEEE Transactions on Information Theory, 58(6), 3933--3940.

C.J. Colbourn, J.H. Dinitz, Handbook of Combinatorial Designs, 2nd ed., CRC Press, 2010, ISBN 978-1-5848-8-5061.

J.H Conway, V. Pless, N.J.A. Sloane (1992) The binary self-dual codes of length up to 32: A revised enumeration, Journal of Combinatorial Theory, Series A, 60(2), 183--195.

F. Gray (1953) Pulse code communication, U.S. Patent 2,632,058, March 17, 1953

M. Harada, A. Munemasa (2010) Classification of self-dual codes of length 36, Advances in Mathematics of Communications, 2, 229--235.

W.C. Huffman, V.S. Pless (2003) Fundamentals of Error-Correcting Codes, Cambridge University Press, ISBN 978-0-5211-3-1704.

V. Pless (1972) A classification of self-orthogonal codes over $GF(2)$, Discrete Mathematics, 3(1-3), 209--246.

D.T. Tang, C.N. Liu (1973) Distance-2 cyclic chaining of constant-weight codes, IEEE Transactions on Computers, 2, 176--180.

V. Tonchev (2017) On resolvable Steiner 2-designs and maximal arcs in projective planes, Designs, Codes and Cryptography, 84(1-2), pp 165--172.


Refbacks

  • There are currently no refbacks.
We use cookies.