Учебно-методический комплекс дисциплины обсужден на заседании кафедры информационной безопасности «7»

Сформулируем правила получения МДНФ функций с помощью карт Вейча. Все клетки, содержащие 1, объединяются в замкнутые области. При этом каждая область должна представлять собой прямоугольник с числом клеток 2k, где k = 0, 1, 2, ... Таким образом, допустимое число клеток в области – 1, 2, 4, 8,... Области могут пересекаться и одни и те же клетки могут входить в разные области. Затем проводится запись выражения МДНФ функции. Каждая из областей в МДНФ представляется членом, число букв в котором на k меньше общего числа аргументов функции n (т. е. равно n – k). Каждый член МДНФ составляется лишь из тех аргументов, которые для клеток соответствующей области имеют одинаковое значение (без инверсии либо с инверсией). Таким образом, при охвате клеток замкнутыми областями следует стремиться, чтобы число областей было минимальным (при этом минимальным будет число членов в МДНФ функции), а каждая область содержала возможно большее число клеток (при этом минимальным будет число букв в членах МДНФ функции). Рассмотрим минимизацию с помощью карты Вейча функции трех аргументов, представленной табл. 3.13. Все клетки, содержащие 1, охватываются двумя областями. В каждой из областей 21 клеток. Таким образом, для них n – k = 3 – 1 = 2 и эти области в МДНФ будут представлены членами, содержащими по две буквы. Первой обласги соответствует член x1? x2 (аргумент x3 здесь не присутствует, так как для одной клетки этой области он имеет значение без инверсии, для другой — с инверсией); второй области соответствует член . Следовательно, МДНФ функции Рассмотрим пример минимизации функции четырех аргумен. тов. заданной табл. 3.14. Первая и четвертая области имеют по две клетки, для них n – k = 4 – 1 = 3. Эти области будут в МДНФ представлены членами, содержащими по три буквы. Вторая и третья области содержат по четыре клетки и в МДНФ выражаются членами, содержащими по две буквы (n – k = 4 – 2 = 2). Минимальная ДНФ функции имеет вид При построении замкнутых областей допускается сворачивание карты в цилиндр с объединением се противоположных граней. В силу этого крайние клетки строки или столбца таблицы рассматриваются как соседние и могут быть объединены в общую область, Иллюстрацию этого приема проведем на примере функции, представленной табл. 3.15, Минимальная ДНФ функции. В силу допустимости такого сворачиванья карты вдоль горизонтальной и вертикальной осей, например, клетки, расположенные н четырех углах карты функции четырех переменных, оказываются соседними и могут быть объединены в одну область. Покажем это на примере минимизации функции, заданной табл. 3.16. Минимальная ДНФ функции Для получения МКНФ функции замкнутыми областями охватываются клетки с нулевыми значениями функции, и при записи членов логического выражения берутся инверсии аргументов, на пересечении которых находятся области. Так, для функции, приведенной в табл. 3.17, МКНФ Таблица 3.17 До сих пор здесь рассматривались логические функции с числом аргументов до четырех. Представление функции и минимизация ее с помощью карт Вейча усложняются, если число аргументов больше четырех. В табл. 3.18 показано представление с помощью карт Вейча функции пяти аргументов. Таблица истинности здесь состоит из двух карт, каждая из которых представляет собой карту четырех переменных. Одна из них соответствует x5 = 1, другая – x5 = 0, Эти карты можно мысленно представить себе расположенными одна над другой (рис. 3.29). При этом области охвата клеток могут быть трехмерными, т. е. одной областью могут охватываться клегки двух карт. Для приведенной в табл. 3.18 функции МДНФ равна Для минимизации функций с числом аргументов, большим пяти, карты Вейча оказываются неудобными. Минимизация таких функций может быть выполнена методом Квайна. Синтез не полностью заданных логических функций По условиям работы логического устройства может оказаться, что некоторые наборы значений аргументов являются запрещенными для данного устройства и никогда не могут появляться на его входах. В этом случае функция оказывается заданной не на всех наборах аргументов. Такие функции будем называть не полностью заданными. При синтезе логического устройства, реализующего не полностью заданную функцию, допустимо произвольно задаваться значениями функции на запрещенных наборах аргументов. При этом в заннсимости от способа задания этих значений функции минимальная фирма может оказаться простой или более сложной. Таким образом, возникает проблема целесообразного доопределения функции на запрещенных наборах аргументов. Может быть использован следующий способ получения минимальной формы не полностью заданной функции f: а) записывается СДПФ (СКИФ) функции f0. полученной из f путем задания значения 0 (значения 1 и случае СНКФ) на всех запрещенных наборах аргументов; б) записывается СДНФ (СКИФ) функции f1, полученной из f путем задания значения 1 (значения 0 в случае СКНФ) на всех запрещенных наборах аргументов; в) функция f1 приводится к сокращенной форме (к форме, содержащей все простые имплнканты); г) составляется импликантнзя таблица из всех членов функции f0 и простых импликант функции f1; д) искомая минимальная форма составляется из простых импликант функции f1, поглощающих все члены СДНФ (СКНФ) функции f0. Рассмотрим применение данного метода к минимизации не полностью заданной функции, приведенной в табл. 3.19. Записываем логическое выражение функции f0 в СДНФ Записываем СДНФ функции f1 Методом Квайна приводим функцию f1 к сокращенной форме: Составляем импликантную таблицу (табл. 3.20). Таблица 3.19 x1 0 0 0 0 1 1 1 1 x2 0 0 1 1 0 0 1 1 x3 0 1 0 1 0 1 0 1 f(x1,x2,x3) * 0 1 * 1 * * 1   Таблица 3.20 ^ Простые импликанты функции f1 Члены СДНФ X X X X X X Минимальная форма логического выражения функции может быть получена исключением любой из трех простых импликант Рассмотрим минимизацию той же функции методом карты Вейча (табл. 3.21). При минимизации функции данным методом следует на запрещенных наборах аргументов задавать функции такие значения, при которых клетки со значением 1 (либо 0) охватываются минимальным числом областей с максимальным числом клеток в каждой из областей. Применительно к рассматриваемся функции такое доопределение функции может быть осуществлено тремя различными способами, представленными в табл. 3.22. Они приводят к полученным выше выражениям МДНФ функции. Синтез логических устройств с несколькими выходами Пусть синтезируемое логическое устройство имеет п входов и т выходов (рис. 3.30). На каждом из выходов должна быть сформирована определенная функция входных переменных. Эта задача могла бы быть решена синтезированием раздельно действующих узлов, каждый из которых реализовывал бы определенную выходную функцию. Однако, если даже каждый из этих узлов будет построен минимальным образом, в целом логическое устройство может оказаться не минимальным. Действительно, такое устройство могло бы быть подвергнуто минимизации путем использования общих элементов и нескольких устройствах, реализующих различные выходные функции. Из этих соображений принадлежность каждой из выходных функций к минимальной форме не является условием получения минимального в целом устройства. При минимизации устройств и целей некоторые из функций могут оказаться представленными в неминимальной форме. Принцип получения минимальной формы устройства сводится к нахождению минимального набора членов с минимальным числом входящих в них букв, достаточного для получения всех формируемых устройством функций. Метод построения минимальных логических устройств с несколькими выходами рассмотрим на примере реализации устройства, способ функционирования которого задан табл. 3.23. Записываем наборы аргументов, на которых хотя бы одна из выходных функций имеет значение 1, Рядом в таблице в качестве признака записываем функции, принимающие значения 1 при данном наборе аргументов (табл. 3.24). рис 3.24 Затем проводим операцию склеивания и получающиеся при этом члены заносим в табл. 3.25, рядом с членами записываем признаки в виде функций, общих в признаках той пары членов табл. 3.24, склеиванием которых они получены. Так склеивание членов табл. 3.24 и Приводит в табл. 3.25 к члену ; склеивание членов и приводит к и т. д. Таблица 3.23 X1 0 0 0 0 1 1 1 1 X2 0 0 1 1 0 0 1 1 X3 0 1 0 1 0 1 0 1 f1(x1,x2,x3) 0 1 0 1 0 0 1 1 f2(x1,x2,x3) 0 0 1 0 1 1 0 0 f2(x1,x2,x3) 0 1 1 1 1 1 0 0 Таблица 3.25 f1f3 f3 f3 f1 f2f3 f1 Не проводится операция склеивания над членами, в признаках которых не имеется общих функций. Далее проводится операция поглощения членами табл. 3.25 членов табл. 3.24. Операция поглощения может проводиться лишь над членами, имеющими одинаковую комбинацию функций в признаках. Указанные операции склеивания и поглощения повторяются, пока их проведение оказывается возможным. Затем составляется импликантная таблица (табл. 3.26). Определяется набор импликант, обеспечивающий перекрятие всех столбцов импликантной таблицы. Этот набор импликант приведен в табл. 3.27. Записываем логические выражения для выходных функций, составленные из этих импликант, в признаках которых содержатся заданные функции: Таблица 3.26 f1 f3 f2 f3 f1 f3 f2 f3 f2 f3 f1 f1 (f2f3) X X (f1f3) X X X X (f3) X X (f3) X X (f1) X (f2f3) X X X X (f1) X X Легко убедиться, что выражение для функции не является минимальным. Минимальная для этой функции форма Однако замена в выражении функции f3 члена членом невыгодна, так как член присутствует и в выражении f2 и он должен быть сформирован для этой функции. На рис. 3.31 приведена функциональная схема устройства, обеспечивающего заданное табл. 3.23 функционирование. Как нидно из схемы, ряд элементов участвует одновременно в формировании нескольких выходных функций. рис 3.31 Синтез логических устройств в базисе ИЛИ_НЕ и И-НЕ Построение логического устройства на элементах ИЛИ-НЕ может быть выполнено при следующей последовательности действий: заданная функция минимизируется с получением МКНФ; производится запись полученного логического выражения через операции ИЛИ-НЕ. Рассмотрим последовательность синтеза на примере построения логического устройства, реализующего функцию, приведенную в табл. 3.28. Для минимизации функции воспользуемся методом Вейча. В табл. 3.29 приведена карта Вейча для рассматриваемой функции. Таблица 3.28 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 0 1 1 0 1 Минимальная КНФ функции Для перехода от базиса И, ИЛИ, НЕ, в котором представлено полученное логическое выражение, к базису ИЛИ-НЕ проводим следующие действия: дважды инвертируем правую часть выражении проводим преобразование по формуле де Моргана записываем выражение с использованием символа операции ИЛИ-НЕ Заметим, что в (3.18) наличие поставленных скобок обязательно, иначе исказится функция. Построенная в соответствии с (3.18) схема логического устройства приведена на рис. 3.32. рис 3.32 рис 3.33 Методика синтеза устройства в базисе И-НЕ сходна с рассмотренной выше методикой синтеза в базисе ИЛИ-НЕ. Имеющиеся особенности рассмотрим на примере построения с использованием элементов И-НЕ логического устройства, реализующего функцию, заданную таблицей истинности (табл. 3.28). Минимизируем функцию. В отличие от синтеза в базисе ИЛИ-НЕ, при котором в процессе минимизации получают МКНФ функции, при синтезе в базисе И-НЕ должна быть получена МДНФ функции. Минимизацию проведем с помощью карты Вейча (табл. 3.30). Минимальная ДНФ функции Дважды инвертируем правую часть выражения Проводим преобразование по формуле де Моргана Записываем выражение с использованием символа операции И-НЕ Выражению (3.20) соответствует схема, приведенная на рис. 3.33  Некоторые особенности построения схем логических устройств Построенная структурная схема логического устройства может содержать элементы с разным числом входов. Так, в схеме на рис. 3.33 используются, кроме инверторов, элементы И-НЕ с двумя и тремя входами. В выпускаемых промышленностью сериях элементов обычно предусматриваются элементы с разным числом входов. Поэтому для построения устройств в большинстве случаев могут быть использованы элементы точно с тем же числом входов, какое требуется в отдельных элементах структурной схемы. Иногда по разным соображениям приходится использовать в схеме элементы, число входов у которых больше или меньше чем то, которое требуется при рассмотренных выше способах синтеза устройств. Ниже рассматриваются возникающие в этих случаях особенности построения устройств. Рассмотрим использование элементов, имеющих избыточное число входов. Для определенности примем, что элементы имеют три входа, причем для подачи входных переменных требуется лишь два входа. Избыточный вход мог бы быть оставлен свободным (не подключенным к каким-либо цепям), как это показано на рис. 3.34,а. Однако для уменьшения влияния наводимых на этот вход помех нежелательно неиспользуемый вход оставлять свободным. При этом возможны следующие способы его включения. Неиспользуемый вход может быть подключен к любому из используемых входов (рис. 3.34,б). Недостаток такого способа соединения состоит в следующем. Объединение входов приводит к тому, что к выходу источника входного сигнала (т. е. к выходу предыдущего элемента, с которого сигнал подается на вход данного элемента) оказывается подключенным большее число входов элемента. Такое возрастание нагрузки вызывает увеличение задержки распространения сигнала, снижение быстродействия элемента. Поэтому наиболее удачным следует считать способ, при котором на неиспользуемый вход подается логическая константа 0 или 1 (т. е. потенциал, соответствующий логической константе 0 либо 1). Такой способ соединения показан на рис. 3.34,в. Здесь на свободные входы элементов ИЛИ и ИЛИ-НЕ подается постоянный потенциал уровня, соответствующего лог. 0, а для элементов И и И-НЕ – потенциал уровня, соответствующего лог. 1. Теперь рассмотрим более сложный случай построения устройства на элементах с недостающим числом входов. рис 3.34 На рис. 3.35 показан способ реализации 3х буквенного члена логического выражения функции на различных типах элементов с двумя входами. рис 3.35 В логическом выражении может оказаться несколько членов с числом букв, превышающим число входов элементов. В этом случае для уменьшения числа используемых элементов следует провести соответствующее преобразование групп членов. Этот прием покажем на примере реализации рассмотренной выше логической функции (3.20). Пусть требуется построить устройстоо, реализующее функцию (3.20) на двухвходовых элементах И-НЕ. Обратимся к (3.19). В нем сгруппируем два последних члена, вынеся за скобки x3: К полученному выражению применим формулу де Моргана Пользуясь формулой де Моргана, можно преобразовать к виду После подстановки в предыдущее выражение получим Запишем данное выражение через операцию И-НЕ: Построенная в соответствии с этим выражением схема приведена на рис. 3.36. Из сравнения схем ва рис. 3.33 и 3.36 видно, что синтез устройств на элементах с уменьшенным числом входов вызвал необходимость применения большего числа элементов. Изложенным приемом удается пользоваться не всегда. Например, им невозможно воспользоваться в случаях, когда члены МДНФ не содержат общих букв. При этом необходимое преобразование логического выражения достигается с использованием тождественного соотношения: Покажем справедливость этого тождества рис 3.36 Пусть требуется синтезировать с использованием двухвходовых элементов И-НЕ логическую функцию, МДНФ которой представляется выражением . Записываем выражение через операцию И-НЕ: Применяя к данному выражению преобразование (3.21), получим Построенная в соответствии с данным выражением функциональная схема логического устройства приведена на рис. 3.37. Рассмотрим реализацию на двухвходовых элементах И-НЕ функции Перейдем к операции И-НЕ и затем применим соотношение (3.21): Аналогичное (3.21) преобразование для случая, когда предполагается реализация логического устройства в базисе ИЛИ-НЕ, имеет вид Покажем справедливость этого тождественного соотношения: рис 3.37 Базовые логические элементы(Вентили) В основе построения компьютеров, а точнее аппаратного обеспечения, лежат так называемые вентили. Они представляют собой достаточно простые элементы, которые можно комбинировать между собой, создавая тем самым различные схемы. Одни схемы подходят для осуществления арифметических операций, а на основе других строят различную память ЭВМ. Простейший вентиль представляет собой транзисторный инвертор, который преобразует низкое напряжение в высокое или наоборот (высокое в низкое). Это можно представить как преобразование логического нуля в логическую единицу или наоборот. Т.е. получаем вентиль НЕ. Соединив пару транзисторов различным способом, получают вентили ИЛИ-НЕ и И-НЕ. Эти вентили принимают уже не один, а два и более входных сигнала. Выходной сигнал всегда один и зависит (выдает высокое или низкое напряжение) от входных сигналов. В случае вентиля ИЛИ-НЕ получить высокое напряжение (логическую единицу) можно только при условии низкого напряжении на всех входах. В случае вентиля И-НЕ все наоборот: логическая единица получается, если все входные сигналы будут нулевыми. Как видно, это обратно таким привычным логическим операциям как И и ИЛИ. Однако обычно используются вентили И-НЕ и ИЛИ-НЕ, т.к. их реализация проще: И-НЕ и ИЛИ-НЕ реализуются двумя транзисторами, тогда как логические И и ИЛИ тремя. Выходной сигнал вентиля можно выражать как функцию от входных. Транзистору требуется очень мало времени для переключения из одного состояния в другое (время переключения оценивается в наносекундах). И в этом одно из существенных преимуществ схем, построенных на их основе. Вопросы для самопроверки: Алгебраическая интерпретация понятий традиционной логики. Канонические формы представления логических функций. ДНФ СДНФ МДНФ Дьяков М., Сяркин Л. DVD. 11.05.2003.— http://w-rabbit.narod.ru/comp/dvd.htm. Долгий Э. Правильный выбор //Экспресс-Электроника”. 2003. №11.— http://www.citforum.ru/hardware/pc/true.shtml. Шкелев Е.И. Электронные цифровые системы и микропроцессоры: Учебное пособие. Нижний Новгород: Изд-во ННГУ, 2004. – 153 с.

