Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Гудилин А.Е., Барбасова Т.А. Теория цифровых автоматов - файл 1.doc


Гудилин А.Е., Барбасова Т.А. Теория цифровых автоматов
скачать (1770.5 kb.)

Доступные файлы (1):

1.doc1771kb.20.12.2011 10:37скачать

Загрузка...

1.doc

  1   2   3   4   5   6   7   8   9   ...   15
Реклама MarketGid:
Загрузка...
ÌÈÍÈÑÒÅÐÑÒÂÎ ÎÁÐÀÇÎÂÀÍÈß ÐÎÑÑÈÉÑÊÎÉ ÔÅÄÅÐÀÖÈÈ





ÞÆÍΖÓÐÀËÜÑÊÈÉ ÃÎÑÓÄÀÐÑÒÂÅÍÍÛÉ ÓÍÈÂÅÐÑÈÒÅÒ




681.3(07)

Ë561
ÒÅÎÐÈß ÖÈÔÐÎÂÛÕ ÀÂÒÎÌÀÒÎÂ




×åëÿáèíñê

2005
À.Å.Ãóäèëèí, Ò.À. Áàðáàñîâà


Ó÷åáíîå ïîñîáèå ïî êóðñó

«Öèôðîâûå àâòîìàòû»
Þæíî-Óðàëüñêèé ãîñóäàðñòâåííûé

óíèâåðñèòåò

Ïðèáîðîñòðîèòåëüíûé ôàêóëüòåò

Êàôåäðà Àâòîìàòèêè è óïðàâëåíèÿ

×åëÿáèíñê

2005
ÑÎÄÅÐÆÀÍÈÅ

ÂÂÅÄÅÍÈÅ 5

Ãëàâà 1 7

ËÎÃÈ×ÅÑÊÈÅ ÎÑÍÎÂÛ ÖÈÔÐÎÂÛÕ ÀÂÒÎÌÀÒΠ7

1.1 Îñíîâíûå ïîíÿòèÿ àëãåáðû ëîãèêè 7

1.2 Áàçèñ È, ÈËÈ, ÍÅ. Ñâîéñòâà ýëåìåíòàðíûõ ôóíêöèé àëãåáðû ëîãèêè 10

1.3 Ñïîñîáû îïèñàíèÿ áóëåâûõ ôóíêöèé 12

1.3.1 Òàáëè÷íîå îïèñàíèå áóëåâûõ ôóíêöèé 13

1.3.2 Àíàëèòè÷åñêîå îïèñàíèå áóëåâûõ ôóíêöèé 14

1.3.3 ×èñëîâàÿ ôîðìà ïðåäñòàâëåíèÿ áóëåâûõ ôóíêöèé 16

1.3.4 Ãðàôè÷åñêàÿ ôîðìà ïðåäñòàâëåíèÿ áóëåâûõ ôóíêöèé 16

1.3.5 Ãåîìåòðè÷åñêîå ïðåäñòàâëåíèå áóëåâûõ ôóíêöèé 17

1.4 Ìèíèìèçàöèÿ ôóíêöèé àëãåáðû ëîãèêè 22

1.4.1 Ìèíèìèçàöèÿ ñ ïîìîùüþ ìèíèìèçèðóþùèõ êàðò 22

1.4.2 Ìèíèìèçàöèÿ ôóíêöèé àëãåáðû ëîãèêè ïî ìåòîäó Êâàéíà 23

1.4.3 ìèíèìèçàöèÿ ôóíêöèé àëãåáðû ëîãèêè 29

ïî ìåòîäó Êâàéíà - Ìàê-Êëàñêè 29

1.5 Ýëåìåíòíàÿ áàçà äëÿ ïîñòðîåíèÿ êîìáèíàöèîííûõ ñõåì 33

1.5.1 Ëîãè÷åñêèå ýëåìåíòû È, ÈËÈ, ÍÅ 33

1.5.2 Ïðèìåðû òåõíè÷åñêîé ðåàëèçàöèè áóëåâûõ ôóíêöèé 37

1.5.3 Ïðîãðàììèðóåìûå ëîãè÷åñêèå ìàòðèöû (ÏËÌ) 39

