Лупал А.М. Теория автоматов (часть 2)

Подождите немного. Документ загружается.

6. ÑÒÐÓÊÒÓÐÍÛÉ ÑÈÍÒÅÇ ÀÂÒÎÌÀÒÎÂ

6.1. Êîìïîçèöèÿ àâòîìàòîâ

Ñòðóêòóðíûé ñèíòåç àâòîìàòîâ îñóùåñòâëÿåòñÿ íà áàçå ñòðóêòóðíîé

òåîðèè àâòîìàòîâ, â êîòîðîé â îòëè÷èå îò àáñòðàêòíîé òåîðèè ïðîèçâî-

äèòñÿ ó÷åò áîëüøîãî ÷èñëà ñâîéñòâ ðåàëüíî ñóùåñòâóþùèõ öèôðîâûõ

àâòîìàòîâ. Àáñòðàêòíûé àâòîìàò ïðåäñòàâëÿåò ñîáîé ìàòåìàòè÷åñêóþ

ìîäåëü ïðîåêòèðóåìîãî óñòðîéñòâà. Â ñòðóêòóðíîì æå àâòîìàòå ó÷èòû-

âàåòñÿ ñòðóêòóðà âõîäíûõ è âûõîäàõ ñèãíàëîâ, à òàêæå âíóòðåííÿÿ ñòðóê-

òóðà àâòîìàòà íà óðîâíå òàê íàçûâàåìûõ ñòðóêòóðíûõ ñõåì. Â ñòðóê-

òóðíîé òåîðèè àâòîìàòîâ ïðèíÿò îòñ÷åò àâòîìàòíîãî âðåìåíè, íà÷èíàÿ

ñ 0 òàêòà, ò. å. t = 0, 1, 2, ...

Ãëàâíîé çàäà÷åé ñòðóêòóðíîé òåîðèè àâòîìàòîâ ÿâëÿåòñÿ íàõîæäå-

íèå îáùèõ ïðèåìîâ ïîñòðîåíèÿ ñòðóêòóðíûõ ñõåì àâòîìàòà íà îñíîâå

êîìïîçèöèè ýëåìåíòàðíûõ àâòîìàòîâ, ïðèíàäëåæàùèõ ê çàðàíåå çàäàí-

íîìó êîíå÷íîìó ÷èñëó òèïîâ. Ðàññìîòðèì, êàê ïðåäñòàâëÿåòñÿ àâòî-

ìàò â ñòðóêòóðíîé òåîðèè àâòîìàòîâ. Ó àáñòðàêòíîãî àâòîìàòà îäèí

âõîäíîé è îäèí âûõîäíîé êàíàëû. Â ñòðóêòóðíîé æå òåîðèè êàê âõîä-

íûå, òàê è âûõîäíûå êàíàëû àâòîìàòà ñ÷èòàþòñÿ ñîñòîÿùèìè èç íå-

ñêîëüêèõ ýëåìåíòàðíûõ âõîäíûõ è ñîîòâåòñòâåííî ýëåìåíòàðíûõ âû-

õîäíûõ êàíàëîâ. Ïî ýòèì êàíàëàì ïåðåäàþòñÿ ýëåìåíòàðíûå ñèãíàëû.

Íàáîð âñåõ âîçìîæíûõ äëÿ äàííîãî àâòîìàòà ýëåìåíòàðíûõ ñèãíàëîâ

íàçûâàåòñÿ ñòðóêòóðíûì àëôàâèòîì äàííîãî àâòîìàòà. Êàæäûé ýëå-

ìåíòàðíûé âõîäíîé êàíàë ïîäñîåäèíåí ê âõîäíîìó óçëó àâòîìàòà, à

êàæäûé ýëåìåíòàðíûé âûõîäíîé êàíàë ê âûõîäíîìó óçëó àâòîìàòà.

Ñôîðìóëèðóåì îïðåäåëåíèå îáùåãî ñïîñîáà êîìïîçèöèè àâòîìà-

òîâ. Ïóñòü {A

, A

, ..., A

}(n ≥ 0)  êîíå÷íîå ìíîæåñòâî àâòîìàòîâ.

Íåîáõîäèìî ïðîèçâåñòè îáúåäèíåíèå ýòèõ àâòîìàòîâ â ñèñòåìó ñîâìå-

ñòíî ðàáîòàþùèõ àâòîìàòîâ. Ââåäåì íåêîòîðîå êîíå÷íîå ìíîæåñòâî

óçëîâ, êîòîðûå íàçîâåì âíåøíèìè âõîäíûìè óçëàìè, è íåêîòîðîå êî-

íå÷íîå ìíîæåñòâî äðóãèõ óçëîâ, êîòîðûå íàçîâåì âíåøíèìè âûõîäíû-

ìè óçëàìè. Âõîäíûå è âûõîäíûå óçëû àâòîìàòîâ A

, A

, ..., A

áóäåì

íàçûâàòü âíóòðåííèìè âõîäíûìè è âûõîäíûìè óçëàìè.

Êîìïîçèöèÿ àâòîìàòîâ ñîñòîèò â òîì, ÷òî â ïîëó÷åííîé ñèñòåìå,

ñîñòîÿùåé èç çàäàííûõ àâòîìàòîâ A

, A

, ..., A

è âíåøíèõ óçëîâ, ïðîèç-

âîäèòñÿ îòîæäåñòâëåíèå íåêîòîðûõ óçëîâ (êàê âíåøíèõ, òàê è âíóòðåí-

íèõ). Ó öèôðîâûõ àâòîìàòîâ îïåðàöèè îòîæäåñòâëåíèÿ óçëîâ ñîîòâåò-

ñòâóåò ñîåäèíåíèå ýòèõ óçëîâ ïðîâîäíèêàìè.

Ïîñëå ïðîâåäåíèÿ îòîæäåñòâëåíèÿ óçëîâ ïðîèçâîëüíàÿ ñèñòåìà àâ-

òîìàòîâ ïðåâðàùàåòñÿ â òàê íàçûâàåìóþ ñõåìó èëè ñåòü àâòîìàòîâ.

Áóäåì ñ÷èòàòü, ÷òî àâòîìàòû, âõîäÿùèå â ñõåìó, ðàáîòàþò ñîâìåñòíî,

åñëè â êàæäûé ìîìåíò t àâòîìàòíîãî âðåìåíè (t = 0, 1, 2, ...) íà âñå

âíåøíèå âõîäíûå óçëû ñõåìû ïîäàåòñÿ êàêîé-ëèáî íàáîð ýëåìåíòàð-

íûõ ñèãíàëîâ (ñòðóêòóðíûé âõîäíîé ñèãíàë), à ñî âñåõ âíåøíèõ âûõîä-

íûõ óçëîâ ñõåìû ñíèìàåòñÿ ïîëó÷åííûé íà íèõ íàáîð ýëåìåíòàðíûõ

âûõîäíûõ ñèãíàëàõ (ñòðóêòóðíûé âûõîäíîé ñèãíàë). Åñëè â êàæäûé ìî-

ìåíò äèñêðåòíîãî âðåìåíè t = 0, 1, 2,... ñòðóêòóðíûé âûõîäíîé ñèãíàë

ñõåìû îäíîçíà÷íî îïðåäåëÿåòñÿ ïîñòóïèâøåé ê ýòîìó âðåìåíè êîíå÷-

íîé ïîñëåäîâàòåëüíîñòüþ ñòðóêòóðíûõ âõîäíûõ ñèãíàëîâ, íà÷àëüíûìè

ñîñòîÿíèÿìè, âõîäÿùèõ â ñõåìó àâòîìàòîâ, è ñäåëàííûìè ïðè ïîñòðîå-

íèè ñõåìû îòîæäåñòâëåíèÿìè (ñîåäèíåíèÿìè) óçëîâ, òî ïîñòðîåííàÿ

ñõåìà ìîæåò ðàññìàòðèâàòüñÿ êàê íåêîòîðûé àâòîìàò À è íàçûâàåòñÿ

ñòðóêòóðíîé ñõåìîé ýòîãî àâòîìàòà. Àâòîìàò À, ïîëó÷åííûé îïèñàí-

íûì ñïîñîáîì, åñòü ðåçóëüòàò êîìïîçèöèè àâòîìàòîâ A

, A

, ..., A

Ñëåäóåò çàìåòèòü, ÷òî îïåðàöèÿ îòîæäåñòâëåíèÿ óçëîâ ìîæåò áûòü

âûïîëíåíà íåîäíîçíà÷íî. Ïðè îòîæäåñòâëåíèè óçëîâ íåîáõîäèìî ñîáëþ-

äàòü äâà óñëîâèÿ, íàçûâàåìûå óñëîâèÿìè êîððåêòíîñòè ïîñòðîåíèÿ

ñòðóêòóðíûõ ñõåì:

â ëþáîé ìîìåíò àâòîìàòíîãî âðåìåíè íà êàæäûé óçåë ñõåìû (êàê

âíåøíèé, òàê è âíóòðåííèé) ïîñòóïàåò êàêîé-ëèáî ýëåìåíòàðíûé ñèã-

íàë;

íåîäíîçíà÷íîñòü ýëåìåíòàðíûõ ñèãíàëîâ â êàêîì-íèáóäü óçëå ñõå-

ìû õîòÿ áû îäèí ìîìåíò àâòîìàòíîãî âðåìåíè ÿâëÿåòñÿ íåäîïóñòè-

ìîé.

Ïåðâîå óñëîâèå êîððåêòíîñòè óäîâëåòâîðÿåòñÿ â òîì ñëó÷àå, åñëè

ëþáîé óçåë ñõåìû áóäåò ïîäêëþ÷åí ÷åðåç êîíå÷íîå ÷èñëî êîìáèíàöè-

îííûõ ñõåì èëè àâòîìàòîâ Ìèëè ê âíåøíåìó óçëó, ïîñêîëüêó ó àâòîìà-

òîâ Ìèëè è êîìáèíàöèîííûõ ñõåì âûõîäíûå ñèãíàëû âîçíèêàþò îäíî-

âðåìåííî ñ ïîñòóïëåíèåì ñèãíàëîâ íà âõîäû.

Íåîäíîçíà÷íîñòü ýëåìåíòàðíîãî ñèãíàëà â óçëå ìîæåò ïîÿâèòüñÿ ïî

äâóì ïðè÷èíàì: ê íåêîòîðîìó âõîäíîìó óçëó ïîäñîåäèíåíî îäíîâðåìåííî

íåñêîëüêî âûõîäíûõ óçëîâ, ÿâëÿþùèõñÿ èñòî÷íèêàìè ýëåìåíòàðíûõ

ñèãíàëîâ, à òàêæå èñòî÷íèêîì íåîäíîçíà÷íîñòè ìîãóò áûòü òàê íàçû-

âàåìûå öèêëè÷åñêèå öåïè èëè ïåòëè ñòðóêòóðíûõ ñõåì. Öåïüþ íàçûâà-

åòñÿ ïîñëåäîâàòåëüíîñòü àâòîìàòîâ, ó êàæäîãî èç êîòîðûõ îäèí èç âû-

õîäíûõ óçëîâ ñîåäèíåí ñ âõîäîì ïîñëåäóþùåãî. Åñëè âûõîäíîé óçåë

ïîñëåäíåãî àâòîìàòà ñîåäèíåí ñî âõîäíûì óçëîì ïåðâîãî, òî òàêàÿ öåïü

íàçûâàåòñÿ öèêëè÷åñêîé èëè ïåòëåé (ðèñ. 6.1).

Åñëè A

, A

 àâòîìàòû Ìèëè, ó êîòîðûõ âûõîäíîé ñèãíàë

ïîÿâëÿåòñÿ îäíîâðåìåííî ñî âõîäíûì, òî íà âõîäå àâòîìàòà âîçíèêàåò

íåîäíîçíà÷íîñòü ýëåìåíòàðíîãî ñèãíàëà, ïîñêîëüêó íåèçâåñòíî, êàêîé

ñèãíàë ñ÷èòàòü èñòèííûì  âõîäíîé èëè ïîñòóïèâøèé ïî ëèíèè îáðàòíîé

ñâÿçè. Àâòîìàò, ïîñòðîåííûé òàêèì îáðàçîì, íàçûâàåòñÿ íåêîððåêò-

íûì. Íåêîððåêòíîñòè ìîæíî èçáåæàòü, åñëè õîòÿ áû îäèí èç âõîäÿùèõ

â ïåòëþ àâòîìàòîâ áóäåò àâòîìàòîì Ìóðà, êîòîðûé ðåàãèðóåò íà òîò

èëè èíîé âõîäíîé ñèãíàë âûõîäíûì ñèãíàëîì, âîçíèêàþùèì íà îäèí òàêò

àâòîìàòíîãî âðåìåíè ïîçæå, ÷åì âûçûâàâøèé åãî ïîÿâëåíèå âõîäíîé

ñèãíàë. Òàêèì îáðàçîì, äëÿ ñîáëþäåíèÿ âòîðîãî óñëîâèÿ êîððåêòíîñòè

íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû ëþáîé âõîäíîé óçåë ñõåìû ñîåäèíÿë-

ñÿ íå áîëåå, ÷åì ñ îäíèì âíåøíèì âõîäíûì èëè âíóòðåííèì âûõîäíûì

óçëîì ñõåìû, è ëþáàÿ íåòðèâèàëüíàÿ (ñîäåðæàùàÿ íå ìåíåå îäíîãî

àâòîìàòà) ïåòëÿ â ñõåìå ñîäåðæàëà áû â ñâîåì ñîñòàâå õîòÿ áû îäèí

àâòîìàò Ìóðà.

Ñõåìà, â êîòîðîé âûïîëíÿþòñÿ âñå óñëîâèÿ êîððåêòíîñòè, íàçûâàåò-

ñÿ ïðàâèëüíîé.

6.2. Êàíîíè÷åñêèé ìåòîä ñòðóêòóðíîãî ñèíòåçà àâòîìàòîâ

Çàäà÷åé ñòðóêòóðíîãî ñèíòåçà êîíå÷íûõ àâòîìàòîâ ÿâëÿåòñÿ ñîçäà-

íèå òàêîé êîìïîçèöèè íåêîòîðîãî ìíîæåñòâà àâòîìàòîâ, íàçûâàåìûõ

ýëåìåíòàðíûìè, ÷òîáû ïîëó÷åííûé àâòîìàò áûë ýêâèâàëåíòåí çàäàí-

íîìó. Ýòà çàäà÷à èìååò ðåøåíèå, åñëè ñèñòåìà ýëåìåíòàðíûõ àâòîìà-

òîâ ñòðóêòóðíî ïîëíà.

Îäíèì èç øèðîêî èñïîëüçóåìûõ ìåòîäîâ ñòðóêòóðíîãî ñèíòåçà ÿâ-

ëÿåòñÿ òàê íàçûâàåìûé êàíîíè÷åñêèé ìåòîä, òåîðåòè÷åñêèå îñíîâû



Ðèñ. 6.1

êîòîðîãî áûëè ðàçðàáîòàíû Ç.Ì. Ãëóøêîâûì, ñôîðìóëèðîâàâøèì è äî-

êàçàâøèì òåîðåìó î ñòðóêòóðíîé ïîëíîòå [2].

Òåîðåìà: âñÿêàÿ ñèñòåìà ýëåìåíòàðíûõ àâòîìàòîâ, êîòîðàÿ ñîäåð-

æèò àâòîìàò Ìóðà, îáëàäàþùèé ïîëíîé ñèñòåìîé ïåðåõîäîâ è ïîë-

íîé ñèñòåìîé âûõîäîâ, è êàêóþ-íèáóäü ôóíêöèîíàëüíî ïîëíóþ ñèñ-

òåìó ëîãè÷åñêèõ ýëåìåíòîâ (ýëåìåíòàðíûõ àâòîìàòîâ áåç ïàìÿòè),

ÿâëÿåòñÿ ñòðóêòóðíî ïîëíîé ñèñòåìîé. Ñóùåñòâóåò îáùèé êîíñòðóê-

òèâíûé ïðèåì (êàíîíè÷åñêèé ìåòîä ñòðóêòóðíîãî ñèíòåçà), ïîçâî-

ëÿþùèé â ðàññìîòðåííîì ñëó÷àå ñâåñòè çàäà÷ó ñèíòåçà ïðîèçâîëü-

íûõ êîíå÷íûõ àâòîìàòîâ ê çàäà÷å ñòðóêòóðíîãî ñèíòåçà êîìáèíàöè-

îííûõ ñõåì.

Ïîëíîòà ñèñòåìû ïåðåõîäîâ â àâòîìàòå îçíà÷àåò, ÷òî äëÿ ëþáîé

ïàðû ñîñòîÿíèé (a

, a

) ýòîãî àâòîìàòà íàéäåòñÿ âõîäíîé ñèãíàë, ïåðå-

âîäÿùèé îäèí ýëåìåíò ýòîé ïàðû â äðóãîé. Ýòî ïîëîæåíèå ñïðàâåäëèâî,

åñëè i = j. ×òîáû äåòåðìèíèðîâàííûé àâòîìàò ìîã óäîâëåòâîðÿòü óñëî-

âèþ ïîëíîòû ïåðåõîäîâ, ÷èñëî åãî âõîäíûõ ñèãíàëîâ äîëæíî áûòü íå

ìåíüøå ÷èñëà ñîñòîÿíèé.

Ïîëíîòà ñèñòåìû âûõîäîâ â àâòîìàòå Ìóðà îçíà÷àåò, ÷òî êàæäîìó

ñîñòîÿíèþ àâòîìàòà ñîîòâåòñòâóåò ñâîé ñîáñòâåííûì âûõîäíîé ñèã-

íàë, îòëè÷íûé îò âûõîäíîãî ñèãíàëà, ñîîòâåòñòâóþùåãî ëþáîìó äðóãî-

ìó ñîñòîÿíèþ. Ïîýòîìó â àâòîìàòå Ìóðà ñ ïîëíîé ñèñòåìîé âûõîäîâ

ìîæíî îòîæäåñòâèòü âíóòðåííèå ñîñòîÿíèÿ ñ âûõîäíûìè ñèãíàëàìè

àâòîìàòà. Äëÿ òîãî, ÷òîáû îáåñïå÷èòü â ýòîì àâòîìàòå ïîëíîòó ñèñòå-

ìû âûõîäîâ, íåîáõîäèìî â âûõîäíîì àëôàâèòå èìåòü ÷èñëî âûõîäíûõ

ñèãíàëîâ íå ìåíüøå ÷èñëà ñîñòîÿíèé àâòîìàòà.

Íà îñíîâàíèè òåîðåìû î ñòðóêòóðíîé ïîëíîòå ñòðóêòóðíàÿ ñõåìà

âñÿêîãî àâòîìàòà À, ñèíòåçèðîâàííîãî êàíîíè÷åñêèì ìåòîäîì, áó-

äåò ñîñòîÿòü èç äâóõ ÷àñòåé: çàïîìèíàþùåé ÷àñòè è êîìáèíàöèîí-

íîé ñõåìû (ðèñ. 6.2). Çàïîìèíàþùàÿ ÷àñòü ïðåäñòàâëÿåò ñîáîé ñî-

âîêóïíîñòü ýëåìåíòàðíûõ àâòîìàòîâ Ìóðà ñ ïîëíîé ñèñòåìîé ïåðå-

õîäîâ è âûõîäîâ, à êîìáèíàöèîííàÿ

÷àñòü ïðåäñòàâëÿåò ñîáîé ñõåìó, ïîñò-

ðîåííóþ èç ëîãè÷åñêèõ ýëåìåíòîâ, ñî-

ñòàâëÿþùèõ ôóíêöèîíàëüíî ïîëíûé áà-

çèñ. Ðàññìîòðèì ýòàïû ñòðóêòóðíîãî

ñèíòåçà àâòîìàòà êàíîíè÷åñêèì ìåòî-

äîì.

ÊÑ Ïàìÿòü

x(t)

Q(t+1)

q(t)

y(t)

Ðèñ. 6.2

1. Êîäèðîâàíèå ñîñòîÿíèé àáñòðàêòíîãî àâòîìàòà. Â ïðîöåññå ñòðóê-

òóðíîãî ñèíòåçà ðàçëè÷íûì ñîñòîÿíèÿì çàäàííîãî àáñòðàêòíîãî àâòî-

ìàòà a

ñòàâÿòñÿ â ñîîòâåòñòâèå ðàçëè÷íûå óïîðÿäî÷åííûå ïîñëåäîâà-

òåëüíîñòè ñîñòîÿíèé ýëåìåíòàðíûõ àâòîìàòîâ Q

, Q

, ..., Q

. Ýòîò ïðî-

öåññ íàçûâàåòñÿ êîäèðîâàíèåì ñîñòîÿíèé àâòîìàòà.

Ðåçóëüòàòîì êîäèðîâàíèÿ ñîñòîÿíèé ÿâëÿåòñÿ âîçíèêíîâåíèå ñòðóê-

òóðíûõ ñîñòîÿíèé àâòîìàòà Q

= Q

... Q

, ãäå l = 0, 1, 2, ..., M (M+1)

 ÷èñëî ñîñòîÿíèé àáñòðàêòíîãî àâòîìàòà. R = ]log

(M+1)[ è ]b[ îçíà÷à-

åò áëèæàéøåå öåëîå ÷èñëî, áîëüøåå b èëè ðàâíîå åìó, åñëè b  öåëîå.

Ýòè ñîñòîÿíèÿ ìîæíî îòîæäåñòâèòü ñî ñòðóêòóðíûìè âûõîäíûìè ñèã-

íàëàìè çàïîìèíàþùåé ÷àñòè àâòîìàòà.

Â ñâÿçè ñ òåì, ÷òî êàæäûé ñòðóêòóðíûé âûõîäíîé ñèãíàë ïàìÿòè

àâòîìàòà ïðåäñòàâëÿåò ñîáîé ñîâîêóïíîñòü ýëåìåíòàðíûõ ñèãíàëîâ,

ïîñòóïàþùèõ ïî îòäåëüíûì êàíàëàì, áóäåì ñ÷èòàòü ñòðóêòóðíûé âû-

õîäíîé ñèãíàë ïàìÿòè âåêòîðíûì ñèãíàëîì Q

, â êîòîðîì êàæäàÿ

êîìïîíåíòà îòîæäåñòâëÿåòñÿ ñ áóêâîé ñòðóêòóðíîãî àëôàâèòà ñîñòîÿ-

íèÿ Q = {Q

, Q

, ..., Q

}, ò. å. Q

∈ Q.

2. Êîäèðîâàíèå àáñòðàêòíûõ âõîäíûõ è âûõîäíûõ ñèãíàëîâ. Àáñòðàêò-

íûì âõîäíûì è âûõîäíûì ñèãíàëàìè z

∈ Z è w

∈ W, ãäå Z è W  âõîäíîé

è âûõîäíîé àáñòðàêòíûå àëôàâèòû, ñòàâÿòñÿ â ñîîòâåòñòâèå âíåøíèå ñòðóê-

òóðíûå âõîäíûå è âûõîäíûå ñèãíàëû àâòîìàòà, îáîçíà÷àåìûå ñîîòâåò-

ñòâåííî x

= x

... x

, è y

= y

... y

, ãäå j = 1, 2, ..., F, F  ÷èñëî

ñèìâîëîâ âõîäíîãî àáñòðàêòíîãî àëôàâèòà, k = 1, 2, ..., G , G  ÷èñëî

ñèìâîëîâ âûõîäíîãî àáñòðàêòíîãî àëôàâèòà, L = ]log

F[ è N = ]log

