Geodesic
Complexity of Elias algorithm based on codes with covering radius three
Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 1 (2013), pp. 44-50

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: nearest neighbors, best match, Eleas algorithm, hash functions, uniformly packed codes, coset weight distribution.
Mots-clés : quasiperfect codes 
@article{UZERU_2013_1_a7,
     author = {L. H. Aslanyan and H. E. Danoyan},
     title = {Complexity of {Elias} algorithm based on codes with covering radius three},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {44--50},
     publisher = {mathdoc},
     number = {1},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2013_1_a7/}
}
TY  - JOUR
AU  - L. H. Aslanyan
AU  - H. E. Danoyan
TI  - Complexity of Elias algorithm based on codes with covering radius three
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2013
SP  - 44
EP  - 50
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2013_1_a7/
LA  - en
ID  - UZERU_2013_1_a7
ER  - 
%0 Journal Article
%A L. H. Aslanyan
%A H. E. Danoyan
%T Complexity of Elias algorithm based on codes with covering radius three
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2013
%P 44-50
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2013_1_a7/
%G en
%F UZERU_2013_1_a7
L. H. Aslanyan; H. E. Danoyan. Complexity of Elias algorithm based on codes with covering radius three. Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 1 (2013), pp. 44-50. http://geodesic.mathdoc.fr/item/UZERU_2013_1_a7/