Представление чисел в двухбазисных системах счисления
Вводяться двобазисні системи числення, що узагальнюють стандартні системи числення, основані на розкладанні чисел за степенями заданого базисного числа. Наведено результати, а також приклад застосування для кодування чисел і дерев. Розглянуто напрямки подальших досліджень. Запропоновано новий парале...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2013 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/86249 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Представление чисел в двухбазисных системах счисления / А.В. Анисимов // Кибернетика и системный анализ. — 2013. — Т. 49, № 4. — С. 17-28. — Бібліогр.: 17 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860130155529240576 |
|---|---|
| author | Анисимов, А.В. |
| author_facet | Анисимов, А.В. |
| citation_txt | Представление чисел в двухбазисных системах счисления / А.В. Анисимов // Кибернетика и системный анализ. — 2013. — Т. 49, № 4. — С. 17-28. — Бібліогр.: 17 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Вводяться двобазисні системи числення, що узагальнюють стандартні системи числення, основані на розкладанні чисел за степенями заданого базисного числа. Наведено результати, а також приклад застосування для кодування чисел і дерев. Розглянуто напрямки подальших досліджень. Запропоновано новий паралельний алгоритм модулярного піднесення до степеня. Вказано новий клас універсальних префіксних кодів.
Two-base numeration systems are introduced in the paper. They are generalizations of standard numeration systems, which are based on powers of a given radix. The results are reviewed and applications for encoding numbers and trees are given. Further research fields are outlined. A new parallel algorithm for modular exponentiation and new classes of prefix codes are presented.
|
| first_indexed | 2025-12-07T17:44:04Z |
| format | Article |
| fulltext |
ÓÄÊ 519.72
À.Â. ÀÍÈÑÈÌÎÂ
ÏÐÅÄÑÒÀÂËÅÍÈÅ ×ÈÑÅË Â ÄÂÓÕÁÀÇÈÑÍÛÕ
ÑÈÑÒÅÌÀÕ Ñ×ÈÑËÅÍÈß
Êëþ÷åâûå ñëîâà: ñèñòåìû ñ÷èñëåíèÿ, êîäèðîâàíèå ÷èñåë, äåðåâüÿ, ëèíåéíûå
ôîðìû, ðåêóðñèÿ, ïðåôèêñíûå êîäû.
ÂÂÅÄÅÍÈÅ
Ôîðìà ïðåäñòàâëåíèÿ ÷èñåë èãðàåò âàæíóþ ðîëü â êîìïüþòåðíîé ìàòåìàòèêå
è âî ìíîãîì îïðåäåëÿåò ýôôåêòèâíîñòü àëãîðèòìîâ îáðàáîòêè èíôîðìàöèè.
Íàèáîëåå èçâåñòíû òðàäèöèîííûå ïðåäñòàâëåíèÿ ÷èñåë â âèäå ðàçëîæåíèÿ ïî
ñòåïåíÿì çàäàííîãî áàçèñíîãî ÷èñëà. Àðõèòåêòóðà ñîâðåìåííûõ âû÷èñëèòåëü-
íûõ óñòðîéñòâ â îñíîâíîì áàçèðóåòñÿ íà äâîè÷íîé àðèôìåòèêå. Òàêæå ïðåä-
ñòàâëÿåò èíòåðåñ òðèòîâàÿ ñèñòåìà ñ÷èñëåíèÿ, èñïîëüçóþùàÿ â êà÷åñòâå áàçèñà
÷èñëî 3.  íàñòîÿùåå âðåìÿ äëÿ çàäà÷ ñæàòèÿ èíôîðìàöèè àêòèâíî èçó÷àåòñÿ
ïðåäñòàâëåíèe ÷èñåë â âèäå ñóìì ÷èñåë Ôèáîíà÷÷è [1–4].  äàííîé ñòàòüå
ðàçâèâàåòñÿ ïîäõîä ïðåäñòàâëåíèÿ ÷èñåë â äâóõáàçèñíûõ ñèñòåìàõ. Ñòàíäàð-
òíûå êëàññè÷åñêèå ñòåïåííûå, à òàêæå ìíîãèå äðóãèå èçâåñòíûå ñèñòåìû ñ÷èñëå-
íèÿ ÿâëÿþòñÿ ÷àñòíûì ñëó÷àåì òàêîãî ñïîñîáà çàäàíèÿ ÷èñåë.
Ïðåäñòàâèì äâóõáàçèñíîå ïðåäñòàâëåíèå ÷èñåë ñ èñïîëüçîâàíèåì ïðîñòûõ
èñõîäíûõ êîìïîíåíòîâ: äâóõ áåñêîíå÷íûõ ïîñëåäîâàòåëüíîñòåé ÷èñåë (áàçèñû)
è ëèíåéíûõ äâóõàðãóìåíòíûõ ôîðì îò ÷èñåë â ýòèõ ïîñëåäîâàòåëüíîñòÿõ. Ðåêóð-
ñèâíàÿ äåêîìïîçèöèÿ ïðîèçâîëüíîãî ÷èñëà â ëèíåéíûå áèíàðíûå ôîðìû â âû-
áðàííûõ áàçèñàõ îïðåäåëÿåò âèä çàäàíèÿ ÷èñëà.
Âû÷èñëèòåëüíîé ìîòèâàöèåé äâóõáàçèñíîãî ïðåäñòàâëåíèÿ ÷èñåë ñëóæèò
ïîèñê áàçèñíûõ ïîñëåäîâàòåëüíîñòåé, äëÿ ýëåìåíòîâ êîòîðûõ îïðåäåëåííûå âû-
÷èñëåíèÿ âûïîëíÿþòñÿ ýôôåêòèâíî. Òàêèì îáðàçîì, âû÷èñëåíèÿ äëÿ ïðîèçâîëü-
íûõ àðãóìåíòîâ â íåêîòîðûõ óäà÷íî âûáðàííûõ áàçèñàõ ìîãóò áûòü ñâåäåíû
ê áîëåå ïðîñòûì âû÷èñëåíèÿì.
Î÷åâèäíû ïðèìåíåíèÿ äâóõáàçèñíûõ ñèñòåì â êðèïòîãðàôèè.  ýòîì ñëó÷àå
áàçèñíûå ïîñëåäîâàòåëüíîñòè ãåíåðèðóþòñÿ ïî âûáðàííûì ñåêðåòíûì ïàðàìåò-
ðàì. ×èñëî êîäèðóåòñÿ èíäåêñàìè êëþ÷åâûõ ïîñëåäîâàòåëüíîñòåé, âîçíèêàþùèõ
ïðè ðåêóðñèâíîé äåêîìïîçèöèè. Tàêæå âîçìîæíû ïðèìåíåíèÿ äâóõáàçèñíûõ
ñèñòåì ïðè ïîñòðîåíèè ñàìîñèíõðîíèçèðóþùèõñÿ ïðåôèêñíûõ êîäîâ. Ïðè ñî-
îòâåòñòâóþùåì âûáîðå áàçèñíûõ ïîñëåäîâàòåëüíîñòåé âîçìîæíî êîíñòðóèðîâà-
íèå âû÷èñëèòåëüíûõ àðõèòåêòóð, êîòîðûå ðåàëèçóþò äâóõáàçèñíóþ àðèôìåòèêó.
ÄÂÓÕÁÀÇÈÑÍÛÅ ÑÈÑÒÅÌÛ Ñ×ÈÑËÅÍÈß
Âñå ðàññìàòðèâàåìûå â íàñòîÿùåé ñòàòüå ÷èñëà ïðèíàäëåæàò íàòóðàëüíîìó
ðÿäó. Äàëåå â òåêñòå ýòî ïðåäïîëàãàåòñÿ ïî óìîë÷àíèþ.
Ïóñòü U u u� 1 2, ,� è V v v� 1 2, ,� — äâå áåñêîíå÷íûå ïîñëåäîâàòåëüíîñòè
÷èñåë. Íàçîâåì èõ îðòîãîíàëüíûìè, åñëè HOÄ ( , )u vi i �1 äëÿ âñåõ i �1 2, ,�
 ýòîì ñëó÷àå èñïîëüçóåì îáîçíà÷åíèå u vi i� è U V� .
 íåêîòîðûõ ñëó÷àÿõ öåëåñîîáðàçíî äîáàâëÿòü â U è V íà÷àëüíóþ ïàðó u0 è
