Программа Для Минимизации Карт Карно
Программа «Минимизация. И карты Карно, минимизацию.
Важнейшим вспомогательным средством для определения наиболее простой логической функции является карта Карно. Это не что иное, как измененная запись таблицы истинности. В этом случае значения аргументов не просто записываются рядом друг с другом, а размещаются по горизонтали и вертикали таблицы, деля ее, наподобие шахматной доски, на отдельные квадраты. При четном количестве аргументов половину из них записывают по горизонтали, а половину – по вертикали. При нечетном числе аргументов по горизонтали размещается на один аргумент больше, чем по вертикали.
Порядок размещения различных комбинаций значений аргументов следует выбирать таким, чтобы при переходе от одной ячейки к соседней изменялся лишь один аргумент. В эти ячейки заносят те значения логической функции, которые соответствуют значениям аргументов.
В качестве примера (рис. 3.1) приведена таблица истинности и соответствующая ей карта Карно для функции И (конъюнкции). Таблица истинности (а) и соответствующая ей карта Карно (б) для функции И (конъюнкции) Карта Карно является упрощенной формой записи таблицы истинности, поэтому на ее основе можно составить СовДНФ искомой логической функции, пользуясь описанным выше методом. Преимуществом карт Карно является простота обнаружения возможных упрощений логической функции. Рассмотрим это на примере, представленном на рис. Таблица истинности (а) и соответствующая ей карта Карно (б) для функции F В первую очередь при составлении СовДНФ следует, как указывалось выше, составить конъюнкции всех аргументов для каждой конституенты единицы, т.е.
Для каждой ячейки, в которой стоит единица. Для ячейки, расположенной в левом верхнем углу, получаем: для ячейки, расположенной правее: Когда будет составлена дизъюнкция всех конституент единицы, помимо других в ней встретится и такой фрагмент: Он упрощается следующим образом: Отсюда следует общее правило упрощения логических функций для карт Карно: если в двух, четырех, восьми и т.д. Ячейках, ограниченных прямоугольным или квадратным контуром, стоят только единицы, можно записывать непосредственно конъюнкцию для всей этой группы, причем в нее должны входить лишь те аргументы, которые остаются неизменными для всех ячеек данной группы. Таким образом, в этом примере конъюнкция для группы II, состоящей из двух ячеек, равна что соответствует ранее полученной функции. В одну группу связываются также те ячейки, которые находятся на левом и правом краях одной строки или в верхней и нижней частях одного столбца.
Для группы I, состоящей из четырех ячеек, можно записать: Для группы III, имеющей квадратную форму и состоящей также из четырех ячеек, получим следующую конъюнкцию: Еще одна единица осталась в правом верхнем углу. Она может быть связана, например, с единицей в нижней части рассматриваемого столбца в группу из двух ячеек. Другая возможность состоит в объединении единиц, находящихся на левом и правом краях первой строки. Однако если принять во внимание, что в каждом углу карты Карно находится единица, то можно найти простейшее решение. Связывая эти единицы в одну четырехэлементную группу, получим: Таким образом, с помощью карты Карно можно найти наипростейший вариант логической функции F: Алгебра логики и цифровые электронные схемы Возникает вопрос: как можно представить логические функции с помощью электрических схем? Так как логические переменные могут иметь только два дискретных значения, следует обратить внимание на схемы, которые могут находиться в двух легко различимых состояниях. Такими схемами являются электрические переключающие схемы, выполняемые на основе транзисторных ключей.
Для представления логических переменных в цифровой схемотехнике используют электрическое напряжение, имеющее два различных уровня: высокий, близкий но уровню к напряжению питания (транзистор закрыт), и низкий, близкий к потенциалу корпуса (транзистор открыт). Этим уровням можно поставить в соответствие состояния логических '1' и '0'. Если высокий уровень напряжения соответствует логической '1', а низкий – '0', такая система обозначений называется позитивной логикой. В противном случае (высокий – '0', низкий – '1') система называется негативной логикой. В соответствии с тремя операциями алгебры логики в схеме цифровых устройств используют следующие логические элементы, входные переменные которых часто обозначают через xi, а выходные через. 1) элемент И – схема логического умножения, конъюнктор (рис. 3.3, а); 2) элемент ИЛИ – схема логического сложения, дизъюнктор (рис.
3.3, б); 3) элемент НЕ – схема логического отрицания, инвертор (рис. Условные обозначения элементов цифровой логики: а – И; б – ИЛИ; в – НЕ; г – И-НЕ; д – ИЛИ-НЕ Этот набор элементов называют основным базисом или основной функционально полной системой элементов.
Последнее означает, что с помощью этих элементов можно создать схему, осуществляющую любую сколь угодно сложную логическую операцию. Помимо этих элементов в интегральной схемотехнике часто применяются логические схемы, выполняющие операции И-НЕ (рис. 3.3, г) и ИЛИ-HE (рис.
Информация, поступающая в цифровое устройство, представляет дискретный (т.е. Состоящий из нулей и единиц) сигнал (код).
На передачу сигнала отводится конечный отрезок времени, называемый тактом работы устройства. Если за один такт в устройство передается один из разрядов двоичного числа, то устройство работает с последовательным кодом, если же за один такт передается все двоичное число одновременно, то устройство работает с параллельным кодом. В общем случае на вход цифрового устройства поступает множество двоичных переменных X ( х1; х2., хn ), а с выхода снимается множество двоичных переменных Y ( y1, у2. Ys ). При этом устройство осуществляет (реализует) определенную связь (логическую функцию) между входными и выходными переменными.
Цифровые устройства делят на комбинационные и последовательностные. В комбинационных устройствах (рис. 3.4, а) значения Y в течение каждого такта определяются значениями X только в этот же такт. Такие устройства состоят из логических элементов.
В последовательностных устройствах (рис. 3.4, б) значения Y определяются значениями X как в течение рассматриваемого такта, так и существовавшими в ряде предыдущих тактов. Для этого в последовательностных устройствах кроме логических должны быть еще и запоминающие элементы. При этом память устройства может охватывать не бесконечно большое, а конечное число тактов.
Поэтому цифровые (дискретные) устройства с памятью называют конечными автоматами, которыми являются все ЭВМ. Подобно входным и выходным переменным, переменные, сохраняемые в памяти устройства, тоже двоичные и зависят от значений входных переменных в предыдущих тактах. Любое дискретное устройство и составляющие его элементы и узлы осуществляют ту или иную булеву функцию над двоичными входными переменными. Известно, что булеву функцию можно задать тремя способами: содержательно (путем словесного описания), таблично и алгебраически. Наиболее часто для описания работы дискретных устройств пользуются табличной формой. Таблицы, показывающие связь между входными и выходными переменными комбинационных устройств, так же как и в алгебре логики, называют таблицами истинности, а алгебраическая форма этих связей представляет систему алгебраических функций: В последовательностных устройствах выходные переменные yi; зависят не только от входных сигналов xk, но и от сигналов элементов памяти, поступающих в этот же такт. При анализе и синтезе последовательностные устройства делят на комбинационную часть и элементы памяти.
Обозначим два следующих друг за другом такта работы автомата как t и (t + 1). Состояние элементов памяти в ( t + 1)-й такт определяется множествами как входных сигналов, так и сигналов на выходах элементов памяти в предыдущий такт ί, т.е.
Это выражение называют функцией переходов. Структура комбинационного (а) и последовательностного (б) цифровых устройств Функции переходов и выходов последовательностных устройств могут выражаться таблицами переходов и выходов.
Поскольку эти таблицы описывают работу последовательностного устройства, т.е. Процесс его переключения, они называются также таблицами переключений. Реальные электрические схемы всегда инерционны, и между моментом изменения сигналов на входе схемы и моментом появления соответствующего сигнала на выходе всегда проходит пусть и небольшое (наносекунды), но конечное время. Таблицы и алгебраические функции описывают лишь установившийся режим, т.е.
Программа Для Скриншотов
В динамической же части такта связь между переменными может отличаться от режима статики. Это явление называют переходным состоянием (гонками в автоматах). Если его не учитывать, то спроектированное устройство может работать с ошибками. Для борьбы с гонками в автоматах используют синхронизацию работы электронных схем. В соответствии с этим цифровые устройства разделяются на асинхронные и синхронные. В асинхронных изменение входных сигналов сразу влечет за собой соответствующее изменение выходных сигналов (конечно, после окончания переходных процессов в электронных схемах).
Программа Для Минимизация Карт Карно
В синхронных изменение выходных сигналов происходит только после подачи синхронизирующих (тактовых) импульсов, управляющих работой автомата. Комбинационные части автоматов являются асинхронными. Значит, на их выходе могут появляться гонки, которые приводят к сбоям (ошибкам), если элементы памяти автомата будут управляться непосредственно выходными сигналами комбинационной части. Такие автоматы называют асинхронными, и в них существует опасность сбоев.
Программа Для Рисования
В синхронных автоматах элементы памяти изменяют свое состояние только с приходом внешнего тактового импульса, т.е. Когда все переходные процессы в комбинационной части закончатся и на ее выходах установятся сигналы, соответствующие входным. Поэтому опасности сбоев из-за гонок в таких автоматах нет.