О двух типах нелинейных автоматов над конечным кольцом
The paper analyzes the structure of a class of automata being analogs over a finite ring of chaotic dynamical systems such as Guckenheimer and Holmes cycles and free-running systems. Problems of parametric identification and identification of initial state are solved, and a set of fixed points of au...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2009 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/44384 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О двух типах нелинейных автоматов над конечным кольцом / В.В. Скобелев // Кибернетика и системный анализ. — 2009. — № 4. — С. 57-68. — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-44384 |
|---|---|
| record_format |
dspace |
| spelling |
Скобелев, В.В. 2013-05-31T20:25:28Z 2013-05-31T20:25:28Z 2009 О двух типах нелинейных автоматов над конечным кольцом / В.В. Скобелев // Кибернетика и системный анализ. — 2009. — № 4. — С. 57-68. — Бібліогр.: 7 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44384 510.5+681.3 The paper analyzes the structure of a class of automata being analogs over a finite ring of chaotic dynamical systems such as Guckenheimer and Holmes cycles and free-running systems. Problems of parametric identification and identification of initial state are solved, and a set of fixed points of automata mappings are characterized. Досліджено структуру класу автоматів, які є аналогами над скінченим кільцем симетричних хаотичних динамічних систем, а саме Guckenheimer and Holmes cycle та free-running system. Вирішено задачі параметричної ідентифікації та ідентифікації початкового стану, а також охарактеризовано множину нерухомих точок відповідних автоматних відображень. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика О двух типах нелинейных автоматов над конечным кольцом Про два типа нелінійних автоматів над скінченим кільцем Two types of nonlinear automata over a finite ring Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
О двух типах нелинейных автоматов над конечным кольцом |
| spellingShingle |
О двух типах нелинейных автоматов над конечным кольцом Скобелев, В.В. Кибернетика |
| title_short |
О двух типах нелинейных автоматов над конечным кольцом |
| title_full |
О двух типах нелинейных автоматов над конечным кольцом |
| title_fullStr |
О двух типах нелинейных автоматов над конечным кольцом |
| title_full_unstemmed |
О двух типах нелинейных автоматов над конечным кольцом |
| title_sort |
о двух типах нелинейных автоматов над конечным кольцом |
| author |
Скобелев, В.В. |
| author_facet |
Скобелев, В.В. |
| topic |
Кибернетика |
| topic_facet |
Кибернетика |
| publishDate |
2009 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Про два типа нелінійних автоматів над скінченим кільцем Two types of nonlinear automata over a finite ring |
| description |
The paper analyzes the structure of a class of automata being analogs over a finite ring of chaotic dynamical systems such as Guckenheimer and Holmes cycles and free-running systems. Problems of parametric identification and identification of initial state are solved, and a set of fixed points of automata mappings are characterized.
Досліджено структуру класу автоматів, які є аналогами над скінченим кільцем симетричних хаотичних динамічних систем, а саме Guckenheimer and Holmes cycle та free-running system. Вирішено задачі параметричної ідентифікації та ідентифікації початкового стану, а також охарактеризовано множину нерухомих точок відповідних автоматних відображень.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/44384 |
| citation_txt |
О двух типах нелинейных автоматов над конечным кольцом / В.В. Скобелев // Кибернетика и системный анализ. — 2009. — № 4. — С. 57-68. — Бібліогр.: 7 назв. — рос. |
| work_keys_str_mv |
AT skobelevvv odvuhtipahnelineinyhavtomatovnadkonečnymkolʹcom AT skobelevvv prodvatipanelíníinihavtomatívnadskínčenimkílʹcem AT skobelevvv twotypesofnonlinearautomataoverafinitering |
| first_indexed |
2025-11-26T02:44:54Z |
| last_indexed |
2025-11-26T02:44:54Z |
| _version_ |
1850608778507976704 |
| fulltext |
ÓÄÊ 510.5+681.3
Â.Â. ÑÊÎÁÅËÅÂ
Î ÄÂÓÕ ÒÈÏÀÕ ÍÅËÈÍÅÉÍÛÕ ÀÂÒÎÌÀÒÎÂ
ÍÀÄ ÊÎÍÅ×ÍÛÌ ÊÎËÜÖÎÌ
Êëþ÷åâûå ñëîâà: ýêâèâàëåíòíûå ñîñòîÿíèÿ, èäåíòèôèêàöèÿ ñîñòîÿíèé, ïàðà-
ìåòðè÷åñêàÿ èäåíòèôèêàöèÿ, íåïîäâèæíûå òî÷êè.
ÂÂÅÄÅÍÈÅ
 ðàáîòå [1] â êà÷åñòâå ìîäåëè ïîòî÷íîãî øèôðà ïðåäëîæåíî ðàññìàòðèâàòü îá-
ðàòèìûå íåëèíåéíûå àâòîìàòû íàä êîëüöîì �p pk k� �( , , )Z � ( p — ïðîñòîå ÷èñ-
ëî, k �N), äëÿ êîòîðûõ «íåëèíåéíîñòü» õàðàêòåðèçóåòñÿ òåì, ÷òî èçìåíåíèå çíà-
÷åíèé ïåðåìåííûõ ñîñòîÿíèé è âûõîäíûõ ïåðåìåííûõ ïðåäñòàâëåíî àëãåáðàè-
÷åñêîé ñóììîé êâàäðàòè÷íîé è ëèíåéíîé ôîðì îò ïåðåìåííûõ ñîñòîÿíèé
ñ ëèíåéíîé ôîðìîé îò âõîäíûõ ïåðåìåííûõ. Âûáîð ýòîãî òèïà «íåëèíåéíîñòè»
îáóñëîâëåí òåì, ÷òî àíàëîãè íàä êîëüöîì �
pk äëÿ áîëüøîãî ÷èñëà ìîäåëüíûõ
õàîòè÷åñêèõ äèíàìè÷åñêèõ ñèñòåì [2] óêëàäûâàþòñÿ â ðàìêè èìåííî òàêîé ìî-
äåëè. Îäíàêî èññëåäîâàííûå â [3] õàîòè÷åñêèå äèíàìè÷åñêèå ñèñòåìû
Guckenheimer and Holmes cycle è free-running system íå îïèñûâàþòñÿ ìîäåëüþ,
ðàññìîòðåííîé â [1]. Èçìåíåíèå äèíàìè÷åñêèõ ïåðåìåííûõ â ïåðâîé ñèñòåìå
ïðåäñòàâëåíî ìíîãî÷ëåíàìè òðåòüåé ñòåïåíè, à âî âòîðîé îñóùåñòâëÿåòñÿ ñ ïî-
ìîùüþ ïîêàçàòåëüíîé ôóíêöèè (êàê èçâåñòíî, äèñêðåòíîå ëîãàðèôìèðîâàíèå —
áàçîâàÿ êîíñòðóêöèÿ ñîâðåìåííîé êðèïòîãðàôèè). Êðîìå òîãî, îáå ñèñòåìû èìå-
þò íåòðèâèàëüíûå ãðóïïû ñèììåòðèé (òåîðèÿ ñèììåòðèé [4] ïðåäñòàâëÿåò ñîáîé
ìîùíûé àïïàðàò àíàëèçà äèíàìè÷åñêèõ ñèñòåì). Ïîýòîìó êàê äëÿ òåîðèè àâòî-
ìàòîâ, òàê è äëÿ êðèïòîãðàôèè ïðåäñòàâëÿåò èíòåðåñ èññëåäîâàíèå àâòîìàòîâ,
ÿâëÿþùèõñÿ àíàëîãàìè íàä êîëüöîì �
pk ýòèõ ñèñòåì. Òàêèå àâòîìàòû èìåþò
ñîîòâåòñòâåííî âèä (x — âõîäíàÿ ïåðåìåííàÿ, q i( ) ( , , )i � 1 2 3 — ïåðåìåííûå ñî-
ñòîÿíèÿ àâòîìàòà, y i( ) ( , , )i � 1 2 3 — âûõîäíûå ïåðåìåííûå)
M
q q d a q b q c q
GH
n n n n n
�
� � � �
�1
1 1 1 2 2 2 3( ) ( ) ( ) ( ) (( ( ) ( ) (� � � �
)
( ) ( ) ( ) ( )
) ) ,
( ( ) ( )
2
1 1
1
2 2 1 2 2
�
� � �
�
�
� �
� � �
x
q q d c q a q
n
n n n n
2 3 2
2 1
1
3 3 1 2
� �
� � �
�
�
b q x
q q d b q
n n
n n n
� �
� �
( ) ) ,
( ( )
( )
( ) ( ) ( )
�
c q a q x
y q i
n n n
n
i
n
i
� � �( ) ( ) ) ,
(
( ) ( )
( ) ( )
2 2 3 2
3 1
1 1
1
� �
� �
�
� �
�
, , ; ),2 3 n �
�
�
�
�
�
�
�
� �Z
(1)
ãäå � � �1 2 3, , — ôèêñèðîâàííûå îáðàòèìûå ýëåìåíòû êîëüöà �
pk ,
a b c d
pk, , , \ { }�Z 0 — ôèêñèðîâàííûå ýëåìåíòû êîëüöà �
pk ;
M
q f q x
q f q
FR
n n
q
n
n n
n
�
� �
�
� �
�
1
1 1
1 1
1
2 2
3
( ) ( )
( ) (
( ) ,
(
( )
� �� �
)
( ) ( )
) ,
( ) ,
( )
( )
� �
� �
� �
� �
q
n
n n
q
n
n
n
x
q f q x
1
2
2 1
1
3 3
3 1
�
� �
�
� �
y q i n
n
i
n
i
� � �� � �
�
�
�
�
�
�
�
�
1 1
1 2 3( ) ( ) ( , , ; ),Z
(2)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 4 57
© Â.Â. Ñêîáåëåâ, 2009
ãäå f x a x x( ) ( )� � � 1Î , ïðè÷åì � � � �1 2 3, , , — ôèêñèðîâàííûå îáðàòèìûå ýëå-
ìåíòû êîëüöà �
pk , a
pk
�Z \ { }0 — ôèêñèðîâàííûé ýëåìåíò êîëüöà �
pk . Îòìå-
òèì, ÷òî â [5] óñòàíîâëåí ðÿä õàðàêòåðèñòèê àâòîìàòîâ (1) è (2) â ïðåäïîëîæå-
íèè, ÷òî xn�
1 0 ( )n � �Z .
Öåëü ðàáîòû — èññëåäîâàíèå àâòîìàòîâ (1) è (2) ïðè xn
pk� �1 Z ( )n � �Z .
 ðàçä. 1 îïðåäåëåíû îñíîâíûå êîíå÷íî-àâòîìàòíûå õàðàêòåðèñòèêè ìîäåëåé (1) è
