Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 86
Текст из файла (страница 86)
равны 1. 4.56. Сколько существует логических функций п переменных, двойственных по отношению к самим себе? (Указание: Рассмотрите структуру таблицы истинности какой-нибудь функции, двойственной по отношению к самой себе.) 4.57. Докажите, что любая логическая функция п переменных Е(ХП ..., Х„), которую можно записать в виде Е=Х~ 0(Хп ..., Х„)+ Х~' 0" (Хь ..., Х„), является двойственной по отношению к самой себе. 4.58. Сравните по быстродействию схемы на рис.4.24(а), (с) н (д), предположив, что задержка распространения инвергирующего вентиля равна 5 нс, а задержка распространения неинвертирующего вентиля равна 8 нс. 4.59.
Найдите минимальные выражения вида «произведение сумм» для логических функций, представленных парис.4.27 и 4.29. 4.60. Покажите, пользуясь правилами алгебры переключений, что логические функции, полученные в задаче 459, равны функциям И вЂ” ИЛИ, приведенным на рис.4.27 и 4.29. 4.61. Проверьте, являются ли минимальными выражения вида «произведение сумм», полученные путем «разнесения слагаемого по сомножителям» из минимальных сумм, приведенных на рис.4.27 и 4.29. 4.62. Докажите справедливость правила объединения на карте Карно 2' клеток, содержащих 1, исходя из аксиом и теорем алгебры переключений.
4.63. Неприводимая сумма (тединг?ап! хит) для логической функции Š— это такая сумма простых импликант Е, что при удалении любой из простых импликант эта сумма уж не равняется Е. Согласно этому определению, неприводимая сумма выглядит очень похожей на минимальную сумму, однако неприводимая сумма не обязательно является минимальной. НапРимеР в минимальной сумме функции, приведенной на рис. 4.35, только три термапроизведевия, тогда как существует неприводимая сумма с четырьмя термами-произведениями.
Найдите эту неприводимую сумму и начертите карту для данной функции, обведя только простые имплнканты, входящие в неприводнмую сумму. Задачи 365 4.64 Найдите другую логическую функцию в параграфе 4.3, у которой есть одна нли большее число неприводимых сумм, не являюшихся минимальными, начертите карту этой функции и обведите только те простые импликанты, которые входят в иеприводимую сумму. 4.66. Начертите карту Карно и присвойте имена переменных входам схемы И-ХОВ, изображенной на рис. Х4.65 так, чтобы сигнал на ее выходе равнялся Е = Х, „„(6, 7, 12, 13). Будьте внимательны: выходной вентиль является двухвходовой логической схемой ИСКЛЮЧАЮ)ЦЕЕ-ИЛИ, а не схемой ИЛИ. Рис.
Х4.65 4.66. На входы 3-разрядного «сравниваюшего устройства» поступают два 3-разрядных двоичных числа: Р = РгР ~ро и О = ОгО1Оо Составьте схему, реализующую минимальную сумму произведений, согласно которой 1 появляется на выходе тогда и только тогда, когда Р > О. 4.67. Найдите минимальные выражения вида «сумма произведений» для схемы с тремя выходами, реализующей функции: Е = 2х „г(0, 1, 2), О = 2х „к[1, 4, 6) и Н = 2.'х„г(0 1 2, 4, 6). 4 бл Проверьте, является ли минимальной суммой следующее выражение.
Сделайте это простейшим возможным способом (то есть алгебранчески, а не с помощью карт). Е=Т' 0 Ч Ч/ Х+Т' 0 Ч' Х 2+Т'.0 ьЧ.Х '1" 2 4 69. В основном тексте утверждалось, что отправной точкой для традиционных методов минимизации комбинационных схем является таблица истинности или ее эквивалент. Сама по себе карта Карно содержит ту же самую информацию, что и таблица истинности. По заданному выражению вида «сумма произведений» можно расставить на карте единицы, непосредственно соответствующие каждому произведению, не составляя в явном виде таблицы истинности или списка минтермов, а затем осуществить процедуру минимизации с использованием карт. Найдите указанным способом минимальные выражения вида «сумма произведений» для каждой из следующих логических функций: (а) Е=Х'.~+Х.'т+Х У' т (Ь)Е=А' С' О+В' С О+А С' О+В С 0 (с) Е=ЧЧ Х 2'+ЧЧ Х' У 2+Х 2 (д) Е = (Х'+У') (ЧЧ'+ Х'+У) 0)Ч'+ Х+ 2) (е)Е=А.В.С'.0'+А'.В С'+А В 0+А' С О+В С 0'.
4.70. В условиях задачи 4.69 найдите минимальные выражения вида «произведе- ние сумм» лля каждой из указанных там логических функций. Збб Глава 4. Принципы проектирования комбинационных логических схем 4.71. Выведите минимальное выражение вида «произвеление сумм» для функции, реализуемой устройством обнаружения простых двоична-десятичных чисел (см. рис.
4.37). Проверьте, равно ли это выражение в алгебраическом смысле минимальному выражению вида «сумма произведений», и объясните полученный результат. 4.72. Карту Карно для функции 5 переменных (5-наг!аЫ« Кагпаий)о тар) можно представить так, как показано на рис. Х4.72. В такой карте клетки, занимающие одинаковое положение в подкартах для и' = 0 и Ч = 1, считаются соседними. (В разделах 7.4.4 и 7.4.5 приведено несколько подробно разобранных примеров карт Карно для функций 5 переменных.) Найдите с помощью карт Карно выражения вида «сумма произведений» для каждой из следующих функций 5 переменных: х (5,7,13,!5,16,20,25,27,29,3!) (Ь)Р 2.ноух (0,7,8,9, !2,13,15,16,22,23,30,31) (с)г=2 ен у (0,1,2,3,4,5,10,11,14,20,21,24,25,26,27,28,29,30) (д) Р = Хну«худ(0, 2, 4, 6, 7, 8, 1О, 11, 12, ! 3, 14, 16, 18, 19, 29, 30) (е) Р=Пн,д „д(4,5,10,12,13,16,17,21,25,26,27,29) (() Р = 2.ну«худ(4, 6, 7, 9, 11, 12, 13, 14, 15, 20, 22, 25, 27, 28, 30) + + г)(1, 5, 29, 31) Рис.
Х4.72 оу пх ух оо Ф 11 10 оо пх ух~ оо о1 и оо оо оо ум и-о 4.73. В условиях задачи 4.72 найдите минимальные выражения вида «произведение сумм» для каждой из указанных там логических функций. 4.74. Карту Карно для функции б перев«нных (6-наг!аЫ« Кагпаид6 тар) можно изобразить так, как показано парис.
Х4.74. В такой карте клетки, занимающие одинаковое положение в соседних подкартах, считаются соседними. Минимизируйте следующие функции 6 переменных с помощью карт Карно: (а) Р=Х„„,нхуд(1,5,9,13,21,23,29,31,37,45,53,61) (Ь) Р = 2.0 нунх уд(0, 4, 8, ! 6, 24, 32, 34, 36, 37, 39, 40, 48, 50, 56) (с) Р ~оно«худ(2,4, 5,6, 12 — 21,28 — 31, 34, 38, 50, 51,60-63), 4.75. СУществует 2п т-мерных подкубов п-мерного куба при т = п — 1, Представьте их в виде текстовых строк и Укажите соответствующие термы-произведения.
(По мере необходимости вы можете использовать многоточия, например: 1, 2, ..., и,) 4.76. Существует только один т-мерный подкуб и-мерного куба при т = и; его представление в виде текстовой строки имеет вид: хх...хх. Запишите терм- произведение, соответствующий этому кубу, Задачи 367 чч ччх чд~ ао о1 и 1о оа ча х Рис. Х4.74 чдч аа а1 о ао ~1ач ил=о,о и,ч аз ччх и чдчч ао о1 и ~о оо ах Г=~ чг'~, оо а1 и 1о аа 1 1 цч-ьо цч=ь1 4.77.
В приведенной в табл.4.9 программе на языке С память используется неэффективно, поскольку она резервируется для максимального числа кубов на каждом уровне, даже если этот максимум никогда не достигается. Перепишите программу таким образом, чтобы массивы сдвэез и сочегей были одномерными и на каждом уровне число элементов в них было бы только таким, какое необходимо. (Указание: Вы можете разместить кубы последовательно, запоминая начальную точку массива на каждом уровне.) 4.78. Сколько раз во внутреннем цикле в программе в табл.
4.9 происходит обращение к каждому отдельному в-мерному кубу только за тем„чтобы «посмотреть на иего» и отбросить? Предложите способ исключения таких нерациональных действий. 4 79. В третьем цикле ~од в табл. 4 9 производится попытка объединения каждого из а-мерных кубов на данном уровне со всеми другими м-мерными кубами этого уровня. На самом деле, обьединять можно только т-мерные кубы с символами 'х' в одинаковых позициях; поэтому есть возможность сократить число итераций в цикле, используя более сложную структуру данных. Предложите структуру данных, в которой кубы данного уровня были бы рассортированы по положению в них символов 'х', и найдите наибольший объем памяти, необходимой для различных элементов в этой структуре данных.
Перепишите соответствующим образом программу, приведенную в табл, 4,9. 4ЛЮ. Проанализируйте, превышает ли экономия, достигаемая за счет уменьшения числа итераций во внутреннем цикле в задаче 4.79, затраты, необходимые для поддержания более сложной структуры данных. Примите разумные предположения о распределении кубов на каждом уровне н оцените зависимость ваших результатов от этих предположений. 4.81. Оптимизируйте функцию опеопе в программе в табл. 4.8. Очевидный способ оптимизации заключается в том, чтобы раньше выходить из цикла, однако существуют и лругие возможности, позволяющие полностью исключить цикл дог. Олна из них основана на просмотре таблицы, а другая состоит 388 Глава 4.
Принципы проектирования комбинационных логических схем в искусном вычислении, включающем инвертирование, выполнение операции ИСКЛЮЧАЮЩЕЕ ИЛИ и сложение 4.82. Расширьте программу на языке С из табл. 4.9, включив обработку безразличных значений. Введите новую структуру данных с!с[мдх чАВБ+1) (мдх С!)ВЕЯ]для регистрациислучаев, когдаданный куб содержит только безразличные значения, и обновляйте ее всякий раз при чтении кубов и их создании, 4.83. (Схема Гамлета.) Продолжите временную диаграмму и объясните, какую функцию выполняет схема, приведенная парис. Х4.83.
В каком месте схема ведет себя в соответствии с ее названием? Рис. Х4.83 2В Е 4 84, Докажите, что в двухуровневой схеме И вЂ” ИЛИ, реализующей полную сумму логической функции, никогда нет источников опасности. 4.85. Найдите логическую функцию четырех переменных, для которой реализация минимальной суммы произведений не является свободной от источников опасности, но существует реализация суммы произведений без источников опасности с меньшим числом термов-произведений, чем в полной сумме. 4.86. Беря в качестве отправной точки операторы г!ВБ(Г в программе на языке А ВЕС в табл. 4.
14, составьте логические равенства для переменных хе -х1о, Объясните, есть ли какие-либо расхождения между вашими результатами и равенствами, приведенными в табл.4.15. 4.87. Нарисуйте принципиальную схему, соответствующую приведенному в табл. 4.12 минимальному двухуровневому выражению логической функции, реализуемой устройством охранной сигнализации. На входах и выходах всех инверторов, вентилей и и вентилей или проставьте пару чисел (гО,г!), где г0 — номер проверочного вектора из табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