ñîîòâåòñòâåííî v0 íå îáÿçàòåëüíî âçàèìíî ïðîñòûõ ÷èñåë. Áîëåå òîãî, äîïóñ-
êàåòñÿ ñëó÷àé, êîãäà u0 0� . Îáîçíà÷èì � ìíîæåñòâî íàòóðàëüíûõ ÷èñåë ñ èñ-
êëþ÷åííûì íóëåì. Ïóñòü x ��.
Ïðåäñòàâëåíèå âèäà
x u vn n� �� �1 2 , (1)
ãäå u Un � , v Vn � , íàçîâåì ëèíåéíîé ( , )U V -ôîðìîé, à èíäåêñ n — ðàíãîì.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4 17
� À.Â. Àíèñèìîâ. 2013
Èç àëãîðèòìà Åâêëèäà íàõîæäåíèÿ HOÄ äâóõ ÷èñåë ñëåäóåò, ÷òî åñëè U V� ,
òî äëÿ ëþáîãî x ñóùåñòâóåò ïðåäñòàâëåíèå âèäà (1). Ñëåäóåò îòìåòèòü ñëó÷àé,
êîãäà �1 è � 2 — íåîòðèöàòåëüíûå ÷èñëà. Ïðåäñòàâëåíèå (1) íàçîâåì ïîëîæè-
òåëüíî îïðåäåëåííûì, åñëè �1 0� è � 2 0� . Çäåñü ðàññìàòðèâàþòñÿ òîëüêî ïîëî-
æèòåëüíî îïðåäåëåííûå ôîðìû ìàêñèìàëüíîãî ðàíãà n. Ïîýòîìó â äàëüíåéøåì
ïî óìîë÷àíèþ ïðåäïîëàãàåì, ÷òî âñå ðàññìàòðèâàåìûå ëèíåéíûå ôîðìû ïîëî-
æèòåëüíî îïðåäåëåííûå è èìåþò ìàêñèìàëüíûé ðàíã.
Ñðåäè âñåõ âîçìîæíûõ ïðåäñòàâëåíèé (1) ôèêñèðîâàííîãî ðàíãà n âûäåëèì
ôîðìó, ãäå êîýôôèöèåíò �1 ìàêñèìàëüíûé. Òàêîå ïðåäñòàâëåíèå íàçîâåì êàíî-
íè÷åñêèì. Èñïîëüçóÿ òîæäåñòâåííîå ïðåîáðàçîâàíèå x kv un n� � �( )�1
� ( )� 2 ku vn n , ïðåäñòàâëåíèå (1) âñåãäà ìîæíî ïðèâåñòè ê êàíîíè÷åñêîìó âèäó.
Ïîýòîìó â ìàêñèìàëüíîì êàíîíè÷åñêîì ( , )U V -ëèíåéíîì ïðåäñòàâëåíèè � 2
un .
Î÷åâèäíî, êàíîíè÷åñêîå ( , )U V -ëèíåéíîå ïðåäñòàâëåíèå ìàêñèìàëüíîãî ðàíãà
åäèíñòâåííîå. Îòìåòèì, ÷òî åñëè äëÿ ïðîèçâåäåíèÿ ÷èñåë u è v âûïîëíÿåòñÿ íå-
ðàâåíñòâî uv x
, òî äëÿ x âñåãäà ñóùåñòâóåò ïîëîæèòåëüíî-îïðåäåëåííîå ïðåä-
ñòàâëåíèå âèäà x u v� �� �1 2 .
Äåéñòâèòåëüíî, ïóñòü x au bv� , ãäå a � 0, b � 0. Òîãäà x a kv u� �( )
� ( )ku b v. Âûáåðåì k òàêîå, ÷òî ku b� è ( )k u b �1 .  ýòîì ñëó÷àå âûïîëíÿåòñÿ
íåðàâåíñòâî 0� �ku b u. Ïðè òàêîì âûáîðå k äîëæíî âûïîëíÿòüñÿ íåðàâåíñòâî
a kv � 0.  ïðîòèâíîì ñëó÷àå âûïîëíÿëîñü áû íåðàâåíñòâî x uv� , ÷òî ïðîòèâî-
ðå÷èò èñõîäíîìó ïðåäïîëîæåíèþ.
Çàìåòèì òàêæå, ÷òî äëÿ çàäàííûõ u è v îïèñàííîå âûøå ïðåîáðàçîâàíèå ïî-
çâîëÿåò ïîëó÷èòü äëÿ x ïîëîæèòåëüíî îïðåäåëåííóþ ôîðìó èëè óáåäèòüñÿ, ÷òî
åå íå ñóùåñòâóåò. Èç ýòîãî ñëåäóåò, ÷òî åñëè (1) çàäàåò êàíîíè÷åñêîå ïðåäñòàâëå-
íèå ìàêñèìàëüíîãî ðàíãà äëÿ x, òî x u vn n� � �1 1.
Ïðåäïîëîæèì, ÷òî çàäàíà êàíîíè÷åñêàÿ ôîðìà (1) ìàêñèìàëüíîãî ðàíãà.
 çàâèñèìîñòè îò ðåøàåìûõ çàäà÷ ìîæíî ðåêóðñèâíî ïðèìåíÿòü ê îáîèì êîýô-
ôèöèåíòàì �1 è � 2 èëè òîëüêî ê îäíîìó èç íèõ àíàëîãè÷íûé ïðîöåññ ðàçëîæå-
íèÿ â êàíîíè÷åñêèå ( , )U V -ëèíåéíûå ôîðìû ìàêñèìàëüíîãî ðàíãà äî òåõ ïîð,
ïîêà òàêîå ðàçëîæåíèå âîçìîæíî.
Îáîçíà÷èì S ïîäìíîæåñòâî íàòóðàëüíûõ ÷èñåë òàêîå, ÷òî äëÿ êàæäîãî ÷èñ-
ëà x èç S ñóùåñòâóåò ïî ìåíüøåé ìåðå îäíà ëèíåéíàÿ ôîðìà (1). Îïèñàííàÿ ðå-
êóðñèâíàÿ ïðîöåäóðà ðàçëîæåíèÿ êîýôôèöèåíòîâ â ñîîòâåòñòâóþùèå ëèíåéíûå
ôîðìû çàäàåò åäèíñòâåííîå ïðåäñòàâëåíèå ÷èñåë èç S . Òàêèì îáðàçîì, äëÿ S
ïàðà ( , )U V ìîæåò ðàññìàòðèâàòüñÿ êàê äâóõáàçèñíàÿ ñèñòåìà ñ÷èñëåíèÿ.
Åñëè ðàçëîæåíèå â ìàêñèìàëüíûå ëèíåéíûå ôîðìû ïðèìåíÿåòñÿ òîëüêî
ê ìóëüòèïëèêàòèâíûì êîýôôèöèåíòàì ýëåìåíòîâ èç V , òî ðàññìàòðèâàåì ïîñëå-
äîâàòåëüíîñòüU êàê îñíîâíîé áàçèñ, à V — êàê âñïîìîãàòåëüíûé.  ýòîì ñëó÷àå
ïðîöåññ äåêîìïîçèöèè îïèñûâàåòñÿ ïîñëåäîâàòåëüíîñòüþ îñòàòî÷íûõ ÷èñåë:
x x u x vn n0 1 11 1
� � �� , x u x v x u x vn n t t n t nt t1 2 2 1 12 2
� � � � �� �, ,� . (2)
 (2) êàæäîå îñòàòî÷íîå ÷èñëî x u x vi i n i ni i
