Разделение полного множества значений булевых функций на основе заданного порога и порогового отношения
Розглянуто алгоритм поділу множини значень булевих функцій на основі заданих порогового значення та відношення, який реалізується на обчислювальній структурі ПЛІС, що автоматично налаштовується на дане порогове значення та відношення. Доведено коректність такої реалізації та розглянуто деякі її заст...
Gespeichert in:
| Datum: | 2012 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/84117 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Разделение полного множества значений булевых функций на основе заданного порога и порогового отношения / В.Н. Опанасенко, С.Л. Крывый // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 163-173. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84117 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-841172015-07-04T03:01:39Z Разделение полного множества значений булевых функций на основе заданного порога и порогового отношения Опанасенко, В.Н. Крывый, С.Л. Новые средства кибернетики, информатики, вычислительной техники и системного анализа Розглянуто алгоритм поділу множини значень булевих функцій на основі заданих порогового значення та відношення, який реалізується на обчислювальній структурі ПЛІС, що автоматично налаштовується на дане порогове значення та відношення. Доведено коректність такої реалізації та розглянуто деякі її застосування. An algorithm for the partition of the range of Boolean functions based on the specified threshold value and relation is considered. The algorithm is implemented by means of the PLD-based automatically adjustable structure. The correctness of such an implementation is proved and some of the applications are considered. 2012 Article Разделение полного множества значений булевых функций на основе заданного порога и порогового отношения / В.Н. Опанасенко, С.Л. Крывый // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 163-173. — Бібліогр.: 7 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/84117 51.681.3 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Новые средства кибернетики, информатики, вычислительной техники и системного анализа Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| spellingShingle |
Новые средства кибернетики, информатики, вычислительной техники и системного анализа Новые средства кибернетики, информатики, вычислительной техники и системного анализа Опанасенко, В.Н. Крывый, С.Л. Разделение полного множества значений булевых функций на основе заданного порога и порогового отношения Кибернетика и системный анализ |
| description |
Розглянуто алгоритм поділу множини значень булевих функцій на основі заданих порогового значення та відношення, який реалізується на обчислювальній структурі ПЛІС, що автоматично налаштовується на дане порогове значення та відношення. Доведено коректність такої реалізації та розглянуто деякі її застосування. |
| format |
Article |
| author |
Опанасенко, В.Н. Крывый, С.Л. |
| author_facet |
Опанасенко, В.Н. Крывый, С.Л. |
| author_sort |
Опанасенко, В.Н. |
| title |
Разделение полного множества значений булевых функций на основе заданного порога и порогового отношения |
| title_short |
Разделение полного множества значений булевых функций на основе заданного порога и порогового отношения |
| title_full |
Разделение полного множества значений булевых функций на основе заданного порога и порогового отношения |
| title_fullStr |
Разделение полного множества значений булевых функций на основе заданного порога и порогового отношения |
| title_full_unstemmed |
Разделение полного множества значений булевых функций на основе заданного порога и порогового отношения |
| title_sort |
разделение полного множества значений булевых функций на основе заданного порога и порогового отношения |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2012 |
| topic_facet |
Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84117 |
| citation_txt |
Разделение полного множества значений булевых функций на основе заданного порога и порогового отношения / В.Н. Опанасенко, С.Л. Крывый // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 163-173. — Бібліогр.: 7 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT opanasenkovn razdeleniepolnogomnožestvaznačenijbulevyhfunkcijnaosnovezadannogoporogaiporogovogootnošeniâ AT kryvyjsl razdeleniepolnogomnožestvaznačenijbulevyhfunkcijnaosnovezadannogoporogaiporogovogootnošeniâ |
| first_indexed |
2025-07-06T11:04:15Z |
| last_indexed |
2025-07-06T11:04:15Z |
| _version_ |
1836895285497823232 |
| fulltext |
Â.Í. ÎÏÀÍÀÑÅÍÊÎ, Ñ.Ë. ÊÐÛÂÛÉ
ÓÄÊ 51.681.3 ÐÀÇÄÅËÅÍÈÅ ÏÎËÍÎÃÎ ÌÍÎÆÅÑÒÂÀ
ÇÍÀ×ÅÍÈÉ ÁÓËÅÂÛÕ ÔÓÍÊÖÈÉ ÍÀ ÎÑÍÎÂÅ
ÇÀÄÀÍÍÎÃÎ ÏÎÐÎÃÀ È ÏÎÐÎÃÎÂÎÃÎ
ÎÒÍÎØÅÍÈß
Êëþ÷åâûå ñëîâà: àäàïòàöèÿ, áóëåâà ôóíêöèÿ, ïîðîãîâîå îòíîøåíèå, çàäà÷à
ðàçäåëåíèÿ.
ÂÂÅÄÅÍÈÅ
Àäàïòàöèÿ àïïàðàòíûõ ñðåäñòâ íà ðåøåíèå çàäàííîãî àëãîðèòìà áûëà ïðåäëî-
æåíà â ðàáîòå [1]. Òàêîé ïîäõîä ïîëó÷èë íàçâàíèå «òåõíîëîãèÿ ðåêîíôèãóðè-
ðóåìîãî êîìïüþòèíãà» [2], âîïëîùåíèå êîòîðîé â ðåàëüíûå ïðîåêòû ñòàëî
âîçìîæíûì òîëüêî ñ ïîÿâëåíèåì ñîâðåìåííûõ ïðîãðàììèðóåìûõ ëîãè÷åñêèõ
èíòåãðàëüíûõ ñõåì (ÏËÈÑ). Â ðàáîòå [3] ðàññìîòðåíû îñíîâû òåîðèè àäàï-
òèâíûõ ëîãè÷åñêèõ ñåòåé (ÀËÑ) íà îñíîâå ÏËÈÑ, îäíàêî íå ïðèâåäåíî ôîð-
ìàëèçîâàííîå îáîñíîâàíèå àëãîðèòìîâ àäàïòàöèè ñòðóêòóðû ÀËÑ íà ðåàëèçà-
öèþ àëãîðèòìîâ êëàññèôèêàöèè [4], ò.å. ðàçäåëåíèå ìíîæåñòâà âõîäíûõ âåêòî-
ðîâ áóëåâûõ ïåðåìåííûõ íà îñíîâå çàäàííûõ ïîðîãîâîãî çíà÷åíèÿ è
ïîðîãîâîãî îòíîøåíèÿ [5]. Íàñòîÿùàÿ ñòàòüÿ ïîñâÿùåíà äîêàçàòåëüñòâó êîð-
ðåêòíîñòè ðåàëèçàöèè òàêèõ àëãîðèòìîâ íà ñòðóêòóðàõ òèïà ÀËÑ, à òàêæå
ïðèìåíåíèþ ýòèõ àëãîðèòìîâ ê íåéðîííûì ñåòÿì.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Ïóñòü X x x xn� � �{ , }1 2 � — àëôàâèò áóëåâûõ ïåðåìåííûõ, ò.å. ïåðåìåííûõ,
ïðèíèìàþùèõ ñâîè çíà÷åíèÿ â ìíîæåñòâå X � { , }0 1 . Ïóñòü òàêæå
x y y yn� � �{ , }1 2 � — áóëåâ âåêòîð, ìíîæåñòâî âñåâîçìîæíûõ çíà÷åíèé êîòî-
ðîãî áóäåì îáîçíà÷àòü A è íàçûâàòü ïîëíûì ìíîæåñòâîì çíà÷åíèé, ãäå
y Xi � , i n�1 2, , ..., . Åñëè A a a a n� � �{ , }1 2 2
� — ïîëíîå ìíîæåñòâî çíà÷åíèé
áóëåâîãî âåêòîðà x y y yn� � �{ , }1 2 � , êîòîðûå áóäåì èçîáðàæàòü ñòðîêàìè, ñî-
ñòîÿùèõ èç íóëåé è åäèíèö, òî çàôèêñèðóåì íåêîòîðîå çíà÷åíèå a A� âåêòîðà
x è áèíàðíîå îòíîøåíèå R íà ìíîæåñòâå A . Çíà÷åíèå a íàçîâåì ïîðîãîâûì
çíà÷åíèåì, à îòíîøåíèå R — ïîðîãîâûì îòíîøåíèåì.
Çàäà÷à ðàçäåëåíèÿ ìíîæåñòâà A íà äâà ïîäìíîæåñòâà: îòíîñèòåëüíî ïîðîãî-
âîãî çíà÷åíèÿ a è ïîðîãîâîãî îòíîøåíèÿ R ñîñòîèò â òîì, ÷òîáû ðàçäåëèòü ìíî-
æåñòâî A íà ïîäìíîæåñòâà A1 è A2 òàêèõ, ÷òî
A x A a x R1 � � �{ : ( , ) } , A x A a x R2 � � �{ :( , ) } .
Òàê, åñëè R �� , òî A x A x a1 � � �{ : } , A x A a x2 � � �{ : } .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 163
© Â.Í. Îïàíàñåíêî, Ñ.Ë. Êðûâûé, 2012
Ñôîðìóëèðîâàííàÿ çàäà÷à îáîáùàåòñÿ íà ñëó÷àé, êîãäà íà ìíîæåñòâå A çà-
äàíî íåñêîëüêî áèíàðíûõ îòíîøåíèé: { , , ..., }R R Rs1 2 .
 íàñòîÿùåé ñòàòüå ðàññìàòðèâàþòñÿ ÷åòûðå áèíàðíûõ îòíîøåíèÿ, çàäàííûå
