Сабақтың тақырыбы: Логикалық функцияларды минимизациялау Модуль/пән атауы
Логикалық функцияларды минимизациялау
жүктеу/скачать 192.71 Kb.
|
- Бұл бет үшін навигация:
- Аналитикалық әдіске машиналық минимизациялау алгоритмдерін жатқызуға болады . Аналитикалық минимизацияны
- Графикалық минимизация
| Логикалық функцияларды минимизациялау
Минимизация дегеніміз - логикалық функцияларды қарапайым түрге келтіру арқылы, оны аппараттық жолмен қолдануға немесе есептеуіш құралдың модуліне қолдануға даярлық жасауды айтады. Минимизацияның аналитикалық және графикалық әдістері бар. Аналитикалық әдіске машиналық минимизациялау алгоритмдерін жатқызуға болады. Аналитикалық минимизацияны - жобалаушы өз интуициясына сүйене отырып жасайды, әрі бұл минимизация қарапайым функиялар үшін (аз аргументтермен) қолданылады. Күрделі функцияларды қысқарту үшін машиналық алгоритмдер жасалған. Кей жағдайларда минимизацияны Квайн теоремасы арқылы жүзеге асыруға болады. Графикалық минимизация - Карно картасын қолдануға негізделген. Карно картасы – бұл торларға бөлінген тік төртбұрыш. Ондағы торлардың саны функция жинтығының максималды санына яғни 2n, (мұндағы n-аргументтер саны), тең. әрбір тор бір жиынға сәйкестендірілген және онда жиынның мәні жазылады: 1 немесе 0. Функция анықталмаған жағдайда Карно картасы белгісіз жиындар үшін (-) таңбасымен) таңбасымен толтырылуы мүмкін., тыйым салынған жиындар үшін ( ) таңбасымен толтырылуы мүмкін. Логикалық функцияларды азайту схемалық технологияны оқыту процесінде типтік міндеттердің бірі болып табылады. Логикалық функцияның күрделілігі, демек, оны жүзеге асыратын тізбектің (тізбектің) күрделілігі мен құны, логикалық амалдар санына және айнымалылардың пайда болу санына немесе олардың теріске шығарылуына пропорционал. Негізінде кез-келген логикалық функцияны аксиомалар мен логикалық теоремалар арқылы тікелей жеңілдетуге болады, бірақ, әдетте, мұндай түрлендірулер күрделі есептеулерді қажет етеді. Сонымен қатар, логикалық өрнектерді жеңілдету процесі алгоритмдік емес. Сондықтан функцияны қарапайым, жылдам және қатесіз жеңілдетуге мүмкіндік беретін арнайы алгоритмдік азайту әдістерін қолданған жөн. Мұндай әдістерге, мысалы, Квин әдісі, Карно картасы әдісі, импликантты сынау әдісі, импликантты матрица әдісі, Квин-мак-класс әдісі және т.б. бұл әдістер әдеттегі практика үшін ең қолайлы, әсіресе Карно карталарын қолдана отырып логикалық функцияны азайту. Карно карталарының әдісі алтыдан аспайтын айнымалылар санында айқындықты сақтайды. Аргументтер саны алтыдан көп болған жағдайда, әдетте Квин-Макласка әдісі қолданылады. Белгілі бір логикалық функцияны азайту процесінде, әдетте, электронды схемалардың көмегімен оның минималды формасын қай негізде тиімді жүзеге асыратындығы ескеріледі. Карно карталарын қолдану арқылы логикалық функцияларды азайту Карта үлкен өрнектермен жұмыс істеудің салыстырмалы қарапайымдылығын және ықтимал жарыстарды жоюды қамтамасыз ететін коммутациялық (логикалық) функцияларды азайтудың Карно — графикалық әдісі. Бұл жұптасқан толық емес желімдеу және элементар сіңіру операциялары. Карно карталары функцияның сәйкесінше қайта құрылған ақиқат кестесі ретінде қарастырылады. Карно карталарын n-өлшемді буль текшесінің белгілі бір жалпақ сканері ретінде қарастыруға болады. Карно карталарын 1952 жылы Эдвард в. Вейч ойлап тапты және 1953 жылы "Bell Labs" физигі Морис Карно жетілдірді және цифрлық электрондық схемаларды жеңілдетуге көмектесуге арналған. Карно картасына логикалық айнымалылар ақиқат кестесінен беріледі және сұр код арқылы реттеледі, онда әрбір келесі Сан алдыңғы саннан тек бір разрядпен ерекшеленеді. SDNF немесе SCNF түрінде ұсынылған логикалық функцияларды азайтудың негізгі әдісі-жұптық толық емес желімдеу және элементар сіңіру операциясы. Жұптық желімдеу операциясы бірдей айнымалылары бар екі термин (терминдер) арасында жүзеге асырылады, олардың пайда болуы (түзу және кері) бір айнымалыдан басқа барлық айнымалыларға сәйкес келеді. Бұл жағдайда бір айнымалыдан басқа барлық айнымалыларды жақшадан шығаруға болады, ал жақшада қалған бір айнымалының тікелей және инверсиялық пайда болуы желімделеді. Мысалы: Сіңіру мүмкіндігі айқын теңдіктерден туындайды Осылайша, SDNF және SCNF-ті азайтудың негізгі міндеті-желімдеуге жарамды терминдерді іздеу, содан кейін сіңіру, бұл үлкен формалар үшін өте қиын міндет болуы мүмкін. Карно карталары мұндай терминдерді табудың көрнекі әдісін ұсынады. Өздеріңіз білетіндей, SDNF немесе SCNF түрінде ұсынылған N айнымалыларының логикалық функциялары құрамында 2N түрлі терминдер болуы мүмкін. Бұл терминдердің барлығы топологиялық тұрғыдан n–өлшемді текшеге тең құрылымды құрайды, кез-келген екі термин желімдеуге және сіңіруге жарамды. Суретте осы кестеге сәйкес келетін екі айнымалы функцияның қарапайым ақиқат кестесі көрсетілген 2 өлшемді текше (шаршы), сондай-ақ SDNF мүшелерін белгілейтін 2 өлшемді текше және терминдерді топтастыруға арналған баламалы кесте: Үш айнымалы функция жағдайында үш өлшемді текшемен күресу керек. Бұл күрделірек және көрнекі емес, бірақ техникалық тұрғыдан мүмкін. Суретте мысал ретінде үш айнымалының логикалық функциясы үшін ақиқат кестесі және оған сәйкес текше көрсетілген. Суреттен көріп отырғаныңыздай, үш өлшемді жағдай үшін терминдердің күрделі конфигурациялары мүмкін. Мысалы, текшенің бір бетіне жататын төрт термин екі айнымалының жұтылуымен бір терминге біріктіріледі: Жалпы алғанда, гиперкубтың бір k–өлшемді бетіне жататын 2K терминдер бір терминде бір-біріне жабысып, k айнымалыларын сіңіреді деп айтуға болады. Көптеген айнымалылардың логикалық функцияларымен жұмысты жеңілдету үшін келесі ыңғайлы әдіс ұсынылды. Терминдердің құрылымы болып табылатын текше суретте көрсетілгендей жазықтыққа жайылады. Осылайша, айнымалылар саны екіден көп логикалық функцияларды жалпақ кесте түрінде ұсыну мүмкіндігі пайда болады. Кестедегі терминдер кодтарының реті (00 01 11 10) екілік сандардың ретіне сәйкес келмейтінін және кестенің шеткі бағандарындағы ұяшықтар бір-біріне жақын орналасқанын есте ұстаған жөн. Сол сияқты төрт, бес немесе одан да көп айнымалылардың функцияларымен жұмыс істеуге болады. N=4 және N=5 кестелерінің мысалдары суретте келтірілген. Бұл кестелер үшін көршілес экстремалды бағандардың сәйкес жасушаларында және жоғарғы және төменгі жолдардың сәйкес жасушаларында орналасқан жасушалар екенін есте ұстаған жөн. 5 немесе одан да көп айнымалылар кестелері үшін 4х4 квадраттар үшінші өлшемде бір-бірінің үстінде болатындығын ескеру қажет, сондықтан екі көршілес 4х4 квадраттардың сәйкес жасушалары іргелес болып табылады және оларға сәйкес терминдерді бір-біріне жабыстыруға болады.
Карно картасы кез-келген айнымалылар үшін жасалуы мүмкін, бірақ бес айнымалыдан аспайтын айнымалылар санымен жұмыс істеу ыңғайлы. Шын мәнінде, Карно картасы — бұл 2 өлшемді түрде жасалған ақиқат кестесі. Ондағы сұр кодты қолданудың арқасында жоғарғы жол төменгі жаққа іргелес,ал оң жақ баған сол жаққа іргелес, яғни. Жол мен бағанның қиылысында ақиқат кестесінен тиісті мән қойылады. Карта толтырылғаннан кейін сіз азайтуға кірісе аласыз. Егер минималды DNF алу қажет болса, онда картада біз тек бірліктері бар жасушаларды қарастырамыз, егер KNF қажет болса, онда нөлдері бар жасушаларды қарастырамыз. Минимизацияның өзі келесі ережелерге сәйкес жүзеге асырылады (DNF мысалында): Біз іргелес жасушаларды біріктіреміз бірліктері бар аймаққа, бір аймақта 2n (N бүтін сан = 0... ) жасушалар болатындай етіп (шеткі жолдар мен бағандар бір-біріне іргелес екенін есте сақтаңыз), аймақта нөлдері бар жасушалар болмауы керек; 1. Аймақ осьтерге(осьтерге) симметриялы орналасуы керек (осьтер әр төрт жасуша арқылы орналасады); 2. Осьтерге(осьтерге) симметриялы орналасқан іргелес емес аймақтар бір-біріне біріктірілуі мүмкін; 3. Аймақ мүмкіндігінше үлкен болуы керек, ал аймақтардың саны мүмкіндігінше аз болуы керек; 4. Аймақтар қиылысуы мүмкін; 5. Жабудың бірнеше нұсқасы болуы мүмкін. Әрі қарай, біз бірінші аймақты аламыз және осы аймақта қандай айнымалылар өзгермейтінін көреміз, осы айнымалылардың конъюнктурасын жазамыз, егер өзгермейтін айнымалы нөлге тең болса, оның үстіне инверсия қоямыз. Біз келесі аймақты аламыз, бірінші және т.б. барлық аймақтар үшін бірдей нәрсені орындаймыз. Біз облыстардың конъюнкцияларын дизъюнкциямен біріктіреміз. Мысалы (2 айнымалыдағы карталар үшін):
KNF үшін бәрі бірдей, біз тек нөлдері бар жасушаларды қарастырамыз, бір аймақта өзгермейтін айнымалыларды дизъюнкцияларға біріктіреміз (инверсияларды бірлік айнымалылардың үстіне қоямыз), ал аймақтардың дизъюнкцияларын конъюнкцияға біріктіреміз. Бұл жағдайда минимизация аяқталды деп саналады. Сонымен, суреттегі Карно картасы үшін.1 DNF форматындағы өрнек келесідей болады: ҚҰФ форматында: жүктеу/скачать 192.71 Kb. Достарыңызбен бөлісу:
|