Ãëàâà 2 47

ÑÈÍÒÅÇ ÖÈÔÐÎÂÛÕ ÀÂÒÎÌÀÒÎÂ 47

2.1 Îïðåäåëåíèå àáñòðàêòíîãî öèôðîâîãî àâòîìàòà 47

2.2 Ìåòîäû îïèñàíèÿ öèôðîâûõ àâòîìàòîâ 51

2.3 Ñèíõðîííûå è àñèíõðîííûå öèôðîâûå àâòîìàòû 55

2.4 Ñâÿçü ìåæäó ìàòåìàòè÷åñêèìè ìîäåëÿìè 56

öèôðîâûõ àâòîìàòîâ Ìèëè è Ìóðà 56

2.5 Ìèíèìèçàöèÿ àáñòðàêòíûõ öèôðîâûõ àâòîìàòîâ 65

2.5.1 Ìèíèìèçàöèÿ àáñòðàêòíîãî àâòîìàòà Ìèëè 65

2.5.2 Ìèíèìèçàöèÿ àáñòðàêòíîãî àâòîìàòà Ìóðà 73

2.6 Ñòðóêòóðíûé ñèíòåç àâòîìàòîâ 78

2.6.1 Ýëåìåíòàðíûå àâòîìàòû ïàìÿòè 78

2.6.2 Ñèíõðîíèçàöèÿ â öèôðîâûõ àâòîìàòàõ 84

2.7 Ñòðóêòóðíûé ñèíòåç öèôðîâûõ àâòîìàòîâ ïî òàáëèöàì 87

2.8 Ñòðóêòóðíûé ñèíòåç öèôðîâîãî àâòîìàòà ïî ãðàôó 100

Ãëàâà 3 105

ÌÈÊÐÎÏÐÎÃÐÀÌÌÍÛÅ ÀÂÒÎÌÀÒÛ 105

3.1 Äåêîìïîçèöèÿ óñòðîéñòâ îáðàáîòêè öèôðîâîé èíôîðìàöèè 105

3.2 Óïðàâëÿþùèå àâòîìàòû 107

3.3 Ïðèíöèï äåéñòâèÿ óïðàâëÿþùåãî àâòîìàòà ñ õðàíèìîé â ïàìÿòè ëîãèêîé è ìèêðîïðîãðàììíîå óïðàâëåíèå 110

3.3.1 Ãîðèçîíòàëüíîå ìèêðîïðîãðàììèðîâàíèå 114

3.3.2 Âåðòèêàëüíîå ìèêðîïðîãðàììèðîâàíèå 114

3.3.3 Ñìåøàííîå ìèêðîïðîãðàììèðîâàíèå 115

3.4 Óïðàâëÿþùèå àâòîìàòû ñ «æ¸ñòêîé ëîãèêîé» 117

3.5 Ãðàô - ñõåìû ìèêðîïðîãðàììíûõ àâòîìàòîâ 118

3.6 Ñèíòåç ìèêðîïðîãðàììíûõ àâòîìàòîâ ïî ãðàô - ñõåìå àëãîðèòìà 125

3.6.1 Ñèíòåç ìèêðîïðîãðàììíîãî àâòîìàòà Ìèëè 125

3.6.2 Ñèíòåç ìèêðîïðîãðàììíîãî àâòîìàòà Ìóðà 129

3.6.3 Ìèíèìèçàöèÿ ìèêðîïðîãðàììíûõ àâòîìàòîâ 134

Çàêëþ÷åíèå 136

ËÈÒÅÐÀÒÓÐÀ 137

ÂÂÅÄÅÍÈÅ




 êóðñå «Öèôðîâàÿ ñõåìîòåõíèêà» ðàññìàòðèâàþòñÿ òåîðåòè÷åñêèå îñíîâû ïîñòðîåíèÿ öèôðîâûõ àâòîìàòîâ êàê ïðåîáðàçîâàòåëåé äâîè÷íûõ öèôðîâûõ ñèãíàëîâ. Âñå ñèñòåìû îáðàáîòêè öèôðîâîé èíôîðìàöèè (â òîì ÷èñëå è öèôðîâûå âû÷èñëèòåëüíûå ìàøèíû - ÝÂÌ) ìîãóò â îáùåì âèäå ïðåäñòàâëåíû êàê êîäîïðåîáðàçîâàòåëè (ðèñ. 1) .