� �� �� �
� 1 11 1
çàäàåòñÿ ( , )U V -ëè-
íåéíîé ôîðìîé ìàêñèìàëüíîãî ðàíãà, i t� 0 1 2 1, , , , –� , u Uni�
�
1
, v Vni�
�
1
. ×èñëî
xt�1 ëèáî ðàâíî åäèíèöå, ëèáî îíî íå ïðåäñòàâèìî â âèäå (1).
Ïîñëåäîâàòåëüíîñòü (2) ìîæíî ïåðåïèñàòü â ñëåäóþùåì ñòðóêòóðíîì âèäå:
x u v u v u x vn n n n t n t nt t
� � � � �� � �1 2 11 1 2 2
( (... ( ) ))� .
Ðàçâèâàÿ òåîðèþ äâóõáàçèñíûõ ÷èñëîâûõ ñèñòåì, íåîáõîäèìî ðåøàòü ñëåäó-
þùèå çàäà÷è.
1. Êàê ýôôåêòèâíî ãåíåðèðîâàòü áàçèñûU èV äëÿ ðåøåíèÿ çàäàííîãî êëàññà
çàäà÷?
2. Åñëè çàäàíû áàçèñû U è V , òî êàêîâà ýôôåêòèâíîñòü àëãîðèòìà ðàçëîæå-
íèÿ ÷èñëà â ìàêñèìàëüíóþ ( , )U V -ëèíåéíóþ ôîðìó?
3. Êàêîâû ñîîòíîøåíèÿ ìåæäó ïàðàìåòðàìè ìàêñèìàëüíîé ëèíåéíîé ôîðìû?
18 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4
4. Êàêèå çàäà÷è èíôîðìàöèîííûõ òåõíîëîãèé ìîæíî ðåøàòü ñ ïîìîùüþ
äâóõáàçèñíûõ ñèñòåì ñ÷èñëåíèÿ?
Ïðè ðàçëîæåíèè â ëèíåéíûå ôîðìû (1) âàæíîå çíà÷åíèå èìååò îöåíêà êîýôôèöè-
åíòîâ �1 è � 2 , ïîñêîëüêó ýòî îïðåäåëÿåò ìíîãèå ñâîéñòâà ðåêóðñèâíîãî ðàçëîæåíèÿ.
Ïóñòü U u u� 1 2, ,� è v v vn � 1 2, ,� — äâå îðòîãîíàëüíûå ïîñëåäîâàòåëü-
íîñòè è ÷èñëî x çàäàíî ðàçëîæåíèåì (1).
Òåîðåìà 1. Ïðåäïîëîæèì, ÷òî v un n� , n �1 2, ,� , è ñóùåñòâóåò ïðåäåë
lim
n
n
n
v
u�
�1 . Òîãäà ñóùåñòâóåò êîíñòàíòà c òàêàÿ, ÷òî � �1 2� � c x.
Äîêàçàòåëüñòâî. Ïóñòü x au bvn n� � . Èñõîäÿ èç òîãî, ÷òî (1) — ëèíåéíàÿ
ôîðìà ìàêñèìàëüíîãî ðàíãà, ñëåäóåò x u vn n� � �1 1. Èç óñëîâèÿ òåîðåìû ïîëó÷àåì
íåðàâåíñòâà
x v
n
�
�1
2 , x vn� �1,
x
v
x
n�
�
1
.
Ýòî ïîçâîëÿåò îöåíèòü ñóììó � �1 2� ñëåäóþùèì îáðàçîì:
u xn ( )� �1 2� � , � �1 2
1
1� � � �
�
�x
u
x
v
v
un n
n
n
.
Èñõîäÿ èç íàëè÷èÿ ïðåäåëà äëÿ
v
u
n
n
�1 ñëåäóåò ñóùåñòâîâàíèå êîíñòàíòû c,
îãðàíè÷èâàþùåé îòíîøåíèå
v
u
n
n
�1 . Îòñþäà èìååì � �1 2� � c x.
Òåîðåìà äîêàçàíà.
Ïîñëåäîâàòåëüíîå ðåêóðñèâíîå ðàçëîæåíèå
÷èñëà x â ìàêñèìàëüíûå ( , )U V -ëèíåéíûå ôîðìû
ïî êîýôôèöèåíòàì ïðè U è V îïðåäåëÿåò èåðàð-
õè÷åñêóþ ñòðóêòóðó — ëèíåéíîå äåðåâî ÷èñëà x.
Íà ðèñ. 1 T�1 è T� 2 — ëèíåéíûå äåðåâüÿ ÷èñåë �1
è � 2 . Ëèñòüÿ äåðåâà ñîîòâåòñòâóþò ÷èñëàì, êîòî-
ðûå íå ðàçëîæèìû â ( , )U V -ëèíåéíûå ôîðìû.
Çäåñü âåðøèíà äîïóñêàåò â íàëè÷èè îäíîãî ñûíà,
åñëè ñîîòâåòñòâóþùèé êîýôôèöèåíò ðàâåí íóëþ.
Ñëåäñòâèå 1. Ïðè âûïîëíåíèè óñëîâèé òåî-
ðåìû 1 ãëóáèíà ëèíåéíîãî äåðåâà ðàçëîæåíèÿ
÷èñëà x îãðàíè÷åíà âåëè÷èíîé O x(log log ( )) .
Äîêàçàòåëüñòâî. Èç òåîðåìû 1 ñëåäóåò, ÷òî
êîýôôèöèåíòû �1 è � 2 , ñîîòâåòñòâóþùèå ïåðâîìó óðîâíþ äåðåâà, íå ïðåâûøà-
þò c x. Êîýôôèöèåíòû íà âòîðîì óðîâíå íå ïðåâûøàþò c c x c x�
�1 1
2
1
4 . Êî-
ý ô ô è ö è å í ò û , ñ î î ò â å ò ñ ò â ó þ ù è å i- ì ó ó ð î â í þ , í å ï ð å â û ø à þ ò
c x
i i
1 1
2
1
2
1
2
� � ��
. Îòñþäà âûâîäèì óòâåðæäåíèå ñëåäñòâèÿ.
Âî ìíîãèõ ñëó÷àÿõ äëÿ îïðåäåëåíèÿ äâóõáàçèñíîé ñèñòåìû ñ÷èñëåíèÿ äîñ-
òàòî÷íî çàäàíèÿ îäíîãî áàçèñàU u u� 1 2, ,� ÏîñëåäîâàòåëüíîñòüV îïðåäåëÿåòñÿ
ñäâèãîì áàçèñà U íà îäíó ïîçèöèþ, v ui i� �1. Ïðåäïîëàãàåòñÿ, ÷òî âûïîëíÿåòñÿ
òðåáîâàíèå HOÄ( , )u ui i� �1 1 , i �1 2, ,�  ýòîì ñëó÷àå ïðåäñòàâëåíèå (1) ïåðåïè-
ñûâàåòñÿ â âèäå x u vn n� � �� �1 2 1.
Äëÿ âûïîëíåíèÿ óñëîâèé òåîðåìû 1 äîñòàòî÷íî, ÷òîáû ïîñëåäîâàòåëüíîñòü
U áûëà ìîíîòîííî âîçðàñòàþùåé è ñóùåñòâîâàë ïðåäåë lim
n
n
n
u
u�
�1 .
Âûáîð áàçèñîâ U è V ïðåäïîëàãàåò èõ êîíñòðóêòèâíóþ ãåíåðàöèþ. Ñóùåñòâó-
åò áîëüøîé âûáîð èíòåðåñíûõ ïîñëåäîâàòåëüíîñòåé â êà÷åñòâå êîíñòðóêòèâíûõ
áàçèñîâ. Â ýòîé ñâÿçè èíòåðåñ ïðåäñòàâëÿåò êàòàëîãèçèðîâàííàÿ áàçà äàííûõ
OEIS (On-Line Encyclopedia of Integer Seguences), êîòîðóþ òàêæå ÷àñòî íàçûâàþò
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4 19
Ðèñ. 1. Ëèíåéíîå äåðåâî äëÿ ÷èñëà
x u vn n� �� �1 2
x
un vn
T �1 T �2
â ÷åñòü åå îñíîâàòåëÿ SLOANE [5], íàñ÷èòûâàþùàÿ áîëåå 200 òûñÿ÷ ïîñëåäîâà-
òåëüíîñòåé, íàêîïëåííûõ â íàó÷íûõ èññëåäîâàíèÿõ.
ÏÐÈÌÅÐÛ ÄÂÓÕÁÀÇÈÑÍÎÃÎ ÏÐÅÄÑÒÀÂËÅÍÈß ×ÈÑÅË
1. Ñòåïåííûå ñèñòåìû ñ÷èñëåíèÿ. Îñíîâíîé áàçèñ U çàäàåòñÿ ïîñëåäîâàòåëüíîñ-
òüþ ñòåïåíåé âûáðàííîãî áàçèñíîãî ÷èñëà M , M �1, âñïîìîãàòåëüíûé áàçèñ V ñî-
ñòîèò èç êîíñòàíòíîé ïîñëåäîâàòåëüíîñòè åäèíèö , U M M� 0 1 2, , , ,� ; V �1 1, ,�
Ïðè òàêîì âûáîðå áàçèñîâ ëèíåéíîå ðàçëîæåíèå ïî êîýôôèöèåíòàì âñïîìî-
ãàòåëüíîãî áàçèñàVñîâïàäàåò ñ êëàññè÷åñêîé M -è÷íîé ñèñòåìîé ñ÷èñëåíèÿ. ×èñ-
ëî 0 èìååò íóëåâîé ðàíã. Ïîëîæèòåëüíûå ÷èñëà, ìåíüøèå M , çàäàþòñÿ êàíîíè-
÷åñêîé ëèíåéíîé ôîðìîé ðàíãà 1 ñ íóëåâûì êîýôôèöèåíòîì � 2 .
2. Àääèòèâíûå ñèñòåìû ïðåäñòàâëåíèÿ ÷èñåë. Ïóñòü çàäàíû îñíîâíîé áà-
çèñ U u u� 1 2, ,� è âñïîìîãàòåëüíûé áàçèñ V �1 1, ,�, ñîñòîÿùèé èç åäèíèö.
Ïðåäïîëîæèì, ÷òî âûïîëíÿþòñÿ íåðàâåíñòâà 2 1u u ui i i� �� , i �1 2, ,� Òîãäà èç
óñëîâèÿ ìàêñèìàëüíîñòè ëèíåéíûõ ôîðì ðàçëîæåíèÿ ñëåäóåò, ÷òî âñå êîýôôèöè-
åíòû � i â (2) ðàâíû åäèíèöå.  ýòîì ñëó÷àå ïðåäñòàâëåíèå ÷èñëà x ïðèíèìàåò
íàèáîëåå ïðîñòîé âèä:
x u u u xn n n tt
� � � � � �1 2 1� , (3)
ãäå n n nt1 2� � �� , 0 1 1
��x ut .  ÷àñòíîñòè, åñëè u1 1� , òî xt� �1 0.
3. Êîä Ôèáîíà÷÷è. Ðàññìîòðèì ñëåäóþùèé ïðèìåð. ×èñëà Ôèáîíà÷÷è
îïðåäåëÿþòñÿ ñ ïîìîùüþ ðåêóðñèâíîãî ñîîòíîøåíèÿ
F F Fi i i� � �1 1 , i � 1, F F0 1 1� � .
Îñíîâíîé áàçèñ U � 2 3 5, , ,� çàäàåòñÿ ïîñëåäîâàòåëüíîñòüþ ÷èñåë Ôèáîíà÷-
÷è, íà÷èíàÿ ñ F2 . Äîïîëíèòåëüíûé áàçèñ V �1 1, ,� ñîñòîèò èç ïîñëåäîâàòåëü-
íîñòè åäèíèö. Äëÿ ÷èñåë Ôèáîíà÷÷è âûïîëíÿåòñÿ óñëîâèå: 2 1F Fi i� � . Ðàñêëàäû-
âàÿ â òàêîì áàçèñå ÷èñëà â ( , )U V -ëèíåéíûå ôîðìû, ïîëó÷àåì ñëåäóþùèé èçâåñò-
íûé ðåçóëüòàò. Äëÿ ëþáîãî íàòóðàëüíîãî ÷èñëà x ñóùåñòâóåò åãî ïðåäñòàâëåíèå
â âèäå ñóììû íåêîòîðûõ ÷èñåë Ôèáîíà÷÷è x d Fi i
i
k
�
�
�
1
, ãäå di �{ }0 1, ,
i k� 1 1, ,� , dk �1 .
Ïîñêîëüêó F F Fn n n �� �1 1, â ïîñëåäîâàòåëüíîñòè d d dk k, , ..., 1 1 íåò ðÿäîì
íàõîäÿùèõñÿ åäèíèö. Äâîè÷íûé êîä Ôèáîíà÷÷è ÷èñëà x çàäàåòñÿ èíâåðòèðîâàí-
íîé ïîñëåäîâàòåëüíîñòüþ d d dk1 2 1, , ..., , , â êîòîðîé ïðèïèñàíà äîïîëíèòåëüíàÿ
åäèíèöà. Íàëè÷èå äâóõ åäèíèö â êîíöå ñëîâà ïîçâîëÿåò ðàçäåëèòü êîäîâûå ñëîâà
ïðè èõ êîíêàòåíàöèè.
4. Àääèòèâíîå ïðåäñòàâëåíèå ÷èñëà â ñèñòåìå ïðîñòûõ ÷èñåë. Ëþáîå
íàòóðàëüíîå ÷èñëî ðàñêëàäûâàåòñÿ â ïðîèçâåäåíèå ïðîñòûõ ÷èñåë. Ïîäîáíîå
óòâåðæäåíèå ñïðàâåäëèâî è äëÿ ïðåäñòàâëåíèÿ ÷èñåë â âèäå ñóìì ïðîñòûõ ÷èñåë.
Ðàññìîòðèì äâóõáàçèñíóþ ñèñòåìó ñëåäóþùåãî âèäà. Îñíîâíîé áàçèñ çàäà-
åòñÿ ïîñëåäîâàòåëüíîñòüþ ïðîñòûõ ÷èñåë, U � 2 3 5 7, , , ... , à âñïîìîãàòåëüíûé áà-
çèñ — ïîñëåäîâàòåëüíîñòüþ åäèíèö, V �1 1, ,�
 òåîðèè ÷èñåë èçâåñòåí ïîñòóëàò Áåðòðàíà, ñôîðìóëèðîâàííûé â 1845 ã.,
ñîãëàñíî êîòîðîìó äëÿ ëþáîãî íàòóðàëüíîãî ÷èñëà n, n � 3, ñóùåñòâóåò ïðîñòîå
÷èñëî p, íàõîäÿùååñÿ â èíòåðâàëå n p n� � 2 2 . Äîêàçàòåëüñòâî ýòîãî ôàêòà
âïåðâûå ïîëó÷åíî Ï. ×åáûøåâûì â 1850 ã. Âïîñëåäñòâèè áîëåå ñèëüíûå ôîðìó-
ëèðîâêè ýòîãî óòâåðæäåíèÿ ïîëó÷åíû Ðàìàíóäæàíîì è Ýðäåøåì.
Îáîçíà÷èì ÷åðåç pi i-å ïðîñòîå ÷èñëî. Èç ïîñòóëàòà Áåðòðàíà ñëåäóåò, ÷òî
2 1p p pi i i� �� . Ñëåäîâàòåëüíî, äëÿ ëþáîãî íàòóðàëüíîãî ÷èñëà x, x � 0, ñó-
ùåñòâóåò åäèíñòâåííîå ïðåäñòàâëåíèå òèïà (3) â âèäå ñóììû ïðîñòûõ ÷èñåë.
 ýòîé ôîðìóëèðîâêå ÷èñëî 1 îòíîñèì ê ïðîñòûì ÷èñëàì.
