2001-0084-0-01 (Лабы), страница 3

PDF-файл 2001-0084-0-01 (Лабы), страница 3 Схемотехника (113697): Лабораторная работа - 2 семестр2001-0084-0-01 (Лабы) - PDF, страница 3 (113697) - СтудИзба2021-10-24СтудИзба

Описание файла

Файл "2001-0084-0-01" внутри архива находится в папке "Лабы". PDF-файл из архива "Лабы", который расположен в категории "". Всё это находится в предмете "схемотехника" из 2 семестр, которые можно найти в файловом архиве НИУ «МЭИ» . Не смотря на прямую связь этого архива с НИУ «МЭИ» , его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 3 страницы из PDF

Функционально полные наборы и базисные наборыФункционально полным называется набор булевых функций {f1,f2, …, fn} такой, что любая сколь угодно сложная булева функция можетбыть выражена в виде суперпозиции (сочетания) функций из этого набора.Базисным называется такой функционально полный набор, из которого нельзя исключить ни одну булеву функцию без ущерба для егофункциональной полноты.Поскольку любая булева функция, заданная таблицей истинности,может быть представлена в виде СДНФ (или СКНФ), то набор1) {&, ∨,  ) – функционально полный набор.Набор 1) не является базисным набором, так как из него можно исключить либо &, либо ∨, а недостающую функцию реализовать с помощьюоставшихся функций.

Например, если из набора 1) исключена &, то ееможно реализовать так: AB =  ( A ∨ B) (выражение справа понимается так: A ∨ B ). Если же из набора 1) исключена функция ∨, то она можетбыть реализована так: X ∨ Y =  ( X Y) = X Y .14Таким образом, получаем два функционально полных (базисных) набора:2) {&,  };3) {∨,  }.Русский математик Жегалкин показал, что любая булева функцияможет быть представлена с использованием операций конъюнкции(&) сложения по модулю 2 (⊕) и константы 1. Покажем, как известные функции набора 1) представить в виде декомпозиции функцийЖегалкина:  A = A ⊕ 1; A ∨ B =  ( A B) = (A ⊕ 1)(B ⊕ 1) ⊕ 1 == AB ⊕ A ⊕ B ⊕ 1 ⊕ 1 = AB ⊕ A ⊕ B.Поэтому следующим функционально полным (базисным) наборомбудет набор функций Жегалкина:4) {&, ⊕ , 1 }.Аналогично можно показать, что набор5) {∨, ⊕ , 1} – базисный набор.Выше было показано, что мажоритарная функция M(X, Y, Z) == XY ∨ XZ ∨ YZ.

Если на один из входов, например Z, подать константу1, то получим M(X, Y, 1) = XY ∨ X ∨ Y = X ∨ Y , а если на этот же вход Zподать константу 0, то получим M(X, Y, 0) = XY. Поэтому получаем ещедва базисных набора:6) {M, , 1};7) {M, , 0}.Когда говорят о “мажоритарном базисе” , то имеют в виду эти дванабора (или их объединение: {M, , 1, 0}), предполагая, что 1 и 0 реализуются “без затрат”, а инверсия аргументов всегда присутствует, есликомбинационная схема подключается к триггерным устройствам (элементарным автоматам), которые имеют как прямой, так и инверсныевыходы.На практике, как правило, используются базисные наборы, состоящие только из одной функции (“штрих Шеффера” или “стрелка Пирса”):8) {/};9) {↓}.Набор 8) реализует функцию  (XY) = XY . Инверсия аргумента может быть получена так:  X =  (XX).

Конъюнкция XY =  ( (XY) == X Y = X Y X Y . Дизъюнкция может быть реализована так: X ∨ Y ==  ( XY) = X Y = X X Y Y .15Набор 9) реализует функцию  (X ∨ Y) = X ∨ Y . Инверсия аргументаможет быть получена так:  (X ∨ X). Дизъюнкция может быть получена так: X ∨ Y =  ( (X ∨ Y)). Конъюнкция может быть получена так:XY = ( X∨ Y).П р и м е р .

Перевести в базис Шеффера и Пирса функцию, заданную в дизъюнктивной форме:F = A B ∨ A CD ∨ B D.В базисе Шеффера функция будет иметь видF = A B AC D B DВ базисе Пирса функция будет иметь видF = A∨ B ∨ A∨ C ∨ D ∨ B ∨ DПримеры для самостоятельной работы.Представить в базисах Шеффера и Пирса следующие функции (принеобходимости предварительно упростить):а) ABC ∨ BD ∨= AC ∨ ACDб) XZ ∨ ZY ∨ ZP =;.1.9. Примеры реализации комбинационных схемРедко задание на проектирование комбинационных схем формулируется в виде перечисления входных и соответствующих им выходныхнаборов (таблиц истинности).

Часто оно задается в виде описания работы.П р и м е р 1. Построить однотактное устройство, реализующее следующий алгоритм работы.На вход устройства подается 5-разрядный двоичный код (x1, x2, x3,x4, x5).На выходе вырабатывается 0, если число единиц в коде равно 0или 1, и вырабатывается 1, если число единиц равно 4 или 5. Остальные случаи не предусмотрены (на остальных наборах можно проставить “–”).Построим диаграмму Вейча по данному описанию.16x3x2x1––1––––0–111–1––––1––––00–––0–00x5x4Выпишем решение при очевидном способе доопределения и представим его в базисе Шеффера и Пирса:F = x2 x3 ∨ x4 x5 = x2 x3 x4 x5 = x2 ∨ x3 ∨ x4 ∨ x5 .Комбинационные схемы на несколько выходов строятся аналогичным образом. Однако предпринимаются попытки провести совместнуюминимизацию схем, реализующих отдельные выходные сигналы.

Примерами таких схем могут служить различные преобразователи кодов.П р и м е р 2. Построить однотактное устройство, преобразующеедвоичный код в код Грэя.Выпишем таблицу истинности четырех разрядов кода Грэя.x40000000011111111x30000111100001111x20011001100110011x10101010101010101y40000000011111111y30000111111110000y20011110000111100y1011001100110011017Число диаграмм Вейча равно четырем, причем для y4 она тривиальная (y4 = x4), а для остальных имеет следующий вид.Для y1x4x311111111y1 = x1 x2 ∨ x1 x2 = x1 ⊕ x2 .x2x1Для y2x4x311111111y2 = x2 x3 x2 ∨ x3 = x2 ⊕ x3 .x2x1Для y3x4x311111111y3 = x3 x4 ∨ x3 x4 = x3 ⊕ x4.x2x11.10.

Изображение комбинационных элементовна функциональных схемахДля изображения комбинационных элементов в различных базисахиспользуются следующие обозначения.18Изображение элемента “И”&Изображение элемента “ИЛИ”1Изображение элемента “И-НЕ” (Шеффера)&Изображение элемента “ИЛИ-НЕ” (Пирса)1Изображение элемента “НЕ”Изображение элемента “⊕” (сумма по модулю 2)⊕Упражнение. Нарисуйте функциональные схемы двух устройств вразличных базисах, которые были синтезированы в подразд.

1.9.192. БУЛЕВЫ ПРЕОБРАЗОВАНИЯДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ2.1. Постановка задачиПусть имеются две двоичные последовательности A(a1, a2, …, an) иB(b1, b2, …, bn). При этом ai, bi ∈ {0, 1}, i = 1, 2, 3, …, n. Элементыпоследовательности B будем получать булевым преобразованием последовательности A, при этом bi будет результатом булевого преобразования, зависящего от ai и некоторых элементов из окружения ai. Максимальное число аргументов булевой преобразующей функции F равноN = 2n – 1. Так, для n = 3 N = 5; для n = 4 N = 7; для n = 5 N = 9.Рассмотрим методы нахождения функций F.2.2.