Îñîáåííîñòüþ öèôðîâîãî àâòîìàòà ÿâëÿåòñÿ çàâèñèìîñòü îïåðàòîðà ïðåîáðàçîâàíèÿ À îò ïðåäûäóùèõ ñîñòîÿíèé êîäîïðåîáðàçîâàòåëÿ, òî åñòü íàëè÷èå ïàìÿòè ó öèôðîâîãî àâòîìàòà.  ÷àñòíîì ñëó÷àå îòñóòñòâèÿ ïàìÿòè ó öèôðîâîãî àâòîìàòà, îí ÿâëÿåòñÿ ëîãè÷åñêîé ñõåìîé. Òàêèì îáðàçîì, ïðåäìåòàìè èññëåäîâàíèÿ â òåîðèè öèôðîâûõ àâòîìàòîâ ÿâëÿþòñÿ êàê ñîáñòâåííî öèôðîâûå àâòîìàòû (ñèñòåìû ñ ïàìÿòüþ), òàê è àâòîìàòû áåç ïàìÿòè èëè ëîãè÷åñêèå ñõåìû.

Íàèáîëåå ðàçðàáîòàíà òåîðèÿ öèôðîâûõ àâòîìàòîâ ïðèìåíèòåëüíî ê êàíîíè÷åñêîé ñòðóêòóðå öèôðîâîãî àâòîìàòà, ïðåäñòàâëåííîé íà ðèñ.2. Äëÿ äàëüíåéøåãî ðàññìîòðåíèÿ èñïîëüçóåòñÿ òîëüêî ýòà ñòðóêòóðà öèôðîâîãî àâòîìàòà.

Ïî ñòðóêòóðíîé ñõåìå öèôðîâîãî àâòîìàòà âèäíî, ÷òî âõîäíûå êîäû âõîäíîé è âûõîäíîé êîìáèíàöèîííûõ ñõåì ïîëó÷àþòñÿ â ðåçóëüòàòå êîíêàòåíàöèè (îáúåäèíåíèÿ) âõîäíîãî êîäà è êîäà ñîñòîÿíèÿ ïàìÿòè öèôðîâîãî àâòîìàòà.

Ãëàâà 1

ËÎÃÈ×ÅÑÊÈÅ ÎÑÍÎÂÛ ÖÈÔÐÎÂÛÕ ÀÂÒÎÌÀÒÎÂ

1.1 Îñíîâíûå ïîíÿòèÿ àëãåáðû ëîãèêè


Ïîíÿòèå öèôðîâîãî àâòîìàòà áûëî ââåäåíî êàê ìîäåëü äëÿ îïèñàíèÿ ôóíêöèîíèðîâàíèÿ óñòðîéñòâ, ïðåäíàçíà÷åííûõ äëÿ ïåðåðàáîòêè öèôðîâîé èëè äèñêðåòíîé èíôîðìàöèè.

Äëÿ ôîðìàëüíîãî îïèñàíèÿ öèôðîâûõ àâòîìàòîâ ïðèìåíÿåòñÿ àïïàðàò àëãåáðû ëîãèêè, ñîçäàííîé àíãëèéñêèì ìàòåìàòèêîì Äæ. Áóëåì (1815-1864). Ïîýòîìó àëãåáðó ëîãèêè íàçûâàþò àëãåáðîé Áóëÿ èëè áóëåâîé àëãåáðîé.

 àëãåáðå ëîãèêè ïðèìåíèòåëüíî ê îïèñàíèþ öèôðîâûõ àâòîìàòîâ, ðàáîòàþùèõ â äâîè÷íîì ïðåäñòàâëåíèè êîäîâ (èëè öèôðîâîé èíôîðìàöèè) îñíîâíûìè ïîíÿòèÿìè ÿâëÿþòñÿ ëîãè÷åñêàÿ (áóëåâà) ïåðåìåííàÿ è ëîãè÷åñêàÿ ôóíêöèÿ (ôóíêöèÿ àëãåáðû ëîãèêè - ÔÀË).

Ëîãè÷åñêàÿ (áóëåâà) ïåðåìåííàÿ - òàêàÿ âåëè÷èíà x, êîòîðàÿ ìîæåò ïðèíèìàòü òîëüêî äâà çíà÷åíèÿ : x = {0,1}.

Ëîãè÷åñêàÿ ôóíêöèÿ (ôóíêöèÿ àëãåáðû ëîãèêè - ÔÀË) - ôóíêöèÿ ìíîãèõ àðãóìåíòîâ f(xn-1, xn-2,, ..., x0), ïðèíèìàþùàÿ çíà÷åíèÿ ðàâíûå íóëþ èëè åäèíèöå íà íàáîðàõ ëîãè÷åñêèõ ïåðåìåííûõ xn-1, xn-2,, ..., x0.

 äàëüíåéøåì â ôîðìàëüíûõ îïèñàíèÿõ íàáîðîâ ïåðåìåííûõ è ëîãè÷åñêèõ ôóíêöèé ñàìè íàáîðû ïåðåìåííûõ èíòåðïðåòèðóþòñÿ êàê äâîè÷íûå êîäû (÷èñëà).  äâîè÷íûõ êîäàõ ðàñïîëîæåíèå ëîãè÷åñêèõ ïåðåìåííûõ óïîðÿäî÷åíî â ïîðÿäêå óìåíüøåíèÿ èíäåêñà ñëåâà íàïðàâî è êàæäàÿ ëîãè÷åñêàÿ ïåðåìåííàÿ èìååò âåñ â çàâèñèìîñòè îò ïîçèöèè â êîäå, óâåëè÷èâàþùèéñÿ ñïðàâà íàëåâî. Âåñ êàæäîé i - òîé ëîãè÷åñêîé ïåðåìåííîé, ÿâëÿþùåéñÿ çíà÷åíèåì ðàçðÿäà äâîè÷íîãî ÷èñëà ðàâåí 2i (i = 0, ... , n-1).

Äëÿ n - ðàçðÿäíîãî êîäà îáùåå êîëè÷åñòâî óíèêàëüíûõ íàáîðîâ ïåðåìåííûõ

N = 2n; (1)

Ìàêñèìàëüíîå ÷èñëîâîå çíà÷åíèå äâîè÷íîãî êîäà ðàâíî

Aìàêñ = 2n-1; (2)

Çíà÷åíèÿ âñåõ ëîãè÷åñêèõ ôóíêöèé îò îäíîé ïåðåìåííîé ïðåäñòàâëåíû â òàáëèöå 1.Òàáëèöà 1


x

f0(x)

f1(x)

f2(x)

f3(x)

0

0

0

1

1

1

0

1

0

1


Ôóíêöèÿ f0(x) íàçûâàåòñÿ êîíñòàíòîé íóëÿ, à ôóíêöèÿ f3(x) - êîíñòàíòîé åäèíèöû. Ôóíêöèÿ f1(x), ïîâòîðÿþùàÿ çíà÷åíèÿ ëîãè÷åñêîé ïåðåìåííîé, -òîæäåñòâåííàÿ ôóíêöèÿ (f1(x) º x), à ôóíêöèÿ f2(x), ïðèíèìàþùàÿ çíà÷åíèÿ, îáðàòíûå çíà÷åíèÿì ïåðåìåííîé x, - ëîãè÷åñêîå îòðèöàíèå èëè èíâåðñèÿ (ÍÅ) (f2(x) = ).

