Карноова карта — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
м Разне исправке; козметичке измене |
||
Ред 1:
[[
'''Карноова карта''', '''Карноова мапа''' или скраћено '''К-мапа''', је метод за упрошћавање израза [[Булова алгебра|Булове алгебре]]. [[Морис Карно]] је измислио овај метод 1953 као побољшање Веичевог дијаграма. Карноова мапа смањује потребу за напорним калкулацијама тако што користи људску способност препознавања образаца. Она такође дозвољава брзу идентификацију и елиминацију потенцијалних проблема са тркама услова.
Потребни Булови резултати су смештени из таблице истинитости у дводимензионалну матрицу где су ћелије поређане у
Карноове мапе се користе да упрошћавање логичких проблема у реалном животу тако да се они могу имплементирати тако да захтевају минималан број логичких кола. Изрази суме производа се увек могу имплементирати коришћењем логичког кола И која се спајају у логичка кола ИЛИ, и производ сума се може имплементирати користећи логичка кола ИЛИ која се спајају у логичка кола И.<ref>{{cite web|title=Simplifying Logic Circuits with Karnaugh Maps|url=http://www.utdallas.edu/~dodge/EE2310/lec5.pdf|publisher=The University of Texas at Dallas|accessdate = 7.
== Пример ==
Карноове мапе се користе као процес упрошћавања функција [[Булова алгебра|Булове алгебре]]. Узмимо Булову или [[Бинарни систем|бинарну]] функцију описану у следећој [[Таблица истинитости|таблици истинитости]].
Ред 66:
Следе две различите нотације које описују исту функцију у неупрошћеном облику Булове алгебре, користећи променљиве <math>A</math>, <math>B</math>, <math>C</math>, <math>D</math> и њихове инверзне вредности.
* <math>f(A, B, C, D) = \sum_{}m(6, 8, 9, 10, 11, 12, 13, 14)</math> Напомена: Вредности у суми су оне које имају излаз 1 у таблици истинитости.
* <math>f(A, B, C, D) = (\overline{A}BC\overline{D}) + (A\overline{B}\,\overline{C}\,\overline{D}) + (A\overline{B}\,\overline{C}D) + (A\overline{B}C\overline{D}) + (A\overline{B}CD) + (AB\overline{C}\,\overline{D}) + (AB\overline{C}D) + (ABC\overline{D})</math>
=== Карноова мапа ===
{| style="float:right"
| [[
|}
{| style="float:right"
| [[
|}
Ред 87:
Мрежа је [[Торус|торусног]] облика што значи да се поља која се налазе на ивици матрице спајају са другим на крајевима матрице (видети слику). Ћелије скроз десно су заправо суседне са ћелијама које су скроз лево. То такође важи и за ћелије које се налазе скро на врху и на дну. Тако да <math>A\scriptstyle \overline{D}</math> може да буде валидан израз – он укључује ћелије 12 и 8 на врху, и спаја их са ћелијама 10 и 14 на дну – као и <math>\scriptstyle\overline{B}\,\overline{D}</math>, који укључује 4 ћошка.
=== Решење ===
[[
Када је Карноова мапа конструисана и суседне јединице повезане у правоугаоне групе, минимално алгебарско решење се може наћи посматрањем променљивих које остају у истим групама.
За црвену групу:
* Променљива <math>A</math> је иста и једнака је јединици у целој групи, што значи да треба да буде укључена у алгебарску репрезентацију израза.
* Променљива <math>B</math> не одржава исто стање, већ се мења из јединице у нули, и она треба да буде искључена.
* Променљива <math>C</math> се не мења. Она је увек нула, чак и њен комплемент, што значи да треба да буде укључена.
* И променљива <math>D</math> се мења, што значи да је искључујемо.
Значи, први део израза у Буловој суми производа је израз <math>A\overline{C}</math>.
Ред 115:
Такође би било могуће доћи до овог решења пажљивом употребом аксиома Булове алгебре, али време које је потребно за тако нешто расте експоненцијално.
=== Изнверз ===
Инверзна функција се решава на исти начин, с тим што се у том случају групишу нуле уместо јединица.
Три израза искоришћена да покрију инверзну функцију су показана са сивим правоугаоницима са различитим бојама оквира:
* Браон—<math>\overline{A}\,\overline{B}</math>
* Златна—<math>\overline{A}\,\overline{C}</math>
* Плава—<math>BCD</math>
Што нам даје инверзну функцију:
Ред 131:
:<math>F = \left(A + B\right)\left(A + C\right)\left(\overline{B} + \overline{C} + \overline{D}\right)</math>
=== Небитна стања ===
[[
Карноове мапа такође дозвољавају лаку минимизацију функција за чије таблице истинитости које садрже небитна стања. Небитно стање је комбинација улаза за које дизајнер не жели да зна шта је излаз. Управо зато, те случајеве можемо искористити и као нуле и као јединице, шта нам више одговара. Оне се углавном означавају са X или d.
Ред 142:
:<math>F = A + BC\overline{D}. \, </math>
Приметите да је први израз <math>A</math>, а не <math>A\overline{C}</math>. У овом случају смо изгубили израз зелене групе,
Случај за инверзну функцију је следећи:
:<math>\overline{F} = \overline{A}\overline{B} + \overline{A}\overline{C} + \overline{A}D</math>
== Трке услова ==
=== Елиминација ===
Карноове мапе су корисне за детектовање и елиминацију трка услова.
* У примеру изнад, потенцијална трка услова постоји када је ''C'' једнако 1 и ''D'' једнако 0, ''A'' је 1, и ''B'' се мења из 1 у 0 (померајући се са плавог у зелено стање). За овај случај, излаз је дефинисан да остане непромењен у 1, али зато што овај прелаз није покривен одговарајућим изразом, постоји потенцијал за краткотрајни квар (тренутна промена излаза у 0).
* Други потенцијални краткотрајни квар у истом примеру је теже приметити. Када је ''D'' једнако 0 и ''A'' и ''B'' су 1, са ''C''-ом које се мења из 1 у 0 (померањем из плавог у црвено стање). У овом случају се краткотрајни квар обавија око врха и дна мапе
[[
Да ли ће се ови краткотрајни кварови јавити, зависи од физичке природе имплементације, и да ли треба да бринемо о њима зависи од примене.
Ред 165:
Слично, додатни израз <math>\overline{A}D</math> се мора додати на инверзну функцију да би се елиминисала потенцијална трка услова. Користећи Де Морганов закон добијамо још један израз производа сума ''F'', али са новим фактором <math>\left(A + \overline{D}\right)</math>.
=== Примери мапа са 2 променљиве ===
Следе примери са свим могућим Карноовима мапама са 2 променљиве. Поред сваке се
<gallery>
File:K-map 2x2 none.svg | <math>\sum_{}</math>m(0); ''K'' = 0
Ред 188:
== Литература ==
{{reflist}}
Ред 197:
* [http://gandraxa.com/detect_overlapping_subrectangles.xml Detect Overlapping Rectangles], by Herbert Glarner.
* [http://www.sccs.swarthmore.edu/users/06/adem/engin/e15/lab1/ Using Karnaugh maps in practical applications], Circuit design project to control traffic lights.
* [http://fullchipdesign.com/kmap2v.htm K-Map Tutorial for 2,3,4 and 5 variables
* [http://www.generalnumbers.com/karnaugh_application1.html Karnaugh Map Example]
| |||