Publication Details:
"ՀՀ ԳԱԱ Զեկույցներ" հանդեսը հիմնադրվել է 1944թ.: Լույս է տեսնում տարին 4 անգամ:
Journal or Publication Title:
ՀՀ ԳԱԱ Զեկույցներ = Доклады НАН РА = Reports NAS RA
Date of publication:
Volume:
Number:
ISSN:
Official URL:
Additional Information:
Title:
Complexity of Elias Algorithm for Hash Functions Based on Hamming and Extended Hamming Codes
Other title:
Creator:
L. H. Aslanyan ; H. E. Danoyan
Contributor(s):
Պատ․ խմբ.՝ Վ. Հ․ Համբարձումյան (1944-1959) ; Մ․ Մ․ Ջրբաշյան (1960-1965) ; Ա․ Գ․ Նազարով (1966-1983) ; Պատ․ խմբ․ տեղակալ՝ Վ․ Հ․ Ղազարյան (1983-1986) ; Պատ․ խմբ․՝ Դ․ Մ․ Սեդրակյան (1987-1999) ; Գլխավոր խմբ․՝ Ս․ Ա․ Համբարձումյան (2000-2004) ; Վ․ Ս․ Զաքարյան (2005-2018) ; Ռ․ Մ․ Մարտիրոսյան (2018-)
Subject:
Uncontrolled Keywords:
best match ; nearest neighbors ; search algorithm ; Elias algorithm ; quasi-perfect codes ; generalizations of perfect codes
Coverage:
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-мерного единичного куба с непересекающими шарами равного радиуса. Такие покрытия получаются с помощью совершенных кодов. Поскольку такие покрытия существуют в единичных случаях, мы рассматриваем покрытия с пересекающми шарами равного радиуса. Такие покрытия в частности получаются с помощью квазисовершенных кодов. Приведена формула сложности алгоритма для случая расширенных кодов Хемминга.
Place of publishing:
Երևան
Publisher:
Date created:
Type:
Format:
Call number:
Digitization:
ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան