(926)274-88-54
Бесплатная доставка.
Бесплатная сборка.
График работы:
Ежедневно. С 8-00 до 20-00.
Почта: soft_hous@mail.ru
|
|
Звоните! (926)274-88-54 Бесплатная доставка. Бесплатная сборка. |
Ассортимент тканей График работы: Ежедневно. С 8-00 до 20-00. Почта: soft_hous@mail.ru |
  
|
Читальный зал --> Особенности интегральных микросхем в качестве накменьших структурных единиц рассматриваются операционные узлы (сумматоры, регистры, счетчики, дешифраторы, мультиплексоры и т. д.). Математический аппарат, обеспечивающий решение задачи проектирования цифровых устройств на логическом н операционном уров-иях, разрабатывается в теории переключательных функций и цифровых автоматов. Переключательные функции. Фуикцноиироваиие цифровых устройств комбинационного типа, имеющих я входов и т выходов, в общем случае описываетси системой функций У, = (*1. *2.....*/.), где значения функций определяют значения выходных сигналов (/ = = 1,т), а наборы аргументов (jcj, х, соответствуют входным сиг- налам. Как фуишши Uj, так и аргументы могут принимать только конечное число значений (обычно jCj, € 0, 1)). Такие функции называют переключательными (булевые, двузначные, логические). Переключательные функции чаще всего задают с помощью таблиц, называемых таблицами истинности, путем перечисления их зиачеиий иа всех наборах зиачеиий аргументов. Для упрощения таблиц истинности наборы аргументов нумеруют. Номер X набора аргументов равен двоичному числу, соответствующему этому набору. Если функция зависит от п аргументов, то число различных наборов аргументов равно 2 , поскольку каждый набор имеет свой номер, а общее число номеров равно количеству различных двоичных я-разрядиых чисел. Две функции отличаются друг от друга, если оии принимают различные значении хотя бы на одном наборе аргументов. Число различных функций от я аргументов равно 2, так как для задании функции / (xj, JCa,..., jc ) необходимо указать набор из 2 констант / (Яц flj, .... а ), а, G С (О, 1}, а число различных 2 -разрядных наборов равно 2. В таблице истинности значения функций иа некоторых наборах могут быть неопределенными, т. е. могут принимать как значение О, так и значение 1. Такие функции называют частично определенными, в отличие от полностью определенных, принимающих значения О и 1 иа всех наборах аргументов. Наборы, иа которых функция ие определена, называют несущественными (фиктивными). Число переключательных функций, зависящих от одного аргумента, равно четырем, причем три из иих являются тривиальными (их значения либо совпадают со значениями аргумента, либо не зависят от иих и постоянно равны О или 1). Единственной нетривиальной функцией является функция отрицания, нли инверсии, которую записывают в виде f (х)= X. Число переключательных функций от двух аргументов равно 2 = = 16. Все такие функции перечислены в табл. 2.1. Перечислить подобным образом функции л > 3 переменных трудно, так как их число очень быстро растет по мере увеличения я. Однако среди функций п переменных всегда можно указать функции, аналогичные по свойствам функциям двух переменных. К таким функциям, например, относятся константы О и 1; переменные Xj, х, х ; конъюнкция, принимающая единичное значение только иа одном наборе аргументов; дизъюнкция, принимающая нулевое значение только иа одном наборе аргументов; сумма по модулю 2; равнозначность; функции Пирса и Шеффера и др. Суперпозицией переключательных функций называют подстановку одних функций вместо аргументов в другие функции. Так как множество значений переключательных функций совпадает со множеством значений их аргументов, то функции от большого числа аргументов могут быть представлены как суперпозиции от меньшего числа аргументов. Система переключательных функций, с помощью которых путем суперпозиций можно представить любую сколь-угодно сложную фуик- Таблица 2.1
цию, называется функционально полной. Функционально полными являются, например, системы функций: 1) JCj V х, хх, ~х\ 5) x-ijx, хх; 2) Xl \ х, хх; 6) Xl \ х; 3) xjx, Xl V х; 7) Xi/x; 4) Xl I x, Xl V x; 8) Xj Ф Xa, XiX, x. Особенностью систем 6) и 7) является то, что каждая из них состоит только из одной функции. Системы 1) - 5) называют избыточно полными, так как одну из функций XiX или JCiV-a можно исключить без потери функциональной полноты. Интегральные ИМС некоторой серии чаще всего реализуют избыточные функционально полные системы, причем не только перечисленные выше, но и получаемые путем объединения некоторых из систем I) - 8), дополнения их другими функциями, увеличения числа аргументов. Переключательную функцию, реализуемую ИМС, называют также элементным логическим оператором [26] и задают в виде И - НЕ, ИЛИ, И - ИЛИ - НЕ и т. п. Канонические формы представления переключательных функций. Одной и той же переключательной функции могут соответствовать различные суперпозиции функций функционально полной системы. В связи с этим возникает задача нахождения такой формы записи функций, при которой каждой функции соответствует одна и только одна функция. Такие формы записи функций называют каноническими. Произвольную переключательную функцию f (Х), где Х- (Xi, х, л; ), можно представить в виде где символ у означает дизъюнкции по всем наборам; Л = (Qi, 2.....а ). ai 6 {О, 1); (2.1) х7 = Xl если ai - O, Xi если а,- = I, < = I, п. Из выражения (2.1) следует, что между всеми функциями п аргументов ( -местными функциями) и их представлениями в виде (2.1) можно установить взаимно однозначное соответствие. Поэтому выражение (2.1) является канонической формой представления переключательных функций. Используя свойства конъюнкции, состоящие в том, что Ол; = О, 1л: = х, выражение (2.1) перепишем в другом виде: /(X) = v?4 ... V. (2.2) где символ V означает, что дизъюнкцию берут только по тем наборам А, на которых / (Л) = 1. Каноническая форма (2.2) называется совершенной дизъюнктивной нормальной формой (СДНФ) или формой И-И,ЛИ. Последнее название указывает, что в данной канонической форме внутренней функцией является конъюнкция (И), а внешней - дизъюнкция (ИЛИ). Очевидно, что каноническую форму И-ИЛИ удобно использовать для проектирования устройств комбинационного типа тогда, когда ИМС реализуют элементные операторы И, ИЛИ, НЕ. При других элементных логических операторах целесообразно использовать другие канонические формы, получаемые из выражения (2.2) с помощью так называемых правил двойного отрицания л: = л; и правила де Моргана л = 1 V Хг, Xl V Хг = хХг, в справедливости которых можно легко убедиться, составив таблицы истинности левых и правых частей соответствующих выражений при всех возможных значениях переменных Xi и х.: /(X) = /(X) = V = & 4 (2.3) где символ & означает коньюнкцию по Всем наборам Л, где / (Л) = 1. Каноническая форма (2.3) называется формой И-НЕ/И-НЕ. Ее целесообразно использовать, когда ИМС реализуют элементные операторы И-h Е. Применив к выражению (2.3) правило де Моргана, получим форму ИЛИ-И -НЕ: /(X) = & ...хУ = & (Х V 4 V V хУ). Так как л; = x i, то с учетом этого последнее выражение примет вид /(Х)= &(х?V4V У хУ). (2.4) Применив к выражению (2.4) еще раз указанное выше правило по-получим форму ИЛИ - НЕ/ИЛИ /(X) = У4У V< ) = V V4 V VхУ). (2.5) которую удобно использовать при наличии ИМС, допускающих paciui:-реиие их логических возможностей по уровню ИЛИ. Для получения t:.v,2 четырех канонических форм запишем в формуле (2.2) отрицание фу!1к-ции / (X): f (X) = Y Д.ДГз . . . где символ означает дизъюнкцию по всем наборам Л, где7(.)= I, т. е. где / (X) = 0. Выполняя действия, аналогичные описанным выше, получаем следующие формы: И - ИЛИ - НЕ И - НЕ/И f(X) = f(X)= - (2G) f = дУ. > = Д . (2.7) ИЛИ -И / (X) = & (хЧх-г . .. /п) = & V 4 V . V хУ). (2.8) или - НЕ/ИЛИ - НЕ f(X)= & V W)- (2.9) Таблица 2.2 Форму (2.8) называют также совершенной конъюнктивной нормальной формой (СКНФ), а формы (2.6), (2.7) и (2.9) можно получить путем преобразования СКНФ. При построении канонических форм используют простейшие выражения, представляющие собой конъюнкции или дизъюнкции нескольких попарно различных переменных, взятых с отрицаниями или без них. Эти выражения называют соответственно элементарным произведением (конъюнкцией, термом) и элементарной дизъюнкцией (дизъюнктивным термом). Элементарное произведение, содержащее все переменные Xi, х, л функции и равное 1 на одном наборе аргументов и О на остальных, называют коистн-туентой единицы или мннтермом. Элементарная дизъюнкция, содержащая все переменные функции и равная О на одном наборе аргументов н 1 на остальных, называется кои-ституентой нуля или макстермом. Использование свойств дистрибутивности функций, входящих в функционально полную систему, позволяет получать так называемые скобочные формы переключательных функций, у которых общие части нескольких элементарных произведений или дизъюнкций вынесены за скобки. Например, для функций fi и /г, заданных таблицей истинности (табл. 2.2), их СДНФ н некоторые из возможных скобочных форм следующие: fi (X) = XiXjJj V XiXXa V xJcXa V - fiVs = = x (х{хз V *i*3 V ад) V хСхз = x (xi V з) V ххХз = == Хз (XiXi V XiX V XiX) V X1X.2X3 = ~Хз (2 V Xi) V X1X.2X3 = = x. (X3 v IciXg) v л; /а (X) = X1X2X3 V ХхХХз V XiXs3 V ХхХХз V xxXj = = X3 (ад V XiXi V - 1*2) V X1X3 = Хз {Xi V 2) V 12- Канонические формы (2.2) - (2.9) не являются скобочными формами, так как наличие скобок обусловлено лишь особенностями используемой символики. Для упрощения записи канонических форм переключательных функций иногда используют их числовое представление. При числовом представлении в СДНФ или СКНФ вместо конституенты О и 1 записывают номера наборов, на которых равны 1 (для СДНФ) илн О (для СКНФ) соответствующие конституенты, например, для функций в табл. 2.2: /1 (X) = 2 V 3 V 4 V 6 = V (2, 3, 4, 6); (X) = 1 V 3 V 4 V 5 V 6 = = V (1. 3, 4, 5, 6). Минимизация переключательных функций. Выше уже отмечалось, что одну и ту же переключательную функцию можно представить различными суперпозициями функций функционально полной системы. Эти суперпозиции по существу являются математическими моделями цифро- вых устройств комбинационного типа и должны быть оптимальными по минимуму аппаратурных затрат на их реализацию. Количество оборудования, требуемого для реализации комбинационного устройства, называют его ценой. Процесс нахождения представления функции с минимальной ценой называют минимизацией. При реализации переключательных функций элементарным произведениям и дизъюнкциям, а также нх отрицаниям соответствуют некоторые достаточно простые электрические цепи, называемые элементами. Поэтому цену какого-либо комбинационного устройства определяют как суммарное число входов всех элементов (это число называют также ценой по Квайну). Функцию ф (X) называют импликаитой функции / (X), если на любом наборе аргументов / (X) > ф (X). Если ф (X) и i) (X) - импликанты функции / (X), то дизъюнкция ф (X) и \) (X) также является импликантой функции / (X). Простой импликантой функции / (X) называют такое элементарное произведение, которое является импликаитой функции / (X), ио никакая его собственная часть уже ие является имплииаитой функции /(X). Под собственной частью произведения С = лгЧ ...* понимают такое произведение В, которое можно получить из С путем вычер:-(нвания одной или Нескольких переменных jc°. Любая функция имеет конечное множество простых импликант, число которых не больше числа конституент 1 в СДНФ. Дизъюнкция всех простых импликант функции / (X) равна этой функции и называется сокращенной дизъюнктивной нормальной формой (ДНФ). Каждая функция имеет единственную сокращенную ДНФ. Один из методов получения сокращенных ДНФ основан на применении операций неполного склеивания XiXyXiXi = ххУXiXi\lXi и поглощения хА\/х=х. Для получения сокращенной ДНФ функции / (X) необходимо в СДНФ функции / (X) произвести все возможные операции неполного склеивания, а затем все возможные операции поглощения. Выполняют это следующим образом. Каждая конституента 1 сравнивается с остальными. Если конституента В отличается от конституенты С только наличием отрицания у однсй из переменных, то к этим конституентам применяется операция склеивания, т. е. выписывается нх общая часть. В результате получают груслу элементарных произведений, состоящих из п - 1 переменных. Описакный процесс повторяется до тех пор, пока не получат группу, к любым двум членам которой нельзя применить операцию склеивания. Функция ф (X) накрывается функцией / (X), если на любом наборе А f (A)(f (А). В общем случае сокращенная ДНФ ие является минимальной, так как некоторые простые импликанты могут накрываться дизъюнкцией других членов и их можно исключить. Минимальная ДНФ (МДНФ) должна состоять исключительно из простых импликант. Нахождение МДНФ функции f (X) сводится к выделению некоторого числа простых импликант данной функции из всего нх множества. Один из методов решения этой задачи основан на применении импликантнсй таблицы (матрицы). Рассмотрим построение такой матрицы для функции fiiX) в табл. 2.2. В имплнкантной табл. 2.3 столбцы отмечаются консти-туентами 1, а строки - простыми импликаитами. В строке против каждой простой импликанты ставятся знаки X под теми констнтуентами, которые поглощаются данной простой импликантой. Непосредственно из таблицы выписывают все тупиковые ДНФ, у которых ни один из дизъюнктивных членов исключить нельзя. В тупиковую ДНФ должны войти все импликанты, отмеченные только одним знаком X, а также минимальное число простых импликант, на пересечении которых с любой конституентой есть хотя бы один знак X . Подсчитывая число букв в тупиковой форме, определяют минимальную ДНФ.
ООО «Мягкий Дом» - это Отечественный производитель мебели. Наша профильная продукция - это диваны еврокнижка. Каждый диван можем изготовить в соответствии с Вашими пожеланияи (размер, ткань и материал). Осуществляем бесплатную доставку и сборку. Звоните! Ежедневно! (926)274-88-54 Продажа и изготовление мебели. Копирование контента сайта запрещено. Авторские права защищаются адвокатской коллегией г. Москвы. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||