Ñîãëàñíî îöåíêå êîëè÷åñòâà ïðîñòûõ ÷èñåë, íå ïðåâûøàþùèõ ÷èñëà x,
�( ) / lnx x x� , ïðÿìîå áèíàðíîå ïðåäñòàâëåíèå òàêîãî çàäàíèÿ ÷èñëà, àíàëîãè÷-
20 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4
íîå äâîè÷íîìó êîäó Ôèáîíà÷÷è, íå ÿâëÿåòñÿ îïòèìàëüíûì. Óëó÷øåíèå áèíàðíî-
ãî ïðåäñòàâëåíèÿ ìîæíî äîáèòüñÿ, èñïîëüçóÿ òàê íàçûâàåìûé äåëüòà-ïîäõîä.
Åñëè x p p pi i ik
� � � �
1 2
� , p pi ij j
�
� 1
, j k� 1 2 1, , ,� , òî äëÿ çàäàíèÿ x äî-
ñòàòî÷íî çàêîäèðîâàòü k-ìåðíûé âåêòîð ðàçíîñòåé (i i1 2 , i i i ik k2 3 1 , ,� , ik ).
Èñõîäÿ èç ýòîãî ïðåäñòàâëåíèÿ, îòìåòèì ñëåäóþùèé ôàêò. Ñóùåñòâóåò äîñòà-
òî÷íî ýôôåêòèâíîå ïðåôèêñíîå êîäèðîâàíèå ÷èñåë, îñíîâàííîå íà èçâåñòíîé
ýêñïåðèìåíòàëüíî ïðîâåðåííîé, íî íå äîêàçàííîé ãèïîòåçå Ãîëüäáàõà: ëþáîå
÷åòíîå ÷èñëî, áîëüøåå äâóõ, ìîæíî ïðåäñòàâèòü â âèäå ñóììû äâóõ ïðîñòûõ ÷èñåë [6].
5. Ïðåäñòàâëåíèå ÷èñåë â âèäå b-ñóìì. Ïðåäïîëîæèì, ÷òî âñïîìîãàòåëü-
íûé áàçèñ çàäàåòñÿ ïîñëåäîâàòåëüíîñòüþ ïîâòîðÿþùåãîñÿ îäíîãî è òîãî æå ÷èñ-
ëà, îòëè÷íîãî îò åäèíèöû.
Ïóñòü U u u� 0 1 2, , ,� — îñíîâíîé áàçèñ, b — íàòóðàëüíîå ÷èñëî, u � 0,
v b0 � , b �1 , V b b� , ,� è ui , u bi � , i �1 2, ,� ×èñëî b çàäàåòñÿ ëèíåéíîé ôîðìîé
íóëåâîãî ðàíãà. ×èñëî bk ïîñëåäîâàòåëüíî k ðàç ðàñêëàäûâàåòñÿ â ëèíåéíûå
ôîðìû íóëåâîãî ðàíãà. Ðàçëîæåíèå ÷èñëà x â òàêîì áàçèñå ïîçâîëÿåò ïðåäñòà-
âèòü x â ñòðóêòóðèðîâàííîì âèäå
x u b u b u x bn
k
n
k
t n t
k
t
t� � � � �� � �1 2 11
1
2
2( (... ( )... ), (4)
ãäå ëèáî xt� �1 1, ëèáî xt�1 — ÷èñëî, íå ïðåäñòàâèìîå â âèäå ïîëîæèòåëü-
íî-îïðåäåëåííîé ( , )U V -ëèíåéíîé ôîðìû.
Ïðåäïîëîæèì, ÷òî b M� . Çàäàäèì áàçèñû U M M� 0 1 2, , , ,� ; V b b� , ,�
 ýòîì ñëó÷àå â (4) x bMt� �1 .
6. Öåïíûå äðîáè. Çíà÷èòåëüíûé èíòåðåñ ïðåäñòàâëÿåò èñïîëüçîâàíèå â êà-
÷åñòâå áàçèñîâ ïîñëåäîâàòåëüíîñòè ÷èñëèòåëåé è (èëè) çíàìåíàòåëåé ïîäõîäÿ-
ùèõ äðîáåé, âîçíèêàþùèõ ïðè ðàçëîæåíèè ÷èñåë â öåïíûå äðîáè.  ÷àñòíîñòè,
ìîæíî èñïîëüçîâàòü õîðîøî èçâåñòíóþ ýôôåêòèâíóþ ãåíåðàöèþ ïîäõîäÿùèõ
äðîáåé êâàäðàòè÷íûõ èððàöèîíàëüíîñòåé âèäà k .
7. Ëèíåéíûå ôîðìû Ôèáîíà÷÷è. Ïóñòü U çàäàåòñÿ ðÿäîì Ôèáîíà÷÷è
1 1 2 3 5, , , , � Ëèíåéíàÿ ôîðìà Ôèáîíà÷÷è ðàíãà n îïðåäåëÿåòñÿ êàê ëèíåéíàÿ ôîð-
ìà âèäà
x aF bFn n� � �1. (5)
Äëÿ ëèíåéíûõ ôîðì Ôèáîíà÷÷è ñóùåñòâóþò áûñòðûå àëãîðèòìû, ïîçâîëÿþ-
ùèå ïîëó÷àòü ìàêñèìàëüíûå ôîðìû. Îñíîâîé ýòèõ àëãîðèòìîâ ñëóæàò
ñëåäóþùèå ïðåîáðàçîâàíèÿ.
1. Åñëè x aF bFk k� � �1 è b a� , òî x b a F aFk k� �� �( ) 1 2 .
2. Åñëè a Fk� �1, òî x a F F b F Fk k k k� � �� �( ) ( )1 1.
Ïðåîáðàçîâàíèå ï. 2 óâåëè÷èâàåò êîýôôèöèåíò b, à ïðåîáðàçîâàíèå ï. 1 óâå-
ëè÷èâàåò ðàíã. Îòñþäà ñëåäóåò óòâåðæäåíèå.
Åñëè (5) — ìàêñèìàëüíàÿ ëè-
íåéíàÿ ôîðìà Ôèáîíà÷÷è äëÿ ÷èñëà
x, a � 0, b � 0, òî b a Fn� � �1. Êîëè-
÷åñòâî àðèôìåòè÷åñêèõ îïåðàöèé â
àëãîðèòìå ïîñòðîåíèÿ ìàêñèìàëü-
íîé ëèíåéíîé ôîðìû Ôèáîíà÷÷è
îãðàíè÷åíî âåëè÷èíîé O x(log ).
Äëÿ ÷èñåë Ôèáîíà÷÷è ñóùåñò-
âóåò ïðåäåë lim
x
n
n
F
F�
� �
�1 5 1
2
. Ïî-
ýòîìó ðàçëîæåíèå ÷èñåë â ëèíåé-
íûå ôîðìû Ôèáîíà÷÷è îòíîñèòñÿ
ê ñëó÷àþ, çàäàâàåìîìó óñëîâèÿìè
òåîðåìû 1 è ñëåäñòâèåì 1. Íà
ðèñ. 2 èçîáðàæåíî ëèíåéíîå äåðå-
âî Ôèáîíà÷÷è äëÿ ÷èñëà 15411.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4 21
Ðèñ. 2. Ëèíåéíîå äåðåâî Ôèáîíà÷÷è äëÿ ÷èñëà 15411
15411
F12
F9
123 31
2 3 21
1 1 1
F11
F3
F10 F5 F6
F4 F3
Ëèíåéíûå ôîðìû Ôèáîíà÷è áûëè ââåäåíû â [7] è èçó÷àëèñü â [8–10].
ÏÀÐÀËËÅËÜÍÎÅ ÌÎÄÓËÜÍÎÅ ÝÊÑÏÎÍÅÍÖÈÐÎÂÀÍÈÅ
Îïåðàöèÿ ìîäóëüíîãî âîçâåäåíèÿ â ñòåïåíü a mx � mod äëÿ áîëüøèõ ÷èñåë ÿâ-
ëÿåòñÿ îäíîé èç îñíîâíûõ ïðîöåäóð ìíîãèõ èçâåñòíûõ êðèïòîñèñòåì. Âðåìÿ
åå âûïîëíåíèÿ îïðåäåëÿåò ýôôåêòèâíîñòü ñîîòâåòñòâóþùèõ àëãîðèòìîâ. Íà
ñåãîäíÿøíèé äåíü âåäóòñÿ àêòèâíûå èññëåäîâàíèÿ, íàïðàâëåííûå íà óñêîðå-
íèå ìîäóëüíîãî ýêñïîíåíöèðîâàíèÿ. Îáçîð ñóùåñòâóþùèõ ðåçóëüòàòîâ â ýòîé
îáëàñòè âûõîäèò çà ðàìêè äàííîé ðàáîòû. Äâóõáàçèñíûå ñèñòåìû ñ÷èñëåíèÿ
ïîçâîëÿþò ïðåäëîæèòü ýôôåêòèâíûå óíèôèöèðîâàííûå ñðåäñòâà äëÿ óâåëè÷å-
íèÿ áûñòðîäåéñòâèÿ âîçâåäåíèÿ â ñòåïåíü çà ñ÷åò ñâåäåíèÿ ê âîçâåäåíèþ
â ñïåöèàëüíî âûáðàííûå ñòåïåíè.
Ïðåäïîëîæèì, ÷òî â áàçèñíûõ ïîñëåäîâàòåëüíîñòÿõ U è V âîçâåäåíèå â ñòå-
ïåíè un è vn âûïîëíÿåòñÿ áîëåå ïðîñòî ïî ñðàâíåíèþ ñ ïðîèçâîëüíîé ñòåïåíüþ.
Åñëè x u vn n� �� �1 2 , òî
a n a a nx u vn n� �mod mod( ) ( )
� �1 2 . (6)
Ðàçëàãàÿ ðåêóðñèâíûì ñïîñîáîì îäíîâðåìåííî �1 è � 2 ïî áàçèñàì ( , )U V
ïîëó÷àåì ðåêóðñèâíî-ïàðàëëåëüíûé àëãîðèòì âû÷èñëåíèÿ ìîäóëÿðíîãî
âîçâåäåíèÿ â ñòåïåíü. Ôîðìóëà (6) îïðåäåëÿåò äâóõïðîõîäíóþ ñòðóêòóðó àëãî-
ðèòìà òèïà áèíàðíîå äåðåâî.
 ïåðâîé ôàçå âûïîëíÿåòñÿ ïðîõîæäåíèå âåðøèí îò êîðíÿ ê ëèñòüÿì.  êàæ-
äîé âåðøèíå ïðîèñõîäÿò îäíîòèïíûå äåéñòâèÿ: ïðèåì ÷èñëà îò âåðøèíû-îòöà,
ðàçëîæåíèå ýòîãî ÷èñëà â ìàêñèìàëüíóþ ( , )U V -ëèíåéíóþ ôîðìó, ìîäóëÿðíîå
âîçâåäåíèå â ñòåïåíè, îïðåäåëÿåìûå ðàíãîâûìè ÷èñëàìè ñîîòâåòñòâóþùèõ áàçè-
ñîâ, ïåðåäà÷à êîýôôèöèåíòîâ ëèíåéíîãî ðàçëîæåíèÿ âåðøèíàì-ñûíîâüÿì.
Âî âòîðîé ôàçå èäåò ñáîðêà ðåçóëüòàòà îò ëèñòüåâ ê êîðíþ äåðåâà. Â êàæäîé âåð-
øèíå âûïîëíÿåòñÿ ìîäóëÿðíîå óìíîæåíèå ÷èñåë, ïîëó÷àåìûõ îò âåðøèí-ñûíîâåé, è
ðåçóëüòàò ïåðåäàåòñÿ âåðøèíå-îòöó. Âòîðóþ ôàçó ìîæíî âûïîëíÿòü áåç ïðîõîæäåíèÿ
ïî äåðåâó. Ðåçóëüòàòû, ïîëó÷åííûå â ëèñòüÿõ, â ïðîèçâîëüíîì ïîðÿäêå ïîäàþòñÿ íà
óçåë ìîäóëÿðíîãî óìíîæåíèÿ, ãäå âñå îíè ïåðåìíîæàþòñÿ ïî çàäàííîìó ìîäóëþ.
Ïîäîáíàÿ àðõèòåêòóðà àëãîðèòìà äîïóñêàåò ìíîãîîáðàçèå ðåàëèçàöèé êàê
íà ïðîãðàììíîì, òàê è íà àïïàðàòíîì óðîâíÿõ. Ñóùåñòâóåò äîñòàòî÷íî ìíîãî
âàðèàíòîâ âûáîðà áàçèñíûõ ïîñëåäîâàòåëüíîñòåé U è V äëÿ ðàññìàòðèâàåìîé
çàäà÷è. Ñ÷èòàåòñÿ, ÷òî âîçâåäåíèå â êâàäðàò ÿâëÿåòñÿ áîëåå ïðîñòîé (áûñòðîé)
îïåðàöèåé ïî ñðàâíåíèþ ñ óìíîæåíèåì äâóõ ÷èñåë. Åñëè x — k-çíà÷íîå ÷èñëî,
çàäàííîå â áàçèñå ñòåïåíåé ÷èñëà b, x x x xk b� ( ... )1 1 0 , òî x xi
i
k
2 2
0
1
� �
�
�
�
� �
�
���2
1
1
0
2
x x bi
j i
k
i
k
j
i j .
Âû÷èñëåíèå x 2 òðåáóåò
1
2
1k k( )� îäíîöèôðîâûõ óìíîæåíèé â áàçèñå b ïî
ñðàâíåíèþ ñ k 2 òàêèõ óìíîæåíèé ïðè âû÷èñëåíèè ïðîèçâåäåíèÿ ïðîèçâîëüíûõ
k-çíà÷íûõ ÷èñåë. Ïîýòîìó äëÿ áîëüøèõ ÷èñåë äëèíîþ â íåñêîëüêî òûñÿ÷ áèò
âîçâåäåíèå â êâàäðàò âûïîëíÿåòñÿ áûñòðåå îáû÷íîãî óìíîæåíèÿ íà 25–50%. Ïî-
ýòîìó â áàçèñàõ U è V áóäåì â îñíîâíîì èñïîëüçîâàòü ñòåïåíè ÷èñëà 2.
Íàèáîëåå î÷åâèäíûì ÿâëÿåòñÿ èñïîëüçîâàíèå áàçèñîâ un
n� 2 , vn
n� �2 1 .
Ïóñòü
x a bk k� � �2 2 1( ). (7)
Ïðåäñòàâëåíèå (7) çàäàåò áûñòðûé ñïîñîá âû÷èñëåíèÿ a b, è n ïî äâîè÷íîìó
çàäàíèþ ÷èñëà x. Äåéñòâèòåëüíî, (7) ìîæíî ïåðåïèñàòü â âèäå x a b bk� � �( )2 .
22 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4
Ñëåäîâàòåëüíî, äîñòàòî÷íî íàéòè ìàêñèìàëüíîå ïðåäñòàâëåíèå x q bk� �2 , q b� ,
a q b� .
Åñëè
x a a a a an
n
n k n k
n
n k
k k
k� � � � � � � �
2 2 2 2 2 21
1
0 1
1
1
1
� ( ) � �� a0 ,
òî â êà÷åñòâå k äîñòàòî÷íî âûáðàòü ÷èñëî
n �
��
�
��
1
2
.  ýòîì ñëó÷àå
q a an k
n
n k
k� � � �
2 21
1
� , b a ak
k� � �
1
1
02 � , a q b� .
Äàííîå ðåøåíèå ëåãêî ïåðåíîñèòñÿ íà ñëó÷àé ñâåðõáîëüøèõ ýêñïîíåíò, çà-
äàâàåìûõ â ñòåïåííîì áàçèñå ñ îñíîâîé b M� 2 .
Îäíèì èç âîçìîæíûõ âàðèàíòîâ ñîîòâåòñòâóþùåãî âûáîðà ïîñëåäîâàòåëü-
íîñòåé U è V ÿâëÿåòñÿ òàêæå âûáîð áàçîâîé ïîñëåäîâàòåëüíîñòè U u u� 0 1, ,� ,
÷ëåíû êîòîðîé óäîâëåòâîðÿþò ðåêóððåíòíîìó ñîîòíîøåíèþ u un
M
n� � �1 12
� un , ãäå M — çàäàííàÿ êîíñòàíòà. ×ëåíû ïîñëåäîâàòåëüíîñòè V çàäàþòñÿ ñäâè-
ãîì íà îäèí øàã ïîñëåäîâàòåëüíîñòè U , v un n� �1, u u0 1 1� � . Âîçìîæíû äðóãèå
âàðèàíòû âûáîðà U , êîãäà, íàïðèìåð, u u un n
M
n� � �1 1 2 . Êîìïüþòåðíûå ýêñïå-
ðèìåíòû ïîêàçàëè âûñîêóþ ýôôåêòèâíîñòü ïðåäëàãàåìîãî ïîäõîäà [11].
Îòìåòèì, ÷òî âî âñåõ ðàññìàòðèâàåìûõ ñëó÷àÿõ ñîãëàñíî ñëåäñòâèþ 1 ãëó-
áèíà äåðåâà àëãîðèòìà ïàðàëëåëüíîãî âîçâåäåíèÿ â ñòåïåíü îãðàíè÷åíà âåëè÷è-
íîé O x(log log ). ×èñëî âåðøèí â äåðåâå ñîñòàâëÿåò O x(log ). Ýòî ïîçâîëÿåò ðàñ-
ñìàòðèâàòü âîçìîæíîñòü ýôôåêòèâíîé ðåàëèçàöèè ïðåäëàãàåìûõ ïàðàëëåëüíûõ
àëãîðèòìîâ íà àïïàðàòíîì óðîâíå.
ÊÎÄÈÐÎÂÀÍÈÅ ÄÅÐÅÂÜÅÂ
Äåðåâüÿ ÿâëÿþòñÿ îäíîé èç íàèáîëåå ÷àñòî èñïîëüçóåìûõ àëãîðèòìè÷åñêèõ
ñòðóêòóð äàííûõ. Ïîýòîìó âî ìíîãèõ ïðèëîæåíèÿõ âîçíèêàþò çàäà÷è èõ îïòè-
ìàëüíîãî õðàíåíèÿ è ïåðåäà÷è.
Ðàçëîæåíèå ÷èñåë â ëèíåéíûå ôîðìû îïðåäåëÿåò ñîîòâåòñòâóþùèå áèíàð-
íûå äåðåâüÿ. Âîçìîæåí îáðàòíûé ïðîöåññ. Åñëè èìååòñÿ ñòðóêòóðà òèïà áèíàð-
íîãî äåðåâà, òî âîçìîæíî âçàèìíî îäíîçíà÷íîå îòîáðàæåíèå òàêîãî äåðåâà
â ÷èñëî, ïîëó÷àåìîå ñ ïîìîùüþ îáðàòíîãî ïðîöåññà — ïîñòðîåíèÿ ìàêñèìàëü-
íûõ ëèíåéíûõ ôîðì (1) ïî êîýôôèöèåíòàì �1 è � 2 . Äëÿ ýòîãî íåîáõîäèìî ïî
÷èñëàì a è b, ñîîòâåòñòâóþùèì êîäàì ëåâîãî è ïðàâîãî ïîääåðåâüåâ, ïîñòðîèòü
÷èñëî x au bvn n� � , êîòîðîå ÿâëÿåòñÿ êîäîì âåðøèíû-îòöà, ïðè ýòîì ëèíåéíîå
ïðåäñòàâëåíèå au bvn n� ÿâëÿåòñÿ ìàêñèìàëüíîé ( , )U V -ëèíåéíîé ôîðìîé äëÿ x.
Äåêîäèðîâàíèå êîäà äåðåâà îñóùåñòâëÿåòñÿ ðàçëîæåíèåì ÷èñëà-êîäà
â ìàêñèìàëüíûå ëèíåéíûå ôîðìû.
Ðåøåíèå äàííîé çàäà÷è ÿâëÿåòñÿ äëÿ ìíîãèõ áàçèñîâ U è V ýôôåêòèâíûì,
â ÷àñòíîñòè äëÿ áàçèñîâ, çàäàâàåìûõ ÷èñëàìè Ôèáîíà÷÷è.  ýòîì ñëó÷àå, åñëè a b� ,
äîñòàòî÷íî âûáðàòü ïåðâîå Fn òàêîå, ÷òî a Fn� . Áîëåå ñëîæíîå êîäèðîâàíèå, èñ-
ïîëüçóþùåå äâîéíîå ðàçëîæåíèå â ìàêñèìàëüíûå ëèíåéíûå ôîðìû, ïðèìåíèìî äëÿ
îòìå÷åííûõ äåðåâüåâ, â âåðøèíàõ êîòîðûõ õðàíèòñÿ èíôîðìàöèÿ (÷èñëà).
Âîçìîäíî òàêæå ïðèìåíåíèå äâóõáàçèñíûõ ñèñòåì, ñâÿçàííûõ ñî ñòðóêòó-
ðîé òèïà áèíàðíîå äåðåâî. Ïóñòü ÷èñëî x çàäàíî â ôîðìå (1). Ðåêóðñèâíîå êîäè-
ðîâàíèå C x( ) ÷èñëà x ñ ïîìîùüþ èíäåêñîâ ðàçëîæåíèÿ â ( , )U V -ëèíåéíûå ôîðìû,
ýêâèâàëåíòíîå ïîñòðîåíèþ ëèíåéíîãî äåðåâà ( , )U V -ðàçëîæåíèÿ ÷èñëà x,
îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì:
C x C n C( ) ( ( )) ( ( ))� � �1 2 .
Òàêîå êîäèðîâàíèå ìîæåò áûòü èñïîëüçîâàíî â êðèïòîãðàôè÷åñêèõ ïðåîáðàçî-
âàíèÿõ. Ïîñëåäîâàòåëüíîñòè U è V ãåíåðèðóþòñÿ ïî ñåêðåòíîìó êëþ÷ó.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4 23
 ïðèíöèïå U è V ìîãóò áûòü ïðîèçâîëüíûìè ïîñëåäîâàòåëüíîñòÿìè âçàèìíî
ïðîñòûõ ÷èñåë, ïðè ýòîì õîòÿ áû îäíà èç íèõ äîëæíà âîçðàñòàòü (íå îáÿçàòåëü-
íî ìîíîòîííî).
Ðàññìîòðèì ÷àñòíûé ñëó÷àé. Êëþ÷ çàäàåòñÿ ÷èñëîì k. Ïóñòü P Qn n/ — ïî-
ñëåäîâàòåëüíîñòü ïîäõîäÿùèõ äðîáåé ðàçëîæåíèÿ â öåïíóþ äðîáü ÷èñëà k .
Ïîñëåäîâàòåëüíîñòè U è V çàäàþòñÿ ÷èñëèòåëÿìè u Pi i� , v Pi i� �1 èëè çíàìåíà-
òåëÿìè Qi è Qi�1. Â êîäîâîì ñëîâå ôèãóðèðóþò òîëüêî èíäåêñû ïîñëåäîâàòåëü-
íîñòåé U è V è êîäû îñòàòî÷íûõ ÷èñåë, ñîîòâåòñòâóþùèõ ëèñòüÿì äåðåâà. Ïîñ-
êîëüêó ñóùåñòâóåò áåñêîíå÷íî ìíîãî âàðèàíòîâ âûáîðà k, òî òîëüêî ïî èíäåêñàì
âîññòàíîâèòü èñõîäíîå ÷èñëî áåç çíàíèÿU èV íå ïðåäñòàâëÿåòñÿ âîçìîæíûì.
Íåòðóäíî ìîäèôèöèðîâàòü ñèñòåìó òàêèì ñïîñîáîì, ÷òîáû U è V ïîñëå
êàæäîãî êîäèðîâàíèÿ ìåíÿëè ÷èñëà ñ ñîîòâåòñòâóþùèìè èñïîëüçóþùèìèñÿ
â êîäèðîâàíèè èíäåêñàìè.  ýòîì ñëó÷àå ïîâòîðíîå êîäèðîâàíèå îäíîãî è òîãî
æå ÷èñëà áóäåò äàâàòü ðàçíûå êîäîâûå ñëîâà.
ÓÍÈÂÅÐÑÀËÜÍÛÅ ÏÐÅÔÈÊÑÍÛÅ ÊÎÄÈÐÎÂÀÍÈß ×ÈÑÅË
Ïðåôèêñíûå (ïðåôèêñíî-ñâîáîäíûå) êîäû ïðåäñòàâëÿþò çíà÷èòåëüíûé èíòåðåñ
â ñâÿçè ñ èõ àêòèâíûì èñïîëüçîâàíèåì âî ìíîãèõ ïðèëîæåíèÿõ, îñîáåííî äëÿ
ñæàòèÿ è ïåðåäà÷è èíôîðìàöèè. Íàèáîëåå èçâåñòíû ïðåäñòàâèòåëè òàêèõ êî-
äîâ: êîä Õàôôìàíà [12], êîäû Ýëëèàñà [13], êîä Ëåâåíøòåéíà [14] è êëàññû
êîäîâ, êîòîðûå èñïîëüçóþò êîäèðîâàíèå Ôèáîíà÷÷è [1–4]. Ñîâðåìåííûé îá-
çîð òàêèõ êîäîâ ìîæíî íàéòè â ðàáîòå [15].
Äâóõáàçèñíîå ïðåäñòàâëåíèå ÷èñåë ïîçâîëÿåò âûÿâèòü øèðîêèé ñïåêòð íî-
âûõ ïðåôèêñíûõ êîäîâ. Äëÿ ýòîãî ðàññìîòðèì äâóõáàçèñíûå ñèñòåìû ñ îãðàíè-
÷åíèÿìè íà êîýôôèöèåíòû �1 è � 2 â (1). Ïóñòü R1 è R2 — çàäàííûå ïîäìíîæåñ-
òâà íàòóðàëüíûõ ÷èñåë.  ïðåäñòàâëåíèè (1) íåîáõîäèìî, ÷òîáû �1 1�R è
� 2 2�R . Çäåñü ( , )U V -ëèíåéíûå ôîðìû ñ òàêèìè îãðàíè÷åíèÿìè îïðåäåëÿþò ñïåöè-
ôè÷åñêèå ïðåäñòàâëåíèÿ ÷èñåë, êîòîðûå èñïîëüçóþò ñâîéñòâà ìíîæåñòâ R1 è R2 .
×àñòíûé ñëó÷àé òàêîãî çàäàíèÿ ÷èñåë ïðåäñòàâëÿåò èíòåðåñ. Ïóñòü p —
ïðîñòîå ÷èñëî è g — îáðàçóþùèé ýëåìåíò ìóëüòèïëèêàòèâíîé ãðóïïû Z p
* âû÷å-
òîâ ïî ìîäóëþ p. Ðàññìîòðèì ( , )U V -ðàçëîæåíèÿ íàòóðàëüíûõ ÷èñåë, ãäå U —
áåñêîíå÷íàÿ ïîñëåäîâàòåëüíîñòü ñòåïåíåé ÷èñëà g, ðàñøèðåííàÿ íóëåì,
U g g g� 0 2 3, , , ,� , à V — êîíñòàíòíàÿ ïîñëåäîâàòåëüíîñòü, îïðåäåëÿåìàÿ ÷èñ-
ëîì p, V p p� , ,� Îãðàíè÷åíèÿ íà êîýôôèöèåíòû çàäàþòñÿ ìíîæåñòâàìè
R1 1� { } è R2 � �. Èíûìè ñëîâàìè, ðàññìàòðèâàþòñÿ òîëüêî ïðåäñòàâëåíèÿ âèäà
g pn � � . Çàìåòèì, ÷òî �p ïîñëåäîâàòåëüíî ðàñêëàäûâàåòñÿ â ÷èñëî �� pk , k � 1 , ãäå
�� íå äåëèòñÿ íà p. Ïðåäïîëîæèì, ÷òî x g p� 1 è HOÄ( , )x p �1. Ó÷èòûâàÿ, ÷òî g —
îáðàçóþùèé ýëåìåíò ãðóïïû Z p
* , ïîëó÷àåì ìàêñèìàëüíóþ ñòåïåíü n1 òàêóþ, ÷òî
x g p x
n b� �1 1
1, (8)
ãäå x1 0� è x1 âçàèìíî ïðîñòîå ñ p.
Äëÿ ÷èñåë, ìåíüøèõ g p 1, òàêîãî ïðåäñòàâëåíèÿ ìîæåò íå áûòü. Ðàññìîò-
ðèì, íàïðèìåð, (2,5)-ñèñòåìó. ×èñëî 11 íå ïðåäñòàâèìî â âèäå (8), òàê êàê íàè-
ìåíüøàÿ ñòåïåíü n äëÿ ÷èñëà 2 òàêàÿ, ÷òî 2 11 5n � mod ðàâíà 4, 2 164 � .
Ðåêóðñèâíî ïðèìåíÿÿ ïðîöåññ ðàçëîæåíèÿ êîýôôèöèåíòîâ ïðè p â ôîðìû
âèäà (8), ïîëó÷àåì ñëåäóþùåå ðàçëîæåíèå:
x x g p x
n k� � �1 2
1 1 ,
x g p x x g p x
n k
t
n k
t
t t
2 3 1
2 2� � � � �, ,� . (9)
 (9) ÷èñëî xt�1 íå ïðåäñòàâèìî â âèäå (8).
24 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4
Ñòðóêòóðíàÿ ôîðìà äëÿ x èìååò âèä
x g p g p g p x
n k n k n k
t
t t� � � � �
1 1 2 2
1( (... ( ))... ).
Îáîçíà÷èì ni ìàêñèìàëüíóþ ñòåïåíü g â ñòåïåííîì ðàçëîæåíèè x ïî áàçèñó g,
x a g a g ai n
n
n
n
i
i
i
i� � � �
1
1
0... , (10)
0
�a gj , j ni� 0, ,� , i t� �1 2 1, , ,� .
Èç (10) ñëåäóåò âûïîëíåíèå íåðàâåíñòâà x gi
ni� �1
. Äëÿ çíà÷åíèÿ ni èìååì
p 1 âîçìîæíîñòåé:
n ni i� , n ni i� 1,�, n n pi i� ( )2 .
Îòñþäà ñëåäóåò âûïîëíåíèå íåðàâåíñòâà
g p g x g
n k n n pi i i i� � �� � 1 1
. (11)
 ëîãàðèôìè÷åñêîì âèäå èç (11) ïîñëå óïðîùåíèé ïîëó÷àåì íåðàâåíñòâî
k p n n gi g i i g
plog log ( )� � � �
1
1 1 , (12)
êîòîðîå ìîæíî ïåðåïèñàòü â âèäå
k p k n n k gi g i i i i g
plog log ( ) � � �
1
1 1 . (13)
Òàê êàê log ( )g
pg p � 1 1 1 , òî ñïðàâåäëèâî íåðàâåíñòâî
k p k n n k pi g i i i ilog � � �1 1 . (14)
Ìèíèìàëüíîå çíà÷åíèå ëåâîé ÷àñòè íåðàâåíñòâà (14) ðàâíî log g p 1 ïðè k i �1.
Ïóñòü c — íàèáîëüøåå íàòóðàëüíîå ÷èñëî òàêîå, ÷òî g pc� �1 . Èç (14) ñëåäó-
þò íåðàâåíñòâà
0 1� log g p c ,
0 1 11� � � �log g i i ip c n n k p c . (15)
Ïîëîæèì � i i i in n k p c� � �1 1 . Èç (15) ñëåäóåò, ÷òî � i � 0. ×èñëà � i
è k i óäîâëåòâîðÿþò íåðàâåíñòâó
k p k ci g c ilog � � . (16)
Ïàðû ( , )� i ik , i t�1 2, , ,� , íàçûâàåì áëîêàìè. ×èñëî x îäíîçíà÷íî îïðåäåëÿåò-
ñÿ ïîñëåäíèì îñòàòî÷íûì ÷èñëîì xt�1 è ïîñëåäîâàòåëüíîñòüþ áëîêîâ
x k k k xt t t� �( , )( , ) ... ( , )( )� � �1 1 2 2 1 . (17)
Âîññòàíîâëåíèå ÷èñëà x ïî (17) ïðîèñõîäèò â îáðàòíîì ïîðÿäêå, íà÷èíàÿ
ñ xt�1. Îáùèé øàã âîññòàíîâëåíèÿ x âûïîëíÿåòñÿ ñëåäóþùèì îáðàçîì. Ïî ÷èñëó
xi�1 âû÷èñëÿåòñÿ ni�1. Çàòåì ïî çíà÷åíèÿì � i ik, , ni�1, p è c íàõîäèòñÿ ÷èñëî ni .
Îñòàòî÷íîå ÷èñëî xi âû÷èñëÿåòñÿ ïî ôîðìóëå
x g p x i t ti
n k
i
i i� � � �1 1 1, , , ,� .
Åñëè x — ïðîèçâîëüíîå ÷èñëî, îòëè÷íîå îò íóëÿ è åäèíèöû, òî îíî ïðåä-
ñòàâëÿåòñÿ â âèäå x g p x
n k� 0 0
1, ãäå x1 — ÷èñëî, âçàèìíî ïðîñòîå ñ g è p. Òàêèì
îáðàçîì, ïðîèçâîëüíîå íàòóðàëüíîå ÷èñëî x îäíîçíà÷íî çàäàåòñÿ ïîñëåäîâàòåëü-
íîñòüþ
( )( , )( , )( , ) ... ( , )x n k k k kt t t�1 0 0 1 1 2 2� � � . (18)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4 25
Îñòàòî÷íûå ÷èñëà â ðàçëîæåíèè (9) óáûâàþò â ãåîìåòðè÷åñêîé ïðîãðåññèè:
x
x g
p
x
p
i
i
n
k
i
k
i
i i
� �
�1 . (19)
Èç (19) ñëåäóåò íåðàâåíñòâî
k p xi log log2 2� � . (20)
Òàê êàê k i � 1, òî äëÿ ÷èñëà áëîêîâ t ïîëó÷àåì ãðóáóþ îöåíêó:
t
x
p
�
log
log
2
2
.
(21)
Ïðåôèêñíûå ( , )g p -êîäû. Ïóñòü { }0 1, * — ìíîæåñòâî âñåõ ñëîâ â àëôàâèòå
{ }0 1, . Åñëè u �{ }0 1, * , òî | |u îáîçíà÷àåò äëèíó ñëîâà u, uk — ïîñëåäîâàòåëüíàÿ
êîíêàòåíàöèÿ k ðàç ñëîâà u. Ïîñëåäîâàòåëüíîñòè âèäà 0 1n k íàçûâàåì 01-ãðóïïàìè.
Ïîñëåäîâàòåëüíîñòü (18) â áèíàðíîì àëôàâèòå { }0 1, êîäèðóåòñÿ ñëåäóþùèì
îáðàçîì. ×èñëî xt�1 óäîâëåòâîðÿåò íåðàâåíñòâó x gt
p
�
�1
1. Ïîýòîìó äëÿ çàäà-
íèÿ âñåõ ÷èñåë, äëÿ êîòîðûõ íåâîçìîæíî ïðåäñòàâëåíèå (7), ðåçåðâèðóåòñÿ êîí-
ñòàíòíîå ÷èñëî áèò. Ýòî ÷èñëî íå ïðåâûøàåò ( ) logp g 1 2 . Ïàðà ( , )n k0 0 êîäèðó-
åòñÿ 01-ãðóïïîé 0 10 01 1n k� �
. Ïàðà ( , )� 1 1k êîäèðóåòñÿ 01-ãðóïïîé 0 1
� i ik
.
Òàêèì îáðàçîì, ( , )g p -ïðåäñòàâëåíèå ÷èñåë çàäàåò èíúåêòèâíîå îòîáðàæå-
íèå � g p, ìíîæåñòâà � â { }0 1, * ,
� g p t
n k k k
x x t t
, ( ) ( ) ...� �
� �
êîä 1
1 1
0 1 0 1 0 10 0 1 1� �
. (22)
Çäåñü êîä ( )xt�1 îáîçíà÷àåò êîäèðîâàíèå ÷èñëà xt�1.
Ïóñòü M — ìíîæåñòâî äàííûõ è U �{ }0 1, * , � : M U� åñòü áèåêòèâíîå îòî-
áðàæåíèå M íà U , îïðåäåëÿþùåå êîäèðîâàíèå ýëåìåíòîâ èç M ñëîâàìè èç U .
Ýëåìåíòû èç U íàçûâàåì êîäîâûìè ñëîâàìè, à U — êîäîì äëÿ M .
Êîäèðîâàíèå � íàçûâàåòñÿ îäíîçíà÷íî äåêîäèðóåìûì (uniquely decodable),
åñëè ïî êîíêàòåíàöèè êîäîâûõ ñëîâ c m c m c mk( ) ( )... ( )1 2 ìîæíî îäíîçíà÷íî âîñ-
ñòàíîâèòü êîäû c mi( ), i k�1, ,� . Êîä U íàçûâàåòñÿ ïðåôèêñíî-ñâîáîäíûì (ïðå-
ôèêñíûì), åñëè íèêàêîå ñëîâî èç U íå ìîæåò áûòü íà÷àëîì (ïðåôèêñîì) ëþáîãî
äðóãîãî ñëîâà èç U .
Îòîáðàæåíèå � g p, íå âñåãäà ÿâëÿåòñÿ îäíîçíà÷íî äåêîäèðóåìûì. Íåðàâåí-
ñòâî (15) ïîçâîëÿåò îïðåäåëèòü ðàçäåëèòåëè ìåæäó êîäîâûìè ñëîâàìè.
Ïóñòü k — íàèìåíüøåå ÷èñëî òàêîå, ÷òî k p k cglog � �1. Ñîãëàñíî (16)
áëîêà ( , )1 k íå ñóùåñòâóåò. Ýòî îçíà÷àåò, ÷òî â áèíàðíîì çàäàíèè êîäèðîâàíèÿ íå
ñóùåñòâóåò êîäà áëîêà âèäà # � 01k . Ïîýòîìó ìîæíî ïðèïèñûâàòü 01k â êîíöå
ñëîâà � g p x, ( ). Òåì ñàìûì ðàñïîçíàåòñÿ îêîí÷àíèå êîäîâîãî ñëîâà.
Îïðåäåëèì êîä � � �g p g p x x, , ( ) # |� �{ }, êîòðûé ÿâëÿåòñÿ ïðåôèêñíî-ñâî-
áîäíûì. Îöåíèì äëèíó êîäîâîãî ñëîâà äëÿ ÷èñëà x x
n k� 2 30 0
1.
Èç ïðåäñòàâëåíèÿ (22) ñëåäóåò
| ( )| | ( )| ( ),� g p t i i
i
t
i
i
x x n k n n k� � � � � �� �
� �
�êîä 1 0 0 1
1
2
1 1
1
t
i
i
t
k t p c� � � �
�
( )
� � � � � � � � �
�
n x n t p c n k n nt t i i
i
1 1 1 0 0
1
1 2(| ( )| ) ( ) ( )êîä
t
� .
Çàìåòèì, ÷òî n ni i
0. Ó÷èòûâàÿ, ÷òî
� �n xi g i� log , x gt
p
�
�1
1, t
x
p
�
log
log
2
2
,
log log log logg x n g k p x� � �0 2 0 2 2 1,
ïîëó÷àåì ñëåäóþùåå óòâåðæäåíèå.
26 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4
Óòâåðæäåíèå 1. Äëèíà êîäîâîãî ñëîâà | ( ) # |,� g p x íå ïðåâûøàåò
c c x1 2 2� log , ãäå c1 è c2 — ñîîòâåòñòâóþùèå êîíñòàíòû.
Ïîäìíîæåñòâî êîäîâûõ ñëîâ U èç { }0 1, * íàçûâàåòñÿ óíèâåðñàëüíûì, åñëè
äëÿ ëþáîãî ïåðå÷èñëèìîãî ìíîæåñòâà äàííûõ M è ëþáîãî ðàñïðåäåëåíèÿ âåðî-
ÿòíîñòåé P, îïðåäåëåííîãî íà M , ïðèïèñûâàíèå äàííûõ â ïîðÿäêå óáûâàíèÿ âå-
ðîÿòíîñòåé ñëîâàì èç U â ïîðÿäêå âîçðàñòàíèÿ äëèí äàåò ñðåäíþþ îæèäàåìóþ
äëèíó êîäîâîãî ñëîâà, îãðàíè÷åííóþ âåëè÷èíîé c c H P1 2� ( ), ãäå c1 è c2 —
êîíñòàíòû, à H P( ) îáîçíà÷àåò ýíòðîïèþ ðàñïðåäåëåíèÿ.
Ïîíÿòèå óíèâåðñàëüíîãî êîäèðîâàíèÿ áûëî ââåäåíî Ï. Ýëèàñîì [13]. Ýòî ïîíÿ-
òèå îòðàæàåò ñâîéñòâî ïåðå÷èñëèìîãî ìíîæåñòâà ñëîâ áûòü ïî÷òè îïòèìàëüíûì êî-
äîì äëÿ ïðîèçâîëüíîãî èñòî÷íèêà äàííûõ ñ ëþáûì ðàñïðåäåëåíèåì âåðîÿòíîñòåé.
 [1], à òàêæå â íåñêîëüêî èíîì ïðåäñòàâëåíèè â [13] èìååòñÿ ñëåäóþùåå
óòâåðæäåíèå. Åñëè äëèíà êîäîâîãî ñëîâà äëÿ ÷èñëà x íå ïðåâûøàåò c c x1 2 2� log ,
òî òàêîå êîäèðîâàíèå âñåõ ÷èñåë ÿâëÿåòñÿ óíèâåðñàëüíûì.
Ó÷èòûâàÿ óòâåðæäåíèå 1, ïîëó÷àåì ñëåäóþùèé ôàêò.
Óòâåðæäåíèå 2. Ëþáîå ( , )g p -ïðåäñòàâëåíèå ÷èñåë çàäàåò óíèâåðñàëüíîå
ïðåôèêñíî-ñâîáîäíîå êîäèðîâàíèå ÷èñåë.
Íàèáîëåå ïðîñòîé ñèñòåìîé ( , )g p -ïðåäñòàâëåíèÿ ÷èñåë ÿâëÿåòñÿ (2,3)-ïðåä-
ñòàâëåíèå, (2,3)-çàäàíèå ÷èñåë ñîâïàäàåò ñ ïðåäñòàâëåíèåì (4) â ñèñòåìå
U � 0 1 2 22, , , ,� è V � 3 3, ,�
Ðàññìîòðèì ïðèìåð (2,3)-ðàçëîæåíèÿ:
20132013 3 6710671� �( )
� � � � � � � � �3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 322 18 17 13 10 9 7 2 2( ( ( ( ( ( ( ( )))))))).
Ôîðìàëüíûé àëãîðèòì (2,3)-ðàçëîæåíèÿ èìååò ñëåäóþùèé âèä:
Àëãîðèòì (2,3)-äåêîìïîçèöèÿ.
Âõîä: ïîëîæèòåëüíîå ÷èñëî x.
Ðåçóëüòàò: ìàññèâ A ïàð ( , )n ki i .
1. Ïðåäñòàâèòü x â âèäå x x
n k� 2 30 0
1, ãäå x1 — íå÷åòíîå ÷èñëî, êîòîðîå íå äå-
ëèòñÿ íà 3.
2. A n k[ ] ( , )0 0 0� , u x� 1.
3. Äî òåõ ïîð, ïîêà x �1 , âûïîëíÿòü
3.1. Ïðåäñòàâèòü u vn k� 2 3 , ãäå n — ìàêñèìàëüíàÿ ñòåïåíü òàêàÿ, ÷òî
u n� 2 3mod è u n �2 0, v — íå÷åòíîå ÷èñëî, âçàèìíî ïðîñòîå ñ ÷èñëîì 3.
3.2. i i� �1.
3.3. A i n k[ ] ( , )� , u v� .
4. Ðåçóëüòàò A.
Îêàçàëîñü, ÷òî (2,3)-êîäû îáëàäàþò ìíîãèìè ýôôåêòèâíûìè êà÷åñòâàìè [17].
Ïðè êîäèðîâàíèè ÷èñåë C âåëè÷èíà C x x( ) log 2 íàçûâàåòñÿ ïîòî÷å÷íîé èçáûòî÷-
íîñòüþ (pointwise redundancy).
Êîýôôèöèåíò ïîòî÷å÷íîé èçáûòî÷íîñòè îïðåäåëÿåòñÿ êàê
lim
( ) log
logx
C x x
x�
2
2
.
Äëÿ (2,3)-êîäîâ ñðåäíåå îæèäàåìîå çíà÷åíèå êîýôôèöèåíòà èçáûòî÷íîñòè
ðàâíî 0,16. Äëÿ êîäèðîâàíèÿ Ôèáîíà÷÷è òàêîå çíà÷åíèå âñåãäà ðàâíî 0,44.
(2,3)-êîäû ÿâëÿþòñÿ ñàìîñèíõðîíèçèðóþùèìèñÿ è îáëàäàþò ñâîéñòâàìè ïîâû-
øåííîé óñòîé÷èâîñòè ê èñêàæåíèÿì.
Ïîäðîáíîå èçó÷åíèå (2,3)-ïðåäñòàâëåíèÿ ÷èñåë áûëî íà÷àòî àâòîðîì ýòîé ðàáî-
òû â [16]. Àñèìïòîòè÷åñêèå õàðàêòåðèñòèêè è ñâîéñòâà (2-3)-êîäîâ èçó÷àëèñü [17].
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4 27
ÇÀÊËÞ×ÅÍÈÅ
Êàê ïîêàçûâàåò äàííûé îáçîð, äâóõáàçèñíîå êîäèðîâàíèå ÷èñåë ïðåäëàãàåò øèðîêèé
ñïåêòð ñðåäñòâ äëÿ ðåøåíèÿ ìíîãèõ ïðèêëàäíûõ çàäà÷. Äâóõáàçèñíîå çàäàíèå ÷èñåë
ïðåäñòàâëÿåò èíòåðåñ êàê ìíîãîìåðíîå îáîáùåíèå èçâåñòíûõ ñèñòåì ñ÷èñëåíèÿ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. A p o s t o l i c o A . , F r a e n k e l A . Robust transmission of unbounded strings using Fibonacci
representations // IEEE Trans. form. Theory. — 1987. — IT-33, N 2. — P. 238–245.
2. K l e i n S . T . , B e n - N i s s a n M . K . On the usefulness of Fibonacci compression codes // The
Computer J. — 2010. — 53, N 6. — P. 701–716.
3. K l e i n S . T . Fast decoding of Fibonacci encoded texts / Proc. Intern., Data Compression Conf.
(DCC), 2007 // IEEE Computer Society (USA), 2007. — P. 388.
4. K l e i n S . T . , B e n - N i s s a n M . K . Using Fibonacci compression codes as alternatives to
dense codes / Proc. Intern., Data Compression Conf. (DCC), 2008 // IEEE Computer Society (USA),
2008. — P. 472–481.
5. h t t p :/ocis.org.
6. F e n w i c k P . Variable length integer codes based on the Goldbach conjecture and other additive
codes // IEEE Trans. Inform. Theory. — 2002. — 48, N 8. — P. 2412–2417.
7. À í è ñ è ì î â À . Â . , Ð û í ä è í ß . Ï . , Ð å ä ü ê î Ñ . Å . Îáðàòíîå ïðåîáðàçîâàíèå
Ôèáîíà÷÷è // Êèáåðíåòèêà. — 1982. — ¹ 3. — Ñ. 9–11.
8. À í è ñ è ì î â À .  . Ëèíåéíûå ôîðìû Ôèáîíà÷÷è è ïàðàëëåëüíûå àëãîðèòìû áîëüøîé
ðàçìåðíîñòè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1995. — ¹ 3. — Ñ. 106–115.
9. A n i s i m o v A . V . Linear Fibonacci forms and parallel algorithms for high dimension arithmetic //
Lect. Notes Comput. Sci. — 1995. — 964. — P. 16–20.
10. À í è ñ è ì î â À .  . Àëãîðèòì³÷íà òåîð³ÿ âåëèêèõ ÷èñåë. Ìîäóëÿðíà àðèôìåòèêà âåëèêèõ
÷èñåë. — Êè¿â: Àêàäåìïåð³îäèêà, 2001. — 153 ñ.
11. Ì å ê ó ø Î . à . Àëîãðèòìè ìîäóëÿðíî¿ àðèôìåòèêè âåëèêèõ ÷èñåë: Àâòîðåô. äèñ. ... êàíä.
ô³ç.-ìàò. íàóê / ÊÍÓ ³ìåí³ Òàðàñà Øåâ÷åíêà. — Êè¿â, 2005. — 17 ñ.
12. H a f f m a n D . A . Method for construction of minimum-redundancy codes // Proc. the IRE. —
1952. — 40, N 9. — P. 1098–1101.
13. E l i a s P . Universal codeword sets and representations of the integers // IEEE Trans. Inform.
Theory. — 1975. — 21, N 2. — P. — 194–203.
14. Ë å â å í ø ò å é í  . È . Îá èçáûòî÷íîñòè è çàìåäëåíèè ðàçäåëèìîãî êîäèðîâàíèÿ
íàòóðàëüíûõ ÷èñåë // Ïðîáë. êèáåðíåòèêè. — 1968. — ¹ 20. — Ñ. 173–179.
15. S a l o m o n D . Variable-length codes for data compression. — London: Springer-Verlag London
Limited. — 2007. — Sept. — 192 p.
16. À í è ñ è ì î â À .  . Ïðåäñòàâëåíèå ÷èñåë â ñìåøàííîì áàçèñå (2,3) // Êèáåðíåòèêà
è ñèñòåìíûé àíàëèç. — 2009. — ¹ 4. — P. 3–18.
17. A n i s i m o v A . Prefix encoding by means of the (2,3)-representation of numbers // IEEE Trans.
Inform. Theory. — 2013. — 59, N 4. — P. 2359–2374.
Ïîñòóïèëà 04.01.2013
28 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4
|
| id | nasplib_isofts_kiev_ua-123456789-86249 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T17:44:04Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Анисимов, А.В. 2015-09-11T16:50:24Z 2015-09-11T16:50:24Z 2013 Представление чисел в двухбазисных системах счисления / А.В. Анисимов // Кибернетика и системный анализ. — 2013. — Т. 49, № 4. — С. 17-28. — Бібліогр.: 17 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/86249 519.72 Вводяться двобазисні системи числення, що узагальнюють стандартні системи числення, основані на розкладанні чисел за степенями заданого базисного числа. Наведено результати, а також приклад застосування для кодування чисел і дерев. Розглянуто напрямки подальших досліджень. Запропоновано новий паралельний алгоритм модулярного піднесення до степеня. Вказано новий клас універсальних префіксних кодів. Two-base numeration systems are introduced in the paper. They are generalizations of standard numeration systems, which are based on powers of a given radix. The results are reviewed and applications for encoding numbers and trees are given. Further research fields are outlined. A new parallel algorithm for modular exponentiation and new classes of prefix codes are presented. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Представление чисел в двухбазисных системах счисления Представлення чисел в двобазисних системах числення Two-base numeration systems Article published earlier |
| spellingShingle | Представление чисел в двухбазисных системах счисления Анисимов, А.В. Кибернетика |
| title | Представление чисел в двухбазисных системах счисления |
| title_alt | Представлення чисел в двобазисних системах числення Two-base numeration systems |
| title_full | Представление чисел в двухбазисных системах счисления |
| title_fullStr | Представление чисел в двухбазисных системах счисления |
| title_full_unstemmed | Представление чисел в двухбазисных системах счисления |
| title_short | Представление чисел в двухбазисных системах счисления |
| title_sort | представление чисел в двухбазисных системах счисления |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/86249 |
| work_keys_str_mv | AT anisimovav predstavleniečiselvdvuhbazisnyhsistemahsčisleniâ AT anisimovav predstavlennâčiselvdvobazisnihsistemahčislennâ AT anisimovav twobasenumerationsystems |