Минимизација на кола за Булови функции

Од Википедија — слободната енциклопедија
Прејди на прегледникот Прејди на пребарувањето

Во Буловата алгебра, минимизацијата на кола е проблем на добивање на најмалото логичко коло (Булова формула) кое претставува дадена Булова функција или таблица на вистинитост. Долго време се претпоставувало дека проблемот на неограничена минимализација на коло е -комплетно,резултат кој конечно бил докажан во 2008 година, но постојат ефективни методи, како што се Карноовите мапи и Квин-Меккласки алгоритмот кои го олеснуваат процесот.

Цел[уреди | уреди извор]

Проблемот со сложеното коло (односно коло со многу елементи, како што се логичките порти) е тоа што секој елемент зазема физички простор за неговото спроведување, како и тоа што се трошат многу време и пари за негово создавање. Миниизацијата на колото може да биде една форма на логичка оптимизација која се користи за да се намали областа на комплексна логика во интегрираните кола

Пример[уреди | уреди извор]

Иако постојат многу начини да се минимализира (намали) колото, овој е пример кој ја минимализира (или поедноставува) Буловата функција. Треба да се забележи дека Буловата функција, извршена со помош на колото е директно поврзана со алгебарскиот израз од кој се имплементира . функцијата. Да го разгледаме колото кое се користи за да се претстави .Очигледно е дека тука се употребени две негации, две конјункции и дисјункција. Тоа значи дека за да се изгради колото потребни се два инвертора, две И порти и ИЛИ порта.

Колото може да се поедностави со примена на логички идентитети или со помош на интуиција. Поради тоа што примерот укажува дека А е точно кога Б е неточно или обратно, може да заклучиме дека тоа едноставно значи дека  . Во однос на логичките врати, нееднаквоста едноставно значи ИКСИЛИ порта(исклучиво ИЛИ). Според тоа, .Двете кола дадени подолу се еквивалентни:

Circuit-minimization.svg

Дополнително може да ја проверите точноста на резултатот со користење на таблица на вистинитост.

Литература[уреди | уреди извор]

  • De Micheli, Giovanni. Synthesis and Optimization of Digital Circuits. McGraw-Hill, 1994, Part III, Logic-Level Synthesis and Optimization
  • Zvi Kohavi, Niraj K. Jha. Switching and Finite Automata Theory. 3rd ed. Cambridge University Press. 2009. ISBN 978-0-521-85748-2, chapters 4–6
  • Knuth, Donald E. (2010). The Art of Computer Programming. chapter 7.1.2: Boolean Evaluation. 4A. Addison-Wesley. стр. 96–133. ISBN 0-201-03804-8.
  • Multi-level minimization part I, partII: CMU lectures slides by Rob A. Rutenbar