Publication Details:

"ՀՀ ԳԱԱ Զեկույցներ" հանդեսը հիմնադրվել է 1944թ.: Լույս է տեսնում տարին 4 անգամ:

Journal or Publication Title:

ՀՀ ԳԱԱ Զեկույցներ = Доклады НАН РА = Reports NAS RA

Date of publication:

2013

Volume:

113

Number:

2

ISSN:

0321-1339

Official URL:

Additional Information:

click here to follow the link

Other title:

Էլիասի ալգորիթմի բարդությունը Հեմմինգի և ընդլայնված Հեմմինգի կոդերով սահմանված հաշ-ֆունկցիաների համար / Լ. Հ. Ասլանյան, Հ. Է. Դանոյան։ Сложность алгоритма Элиаса для хеш-функциий определенных кодами Хемминга и расширенными кодами Хемминга / Л. А. Асланян, А. Э. Даноян.

Contributor(s):

Պատ․ խմբ.՝ Վ. Հ․ Համբարձումյան (1944-1959) ; Մ․ Մ․ Ջրբաշյան (1960-1965) ; Ա․ Գ․ Նազարով (1966-1983) ; Պատ․ խմբ․ տեղակալ՝ Վ․ Հ․ Ղազարյան (1983-1986) ; Պատ․ խմբ․՝ Դ․ Մ․ Սեդրակյան (1987-1999) ; Գլխավոր խմբ․՝ Ս․ Ա․ Համբարձումյան (2000-2004) ; Վ․ Ս․ Զաքարյան (2005-2018) ; Ռ․ Մ․ Մարտիրոսյան (2018-)

Coverage:

150-157

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:

2013-06-15

Format:

pdf

Identifier:

oai:arar.sci.am:46585

Call number:

АЖ 144

Digitization:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան

Location of original object:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան