ՀՀ ԳԱԱ Զեկույցներ =Reports NAS RA

Complexity of Elias Algorithm for Hash Functions Based on Hamming and Extended Hamming Codes

Aslanyan, L. H. and Danoyan, H. E. (2013) Complexity of Elias Algorithm for Hash Functions Based on Hamming and Extended Hamming Codes. ՀՀ ԳԱԱ Զեկույցներ, 113 (2). pp. 150-157. ISSN 0321-1339

[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
355Kb

Abstract

The procedure of finding the set of all “nearest neighbors” in a set, known as the Elias algorithm is addressed. In connection to it the hash coding schemes associated with the n-dimensional unit cube coverings by non-intersecting spheres of the same radius is considered. Such coverings, in particular, can be obtained via perfect codes. We get a formula presentation for complexity of the search algorithm in case of Hamming codes. As such coverings are possible in very simple cases and we consider coverings by intersecting spheres of the same radius. These can be obtained via quasiperfect codes. A formula of complexity of algorithm for extended Hamming codes is obtained as. Ուսումնասիրման առարկան բազմության տրված էլեմենտի «ամենամոտ հարևանների» գտնելու հայտնի Էլիասի ալգորիթմն է: Դրա հետ կապված դիտարկվում են հաշ-կոդավորման սխեմաներ՝ ասոցիացված n-չափանի միավոր խորանարդի՝ միևնույն շառավղով չհատվող գնդերով ծածկույթների հետ: Այդպիսի ծածկույթներ ստացվում են կատարյալ կոդերի միջոցով: Բերված է որոնման ալգորիթմի բարդության բանաձև Հեմմինգի կոդի դեպքում: Քանի որ նման ծածկուլթներ գոյություն ունեն եզակի դեպքերում, դիտարկում ենք նաև ծածկույթներ միևնույն շառավղով հատվող գնդերի տեսքով: Այդպիսի ծածկույթներ մասնավորապես ստացվում են քվազիկատարյալ կոդերի միջոցով: Բերված է ալգորիթմի բարդության բանաձև ընդլայնված Հեմմինգի կոդի դեպքում: Известен алгоритм нахождения всех «ближайших соседей» к данной точке из данного множества. В связи с этим рассматриваются схемы хеш-кодирования, ассоцированные с покрытиями n-мерного единичного куба с непересекающими шарами равного радиуса. Такие покрытия получаются с помощью совершенных кодов. Поскольку такие покрытия существуют в единичных случаях, мы рассматриваем покрытия с пересекающми шарами равного радиуса. Такие покрытия в частности получаются с помощью квазисовершенных кодов. Приведена формула сложности алгоритма для случая расширенных кодов Хемминга.

Item Type:Article
Additional Information:Էլիասի ալգորիթմի բարդությունը Հեմմինգի և ընդլայնված Հեմմինգի կոդերով սահմանված հաշ-ֆունկցիաների համար / Լ. Հ. Ասլանյան, Հ. Է. Դանոյան։ Сложность алгоритма Элиаса для хеш-функциий определенных кодами Хемминга и расширенными кодами Хемминга / Л. А. Асланян, А. Э. Даноян.
Uncontrolled Keywords:best match, nearest neighbors, search algorithm, Elias algorithm, quasi-perfect codes, generalizations of perfect codes
Subjects:Q Science > QA Mathematics
ID Code:6122
Deposited By:NAS Reports
Deposited On:28 Aug 2013 12:58
Last Modified:13 Mar 2014 08:16

Repository Staff Only: item control page