íà ìíîæåñòâå A R: ( )1 � , R2 ( )� , R3 ( )� , R4 ( ) . Íà ïðàêòèêå íåò íåîáõîäèìîñòè
ÿâíî ñòðîèòü ðàçáèåíèå ìíîæåñòâà A , à ñëåäóåò âû÷èñëÿòü çíà÷åíèå ôóíêöèè
�R a x
a x R
a x R
( , )
, ( , ) ;
, ( , ) .
�
�
�
�
�
1
0
åñëè
åñëè
Èç îïðåäåëåíèÿ ýòîé ôóíêöèè âûòåêàåò, ÷òî îíà ïðèíèìàåò çíà÷åíèå 1 íà
ìíîæåñòâå A1 , à íà ìíîæåñòâå A2 — çíà÷åíèå 0.
ÍÅÏÎÑÐÅÄÑÒÂÅÍÍÛÉ ÀËÃÎÐÈÒÌ ÐÅØÅÍÈß ÇÀÄÀ×È
Ïîñêîëüêó ìíîæåñòâî çíà÷åíèé ñîñòîèò èç áóëåâûõ ñëîâ, ò.å. ñëîâ â àëôàâèòå
�X { , }0 1 , òî íà ýòè ñëîâà åñòåñòâåííûì îáðàçîì ââîäÿòñÿ áóëåâû îïåðàöèè,
âûïîëíÿåìûå ïîðàçðÿäíî: � (êîíúþíêöèÿ), &(äèçúþíêöèÿ), � (îòðèöàíèå),
� (ñëîæåíèå ïî ìîäóëþ 2). Ñ ïîìîùüþ ýòèõ îïåðàöèé ñòðîÿòñÿ ôóíêöèè, íà-
çûâàåìûå ëîãè÷åñêèìè:
a b� , a b� , a b� , a b� , a b& , a b& , a b& , a b& ,
a b� , a b� , a , b .
Ñ ìàòåìàòè÷åñêîé òî÷êè çðåíèÿ çàäà÷à âû÷èñëåíèÿ çíà÷åíèÿ ôóíêöèè
�R a x( , ) èìååò î÷åâèäíîå ðåøåíèå áëàãîäàðÿ òîìó, ÷òî ïîðîãîâîå îòíîøåíèå R
ìîæíî ïåðåíåñòè íà ðàçðÿäû. Òîãäà, ñðàâíèâàÿ ïîðîãîâîå çíà÷åíèå a ñî çíà÷åíè-
ÿìè òåêóùåãî âåêòîðà x , íà÷èíàÿ ñî ñòàðøèõ ðàçðÿäîâ, ïîëó÷àåì ( , )x a R� , ãäå
k-å ðàçðÿäû ñëîâ ðàçíûå, à âñå ïðåäûäóùèå ðàçðÿäû îäèíàêîâûå, è ( , )x a Rk k � ,
ãäå xk è ak îáîçíà÷àþò k-å ðàçðÿäû (k-å ñèìâîëû) ñëîâ x è a ñîîòâåòñòâåííî.
Åñëè âñå ðàçðÿäû â ñëîâàõ a è x îäèíàêîâûå, òî ( , )x a R� � R ÿâëÿåòñÿ îäíèì èç
ïîðîãîâûõ îòíîøåíèé { , }� .
Èç ýòîãî îïèñàíèÿ âûòåêàåò î÷åâèäíûé àëãîðèòì ðåøåíèÿ çàäà÷è ðàçäåëå-
íèÿ. Ïóñòü a a a a an n� �{ ... }1 2 1 — çíà÷åíèå ïîðîãîâîãî âåêòîðà, x �
� �{ ... }x x x xn n 1 2 1 — òåêóùèé âåêòîð, çíà÷åíèÿ êîîðäèíàò êîòîðîãî ïîäàþòñÿ íà
âõîä àëãîðèòìà, ãäå ak — k-é ðàçðÿä ïîðîãîâîãî âåêòîðà a .  ýòèõ îáîçíà÷åíèÿõ
àëãîðèòì ïðèíèìàåò ñëåäóþùèé âèä.
ÐÀÇÄÅËÅÍÈÅ ( , , )a R x
Âõîä: a — ïîðîãîâîå çíà÷åíèå, R — ïîðîãîâîå îòíîøåíèå, x — òåêóùåå
çíà÷åíèå âõîäíîãî âåêòîðà.
Âûõîä: çíà÷åíèå ëîãè÷åñêîé ôóíêöèè
�R a x
a x R
a x R
( , )
, ( , ) ;
, ( , ) .
�
�
�
�
�
1
0
åñëè
åñëè
Ìåòîä:
begin
i n� ;
while (x a ii i� � � 0) do
i i� �1
od
if i � 0 then
if R � � { , } then return (1)
else return (0)
else
if ( , )x a Ri i � then return (1)
else return (0)
end
164 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
Ïðàâèëüíîñòü äàííîãî àëãîðèòìà î÷åâèäíà è íå òðåáóåò îáîñíîâàíèÿ. Ýòîò
àëãîðèòì íàçûâàåòñÿ íåïîñðåäñòâåííûì.
Ïðèìåð 1. Ïóñòü a �11001, x �11010, y � 01110, z �11001, R1 �� . Òîãäà äëÿ
R1 è x y z, , ïîëó÷àåì ñëåäóþùèå çíà÷åíèÿ, ãåíåðèðóåìûå àëãîðèòìîì:
— äëÿ x ïåðâûå òðè ðàçðÿäà îäèíàêîâû, à îñòàëüíûå ðàçðÿäû ðàçëè÷íûå, ò.å.
a x a x2 2 2 2� �, è ïîýòîìó a x� è ( , )a x R� 1 ; ñëåäîâàòåëüíî, îêîí÷àòåëüíîå çíà-
÷åíèå ôóíêöèè �R a x( , ) ðàâíî 0;
— äëÿ y èìååì a y a y5 5 5 5� �, , ïîýòîìó y a� è îêîí÷àòåëüíîå çíà÷åíèå
ôóíêöèè �R a x( , ) ðàâíî 1;
— äëÿ z âñå ðàçðÿäû ðàâíû ñîîòâåòñòâóþùèì ðàçðÿäàì a è ïîñêîëüêó
R1 � � { , } , òî îêîí÷àòåëüíîå çíà÷åíèå ôóíêöèè �R a x( , ) ðàâíî 0.
ÐÅØÅÍÈÅ ÇÀÄÀ×È ÐÀÇÄÅËÅÍÈß ÍÀ ÂÛ×ÈÑËÈÒÅËÜÍÎÉ ÑÒÐÓÊÒÓÐÅ
Ñèòóàöèÿ ñ îáîñíîâàíèåì àëãîðèòìà èçìåíÿåòñÿ, åñëè íà ôèêñèðîâàííîé
ñòðóêòóðå ÀËÑ, ñîñòîÿùåé èç óíèâåðñàëüíûõ ëîãè÷åñêèõ ýëåìåíòîâ (ðåàëèçó-
þùèõ ïðîèçâîëüíóþ ëîãè÷åñêóþ ôóíêöèþ), íåîáõîäèìî ðåàëèçîâàòü ôóíêöèþ
�R a x( , ) , âû÷èñëåííóþ àëãîðèòìîì ÐÀÇÄÅËÅÍÈÅ.
Îñîáåííîñòü ñòðóêòóðû ýëå-
ìåíòîâ ÀËÑ (ðèñ. 1) ñîñòîèò â òîì,
÷òî îíè ñïîñîáíû íàñòðàèâàòüñÿ íà
ðåàëèçàöèþ ëþáîé ëîãè÷åñêîé
ôóíêöèè: � , & , � , � . Îòìåòèì,
÷òî íà âõîä ñòðóêòóðû ïîäàþòñÿ
ðàçðÿäû òåêóùåãî ñëîâà x , ïðè÷åì
ñòàðøèé ðàçðÿä ïîäàåòñÿ íà êàæ-
äûé óçåë íèæíåãî óðîâíÿ.
Ðàññìîòðèì ðåøåíèå çàäà÷è
ðàçäåëåíèÿ íà âû÷èñëèòåëüíîé
ñòðóêòóðå, ïîêàçàííîé íà ðèñ. 1.
Ôîðìèðîâàíèå ñðåäû âû÷èñëåíèÿ
íà ýòîé ñòðóêòóðå ïðîèñõîäèò ïó-
òåì íàñòðàèâàíèÿ êàæäîãî åe
óðîâíÿ íà çàäàííóþ ëîãè÷åñêóþ
ôóíêöèþ â çàâèñèìîñòè îò çíà÷å-
íèÿ ïîðîãà a è ïîðîãîâîãî îòíî-
øåíèÿ R . Òèï ëîãè÷åñêîé ôóíêöèè äëÿ i-ãî óðîâíÿ (i n� �[( ), ]1 2 ) îïðåäåëÿåòñÿ
ñîãëàñíî ïðàâèëó
F a bi
R � � , åñëè ai � 0 ; F a bi
R : &� , åñëè ai �1 .
Îò ïîðîãîâîãî îòíîøåíèÿ çàâèñÿò çíà÷åíèÿ ïîðîãà, äëÿ êîòîðûõ âû÷èñëå-
íèå çíà÷åíèÿ îòëè÷àåòñÿ îò ïðèíÿòîãî ïðàâèëà. Òàêèå çíà÷åíèÿ ïîðîãà áóäåì íà-
çûâàòü îñîáûìè òî÷êàìè ïîðîãîâîãî îòíîøåíèÿ.
Ïðåæäå ÷åì ðàññìîòðåòü âû÷èñëåíèÿ çíà÷åíèé ïîðîãîâûõ îòíîøåíèé â îñî-
áûõ òî÷êàõ, ðàññìîòðèì ïðèìåð, êîòîðûé èëëþñòðèðóåòñÿ âû÷èñëèòåëüíîé
ñòðóêòóðîé èç ðèñ. 1. Ïóñòü n � 5 , R �� , a �10101 , x �10111 , y � 01010 . Òîãäà
íà êàæäîì óðîâíå ñòðóêòóðû äëÿ a è x èìååì òàêèå çíà÷åíèÿ: 0111 � 111 �
�11, ÷òî îïðåäåëÿåò çíà÷åíèå 0 äëÿ ïîðîãîâîãî îòíîøåíèÿ, à äëÿ a è y — çíà÷å-
íèÿ 0000 � 000 � 00, ÷òî îïðåäåëÿåò çíà÷åíèå 1 äëÿ ïîðîãîâîãî îòíîøåíèÿ.
Ýòî çíà÷èò, ÷òî �R a x( , ) � 0 è �R a y( , ) �1 , ïîñêîëüêó a x� è y a� .
Èç ýòîãî ïðèìåðà ñëåäóåò, ÷òî îêîí÷àòåëüíîå çíà÷åíèå ïîðîãîâîãî îòíîøå-
íèÿ �R a x( , ) äëÿ çàäàííîãî ïîðîãà è çàäàííîãî îòíîøåíèÿ îïðåäåëÿåòñÿ, èñõîäÿ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 165
Ðèñ. 1. Ñòðóêòóðà âû÷èñëèòåëüíîé ñðåäû (n � 5)
Çíà÷åíèå �R
f3
f2
f1
x5 x4 x3 x2 x1
èç çíà÷åíèé äâóõ ïîñëåäíèõ áèòîâ, ïîëó÷àåìûõ íà óðîâíå i �1 . Ïóñòü a2 , a1 —
äâà ïîñëåäíèõ áèòà, ïîëó÷àåìûõ â ðåçóëüòàòå âû÷èñëåíèÿ. Òîãäà çíà÷åíèå ïîðî-
ãîâîãî îòíîøåíèÿ íà ýòîì óðîâíå âû÷èñëèòåëüíîé ñòðóêòóðû îïðåäåëÿþòñÿ
ñëåäóþùèìè ôóíêöèÿìè:
a a2 10 0� �, , òîãäà F a b
R
1
2 � � , F a b
R
1
3 � & ;
a a2 10 1� �, , òîãäà F a b
R
1
1 � & , F a
R
1
2 � , F a
R
1
3 � , F a b
R
1
4 � � ;
a a2 11 0� �, , òîãäà F a
R
1
1 � , F a b
R
1
2 � & , F a b
R
1
3 � � , F a
R
1
4 � ;
a a2 11 1� �, , òîãäà F a b
R
1
1 � � , F a b
R
1
4 � & .
Åñëè ýòè ôóíêöèè èñïîëüçîâàòü â ðàññìîòðåííîì âûøå ïðèìåðå, òî ïîëó÷èì
òðåáóåìûå çíà÷åíèÿ.
Äàëåå ðàññìîòðèì ïîðîãîâûå îòíîøåíèÿ è èõ îñîáûå òî÷êè. Íàñòðîéêà íà
ôóíêöèþ âû÷èñëåíèÿ çíà÷åíèÿ îòíîøåíèÿ âûïîëíÿåòñÿ ïóòåì àíàëèçà ïåðâîãî
áèòà ïîðîãîâîãî çíà÷åíèÿ, à òàêæå ïîðîãîâîãî îòíîøåíèÿ ñëåäóþùèõ òèïîâ.
— Ïîðîãîâîå îòíîøåíèå R1 �� . Îñîáîé òî÷êîé ýòîãî îòíîøåíèÿ ÿâëÿåòñÿ
çíà÷åíèå ïîðîãà a �100 0... . Òîãäà âû÷èñëåíèå çíà÷åíèÿ R1 âûïîëíÿåòñÿ ñ ïî-
ìîùüþ ôóíêöèé
F ai
R1 � , F a b
i
R
� �
1
1 & .
Äëÿ óðîâíÿ i �1 çíà÷åíèå îòíîøåíèÿ ðàâíî íóëþ, åñëè íà íèæíåì óðîâíå ïî-
ëó÷åí 0, è ðàâíî çíà÷åíèþ 1, åñëè íà íèæíåì óðîâíå èìååì 1. Íàïðèìåð,
ïóñòü a �10000, x �11001, y � 01101. Òîãäà íà óðîâíÿõ äëÿ a è x ïîëó÷àåì çíà-
÷åíèÿ
0000 � 000 � 00 � 0, òàê êàê a x� ,
à äëÿ a è y — çíà÷åíèÿ
1111 � 111 � 11 � 1, òàê êàê y a� .
— Ïîðîãîâîå îòíîøåíèå R2 ��. Îñîáîé òî÷êîé ýòîãî îòíîøåíèÿ ÿâëÿåòñÿ
çíà÷åíèå ïîðîãà a � 011 1... . Òîãäà âû÷èñëåíèå çíà÷åíèÿ R2 âûïîëíÿåòñÿ ñ ïî-
ìîùüþ ôóíêöèé
F ai
R2 � , F a b
i
R
� �
1
2 & .
Äëÿ óðîâíÿ i �1 çíà÷åíèå îòíîøåíèÿ ðàâíî íóëþ, åñëè íà íèæíåì óðîâíå
ïîëó÷åí 0, è ðàâíî çíà÷åíèþ 1, åñëè íà íèæíåì óðîâíå èìååì 1. Íàïðèìåð, ïóñòü
a � 01111, x �11001, y � 01101. Òîãäà íà óðîâíÿõ äëÿ a è x ïîëó÷àåì çíà÷åíèÿ
1111 � 111 � 11 � 1, òàê êàê a x� ,
à äëÿ a è y — çíà÷åíèÿ
0000 � 000 � 00 � 0, òàê êàê y a� .
— Ïîðîãîâîå îòíîøåíèå R3 � � . Îñîáîé òî÷êîé ýòîãî îòíîøåíèÿ ÿâëÿåòñÿ
çíà÷åíèå ïîðîãà a � 011 1... . Òîãäà âû÷èñëåíèå çíà÷åíèÿ R3 âûïîëíÿåòñÿ ñ ïî-
ìîùüþ ôóíêöèé
F ai
R3 � , F a b
i
R
� �
1
3 & .
Äëÿ óðîâíÿ i �1 çíà÷åíèå îòíîøåíèÿ ðàâíî íóëþ, åñëè íà íèæíåì óðîâíå ïîëó-
÷åí 0, è ðàâíî çíà÷åíèþ 1, åñëè íà íèæíåì óðîâíå èìååì 1. Íàïðèìåð, ïóñòü
a � 01111, x �11001, y � 01101. Òîãäà íà óðîâíÿõ äëÿ a è x ïîëó÷àåì çíà÷åíèÿ
0000 � 000 � 00 � 0, òàê êàê a x� ,
à äëÿ a è y — çíà÷åíèÿ 1111 � 111 � 11 � 1, òàê êàê y a� .
166 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
— Ïîðîãîâîå îòíîøåíèå R4 � . Îñîáîé òî÷êîé ýòîãî îòíîøåíèÿ ÿâëÿåòñÿ
çíà÷åíèå ïîðîãà a �100 0... . Òîãäà âû÷èñëåíèå çíà÷åíèÿ R4 âûïîëíÿåòñÿ ñ ïî-
ìîùüþ ôóíêöèé
F ai
R4 � , F a b
i
R
� �
1
4 & .
Äëÿ óðîâíÿ i �1 çíà÷åíèå îòíîøåíèÿ ðàâíî íóëþ, åñëè íà íèæíåì óðîâíå ïî-
ëó÷åí 0, è ðàâíî çíà÷åíèþ 1, åñëè íà íèæíåì óðîâíå èìååì 1. Íàïðèìåð, ïóñòü
a � 01111, x �11001, y � 01101. Òîãäà íà óðîâíÿõ äëÿ a è x ïîëó÷àåì çíà÷åíèÿ
1111 � 111 � 11 � 1, òàê êàê a x�
à äëÿ a è y — çíà÷åíèÿ
0000 � 000 � 00 � 0, òàê êàê y a� .
ÎÁÎÑÍÎÂÀÍÈÅ ÀËÃÎÐÈÒÌÀ
Ðàññìîòðèì âîïðîñ î êîððåêòíîñòè ïðåäñòàâëåííîãî àëãîðèòìà íà îñíîâå âû-
÷èñëèòåëüíîé ñðåäû (ñì. ðèñ. 1). Íàçîâåì ýòîò àëãîðèòì ÐÀÇÄ–ÀËÑ è áóäåì
ñ÷èòàòü åãî êîððåêòíûì, åñëè çíà÷åíèå, íàéäåííîå ñ ïîìîùüþ ýòîãî àëãîðèò-
ìîì äëÿ ëþáûõ a R x, , , ñîâïàäàåò ñî çíà÷åíèåì ôóíêöèè �R a x( , ) , âû÷èñëåí-
íûì àëãîðèòìîì ÐÀÇÄÅËÅÍÈÅ.
Òåîðåìà 1. Àëãîðèòì ÐÀÇÄ–ÀËÑ êîððåêòåí.
Äîêàçàòåëüñòâî òåîðåìû îïèðàåòñÿ íà ðÿä îäíîòèïíûõ ëåìì äëÿ êàæäîãî
ïîðîãîâîãî îòíîøåíèÿ. Äîêàæåì ýòî äëÿ ïåðâûõ äâóõ îòíîøåíèé, à äëÿ ïîðîãî-
âûõ îòíîøåíèé R3 � � , R4 � ê äîêàçàòåëüñòâó êîððåêòíîñòè àëãîðèòìà
ÐÀÇÄ–ÀËÑ ìîæíî ïðèéòè ñàìîñòîÿòåëüíî.
Ëåììà 1. Àëãîðèòì ÐÀÇÄ–ÀËÑ ïðàâèëüíî âû÷èñëÿåò çíà÷åíèå �R a x
1
( , )
äëÿ ïîðîãîâîãî îòíîøåíèÿ R1 � � .
Äîêàçàòåëüñòâî. Ïóñòü a a a a an n� �1 2 1... — ïîðîãîâîå çíà÷åíèå è
x x x x xn n� �1 2 1... — âõîäíîé âåêòîð. Ïóñòü a xj j� äëÿ âñåõ j n i� �, ..., ( )1 è
a xi i� , ïðè÷åì a a a a aj j� �1 2 1... íå ñîäåðæèò îñîáûõ òî÷åê îòíîøåíèÿ R1 äëÿ
j n i� �, ..., ( )1 . Ðàññìîòðèì âîçìîæíûå ñëó÷àè.
1. Ïóñòü ai �1 , xi � 0 . Òîãäà íà âñåõ ïîñëåäóþùèõ óðîâíÿõ ñîãëàñíî àëãî-
ðèòìó ÐÀÇÄ–ÀËÑ äî âîçíèêíîâåíèÿ îñîáîé òî÷êè ïîëó÷àåì âåêòîðû, ñîñòîÿùèå
èç íóëåâûõ ñòðîê.
Åñëè â êîíöå ïîñëåäîâàòåëüíîñòè ïîëó÷àåì a a2 1 00� , òî ýòî çíà÷èò, ÷òî íà
k-ì óðîâíå (i k� � 3) èìååòñÿ îñîáàÿ òî÷êà îòíîøåíèÿ R1 . Òîãäà íà ýòîì óðîâíå
âû÷èñëèòåëüíàÿ ñòðóêòóðà íàñòðàèâàåòñÿ íà ôóíêöèè F ai
R1 � , F a b
i
R
� �
1
1 & è, íà÷è-
íàÿ ñ ýòîãî óðîâíÿ, âñå âõîäíûå çíà÷åíèÿ ñòàíîâÿòñÿ ðàâíûìè åäèíèöå. Ïîýòîìó íà
âûõîäå âû÷èñëèòåëüíîé ñòðóêòóðû ïîëó÷àåì F a b
R
1
1 1� �& . Ýòî çíà÷åíèå ñîâïà-
äàåò ñî çíà÷åíèåì ôóíêöèè �R a x
1
1( , ) � , êîòîðîå âû÷èñëÿåò àëãîðèòì
ÐÀÇÄÅËÅÍÈÅ.
Åñëè â êîíöå ïîñëåäîâàòåëüíîñòè ïîëó÷àåì a a2 1 01� , òî F a b
R
1
1 � & è ïðè
çíà÷åíèÿõ x x2 1 00� íà âûõîäå âû÷èñëèòåëüíîé ñòðóêòóðû ïîëó÷àåì
F a b
R
1
1 1� �& , à íà îñòàëüíûõ âåêòîðàõ x x2 1 âûõîäíûå çíà÷åíèÿ ðàâíû íóëþ.
Ýòî çíà÷åíèå ñîâïàäàåò ñî çíà÷åíèåì ôóíêöèè �R a x
1
( , ) , êîòîðîå âû÷èñëÿåò àë-
ãîðèòì ÐÀÇÄÅËÅÍÈÅ.
Åñëè â êîíöå ïîñëåäîâàòåëüíîñòè ïîëó÷àåì a a2 1 10� , òî F ai
R1 � è ïðè çíà-
÷åíèÿõ x x2 1 00� è x x2 1 01� íà âûõîäå âû÷èñëèòåëüíîé ñòðóêòóðû ïîëó÷àåì
F ai
R1 1� � , à íà îñòàëüíûõ âåêòîðàõ x x2 1 âûõîäíûå çíà÷åíèÿ ðàâíû íóëþ. Ýòè
çíà÷åíèÿ ñîâïàäàþò ñî çíà÷åíèÿìè ôóíêöèè �R a x
1
( , ) , êîòîðûå âû÷èñëÿþòñÿ
àëãîðèòìîì ÐÀÇÄÅËÅÍÈÅ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 167
Åñëè â êîíöå ïîñëåäîâàòåëüíîñòè ïîëó÷àåì a a2 1 11� , òî F a b
R
1
1 � � è ïðè
âñåõ çíà÷åíèÿõ x x2 1 , êðîìå çíà÷åíèÿ x x2 1 11� , íà âûõîäå âû÷èñëèòåëüíîé
ñòðóêòóðû ïîëó÷àåì F a b
R
1
1 1� � � . Ýòè çíà÷åíèÿ ñîâïàäàþò ñî çíà÷åíèÿìè
ôóíêöèè �R a x
1
( , ) , êîòîðûå âû÷èñëÿþòñÿ àëãîðèòìîì ÐÀÇÄÅËÅÍÈÅ.
2. Ïóñòü ai � 0 , xi �1 . Òîãäà íà âñåõ ïîñëåäóþùèõ óðîâíÿõ ñîãëàñíî àëãî-
ðèòìó ÐÀÇÄ–ÀËÑ äî âîçíèêíîâåíèÿ îñîáîé òî÷êè (åñëè òàêîâàÿ èìååòñÿ) ïîëó-
÷àåì âåêòîðû, ñîñòîÿùèå èç åäèíèö.
Åñëè â êîíöå ïîñëåäîâàòåëüíîñòè ïîëó÷àåì a a2 1 00� , òî ýòî çíà÷èò, ÷òî íà
k-ì óðîâíå (i k� � 3), âñòðåòèëàñü îñîáàÿ òî÷êà îòíîøåíèÿ R1 . Òîãäà íà ýòîì
óðîâíå âû÷èñëèòåëüíàÿ ñòðóêòóðà íàñòðàèâàåòñÿ íà ôóíêöèè F ai
R1 � ,
F a b
i
R
� �
1
1 & è, íà÷èíàÿ ñ ýòîãî óðîâíÿ, âñå âõîäíûå çíà÷åíèÿ ñòàíîâÿòñÿ íóëåâû-
ìè ñòðîêàìè. Ïîýòîìó íà âûõîäå âû÷èñëèòåëüíîé ñòðóêòóðû ïîëó÷àåì
F a b
R
1
1 0� �& . Ýòî çíà÷åíèå ñîâïàäàåò ñî çíà÷åíèåì ôóíêöèè �R a x
1
0( , ) � , êî-
òîðîå âû÷èñëÿåò àëãîðèòì ÐÀÇÄÅËÅÍÈÅ.
Åñëè â êîíöå ïîñëåäîâàòåëüíîñòè ïîëó÷àåì a a2 1 01� , òî F a b
R
1
1 � & è ïðè
çíà÷åíèÿõ x x2 1 00� íà âûõîäå âû÷èñëèòåëüíîé ñòðóêòóðû ïîëó÷àåì
F a b
R
1
1 1� �& , à íà îñòàëüíûõ âåêòîðàõ x x2 1 âûõîäíûå çíà÷åíèÿ ðàâíû íóëþ.
Ýòî çíà÷åíèå ñîâïàäàåò ñî çíà÷åíèåì ôóíêöèè �R a x
1
( , ) , êîòîðîå âû÷èñëÿåò àë-
ãîðèòì ÐÀÇÄÅËÅÍÈÅ.
Åñëè â êîíöå ïîñëåäîâàòåëüíîñòè ïîëó÷àåì a a2 1 10� , òî F ai
R1 � è ïðè çíà-
÷åíèÿõ x x2 1 00� è x x2 1 01� íà âûõîäå âû÷èñëèòåëüíîé ñòðóêòóðû ïîëó÷àåì
F ai
R1 1� � , à íà îñòàëüíûõ âåêòîðàõ x x2 1 âûõîäíûå çíà÷åíèÿ ðàâíû íóëþ. Ýòè
çíà÷åíèÿ ñîâïàäàþò ñî çíà÷åíèÿìè ôóíêöèè �R a x
1
( , ) , êîòîðûå âû÷èñëÿþòñÿ
àëãîðèòìîì ÐÀÇÄÅËÅÍÈÅ.
Åñëè â êîíöå ïîñëåäîâàòåëüíîñòè ïîëó÷àåì a a2 1 11� , òî F a b
R
1
1 � � è ïðè
âñåõ çíà÷åíèÿõ x x2 1 , êðîìå çíà÷åíèÿ x x2 1 11� , íà âûõîäå âû÷èñëèòåëüíîé
ñòðóêòóðû ïîëó÷àåì F a b
R
1
1 1� � � . Ýòè çíà÷åíèÿ ñîâïàäàþò ñî çíà÷åíèÿìè
ôóíêöèè �R a x
1
( , ) , êîòîðûå âû÷èñëÿþòñÿ àëãîðèòìîì ÐÀÇÄÅËÅÍÈÅ.
Ëåììà äîêàçàíà.
Ëåììà 2. Àëãîðèòì ÐÀÇÄ–ÀËÑ ïðàâèëüíî âû÷èñëÿåò çíà÷åíèå �R a x
2
( , )
äëÿ ïîðîãîâîãî îòíîøåíèÿ R2 �� .
Äîêàçàòåëüñòâî. Ïóñòü a a a a an n� �1 2 1... — ïîðîãîâîå çíà÷åíèå è
x x x x xn n� �1 2 1... — âõîäíîé âåêòîð. Ïóñòü a xj j� äëÿ âñåõ j n i� �, ..., ( )1 è
a xi i� , ïðè÷åì a a a a aj j� �1 2 1... íå ñîäåðæèò îñîáûõ òî÷åê îòíîøåíèÿ R2 äëÿ
j n i� �, ..., ( )1 . Ðàññìîòðèì âîçìîæíûå ñëó÷àè.
1. Ïóñòü ai �1, xi � 0 . Òîãäà íà âñåõ ïîñëåäóþùèõ óðîâíÿõ ñîãëàñíî àëãî-
ðèòìó ÐÀÇÄ–ÀËÑ äî âîçíèêíîâåíèÿ îñîáîé òî÷êè ïîëó÷àåì âåêòîðû, ñîñòîÿùèå
èç íóëåâûõ ñòðîê.
Åñëè â êîíöå ïîñëåäîâàòåëüíîñòè ïîëó÷àåì a a2 1 11� , òî ýòî çíà÷èò, ÷òî íà
k-ì óðîâíå (i k� � 3) èìååòñÿ îñîáàÿ òî÷êà îòíîøåíèÿ R2 . Òîãäà íà ýòîì óðîâíå
âû÷èñëèòåëüíàÿ ñòðóêòóðà íàñòðàèâàåòñÿ íà ôóíêöèè F ai
R2 � , F a b
i
R
� �
1
2 & è, íà-
÷èíàÿ ñ ýòîãî óðîâíÿ, âñå âõîäíûå çíà÷åíèÿ ñòàíîâÿòñÿ ðàâíûìè íóëþ. Ïîýòîìó
íà âûõîäå âû÷èñëèòåëüíîé ñòðóêòóðû äëÿ x x2 1 00� ïîëó÷àåì F a b
R
1
2 0� �& .
Ýòî çíà÷åíèå ñîâïàäàåò ñî çíà÷åíèåì ôóíêöèè �R a x
2
0( , ) � , êîòîðîå âû÷èñëÿåò
àëãîðèòì ÐÀÇÄÅËÅÍÈÅ, ïîñêîëüêó a x� .
Åñëè â êîíöå ïîñëåäîâàòåëüíîñòè ïîëó÷àåì a a2 1 01� , òî F a
R
1
2 � è ïðè çíà-
÷åíèÿõ x x2 1 00� íà âûõîäå âû÷èñëèòåëüíîé ñòðóêòóðû ïîëó÷àåì çíà÷åíèå 0,
168 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
êîòîðîå ñîâïàäàåò ñî çíà÷åíèåì ôóíêöèè �R a x
2
( , ) , êîòîðîå âû÷èñëÿåò àëãî-
ðèòì ÐÀÇÄÅËÅÍÈÅ.
Åñëè â êîíöå ïîñëåäîâàòåëüíîñòè ïîëó÷àåì a a2 1 10� , òî F a b
R
1
2 � & è ïðè
çíà÷åíèÿõ x x2 1 00� ïîëó÷àåì F a b
R
1
2 0� �& . Ýòè çíà÷åíèÿ ñîâïàäàþò ñî çíà÷å-
íèÿìè ôóíêöèè �R a x
2
( , ) , êîòîðûå âû÷èñëÿþòñÿ àëãîðèòìîì ÐÀÇÄÅËÅÍÈÅ.
Åñëè â êîíöå ïîñëåäîâàòåëüíîñòè ïîëó÷àåì a a2 1 00� , òî F a b
R
1
2 � � è ïðè
çíà÷åíèÿõ x x2 1 00� íà âûõîäå âû÷èñëèòåëüíîé ñòðóêòóðû ïîëó÷àåì
F a b
R
1
2 0� � � . Ýòè çíà÷åíèÿ ñîâïàäàþò ñî çíà÷åíèÿìè ôóíêöèè �R a x
2
( , ) , êî-
òîðûå âû÷èñëÿþòñÿ àëãîðèòìîì ÐÀÇÄÅËÅÍÈÅ.
2. Ïóñòü ai � 0 , xi �1 . Òîãäà íà âñåõ ïîñëåäóþùèõ óðîâíÿõ ñîãëàñíî àëãî-
ðèòìó ÐÀÇÄ–ÀËÑ äî âîçíèêíîâåíèÿ îñîáîé òî÷êè (åñëè òàêîâàÿ èìååòñÿ) ïîëó-
÷àåì âåêòîðû, ñîñòîÿùèå èç åäèíèö.
Åñëè â êîíöå ïîñëåäîâàòåëüíîñòè ïîëó÷àåì a a2 1 00� , òî F a b
R
1
2 � � è ïðè
çíà÷åíèÿõ x x2 1 11� ïîëó÷àåì íà âûõîäå âû÷èñëèòåëüíîé ñòðóêòóðû çíà÷åíèå
F a b
R
1
2 1� � � , êîòîðîå ñîâïàäàåò ñî çíà÷åíèåì ôóíêöèè �R a x
2
0( , ) � , âû÷èñëÿ-
åìîå àëãîðèòìîì ÐÀÇÄÅËÅÍÈÅ, ïîñêîëüêó x a� .
Åñëè â êîíöå ïîñëåäîâàòåëüíîñòè ïîëó÷àåì a a2 1 01� , òî ïðè çíà÷åíèÿõ
x x2 1 11� íà âûõîäå âû÷èñëèòåëüíîé ñòðóêòóðû ïîëó÷àåì çíà÷åíèå F a
R
1
2 1� � ,
êîòîðîå ñîâïàäàåò ñî çíà÷åíèåì ôóíêöèè �R a x
2
( , ) , êîòîðîå âû÷èñëÿåò àëãî-
ðèòì ÐÀÇÄÅËÅÍÈÅ.
Åñëè â êîíöå ïîñëåäîâàòåëüíîñòè ïîëó÷àåì a a2 1 10� , òî F a b
R
1
2 � & , òîãäà
ïðè çíà÷åíèÿõ x x2 1 11� íà âûõîäå âû÷èñëèòåëüíîé ñòðóêòóðû ïîëó÷àåì
F a b
R
1
2 1� �& . Ýòè çíà÷åíèÿ ñîâïàäàþò ñî çíà÷åíèÿìè ôóíêöèè �R a x
2
( , ) , êî-
òîðûå âû÷èñëÿþòñÿ àëãîðèòìîì ÐÀÇÄÅËÅÍÈÅ.
Åñëè â êîíöå ïîñëåäîâàòåëüíîñòè ïîëó÷àåì a a2 1 11� , òî ýòî çíà÷èò, ÷òî íà
k-ì óðîâíå (i k� � 3) âñòðåòèëàñü îñîáàÿ òî÷êà îòíîøåíèÿ R2 . Òîãäà íà ýòîì
óðîâíå âû÷èñëèòåëüíàÿ ñòðóêòóðà íàñòðàèâàåòñÿ íà ôóíêöèè F ai
R2 � ,
F a b
i
R
� �
1
2 & è, íà÷èíàÿ ñ ýòîãî óðîâíÿ, âñå âõîäíûå çíà÷åíèÿ ñòàíîâÿòñÿ ñòðîêà-
ìè, ñîñòîÿùèìè èç åäèíèö, ò.å. x x2 1 11� . Ïîýòîìó íà âûõîäå ïîëó÷àåì
F a b
R
1
2 1� �& . Ýòî çíà÷åíèå ñîâïàäàåò ñî çíà÷åíèåì ôóíêöèè �R a x
2
1( , ) � , êî-
òîðîå âû÷èñëÿåò àëãîðèòì ÐÀÇÄÅËÅÍÈÅ.
Ëåììà äîêàçàíà.
Îñòàeòñÿ äîêàçàòü êîððåêòíîñòü àëãîðèòìà ÐÀÇÄ–ÀËÑ äëÿ ñëó÷àÿ îñîáîé òî÷êè.
Ëåììà 3. Àëãîðèòì ÐÀÇÄ–ÀËÑ ïðàâèëüíî âû÷èñëÿåò çíà÷åíèå ôóíêöèè
�R x( ) â îñîáûõ òî÷êàõ ïîðîãîâûõ îòíîøåíèé.
Äîêàçàòåëüñòâî. Ðàññìîòðèì âîçìîæíûå ñëó÷àè.
1. Ïîðîãîâîå îòíîøåíèå R1 �� è åãî îñîáàÿ òî÷êà íà i-ì óðîâíå âû÷èñëåíèé
a i( ) ...�100 00 . Òîãäà ñîãëàñíî îïðåäåëåíèþ èìååì F ai
R1 � , F a b
i
R
� �
1
1 & .
Åñëè xi � 0 , òî íà ñëåäóþùèõ óðîâíÿõ âñå çíà÷åíèÿ áóäóò åäèíè÷íûìè
ñòðîêàìè è, ñëåäîâàòåëüíî, x x2 1 11� . Íà ýòîì óðîâíå âûõîäíûì çíà÷åíèåì áó-
äåò åäèíèöà, ÷òî ñîâïàäàåò ñî çíà÷åíèåì, êîòîðîå âû÷èñëÿåò àëãîðèòì
ÐÀÇÄÅËÅÍÈÅ, ïîñêîëüêó x a� .
Åñëè xi �1 , òî íà âñåõ ïîñëåäóþùèõ óðîâíÿõ çíà÷åíèÿ áóäóò íóëåâûìè
ñòðîêàìè è, ñëåäîâàòåëüíî, x x2 1 00� . Íà ýòîì óðîâíå âûõîäíûì çíà÷åíèåì àë-
ãîðèòìà áóäåò íóëü, ÷òî ñîâïàäàåò ñî çíà÷åíèåì, êîòîðîå âû÷èñëÿåò àëãîðèòì
ÐÀÇÄÅËÅÍÈÅ, ïîñêîëüêó x a .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 169
2. Ïîðîãîâîå îòíîøåíèå R2 �� è åãî îñîáàÿ òî÷êà íà i-ì óðîâíå âû÷èñëåíèé
a i( ) ...� 011 11 . Òîãäà ñîãëàñíî îïðåäåëåíèþ èìååì F ai
R2 � , F a b
i
R
� �
1
2 & .
Åñëè xi � 0 , òî íà ñëåäóþùèõ óðîâíÿõ âñå çíà÷åíèÿ áóäóò íóëåâûìè ñòðîêà-
ìè è, ñëåäîâàòåëüíî, x x2 1 00� . Íà ýòîì óðîâíå âûõîäíûì çíà÷åíèåì áóäåò
íóëü, ÷òî ñîâïàäàåò ñî çíà÷åíèåì, êîòîðîå âû÷èñëÿåò àëãîðèòì ÐÀÇÄÅËÅÍÈÅ,
ïîñêîëüêó x a� .
Åñëè xi �1 , òî íà âñåõ ïîñëåäóþùèõ óðîâíÿõ çíà÷åíèÿ áóäóò åäèíè÷íûìè
ñòðîêàìè è, ñëåäîâàòåëüíî, x x2 1 11� . Íà ýòîì óðîâíå âûõîäíûì çíà÷åíèåì àë-
ãîðèòìà áóäåò åäèíèöà, ÷òî ñîâïàäàåò ñî çíà÷åíèåì, êîòîðîå âû÷èñëÿåò àëãî-
ðèòì ÐÀÇÄÅËÅÍÈÅ, ïîñêîëüêó x a� .
3. Ïîðîãîâîå îòíîøåíèå R3 �� è åãî îñîáàÿ òî÷êà íà i-ì óðîâíå âû÷èñëåíèé
a i( ) ...� 011 11 . Òîãäà ñîãëàñíî îïðåäåëåíèþ èìååì F ai
R3 � , F a b
i
R
� �
1
3 & .
Åñëè xi � 0 , òî íà ñëåäóþùèõ óðîâíÿõ âñå çíà÷åíèÿ áóäóò åäèíè÷íûìè
ñòðîêàìè è, ñëåäîâàòåëüíî, x x2 1 11� . Íà ýòîì óðîâíå âûõîäíûì çíà÷åíèåì áó-
äåò åäèíèöà, ÷òî ñîâïàäàåò ñî çíà÷åíèåì, êîòîðîå âû÷èñëÿåò àëãîðèòì
ÐÀÇÄÅËÅÍÈÅ, ïîñêîëüêó x a� .
Åñëè xi �1 , òî íà âñåõ ïîñëåäóþùèõ óðîâíÿõ çíà÷åíèÿ áóäóò íóëåâûìè
ñòðîêàìè è, ñëåäîâàòåëüíî, x x2 1 00� . Íà ýòîì óðîâíå âûõîäíûì çíà÷åíèåì àë-
ãîðèòìà áóäåò íóëü, ÷òî ñîâïàäàåò ñî çíà÷åíèåì, êîòîðîå âû÷èñëÿåò àëãîðèòì
ÐÀÇÄÅËÅÍÈÅ, ïîñêîëüêó x a� .
4. Ïîðîãîâîå îòíîøåíèå R4 � è åãî îñîáàÿ òî÷êà íà i-ì óðîâíå âû÷èñëåíèé
a i( ) ...�100 00 . Òîãäà ñîãëàñíî îïðåäåëåíèþ èìååì F ai
R4 � , F a b
i
R
� �
1
4 & .
Åñëè xi � 0 , òî íà ñëåäóþùèõ óðîâíÿõ âñå çíà÷åíèÿ áóäóò íóëåâûìè ñòðîêà-
ìè è, ñëåäîâàòåëüíî, x x2 1 00� . Ïðè ýòèõ çíà÷åíèÿõ âûõîäíûì çíà÷åíèåì áóäåò
íóëü, ÷òî ñîâïàäàåò ñî çíà÷åíèåì, êîòîðîå âû÷èñëÿåò àëãîðèòì ÐÀÇÄÅËÅÍÈÅ,
ïîñêîëüêó x a� .
Åñëè xi �1 , òî íà âñåõ ïîñëåäóþùèõ óðîâíÿõ çíà÷åíèÿ áóäóò åäèíè÷íûìè
ñòðîêàìè è, ñëåäîâàòåëüíî, x x2 1 11� . Ïðè ýòèõ çíà÷åíèÿõ âûõîäíûì çíà÷åíèåì
àëãîðèòìà áóäåò åäèíèöà, ÷òî ñîâïàäàåò ñî çíà÷åíèåì, êîòîðîå âû÷èñëÿåò àëãî-
ðèòì ÐÀÇÄÅËÅÍÈÅ, ïîñêîëüêó x a .
Ëåììà äîêàçàíà.
Äîêàçàòåëüñòâî òåîðåìû âûòåêàåò èç äîêàçàííûõ ëåìì.
ÏÐÈÌÅÍÅÍÈÅ ÀËÑ
Îäíèì èç ïðèìåíåíèé ÀËÑ — íåéðîííûå ñåòè íà îñíîâå ïåðñåïòðîíîâ.
 [6,7] îïèñàíà ïðîáëåìà ôóíêöèè XOR, ñîãëàñíî êîòîðîé îäíîñëîéíûé