(2); â ðàçä. 2 ðåøåíû çàäà÷è ïàðàìåòðè÷åñêîé èäåíòèôèêàöèè è èäåíòèôèêàöèè íà-
÷àëüíîãî ñîñòîÿíèÿ; â ðàçä. 3 ïðèâåäåí àíàëèç ìíîæåñòâà íåïîäâèæíûõ òî÷åê èñ-
ñëåäóåìûõ àâòîìàòíûõ îòîáðàæåíèé; çàêëþ÷åíèå ñîäåðæèò ðÿä âûâîäîâ.
1. ÑÂÎÉÑÒÂÀ ÌÎÄÅËÅÉ
Îáîçíà÷èì �GH p k( , ) è �FR p k( , ) ìíîæåñòâî âñåõ àâòîìàòîâ ñîîòâåòñòâåííî
(1) è (2) íàä êîëüöîì �
pk
.
Óòâåðæäåíèå 1. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p ïðè âñåõ çíà÷åíèÿõ ÷èñëà k �N
ëþáîé àâòîìàò M p kGH GH� � ( , ), à òàêæå ëþáîé àâòîìàò M p kFR FR� � ( , ) ÿâëÿ-
þòñÿ îáðàòèìûìè.
Äîêàçàòåëüñòâî. Òàê êàê � � �1 2 3, , — îáðàòèìûå ýëåìåíòû êîëüöà �
pk , èç
ïåðâûõ òðåõ óðàâíåíèé ñèñòåì (1) è (2) íàõîäèì ñîîòâåòñòâåííî
x q q d a q b qn n n n n�
�
�
� � � �1 1
1
1
1 1 1 2 2 2� � � � �( ( ( ) ( )( ) ( ) ( ) ( )O c q
x q q d c q
n
n n n n
�
� � �
( ) )),
( ( ( )
( )
( ) ( ) ( )
3 2
1 2
1
1
2 2 1
�
�
�
� �� O 2 2 2 3 2
1 3
1
1
3 3
� �
��
�
�
a q b q
x q q
n n
n n n
� �
�
( ) ( ) )),
(
( ) ( )
( ) ( )� O � � � �( ( ) ( ) ( ) )) ( ),( ) ( ) ( )d b q c q a q nn n n� � � �
�
�
�
�
�
1 2 2 2 3 2 Z
�
�
(3)
x q f q
x q
n n n
q
n n
n
�
�
�
�
�
�
�
�
1 1
1
1
1 1
1 2
1
3
� �
�
� �
�
( ( ) ),
(
( ) ( )
( )
O
1
2 2
1 3
1
1
3 3
1
( ) ( )
( ) ( )
( ) ),
( ( )
( )
O
O
f q
x q f q
n
q
n n n
n
�
� �
�
��
�
�
� � qn n
( )
) ( ).
2
�
�
�
�
�
�
� �Z
(4)
Èç ïîñëåäíèõ òðåõ óðàâíåíèé ñèñòåì (1) è (2) èìååì
q yn
i
n
i( ) ( )� ( , , )i � 1 2 3 (5)
äëÿ âñåõ n � �Z , ïðè÷åì y q0 0� .
Ïîäñòàâèâ (5) â (3) è (4), à òàêæå çàìåíèâ ïåðåìåííóþ x ïåðåìåííîé y, ïåðå-
ìåííóþ y — ïåðåìåííîé x, ïîëó÷èì
M
y x x d a x b x
GH
n n n n n
�
�
�
�
�
� � �
1
1 1
1
1
1 1 1 2� � � � �( ( ( ) (( ) ( ) ( )O ( ) ( )
( ) ( )
) ( ) )),
( ( (
2 2 3 2
1 2
1
1
2 2
�
� ��
�
�
c x
y x x d c
n
n n n
�
� � �� O x a x b x
y x
n n n
n n
( ) ( ) ( )
( )
) ( ) ( ) )),
(
1 2 2 2 3 2
1 3
1
1
3
� �
��
�
�
� �
�� Ox d b x c x a x
n
n n n n
( ) ( ) ( ) ( )( ( ) ( ) ( ) ))
( )
3 1 2 2 2 3 2
� � � �� � �
� �Z ;
�
�
�
��
�
�
�
(6)
M
y x f x
y
FR
n n n
x
n
n
�
�
�
�
�
��
�
�1
1 1
1
1
1 1
1 2
3
� �
�
� �( ( ) ),( ) ( )
( )
O
1
1
2 2
1 3
1
1
3
1
� �
�
( ( ) ),
( (
( ) ( )
( )
( )
x f x
y x f x
n n
x
n n
n
�
�
�
�
�
O
O
�
� n
xn n( ) ) ) ( ).
( )
3
2
� � �
�
�
�
�
�
� �Z (7)
Óòâåðæäåíèå äîêàçàíî.
58 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 4
Ïðè èñïîëüçîâàíèè àâòîìàòà (1) èëè (2) â êà÷åñòâå ïîòî÷íîãî øèôðà ïàðà-
ìåòðû ïðåäñòàâëÿþò ñîáîé êëþ÷ ñðåäíåé äëèòåëüíîñòè, à íà÷àëüíîå ñîñòîÿíèå
q0 0
1
0
2
0
3� ( , , )( ) ( ) ( )q q q — ñåàíñîâûé êëþ÷. Ïðè ýòîì â ïðîöåññå «øèôðîâàíèå-ðàñ-
øèôðîâêà» êàê àâòîìàòû M p kGH GH� � ( , ) è M
GH
�1 , òàê è àâòîìàòû M FR �
� �FR p k( , ) è M
FR
�1 äâèæóòñÿ â ïðîñòðàíñòâå ñîñòîÿíèé ïî îäíîé è òîé æå òðàåêòî-
ðèè â îäíîì è òîì æå íàïðàâëåíèè.
Ïðåäñòàâèì ýëåìåíòû êîëüöà �
pk
äâîè÷íûìè ïîñëåäîâàòåëüíîñòÿìè äëèíû
l k p� �
log . Ðàññìîòðèì î÷åðåäíóþ âûõîäíóþ ïîñëåäîâàòåëüíîñòü � �1 3� l , ãå-
íåðèðóåìóþ àâòîìàòîì M p kGH GH� � ( , ) (ñîîòâåòñòâåííî àâòîìàòîì M FR �
� �FR p k( , )). Ïðåäïîëîæèì, ÷òî îøèáêè, ñîñòîÿùèå â èíâåðòèðîâàíèè çíà÷åíèé
áèòîâ, ìîãóò âîçíèêíóòü òîëüêî â ïðîöåññå ïåðåäà÷è èíôîðìàöèè ïî êàíàëó ñâÿçè.
Ïîäñîåäèíèì âûõîäû àâòîìàòà M
GH
�1 (àâòîìàòà M
FR
�1 ) ê âõîäàì ìàæîðèòàðíîé ñõå-
ìû. Èç (6) è (7) âûòåêàåò, ÷òî â ïðîöåññå ðàñøèôðîâêè îáíàðóæàòñÿ âñå òàêèå
îøèáêè, ÷òî � � �3 1 3 2 3 3
0i i i� � �� � � ( )i l�Z , à èñïðàâëåíû òîëüêî òå èç íèõ,
äëÿ êîòîðûõ â êàæäîé òðîéêå áèòîâ � � �
3 3 2 3 3i i i, ,� � ( )i l�Z îøèáêà ïðîèçîøëà
íå áîëåå ÷åì â îäíîì áèòå.
Óòâåðæäåíèå 2. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p ïðè âñåõ çíà÷åíèÿõ ÷èñëà
k �N
| ( , )| ( ) ( ( ))�GH
k kp k p p p p� � ��1 14 3 1 3 , (8)
| ( , )| ( ) ( ( ))�FR
k kp k p p p p� � ��1 14 1 4 . (9)
Äîêàçàòåëüñòâî. Â àâòîìàòå M p kGH GH� � ( , ) ïàðàìåòðû � � �1 2 3, , — îáðà-
òèìûå ýëåìåíòû êîëüöà �
pk
, à a b c d
pk, , , \ { }�Z 0 . ×èñëî îáðàòèìûõ ýëåìåíòîâ
êîëüöà �
pk ðàâíî p pk� �1 1( ) , à âûáîð ïàðàìåòðîâ � � �1 2 3, , , , , ,a b c d îñóùåñòâëÿ-
åòñÿ íåçàâèñèìî. Îòñþäà âûòåêàåò, ÷òî ðàâåíñòâî (8) èñòèííî.
 àâòîìàòå M p kFR FR� � ( , ) ïàðàìåòðû � � � �1 2 3, , , — îáðàòèìûå ýëåìåíòû