Çíà÷åíèÿ âñåõ ëîãè÷åñêèõ ôóíêöèé îò äâóõ ïåðåìåííûõ ïðåäñòàâëåíû â òàáëèöå 2. Äëÿ ôóíêöèè äâóõ ïåðåìåííûõ, ñîãëàñíî ô.(1), ñóùåñòâóåò ÷åòûðå óíèêàëüíûõ íàáîðà ïåðåìåííûõ. Ôóíêöèè îòëè÷àþòñÿ äðóã îò äðóãà íàáîðîì çíà÷åíèé 0 è 1 â ÷åòûðåõ ðàçðÿäàõ êîäà çíà÷åíèé ôóíêöèè. Îáùåå êîëè÷åñòâî ôóíêöèé íà n - ìåñòíîì èëè n - ðàçðÿäíîì íàáîðå ïåðåìåííûõ ðàâíî

; (3)

 òàáëèöå 2 ïðèâåäåíû ïðèìåðû àíàëèòè÷åñêîé çàïèñè íåêîòîðûõ áóëåâûõ ôóíêöèé ñ èñïîëüçîâàíèåì äðóãèõ áóëåâûõ ôóíêöèé, òî åñòü ñóùåñòâóåò òàêîé íàáîð áóëåâûõ ôóíêöèé, èç êîòîðîãî ìîæíî ñêîíñòðóèðîâàòü ëþáóþ áóëåâó ôóíêöèþ, ðàâíîñèëüíóþ çàäàííîé.

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

Àíàëèòè÷åñêè ýòî ñâîéñòâî îïèñûâàåòñÿ ñëåäóþùåé ôîðìóëîé:
f1 (xn-1, xn-2,, ..., x0) = f2 (xn-1, xn-2,, ..., x0); (4)
Îáå ôóíêöèè â ô.(4) ìîãóò èìåòü ðàçíûå ôîðìû àíàëèòè÷åñêîé çàïèñè, íî ïðàêòè÷åñêè íàèáîëåå âûãîäíîé áóäåò ñàìàÿ ïðîñòàÿ ôîðìà çàïèñè.


Ñèñòåìà áóëåâûõ ôóíêöèé W íàçûâàåòñÿ ôóíêöèîíàëüíî ïîëíîé, åñëè äëÿ ëþáîé áóëåâîé ôóíêöèè n - ïåðåìåííûõ f(xn-1, xn-2,, ..., x0) ìîæåò áûòü ïîñòðîåíà ðàâíîñèëüíàÿ åé ôóíêöèÿ êîìáèíèðîâàíèåì áóëåâûõ ïåðåìåííûõ xn-1, xn-2,, ..., x0 è ôóíêöèé ñèñòåìû W, âçÿòûõ â ëþáîì êîíå÷íîì êîëè÷åñòâå ýêçåìïëÿðîâ êàæäàÿ. Òàêàÿ ñèñòåìà áóëåâûõ ôóíêöèé (W) íàçûâàåòñÿ áàçèñîì.

Òàêèì îáðàçîì, áàçèñ - ïîëíàÿ ñèñòåìà ôóíêöèé àëãåáðû ëîãèêè (ÔÀË), ñ ïîìîùüþ êîòîðîé ëþáàÿ ÔÀË ìîæåò áûòü ïðåäñòàâëåíà ñóïåðïîçèöèåé èñõîäíûõ ôóíêöèé W.

Áàçèñîì ÿâëÿåòñÿ ñèñòåìà ôóíêöèé È ( êîíúþíêöèÿ), ÈËÈ ( äèçúþíêöèÿ), ÍÅ ( èíâåðñèÿ), ñâîéñòâà êîòîðûõ áûëè âïåðâûå èçó÷åíû Äæ. Áóëåì.

Áàçèñàìè ÿâëÿþòñÿ ñèñòåìû:

- È,ÍÅ;

- ÈËÈ,ÍÅ;

- ôóíêöèÿ Øåôôåðà È-ÍÅ;

- ôóíêöèÿ Ïèðñà ÈËÈ-ÍÅ.

Áàçèñ ÿâëÿåòñÿ ìèíèìàëüíûì, åñëè óäàëåíèå èç íåãî õîòÿ áû îäíîé ôóíêöèè ïðåâðàùàåò ñèñòåìó ÔÀË â íåïîëíóþ. Áàçèñ È, ÈËÈ, ÍÅ - èçáûòî÷íûé.

  1   2   3   4   5   6   7   8   9   ...   15



Скачать файл (1770.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru