On Some Properties of Intersection and Union of Spheres in Hamming Metric
Keywords:
Nearest neighbors, best-match, Hamming spheres, concave function, quasi-perfect codeAbstract
The problems of intersection and union of spheres of the same radius in Hamming metric are considered. The formula for number of points in intersection is derived in case of two spheres. It is proved that three or more spheres of radius RC (covering radius of a code C) centered at points belonging to some quasi-perfect code C intersect at most at one point. It is also proved that the increase of cardinality of union of spheres of the same radius, depending on radius, is a concave function and can have at most one or two maximum values depending on length.
References
F. J. Mac Williams, N. J. A. Sloane, The Theory of Error-Correcting Codes, 1977.
I. Honkala, “On the intersection and unions of Hamming Spheres”, The Very Knowledge of Coding, pp. 70-81, 1987.
G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Covering Codes, 1997.
R.L. Rivest, “On the optimality of Elias's algorithm for performing best-match searches”, Information Processing, pp. 678-681, 1974.
Yu.Zhuravlev, Selected Scientific Works, (in russian), 1998.
L. Aslanyan, “Metric decompositions and the discrete isoperimetry”, IFAC Symposium on Manufacturing, Modelling, Management and Control, pp. 433-438, 2000.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
