|
Proceedings of the Yerevan State University, series Physical and Mathematical Sciences, 2013, Issue 1, Pages 44–50
(Mi uzeru109)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Informatics
Complexity of Elias algorithm based on codes with covering radius three
L. H. Aslanyana, H. E. Danoyanb a Institute for Informatics and Automation Problems of National Academy of Science of the Republic of Armenia
b Yerevan State University
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.
Keywords:
nearest neighbors, best match, Eleas algorithm, hash functions, quasiperfect codes, uniformly packed codes, coset weight distribution.
Received: 28.02.2013 Accepted: 25.03.2013
Citation:
L. H. Aslanyan, H. E. Danoyan, “Complexity of Elias algorithm based on codes with covering radius three”, Proceedings of the YSU, Physical and Mathematical Sciences, 2013, no. 1, 44–50
Linking options:
https://www.mathnet.ru/eng/uzeru109 https://www.mathnet.ru/eng/uzeru/y2013/i1/p44
|
Statistics & downloads: |
Abstract page: | 78 | Full-text PDF : | 22 | References: | 26 |
|