Составители:
19
Ñòðóêòóðíûé ñèíòåç àâòîìàòà âûïîëíÿåòñÿ ïî èçâåñòíûì ìåòîäèêàì,
îïèñàííûì, íàïðèìåð â [10]. Äëÿ óäîáñòâà ôîðìèðîâàíèÿ âûõîäíûõ ñèã-
íàëîâ àâòîìàòà ïðèìåì ñëåäóþùóþ ôîðìó êîäèðîâàíèÿ ñîñòîÿíèé:
a1 –
Q1Q2Q3Q4
,
a2 –
Q1Q2Q3Q4
,
a3 –
Q1Q2Q3Q4
,
a4 –
Q1Q2Q3Q4
,
à5 –
Q1Q2Q3Q4
.
Óðàâíåíèÿ êîìáèíàöèîííîé ñõåìû àâòîìàòà, èñïîëüçóþùåãî â êà-
÷åñòâå ýëåìåíòà ïàìÿòè j-k òðèããåð, èìåþò âèä:
y1 = Q1, j1 = z2 &
z3
, k1 = Q1,
y2 = Q2, j2 = Q1 v
z1
, k2 = z1,
y3 = Q3, j3 = z1, k3 = Q3,
y4 = Q4, j4 = Q3 v
z2
, k4 = z2.
y5 =
Q1Q2Q3Q4
.
Íà ðèñ. 7 ïðèâåäåíà AC ñòðóêòóðíîé ñõåìû óïðàâëÿþùåãî àâòîìà-
òà. Ïðè âûáðàííîì ñïîñîáå êîäèðîâàíèÿ ñîñòîÿíèé ýëåìåíòû ïàìÿòè
àâòîìàòà ìîãóò áûòü âêëþ÷åíû â ñîñòàâ ñõåì öèêëîâ. Ñèíòåç óïðàâëÿ-
þùåãî àâòîìàòà áóäåò ïðè ýòîì ñîñòîÿòü â ôîðìèðîâàíèè AC êîìáèíà-
öèîííîé ñõåìû.
Åñëè âíåøíÿÿ ê öèêëó ñåòü íå ñîäåðæèò îïåðàòîðîâ çàäåðæêè, òî íà
ïåðâîì øàãå ñ÷åòà íà AC áóäóò îïðåäåëåíû âñå íåîáõîäèìûå âõîäíûå
âåëè÷èíû äëÿ ðåàëèçàöèè èòåðàöèîííîé ïðîöåäóðû öèêëà. Ýòè âåëè-
÷èíû áóäóò ñîõðàíÿòü ñâîå çíà÷åíèå äî îêîí÷àíèÿ ñ÷åòà â öèêëå. Çíà÷å-
íèÿ ïåðåìåííûõ AC, â ðàñ÷åòå êîòîðûõ ó÷àñòâóþò âûõîäíûå ïåðåìåí-
íûå öèêëà áóäóò ïîëó÷åíû ïî çàâåðøåíèþ èòåðàöèîííîé ïðîöåäóðû
ñ÷åòà. Äëÿ ðàññìàòðèâàåìîãî ïðèìåðà ðåçóëüòàòû ðàñ÷åòîâ ôèêñèðóþò-
ñÿ ïðè ïåðåõîäå óïðàâëÿþùåãî àâòîìàòà â ñîñòîÿíèå à5.
Ïîäõîä ÿâëÿåòñÿ óíèâåðñàëüíûì è ïîçâîëÿåò ôîðìèðîâàòü ïðîèç-
âîëüíûå öèêëè÷åñêèå ïðîöåäóðû â êàíîíè÷åñêèõ AC áåç ðàñøèðåíèÿ
íàáîðà îïåðàòîðîâ àëãîðèòìè÷åñêîãî áàçèñà. Ïîëó÷åííûå ðåçóëüòàòû
ïîçâîëèëè äîêàçàòü òåîðåìó, ïîäòâåðæäàþùóþ àëãîðèòìè÷åñêóþ ïîë-
íîòó êàíîíè÷åñêèõ AC [3]:
Äëÿ ëþáîé ÷àñòè÷íî-ðåêóðñèâíîé ôóíêöèè ìîæåò áûòü ïîñòðîåíà
ðåàëèçóþùàÿ åå êîíå÷íàÿ AC.