Теорема о преобразованияхдвоичных последовательностейСформулируем теорему, на основании которой можно строить булевы функции, преобразующиe одну последовательность в другую. Этатеорема являeтся аналогом теоремы, доказанной в литературе1.Теорема. Для того чтобы существовала булева функция F, преобразующая произвольную последовательность А в произвольную последовательность В, необходимо и достаточно, чтобы А была ненулевой последовательностью. Число аргументов F не превышает 2n – 1.Необходимость следует из того, что при нулевой последовательности А все элементы последовательности В будут либо нулями, либо единицами, и в этом случае В не может быть произвольной последовательностью.Для доказательства достаточности построим часть таблицы истинности функции F, в которой функция определена:1Åðîø È. Ë., Èãíàòüåâ Ì.

Á., Ìîñêàëåâ Ý. Ñ. Àäàïòèâíûå ñèñòåìû óïðàâëåíèÿ ïðîìûøëåííûìè ðîáîòàìè: Ó÷åá. ïîñîáèå äëÿ âòóçîâ / ËÈÀÏ. Ë., 1985. 144 ñ.20a1 a2 … anb1a1 a2 … anb2a1 a2 … anb3……………………………………………bna1 a2 … an+1Если хотя бы один элемент последовательности А не равен 0, то всенаборы, на которых функция определена, будут различными, поэтому несуществует ни одной одинаковой пары наборов, на которой функция должна принимать одновременно значение 0 и 1.П р и м е р .

Пусть A (101), B (011). Функция F будет зависеть отаргументов (ai – 2 , ai – 1, ai , ai + 1, ai + 2). Таблица истинности этойфункции (точнее, только та ее часть, на которой функция определена)будет иметь видai – 2ai – 11aiai+11010101aiB+21011Функция пяти аргументов задается на 32 наборах. Однако эта функция задана в примере всего на 3 наборах.

На остальных 29 наборахфункция не определена и ее можно доопределить 229 способами. Диаграмма Вейча этой функции будет иметь видai – 2ai – 1ai––––––0–––––––––––––1––––1––––––ai + 2ai + 1Доопределить и минимизировать данную функцию достаточно просто: F = ai + 2 . Действительно, применив булево преобразование F к A,получим B.21При длинах векторов A и B, равных n, булева функция будет задаваться на n наборах, а на 2(2n-1) – n наборах функция будет не определена.

Доопределение и минимизация булевой функции не однозначны.Определение. Два набора Ai и Aj длины n будем называть связанными сдвигом, если при некотором сдвиге одного набора относительнодругого у этих наборов совпадают позиции всех единиц. Например, A =1 0 0 1 0 1 1 0 0 0 и B = 0 0 1 0 0 1 0 1 1 0 – наборы, связанные сдвигом.Из приведенной выше теоремы сформулируем следствия.Следствие 1. Если Ai, i = 1, 2, 3, …, k – двоичные векторы, не связанные сдвигом, и В – произвольный вектор, то существует одна булевафункция F, преобразующая любой вектор Ai в вектор В, т.

е. B = F(Ai),i = 1, 2, 3, …, k.П р и м е р 1. Пусть A1 = 1011; A2 = 1001; A3 = 0110; B = 0111.Построим часть таблицы истинности функПример 1 ции F, выписывая только те наборы, на которых функция определена, при этом для удобa b c d e g h Fства введем очевидные переобозначения1 0 1 1 0аргументов.1 0 1 11Упражнение. Постройте диаграмму Вейча функции F и убедитесь в том, что при не1 0 1 11котором способе доопределения функция1 0 1 11будет иметь вид1 0 0 1 0F=a∨c∨e g.Проверьте, что эта функция из любой при1веденной последовательности Ai (i = 1, 2, 3)1строит одну и ту же последовательность В.1 0 0Следствие 2.

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5288
Авторов
на СтудИзбе
417
Средний доход
с одного платного файла
Обучение Подробнее