êîëüöà �
pk , à a pk�Z \ { }0 . Âûáîð ïàðàìåòðîâ � � � �1 2 3, , , , a îñóùåñòâëÿåòñÿ íåçà-
âèñèìî. Îòñþäà âûòåêàåò, ÷òî ðàâåíñòâî (9) èñòèííî.
Óòâåðæäåíèå äîêàçàíî.
Îõàðàêòåðèçóåì ñòðóêòóðó àâòîìàòîâ, ïðèíàäëåæàùèõ ìíîæåñòâàì �GH p k( , )
è �FR p k( , ) .
Óòâåðæäåíèå 3. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p ïðè âñåõ çíà÷åíèÿõ ÷èñëà k �N
ëþáîé àâòîìàò M p kGH GH� � ( , ), à òàêæå ëþáîé àâòîìàò M p kFR FR� � ( , ) íå ÿâ-
ëÿþòñÿ ñèëüíî ñâÿçíûìè àâòîìàòàìè.
Äîêàçàòåëüñòâî. Ïóñòü q Z0 0 0 0
3� �( , , )q q q
pk
. Èç (1) (ñîîòâåòñòâåííî èç (2))
âûòåêàåò, ÷òî q1 1 1 1� ( , , )q q q äëÿ ëþáîãî âõîäíîãî ñèìâîëà x pk1 �Z . Èíäóêöèåé
ïî äëèíå ñëîâà ìîæíî ïîêàçàòü, ÷òî qn n n nq q q� ( , , ) äëÿ ëþáîãî âõîäíîãî ñëîâà
x xn
p
n
k1 � �Z .
Ïîñêîëüêó � — îáðàòèìûé ýëåìåíò êîëüöà �
pk , èç (1) (ñîîòâåòñòâåííî èç (2))
âûòåêàåò, ÷òî äëÿ ëþáûõ ôèêñèðîâàííûõ ñîñòîÿíèé q Z� �( , , )q q q
pk
3 è
~ (~, ~, ~)q Z� �q q q
pk
3 àâòîìàòà M p kGH GH� � ( , ) (àâòîìàòà M p kFR FR� � ( , )) ñóùå-
ñòâóåò åäèíñòâåííûé âõîäíîé ñèìâîë x
pk�Z , ïåðåâîäÿùèé ñîñòîÿíèå q â ñîñòîÿíèå ~q .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 4 59
Ñëåäîâàòåëüíî, ñîáñòâåííîå ïîäìíîæåñòâî S q q q q
pk1 � � �{ ( , , )|q Z } ñîñòîÿ-
íèé àâòîìàòà M p kGH GH� � ( , ) (àâòîìàòà M p kFR FR� � ( , )) îïðåäåëÿåò êîìïî-
íåíòó ñèëüíîé ñâÿçàííîñòè. Îòñþäà âûòåêàåò, ÷òî àâòîìàò M p kGH GH� � ( , ) (àâ-
òîìàò M p kFR FR� � ( , )) íå ÿâëÿåòñÿ ñèëüíî ñâÿçíûì àâòîìàòîì.
Óòâåðæäåíèå äîêàçàíî.
Èç äîêàçàòåëüñòâà óòâåðæäåíèÿ 3 âûòåêàåò ñëåäñòâèå.
Ñëåäñòâèå 1. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p ïðè âñåõ çíà÷åíèÿõ ÷èñëà k �N êàê
ïîäàâòîìàò àâòîìàòà M p kGH GH� � ( , ) , òàê è ïîäàâòîìàò àâòîìàòà M FR �
� �FR p k( , ), îïðåäåëÿåìûé ìíîæåñòâîì ñîñòîÿíèé S q q q q pk1 � � �{ ( , , )|q Z }, ÿâ-
ëÿþòñÿ ïðèâåäåííûìè ïåðåñòàíîâî÷íûìè àâòîìàòàìè, äèàìåòð ãðàôà ïåðåõîäîâ
êîòîðûõ ðàâåí 1.
Ñëåäóþùåå óòâåðæäåíèå ïîêàçûâàåò, ÷òî ñòðóêòóðà àâòîìàòà MGH �
� �GH p k( , ) ìîæåò ñóùåñòâåííî îòëè÷àòüñÿ îò ñòðóêòóðû åãî ïîäàâòîìàòà, îïðåäå-
ëÿåìîãî ìíîæåñòâîì ñîñòîÿíèé S1.
Óòâåðæäåíèå 4. Ïóñòü
d p k
�
0 0 5( ),mod . (10)
Òîãäà äëÿ ïðîñòîãî ÷èñëà p ïðè âñåõ çíà÷åíèÿõ ÷èñëà k �N ìíîæåñòâî ñîñòîÿ-
íèé
S q q q q p ii k
2
1 2 3 0 50 1 2 3� �
��
{ ( , , ) | ( ) ( , , )( ) ( ) ( ) ( ) ,q mod } (11)
àâòîìàòà M p kGH GH� � ( , ) ïîä äåéñòâèåì ëþáîãî âõîäíîãî ñèìâîëà x
pk�Z ïå-
ðåõîäèò â îäíî è òî æå ñîñòîÿíèå
q1 1 2 3� ( , , )� � �� � �x x x . (12)
Äîêàçàòåëüñòâî. Ïóñòü âûïîëíåíî óñëîâèå (10) è q0
1 2 3
2� �( , , )( ) ( ) ( )q q q S .
Ïîñêîëüêó q p ii k( ) ,( ) ( , , )
��
0 1 2 30 5mod , èìååì
( )( )q i 2 0� ( , , )i � 1 2 3 . (13)
Òàê êàê q p ii k( ) ,( ) ( , , )
��
0 1 2 30 5mod è d p k
�
0 0 5( ),mod , ïîëó÷àåì
q d ii( ) ( , , )� � �0 1 2 3 . (14)
Èç (1), (13) è (14) âûòåêàåò, ÷òî ïîä äåéñòâèåì ëþáîãî âõîäíîãî ñèìâîëà
x pk�Z ñîñòîÿíèå q0 ïåðåõîäèò â ñîñòîÿíèå q1, îïðåäåëÿåìîå ðàâåíñòâîì (12).
Óòâåðæäåíèå äîêàçàíî.
Èç óòâåðæäåíèÿ 4 âûòåêàåò cëåäñòâèå.
Ñëåäñòâèå 2. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p ïðè âñåõ çíà÷åíèÿõ ÷èñëà k �N,
åñëè d p k
�
0 0 5( ),mod , òî ëþáîé àâòîìàò M p kGH GH� � ( , ) íå ÿâëÿåòñÿ ïåðåñòà-
íîâî÷íûì àâòîìàòîì.
Èç (2) âûòåêàåò, ÷òî äëÿ àâòîìàòà M p kFR FR� � ( , ) èìååò ìåñòî ñëåäóþùåå
óòâåðæäåíèå.
Óòâåðæäåíèå 5. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p ïðè âñåõ çíà÷åíèÿõ ÷èñëà k �N
ìíîæåñòâî ñîñòîÿíèé S q q q q q ii
3
1 2 3 0 1 1 2 3� � � �{ ( , , )| { , }( , , )}( ) ( ) ( ) ( ) ëþáîãî
àâòîìàòà M p kFR FR� � ( , ) ïîä äåéñòâèåì ëþáîãî âõîäíîãî ñèìâîëà x
pk�Z
ïåðåõîäèò â îäíî è òî æå ñîñòîÿíèå q1 1 2 3� ( , , , )� � �� � �x x x .
Èç óòâåðæäåíèÿ 5 âûòåêàåò cëåäñòâèå.
Ñëåäñòâèå 3. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p ïðè âñåõ çíà÷åíèÿõ ÷èñëà k �N
ëþáîé àâòîìàò M p kFR FR� � ( , ) íå ÿâëÿåòñÿ ïåðåñòàíîâî÷íûì àâòîìàòîì.
60 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 4
Îáîçíà÷èì K M u( , )q ( { , })u GH FR� ìíîæåñòâî âñåõ ñîñòîÿíèé àâòîìàòà
M p ku u� � ( , ), ýêâèâàëåíòíûõ ñîñòîÿíèþ q Z�
pk
3 .
Òåîðåìà 1. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p ïðè âñåõ çíà÷åíèÿõ ÷èñëà k �N äëÿ
ëþáîãî àâòîìàòà M p kGH GH� � ( , ) è ëþáîãî ñîñòîÿíèÿ q Z� �( , , )( ) ( ) ( )q q q
pk
1 2 3 3
ìíîæåñòâî K MGH( , )q ñîñòîèò èç âñåõ òàêèõ ñîñòîÿíèé ~ (~ , ~ , ~ )( ) ( ) ( )q Z� �q q q
pk
1 2 3 3 ,
÷òî èñòèííû ðàâåíñòâà
~ ( (~ ) (~ ) (~ ) )
(
( ) ( ) ( ) ( )
( )
q d a q b q c q
q
1 1 2 2 2 3 2
1
� � � �
�
� � � �
� d a q b q c q
q d c q
� � �
�
� � �
� �
( ) ( ) ( ) ),
~ ( (~
( ) ( ) ( )
( ) ( )
1 2 2 2 3 2
2 1 ) (~ ) (~ ) )
( ( ) (
( ) ( )
( ) ( ) (
2 2 2 3 2
2 1 2
� � �
� � �
a q b q
q d c q a q
� �
� � �
2 2 3 2
3 1 2 2 2
) ( )
( ) ( ) ( )
) ( ) ),
~ ( (~ ) (~ ) (
�
� � �
b q
q d b q c q a
�
� � � �
~ ) )
( ( ) ( ) ( ) ).
( )
( ) ( ) ( ) ( )
q
q d b q c q a q
3 2
3 1 2 2 2 3 2
�
� � � �
�
� � � �
�
�
�
�
��
�
�
�
�
�
(15)
Äîêàçàòåëüñòâî. Çàôèêñèðóåì ñîñòîÿíèå q Z� �( , , )( ) ( ) ( )q q q
pk
1 2 3 3 àâòîìàòà
M p kGH GH� � ( , ). Ïóñòü ~ (~ , ~ , ~ ) ( , )( ) ( ) ( )q q� �q q q K MGH
1 2 3 . Èç ïåðâûõ òðåõ óðàâ-
íåíèé ñèñòåìû (1) íàõîäèì, ÷òî äëÿ ëþáîãî âõîäíîãî ñèìâîëà x pk�Z
q q d a q b q c q x
1
1 1 1 2 2 2 3 2
1
( ) ( ) ( ) ( ) ( )( ( ) ( ) ( ) ) ,� � � � �� � � � ��
q q d c q a q b q x
1
2 2 1 2 2 2 3 2
2
( ) ( ) ( ) ( ) ( )( ( ) ( ) ( ) ) ,� � � � �� � � � ��
q q d b q c q a q x
1
3 3 1 2 2 2 3 2
3
( ) ( ) ( ) ( ) ( )( ( ) ( ) ( ) ) ,� � � � �� � � � ��
�
�
�
�
�
�
(16)
~ ~ ( (~ ) (~ ) (~ ) )( ) ( ) ( ) ( ) ( )q q d a q b q c q
1
1 1 1 2 2 2 3 2� � � � �� � � � �1
1
2 2 1 2 2 2 3
�
� � � �
x
q q d c q a q b q
,
~ ~ ( (~ ) (~ ) (~( ) ( ) ( ) ( ) (� � � � )
( ) ( ) ( ) ( )
) ) ,
~ ~ ( (~ ) (~ )
2
2
1
3 3 1 2 2 2
�
� � � �
� �
� � � �
x
q q d b q c q a (~ ) ) .( )q x3 2
3�
�
�
�
�
�
� � �
(17)
Ïîñêîëüêó q è ~q — ýêâèâàëåíòíûå ñîñòîÿíèÿ àâòîìàòà M p kGH GH� � ( , ) , èç
ïîñëåäíèõ òðåõ óðàâíåíèé ñèñòåìû (1) âûòåêàåò
q qi i
1 1
( ) ( )~� ( , , )i � 1 2 3 . (18)
Èç ôîðìóë (16)–(18) ñëåäóåò (15).
Òåîðåìà äîêàçàíà.
Èç äîêàçàòåëüñòâà òåîðåìû 1 âûòåêàåò ñëåäñòâèå.
Ñëåäñòâèå 4. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p ïðè âñåõ çíà÷åíèÿõ ÷èñëà k �N
ëþáûå ýêâèâàëåíòíûå îäèí äðóãîìó ñîñòîÿíèÿ ëþáîãî àâòîìàòà MGH �
� �GH p k( , ) — áëèçíåöû.
Òåîðåìà 2. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p ïðè âñåõ çíà÷åíèÿõ ÷èñëà k �N äëÿ
ëþáîãî àâòîìàòà M p kFR FR� � ( , ) è ëþáîãî ñîñòîÿíèÿ q Z� �( , , )( ) ( ) ( )q q q
pk
1 2 3 3
ìíîæåñòâî K M FR( , )q ñîñòîèò èç âñåõ òàêèõ ñîñòîÿíèé ~ (~ , ~ , ~ )( ) ( ) ( )q Z� �q q q
pk
1 2 3 3 ,
÷òî èñòèííû ðàâåíñòâà
f q f q
f q
q q
q q
(~ ) ( ),
(~ )
( ) ~ ( )
( ) ~
( ) ( )
( ) ( )
1 1
2
3 3
1 1
�
�
�
�
�
�
�
� f q
f q f qq q
( ),
(~ ) ( ).
( )
( ) ~ ( )
( ) ( )
2
3 3
2 2
� � � �
�
�
�
�
�
�
(19)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 4 61
Äîêàçàòåëüñòâî. Çàôèêñèðóåì ñîñòîÿíèå q Z� �( , , )( ) ( ) ( )q q q
pk
1 2 3 3 àâòîìàòà
M p kFR FR� � ( , ) . Ïóñòü ~ (~ , ~ , ~ ) ( , )( ) ( ) ( )q q� �q q q K M FR
1 2 3 . Èç ïåðâûõ òðåõ óðàâíå-
íèé ñèñòåìû (2) íàõîäèì, ÷òî äëÿ ëþáîãî âõîäíîãî ñèìâîëà x
pk�Z
q f q x
q f q
q
n
q
1
1 1
1 1
1
2 2
2
3
1
( ) ( )
( ) ( )
( ) ,
( )
( )
( )
� �
� �
�� �
�
� �
� � �
� �
x
q f q x
n
q
n
�
�� �
�
�
�
�
�
�
1
1
3 3
3 1
2
,
( ) ,( ) ( )
( )
� �
(20)
~ (~ ) ,
~ (~ )
( ) ( ) ~
( ) ( ) ~
( )
q f q x
q f q
q
n
q
1
1 1
1 1
1
2 2
3
� �
�
�� �
�
� �
�
( )
( )
,
~ (~ ) .( ) ( ) ~
1
2
2 1
1
3 3
3 1
�
� �
�
�
�
�
�
�
�
�
�
� �
�
� �
x
q f q x
n
q
n
(21)
Ïîñêîëüêó q è ~q — ýêâèâàëåíòíûå ñîñòîÿíèÿ àâòîìàòà M FR , èç ïîñëåäíèõ
òðåõ óðàâíåíèé ñèñòåìû (2) âûòåêàåò
q qi i
1 1
( ) ( )~� ( , , )i � 1 2 3 . (22)
Èç (20)–(22) ñëåäóåò
f q x f q x
f q
q
n
q
n( ) (~ ) ,
(
( ) ( ) ~
(
( ) ( )
1
1 1
1
1 1
3 3
� � � �� � � �� � �� �
2
2 1
2
2 1
3
1 1
) ( ) ~
( )
) (~ ) ,
( )
( ) ( )
� � � �� � � �q
n
q
nx f q x
f q
� � � �� �
� � � �� � � �q
n
q
nx f q x
( ) ( )
(~ )( ) ~2 2
3 1
3
3 1� � �
�
�
�
�
�
� � �
�
�
�
f q f q
f q f q
q q
q
( ) (~ ) ,
( ) (~
( ) ( ) ~
( ) (
( ) ( )
( )
1 1
2
3 3
1
� �
�
� �
� 2
3 3
1
2 2
) ~
( ) ( ) ~
) ,
( ) (~ ) .
( )
( ) ( )
�
� �
�
� �
q
q qf q f q�
�
�
�
�
�
�
(23)
Òàê êàê � — îáðàòèìûé ýëåìåíò êîëüöà �
pk , èç (23) ñëåäóþò ðàâåíñòâà (19).
Òåîðåìà äîêàçàíà.
Èç äîêàçàòåëüñòâà òåîðåìû 2 âûòåêàåò ñëåäñòâèå.
Ñëåäñòâèå 5. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p ïðè âñåõ çíà÷åíèÿõ ÷èñëà k �N
ëþáûå ýêâèâàëåíòíûå îäèí äðóãîìó ñîñòîÿíèÿ ëþáîãî àâòîìàòà M FR �
� �FR p k( , ) — áëèçíåöû.
Ìíîæåñòâî K M FR( , )q ìîæåò áûòü âû÷èñëåíî ñëåäóþùèì îáðàçîì. Ïóñòü �
ïðèíàäëåæèò ïîêàçàòåëþ �, ò.å. � — òàêîå íàèìåíüøåå íàòóðàëüíîå ÷èñëî, ÷òî
� �
1( )mod pk . Ïðåäñòàâèì êîìïîíåíòû ñîñòîÿíèÿ q Z� �( , , )( ) ( ) ( )q q q
pk
1 2 3 3
â âèäå q bi h
i
i( ) � � � ( , , )i � 1 2 3 , ãäå ( , )bi � � 1 ( , , )i � 1 2 3 . Èç (19) âûòåêàåò, ÷òî
êîìïîíåíòû ëþáîãî ñîñòîÿíèÿ ~ (~ , ~ , ~ ) ( , )( ) ( ) ( )q q� �q q q K M FR
1 2 3 óäîâëåòâîðÿþò
ðàâåíñòâàì
f q b
f q b
f q b
l
l
l
(~ ) ,
(~ ) ,
(~ ) .
( )
( )
( )
1
1
2
2
3
3
3
1
2
�
�
�
�
�
�
�
�
�
�
�
��
�
�
(24)
62 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 4
Èç (19) è (24) âûòåêàåò
~ ( ),
~ ( ),
~
( ) ( )
( ) ( )
(
q h q l
q h q l
q
1
1
1
1
2
2
2
2
3
�
�
O mod
O mod
�
�
) ( ) ( ).
�
�
�
��
�
� h q l3
3
3O mod �
(25)
Èòàê, äëÿ ïîñòðîåíèÿ ìíîæåñòâà K M FR( , )q äîñòàòî÷íî íàéòè âñå ðåøåíèÿ
(~ , ~ , ~ )( ) ( ) ( )q q q1 2 3 ñèñòåì ñðàâíåíèé (25) ïðè âñåõ çíà÷åíèÿõ l l l1 2 3 0 1 1, , { , , , }� �� � . Ïðè
ýòîì (~ , ~ , ~ ) ( , )( ) ( ) ( )q q q K M FR
1 2 3 � q òîãäà è òîëüêî òîãäà, êîãäà èñòèííû ðàâåíñòâà (24).
2. ÈÄÅÍÒÈÔÈÊÀÖÈß ÌÎÄÅËÅÉ
Ðàññìîòðèì çàäà÷ó ïàðàìåòðè÷åñêîé èäåíòèôèêàöèè àâòîìàòà M p ku u� � ( , )
( , )u GH FR� â ïðåäïîëîæåíèè, ÷òî ýêñïåðèìåíòàòîð ìîæåò óïðàâëÿòü âõîäîì è
èíèöèàëèçàöèåé àâòîìàòà.
Óòâåðæäåíèå 6. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p ïðè âñåõ çíà÷åíèÿõ ÷èñëà k �N
èäåíòèôèêàöèÿ ïàðàìåòðîâ � � �1 2 3, , ëþáîãî àâòîìàòà M p kGH GH� � ( , ) è
M p kFR FR� � ( , ) îñóùåñòâëÿåòñÿ ïðîñòûì ýêñïåðèìåíòîì äëèíû 1.
Äîêàçàòåëüñòâî. Ïîëîæèì q q q
0
1
0
2
0
3 0( ) ( ) ( )� � � è x � 1. Èç ðàâåíñòâ (1), (2) âû-
òåêàåò � i
iy�
1
( ) ( , , )i � 1 2 3 .
Óòâåðæäåíèå äîêàçàíî.
Òåîðåìà 3. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p ïðè âñåõ çíà÷åíèÿõ ÷èñëà k �N èäåí-
òèôèêàöèÿ ïàðàìåòðîâ b è c ëþáîãî àâòîìàòà M p kGH GH� � ( , ) îñóùåñòâëÿåòñÿ
êðàòíûì ýêñïåðèìåíòîì êðàòíîñòè 2 è âûñîòû 1.
Äîêàçàòåëüñòâî. Ïîëîæèâ q0 1 0 0� ( , , ) è x1 0� , èç (1) íàõîäèì
d a y� �
1
1( ) . (26)
Ïîëîæèâ ~ ( , , )q0 1 1 0� è x'
1 0� , èç (1) ïîëó÷àåì
d a b y
d a c y
� � �
� � �
�
�
�
�
~ ,
~ .
( )
( )
1
1
1
2
(27)
Èç (26) è (27) èìååì
b y y
c y y
�
�
�
�
�
�
~ ,
~ .
( ) ( )
( ) ( )
1
1
1
1
1
2
1
1
O
O
Òåîðåìà äîêàçàíà.
Òåîðåìà 4. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p � 3 ïðè âñåõ çíà÷åíèÿõ ÷èñëà k �N
èäåíòèôèêàöèÿ ïàðàìåòðîâ a è d ëþáîãî àâòîìàòà M p kGH GH� � ( , ) ñâîäèòñÿ
ê ðåøåíèþ ñèñòåìû äâóõ ëèíåéíûõ óðàâíåíèé, ñôîðìèðîâàííîé â ðåçóëüòàòå ïðî-
ñòîãî ýêñïåðèìåíòà äëèíû 1.
Äîêàçàòåëüñòâî. Ïîëîæèâ q0 1 2 0� ( , , ) è x1 0� , èç (1) íàõîäèì
d a b y
d p a c y
� � �
� � �
�
�
�
�
�
4
2 8 2
1
1
1
2
�
� � �
( )
( )
,
( ( ))mod
d a y b
d p a y c
� �
� �
�
�
�
�
�
1
1
1
2
4
2 8 2
( )
( )
,
( ( ))
O
mod O
�
� � �
�
� �
�
( ( ) ) ( ( )) ,( ) ( )
(
8 2 2 2 8
1
2
1
1
1
mod O O O modp a y y c p b
d y
� � � �
1 4) .O O� b a
�
�
�
�
(28)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 4 63
Òàê êàê p — ïðîñòîå ÷èñëî è p � 3 , ýëåìåíò 8 2( )mod Op ÿâëÿåòñÿ îáðàòèìûì
ýëåìåíòîì êîëüöà �
pk
.
Èç (28) âûòåêàåò
a p y y c p b
d
� �
�
�( ( ) ) ( ( ( )) ),( ) ( )8 2 2 2 81
1
2
1
1mod O O O mod� � � �
y b p y y c p
1
1 1
1
2
1
14 8 2 2 2 8( ) ( ) ( )( ( ) ) ( ( (O O mod O O O mod� � � �
� � )) ).� b
�
�
�
�
Òåîðåìà äîêàçàíà.
Òåîðåìà 5. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p � 3 ïðè âñåõ çíà÷åíèÿõ ÷èñëà k �N,
åñëè èçâåñòíî, ÷òî a — îáðàòèìûé ýëåìåíò êîëüöà �
pk
, òî èäåíòèôèêàöèÿ ïàðà-
ìåòðîâ a è � àâòîìàòà M p kFR FR� � ( , ) ñâîäèòñÿ ê ðåøåíèþ ñèñòåìû äâóõ óðàâíå-
íèé, ïîëó÷åííîé â ðåçóëüòàòå ïðîñòîãî ýêñïåðèìåíòà äëèíû 1.
Äîêàçàòåëüñòâî. Ïóñòü a — îáðàòèìûé ýëåìåíò êîëüöà �
pk
. Ïîëîæèâ
q0 2 3 1� ( , , ) è x1 0� , èç (2) íàõîäèì
�
�
� � �
� � �
a p y
a p y
k
k
2 1
3 2
1
1
2
1
2
( ) ,
( ) .
( )
( )
� �
� �
�
�
�
�
(29)
Ïîñêîëüêó p — ïðîñòîå ÷èñëî è p � 3, ýëåìåíòû 2, 3, pk �1è pk � 2 ÿâëÿþòñÿ îá-
ðàòèìûìè ýëåìåíòàìè êîëüöà �
pk
. Òàê êàê a — îáðàòèìûé ýëåìåíò êîëüöà �
pk
è
ñèñòåìà óðàâíåíèé (29) ñîâìåñòíàÿ, y i
1
( ) ( , )i � 1 2 — îáðàòèìûå ýëåìåíòû êîëüöà �
pk
.
Ñëåäîâàòåëüíî, èç (29) âûòåêàåò
� � � �
�
� � �( ) ( ) ( ) ,
( )
( ) ( )
( )
y y p p
a y
k k
1
1 1
1
2 1 1
1
1 2
2 3 1 2� � � � �
� � � � �( ) ( ) ( ).( )y p pk k
1
2 1 1 24 3 1 2� � �� �
�
�
�
�
Òåîðåìà äîêàçàíà.
Îòìåòèì, ÷òî äëÿ àâòîìàòà M p kFR FR� � ( , ) èäåíòèôèêàöèÿ ïàðàìåòðîâ a è � ñó-
ùåñòâåííî óñëîæíÿåòñÿ, åñëè a — íåîáðàòèìûé ýëåìåíò êîëüöà �
pk
.  ýòîì ñëó÷àå âíà-
÷àëå íåîáõîäèìî íàéòè âñå ðåøåíèÿ a è � ñèñòåìû óðàâíåíèé (29), à çàòåì îáû÷íûìè ìå-
òîäàìè òåîðèè àâòîìàòîâ ñ ïîìîùüþ ïðîñòîãî (èëè êðàòíîãî) ýêñïåðèìåíòà [6] ðåøèòü
çàäà÷ó èäåíòèôèêàöèè àâòîìàòà â êëàññå âñåõ äîïóñòèìûõ àâòîìàòîâ M p kFR FR� � ( , ) .
Ðàññìîòðèì çàäà÷ó èäåíòèôèêàöèè íà÷àëüíîãî ñîñòîÿíèÿ àâòîìàòà
M p ku u� � ( , ) ( { , })u GH FR� â ïðåäïîëîæåíèè, ÷òî ýêñïåðèìåíòàòîðó èçâåñòíû
ïàðàìåòðû àâòîìàòà è îí ìîæåò óïðàâëÿòü âõîäîì àâòîìàòà. ßñíî, ÷òî ñëîæíîñòü
ðåøåíèÿ ýòîé çàäà÷è ñóùåñòâåííî çàâèñèò îò âîçìîæíîñòè ýêñïåðèìåíòàòîðà
óïðàâëÿòü ïàðàìåòðàìè àâòîìàòà.
Ðàññìîòðèì àâòîìàò M p kGH GH� � ( , ) .
Ïðåäïîëîæèì âíà÷àëå, ÷òî ýêñïåðèìåíòàòîð ìîæåò óïðàâëÿòü ïàðàìåòðàìè àâ-
òîìàòà M p kGH GH� � ( , ). Ïîëîæèâ ( , , , ) ( , , , )a b c d � 0 0 0 1 è x1 0� , èç (1) íàõîäèì,
÷òî q yi i
0 1
( ) ( )� ( , , )i � 1 2 3 .
Ïðåäïîëîæèì òåïåðü, ÷òî ýêñïåðèìåíòàòîð íå ìîæåò óïðàâëÿòü ïàðàìåòðàìè
àâòîìàòà M a b c d p kGH GH( , , , , , , ) ( , )� � �1 2 3 � � . Èç (1) âûòåêàåò, ÷òî äëÿ ëþáîãî
64 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 4
âõîäíîãî ñèìâîëà x
pk�Z ïîëó÷èì ñèñòåìó òðåõ íåëèíåéíûõ óðàâíåíèé
q d a q b q c q y
0
1
0
1 2
0
2 2
0
3 2
1
1( ) ( ) ( ) ( ) ( )( ( ) ( ) ( ) )� � � �� � � � O �1
0
2
0
1 2
0
2 2
0
3 2
1
�
� � � �
x
q d c q a q b q y
,
( ( ) ( ) ( ) )( ) ( ) ( ) ( ) (� � � � 2
2
0
3
0
1 2
0
2 2
0
3 2
)
( ) ( ) ( ) ( )
,
( ( ) ( ) ( ) )
O � �
� � � �
x
q d b q c q a q� � � �
�
�
�
�
�
� y x
1
3
3
( ) .O � �
(30)
Ìíîæåñòâî S ðåøåíèé ( , , )( ) ( ) ( )q q q
0
1
0
2
0
3 ñèñòåìû (30) óðàâíåíèé òðåòüåé ñòåïå-
íè íàä êîëüöîì �
pk
îïðåäåëÿåò ìíîæåñòâî âñåõ äîïóñòèìûõ êàíäèäàòîâ íà íà-
÷àëüíîå ñîñòîÿíèå èññëåäóåìîãî àâòîìàòà. Íåýêâèâàëåíòíûå ñîñòîÿíèÿ àâòîìàòà
M p kGH GH� � ( , ) , ïðèíàäëåæàùèå ìíîæåñòâó S (åñëè òàêèå èìåþòñÿ), íåîáõîäè-
ìî ðàçëè÷èòü îáû÷íûìè ìåòîäàìè òåîðèè àâòîìàòîâ, ò.å. ñ ïîìîùüþ äèàãíîñòè÷åñ-
êîãî ýêñïåðèìåíòà [6].
Ðàññìîòðèì àâòîìàò M p kFR FR� � ( , ). Ïðåäïîëîæèì âíà÷àëå, ÷òî ýêñïåðè-
ìåíòàòîð èìååò âîçìîæíîñòü óïðàâëÿòü ïàðàìåòðàìè ýòîãî àâòîìàòà.
Ïóñòü pk � 4. Ïîëîæèì a � 4 è � � 1. Èç (2) âûòåêàåò, ÷òî äëÿ ëþáîãî âõîäíîãî
ñèìâîëà x
pk�Z ïîëó÷èì ñëåäóþùóþ ñèñòåìó òðåõ óðàâíåíèé íàä êîëüöîì �
� � :
( ) ,
( )
( ) ( )
( ) ( )
2 1 1
2 1
0
1 2
1 1
1
0
2 2
2 1
2
� �
� �
q x y
q x y
O O
O O
� �
� �
�
� 1
2 1 1
0
3 2
3 1
3
,
( ) .( ) ( )
� �q x yO O� �
�
�
�
�
�
� �
(31)
Ìíîæåñòâî S ðåøåíèé ( , , )( ) ( ) ( )q q q
0
1
0
2
0
3 ñèñòåìû óðàâíåíèé (31) îïðåäåëÿåò
ìíîæåñòâî âñåõ äîïóñòèìûõ êàíäèäàòîâ íà íà÷àëüíîå ñîñòîÿíèå èññëåäóåìîãî àâ-
òîìàòà. Ïðè ýòîì | | ( )S o pk� , åñëè p � � èëè k � � .
Íåýêâèâàëåíòíûå ñîñòîÿíèÿ àâòîìàòà M FR , ïðèíàäëåæàùèå ìíîæåñòâó S
(åñëè òàêèå èìåþòñÿ), íåîáõîäèìî ðàçëè÷èòü îáû÷íûìè ìåòîäàìè òåîðèè àâòîìà-
òîâ, ò.å. ñ ïîìîùüþ äèàãíîñòè÷åñêîãî ýêñïåðèìåíòà.
Ïðåäïîëîæèì, ÷òî ýêñïåðèìåíòàòîð íå ìîæåò óïðàâëÿòü ïàðàìåòðàìè àâòîìà-
òà M p kFR FR� � ( , ). Èç (2) ñëåäóåò, ÷òî äëÿ ëþáîãî âõîäíîãî ñèìâîëà x
pk�Z
f q y x
f q y
q
q
( ) ,
( )
( ) ( )
( ) ( )
( )
( )
0
1
1
1
1 1
0
2
1
2
0
3
0
1
� �
�
� �
�
�
�
O
O�
� �
2 1
0
3
1
3
3 1
0
2
�
� �
x
f q y x
q
,
( ) .( ) ( )
( )
�
�
�
�
��
�
�
�
O
(32)
Ïîñêîëüêó ñèñòåìà óðàâíåíèé (32) ñîâìåñòíàÿ, èìååì
y x b
y x b
y x
h
h
1
1
1 1 1
1
2
2 1 2
1
3
3 1
3
1
( )
( )
( )
,
,
O
O
O
� �
� �
�
� �
� �
�
�
�
� b
h
3
2
� � ,
�
�
�
�
�
�
(33)
ãäå ( , )bi � � 1 ( , , )i � 1 2 3 . Èç (32) è (33) ïîëó÷àåì ñèñòåìó óðàâíåíèé
f q b
f q b
f q b
l
l
l
( ) ,
( ) ,
( ) .
( )
( )
( )
0
1
1
0
2
2
0
3
3
3
1
2
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
(34)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 4 65
Ïóñòü ÷èñëî � ïðèíàäëåæèò ïîêàçàòåëþ �. Ïîäñòàâèâ (33) è (34) â (32), ïîëó-
÷èì
q h l
q h l
q h l
0
1
1 1
0
2
2 2
0
3
3 3
( )
( )
( )
( ),
( ),
(
O mod
O mod
O mo
�
�
d �).
�
�
�
�
�
�
(35)
Òàêèì îáðàçîì, äëÿ èäåíòèôèêàöèè íà÷àëüíîãî ñîñòîÿíèÿ ëþáîãî àâòîìàòà
M p kFR FR� � ( , ) äîñòàòî÷íî íàéòè ìíîæåñòâî S âñåõ ðåøåíèé ( , , )( ) ( ) ( )q q q
0
1
0
2
0
3
ñèñòåì ñðàâíåíèé (35) ïðè âñåõ çíà÷åíèÿõ ÷èñåë l l l1 2 3 0 1 1, , { , , , }� �� � , âû÷èñëèòü
ïîäìíîæåñòâî
~
S , ñîñòîÿùåå èç âñåõ ýëåìåíòîâ ( , , )( ) ( ) ( )q q q S
0
1
0
2
0
3 � , óäîâëåòâîðÿþ-
ùèõ ñèñòåìå óðàâíåíèé (34), è ðàçëè÷èòü íåýêâèâàëåíòíûå ñîñòîÿíèÿ àâòîìàòà
M FR , ïðèíàäëåæàùèå ìíîæåñòâó
~
S (åñëè òàêèå èìåþòñÿ), îáû÷íûìè ìåòîäàìè òå-
îðèè àâòîìàòîâ, ò.å. ñ ïîìîùüþ äèàãíîñòè÷åñêîãî ýêñïåðèìåíòà.
3. ÍÅÏÎÄÂÈÆÍÛÅ ÒÎ×ÊÈ ÌÎÄÅËÅÉ
Îõàðàêòåðèçóåì ìíîæåñòâà íåïîäâèæíûõ òî÷åê îãðàíè÷åííî-äåòåðìèíèðîâàííûõ
(î.-ä.) ôóíêöèé [7], ðåàëèçóåìûõ èíèöèàëüíûìè àâòîìàòàìè ( , )MGH q0 è
( , )M FR q0 . Ïóñòü X M u( , )q ( { , })u GH FR� — ìíîæåñòâî âñåõ íåïîäâèæíûõ òî-
÷åê î.-ä. ôóíêöèè, ðåàëèçóåìîé èíèöèàëüíûì àâòîìàòîì ( , )M u q . Ïîëîæèì
X M X Mu u pk
( ) ( , ) ( , )1 q q Z� � .
Ðàññìîòðèì àâòîìàò M p kGH GH� � ( , ). Èç (2) âûòåêàåò, ÷òî
x X MGH1
1
0� ( ) ( , )q òîãäà è òîëüêî òîãäà, êîãäà x1 — ðåøåíèå ñèñòåìû óðàâíåíèé
( ) ( ( ) ( ) ( )( ) ( ) ( ) ( )1 1 1 0
1
0
1 2
0
2 2
0
3O� � � � � �x q d a q b q c q� � � � 2
2 1 0
2
0
1 2
0
2 2
0
1
),
( ) ( ( ) ( ) (( ) ( ) ( ) (O� � � � � �x q d c q a q b q� � � � 3 2
3 1 0
3
0
1 2
0
2 21
)
( ) ( ) ( )
) ),
( ) ( ( ) ( ) (O� � � � � �x q d b q c q a� � � � q
0
3 2( ) ) ).
�
�
�
�
�
�
(36)
Èç (36) âûòåêàþò ñëåäóþùèå óòâåðæäåíèÿ.
Óòâåðæäåíèå 7. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p ïðè âñåõ çíà÷åíèÿõ ÷èñëà k �N,
åñëè êàæäûé ýëåìåíò 1O� i ( , , )i � 1 2 3 ÿâëÿåòñÿ îáðàòèìûì ýëåìåíòîì êîëüöà �
pk ,
òî èìååò ìåñòî ñëåäóþùåå:
1) ðàâåíñòâî X MGH
( ) ( , )1
0q � � èñòèííî òîãäà è òîëüêî òîãäà, êîãäà âûïîëíå-
íî ïî êðàéíåé ìåðå îäíî èç óñëîâèé:
( ) ( ( ) ( ) ( )( ) ( ) ( ) ( )1 1
1
0
1
0
1 2
0
2 2
0
3 2O� � � � �� � � � �q d a q b q c q ) �
� � � ��( ) ( ( ) ( ) ( )( ) ( ) ( ) ( )1 2
1
0
2
0
1 2
0
2 2
0
3O� � � � � �q d c q a q b q 2 ) , (37)
( ) ( ( ) ( ) ( )( ) ( ) ( ) ( )1 1
1
0
1
0
1 2
0
2 2
0
3 2O� � � � �� � � � �q d a q b q c q ) �
� � � ��( ) ( ( ) ( ) ( )( ) ( ) ( ) ( )1 3
1
0
3
0
1 2
0
2 2
0
3O� � � � � �q d b q c q a q 2 ) (38)
èëè
( ) ( ( ) ( ) ( )( ) ( ) ( ) ( )1 2
1
0
2
0
1 2
0
2 2
0
3 2O� � � � �� � � � �q d c q a q b q ) �
� � � ��( ) ( ( ) ( ) ( )( ) ( ) ( ) ( )1 3
1
0
3
0
1 2
0
2 2
0
3O� � � � � �q d b q c q a q 2 ); (39)
66 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 4
2) ðàâåíñòâî | ( ( , , , , , , ), )|( )X M a b c dGH
1
1 2 3 0 1� � � q � èñòèííî òîãäà è òîëüêî
òîãäà, êîãäà íè îäíî èç óñëîâèé (37)–(39) íå âûïîëíåíî.
Óòâåðæäåíèå 8. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p ïðè âñåõ çíà÷åíèÿõ ÷èñëà k �N,
åñëè ïî êðàéíåé ìåðå îäèí èç ýëåìåíòîâ 1O� i ( , , )i � 1 2 3 — íåîáðàòèìûé ýëåìåíò
êîëüöà �
pk
, òî ðàâåíñòâî X MGH
( ) ( , )1
0q � � èñòèííî, åñëè âûïîëíåíî ïî êðàéíåé
ìåðå îäíî èç óñëîâèé:
1) q d a q b q c q
0
1
0
1 2
0
2 2
0
3 2( ) ( ) ( ) ( )( ( ) ( ) ( ) )� � � �� � � — îáðàòèìûé ýëåìåíò
êîëüöà �
pk
, à 1 1O � — íåîáðàòèìûé ýëåìåíò êîëüöà �
pk
;
2) q d c q a q b q
0
2
0
1 2
0
2 2
0
3 2( ) ( ) ( ) ( )( ( ) ( ) ( ) )� � � �� � � — îáðàòèìûé ýëåìåíò
êîëüöà �
pk
, à 1 2O� — íåîáðàòèìûé ýëåìåíò êîëüöà �
pk
;
3) q d b q c q a q
0
3
0
1 2
0
2 2
0
3 2( ) ( ) ( ) ( )( ( ) ( ) ( ) )� � � �� � � — îáðàòèìûé ýëåìåíò
êîëüöà �
pk , à 1 3O� — íåîáðàòèìûé ýëåìåíò êîëüöà �
pk
.
Ðàññìîòðèì àâòîìàò M p kFR FR� � ( , ) . Èç (2) âûòåêàåò, ÷òî
x X M FR1
1
0� ( ) ( , )q òîãäà è òîëüêî òîãäà, êîãäà x1 ÿâëÿåòñÿ ðåøåíèåì ñèñòåìû
óðàâíåíèé
( ) ( ) ,
( ) ( )
( )
( )
( )
(
1
1
1 1 0
1
2 1 0
2
0
3
0
1
O
O
� �
� �
� �
� �
x f q
x f q
q
q
�
�
)
( )
,
( ) ( ) .( )1 3 1 0
3 0
2
O� �� �x f q
q
�
�
�
�
��
�
�
�
(40)
Èç (40) âûòåêàþò ñëåäóþùèå óòâåðæäåíèÿ.
Óòâåðæäåíèå 9. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p ïðè âñåõ çíà÷åíèÿõ ÷èñëà k �N,
åñëè êàæäûé ýëåìåíò 1O� i ( , , )i � 1 2 3 ÿâëÿåòñÿ îáðàòèìûì ýëåìåíòîì êîëüöà �
pk
,
òî èìååò ìåñòî ñëåäóþùåå:
1) ðàâåíñòâî X M FR
( ) ( , )1
0q � � èñòèííî òîãäà è òîëüêî òîãäà, êîãäà âûïîëíå-
íî ïî êðàéíåé ìåðå îäíî èç óñëîâèé:
( ) ( ) ( ) ( )( ) ( )
( ) ( )
1 11
1
0
1
2
1
0
20
3
0
1
O O� � � �� ��� � � �f q f q
q q
,
(41)
( ) ( ) ( ) ( )( ) ( )
( ) ( )
1 11
1
0
1
3
1
0
30
3
0
2
O O� � � �� ��� � � �f q f q
q q (42)
èëè
( ) ( ) ( ) ( )( ) ( )
( ) ( )
1 12
1
0
2
3
1
0
30
1
0
2
O O� � � �� ��� � � �f q f q
q q
; (43)
2) ðàâåíñòâî | ( , )|( )X M FR
1
0 1q � èñòèííî òîãäà è òîëüêî òîãäà, êîãäà íè îäíî
èç óñëîâèé (41)–(43) íå âûïîëíåíî.
Óòâåðæäåíèå 10. Äëÿ ëþáîãî ïðîñòîãî ÷èñëà p ïðè âñåõ çíà÷åíèÿõ ÷èñëà
k �N, åñëè ñóùåñòâóåò òàêîå çíà÷åíèå i �{ , , }1 2 3 , ÷òî 1O� i è f q i( )( )
0
— ñîîòâå-
òñòâåííî íåîáðàòèìûé è îáðàòèìûé ýëåìåíòû êîëüöà �
pk
, òî X M FR
( ) ( , )1
0q � �.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 4 67
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ðàáîòå èññëåäîâàíû êëàññû �GH p k( , ) è �FR p k( , ) íåëèíåéíûõ àâòî-
ìàòîâ íàä êîëüöîì �
pk
, ÿâëÿþùèõñÿ àíàëîãàìè ìîäåëüíûõ ñèììåòðè÷åñêèõ õàîòè-
÷åñêèõ äèíàìè÷åñêèõ ñèñòåì Guckenheimer and Holmes cycle è free-running system
ñîîòâåòñòâåííî. Ïîêàçàíî, ÷òî àâòîìàòû, ïðèíàäëåæàùèå ýòèì êëàññàì, ìîãóò áûòü
èñïîëüçîâàíû â êà÷åñòâå êàíäèäàòà íà ïîòî÷íûé øèôð, ñïîñîáíûé êîíòðîëèðîâàòü
îøèáêè, âîçíèêøèå â ïðîöåññå ïåðåäà÷è èíôîðìàöèè ïî êàíàëó ñâÿçè è ñîñòîÿùèå
â èíâåðòèðîâàíèè çíà÷åíèé áèòîâ. Ñ ïîçèöèè òåîðèè àâòîìàòîâ îõàðàêòåðèçîâàíà
ñòðóêòóðà àâòîìàòîâ, ïðèíàäëåæàùèõ êëàññàì �GH p k( , ) è �FR p k( , ) .
Áîëåå òîíêèé àíàëèç êîìïîíåíòîâ ñâÿçàííîñòè ýòèõ àâòîìàòîâ è ìíîæåñòâ íå-
ïîäâèæíûõ òî÷åê î.-ä. ôóíêöèé, ðåàëèçóåìûõ èíèöèàëüíûìè àâòîìàòàìè, — îäíî
èç âîçìîæíûõ íàïðàâëåíèé äàëüíåéøèõ èññëåäîâàíèé. Âòîðîå íàïðàâëåíèå ïðåä-
ïîëàãàåò äåòàëüíûé àíàëèç ñëîæíîñòè ðåøåíèÿ çàäà÷ ïàðàìåòðè÷åñêîé èäåíòèôè-
êàöèè è èäåíòèôèêàöèè íà÷àëüíîãî ñîñòîÿíèÿ àâòîìàòîâ, ïðèíàäëåæàùèõ
óêàçàííûì êëàññàì. Îí äàåò âîçìîæíîñòü âûáðàòü íàèáîëåå ïîäõîäÿùèå çíà÷åíèÿ
ïàðàìåòðîâ ïðè èñïîëüçîâàíèè òàêîãî àâòîìàòà â êà÷åñòâå ïîòî÷íîãî øèôðà.
Òðåòüå íàïðàâëåíèå îñíîâàíî íà ðàçðàáîòêå ñðåäñòâ àâòîìàòèçàöèè ðåøåíèÿ çàäà÷
ïîñòðîåíèÿ êëàññîâ ýêâèâàëåíòíûõ ñîñòîÿíèé, ïàðàìåòðè÷åñêîé èäåíòèôèêàöèè è
èäåíòèôèêàöèè íà÷àëüíîãî ñîñòîÿíèÿ àâòîìàòîâ, ïðèíàäëåæàùèõ êëàññàì
�GH p k( , ) è �FR p k( , ) . ×åòâåðòîå íàïðàâëåíèå èññëåäîâàíèé ñâÿçàíî ñ êîìïüþ-
òåðíûì àíàëèçîì âû÷èñëèòåëüíîé ñòîéêîñòè øèôðîâ, ïîñòðîåííûõ íà îñíîâå àâòî-
ìàòîâ, ïðèíàäëåæàùèõ ýòèì êëàññàì.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ñ ê î á å ë å â  . à . Íåëèíåéíûå àâòîìàòû íàä êîíå÷íûì êîëüöîì // Êèáåðíåòèêà è ñèñòåìíûé
àíàëèç. — 2006. — ¹ 6. — Ñ. 29–42.
2. Ê ó ç í å ö î â Ñ . Ï . Äèíàìè÷åñêèé õàîñ. — Ì.: Ôèçìàòëèò, 2001. — 296 ñ.
3. A s h w i n P . , R u c k l i d g e A . M . , S t u r m a n R . Cyclic attractors of coupled cell systems and dy-
namics with symmetry // Synchronization: Theory and application. NATO Science Series. — 2003. —
109. — P. 5–23.
4. à î ë î ä Ï . È . , Ê ë è ì û ê À . Ó . Ìàòåìàòè÷åñêèå îñíîâû òåîðèè ñèììåòðèé. — Èæåâñê: ÍÈÖ
«Ðåãóëÿðíàÿ è õàîòè÷åñêàÿ äèíàìèêà», 2001. — 528 ñ.
5. Ñ ê î á å ë å â  .  . Ñèììåòðè÷åñêèå äèíàìè÷åñêèå ñèñòåìû íàä êîíå÷íûì êîëüöîì: ñâîéñòâà è
ñëîæíîñòü èäåíòèôèêàöèè // Òð. ÈÏÌÌ ÍÀÍÓ. — 2005. — 10. — Ñ. 184–189.
6. à è ë ë À . Ââåäåíèå â òåîðèþ êîíå÷íûõ àâòîìàòîâ. — Ì.: Íàóêà, 1966. — 272 ñ.
7. Ê ó ä ð ÿ â ö å â  . Á . , Ï î ä ê î ë ç è í À . Ñ . , Ó ø ÷ ó ì ë è ÷ Ø . Ââåäåíèå â òåîðèþ êîíå÷íûõ
àâòîìàòîâ. — Ì.: Íàóêà, 1985. — 320 ñ.
Ïîñòóïèëà 15.01.2009
68 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 4
|