G[.

Ñèãíàëû N

è O

ÿâëÿþòñÿ âåêòîðíûìè ñèãíàëàìè, êîìïîíåíòû êîòî-

ðûõ x

è y

 ñîîòâåòñòâåííî ýëåìåíòàðíûå âõîäíûå è âûõîäíûå

ñèãíàëû íà êàæäîì ýëåìåíòàðíîì âõîäíîì èëè âûõîäíîì êàíàëå, ò. å.

∈ X = {x

, x

, ..., x

}, à y

∈ Y = {y

, y

, ..., y

},  ãäå X è Y  ñîîòâåò-

ñòâåííî ñòðóêòóðíûå âõîäíîé è âûõîäíîé àëôàâèòû.

3. Ñîñòàâëåíèå êîäèðîâàííûõ òàáëèö ïåðåõîäîâ-âûõîäîâ ñòðóêòóðíî-

ãî àâòîìàòà. Â ïðîöåññå ñèíòåçà íåîáõîäèìî îáåñïå÷èòü, ÷òîáû ïåðåõî-

äû èç îäíîé ïîñëåäîâàòåëüíîñòè ñîñòîÿíèé ýëåìåíòàðíûõ àâòîìàòîâ â

äðóãóþ ïðîèñõîäèëè â ïîëíîì ñîîòâåòñòâèè ñ ôóíêöèåé ïåðåõîäîâ çà-

äàííîãî àáñòðàêòíîãî àâòîìàòà, à çíà÷åíèÿ ñòðóêòóðíûõ âûõîäíûõ ñèã-

íàëîâ âûðàáàòûâàëèñü â ñîîòâåòñòâèè ñ çàäàííîé ïîñëåäîâàòåëüíîñ-

òüþ àáñòðàêòíûõ âõîäíûõ ñèãíàëîâ. Òàêèì îáðàçîì, äîëæíû áûòü îáåñ-

ïå÷åíû ñëåäóþùèå çàêîíû ôóíêöèîíèðîâàíèÿ äëÿ ñòðóêòóðíîãî àâòî-

ìàòà Ìèëè:

Q(t+1) =δ(Q(t), x(t)),

y(t) = λ(Q(t), x(t)) (6.1)

è äëÿ ñòðóêòóðíîãî àâòîìàòà Ìóðà

Q(t+1) =δ(Q(t), x(t)),

y(t) = λ(Q(t)). (6.2)

Çàêîí ôóíêöèîíèðîâàíèÿ ñòðóêòóðíîãî àâòîìàòà ìîæåò áûòü îïèñàí

ñ ïîìîùüþ êîäèðîâàííûõ òàáëèö ïåðåõîäîâ-âûõîäîâ, êîòîðûå ôîðìè-

ðóþòñÿ íà îñíîâàíèè òàáëèö ïåðåõîäîâ-âûõîäîâ àáñòðàêòíîãî àâòîìà-

òà è ïîëó÷åííûõ íà ïåðâûõ äâóõ ýòàïàõ ñòðóêòóðíûõ çíà÷åíèé ñîñòîÿ-

íèé è ñèãíàëîâ àâòîìàòà. Â êëåòêàõ ýòèõ òàáëèö âìåñòî ñèìâîëîâ, îáî-

çíà÷àþùèõ àáñòðàêòíûå ñîñòîÿíèÿ è ñèãíàëû, çàïèñûâàþòñÿ êîäû ñî-

îòâåòñòâóþùèõ èì ñòðóêòóðíûõ ñîñòîÿíèè è ñèãíàëîâ.

4. Ôîðìèðîâàíèå òàáëèöû ôóíêöèé âîçáóæäåíèÿ ñòðóêòóðíîãî àâòîìà-

òà. Èç ðèñ. 6.2 ñëåäóåò, ÷òî

q(t) = γ(Q(t), x(t)). (6.3)

Ñðàâíèâàÿ âûðàæåíèå (6.3) ñ ôóíêöèåé ïåðåõîäîâ ñòðóêòóðíîãî àâòî-

ìàòà (6.1) èëè (6.2) ìîæíî ñäåëàòü âûâîä, ÷òî èìåííî ñèãíàëîì q(t)

ìîæíî îñóùåñòâèòü òðåáóåìûå ïåðåõîäû ïðè óñëîâèè ôîðìèðîâàíèÿ

íåêîòîðîé ôóíêöèè γ(Q, x), íàçûâàåìîé ôóíêöèåé âîçáóæäåíèÿ àâòîìà-

òà A , â ñîîòâåòñòâèè ñ ôóíêöèåé ïåðåõîäîâ δ(Q, x). Â äàëüíåéøåì äëÿ

óïðîùåíèÿ ôîðìóëèðîâîê ñèãíàë q(t) áóäåì òàêæå íàçûâàòü ôóíêöèåé

âîçáóæäåíèÿ àâòîìàòà A. Îòäåëüíûå êîìïîíåíòû âåêòîðà q(t) ÿâëÿþò-

ñÿ âõîäíûìè ñèãíàëàìè èñïîëüçóåìûõ ýëåìåíòàðíûõ àâòîìàòîâ.

Ôóíêöèè âîçáóæäåíèÿ çàäàþòñÿ î ïîìîùüþ òàáëèöû, ñôîðìèðîâàí-

íîé íà áàçå ñòðóêòóðíîé òàáëèöû ïåðåõîäîâ ïðîåêòèðóåìîãî àâòîìàòà,

è òàáëèöû ïåðåõîäîâ çàäàííîãî ýëåìåíòàðíîãî àâòîìàòà. Â êëåòêàõ

òàáëèöû ôóíêöèé âîçáóæäåíèÿ çàïèñûâàþòñÿ çíà÷åíèÿ ñòðóêòóðíûõ

âõîäíûõ ñèãíàëîâ âûáðàííûõ ýëåìåíòàðíûõ àâòîìàòîâ, îáåñïå÷èâàþ-

ùèå ïåðåõîäû èõ ñîñòîÿíèé â ñîîòâåòñòâèè ñ êîäèðîâàííîé òàáëèöåé

ïåðåõîäîâ.

5. Ïîëó÷åíèå ëîãè÷åñêèõ âûðàæåíèé ôóíêöèé âîçáóæäåíèÿ è âû-

õîäíûõ ñèãíàëîâ àâòîìàòîâ. Ñèãíàë q(t) ÿâëÿåòñÿ ñòðóêòóðíûì âûõîä-

íûì ñèãíàëîì êîìáèíàöèîííîé ñõåìû àâòîìàòà À, îòëè÷àþùåéñÿ òåì,

÷òî åå ñòðóêòóðíûé âûõîäíîé ñèãíàë ïîëó÷àåòñÿ ïóòåì ïðåîáðàçîâàíèÿ

ñòðóêòóðíîãî âõîäíîãî ñèãíàëà x(t) àâòîìàòà À è ñòðóêòóðíîãî âûõîä-

íîãî ñèãíàëà Q(t) åãî ïàìÿòè. Ðåàëèçóÿ ñõåìó ïðåîáðàçîâàíèÿ â âèäå

êîìïîçèöèè çàäàííûõ ëîãè÷åñêèõ ýëåìåíòîâ, ìîæíî îñóùåñòâèòü âñå

òå ïåðåõîäû, êîòîðûå ïðåäóñìàòðèâàþòñÿ ôóíêöèåé ïåðåõîäîâ àâòîìà-

òà À. Àíàëîãè÷íî ôîðìèðóåòñÿ ñòðóêòóðíûé âûõîäíîé ñèãíàë y(t) íà

âûõîäå êîìáèíàöèîííîé ñõåìû àâòîìàòà À. Òðåáóåìûå çíà÷åíèÿ âûõîä-

íîãî ñèãíàëà îáåñïå÷èâàþòñÿ ñîîòâåòñòâóþùèì ñèíòåçîì ýòîé ñõåìû.

Äëÿ ïîëó÷åíèÿ ëîãè÷åñêèõ âûðàæåíèé ôóíêöèé âîçáóæäåíèÿ è âû-

õîäíûõ ñèãíàëîâ íåîáõîäèìî âîñïîëüçîâàòüñÿ ñîîòâåòñòâåííî òàáëèöåé

ôóíêöèé âîçáóæäåíèÿ è êîäèðîâàííîé òàáëèöåé âûõîäîâ â êà÷åñòâå òàá-

ëèö èñòèííîñòè.

Êàê èçâåñòíî, ïî òàáëèöå èñòèííîñòè ìîæíî ïîëó÷èòü òîëüêî ñîâåð-

øåííóþ äèçúþíêòèâíóþ è íîðìàëüíóþ ôîðìó (ÑÄÍÔ) çàäàííîé ôóíê-

öèè. Äëÿ òîãî ÷òîáû ìèíèìèçèðîâàòü ôóíêöèþ, öåëåñîîáðàçíî âîñïîëü-

çîâàòüñÿ äèàãðàììîé Âåé÷à.

6. Ïîñòðîåíèå ñòðóêòóðíîé ñõåìû. Íà îñíîâàíèè ïîëó÷åííûõ ëîãè-

÷åñêèõ âûðàæåíèé ñòðîèòñÿ ñõåìà ñòðóêòóðíîãî àâòîìàòà èç çàäàííûõ

ýëåìåíòàðíûõ àâòîìàòîâ è ëîãè÷åñêèõ ýëåìåíòîâ ôóíêöèîíàëüíî ïîë-

íîãî áàçèñà.

Ðàññìîòðèì â êà÷åñòâå ïðèìåðà ñèíòåç ñòðóêòóðíîé ñõåìû àâòîìàòà

Ìèëè, ñïðîåêòèðîâàííîãî â ðàçäåëå 5, ôóíêöèè ïåðåõîäîâ êîòîðîãî

îïèñûâàþòñÿ â òàáë. 5.14.

Îáû÷íî â êà÷åñòâå ñòðóêòóðíîãî àëôàâèòà èñïîëüçóåòñÿ äâîè÷íûé

ñòðóêòóðíûé àëôàâèò {0, 1}, à â êà÷åñòâå ýëåìåíòàðíîãî àâòîìàòà èñ-

ïîëüçóåòñÿ àâòîìàò Ìóðà ñ äâóìÿ ñîñòîÿíèÿìè.

Ïóñòü èìååì àáñòðàêòíûé ýëåìåíòàðíûé àâòîìàò ñ âõîäíûì àëôàâè-

òîì V={v

}, âûõîäíûì àëôàâèòîì è àëôàâèòîì ñîñòîÿíèé C={c

}

è òàáëèöåé ïåðåõîäîâ-âûõîäîâ (òàáë. 6.1).

Ïðîèçâåäåì îïåðàöèþ êîäèðîâàíèÿ ñîñòîÿíèé,

âõîäíûõ è âûõîäíûõ ñèãíàëîâ ó ýëåìåíòàðíîãî è

èñõîäíîãî àâòîìàòîâ. Ïîñêîëüêó ñòðóêòóðíûé àë-

ôàâèò äâîè÷íûé, ÷èñëî ýëåìåíòàðíûõ âõîäíûõ êà-

íàëîâ àâòîìàòà îïðåäåëÿåòñÿ êàê L ≥ ]log

F[, ÷èñ-

ëî ýëåìåíòàðíûõ âûõîäíûõ êàíàëîâ îïðåäåëÿåòñÿ

êàê N ≥ ]log

G[, à ÷èñëî ýëåìåíòîâ ïàìÿòè àâòîìà-

òà  êàê R ≥ ]log

(M+1)[.

Ïåðåéäåì îò àáñòðàêòíîãî ýëåìåíòàðíîãî àâòîìàòà ê ñòðóêòóðíîìó.

Çàêîäèðóåì àáñòðàêòíûå âõîäíûå ñèãíàëû (òàáë. 6.2), âûõîäíûå ñèãíàëû

è ñîñòîÿíèÿ (òàáë. 6.3). Ïîëó÷èì êîäèðîâàííóþ òàáëèöó ïåðåõîäîâ-âû-

õîäîâ ýëåìåíòàðíîãî àâòîìàòà (òàáë. 6.4).



Òàáëèöà 6.1

Òàáëèöà 6.2 Òàáëèöà 6.3 Òàáëèöà 6.4

Ïðîèçâåäåì òàêæå êîäèðîâàíèå àáñòðàêòíûõ âõîäíûõ ñèãíàëîâ

(òàáë. 6.5), âûõîäíûõ ñèãíàëîâ (òàáë. 6.6) è ñîñòîÿíèé (òàáë. 6.7) çàäàí-

íîãî àâòîìàòà, îïðåäåëèâ ïðè ýòîì ÷èñëî ýëåìåíòîâ ïàìÿòè. ×èñëî ýëå-

ìåíòàðíûõ âõîäíûõ êàíàëîâ ïðîåêòèðóåìîãî ñòðóêòóðíîãî àâòîìàòà

L ≥ ]log

3[ = 2. ×èñëî åãî ýëåìåíòàðíûõ âûõîäíûõ êàíàëîâ N≥]log

3[ = 2

è ÷èñëî ýëåìåíòîâ ïàìÿòè R ≥ ]log

7[ = 3. Ñëåäîâàòåëüíî, ñõåìà ïðî-

åêòèðóåìîãî ñòðóêòóðíîãî àâòîìàòà äîëæíà èìåòü âèä, ïðåäñòàâ-

ëåííûé íà ðèñ. 6.3. Îïðåäåëèì ñòðóêòóðíûé âõîäíîé àëôàâèò àâòî-

ìàòà (òàáë. 6.5), ñòðóêòóðíûé âûõîäíîé àëôàâèò (òàáë. 6.6) è àëôàâèò

ñîñòîÿíèé (òàáë. 6.7). Ðàçîáüåì òàáëèöó ïåðåõîäîâ-âûõîäîâ äëÿ äàííî-

ãî àáñòðàêòíîãî àâòîìàòà (òàáë. 5.14) íà äâå òàáëèöû: òàáëèöó ïåðåõî-

äîâ (òàáë. 6.8) è òàáëèöó âûõîäîâ (òàáë. 6.9).

Òàáëèöà 6.5 Òàáëèöà 6.6 Òàáëèöà 6.7

Íà îñíîâàíèè òàáë. 6.8 è 6.7 ïîñòðîèì êî-

äèðîâàííóþ òàáëèöó ïåðåõîäîâ àâòîìàòà









































? 3

















 



Q(t+

)

Q(t+

)

(

)

q(t)

x(t)

(t)

y(t)

Q1 Q2 Q3

Ðèñ. 6.3

(òàáë. 6.10), à íà îñíîâàíèè òàáë. 6.6 è 6.9 ïîñòðîèì êîäèðîâàííóþ

òàáëèöó âûõîäîâ (òàáë. 6.11).

Òàáëèöà 6.8 Òàáëèöà 6.9

Òàáëèöà 6.10 Òàáëèöà 6.11

Â êàæäîé êëåòêå òàáë. 6.10 ïåðåõîäîâ çàïèñûâàåòñÿ äâîè÷íûé êîä

ñîîòâåòñòâóþùåãî ñîñòîÿíèÿ àâòîìàòà, à â êàæäîé êëåòêå òàáë. 6.11

âûõîäîâ  äâîè÷íûé êîä ñîîòâåòñòâóþùåãî âûõîäíîãî ñèãíàëà. Äàëåå,

ïîëüçóÿñü òàáë. 6.10 è 6.4, ìîæíî ïîñòðîèòü òàáëèöó ôóíêöèé âîçáóæ-

äåíèÿ ñòðóêòóðíîãî àâòîìàòà (òàáë. 6.12), äëÿ ÷åãî â êàæäîé êëåòêå

ýòîé òàáëèöû íåîáõîäèìî çàïèñàòü çíà÷åíèÿ òðåáóåìûõ âõîäíûõ ñèã-

íàëîâ q

, q

è q

äëÿ êàæäîãî èç òðåõ ýëåìåíòîâ ïàìÿòè Q

, Q

è Q

çàâèñèìîñòè îò ôèêñèðóåìîãî â ñîîòâåòñòâóþùåé êëåòêå òàáë. 6.10

ïåðåõîäà èç îäíîãî ñîñòîÿíèÿ â äðóãîå. Äàëåå ïî òàáë. 6.11 è 6.12 ñôîð-

ìèðóåì ëîãè÷åñêèå âûðàæåíèÿ äëÿ ôóíêöèé âîçáóæäåíèÿ è âûõîäíîãî

ñèãíàëà.

×òîáû ïîëó÷èòü ìèíèìàëüíûå ÄÍÔ ôóíêöèé âîçáóæäåíèÿ q

, q

è âûõîäíûõ ñèãíàëîâ Q

, Q

, ïîñòðîèì äèàãðàììû Âåé÷à äëÿ êàæ-





 

 

 

 

 

  ` 

 ` 





 

 

 

 

 

  ` 

 ` 

c t 













c

c t 





ββ



ββ













w





w





äîé èç èñêîìûõ ôóíêöèé. Àðãóìåíòàìè

âñåõ ôóíêöèé âîçáóæäåíèÿ â ñîîòâåòñòâèè

ñ âûðàæåíèåì (6.3) è òàáë. 6.12 ÿâëÿþò-

ñÿ ñîñòîÿíèÿ ýëåìåíòàðíûõ àâòîìàòîâ

, Q

è âõîäíûå ñèãíàëû x

è x

Ò. å.

(t), Q

(t), x

(t)),

(t), Q

(t), x

(t)),

(t), Q

(t), x

(t)).

Àðãóìåíòàìè äëÿ y

è y

â ñîîòâåò-

ñòâèè ñ âûðàæåíèåì (6.1) è òàáë. 6.11 òàê-

æå ÿâëÿþòñÿ Q

, Q

, x

è x

. Òàêèì

îáðàçîì,

(t) = λ

(t), Q

(t), x

(t)),

(t) = λ

(t), Q

(t), x

(t)).

Â ðåçóëüòàòå ïðîâåäåííîé ìèíèìèçàöèè ïîëó÷èì ñëåäóþùèå ëîãè-

÷åñêèå âûðàæåíèÿ äëÿ ôóíêöèé âîçáóæäåíèÿ:

123 123 1123 12

xQQ xQQ xQQQ QQ

∨∨ ∨

113 2123 12

xQQ xQQQ QQ

∨∨

213 213 212 1212

xQQ xQQ xQQ xxQQ

∨∨∨

Ïîñêîëüêó íà êîìáèíàöèîííîé ñõåìå âûõîäíûå ñèãíàëû âûðàáàòûâà-

þòñÿ ïðàêòè÷åñêè îäíîâðåìåííî ñ ìîìåíòîì ïîñòóïëåíèÿ âõîäíûõ ñèã-

íàëîâ, âðåìåííûå ñîîòíîøåíèÿ ìîãóò áûòü â âûðàæåíèÿõ îïóùåíû.

Ëîãè÷åñêîå âûðàæåíèå äëÿ âûõîäíîãî ñèãíàëà y

öåëåñîîáðàçíî ïî-

ëó÷àòü, ìèíèìèçèðóÿ y

ïî 0, à íå ïî 1, ïîñêîëüêó â ýòîì ñëó÷àå

ïîëó÷àåòñÿ âûðàæåíèå ñ ìåíüøèé ðàíãîì. Â ðåçóëüòàòå èìååì

112 2 23

xQQ xQQ

∨

21 123 121 212 122 123

xQ xQQ xxQ xQQ xxQ QQQ

∨∨∨∨∨

Íà áàçå ïîëó÷åííûõ âûðàæåíèé ìîæíî ïîñòðîèòü ñòðóêòóðíóþ ñõå-

ìó àâòîìàòà â ëþáîì ôóíêöèîíàëüíî ïîëíîì áàçèñå.





 

 

 

 

 

  ` 

 ` 

Òàáëèöà 6.12