ïåðñåïòðîí íå ìîæåò âîñïðîèçâåñòè òàêóþ ïðîñòóþ ôóíêöèþ, êàê XOR.
Ïðîáëåìà èëëþñòðèðóåòñÿ îäíîñëîéíîé îäíîíåéðîííîé ñèñòåìîé ñ äâóìÿ âõîäà-
ìè (x y, ) (ðèñ. 2) ñ ñîîòâåòñòâóþùèìè âåñîâûìè êîýôôèöèåíòàìè (w1 , w2). Íåé-
ðîí âû÷èñëÿåò ñóììó âçâåøåííûõ
âõîäîâ: NET xw xw� �1 2 . Ýòî óðàâ-
íåíèå ëèíåéíî ïî x è y . Ôóíêöèÿ G
ðåàëèçóåò ïîðîãîâîå îòíîøåíèå R4 � ,
ïîýòîìó âûõîä ïåðñåïòðîíà OUT
ïðèíèìàåò çíà÷åíèå íóëü, êîãäà çíà-
÷åíèå âçâåøåííîé ñóììû NET ìåíåå
çíà÷åíèÿ ïîðîãà (âåêòîðà a), è çíà÷å-
íèå åäèíèöû â ñëó÷àå ðàâåíñòâà èëè
ïðåâûøåíèÿ çíà÷åíèÿ ïîðîãà.
170 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
Ðèñ. 2. Îäíîíåéðîííàÿ ñèñòåìà
x
w1
y
w2
NET
G
OUT
Âñå âîçìîæíûå êîìáèíàöèè
ôóíêöèé ïåðåìåííûõ ñîñòîÿò èç ÷å-
òûðåõ òî÷åê íà ïëîñêîñòè (ðèñ. 3).
 çàâèñèìîñòè îò ïåðåìåííûõ çíà-
÷åíèé w w1 2, è ïîðîãà a a a( ( ) ( ))1 3� èçìåíÿåòñÿ óãîë íàêëîíà è ñìåùåíèå ïðÿ-
ìîé îòíîñèòåëüíî íà÷àëà êîîðäèíàò. Äëÿ òîãî ÷òîáû ñåòü ðåàëèçîâàëà ôóíê-
öèþ XOR, íåîáõîäèìî ðàñïîëîæèòü ïðÿìóþ òàê, ÷òîáû òî÷êè A áûëè ñ îäíîé
ñòîðîíû ïðÿìîé, à òî÷êè B — ñ äðóãîé. Íî ýòî íåâîçìîæíî. Íèêàêàÿ êîìáè-
íàöèÿ çíà÷åíèé äâóõ âåñîâûõ êîýôôèöèåíòîâ è ïîðîãà íå ñìîæåò äàòü ñîîò-
íîøåíèÿ ìåæäó âõîäîì è âûõîäîì, êîòîðîå çàäàíî òàáë. 1.
Äëÿ ðåàëèçàöèè ôóíêöèè XOR ðàññìîòðèì äâóõñëîéíóþ ñåòü ñ äâóìÿ
äâóõâõîäîâûìè íåéðîíàìè ïåðâîãî ñëîÿ, êîòîðûå ñîåäèíåíû ñ îäíèì íåéðî-
íîì âî âòîðîì ñëîå (ðèñ. 4). Êàæäûé íåéðîí ïåðâîãî ñëîÿ ðàçáèâàåò ïëîñ-
êîñòü x y� íà äâå ïîëóïëîñêîñòè. Ïåðâàÿ îáåñïå÷èâàåò «åäèíè÷íûé» âûõîä
(òî÷êà A1) âûøå âåðõíåé ëèíèè (ëîãè÷åñêàÿ ôóíêöèÿ AND), âòîðàÿ — «åäè-
íè÷íûé» âûõîä (òî÷êà A0) íèæå íèæíåé ëèíèè (ëîãè÷åñêàÿ ôóíêöèÿ NOR1).
Âûõîäíîé ñèãíàë íåéðîíà âòîðîãî ñëîÿ ðàâåí åäèíèöå òîëüêî â ñëó÷àå, êîã-
äà îí âûøå âåðõíåé è íèæå íèæíåé ëèíèé (ëîãè÷åñêàÿ ôóíêöèÿ NOR2). Òàêèì
îáðàçîì, ïðîáëåìà XOR ðàçðåøèìà (òàáë. 2).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 171
Ðèñ. 3. Ãðàôè÷åñêîå ïðåäñòàâëåíèå ïðîáëåìû XOR
Ò à á ë è ö à 1
Òî÷êa
Çíà÷åíèå
x
Çíà÷åíèå
y
Çíà÷åíèå
ôóíêöèè
XOR
A0 0 0 0
B0 1 0 1
B1 0 1 1
A1 1 1 0
Ðèñ. 4. Ñòðóêòóðà äâóõñëîéíîé ñåòè äëÿ ðåøåíèÿ ïðîáëåìû XOR (à) è åå ãðàôè÷åñêîå
ïðåäñòàâëåíèå (á)
à á
w1
w2
w3
w4
w5
w6
x
y
Ò à á ë è ö à 2
Òî÷êa Çíà÷åíèå x Çíà÷åíèå y NOR1 AND
Âûõîäíîå
çíà÷åíèå
(NOR2)
A0 0 0 1 0 0
B0 1 0 0 0 1
B1 0 1 0 0 1
A1 1 1 0 1 0
Ðàññìîòðèì ïðèìåð ðàçðå-
øåíèÿ ïðîáëåìû XOR â íåé-
ðîííûõ ñåòÿõ ñ ïîìîùüþ äâóõ-
ñëîéíîé ñåòè, ãäå â êà÷åñòâå
ïîðîãîâîãî óñòðîéñòâà â íåé-
ðîíàõ èñïîëüçóþòñÿ íå êîìïà-
ðàòîðû, à ñèíòåçèðîâàííûå
ñ ïîìîùüþ ðàññìîòðåííîãî
âûøå àëãîðèòìà àäàïòàöèè (ñèí-
òåçà) ñòðóêòóð ïîðîãîâûå óñòðî-
éñòâà äëÿ çàäàííûõ ïàðàìåòðîâ:
çíà÷åíèå ïîðîãà a � 0010 , ïîðî-
ãîâîå îòíîøåíèå R3 �� . Íà÷è-
íàåì àíàëèçèðîâàòü çíà÷åíèÿ
ïîðîãà (âåêòîðà a) ñî ñòàðøèõ
áèòîâ. Ïðè a4 0� òèï ëîãè÷å-
ñêîé ôóíêöèè äëÿ ýòîãî óðîâíÿ îïðåäåëÿåòñÿ êàê F a b
3
3 :� � , ïðè a3 0� èìååì
F a b
2
3 :� � , ïðè a2 1� , a1 0� èìååì F a b
1
3 :� � .
Ñèíòåçèðîâàííàÿ ñòðóêòóðíàÿ ñõåìà ïîðîãîâîãî óñòðîéñòâà ñ èñïîëüçîâàíèåì
èíñòðóìåíòàëüíîé ñèñòåìû ISE Foundation ïðåäñòàâëåíà íà ðèñ. 5, à åãî âðåìåííàÿ
äèàãðàììà ðàáîòû — íà ðèñ. 6.
Èñõîäíûå äàííûå äëÿ ñèíòåçà äâóõñëîéíîé íåéðîííîé ñåòè ïðèâåäåíû â
òàáë. 3. Ñèíòåçèðîâàííàÿ ñòðóêòóðà äâóõñëîéíîé íåéðîííîé ñåòè ñ èñïîëüçîâà-
íèåì èíñòðóìåíòàëüíîé ñèñòåìû ISE Foundation ïðåäñòàâëåíà íà ðèñ. 7, à åå âðå-
ìåííàÿ äèàãðàììà ðàáîòû — íà ðèñ. 8. Åñëè â àíàëîãè÷íîé íåéðîííîé ñåòè ïîðî-
ãîâûå óñòðîéñòâà ðåàëèçîâàòü ñ ïîìîùüþ ñòàíäàðòíûõ êîìïàðàòîðîâ, òî ïîëó÷èì
ðåçóëüòàòû ñèíòåçà ñòðóêòóðû (òàáë. 4).
172 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
Ðèñ. 5. Ñèíòåçèðîâàííàÿ ñòðóêòóðíàÿ ñõåìà ïîðîãîâîãî
óñòðîéñòâà
Ðèñ. 6. Âðåìåííàÿ äèàãðàììà ðàáîòû ïîðîãîâîãî óñòðîéñòâà
Ò à á ë è ö à 3
Çíà÷åíèå
ïàðàìåòðà
Ïåðâûé íåéðîí (neur_1)
ïåðâîãî ñëîÿ (NOR1)
Âòîðîé íåéðîí (neur_2)
ïåðâîãî ñëîÿ (AND)
Òðåòèé íåéðîí (neur_3)
âòîðîãî ñëîÿ (NOR2)
R R1 �� R4 � R1 ��
a 00011 11000 00010
w w1 4� , w2 7� w3 14� , w4 11� w5 5� , w6 6�
Ðèñ. 7. Ñòðóêòóðà äâóõñëîéíîé íåéðîííîé ñåòè
íà îñíîâå ïîðîãîâîãî óñòðîéñòâà
Ò à á ë è ö à 4
Ïàðàìåòðû
Îöåíêà âàðèàíòîâ íåéðîííîé
ñåòè
íà îñíîâå
êîìïàðàòîðà
íà îñíîâå
ïîðîãîâîãî
óñòðîéñòâà
Àïïàðàòíûå
çàòðàòû
(êîëè÷åñòâî
ñëàéñîâ)
24 18
Áûñòðî-
äåéñòâèå, íñ
8,42 7,94
ÇÀÊËÞ×ÅÍÈÅ
Ðàññìîòðåííûé â ñòàòüå àëãîðèòì àäàïòàöèè ñòðóêòóð òèïà ÀËÑ íà ðàçäåëå-
íèå ìíîæåñòâà çíà÷åíèé áóëåâûõ ôóíêöèé íà îñíîâå çàäàííûõ ïîðîãîâîãî
çíà÷åíèÿ è ïîðîãîâîãî îòíîøåíèÿ ïîçâîëÿåò ïðè ôèêñèðîâàííîé ñòðóêòóðå
ñâÿçåé îïðåäåëèòü òèïû ëîãè÷åñêèõ ôóíêöèé äëÿ óíèâåðñàëüíûõ ëîãè÷åñêèõ
ýëåìåíòîâ. Ïðèìåíåíèå ÀËÑ äëÿ ðåàëèçàöèè ïîðîãîâîãî óñòðîéñòâà â íåéðîí-
íûõ ñåòÿõ íà îñíîâå ïåðñåïòðîíîâ ïîçâîëÿåò íà òðåòü ñîêðàòèòü àïïàðàòíûå
çàòðàòû êðèñòàëëà ÏËÈÑ (âûðàæåííûå â êîëè÷åñòâå ñëàéñîâ), à òàêæå (õîòÿ è
íåçíà÷èòåëüíî) ïîâûñèòü áûñòðîäåéñòâèå.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. E s t r i n G . Organization of computer system: The fixed plus variable structure computer // Proc. Western
Joint Computer Conf. — 1960. — N 5. — P. 33–40.
2. Ï à ë à ã è í À . Â . , Î ï à í à ñ å í ê î Â . Í . Òåõíîëîãèÿ ðåêîíôèãóðèðóåìîãî êîìïüþòèíãà //
Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2007. — 43, ¹ 5. — Ñ. 72–86.
3. Ï à ë à ã è í À .  . , Î ï à í à ñ å í ê î  . Í . Ðåêîíôèãóðèðóåìûå âû÷èñëèòåëüíûå ñèñòåìû. — Ê.:
Ïðîñâ³òà, 2006. — 295 ñ.
4. Ä è ñ ê ð å ò í à ÿ ìàòåìàòèêà è ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè / Þ.Ë. Âàñèëüåâ,
Ô.ß. Âåòóõíîâñêèé, Â.Â. Ãëàãîëåâ, Þ.È. Æóðàâë¸â è äð. — Ì.: Íàóêà, 1971. — 311 ñ.
5. Á è ð ê ã î ô Ã . , Á à ð ò è Ò . Ñîâðåìåííàÿ ïðèêëàäíàÿ àëãåáðà. — Ì.: Ìèð, 1976. — 400 ñ.
6. Ê ó ñ ñ ó ë ü Í . Í . Îáó÷åíèå íåéðîííûõ ñåòåé ñ èñïîëüçîâàíèåì ìåòîäà íå÷åòêèõ ýëëèïñîèäàëüíûõ
îöåíîê // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. — 2001. — ¹ 1. — Ñ. 14–21.
7. Ê ó ñ ñ ó ë ü Í . Ì . , Ø å ë å ñ ò î â À . Þ . , Ë à â ð å í þ ê À . Ì . ²íòåëåêòóàëüí³ îá÷èñëåííÿ. — Ê.: Íàóê.
äóìêà, 2006. — 186 ñ.
Ïîñòóïèëà 21.02.2011
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 173
Ðèñ. 8. Âðåìåííàÿ äèàãðàììà ðàáîòû äâóõñëîéíîé ñåòè
|