Похожие:

	Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Учебно-методический комплекс дисциплины составлен на основании требований государственного образовательного стандарта высшего профессионального...		Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Системы и сети связи 090104. 65 – Комплексная защита объектов информатизации Форма подготовки очная
	Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Защита информационных процессов в компьютерных системах 090104. 65 – Комплексная защита объектов информатизации Форма подготовки...		Учебно-методический комплекс дисциплины Туризм, утвержденного приказом Министерства образования и науки РФ от 20. 01. 2006 г. №739гум/бак. Учебно-методический комплекс обсужден...
	Учебно-методический комплекс дисциплины «Формальности проживания в гостинице» Туризм, утвержденного приказом Министерства образования и науки РФ от 20. 01. 2006 г. №739гум/бак. Учебно-методический комплекс обсужден...		Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Учебно-методический комплекс составлен в соответствии с требованиями государственного образовательного стандарта высшего профессионального...
	Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Учебно-методический комплекс составлен в соответствии с требованиями государственного образовательного стандарта высшего профессионального...		Учебно-методический комплекс дисциплины обсужден на заседании кафедры «Финансы и кредит» Учебно-методический комплекс составлен в соответствии с требованиями государственного образовательного стандарта высшего профессионального...
	Учебно-методический комплекс дисциплины организация работы гостиниц 100200. 62 «Туризм» Туризм, утвержденного приказом Министерства образования и науки РФ от 20. 01. 2006 г. №739гум/бак. Учебно-методический комплекс обсужден...		Учебно-методический комплекс дисциплины обсужден на заседании кафедры компьютерных систем «03» Учебно-методический комплекс составлен в соответствии с требованиями федерального государственного образовательного стандарта высшего...
	Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Учебно-методический комплекс составлен в соответствии с требованиями федерального государственного образовательного стандарта высшего...		Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Учебно-методический комплекс составлен в соответствии с требованиями государственного стандарта высшего профессионального образования...
	Проект) (КР,КП), Расчётно-графическая работа (ргр) Домашнее задание... Учебно-методический комплекс дисциплины обсуждён и утверждён на заседании кафедры «Гидротехнические сооружения»		Учебно-методический комплекс составлен на основании требований государственного... Учебно-методический комплекс дисциплины обсуждена на заседании кафедры Информационные системы управления «29» июня 2011 г
	Учебно-методический комплекс дисциплины материаловедение направление... Учебная программа обсуждена на заседании кафедры технологии и предпринимательства		Учебно-методический комплекс Наименование дисциплины Аритмология... Переутверждено на заседании кафедры госпитальной хирургии с курсом детской хирургии