Сандық ҚҰрылғылардың математикалық негіздері 1 Санау жүйесі 2

жүктеу 3,51 Mb.

бет	17/30
Дата	21.05.2018
өлшемі	3,51 Mb.
	#15431

1 ... 13 14 15 16 17 18 19 20 ... 30

1.10 сурет

Осы үш Карно карталарын бір біріне салғанда 1.11а) суретінде көрсетілген карта шығады. Қалған бос клеткаларға 0- ді қойғаннан соң, 1.11б) суретінде көрсетілген толық толтырылған Карно картасы шығады.

1.11 сурет
Карно картасын толтырғаннан кейін кішірейту басталады. Кішірейту процессінде 1 (немесе 0) қамитын барлық клеткалар топтарға біріктірілуі керек.

Топтарға 1 (немесе 0) қамтитын және тікбұрыш немесе квадрат құрайтын көрші клеткалар біріктіріледі. Топ 2 ⁿклеткалар қамту керек (n = 0, 1, 2, 3 ж т.с.с), басқаша айтқанда 1, 2, 4, 8, 16 және т.с.с клеткалар. Топтар неғұрлым аз болуына тырысу керек, осыған жету үшін әр бір топқа клеткалардың максималды болымды санын қосу керек. Топтарды құру процессі барлық клеткалар топқа біріктірілмегенінше жалғасады.басқалармен біріктіруге болмайтын 1мен (немесе 0мен ) клеткалар, 1 клеткалар санымен топ құады. Сол бір клетка бірнеше топқа кіруі мүмкін.

Көрші клеткаларын анықтағанда Карно картасын көлденеңмен тігімен рулонға орауға болады. Карно картасында 1.8в) суретінде мысалы, көрші клеткалар 2 мен 10 болады; 1, 5, 9 бен 13; сондай ақ 0, 4, 8 бен 12!

Клеткаларды біріктіру теңмәнді нұсқалар бірнеше болуы мүмкін.

Кішірейтілген функцияны дизъюнктивті нормальді формада (ДНФ) немесе конъюнктивті нормальді формада (КНФ) жазады. Жиі ДНФ қолданылады. ДНФ- те клеткаларды бірліктермен біріктіргенде кішірейтілген функция түрі:

клеткаларды нөлдермен біріктіргенде:
,
мұнда С_i – i – ші топ үшін конъюнкция; m – топтар саны.

Конъюнкция өрнегіне инверсиямен инверсиясыз айнымалылар (бірақ бір уақытта емес) ауданында i – ші бүтін болатын топ кіреді.

Топ бүтіндей болатын аудандарды анықтау үшін келесі алгоритм ұсынуға болады.

Ойша немесе пішінше (мысалы, Карно картасының ауданының өлшемі бойынша кесілген қағазбен,)Карно картасының айнымалы аудандарының бірі жабылады. Егер Карно картасының қарастырылып отырған клеткалар топтары толық жабылып және жабылған ауданнан шығып тұрмаса, онда, берілген айнымалы конъюнкция өрнегіне кіреді қарастырылып отырған клеткалар топтары үшін. Бұл іс әрекет Карно картасының барлық аудандарына кайталанады. Мысалы, Карно картасында төрт айнымалылар ол-

Мысалы, 1.12суретінде көрсетілген 1 мен толық клетка топтары қай айнымалы аудандарында екенін анықтау керек.

1.12 сурет

айнымалылар аудандарын ретімен жаба отырып, 1.13 суретінде көрсетілген бейнені аламыз.

1.13 сурет
Осы суретте 1 мен клетка топтары толық в) және е) суреттерінде ғана жабылған, ал а) және б) суреттерінде ол жартылай ғана жабылған, ал г ) және д) суреттерінде мүлдем жабылмаған. Конъюнкция осы клекалардың тобына

айнымалыларын қамтиды, с.с

түрі болады.

Егер туынды (барлық емес айнымалыларға анықталған) функция ақиқат кестесімен берілсе, онда Карно картасын клеткаларға толтырғанда, оларға функция анықталмаған, функцияның минималды аяққы аналитикалық өрнегі мәндерін орнатады. Карно картасын толтырғанда мұндай клеткаларға жиі (Х) мәнін қояды.

Карно картасы көмегімен функцияны кішірейту реті келесі:

1 Ақиқат кестесін немесе фунцияның аналитикалық өрнегін қолдана отырып,Карно картасын толтырады;

2 Карно картасында 1 мен клеткаларды (немесе 0 мен) біріктіретін топтар жасалынады. 1 немесе 0 бойынша функцияны кішірейту арасындағы қағидалы әр түрлілігі жоқ. Функция минималды өрнегі бар нұсқа алынады;

3 Функцияның таңдалған формада кішірейтілген өрнегін жазады.

Мысалы, келесі ақиқат кестесімен берілген функцияны кішірейту керек

Х ₄	Х₃	Х₂	Х₁	f (ν)
0	0	0	1	0
0	0	1	1	1
0	1	0	1	1
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	1
1	0	1	1	0
1	0	1	0
1	1	0	1
1	1	1	1

жүктеу 3,51 Mb.

Достарыңызбен бөлісу:

1 ... 13 14 15 16 17 18 19 20 ... 30