Разбиение множества векторов с целыми координатами логическими аппаратными средствами

Рассматривается задача разбиения множества векторов с целыми координатами относительно покоординатного и лексикографического порядка на векторах с использованием автоматной интерпретации. Предложена аппаратная реализация операций трехзначной логики на базе кристаллов FPGA для проверки выполнимости ф...

Full description

Saved in:

Bibliographic Details
Published in:	Кибернетика и системный анализ
Date:	2019
Main Authors:	Крывый, С.Л., Опанасенко, В.Н., Завьялов, С.Б.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Subjects:	Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/180877
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:	Разбиение множества векторов с целыми координатами логическими аппаратными средствами / С.Л. Крывый, В.Н. Опанасенко, С.Б. Завьялов // Кибернетика и системный анализ. — 2019. — Т. 56, № 3. — С. 136-148. — Бібліогр.: 16 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859587773558685696
author	Крывый, С.Л. Опанасенко, В.Н. Завьялов, С.Б.
author_facet	Крывый, С.Л. Опанасенко, В.Н. Завьялов, С.Б.
citation_txt	Разбиение множества векторов с целыми координатами логическими аппаратными средствами / С.Л. Крывый, В.Н. Опанасенко, С.Б. Завьялов // Кибернетика и системный анализ. — 2019. — Т. 56, № 3. — С. 136-148. — Бібліогр.: 16 назв. — рос.
collection	DSpace DC
container_title	Кибернетика и системный анализ
description	Рассматривается задача разбиения множества векторов с целыми координатами относительно покоординатного и лексикографического порядка на векторах с использованием автоматной интерпретации. Предложена аппаратная реализация операций трехзначной логики на базе кристаллов FPGA для проверки выполнимости формул этой логики. Розглянуто задачу розбиття множини векторів з цілими координатами відносно покоординатного і лексикографічного порядку на векторах із використанням автоматної інтерпретації. Запропоновано апаратну реалізацію операцій тризначної логіки на базі кристалів FPGA для перевірки виконуваності формул цієї логіки. The problem of partitioning a set of vectors with integer coordinates with respect to the coordinate-wise and lexicographic order on vectors by using an automatic interpretation is considered. The FPGA-based hardware implementation of three-valued logic operations for feasibility verification of the formulas of this logic is proposed.
first_indexed	2025-11-27T11:44:55Z
format	Article
fulltext	Ñ.Ë. ÊÐÛÂÛÉ, Â.Í. ÎÏÀÍÀÑÅÍÊÎ, Ñ.Á. ÇÀÂÜßËÎÂ ÓÄÊ 516.813 ÐÀÇÁÈÅÍÈÅ ÌÍÎÆÅÑÒÂÀ ÂÅÊÒÎÐÎÂ Ñ ÖÅËÛÌÈ ÊÎÎÐÄÈÍÀÒÀÌÈ ËÎÃÈ×ÅÑÊÈÌÈ ÀÏÏÀÐÀÒÍÛÌÈ ÑÐÅÄÑÒÂÀÌÈ Àííîòàöèÿ. Ðàññìîòðåíà çàäà÷à ðàçáèåíèÿ ìíîæåñòâà âåêòîðîâ ñ öåëûìè êîîðäèíàòàìè îòíîñèòåëüíî ïîêîîðäèíàòíîãî è ëåêñèêîãðàôè÷åñêîãî ïîðÿä- êà íà âåêòîðàõ ñ èñïîëüçîâàíèåì àâòîìàòíîé èíòåðïðåòàöèè. Ïðåäëîæåíà àïïàðàòíàÿ ðåàëèçàöèÿ îïåðàöèé òðåõçíà÷íîé ëîãèêè íà áàçå êðèñòàëëîâ FPGA äëÿ ïðîâåðêè âûïîëíèìîñòè ôîðìóë ýòîé ëîãèêè. Êëþ÷åâûå ñëîâà: öåëî÷èñëåííûå âåêòîðû, ïîðîãîâûå çíà÷åíèÿ, êîíå÷íûå àâòîìàòû, òðåõçíà÷íàÿ ëîãèêà. ÂÂÅÄÅÍÈÅ Ñèíòåç àïïàðàòíûõ ñðåäñòâ äëÿ ðåøåíèÿ çàäà÷è ðàçáèåíèÿ ìíîæåñòâà áóëåâûõ âåêòîðîâ è âåêòîðîâ ñ öåëî÷èñëåííûìè íåîòðèöàòåëüíûìè êîîðäèíàòàìè è ïîðîãîâîãî çíà÷åíèÿ ðàññìàòðèâàëñÿ â [1] (ñ èñïîëüçîâàíèåì àëãîðèòìîâ èç ðàáîò [2, 3]). Òàêîé ïîäõîä èçâåñòåí êàê «òåõíîëîãèÿ ðåêîíôèãóðèðóåìîãî êîìïüþòèíãà» [4, 5], è åãî âîïëîùåíèå â ðåàëüíûå ïðîåêòû (ñì. [6–13]) ñòàëî âîçìîæíûì áëàãîäàðÿ ïîÿâëåíèþ ïðîãðàììèðóåìûõ ëîãè÷åñêèõ èíòåãðàëüíûõ ñõåì (ÏËÈÑ). Â íàñòîÿùåé ñòàòüå ðàññìàòðèâàåòñÿ îáîáùåíèå ìåòîäà ðåøåíèÿ çàäà÷è ðàç- áèåíèÿ ìíîæåñòâà âåêòîðîâ, êîòîðûé ðàññìàòðèâàëñÿ â ðàáîòå [1], è èñïîëüçîâà- íèå ýòîãî ìåòîäà äëÿ ïðîâåðêè âûïîëíèìîñòè ôîðìóë òðåõçíà÷íîé ëîãèêè. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È Äàíû êîíå÷íîå ìíîæåñòâî âåêòîðîâ V m� { }� � �1 2, , ,� ðàçìåðíîñòè n N� è ôèêñèðîâàííûé ïîðîãîâûé âåêòîð a c c cn� ( , , , )1 2 � , ãäå � i , a Z n� , Z — ìíîæåñòâî öåëûõ ÷èñåë. Íà ìíîæåñòâå âåêòîðîâ çàäàíî îòíîøåíèå ïîðÿäêà. Íàè- áîëåå ÷àñòî òàêèì îòíîøåíèåì ÿâëÿåòñÿ ïîêîîðäèíàòíûé (÷àñòè÷íûé) ïîðÿäîê èëè ëåêñèêîãðàôè÷åñêèé (ïîëíûé) ïîðÿäîê. Îïðåäåëåíèå 1. Ïóñòü x x x Zn n� �( , , )1 � , y y y Zn n� �( , , )1 � . Áèíàðíîå îòíîøåíèå x y i n x yi i� � � � �1, , ,� íàçûâàåòñÿ ïîêîîðäèíàòíûì ïîðÿäêîì. Áèíàðíîå îòíîøåíèå x y i j x y x yi i j j� � � � � � �( ) ( ), i j n, , ,�1 � , íàçû- âàåòñÿ ëåêñèêîãðàôè÷åñêèì ïîðÿäêîì. Ñ÷èòàåì, ÷òî îòíîñèòåëüíî ïîêîîðäèíàòíîãî ïîðÿäêà x y� õîòÿ áû äëÿ îä- íîãî i n�1, ,� èìååì x yi i� . Çàäà÷à ðàçáèåíèÿ. Íåîáõîäèìî ðàçáèòü ìíîæåñòâî V îòíîñèòåëüíî ïîðîãîâî- ãî âåêòîðà a íà ïîäìíîæåñòâà V V a1 � � �{ }� �\| , V V a2 � � { }� �\| ,V V3 � �{� \| � � a}, V V a4 � �{ }� �\| � , ãäå ñèìâîë � îçíà÷àåò, ÷òî âåêòîðû íå ñðàâíèìû 136 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 © Ñ.Ë. Êðûâûé, Â.Í. Îïàíàñåíêî, Ñ.Á. Çàâüÿëîâ, 2019 (äëÿ ëåêñèêîãðàôè÷åñêîãî ïîðÿäêà òàêèõ ïîä- ìíîæåñòâ áóäåò òðè: V1, V2 , V3). Â íàñòîÿùåé ñòàòüå ðàññìàòðèâàåòñÿ ïî- êîîðäèíàòíûé ïîðÿäîê, ïîñêîëüêó ðåøåíèå çàäà÷è ðàçáèåíèÿ äëÿ ëåêñèêîãðàôè÷åñêîãî ïîðÿäêà î÷åâèäíûì îáðàçîì ñëåäóåò èç ðåøå- íèÿ çàäà÷è ðàçáèåíèÿ äëÿ ïîêîîðäèíàòíîãî ïîðÿäêà. ÀÂÒÎÌÀÒÍÀß ÈÍÒÅÐÏÐÅÒÀÖÈß ÇÀÄÀ×È ÐÀÇÁÈÅÍÈß Ñëó÷àé öåëûõ íåîòðèöàòåëüíûõ êîîðäèíàò âåêòîðîâ. Àâòîìàòíûé ïîäõîä ê ðåøåíèþ çàäà÷è ðàçáèåíèÿ ñîñòîèò â ïîñòðîåíèè îäíîðîäíîé ñåòè èç ïðî- ñòûõ àâòîìàòîâ, ïî ôèíàëüíûì ñîñòîÿíèÿì êîòîðûõ îïðåäåëÿåòñÿ ïðèíàäëåæ- íîñòü âåêòîðà � �V ê îäíîìó èç ïîäìíîæåñòâ: V1, V2 , V3 , V4 . Ïðåèìóùåñòâî àâòîìàòíîãî ïîäõîäà ñîñòîèò â òîì, ÷òî îí ïîçâîëÿåò âûïîëíèòü ðàçáèåíèå ìíîæåñòâà V íà ïîäìíîæåñòâà V1, V2 , V3 , V4 îäíîâðåìåííî äëÿ âñåõ îòíîøå- íèé R � � �{ }, , ,� . Àâòîìàòû, èç êîòîðûõ ñòðîèòñÿ ñåòü, ÿâëÿþòñÿ àâòîìàòà- ìè áåç âûõîäîâ [14, 15], à ôîðìàëüíîå îïðåäåëåíèå ñåòè àâòîìàòîâ èìååò ñëå- äóþùèé âèä. Îïðåäåëåíèå 2. Ñåòüþ àâòîìàòîâ íàçûâàåòñÿ n-êà A � ( , , )A An1 � , ñîñòîÿ- ùàÿ èç àâòîìàòîâ, ïðåäñòàâëåííûõ â âèäå A S X f a Fi i i i i i� ( , , , , ) 0 , i n�1 2, , ,� . Ñîñòîÿíèåì ñåòè A íàçûâàåòñÿ n-êà ñîñòîÿíèé ( , , )a an1 � , ãäå a Si i� äëÿ êàæäî- ãî i n�1 2, , ,� . Ñîñòîÿíèå ñåòè ( , , )a an1 � íàçûâàåòñÿ íà÷àëüíûì, åñëè a ai i� 0 , è ôèíàëüíûì èëè çàêëþ÷èòåëüíûì, åñëè a Fi i� äëÿ âñåõ i n�1 2, , ,� . Òîãäà n-êà x x xn� ( , , )1 � , ãäå x X i ni i� �, , , ,1 2 � , íàçûâàåòñÿ äåéñòâèåì â ñåòè A, êîòîðîå ïåðåâîäèò ñåòü èç ñîñòîÿíèÿ ( , , )a an1 � â ñîñòîÿíèå ( , , )b bn1 � òàê, ÷òî ( , , )b bn1 � � ( ( , ), , ( , ))f a x f a xn n n1 1 1 � . Ñåòü íàçîâåì îäíîðîäíîé, åñëè âñå åå àâòîìàòû èìåþò îäèí âèä. Äëÿ ðåøåíèÿ çàäà÷è êëàññèôèêàöèè èñïîëüçóåòñÿ îäíîðîäíàÿ ñåòü àâòîìà- òîâ [14, 15], âèä êîòîðûõ ïîêàçàí íà ðèñ. 1. Íà÷àëüíîå ñîñòîÿíèå àâòîìàòà íóëåâîå, âñå ñîñòîÿíèÿ àâòîìàòà çàêëþ÷èòåëüíûå, à âõîäíûì àëôàâèòîì ÿâëÿþòñÿ âåê- òîð-ñòîëáöû â äâîè÷íîì àëôàâèòå, êîòîðûå ïðåäñòàâëÿþò ñîîòâåòñòâóþùèå ïàðû êîîðäèíàò âåêòîðà � èç V è ïîðîãîâîãî âåêòîðà a . Ïîÿñíèì ýòî ïðåäñòàâëåíèå íà ïðèìåðå. Ïðèìåð 1. Ïóñòü � � ( , )3 4 è a � ( , )3 2 . Ýòè âåêòîðû ïðåäñòàâëÿþòñÿ äâîè÷- íûìè ñëîâàìè � � � � T � � � � � � � �� 3 4 011 100 3 2 1, ãäå � 3 0 1 � � �� , � 2 1 0 � � �� , �1 1 0 � � �� ; a a a aT � � � � � � � �� 3 2 011 010 3 2 1, ãäå a3 0 0 � � �� , a2 1 1 � � �� , a1 1 0 � � �� . Òàêèì îáðàçîì, àëôà- âèò àâòîìàòà A1 ñîñòàâëÿþò ñèìâîëû x1 0 0 � � �� , x2 0 1 � � �� , x3 1 0 � � �� , x4 1 1 � � �� . Íà âõîä àâòîìàòà A1 ñòàðøèìè ðàçðÿäàìè ïîäàþòñÿ ñëîâà p x x x1 1 4 4 011 011 � � �� , p x x x2 3 2 1 100 010 � � �� , ïðåäñòàâëÿþùèå ïåðâûå è âòîðûå êîîðäèíàòû âåêòîðîâ � è a ñîîòâåòñòâåííî. Êîíåö ïðèìåðà 1. Îïðåäåëåíèå ìíîæåñòâà, êîòîðîìó ïðèíàäëåæèò âåêòîð �, çàâèñèò îò òîãî, â êàêîì ôèíàëüíîì ñîñòîÿíèè îñòàíîâèòñÿ ñåòü àâòîìàòîâ A. Â ïðèâåäåííîì ïðèìåðå èìååì âåêòîð � a îòíîñèòåëüíî ïîêîîðäèíàòíîãî è ëåêñèêîãðàôè÷åñ- êîãî ïîðÿäêîâ è åãî ñëåäóåò îòíåñòè ê ïîäìíîæåñòâó V2 . ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 137 2 0 1 0 1 01 01 0110 1010 1010 0110 1 0 Ðèñ. 1. Àâòîìàò A1 Ïðåäëîæåíèå 1. Àâòîìàò A1 ïðàâèëüíî âû÷èñëÿåò îòíîøåíèå x y� ìåæäó äâóìÿ öåëûìè ïîëîæèòåëüíûìè ÷èñëàìè: x è y, ïðåäñòàâëåííûìè â äâîè÷íîé ñèñòåìå ñ÷èñëåíèÿ. Äîêàçàòåëüñòâî î÷åâèäíûì îáðàçîì ñëåäóåò èç òîãî ôàêòà, ÷òî îòíîøåíèå ïî- ðÿäêà x y� íà âåêòîðàõ ïåðåíîñèòñÿ íà ðàçðÿäû èõ äâîè÷íîãî ïðåäñòàâëåíèÿ êîîð- äèíàò. Äåéñòâèòåëüíî, ïóñòü p x x xx k� 1 2� è p y y yy k� 1 2� — äâîè÷íûå ñëîâà, ïðåäñòàâëÿþùèå ÷èñëà x è y ñîîòâåòñòâåííî. Ïîñêîëüêó äâîè÷íûå ñëîâà ïîäàþòñÿ íà âõîä àâòîìàòà A1 ñòàðøèìè ðàçðÿäàìè, òî x y� , åñëè x yj j� äëÿ íåêîòîðîãî 1 � �j k , è x yi i� äëÿ âñåõ i j� . Ýòî îçíà÷àåò, ÷òî j-é ðàçðÿä ÷èñëà x ìåíüøå j-ãî ðàçðÿäà ÷èñëà y, è òîãäà àâòîìàò èç ñîñòîÿíèÿ 0 ïåðåéäåò â ñîñòîÿíèå 2 (ñì. ðèñ. 1). À ýòî çíà÷èò, ÷òî x y� . Îñòàëüíûå ñëó÷àè àíàëîãè÷íû. Êîíåö äîêàçàòåëüñòâà. Îáùåå ðåøåíèå çàäà÷è ðàçáèåíèÿ ìíîæåñòâà V âûïîëíÿåòñÿ ñåòüþ àâòîìà- òîâ A � ( , , )A An1 � (ñëó÷àé n-ìåðíûõ âåêòîðîâ èç V ). Íàñòðîéêà ñåòè íà ðåøå- íèå çàäà÷è ðàçáèåíèÿ ñîñòîèò â ñëåäóþùåì: âñå àâòîìàòû ñåòè îäèíàêîâûå (n ýêçåìïëÿðîâ àâòîìàòà A1 íà ðèñ. 1); ñåòü íàõîäèòñÿ â íà÷àëüíîì ñîñòîÿíèè; ñëîâà ïîäàþòñÿ íà âõîä àâòîìàòîâ ñåòè ñòàðøèìè ðàçðÿäàìè. Íà âõîä ïåðâîãî àâòîìàòà ñåòè ïîäàåòñÿ äâîè÷íîå ñëîâî, ïðåäñòàâëÿþùåå ïåðâûå êîîðäèíàòû âåêòîðîâ � è a, íà âõîä âòîðîãî àâòîìàòà ñåòè — ñëîâî, ïðåäñòàâëÿþùåå âòîðûå êîîðäèíàòû âåêòîðîâ è ò.ä. Ïðèíàäëåæíîñòü âåêòîðà � ê ïîäìíîæåñòâó Vi , êàê îòìå÷àëîñü âûøå, çàâèñèò îò ôèíàëüíîãî ñîñòîÿíèÿ ñåòè, â êîòîðîì îíà îêàçà- ëàñü ïîñëå ïðî÷òåíèÿ âõîäíûõ ñëîâ. Åñëè îòíîøåíèå ïîðÿäêà ïîêîîðäèíàòíîå è ôèíàëüíûì ñîñòîÿíèåì ñåòè ÿâëÿþòñÿ à) (0, 0, 0), òî � � a , ïîýòîìó � �V3 ; á) ( p q r, , ), ãäå p q r, , ,�{ }0 1 è íå âñå çíà÷åíèÿ p q r, , ðàâíû íóëþ, òî � a , ïîýòîìó � �V2 ; â) ( p q r, , ), ãäå p q r, , ,�{ }0 2 è íå âñå çíà÷åíèÿ p q r, , ðàâíû íóëþ, òî � � a , ïîýòîìó � �V1; ã) (1, 2, 0), (0, 1, 2), (2, 1, 0), (2, 1, 2). (2, 2, 1), …, òî âåêòîð � íå ñðàâíèì ñ a , ïîýòîìó � �V4 . Åñëè îòíîøåíèå ïîðÿäêà ëåêñèêîãðàôè÷åñêîå è ôèíàëüíûì ñîñòîÿíèåì ñåòè ÿâëÿåòñÿ à' ) (0, 0, 0), òî � � a , ïîýòîìó � �V3 ; á' ) ( p q r, , ) è p q� èëè p q� è q r� , òî � a , ïîýòîìó � �V2 ; â' ) ( p q r, , ) è p q èëè p q� è q r , òî � � a , ïîýòîìó � �V1. Ïðèìåð 2. Ïóñòü V � �{�1 4 5 0( , , ), � 2 3 4 2� ( , , ), � 3 0 1 1� ( , , ), � 4 1 1 2� ( , , ), � 5 4 3 1� ( , , )} è ïîðîãîâûé âåêòîð a � ( , , )1 1 2 . Òîãäà ïàðà ( , )�1 a èìååò ïðåäñòàâëåíèå �1 4 5 0 100 101 000 � � � � � � � � � � � � � � � � , a � � � � � � � � � � � � � � � � 1 1 2 001 001 010 è ñëîâà, ñîîòâåòñòâóþùèå ïåðâûì êîîðäèíàòàì, èìåþò âèä p1 100 001 � � �� , ñîîòâåòñò- âóþùèå âòîðûì êîîðäèíàòàì — p2 101 001 � � �� , òðåòüèì êîîðäèíàòàì — p3 000 010 � � �� . Ñëîâî p1 ïîäàåòñÿ íà âõîä ïåðâîãî àâòîìàòà ñåòè, ñëîâî p2 — íà âõîä âòî- ðîãî àâòîìàòà ñåòè è p3 ïîäàåòñÿ íà âõîä òðåòüåãî àâòîìàòà. Â ðåçóëüòàòå ïîëó- ÷àåì ñîñòîÿíèÿ (1, 1, 2), â êîòîðûõ îñòàíîâèëèñü àâòîìàòû. Ýòî çíà÷èò, ÷òî âåê- òîðû �1 è a íå ñðàâíèìû îòíîñèòåëüíî ïîêîîðäèíàòíîãî ïîðÿäêà, à îòíîñèòåëü- íî ëåêñèêîãðàôè÷åñêîãî ïîðÿäêà �1 a . Äàëåå äëÿ ïîêîîðäèíàòíîãî ïîðÿäêà ïîëó÷àåì êîîðäèíàòû 138 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 � 2 1 011 100 010 011 001 � � � � � � � � � � � � �� p , p2 100 001 � � �� , p3 010 010 � � �� , êîòîðûå ïåðåâîäÿò ñåòü â ñîñòîÿíèÿ (1, 1, 0), ÷òî îçíà÷àåò � 2 a ; êîîðäèíàòû � 3 1 000 001 001 000 001 � � � � � � � � � � � � �� p , p2 001 001 � � �� , p3 001 010 � � �� , êîòîðûå ïåðåâîäÿò ñåòü â ñîñòîÿíèÿ (2, 0, 2), ÷òî îçíà÷àåò � 3 � a ; êîîðäèíàòû � 4 1 100 100 010 001 001 � � � � � � � � � � � � �� p , p2 001 001 � � �� , p3 010 010 � � �� , êîòîðûå ïåðåâîäÿò ñåòü â ñîñòîÿíèå (0, 0, 0), ÷òî îçíà÷àåò � 4 � a ; êîîðäèíàòû � 5 1 100 011 001 100 001 � � � � � � � � � � � � �� p , p2 011 001 � � �� , p3 001 010 � � �� , êîòîðûå ïåðåâîäÿò ñåòü â ñîñòîÿíèå (1,1,2), ýòî îçíà÷àåò, ÷òî âåêòîð � 5 íå ñðàâíèì ñ a. Òàêèì îáðàçîì, V V V V V� � � �1 2 3 4 , ãäå V1 3� { }� , V2 2� { }� , V3 4� { }� , V4 1 5� { }� �, — ðàçáèåíèå ìíîæåñòâà A îòíîñèòåëüíî ïîêîîðäèíàòíîãî ïîðÿäêà. Êîíåö ïðèìåðà 2. Ïðåäëîæåíèå 2. Îäíîðîäíàÿ ñåòü àâòîìàòîâ A � ( , , )A An1 � ïðàâèëüíî âû- ÷èñëÿåò îòíîøåíèå x y� ìåæäó äâóìÿ âåêòîðàìè x è y ñ öåëûìè ïîëîæèòåëüíû- ìè êîîðäèíàòàìè, êîòîðûå ïðåäñòàâëåíû â äâîè÷íîé ñèñòåìå ñ÷èñëåíèÿ. Äîêàçàòåëüñòâî ñëåäóåò íåïîñðåäñòâåííî èç ïðåäëîæåíèÿ 1 è ïï. à) – ã) äëÿ ïîêîîðäèíàòíîãî îòíîøåíèÿ ïîðÿäêà, à äëÿ ëåêñèêîãðàôè÷åñêîãî îòíîøåíèÿ ïîðÿäêà — èç ïï. à' ) – â' ). Äåéñòâèòåëüíî, ïóñòü x y� , òîãäà îäèí èç àâòîìàòîâ ñåòè A ñîãëàñíî ïðåäëîæåíèþ 1 ïåðåõîäèò â çàêëþ÷èòåëüíîå ñîñòîÿíèå 2 (ñì. ðèñ. 1), èç êîòîðîãî óæå íå âûõîäèò, à îñòàëüíûå àâòîìàòû ëèáî îñòàþòñÿ â ñîñòîÿíèè 0 (ðàâåíñòâî êîîðäèíàò), ëèáî ïåðåõîäÿò â ñîñòîÿíèå 2, ãäå îñòàþòñÿ äî êîíöà ðàáîòû. Ñîãëàñíî ï. â) äëÿ ïîêîîðäèíàòíîãî ïîðÿäêà � � a . Äëÿ ëåêñè- êîãðàôè÷åñêîãî îòíîøåíèÿ ïîðÿäêà äîêàçàòåëüñòâî ñëåäóåò èç ï. â' ). Îñòàëüíûå ñëó÷àè àíàëîãè÷íû. Êîíåö äîêàçàòåëüñòâà. Ñëó÷àé öåëî÷èñëåííûõ êîîðäèíàò âåêòîðîâ. Ðàññìîòðèì ïðèâåäåííóþ âûøå ïîñòàíîâêó çàäà÷è, íî êîîðäèíàòàìè âåêòîðîâ èç V çäåñü ÿâëÿþòñÿ íå íàòó- ðàëüíûå, à öåëûå ÷èñëà. Â ýòîì ñëó÷àå çàäà÷à áóäåò ðåøàòüñÿ ðàññìîòðåííûì âûøå ñïîñîáîì, åñëè îòðèöàòåëüíûå êîîðäèíàòû âåêòîðîâ ïðåäñòàâèòü â âèäå 2-äîïîëíå- íèÿ. Îòìåòèì, ÷òî 2-äîïîëíåíèå ÷èñëà x , äâîè÷íîå ïðåäñòàâëåíèå êîòîðîãî x x x xn n�1 1 0... , îïðåäåëÿåòñÿ òàêèì îáðàçîì: åñëè x � 0, òî xn � 0 è ( ) ...x x x xn2 1 1 00� � , åñëè x � 0, òî xn �1 è ( )x x xn2 1 01 1� �� , ãäå áèò xn ÿâëÿåòñÿ çíàêîâûì, à x xi i� �1 äëÿ 0 1� � �i n . Àâòîìàò äëÿ âû÷èñëåíèÿ 2-äîïîëíåíèÿ ïðåäñòàâëÿåòñÿ êîìïîçèöèåé äâóõ àâòîìàòîâ, ïåðâûé èç êîòîðûõ ñòðîèò äîïîëíåíèå, à âòîðîé ðåàëèçóåò îïåðàöèþ ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 139 ïðèáàâëåíèÿ åäèíèöû. Êîìïîçèöèÿ ýòèõ àâòîìàòîâ ïðåäñòàâëÿåòñÿ àâòîìàòîì C , ïîêàçàííûì íà ðèñ. 2. Íà ðèñ. 3 ïðåäñòàâëåí àâòîìàò B1; èç òàêèõ àâòîìàòîâ ñòðîèì îäíîðîäíóþ ñåòü B. Ñîñòîÿíèå a0 ââåäåíî äëÿ ðàñïîç- íàâàíèÿ çíàêîâ äâîè÷íûõ ÷èñåë, ïðåä- ñòàâëÿþùèõ êîîðäèíàòû âåêòîðîâ èç V . Âñå ñîñòîÿíèÿ àâòîìàòà B1, êðîìå ñîñòî- ÿíèÿ a0 , çàêëþ÷èòåëüíûå. Åñëè çíàêîâûå áèòû ðàçëè÷íû, òî ñðàçó ìîæíî îïðåäå- ëèòü, êàêîé èç âåêòîðîâ áîëüøå. Åñëè çíàêîâûå áèòû îäèíàêîâûå, òî ñðàâíåíèå âûïîëíÿåòñÿ â ñëó÷àå ïîëîæèòåëüíûõ êîîðäèíàò, êàê ïîêàçàíî âûøå, à åñëè áèòû îòðèöàòåëüíûå, òî ñðàâíåíèå âû- ïîëíÿåòñÿ ÷àñòüþ àâòîìàòà, êîòîðàÿ ñî- îòâåòñòâóåò ñîñòîÿíèþ 3 íà ðèñ. 3. Ïðèìåð 3. Ïóñòü V � � �{�1 4 5 0( , , ), �2 3 4 2� �( , , ), � 3 0 1 1� �( , , ), � 4 1 1 2� ( , , )} è ïîðîãîâûé âåêòîð a � �( , , )1 1 2 . Òîãäà ïàðà ( , )�1 a èìååò ïðåäñòàâëåíèå �1 4 5 0 1100 0101 0000 � � � � � � � � � � � � � � � � � , a � � � � � � � � � � � � � � � � � 1 1 2 1111 0001 0010 è ñîîòâåòñòâóþùèå êîîðäèíàòàì ñëîâà p1 1100 1111 � � �� , p2 0101 0001 � � �� , p3 0000 0010 � � �� , à ðåçóëüòàò ïðåäñòàâëÿåòñÿ ñîñòîÿíèåì (1, 1, 2). Ýòî çíà÷èò, ÷òî âåêòîðû �1 è a íå ñðàâíèìû. Äëÿ � 2 è a èìååì � 2 1 0011 0100 1110 1100 1111 � � � � � � � � � � � � �� p , p2 0100 0001 � � �� , p3 1110 0010 � � �� è ðåçóëüòàò — ñîñòîÿíèå (1, 1, 2); ñëåäîâàòåëüíî, � 2 è a òàêæå íå ñðàâíèìû. Äëÿ � 3 è a èìååì � 3 1 0000 1111 0001 0000 1111 � � � � � � � � � � � � �� p , p2 1111 0001 � � �� , p3 0001 0010 � � �� è ðåçóëüòàò — ñîñòîÿíèå (1, 2, 1); ýòî çíà÷èò, ÷òî � 3 è a íå ñðàâíèìû. Äëÿ � 4 è a èìååì � 4 1 0001 0001 0010 0001 1111 � � � � � � � � � � � � �� p , p2 0001 0001 � � �� , p3 0010 0010 � � �� è ðåçóëüòàò — ýòî (1, 0, 0), ÷òî îçíà÷àåò a � � 4 . Êîíåö ïðèìåðà 3. 140 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 1 2 0 0 1 3 1 0 0 1 0 1 1 0 1 1 0 0 1 0 0110 0101 0110 0101 01 01 01 01 a0 Ðèñ. 3. Àâòîìàò B1 0/0 1/1 1/0 0/1 0 1 Ðèñ. 2. Àâòîìàò C äëÿ âû÷èñëåíèÿ 2-äîïîë- íåíèÿ Ïðåäëîæåíèå 3. Àâòîìàò B1 ïðàâèëüíî âû÷èñëÿåò îòíîøåíèå x y� ìåæäó äâóìÿ öåëûìè ÷èñëàìè x è y, ïðåäñòàâëåííûìè â äâîè÷íîé ñèñòåìå ñ÷èñëåíèÿ â âèäå 2-äîïîëíåíèÿ. Äîêàçàòåëüñòâî î÷åâèäíûì îáðàçîì ñëåäóåò èç ïðåäëîæåíèÿ 1. Äåéñòâèòåëüíî, àâòîìàò B1 ïðè ïåðåõîäå èç íà÷àëüíîãî ñîñòîÿíèÿ a0 ðàñïîçíàåò çíàê è ïåðåõîäèò â ñîñòîÿíèå 0, åñëè ÷èñëà ïîëîæèòåëüíûå, è äàëåå ðàáîòàåò êàê àâòîìàò A1. Åñëè ÷èñëà îòðèöàòåëüíûå, òî àâòîìàò B1 ïåðåõîäèò â ñîñòîÿíèå 3 è äàëåå ðàáîòàåò êàê àâòîìàò A1, òîëüêî ïåðåõîäû èç ñîñòîÿíèÿ 3 â ñîñòîÿíèå 1 èëè 2 àñèììåòðè÷íû ïå- ðåõîäàì àâòîìàòà A1 èç ñîñòîÿíèÿ 0 â ñîñòîÿíèå 1 èëè 2. Åñëè çíàêè ðàçíûå, òî àâ- òîìàò B1 ïåðåõîäèò ñðàçó ëèáî â ñîñòîÿíèå 1 (ñëó÷àé x y ), ëèáî â ñîñòîÿíèå 2 (ñëó÷àé x y� ). Àâòîìàò B1 â ïðîöåññå ñðàâíåíèÿ, ïîïàäàÿ â ñîñòîÿíèå 1 (èëè 2), èç íåãî óæå íå âûõîäÿò. Ýòî çíà÷èò, ÷òî ñðàâíåíèå âûïîëíÿåòñÿ îäíîçíà÷íî. Êîíåö äîêàçàòåëüñòâà. Ñðàâíåíèå âåêòîðîâ ðàçìåðíîñòè n âûïîëíÿåòñÿ îäíîðîäíîé ñåòüþ èç àâòî- ìàòîâ B1. Òåîðåìà 1. Ñåòè A è B ïðàâèëüíî âûïîëíÿþò ðàçáèåíèå ìíîæåñòâà âåêòî- ðîâ îòíîñèòåëüíî ïîêîîðäèíàòíîãî è ëåêñèêîãðàôè÷åñêîãî ïîðÿäêîâ è ïîðîãî- âîãî âåêòîðà. Äîêàçàòåëüñòâî ñëåäóåò èç ïðåäëîæåíèé 1–3. Êîððåêòíîñòü ôóíêöèîíèðîâàíèÿ îäíîðîäíîé ñåòè B äëÿ ëåêñèêîãðàôè÷åñêîãî ïîðÿäêà èëëþñòðèðóåòñÿ òàêæå ðåçóëüòàòàìè òåñòèðîâàíèÿ, ïðèâåäåííûìè â òàáë. 1. ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 141 Ò à á ë è ö à 1 . Ðåçóëüòàòû ñðàâíåíèÿ âåêòîðîâ A è B , ïðåäñòàâëåííûõ â ïðÿ- ìîì è äîïîëíèòåëüíîì êîäàõ Ïðÿìîé äâîè÷íûé êîä Äîïîëíèòåëüíûé äâîè÷íûé êîä Äâîè÷íûé âåêòîð A j Äâîè÷íûé âåêòîð Bi Ðåçóëüòàò ñðàâíåíèÿ Äâîè÷íûé âåêòîð A j Äâîè÷íûé âåêòîð Bi Ðåçóëüòàò ñðàâíåíèÿ A1 000 0� �( ) B1 000 0� �( ) A B� (Equal) A1 000 0� �( ) B1 000 0� �( ) A B� (Equal) B2 010 2� �( ) B A (More) B2 010 2� �( ) B A (More) B3 111 3� �( ) B A� (Less) B3 101 3� �( ) B A� (Less) B4 110 2� �( ) B A� (Less) B4 110 2� �( ) B A� (Less) B5 101 1� �( ) B A� (Less) B5 111 1� �( ) B A� (Less) A2 001 1� �( ) B1 000 0� �( ) B A� (Less) A2 001 1� �( ) B1 000 0� �( ) B A� (Less) B2 010 2� �( ) B A (More) B2 010 2� �( ) B A (More) B3 111 3� �( ) B A� (Less) B3 101 3� �( ) B A� (Less) B4 110 2� �( ) B A� (Less) B4 110 2� �( ) B A� (Less) B5 101 1� �( ) B A� (Less) B5 111 1� �( ) B A� (Less) A3 011 3� �( ) B1 000 0� �( ) B A� (Less) A3 011 3� �( ) B1 000 0� �( ) B A� (Less) B2 010 2� �( ) B A� (Less) B2 010 2� �( ) B A� (Less) B3 111 3� �( ) B A� (Less) B3 101 3� �( ) B A� (Less) B4 110 2� �( ) B A� (Less) B4 110 2� �( ) B A� (Less) B5 101 1� �( ) B A� (Less) B5 111 1� �( ) B A� (Less) A4 110 2� �( ) B1 000 0� �( ) B A (More) A4 110 2� �( ) B1 000 0� �( ) B A (More) B2 010 2� �( ) B A (More) B2 010 2� �( ) B A (More) B3 111 3� �( ) B A� (Less) B3 101 3� �( ) B A� (Less) B4 110 2� �( ) A B� (Equal) B4 110 2� �( ) A B� (Equal) B5 101 1� �( ) B A (More) B5 111 1� �( ) B A (More) ÐÅÀËÈÇÀÖÈß ÑÐÀÂÍÅÍÈß ÄÂÓÕ ÂÅÊÒÎÐÎÂ ÍÀ ÎÑÍÎÂÅ ËÎÃÈ×ÅÑÊÈÕ ÑÒÐÓÊÒÓÐ Ïîñêîëüêó ðåøåíèå çàäà÷è êëàññèôèêàöèè âûïîëíÿåòñÿ îäíîðîäíîé ñåòüþ àâ- òîìàòîâ, äîñòàòî÷íî ðåàëèçîâàòü íà îñíîâå ëîãè÷åñêîé ñòðóêòóðû òîëüêî îïå- ðàöèè ñðàâíåíèÿ äâóõ âåêòîðîâ, ò.å. òîëüêî àâòîìàòîâ A1 è B1. Äëÿ ïðîèçâîëü- íîãî âåêòîðà � �V ðàçìåðíîñòè n N� è ôèêñèðîâàííîãî ïîðîãîâîãî âåêòîðà a, ãäå �, a Z n� , à Z — ìíîæåñòâî öåëûõ ÷èñåë, íåîáõîäèìî ñôîðìèðîâàòü ðå- çóëüòàòû ñðàâíåíèÿ: � � a (Less); � a (More) è � � a (Equal). Ïóñòü A è B ( A a� , B � �) — äâîè÷íûå âåêòîðû ðàçìåðíîñòè n, ïðåäñòàâëåí- íûå ñëåäóþùèì îáðàçîì: A a a a an n n� � �1 2 0... , B b b b bn n n� � �1 2 0... , ãäå a bn n, — çíàêîâûå ðàçðÿäû A è B . Áëîê-ñõåìà àëãîðèòìà ñðàâíåíèÿ äâîè÷íûõ âåêòîðîâ (â ïðÿìûõ êîäàõ) ïðåäñòàâëåíà íà ðèñ. 4. Îòñþäà ìîæíî âèäåòü ðåçóëüòàò ñðàâ- íåíèÿ äâóõ âåêòîðîâ. Ïðèìåð 4. Ïóñòü A è B — ìíîæåñòâà âåêòîðîâ, èìåþùèõ äâîè÷íîå ïðåä- ñòàâëåíèå ñâîèõ êîîðäèíàò, ò.å. a a a a a An n n� �� 1 2 0... , b b b b b Bn n n� �� 1 2 0... , ãäå an , bn — çíàêîâûå ðàçðÿäû a è b. Äëÿ ñëó÷àÿ n � 3 ïóñòü A A A A A� � � � �{ }1 2 3 4000 001 011 110; ; ; , B B B B B B� � � � � �{ }1 2 3 4 5000 010 111 110 101; ; ; ; . Íàéòè ðàçáèåíèå âåêòîðîâ èç ìíîæåñòâà B îòíîñèòåëüíî ëåêñèêîãðàôè÷åñ- êîãî ïîðÿäêà è ñîîòâåòñòâóþùèõ ïîðîãîâûõ âåêòîðîâ èç ìíîæåñòâà A äëÿ îòíî- øåíèÿ R � � �{ }, , . 142 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 Ðèñ. 5. Âðåìåííàÿ äèàãðàììà àëãîðèòìà ñðàâíåíèÿ äâîè÷íûõ ÷èñåë ñî çíàêîì â ïðÿìîì êîäå ÍÀ×ÀËÎ 1 0 0 ÊÎÍÅÖ 0 1 01 0 0 1 1 0 1 1 0 0 1 Ðèñ. 4. Áëîê-ñõåìà àëãîðèòìà ñðàâíåíèÿ äâîè÷íûõ ÷èñåë ñî çíàêîì i n:� �i ia��i � 1 i i:� � 1 �i � 1 �i � 1�i ia� i � 0 i i:� � 1 �i ia� �i � 1i � 0 Equal : B A� More : B A Less : B A� Ðàññìîòðèì òåïåðü ðåàëèçàöèþ àëãîðèòìà ñðàâíåíèÿ (÷èñëà ïðåäñòàâëåíû â ïðÿìûõ êîäàõ) íà îñíîâå êðèñòàëëîâ FPGA ñ èñïîëüçîâàíèåì ÑÀÏÐ ñ ïîñëåäóþ- ùèì ìîäåëèðîâàíèåì â ñðåäå ModelSim. Ðåçóëüòàòû ìîäåëèðîâàíèÿ (âðåìåííàÿ äèàãðàììà, ïðåäñòàâëåííàÿ íà ðèñ. 5) ïîäòâåðæäàþò ïðàâèëüíîñòü ôóíêöèîíèðî- âàíèÿ ñòðóêòóðû ñðàâíåíèÿ ÷èñåë ñî çíàêîì è èìåþò ñëåäóþùèå îáîçíà÷åíèÿ: A h1 000 3 0� � � , A h2 001 3 1� � � , A h3 011 3 3� � � , A h4 110 3 6� � � ; B h1 000 3 0� � � , B h2 010 3 2� � � , B h3 111 3 7� � � , B h4 110 3 6� � � , B h5 101 3 5� � � . Ðàññìîòðåííûé ïðèìåð ðåàëèçàöèè àëãîðèòìà ñðàâíåíèÿ äâóõðàçðÿäíûõ ÷èñåë ñî çíàêîì ïî ðåçóëüòàòàì ìîäåëèðîâàíèÿ âûïîëíÿåòñÿ â êðèñòàëëå FPGA çà åäèíè- öû íàíîñåêóíä. Ïðè ðàñøèðåíèè ðàçðÿäíîñòè ÷èñåë âðåìÿ âûïîëíåíèÿ îïåðàöèè ïðàêòè÷åñêè íå èçìåíÿåòñÿ, ïîñêîëüêó ðåàëèçàöèÿ ïðåäïîëàãàåò ïàðàëëåëüíîå ïî- ðàçðÿäíîå ñðàâíåíèå. Êîíåö ïðèìåðà 4. ÐÅÀËÈÇÀÖÈß ÎÏÅÐÀÖÈÉ Â ÒÐÅÕÇÍÀ×ÍÎÉ ËÎÃÈÊÅ Ðàññìîòðèì ìåòîä ïðîâåðêè âûïîëíèìîñòè ôîðìóë òðåõçíà÷íîé ëîãèêè Ëóêàñå- âè÷à [16], êîòîðûé ïðèìåíèì òàêæå äëÿ òðåõçíà÷íîé ëîãèêè Êëèíè è äëÿ òðåõ- çíà÷íîé ëîãèêè Áî÷âàðà, à òàêæå äëÿ ëþáîé k-çíà÷íîé ëîãèêè. Âîçìîæíîñòü ïðè- ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 143 Ò à á ë è ö à 2 . Çíà÷åíèÿ èñòèííîñòè ëîãè÷åñêèõ ôóíêöèé äëÿ òðîè÷íîé ëîãèêè A x� B y� min ( , )x y ñîîòâåòñòâóåò A B� max ( , )x y ñîîòâåòñòâóåò A B� min ( , )1 1 � �x y ñîîòâåòñòâóåò A B� ( – )1 x ñîîòâåòñòâóåò A 1 1 1 1 1 0 1 1 2/ 1 2/ 1 1 2/ 0 1 0 0 1 0 0 1 2/ 1 1 2/ 1 1 1 2/ 1 2/ 1 2/ 1 2/ 1 2/ 1 1 2/ 1 2/ 0 0 1 2/ 1 2/ 1 2/ 0 1 0 1 1 1 0 1 2/ 0 1 2/ 1 1 0 0 0 0 1 1 Ò à á ë è ö à 3 . Ìîäåëèðîâàíèå çíà÷åíèé èñòèííîñòè ëîãè÷åñêèõ ôóíêöèé äëÿ òðîè÷íîé ëîãèêè A x� B y� min ( , )x y ñîîòâåòñòâóåò A B� max ( , )x y ñîîòâåòñòâóåò A B� min ( , )1 1 � �x y ñîîòâåòñòâóåò A B� ( – )1 x ñîîòâåòñòâóåò A 10 10 10 10 10 00 10 01 01 10 01 00 10 00 00 10 00 00 01 10 01 10 10 01 01 01 01 01 10 01 01 00 00 01 01 01 00 10 00 10 10 10 00 01 00 01 10 10 00 00 00 00 10 10 ìåíåíèÿ îïèñàííîãî ìåòîäà ñòðîèòñÿ íà ìîäåëèðîâàíèè îïåðàöèé òðåõçíà÷íîé ëîãèêè ñ ïîìîùüþ äâóçíà÷íîé ëîãèêè. Ïðåäñòàâèì òàáëèöó îïåðàöèé òðåõçíà÷- íîé ëîãèêè Ëóêàñåâè÷à, â êîòîðîé èñïîëüçóþòñÿ çíà÷åíèÿ 1, 1/2, 0 (òàáë. 2), è òàáëèöó ìîäåëèðîâàíèÿ ýòèõ îïåðàöèé äâóçíà÷íîé ëîãèêîé (òàáë. 3). Äëÿ ñîîòâåòñòâèÿ ñ äâóçíà÷íîé ëîãèêîé ïðèìåíÿåòñÿ òàêîå êîäèðîâàíèå çíà- ÷åíèé òðåõçíà÷íîé ëîãèêè: 1 10� , 1 2 01/ � è 0 00� . Ïîñêîëüêó äëÿ êîäèðîâàíèÿ çíà÷åíèé òðåõçíà÷íîé ëîãèêè èñïîëüçóþòñÿ äâà áèòà, òî âûõîäíûå çíà÷åíèÿ òàêæå áóäóò äâóõáèòîâûìè. Ïóñòü x x x� 1 0 , y y y� 1 0 , z z z� 1 0 — áèòîâîå ïðåäñòàâëåíèå âõîäíûõ è âûõîäíûõ çíà÷åíèé ïåðå- ìåííûõ. Ïîñòðîèì àëãåáðàè÷åñêèå âûðàæåíèÿ äëÿ ïðåäñòàâëåííûõ ëîãè÷åñêèõ îïåðàöèé ñ ó÷åòîì ïðèíÿòîé êîäèðîâêè: 1) îïåðàöèÿ A B� : z x x y y y y x x y y0 1 0 1 0 1 0 0 1 1 0� � �( ) , z x x y y1 0 1 1 0� , ñõåìà ðåàëèçàöèè ýòîé îïåðàöèè ïðåäñòàâëåíà íà ðèñ. 6; 144 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 AND AND AND AND AND OR AND AND OR Ðèñ. 6. Ñõåìà ðåàëèçàöèè îïåðàöèè A B� x1 x0 y1 y0 z1 z0 x x0 1 x x1 0 y y0 1 y y1 0 AND AND ANDOR OR OR AND AND AND AND Ðèñ. 7. Ñõåìà ðåàëèçàöèè îïåðàöèè A B� x1 x0 y1 y0 z1 z0 x y1 1 x y0 0 2) îïåðàöèÿ A B� : z x y x x y0 1 1 0 0 0� �( ), z x y y x x y y y1 1 1 0 0 1 1 0 1� � �( ) , ñõåìà ðåàëèçàöèè ýòîé îïåðàöèè ïðåäñòàâëåíà íà ðèñ. 7; 3) îïåðàöèÿ A B� : z y x x y x x y0 1 1 0 0 1 0 0� �( ), z y y x x x x y x x y1 1 0 1 0 1 1 1 0 0 0� � � �( ) ( ) ñõåìà ðåàëèçàöèè ýòîé îïåðàöèè ïðåäñòàâëåíà íà ðèñ. 8; 4) îïåðàöèÿ A : z x x0 1 0� , z x x1 0 1� ; ñõåìà ðåàëèçàöèè ýòîé îïåðàöèè ïðåäñòàâëåíà íà ðèñ. 9. Ðàññìîòðèì òåïåðü ðåàëèçàöèþ îïåðàöèé òðåõçíà÷íîé ëîãèêè (ñîîòâåòñòâóåò òàáë. 3) íà îñíîâå êðèñòàëëîâ FPGA ñ èñïîëüçîâàíèåì ÑÀÏÐ ñ ïîñëåäóþùèì ìîäå- ëèðîâàíèåì â ñðåäå ModelSim. Ðåçóëüòàòû ìîäåëèðîâàíèÿ (âðåìåííàÿ äèàãðàììà, ïðåäñòàâëåííàÿ íà ðèñ. 10) ïîäòâåðæ- äàþò ïðàâèëüíîñòü ôóíêöèîíèðîâàíèÿ ñòðóêòóð òðåõçíà÷íîé ëîãèêè. Èñïîëü- çîâàíû ñëåäóþùèå îáîçíà÷åíèÿ: Zand, Zor, AsB, invA ñîîòâåòñòâóþò ëîãè÷åñ- êèì îïåðàöèÿì A B� , A B� , A B� , A , à ñîñòîÿíèÿ �2 0h , �2 1h , �2 2h ñîîòâåò- ñòâóþò çíà÷åíèÿì òðåõçíà÷íîé ëîãèêè â êîäèðîâêå 0 00� , 1 2 01/ � , 1 10� ; �2 3h — çàïðåùåííîå ñîñòîÿíèå. ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 145 AND AND AND OR AND AND AND AND OR OR AND AND AND AND OR Ðèñ. 8. Ñõåìà ðåàëèçàöèè îïåðàöèè A B� x1 x0 y1 y0 z1 z0 y x1 1 x x0 1 x x1 0 y y0 1 y y1 0 y y1 0 x y0 0 AND AND Ðèñ. 9. Ñõåìà ðåàëèçàöèè îïåðàöèè A x0 x1 z0 z1 x x0 1 x x1 0 Òåîðåìà 2. Ïðèâåäåííàÿ ðåàëèçàöèÿ ëîãè÷åñêèõ îïåðàöèé äëÿ òðåõçíà÷íîé ëîãèêè êîððåêòíà, ò.å. ïðàâèëüíî âû÷èñëÿþòñÿ çíà÷åíèÿ ýòèõ îïåðàöèé. Äîêàçàòåëüñòâî ñâîäèòñÿ ê ðàññìîòðåíèþ ïðàâèëüíîñòè ðåàëèçàöèè êàæäîé îïåðàöèè. Ïðèâåäåì äîêàçàòåëüñòâî òîëüêî äëÿ ñëó÷àÿ îïåðàöèè êîíúþíêöèè è äèçúþíêöèè, ïîñêîëüêó äëÿ îñòàëüíûõ îïåðàöèé îíî âûïîëíÿåòñÿ àíàëîãè÷íî. Îïåðàöèè A B� ñîãëàñíî òàáëèöå êîäèðîâàíèÿ ñîîòâåòñòâóåò ÄÍÔ âèäà z x x y y x x y y x x y y0 0 1 1 0 1 0 1 0 1 0 1 0� � � , êîòîðàÿ ïðåîáðàçîâûâàåòñÿ ê òàêîìó îêîí- ÷àòåëüíîìó âûðàæåíèþ: z x x y y y y x x y y0 1 0 1 0 1 0 0 1 1 0� � �( ) , à äëÿ z x x y y1 0 1 1 0� íèêàêèõ ïðåîáðàçîâàíèé íå òðåáóåòñÿ. Èìåííî ýòè âûðàæåíèÿ ðåàëèçóþòñÿ ñõå- ìîé äëÿ A B� . Îïåðàöèè A B� ñîãëàñíî òàáëèöå êîäèðîâàíèÿ ñîîòâåòñòâóåò ÄÍÔ âèäà z x x y y x x y y y y x x0 1 0 0 1 1 0 0 1 1 0 0 1� � � , êîòîðàÿ ïðåîáðàçîâûâàåòñÿ ê òàêîìó îêîí÷àòåëüíîìó âûðàæåíèþ: z x y x x y0 1 1 0 0 0� �( ), à äëÿ z1 ÄÍÔ èìååì âèä z x x y y x x y y x x y y y y x x y y x x1 0 1 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 0 1 0� � � � � , êîòîðàÿ ïðåîáðàçî- âûâàåòñÿ ê òàêîìó îêîí÷àòåëüíîìó âûðàæåíèþ: z x y y x x y y y1 1 1 0 0 1 1 0 1� � �( ). Èìåííî ýòè âûðàæåíèÿ ðåàëèçóþòñÿ ñõåìîé äëÿ A B� . Êîíåö äîêàçàòåëüñòâà. Ïðèìåð 5. Âû÷èñëèì çíà÷åíèå ôîðìóëû òðåõçíà÷íîé ëîãèêè Ëóêàñåâè÷à âèäà F � � � � ��(( ) ( )) .A B C D B Äëÿ âû÷èñëåíèÿ çíà÷åíèÿ ýòîé ôîðìóëû ñèíòåçèðóåòñÿ ñåòü ïî ñòðóêòóðå ôîðìóëû F . Ñèíòåçèðîâàííàÿ ñåòü ïðèíèìàåò âèä S S S S S1 2 3 1 4( ( ( , ), ( , )), ( ))A B C D B , ãäå S1, S 2 , S 3 , S 4 — ñõåìû ðåàëèçàöèè ôóíêöèé êîíúþíêöèè, äèçúþíêöèè, èìïëèêàöèè è îòðèöàíèÿ ñîîòâåòñòâåííî. Òàê, ïóñòü çàäàíû âõîäíûå çíà÷åíèÿ ïåðåìåííûõ: A �1, B � 0, C �1 2/ , D � 0, òîãäà íà âûõîäå ïîëó÷àåì òàêîå çíà- ÷åíèå ôîðìóëû F : S 3 10 00 00( , ) � , S1 01 00 00( , ) � , S 4 00 10( ) � , S S S S S S S S1 2 3 1 4 1 2 410 00 01 00 00 00 00( ( ( , ), ( , )), ( )) ( ( , ),� ( )) ( , )00 00 10 001� �S . Òàêèì îáðàçîì, çíà÷åíèå ôîðìóëû ðàâíî íóëþ, ÷òî ñîîòâåòñòâóåò çíà÷å- íèþ, âû÷èñëåííîìó ïî òàáë. 2. Äëÿ çíà÷åíèé A �1, B �1, C �1 2/ , D �1 2/ ïîëó÷à- åì ñëåäóþùåå çíà÷åíèå ôîðìóëû F : S 3 10 10 10( , ) � , S1 01 01 01( , ) � , S 4 10 00( ) � , S S S S S S S S1 2 3 1 4 1 2 410 10 01 01 10 10 01( ( ( , ), ( , )), ( )) ( ( , ),� ( )) ( , )10 10 00 001� �S . 146 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 Ðèñ. 10. Âðåìåííàÿ äèàãðàììà ôóíêöèîíèðîâàíèÿ îïåðàöèé òðåõçíà÷íîé ëîãèêè Êîíåö ïðèìåðà 5. Èç ïðèìåðà 5 ñëåäóåò, ÷òî äàííûé ïîäõîä ïîçâîëÿåò ïî ñòðóêòóðå çàäàííîé ôîðìóëû òðåõçíà÷íîé ëîãèêè ñèíòåçèðîâàòü ñåòü, ñ ïîìîùüþ êîòîðîé ìîæíî ïðîâåðÿòü âûïîëíèìîñòü äàííîé ôîðìóëû äëÿ çíà÷åíèé âõîäíûõ ïåðåìåííûõ. ÇÀÊËÞ×ÅÍÈÅ Â íàñòîÿùåé ñòàòüå ðàññìîòðåíî ðåøåíèå çàäà÷è ðàçáèåíèÿ ìíîæåñòâà âåêòî- ðîâ ñ öåëûìè êîîðäèíàòàìè îòíîñèòåëüíî ïîêîîðäèíàòíîãî è ëåêñèêîãðàôè- ÷åñêîãî ïîðÿäêîâ íà âåêòîðàõ. Ïðè ýòîì èñïîëüçîâàëàñü àâòîìàòíàÿ èíòåðïðå- òàöèÿ çàäà÷è ðàçáèåíèÿ, êîòîðàÿ ðåøàåò çàäà÷ó â îáùåì âèäå. Ïðèâåäåííîå ðåøåíèå íå çàâèñèò îò ðàçðÿäíîñòè êîîðäèíàò âåêòîðîâ è ïðèìåíèìî ê ïðîèç- âîëüíûì âåëè÷èíàì êîîðäèíàò âåêòîðîâ è ïîðîãîâûì çíà÷åíèÿì. Òàêèì îáðà- çîì, îáîáùàþòñÿ ñïîñîáû ðåøåíèÿ çàäà÷ ðàçáèåíèÿ, êîòîðûå ðàññìàòðèâàëèñü â ðàáîòå [1]. Êîððåêòíîñòü ïðåäëîæåííîãî ðåøåíèÿ äîêàçàíà è ïîäòâåðæäåíà àïïàðàòíîé ðåàëèçàöèåé íà êðèñòàëëàõ FPGA è ñîîòâåòñòâóþùèì ìîäåëèðîâà- íèåì ñ ïîëó÷åíèåì âðåìåííûõ äèàãðàìì. Ýòè ìåòîäû ïðèìåíÿþòñÿ äëÿ ïðî- âåðêè âûïîëíèìîñòè ôîðìóë òðåõçíà÷íîé ëîãèêè. Ñîîòâåòñòâóþùàÿ ëîãè÷åñ- êàÿ ñåòü ñèíòåçèðóåòñÿ ïî ñòðóêòóðå ôîðìóëû. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Kryvyi S.L., Opanasenko V.N. Partitioning a set of vectors with nonnegative integer coordinates using logical hardware. Cybernetics and Systems Analysis. 2018, Vol. 54, N 2. P. 310–319. 2. Krivoi S. A criteria of compatibility systems of linear diophantine constraints. Lecture Notes in Computer Science. 2002. Vol. 2328. P. 264–271. 3. Kryvyi S.L. Algorithms for solving systems of linear Diophantine equations in residue fields. Cybernetics and Systems Analysis. 2007. Vol. 43, N 2. P. 3–17. 4. Palagin A.V., Opanasenko V.N. Reconfigurable computing technology. Cybernetics and Systems Analysis. 2007. Vol. 43, N 5. P. 675–686. 5. Palagin A.V., Opanasenko V.N. Design and application of the PLD-based reconfigurable devices. In: Design of Digital Systems and Devices. Lecture Notes in Electrical Engineering. Adamski M., Barkalov A., Wegrzyn M. (Eds.). Berlin; Heidelberg: Springer-Verlag, 2011. Vol. 79. P. 59–91. 6. Opanasenko V., Kryvyi S. Synthesis of multilevel structures with multiple outputs. CEUR Workshop Proceeding of 10th International Conference of Programming, UkrPROG 2016, Kyiv, Ukraine. 2016. Vol. 1631, Code 122904. P. 32–37. 7. Kondratenko Y.P., Gordienko E. Implementation of the neural networks for adaptive control system on FPGA. In: Annals of DAAAM for 2012 & Proceeding of 23rd DAAAM International Symposium on Intelligent Manufacturing and Automation. Katalinic B. (Ed.). Vienna, Austria, 2012. Vol. 23, N 1. P. 0389–0392. 8. Kondratenko Y., Kondratenko V. Soft computing algorithm for arithmetic multiplication of fuzzy sets based on universal analytic models. In: Information and Communication Technologies in Education, Research, and Industrial Application. Ser. Communications in Computer and Information Science. 2014. Vol. 469. P. 49–77. 9. Palagin A.V., Opanasenko V.N., Kryvyi S.L. Resource and energy optimization oriented development of FPGA-based adaptive logical networks for classification problem. In: Green IT Engineering: Components, Networks and Systems Implementation. Kharchenko V., Kondratenko Y., Kacprzyk J. (Eds.). 2017. Vol. 105. P. 195–218. DOI: DOI 10.1007 978-3-319-55595-9_10. 10. Opanasenko V.N., Kryvyi S.L. Synthesis of neural-like networks on the basis of conversion of cyclic hamming codes. Cybernetics and Systems Analysis. 2017. Vol. 53, N 4. P. 627–635. ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 147 11. Palagin A., Opanasenko V. The implementation of extended arithmetic’s on FPGA-based structures. Proceedings of the 9th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications, IDAACS’2017. (21–23 September 2017, Bucharest, Romania). 2017. Vol. 2. P. 1014–1019. 12. Drozd J., Drozd A., Antoshchuk S., Kushnerov A., Nikul V. Effectiveness of matrix and pipeline FPGA-based arithmetic components of safety-related systems. Proceedings of the 8th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications. Warsaw, Poland, 2015. P. 785–789. 13. Woods R., McAllister J., Lightbody G., Ying Yi. FPGA-based implementation of signal processing systems. Chichester: John Wiley and Sons, 2008. 362 p. 14. Ãëóøêîâ Â.Ì., Ëåòè÷åâñêèé À.À., Ãîäëåâñêèé À.Á. Ìåòîäû ñèíòåçà äèñêðåòíûõ ìîäåëåé áèî- ëîãè÷åñêèõ ñèñòåì. Êèåâ: Âèùà øê., 1983. 262 ñ. 15. Anderson J. Automata theory with modern applications. Cambridge: Cambridge University Press, 2006. 255 p. 16. Ëóêàñåâè÷ ß. Àðèñòîòåëåâñêàÿ ñèëëîãèñòèêà ñ òî÷êè çðåíèÿ ñîâðåìåííîé ôîðìàëüíîé ëîãèêè. Ìîñêâà: Èíîñòðàííàÿ ëèòåðàòóðà, 1959. 312 ñ. Íàä³éøëà äî ðåäàêö³¿ 12.09.2018 Ñ.Ë. Êðèâèé, Â.Ì. Îïàíàñåíêî, Ñ.Á. Çàâ’ÿëîâ ÐÎÇÁÈÒÒß ÌÍÎÆÈÍÈ ÂÅÊÒÎÐ²Â Ç Ö²ËÈÌÈ ÊÎÎÐÄÈÍÀÒÀÌÈ ËÎÃ²ÊÎÂÈÌÈ ÀÏÀÐÀÒÍÈÌÈ ÇÀÑÎÁÀÌÈ Àíîòàö³ÿ. Ðîçãëÿíóòî çàäà÷ó ðîçáèòòÿ ìíîæèíè âåêòîð³â ç ö³ëèìè êîîðäè- íàòàìè â³äíîñíî ïîêîîðäèíàòíîãî ³ ëåêñèêîãðàô³÷íîãî ïîðÿäêó íà âåêòîðàõ ³ç âèêîðèñòàííÿì àâòîìàòíî¿ ³íòåðïðåòàö³¿. Çàïðîïîíîâàíî àïàðàòíó ðåà- ë³çàö³þ îïåðàö³é òðèçíà÷íî¿ ëîã³êè íà áàç³ êðèñòàë³â FPGA äëÿ ïåðåâ³ðêè âèêîíóâàíîñò³ ôîðìóë ö³º¿ ëîã³êè. Êëþ÷îâ³ ñëîâà: ö³ëî÷èñëîâ³ âåêòîðè, ïîðîãîâ³ çíà÷åííÿ, ñê³í÷åíí³ àâòî- ìàòè, òðèçíà÷íà ëîã³êà. S.L. Kryvyi, V.M. Opanasenko, S.B. Zavyalov PARTITIONING OF A SET OF VECTORS WITH INTEGER COORDINATES BY MEANS OF THE LOGICAL HARDWARE Abstract. The problem of partitioning a set of vectors with integer coordinates with respect to the coordinate-wise and lexicographic order on vectors by using an automatic interpretation is considered. The FPGA-based hardware implementation of three-valued logic operations for feasibility verification of the formulas of this logic is proposed. Keywords: vectors with integer items, threshold value, finite automata, three-valued logic. Êðûâûé Ñåðãåé Ëóêüÿíîâè÷, äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð, ïðîôåññîð Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè Òàðàñà Øåâ÷åíêî, Êèåâ, e-mail: sl.krivoi@gmail.com. Îïàíàñåíêî Âëàäèìèð Íèêîëàåâè÷, äîêòîð òåõí. íàóê, ïðîôåññîð, âåäóùèé íàó÷íûé ñîòðóäíèê Èíñòèòóòà êèáåðíåòèêè èì. Â.Ì. Ãëóø- êîâà ÍÀÍ Óêðàèíû, Êèåâ, e-mail: OpanasenkoVM@nas.gov.ua. Çàâüÿëîâ Ñòàíèñëàâ Áîðèñîâè÷, êàíäèäàò òåõí. íàóê, äèðåêòîð ÎÎÎ «Ðàäèîíèêñ», Êèåâ, e-mail: radionix13@gmail.com. 148 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3
id	nasplib_isofts_kiev_ua-123456789-180877
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1019-5262
language	Russian
last_indexed	2025-11-27T11:44:55Z
publishDate	2019
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
record_format	dspace
spelling	Крывый, С.Л. Опанасенко, В.Н. Завьялов, С.Б. 2021-10-23T17:00:22Z 2021-10-23T17:00:22Z 2019 Разбиение множества векторов с целыми координатами логическими аппаратными средствами / С.Л. Крывый, В.Н. Опанасенко, С.Б. Завьялов // Кибернетика и системный анализ. — 2019. — Т. 56, № 3. — С. 136-148. — Бібліогр.: 16 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/180877 516.813 Рассматривается задача разбиения множества векторов с целыми координатами относительно покоординатного и лексикографического порядка на векторах с использованием автоматной интерпретации. Предложена аппаратная реализация операций трехзначной логики на базе кристаллов FPGA для проверки выполнимости формул этой логики. Розглянуто задачу розбиття множини векторів з цілими координатами відносно покоординатного і лексикографічного порядку на векторах із використанням автоматної інтерпретації. Запропоновано апаратну реалізацію операцій тризначної логіки на базі кристалів FPGA для перевірки виконуваності формул цієї логіки. The problem of partitioning a set of vectors with integer coordinates with respect to the coordinate-wise and lexicographic order on vectors by using an automatic interpretation is considered. The FPGA-based hardware implementation of three-valued logic operations for feasibility verification of the formulas of this logic is proposed. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Разбиение множества векторов с целыми координатами логическими аппаратными средствами Розбиття множини векторів з цілими координатами логіковими апаратними засобами Partitioning of a set of vectors with integer coordinates by means of the logical hardware Article published earlier
spellingShingle	Разбиение множества векторов с целыми координатами логическими аппаратными средствами Крывый, С.Л. Опанасенко, В.Н. Завьялов, С.Б. Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу
title	Разбиение множества векторов с целыми координатами логическими аппаратными средствами
title_alt	Розбиття множини векторів з цілими координатами логіковими апаратними засобами Partitioning of a set of vectors with integer coordinates by means of the logical hardware
title_full	Разбиение множества векторов с целыми координатами логическими аппаратными средствами
title_fullStr	Разбиение множества векторов с целыми координатами логическими аппаратными средствами
title_full_unstemmed	Разбиение множества векторов с целыми координатами логическими аппаратными средствами
title_short	Разбиение множества векторов с целыми координатами логическими аппаратными средствами
title_sort	разбиение множества векторов с целыми координатами логическими аппаратными средствами
topic	Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу
topic_facet	Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу
url	https://nasplib.isofts.kiev.ua/handle/123456789/180877
work_keys_str_mv	AT kryvyisl razbieniemnožestvavektorovscelymikoordinatamilogičeskimiapparatnymisredstvami AT opanasenkovn razbieniemnožestvavektorovscelymikoordinatamilogičeskimiapparatnymisredstvami AT zavʹâlovsb razbieniemnožestvavektorovscelymikoordinatamilogičeskimiapparatnymisredstvami AT kryvyisl rozbittâmnožinivektorívzcílimikoordinatamilogíkovimiaparatnimizasobami AT opanasenkovn rozbittâmnožinivektorívzcílimikoordinatamilogíkovimiaparatnimizasobami AT zavʹâlovsb rozbittâmnožinivektorívzcílimikoordinatamilogíkovimiaparatnimizasobami AT kryvyisl partitioningofasetofvectorswithintegercoordinatesbymeansofthelogicalhardware AT opanasenkovn partitioningofasetofvectorswithintegercoordinatesbymeansofthelogicalhardware AT zavʹâlovsb partitioningofasetofvectorswithintegercoordinatesbymeansofthelogicalhardware

Разбиение множества векторов с целыми координатами логическими аппаратными средствами

Institution

Similar Items