Characteristic vector and weight distribution of a linear code
- PDF / 1,110,833 Bytes
- 20 Pages / 439.642 x 666.49 pts Page_size
- 74 Downloads / 193 Views
Characteristic vector and weight distribution of a linear code Iliya Bouyukliev1 · Stefka Bouyuklieva2
· Tatsuya Maruta3 · Paskal Piperkov1
Received: 15 December 2019 / Accepted: 24 September 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract An algorithm for computing the weight distribution of a linear [n, k] code over a finite field Fq is developed. The codes are represented by their characteristic vector with respect to a given generator matrix and a generator matrix of the k-dimensional simplex code Sq,k . Keywords Linear code · Weight distribution · Walsh transform Mathematics Subject Classification (2010) 94B05 · 15B36 · 11Y16
1 Introduction Many problems in coding theory require efficient computing of the weight distribution of a given linear code. Some sufficient conditions for a linear code to be good or proper for error detection are expressed in terms of the weight distribution [13]. The weight distribution of the hull of a code provides a signature and the same signature computed for any permutation-equivalent code will allow the reconstruction of the permutation [31]. The weight distributions of codes can be used to compute some characteristics of the Boolean and vectorial Boolean functions [10]. Stefka Bouyuklieva
[email protected] Iliya Bouyukliev [email protected] Tatsuya Maruta [email protected] Paskal Piperkov [email protected] 1
Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, P.O. Box 323, Veliko Tarnovo, Bulgaria
2
Faculty of Mathematics and Informatics, St. Cyril and St. Methodius University of Veliko Tarnovo, Veliko Tarnovo, Bulgaria
3
Department of Mathematical Sciences, Osaka Prefecture University, Sakai, Osaka, 599-8531, Japan
Cryptography and Communications
In 1978, Berlekamp, McEliece, and van Tilborg [3] proved that two fundamental problems in coding theory, namely maximum-likelihood decoding and computation of the weight distribution, are NP-hard for the class of binary linear codes. The formal statement of the corresponding decision problem is [33] Problem: WEIGHT DISTRIBUTION Instance A binary m × n matrix H and an integer w > 0. Question: Is there a vector x∈ Fn2 of weight w, such that H x T = 0? Berlekamp, McEliece, and van Tilborg [3] proved that this problem is NP-complete. Nevertheless, many algorithms for calculating the weight distribution have been developed. Some of them are implemented in the software systems related to Coding theory, such as MAGMA, GUAVA, Q-EXTENSION, etc. [1, 7, 8]. The main idea in the common algorithms is to obtain all linear combinations of the basis vectors and to calculate their weights. The efficient algorithms generate all codewords in a sequence, where any codeword is obtained from the previous one by adding only one codeword. They usually use q-ary Gray codes (see for example [18]) or an additional matrix (see [9]). The complexity of these algorithms is O(nq k ) for a fixed q. Katsman and Tsfasman in [25] proposed a geometric method based on algebraic-geomet
Data Loading...
