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/

[1] F.J. Mac-Williams, N.J. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, Amsterdam, 1977, 762 pp.

[2] V.A. Zinoviev, V.K. Leont’ev, “The Nonexistence of Perfect Codes Over Galois Fields”, Problems of Control and Info. Theory, 2:2 (1973), 123–132

[3] L.A. Bassalygo, G.V. Zaitsev, V.A. Zinoviev, “Uniformly Packed Codes”, Problemi Peredachi Informatsii, 10:1 (1974), 9–14 (in Russian) | MR | Zbl

[4] G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Covering codes, North-Holland Mathematical Library, Amsterdam, 1997, 542 pp. | MR | Zbl

[5] T. Baicheva, I. Bouyukliev, S. Dodunekov, “Binary and Ternary Linear Quasi-Perfect Codes with Small Dimensions”, Transactions of Information Theory, 54:9 (2008), 4335–4339 | DOI | MR | Zbl

[6] E.M. Gabidulin, A.A. Davydov, L.M. Tombak, “Linear Codes with Covering Radius 2 and Other New Covering Codes”, Transactions of Information Theory, 37:1 (1991), 219–224 | DOI | MR | Zbl

[7] A.A. Davydov, L.M. Tombak, “Quasiperfect Linear Binary odes with Distance 4 and Complete Caps in Projective Geometry”, Problemi Peredachi Informatsii, 25:4 (1989), 265–275 (in Russian) | MR | Zbl

[8] A.A. Davydov, A.Yu. Drozhzhina-Labinskaya, “Constructions, Families, and Tables of Binary Linear Covering Codes”, Transactions of Information Theory, 40:4 (1994), 1270–1279 | DOI | MR | Zbl

[9] T. Etzion, B. Mounits, “Quasi-Perfect Codes with Small Distance”, Transactions of Information Theory, 51:11 (2005), 3938–3946 | DOI | MR | Zbl

[10] T. Etzion, G. Greenberg, “Constructions for Perfect Mixed Codes and Other Covering Codes”, Transactions of Information Theory, 39:1 (1993), 209–214 | DOI | MR | Zbl

[11] D. Gorenstein, W. Peterson, N. Zierler, “Two Error-Correcting Bose-Chaudhuri Codes are Quasi Perfect”, Information and Control, 3:3 (1960), 291–294 | DOI | MR

[12] T. Kasami, S. Lin, W. Peterson, “Some Results on the Weight Distributions of BCH Codes”, Transactions of Information Theory, 12:2 (1966), 274–277

[13] P. Charpin, “Weight Distributions of Cosets of Two-Error-Correcting BCH Codes, Extended or Not”, Transactions of Information Theory, 40:5 (1994), 1425–1442 | DOI | MR | Zbl

[14] D.E. Knuth, The Art of Computer Programming, v. 3, Sorting and Searching, Addison-Wesley, Massachusetts, 1998, 780 pp. | MR

[15] R.L. Rivest, “On the Optimality of Elias’s Algorithm for Performing Best-Match Searches”, Information Processing, 1974, 678–681 | MR | Zbl

[16] L.H. Aslanyan, “The Discrete Isoperimetry Problem and Related Extremal Problems for Discrete Spaces”, Problemi Kibernetiki, 36 (1979), 85–128 (in Russian) | MR