COMPLEXITY OF ELIAS ALGORITHM BASED ON CODES WITH COVERING RADIUS THREE

L.H. Aslanyan; H.E. Danoyan

doi:10.46991/PYSU:A/2013.47.1.044

COMPLEXITY OF ELIAS ALGORITHM BASED ON CODES WITH COVERING RADIUS THREE

Authors

L.H. Aslanyan Institute of Informatics and Automation Problems of NAS RA
H.E. Danoyan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia

DOI:

https://doi.org/10.46991/PYSU:A/2013.47.1.044

Keywords:

nearest neighbors, best match, Eleas algorithm, hash functions, quasiperfect codes, uniformly packed codes, coset weight distribution

Abstract

The algorithm for finding the set of ”nearest neighbors” in a set using compact blocks and hash functions is known (Elias algorithm). In this paper hash coding schemas associated to coverings by spheres of the same radius are considered. In general, such coverings can be obtained via perfect codes, and some other generalizations of perfect codes such as uniformly packed or quasi perfect codes. We consider the mentioned algorithm for Golay code and for two-error-correcting primitive BCH codes of lenght $2^m-1$ for odd $m$. A formula of time complexity of the algorithm is obtained in these cases.

Downloads

Published

2013-04-10

How to Cite

Aslanyan, L., & Danoyan, H. (2013). COMPLEXITY OF ELIAS ALGORITHM BASED ON CODES WITH COVERING RADIUS THREE. Proceedings of the YSU A: Physical and Mathematical Sciences, 47(1 (230), 44–50. https://doi.org/10.46991/PYSU:A/2013.47.1.044