Refinements of Levenshtein bounds in q-ary Hamming spaces

DOI10.1134/S0032946018040026zbMATH Open1471.94026arXiv1801.01982OpenAlexW2964264560MaRDI QIDQ2278701FDOQ2278701

Authors: Danyo Danev, Peter Boyvalenkov, M. M. Stoyanova 

Publication date: 10 December 2019

Published in: Problems of Information Transmission (Search for Journal in Brave)

Abstract: We develop refinements of the Levenshtein bound in $q$-ary Hamming spaces by taking into account the discrete nature of the distances versus the continuous behavior of certain parameters used by Levenshtein. The first relevant cases are investigated in detail and new bounds are presented. In particular, we derive generalizations and $q$-ary analogs of a MacEliece bound. We provide evidence that our approach is as good as the complete linear programming and discuss how faster are our calculations. Finally, we present a table with parameters of codes which, if exist, would attain our bounds.

Full work available at URL: https://arxiv.org/abs/1801.01982

Recommendations

• New upper bounds on Lee codes
• Some new bounds for q-ary linear block codes
• Improving the Gilbert-Varshamov bound for \(q\)-ary codes
• Improving the Gilbert–Varshamov Bound for<tex>$q$</tex>-Ary Codes
• Some remarks on the Plotkin bound

zbMATH Keywords

asymptotic boundsLevenshtein boundgeneral LP bound

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Linear codes (general theory) (94B05) Bounds on codes (94B65)

Cites Work

• Title not available (Why is that?)
• Orthogonal arrays. Theory and applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Association schemes and coding theory
• Title not available (Why is that?)
• Bounds for binary codes of length less than 25
• A class of low-rate nonlinear binary codes
• New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
• A table of upper bounds for binary codes
• New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming
• Spectral approach to linear programming bounds on codes
• Title not available (Why is that?)
• Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces
• Title not available (Why is that?)
• On integral zeros of Krawtchouk polynomials
• On the optimum of Delsarte's linear program
• Designs as maximum codes in polynomial metric spaces
• On linear programming bounds for codes in polynomial metric spaces
• Linear programming bounds for codes of small size
• Bounds for binary codes just outside the plotkin range
• Semidefinite bounds for nonbinary codes based on quadruples
• Numerical results on the asymptotic rate of binary codes
• Linear spaces of quadrics and new good codes
• Title not available (Why is that?)

Cited In (2)

• High-dimensional sphere packing and the modular bootstrap
• On Rosenbloom and Tsfasman's generalization of the Hamming space

Uses Software

• SageMath

This page was built for publication: Refinements of Levenshtein bounds in \(q\)-ary Hamming spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2278701)