Цифрлық құрылғыларды логикалық жобалау. Цифрлық құрылғыларды логикалық жобалау негіздері. Цифрлы рылыларды логикалы жобалау негіздері. Буль алгебрасыны негізгі тсініктері
 Скачать 146.54 Kb.
|
|
F-r=(n-1) рангті терм. Сонымен терм рангін r=n -нен r=n-1 -ге дейін төмендетіледі. Бұл операция қажетінше қайталанады. Жапсыру операциясына қатыспайтын термдерді бастапқы импликанттар деп атайды. Дизъюнкция белгісімен байланысқа бастапқы импликанттар жиыны МҚДФ түрінде бола бермейді. Сондықтан алынған импликанттар жиыны кейбір бастапқы импликанттарды алып тастау жолымен ықшамдалады. Алып тасталған имплианттар функцияның тепе-теңдігін бұзбауы керек. Квайн әдісінің елеулі кемістігі жапсыру амалын қолдану үшін барлық термдерді қос-қостан салыстыру керектігінде. 1956 жылы Мак-Класки конъюнктивтік термдерді (  ) екілік айнымалылар жиынтығы түрінде жазуды ұсынды. Мұнда термге t-куб сәйекстендіріледі. Бұл термдердің епетейсіз жазылуынан айырып, жапсыру операциясын қолдану үстінде термдерді қос-қосап салыстыру санын қысқартуға мүмкіндік береді. Өйкені барлық  айнымалылар жиынтықтарын олардағы бірліктер санымен қиылыспайтын топтарға бөлуге болады, і-топқа і-бірліктері бар барлық жиынтықтар кіреді. Бұл жағдайда тек көршілес топтағы жиынтықтар бір-бірімен салыстырылады. (i-1) топ пен і топ; і топпен і+1 топ және т.с.с. көршілес емес топтарға кіретін жиынтықтар бір-бірімен кем дегенде екі бірліктермен өзгеше болады.Сондықтан олардың жапсырылу ықтималдығы 0-ге тең. Төменде Квайнның Мак-Класки жетілдірген (Квайн-Мак-Класки әдісі) кезеңдерге бөлінген формальді алгоритмі баяндалады. 1-кезең. Бастапқы импликантты табу. ЖҚДФ-ға кіретін барлық {m} термдерді екілік айнымалылар жиынтығы  түрінде (0-кубтар К0 кешені) топтап олардағы бірліктер санына қарай жазып алады. Көршілес екі жиынтыққа жапсыру амалы қолданылады. Нәтижелерді топтап 1-кубтар К1 кешені түрінде жазылады. Көршілес топтарға (К1) кіретін 1-кубтар бір-бірімен салыстырып 2-кубтар түзіледі. Бұл салыстыру және жапсыру амалдары t кубтардың Kt кешентерін алғанша орындалады. Олар бір-бірімен жапсырылуы тиісті емес. Жапсыру амалдарына қатыспаған кубтар бастапқы импликанттар {l} жиынтығын құрады.2-кезең. Импликанттық матрица құру. Матрицаның жолдарын бастапқы импликанттармен, ал бағандарын алғашқы (негізгі) импликанттармен (0-кубтармен) белгілейді. Егер бастапқы импликантта  терміне енсе  онда і жолымен j баған қиылысқан жеріне белгі қойылады.3-кезең. Мәнді импликанттарды табу. Егер импликанттық матрицаның қайсыбір бағынында тек бір ғана белгі болса, онда осы белгіге сәйкес келетін алғашқы импликантта мәнді болып табылады, өйткені онсыз берілген термдердің барлық жиынтығын {m} алуға болмайды. Мәнді импликанттар міндетті түрде МҚДФ құрамына кіруі керек. Мәнді импликанттармен жабылатын термдерге сәйкес келетін бағандар және мәнді импликантты жолдар матрицадан сызылып тасталады. 4-кезең. Басы артық бастапқы импликанттарды сызып тастау. Алдыңғы кезеңдер орындалған соң, импликанттық матрицада бірде-бір белгісі жоқ жолдар пайда болуы мүмкін. Мұндай жолдарға сәйкес келетін бастапқы импликанттар әрі қарай қаралмайды, өйткені олар матрицадағы қалған алғашқы термдерді жаба алмайды. 5-кезең. Минималь жабын алу. Импликанттық матрицаның жолдары мен бағандарын сызып тастағанмен алынған матрица зерттеледі. Қалған жолдар ішінен қалған алғашқы термдерді тегіс жабатын бастапқы импликанттар жиынтығы іріктелініп алынады. Мұндай импликанттардан әріп сандарын аз жиынтық таңдалынып алынады. Оларға мәнді импликанттарды қосып, мөлшері әр-түрлі куб түрінде жазылған бастапқы импликанттардан рангі әр түрлі конъюнктивтік термдерге көшіріледі. Соңғыларды дизъюнкция белгісімен біріктіріп МҚДФ алынады. Мысал. Квайн-Мак-Класки әдісімен f(x1,x2 ,x3 ,x4) логикалық функциясының МҚДФ табу керек: f(x1,x2,x3 x4)= =  Шешуі. К0 кешені  бірнеше топқа бөлінеді: |