zbMATH — the first resource for mathematics

Hamming distances from a function to all codewords of a generalized Reed-Muller code of order one. (English) Zbl 1386.94099
Summary: For any finite field \(\mathbb {F}_q\) with \(q\) elements, we study the set \(\mathcal {F}_{(q,m)}\) of functions from \(\mathbb {F}_q^m\) into \(\mathbb {F}_q\) from geometric, analytic and algorithmic points of view. We determine a linear system of \(q^{m+1}\) equations and \(q^{m+1}\) unknowns, which has for unique solution the Hamming distances of a function in \(\mathcal {F}_{(q,m)}\) to all the affine functions. Moreover, we introduce a Fourier-like transform which allows us to compute all these distances at a cost \(O(mq^m)\) and which would be useful for further problems.
94B05 Linear codes, general
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
Full Text: DOI arXiv
[1] Ashikhmin, A; Litsyn, S, Fast decoding of non-binary first order Reed-muller codes, AAECC, 7, 299-308, (1996) · Zbl 0858.94027
[2] Colbourn, C., Dinitz, H. (eds.): Handbook of Combinatorial Designs. Discrete Mathematics and its Applications, 2nd edn. Chapman and Hall/CRC, Boca Raton (2007) · Zbl 1101.05001
[3] Lachaud, G; Wolfmann, J, The weights of the orthogonals of the extended quadratic binary Goppa codes, IEEE Tans. Inf. Theory, 36, 686-692, (1990) · Zbl 0703.94011
[4] Langevin, P.: Rayon de Recouvrement des Codes de Reed-Muller Affines. Ph.D. Thesis, Université de Limoges (1992)
[5] Langevin, P.: On the Orphans and Covering Radius of the Reed-Muller Codes. Lecture Notes in Computer Sciences, vol. 539. Springer, Berlin (1991) · Zbl 0767.94008
[6] Leducq, E, On the covering radius of first order generalized Reed-muller codes, IEEE Trans. Inf. Theory, 59, 1590-1596, (2013) · Zbl 1364.94678
[7] Mc Eliece, RJ, Quadratic forms over finite fields and second order Reed-muller codes, JPL Sp. Pograms Summ., III, 37-58, (1969)
[8] Rolland, R.: Fonction maximalement non linéaires sur un corps fini. Technical Report 25, Institut de Mathématiques de Luminy (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.