Відповіді до теоретичних питань 1-30. Державний іспит з Інші. Робота № 501489

Перехід до торгівельного партнера Binance

Відповіді до теоретичних питань 1-30

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

Інформація про роботу

Рік:

2024

Тип роботи:

Державний іспит

Предмет:

Інші

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Поняття про інформацію та її види. Три підходи до вивчення теорії інформації. Порівняння аналогової та цифрової обчислювальної техніки Інформацію назив. відомістю, які можна отримати, передати, керувати, обробляти, зберігати. Інформація є міра різноманітності або однорідності в матеріалі , речовині та енергії у просторі та часі. Порівняння АТ та ЦТ 1. Точність АТ=102/1=103/1=104/1 Відношення Сигнал/Завада ЦТ=1010/1 2. Швидкодія АТ властивий паралельний алгоритм роботи. 3. Універсальність ЦОМ – універсальні,спеціалізовані ,а АОМ – спеціалізовані 4. Вартість EMBED Visio.Drawing.11 3 підходи до вивчення теорії інформації: 1. Структурна теорія інформації 2. Статистична (поняття ентропії) 3. Семантична (Акад. Маркевич О.О. Вартість інфи тим вища, чим більше змін робиться в сфері керування) Поясніть, у чому полягає зміст та значення теореми Котельникова. При дискретизации сигналов приходится решать вопрос о том, как часто следует производить отсчеты функции, т.е. каков должен быть шаг дискретизации. Кожний процес має обмеження на частоту спектра Fm. Согласно теореме В.А.Котельникова, если функция s(t) не содержит частот выше некоторой Fm, то она полностью определяется своими мгновенными значениями в моменты времени, отстоящими друг от друга на величину 1/(2Fm ), т.е. EMBED Equation.2 , где k - порядковый номер отсчета функции; t = 1/(2Fm) - шаг дискретизации по времени,sk = s(tk) - мгновенные значения сигнала s(t) в k-ой отсчетной точке tk = k/m = k/(2Fm) = kt. Из этой теоремы следует, что для однозначного представления функции с ограниченным спектром на интервале времени Т достаточно иметь некоторые n значений этой функции, где n = T / t = 2FmT. При выполнении этого равенства (условия) непрерывная и дискретная функции обратимы между собой, т.е. тождественны. Таким образом, произвольный сигнал, спектр которого не содержит частот выше Fm может быть представлен в виде последовательности импульсов, амплитуда которых равна значению исходного сигнала в дискретные моменты времени kt= а интервалы между ними t = 1/(2Fm). Из приведенной выше формулировки теоремы Котельникова однозначно следует, что для выбора оптимального шага дискретизации необходимо предварительно провести количественные оценки всех значащих гармоник спектрального разложения исходного непрерывного сигнала, для нахождения величины Fm, т.е.m. Основні ознаки алгоритму. Навести підхід до формального визначення алгоритму. Універсальні формальні алгоритмічні системи. Основна гіпотеза теорії алгоритмів. Совокупность правил перехода автомата из одного состояния в другое в зависимости от входной информации и внутренних состояний автомата называется алгоритмом преобразования (переработки) информации. Вообще алгоритмом называется конечная совокупность точно сформулированных правил решения какойто задачи. Можно привести еще одно определение понятия алгоритма. Алгоритм - это строго формальное описание конечной последовательности некоторых "элементарных" действий или процедур, которую надо выполнить над исходными данными и над промежуточными результатами, возникшими в ходе выполнения этих операций, для того чтобы прийти к информации, являющейся результатом обработки исходных данных. Ознаки алгоритму: Справа з даними (вхідні, провідні, вихідні) Пам'ять для зберігання Алгор. виконується по кроках, к-ть яких скінченна Алгор. мусить бути детермінований Результативність Більш строге визначеня можна дати в рамках теорії Формальних Алгор. Системах (ФАС): Рекурсивні ф-ції Машина Тюрінга Машина Поста Нормальні алгор. Маркова Схема Колмагорова Цифрові автомати Мілі та Мура Сист Черкаського Основна гіпотеза теорії алгоритмів: будь-який алгор.. може бути використаний із допомогою ФАС. Перечисленные, в этой главе понятия относятся к абстрактной теории цифровых автоматов, в которой рассматриваются автоматы, имеющие один вход и один выход. Поэтому применить все это к ЭВМ можно только в самом общем виде, ограничивая круг рассматриваемых устройств устройствами, входящими в состав процессора, или же в случае когда рассматривается вообще некоторый узел ЭВМ, предназначенный для достаточно элементарной обработки цифровой информации. В самом деле, в зависимости от команд, подаваемых устройством управления процессора, арифметическо-логическое устройство осуществляет соответствующие действия (изменение внутренних состояний) с выдачей необходимых результатов. Однако изменение внутренних состояний всей ЭВМ в целом носит настолько сложный характер, что этот процесс невозможно отобразить в аналитическом виде. Поэтому понятие цифрового автомата целесообразно использовать применительно к алгоритмам, реализующим некотору. программу или последовательность операций. При этом каждая операция представляется как элементарное действие, осуществляемое в процессе переработки информации. Автомат. Класифікація автоматів. Поняття про модель цифрового автомата типу Мілі та Мура. Цифровой автомат это устройство, характеризующееся набором некоторых внутренних состояний A = {a1(t), a2(t), ..., an(t)}= в которые оно попадает под воздействием входных сигналов и команд программы решения задачи. Пусть имеется автомат с одним входом и одним выходом: A = {ai(t)} z(t) (t) Рис.1.3. Цифровой автомат Цифровые автоматы могут быть с "жесткой", или схемной, логикой и с логикой, хранимой в памяти. Различают два класса автоматов: асинхронные и синхронные. Синхронный автомат характеризуется тем, что функционирует под управлением тактовых (или синхронизирующих) сигналов - ТС, с постоянной длительностью tТС и постоянной частотой fТС, если квантование времени равномерное. Такт (квант) времени ti совмещается с фронтом i-того сигнала ТС. Входные сигналы могут воздействовать на автомат лишь при наличии сигнала ТС и не изменяются в течение tТС. Период следования сигналов ТС должен быть больше или равен времени, которое необходимо реальному автомату для перехода из одного состояния в другое. Когда рассматривается абстрактный автомат, то считается, что изменение внутренних состояний автомата происходит в интервалы времени между смежными ТС, а выходные сигналы формируются по фронту очередного ТС. В асинхронных автоматах длительность интервала времени, в течение которого остается неизменным состояние входных сигналов, является величиной переменной и определяется временем, которое необходимо автомату для установки соответствующих выходных сигналов и завершения перехода в новое состояние. Следовательно, асинхронный автомат должен формировать каким-нибудь подходящим способом сигнал о завершении очередного такта, по которому текущие входные сигналы могут быть сняты, после чего может начаться следующий такт, т.е. возможно поступление новых входных сигналов. Как отмечалось в главе 1, абстрактный автомат с одним входом и одним выходом можно представить следующим образом: A X Y Для задания конечного автомата фиксируются три конечных множества (алфавита): - множество возможных входных сигналов: X = {x1, x2, ..., xm}; - множество возможных выходных сигналов: Y = {y1, y2, ..., yk}; - множество возможных внутренних состояний автомата: A = {a0, a1, ..., an}. На этих множествах задают два логических оператора: - функцию переходов f, определяющую состояние автомата a(t + 1) в момент дискретного времени t + 1 в зависимости от состояния автомата a(t) и значения входного сигнала x(t) в момент времени t: a(t + 1) = f[a(t), x(t)]; (10.1) - функцию выходов , определяющую зависимость выходного сигнала автомата y(t) от состояния автомата a(t) и входного сигнала x(t) в момент времени t: y(t) =  [a(t), x(t)]. (10.2) Кроме того, на множестве состояний автомата фиксируют одно из внутренних состояний а0 в качестве начального состояния. Понятие состояние автомата используется для описания систем, выходные сигналы которых зависят не только от входных сигналов в данный момент времени, но и от некоторой предыстории, т.е. сигналов, которые поступали на входы системы ранее. Следовательно, цифровые автоматы относятся к последовательностным схемам, которые, как уже отмечалось, обладают памятью. Понятие состояние автомата соответствует некоторой памяти о прошлом, поэтому ввод этого понятия позволяет устранить время как явную переменную и выразить выходные сигналы как функцию состояний и входных сигналов. Работу абстрактного автомата следует рассматривать применительно к конкретным интервалам времени, т.к. каждому интервалу дискретности t будет соответствовать свой выходной сигнал y(t). Следовательно, функционирование автомата рассматривается через дискретные интервалы времени конечной продолжительности. В абстрактной теории цифровых автоматов считается, что входные сигналы воздействуют на синхронный автомат в момент начала каждого i-того интервала (кванта) времени, выделенного соответствующим синхроимпульсом (тактом), а изменение внутренних состояний автомата происходит в интервалы времени между смежными синхроимпульсами, когда нет воздействия входных сигналов. Операторы, описывающие работу автомата, обычно задают таблицей переходов и таблицей выходов. В таблице переходов показывают в какое состояние попадает автомат от того или иного входного сигнала. В таблице выходов показывают какой выходной сигнал генерирует автомат в зависимости от типа входного сигнала и текущего состояния автомата. К примеру, рассмотрим таблицы переходов и выходов некоторого автомата. Таблица переходов автомата Таблица выходов автомата В клетку таблицы переходов, находящуюся на пересечении столбца с буквой аi и строки с буквой xj, записывается состояние автомата, в которое он переходит из состояния аi при подаче на вход сигнала xj. В аналогичную клетку таблицы выходов записывается выходной сигнал yi, который формируется автоматом при таком переходе. Операторы переходов и выходов могут быть заданы одной таблицей, по которой однозначно определяются переходы и выходы автомата. Таблица переходов и выходов автомата большую наглядность обеспечивает задание конечных автоматов с помощью графов или диаграмм состояний. Граф автомата состоит из узлов, соединенных ветвями. Узлы (кружки на схеме графа) отождествляют внутренние состояния автомата. Каждая ветвь графа, т.е. ориентированная линия, стрелка которой указывает следующее состояние автомата, отмечается входным сигналом, вызывающим в автомате соответствующий данной ветви переход, и выходным сигналом, который возникает при этом переходе. Входной и соответствующий ему выходной сигналы разделяются на чертеже запятой или косой чертой. Если некоторый входной сигнал не меняет состояния автомата, то соответствующая ветвь замыкается на кружке (узле), из которого она выходит. Поскольку таблица состояний и граф (диаграмма) состояний несут одну и ту же информацию, их можно преобразовать друг в друга. Каждое состояние представляется кружком, а каждый элемент таблицы преобразуется в отрезок ориентированной линии, соединяющей соответствующие кружки. Процедура обратного преобразования очевидна. В настоящее время в классе синхронных атоматов рассматривают, в основном, два типа автоматов: автомат Мили и автомат Мура. Графа атомата Мили, заданного вышеприведенными таблицами, отражен на рис. 10.1. Закон функционирования автоматов Мили может быть задан следующим образом: a(t + 1) = f[a(t), x(t)]; y(t) =  [a(t), x(t)], где t = 1, 2, ..... Отличительная особенность автоматов Мили состоит в том, что их выходные сигналы в некоторый момент времени не зависят как от состояния автомата, так и от значения входного сигнала в этот же момент времени. Рис. 10.1. Граф автомата Мили. У автоматов Мура выходные сигналы в момент времени t однозначно определяются состоянием автомата в этот же момент времени и в явном виде не зависят от значения входных сигналов xi(t). Функции переходов и выходов автомата Мура, заданного на множестве входных сигналов X, множестве внутренних состояний A = {a0, a1, ,an} и множестве выходных сигналов Y, можно записать в виде a(t + 1) = f[a(t), x(t)], (10.3) y(t) =  [a(t)]. (10.4) эти операторы удобно задавать отмеченной таблицей переходов. Такие таблицы строятся так же, как и таблицы переходов автомата Мили, но над символами каждого внутреннего состояния записываются выходные сигналы, которые выдает автомат в данном состоянии. Отмеченная таблица переходов автомата Граф автомата Мура, заданного этой таблицей, приведен на рис. 10.2. На этом рисунке состояния автомата обозначаются сиволами bi. На графах автомата Мура значения выходных сигналов записываются около узлов. Рис. 10.2. Автомат Мура. Между автоматами Мили и Мура существует соответствие, позволяющее преобразовать закон функционирования одного из них в другой или обратно. Автомат Мура можно рассматривать как частный случай автомата Мили, имея в виду, что последовательность состояний выходов автомата Мили опережает на один такт последовательность состояний выходов автомата Мура, т.е различие между автоматами Мили и Мура состоит в том, что в автоматах Мили состояние выхода возникает одновременно с вызывающим его состоянием входа, а в автоматах Мура - с задержкой на один такт, т.к в автоматах Мура входные сигналы изменяют только состояние автомата. Помимо автоматов Мили и Мура выделяют еще, так называемый, совмещенный автомат - С-автомат. Абстрактный С-автомат можно представить в виде устройства с одним входом, на который поступают входные сигналы X, и двумя выходами, на которых появляются выходные сигналы Y и U. A Y рис. 10.3 X U Здесь X - входной алфавит; A - множество состояний; Y - выходной алфавит первого типа; U = {u1(t) ... um(t)} - выходной алфавит второго типа. Отличие С-автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов 1 и 2, каждая из которых характерна для этих моделей в отдельности. Этот автомат можно описать следующей системой уравнений: a(t+1) = f [a(t), x(t)]; (10.5) y(t) = 1[a(t), x(t)]; u(t) = 2[a(t)]. Выходной сигнал u = 2(as) выделяется все время, пока автомат находится в состоянии as. Выходной сигнал yk = 1(as, xn) выдается во время действия входного сигнала xn при нахождении автомата в состоянии as. От С-автомата легко перейти к автоматам Мили или Мура (с учетом возможных сдвигов во времени на один такт), так же как возможна трансформация автомата Мили в автомат Мура и наоборот. Буква, слово, алфавіт. Переваги, фізична реалізація та форми представлення дволітерних алфавітів. Буква – сигнал, який поступає на вхід ЦА в момент часу ti (проміжна, вихідна) Слово – послідовність вхідних букв. Алфавіт – це множина всіх букв, які відрізняються. A X Y Для задания конечного автомата фиксируются три конечных множества (алфавита): - множество возможных входных сигналов: X = {x1, x2, ..., xm}; - множество возможных выходных сигналов: Y = {y1, y2, ..., yk}; - множество возможных внутренних состояний автомата:A = {a0, a1, ..., an}. Причини застосування двозначного алфавіту: У внутрішньому алфавіті кожна буква з двох являє зоною чи смугою. EMBED Visio.Drawing.11 Відрізняються стани не тільки кількісно, але і якісно. Арифметичні та логічні операції виконуються простіше в двохбуквених алфавітах. Простіше реалізовуються пристрої памяті. Фізичне представлення Форми представлення EMBED Visio.Drawing.11 EMBED Visio.Drawing.11 Потенціальна (статична) 4. Фазова EMBED Visio.Drawing.11 EMBED Visio.Drawing.11 Імпульсна (динамічна) EMBED Visio.Drawing.11 EMBED Visio.Drawing.11 EMBED Visio.Drawing.11 Частотні Алгебра логіки. Поняття про аналіз і синтез. Операції суперпозиції та перестановки. Логической основой цифровых автоматов или компьютеров является алгебра логики (булева алгебра) - одна из основных частей математической логики. Теория логических основ цифровых автоматов чрезвычайно насыщена достаточно специфическими терминами, понятиями. Поэтому в этой главе и во всех последующих будет приведено много определений этих понятий. Причем, нередко для одного и того же понятия будет использовано несколько определений для более четкого понимания его сущности и взаимосвязи с другими специфическими понятиями теории логических основ цифровых автоматов. Итак, приведем первый вариант определения понятий логической переменной и логической функции. Функция f(x1, x2, ..., xn) называется логической (переключательной), или булевой, если она, так же как и ее аргументы xi, может принимать только два значения: 0 или 1. Логическая (булева) переменная эта такая величина x, которая может принимать только два значения: 0 или 1. Таким образом, логические функции, их аргументы и просто логические переменные могут принимать только два значения 0 или 1. Причем, в этих случаях цифры 0 и 1 являются символами состояния, а не числами. Алгебра логики является алгеброй состояний, а не алгеброй чисел, поэтому эту алгебру называют также алгеброй высказываний. Совокупность значений аргументов логической функции называется набором (или точкой) и может обозначаться, в частности, как х1, х2,..., хn, где xi равно нулю или единице (i = 1, 2, ..., n). Очевидно, что набор значений аргументов фактически представляет собой некоторое двоичное число. Каждому набору значений аргументов приписывается номер, равный двоичному числу, которое соответствует значению данного набора. Например, для четырех аргументов 0, 0, 0, 0 - нулевой набор; 0, 0, 0, 1 - первый набор;0, 0, 1, 0 - второй набор; 1, 0, 1, 0 - десятый набор и т.д. Суперпозиція Подстановка в логическую функцию вместо ее аргументов других логических функций называется суперпозицией. xyz=x (yz), xyz=x(yz), xyzx(yz) Перестановка xy= yx, xy=yx, xyyx Змінна, набір, функції алгебри логіки (ФАЛ) нуля, однієї та двох змінних Совокупность значений аргументов логической функции называется набором (или точкой) и может обозначаться, в частности, как х1, х2,..., хn, где xi равно нулю или единице (i = 1, 2, ..., n). Очевидно, что набор значений аргументов фактически представляет собой некоторое двоичное число. Каждому набору значений аргументов приписывается номер, равный двоичному числу, которое соответствует значению данного набора. Например, для четырех аргументов 0, 0, 0, 0 - нулевой набор; 0, 0, 0, 1 - первый набор;0, 0, 1, 0 - второй набор; 1, 0, 1, 0 - десятый набор и т.д. Таким образом, логическая функция (функция алгебры логики) это функция f(x1, x2, ..., xn) которая принимает значение 0 или 1 на наборе логических переменных x1, x2, ..., xn. Каждой логической функции данного набора аргументов, также принято приписывать номер: 0, 1, 2,....... Любая логическая функция n аргументов определена на 2n наборах, т.е. может иметь 2n наборов. Число различных логических функций n аргументов конечно и равно 2 EMBED Equation.2 . Неполностью определенная логическая функция n переменных, это функция, заданная на числе наборов меньшем 2n. Для наборов, на которых функция не определена, ее значение можно принять произвольным. Например, для одного аргумента имеем 21, т.е. 2 набора и 22 , 4, т.е. четыре логические функции от одной переменной, которые приведены в таблице 7.1. Т а б л и ц а 7.1 В связи с тем, что функция f0(x) равна единице при любых значениях аргумента, то эта функция называется абсолютно истинной (константа единицы), тогда функция f1(x) - абсолютно ложная функция (константа нуля). Функция f2(x), повторяющая абсолютное значение логической переменной, - тождественная функция: f2(x)  x. Функция f3(x), принимающая значение, обратное значению x, - логическое отрицание (инверсия), или функция НЕ (NOT), которая обозначается одним из следующих способов: f3(x) =  x = x. Логическое отрицание или инверсия некоторой логической переменной, например переменной А, это также логическая переменная, принимающая значение обратное значению переменной А, и обозначаемая как А. Если А =1, то А = 0, если же А = 0, то А = 1. Но нужно учесть, что часто посредством отрицания, т.е. инверсии переменной просто обозначают случай, когда ее значение равно нулю. ФАЛ 2-х Дизъюнкция (логическое сложение) или функция ИЛИ (OR) - это функция f7(x1, x2), которая истинна тогда, когда истинна хотя бы одна из ее переменных. Условные обозначения этой функции: f7(x1, x2) = x1 + x2 = x1  x2 = x1 ! x2 Это читается следующим образом: функция истинна, т.е. равна единице, когда аргумент x1 = 1, т.е. истинен, или аргумент x2 = 1, или же оба аргумента истинны одновременно. Т а б л и ц а 7.2 Конъюнкция (логическое умножение) или функция И (AND) - это функция f1(x1, x2), которая истинна тогда, когда все ее переменные одновременно истинны. Эту функцию условно обозначают следующим образом: f1(x1, x2) = x1  x2 = x1  x2 = x1 & x2 Это читается следующим образом: функция истинна, т.е. равна единице, когда оба аргумента одновременно истинны, т.е. равны единице. Функция (штрих) Шеффера или функция И-НЕ - это функция f14(x1, x2), которая ложна тогда, когда все переменные истинны. Условное обозначение этой фнкции: f14(x1, x2) = x1/x2 Это читается следующим образом: функция ложна, т.е. равна 0, когда оба аргумента одновременно истинны, т.е. равны единице, и функция истинна, т.е. равна единице, когда или оба аргумента одновременно ложны, или же хотя бы один из них ложен. Функция (стрелка) Пирса (Вебба) или функция ИЛИ-НЕ - это функция f8(x1, x2), которая истинна только тогда, когда все переменные ложны. Условное обозначение этой функции: f8(x1, x2) = x1  x2 = x1 O x2. Это читается следующим образом: функция ложна, т.е. равна 0, когда хотя бы один из ее аргументов истинен, или же оба одновременно истинны, т.е. равны единице, и функция истинна, т.е. равна единице, когда оба аргумента одновременно ложны. Импликация или функция ЕСЛИ-ТО (IF-THEN) это функция f13(x1, x2), которая ложна тогда и только тогда, когда x1 истинно и x2 ложно. Аргумент х1 называется посылкой, а х2 - следствием. Ее условное обозначение f13(x1, x2) = x1  x2. Исключающее ИЛИ (XOR) - это функция f6(x1, x2), которая обозначается знаком . Эта операция, как видно из таблицы, реализует функцию неравнозначности, т.е. фактически реализуется процедура суммирования по модулю 2, которая обозначается знаком : f6(x1, x2) = x1  x2 = x1  x2 Все рассмотренные функции являются элементарными. Из всех приведенных выше определениий ясно, что в алгебре логики все знаки действий:  или &,  или +, ,  и т.д, в отличии от обыкновенной алгебры, являются знаками логических связок, т.е. логических действий, а не знаками арифметических действий. Введем еще три специфических понятия алгебры логики. Две функции считаются равносильными друг другу, если они принимают на всех возможных наборах своих аргументов одни и те же значения. Логическая переменная xi действительна, если значение логической функции f(x1, x2, ..., xn) изменяется при изменении xi. В противном случае эта переменная для данной функции фиктивна, т.е. не является ее аргументом. Необходимость ввода этих двух последних понятий возникла по следующей причине. При анализе некоторой неизвестной логической функции (логической схемы), для которой необходимо сформировать аналитическое выражение, не все подключаемые для этого анализа логические переменные могут быть аргументами этой функции, что и выявляется в итоге проведенного анализа. Как будет показано в дальнейшем, любые логические операции над логическими переменными можно свести к определенной совокупности элементарных логических функций, например, таких как И, ИЛИ, НЕ и исключающе ИЛИ. Элементарные логические операции в компьтерах выполняются также над двоичными числами, по разрядно. Рассмотрим несколько простых примеров выполнения логических операций над двумя двоичными числами: И ИЛИ Искл. ИЛИ НЕ 01011010 0101010 0101010 01011010 11110000 1111000 1111000 10100101 01010000 1111010 1010010 Подстановка в логическую функцию вместо ее аргументов других логических функций называется суперпозицией. Система логических функций называется функционально полной, если с помощью функций, входящих в эту систему, применяя операции суперпозиции и подстановки, можно получить любую сколь угодно сложную логическую функцию. Основні властивості ФАЛ за Постом. Методи виявлення ФАЛ із цими властивостями. Для побудови ПС(повна система) ФАЛ(Функція Алгебри-Логіки) яка має хоч би одну функцію, яка не зберігає константу 0, не зберігає константу 1, нелінійна, немонотонна, несамодвоїста. Якщо функція на нульовому наборі змінних дорівнює 0, то ф-ція зберігає конст. 0. Якщо функція на одиничному наборі змінних дорівнює 1, то ф-ція зберігає конст. 1. ФАЛ назив. монотонною, якщо при будь-якому зростанні кількості 1 у послідовності сусідніх( тобот на тих, які відрізняються тільки в одному розряді) на наборі змінних значення функції не змінюється або збільшується. ФАЛ назив. самодвоїстою, якщо на кожній парі протилежних наборів (х0,х1,..) та (#х0, #х1,..) вона приймає протилежні значення. EMBED Equation.3 ФАЛ назив. лінійною , якщо її можна зобразити поліномом 1 порядку в базисі Жегалкіна без добутків змінних ВСАС1 – нелінійна АС1 - лінійна EMBED Equation.3 Приклад нелінійна лінійна Базис Жегалкіна. Основні тотожності. Синтез комбінаційних схем на прикладі однорозрядних суматорів на два та на три входи. EMBED Equation.3 {&, , 1} Реалізація комбінаційних схем Однорозрядний суматор на 2 входи EMBED Visio.Drawing.11 EMBED Visio.Drawing.11 S=AB P=AB Однорозрядний суматор на 3 входи S=ABC P=ABCABCABCABC=(A1)BCA(B1)CAB EMBED Visio.Drawing.11 (C1) ABC=ABCBCABCACABCABABC= =BCACAB EMBED Visio.Drawing.11 Базис Буля. Основні тотожності. EMBED Equation.3 {&, , } Рассмотрим основные законы, аксиомы и теоремы алгебры логики Некоторые законы обычной алгебры применимы и к алгебре логики. Например: Закон коммутативности: для умножения АВ = ВА для сложения A  B = B  A Закон ассоциативности: для умножения A(BC) = (AB)С для сложения A  (B  С) = (A  B)  С Закон дистрибутивности умножения по отношению к сложению: A(B  С) = AB  AC В алгебре логики действует также закон дистрибутивности сложения по отношению к умножению: A BС = (A  B)(A  С) Алгебра логики имеет ряд специфических аксиом и теорем, основные из которых, необходимые для анализа и синтеза логических цепей или схем, приведены ниже. В алгебре логики широко используется также специфический закон склеивания: Форми завдання ФАЛ у базисі Буля. Класифікація аналітичних форм завдання ФАЛ у базисі Буля. Таблиці Скорочені Квадратні таблиці 2. Аналітичний EMBED Visio.Drawing.11 Досконала – будь-які нормальні форми можуть бути дизюктивними та конюктивними, кожний терм має усі змінні. Мінімальна – яка має мінімальну к-ть букв. Скорочена – коли хоча б 1 терм не має всіх змінних. Найкоротша – має мінімальну к-ть термів, змінних, букв. Например, если некоторая, заданная таблично, функция f(x1, x2, x3) принимает значение единицы на наборах с номерами 0, 3, 4 и 6, то ее можно представить следующим образом: f(x1, x2, x3) = F(0, 3, 4, 6), 1 или f(x1, x2, x3) =  F(0, 3, 4, 6), Если эта же функция на наборах 1, 2, 5, 7 - принимает значение 0, то ее можно представить так: f(x1, x2, x3) = F(1, 2, 5, 7), 0 или f(x1, x2, x3) =  F(1, 2, 5, 7) Такую форму записи называют числовой. Первый вид такой формы используют когда функция представляется в СНДФ, а второй - когда в СНКФ. Многие преобразования, выполняемые над логическими функциями, иногда удобно интерпретируются с использованием их геометрических представлений. Например, функцию двух переменных можно интерпретировать как некоторую плоскость, заданную в системе координат х1, х2. Если отложить по каждой оси единичные отрезки х1 и х2, то получится квадрат, вершины которого соответствуют комбинациям переменных. x1x2 x1 x1x2 x2 x2 x1x2 x1 x1x2 Отсюда следует, что две вершины, принадлежащие одному и тому же ребру и называемые соседними, "склеиваются" по переменной, меняющейся вдоль этого ребра. Например, x1x2 + x1x2 = x2, т.к, как нам уже известно, из свойств логических функций, что x1x2 + x1x2 = (x1 + x1)x2 = 1x2 = x2 Для функций трех переменных геометрическое представление выполняют в виде трехмерного куба. Ребра куба поглощают вершины. Грани куба поглощают свои ребра и, следовательно, вершины. В случае же четырех переменных - "четырехмерного" куба. В геометрическом смысле каждый набор переменных x1, x2, x3,...., xn можно рассмаривать как n-мерный вектор, определяющий точку n-мерного простанства. Поэтому все множество наборов, на которых определена функия n переменных, представляется в виде вершин n-мерного куба. Координаты вершин куба указываются в порядке, соответствующем порядку перечисления переменных в записи функции. Отмечая точками вершины, в которых функция принимает значение, равное единице, получаем геометрическое представление ФАЛ. Проблема мінімізації у базисі Буля. Канонічна та загальна задачі мінімізації. Огляд методів розв’язання. EMBED Equation.3 EMBED Visio.Drawing.11 1. EMBED Visio.Drawing.11 2. Карта Карно EMBED Equation.3 EMBED Visio.Drawing.11 EMBED Equation.3 EMBED Equation.3 3. 4. Метод глобального винесення за дужки: EMBED Equation.3 11 букв 9 букв 8 букв Чим більше винесення за дужки, тим менша швидкодія 5.Введення надлишковості з глобальним винесенням за дужки: x1x2x3x1x3x4x5x1x2x4x6x4x5x6 = – 14 букв =x1x2(x1x3x4x6) x4x5(x1x3x4x6)=(x1x3x4x6)(x1x2x4x5) – 8 букв Особливості застосування методу мінімізації Квайна-Мак-Класкі-Петріка в базисі Буля. Метод получения сокращенной дизъюнктивной нормальной формы логической функции называется методом Квайна. При минимизации по методу Квайна в базисе 1 предполагается, что исходная функция задана в СНДФ. Напомним, что импликанта функции - это некоторая логическая функция, обращаемая в ноль при наборе переменных, на которых сама функция также равна нулю. Поэтому любой минтерм в составе СНДФ, или группа минтермов, соединенных знаками дизъюнкции, являются импликантами исходной НДФ. Первичная или простая импликанта функции - это импликанта типа элементарной конъюнкции некоторых переменных, никакая часть которой уже не является импликантой данной функции. Дизъюнкция простых импликант, ни одну из которых исключить нельзя, называется тупиковой НДФ заданной функции. Некоторые функции имеют несколько тупиковых форм. Тупиковые формы, содержащие наименьшее количество букв, будут минимальными. Задача минимизации по методу Квайна состоит в попарном сравнении всех импликант, входящих в СНДФ, с целью выявления возможности поглощения какой-то переменной: Fxi  Fxi = F Таким образом, удается снизить ранг термов. Эта процедура проводится до тех пор, пока не останется ни одного члена, допускающего поглощение с каким-либо другим термом. Термы, подвергшиеся поглощению, отмечаются. Неотмеченные термы представляют собой первичные импликанты. Полученное логическое выражение не всегда оказывается минимальным. Поэтому исследуется возможность дальнейшего упрощения. Для этого составляется таблица, в строках которой записываются найденные первичные импликанты, а в столбцах указываются термы исходного уравнения. Клетки этой таблицы отмечаются в случае, если первичная импликанта входит в состав какого-либо терма. После этого задача упрощения сводится к тому, чтобы найти такое минимальное количество первичных импликант, которые покрывают все столбцы. В этом методе используются операции неполного склеивания (полным склеиванием, как нам известно, будет:xy  xy = x) и поглощения (x  xy = x). Применяемая в методе Квайна операция неполного склеивания определяется формулой: xy  xy = x  xy  xy. Заметим, что в правой части равенства, кроме члена ч, полученного в результате полного склеивания, остаются оба члена, участвующие в склеивании. Теорема Квайна. Если в совершенной дизъюнктивной нормальной форме логической функции провести все операции неполного склеивания и затем все операции поглощения, то в результате получается сокращенная дизъюнктивная нормальная форма этой функции, т.е. дизъюнкция всех ее простых импликант. Метод Квайна выполняется в несколько этапов и сокращенную НДФ удобно находить в следующей последовательности. Провести в СНДФ функции все возможные операции склеивания конституент единицы. В результате этого образуются произведения, содержащие (n - 1) букв. Подчеркнем, что склеиваться могут только произведения с одинаковым числом букв. Поэтому после этой процедуры производится операция поглощения, а затем выполняются все возможные склеивания членов с (n - 1) буквой. После этого проводится поглощение членов с (n - 1) буквой и вновь выполняется операция склеивания членов с числом букв, равным (n - 2), и т.д. Пример. Найти сокращенную дизъюнктивную нормальную форму логической функции, заданной таблично. Представим функцию в совершенной дизъюнктивной нормальной форме f(x, y, z) =xyz  xyz  xyz. В правой части полученного выражения можно выполнить только одно склеивание: второго члена с третьим по переменной z. При этом получим f(x, y, z) = xy xyz  xyz  xyz. Произведение xy поглощает члены xyz b xyz: f(x, y, z) = xy xyz. Это выражение является сокращенной дизъюнктивной нормальной формой заданной логической функции, так как дальнейшее применение склеивания и поглощения невозможно. Теперь рассмотрим процедуру минимизации более сложной функции с использованием импликативных матриц. Предположим, что требуется найти минимальную НДФ логической функции, СНДФ которой определяется выражением: f(A, B, C, D) =ABCD ABCD  ABCD  ABCD  ABCD ABCD Построим для этой функции импликантную матрицу, представляющую собой таблицу, в вертикальные и горизонтальные входы которой записываются все конституенты единицы, т.е. все минтермы, и все простые импликанты заданной функции соответственно. Для нахождения простых импликант мы должны провести вначале процедуру неполного склеивания. Чтобы быстрее находить члены, которые склеиваются друг с другом, напомним, что склеиваться могут только соседние члены, т.е. такие члены, у которых число переменных с отрицаниями отличается на единицу. Проведем операции склеивания в следующем порядке: - выполним все возможные склеивания 1-го члена с остальными; - выполним все возможные склеивания 2-го члена с остальными, кроме 1-го; - выполним все возможные склеивания 3-го члена с остальными, кроме 1-го и 2-го и т.д. Запишем результат: 1* - 2* =ABCD ABCD = ACD(BB) =ACD (по B); 2 - 3* =BCD (по A); 3 - 4* = ABD (по C); 4 - 5* = ABC (по D); 5 - 6* = BCD (по A). Получили простые импликанты. После процедуры неполного склеивания выражение примет следующий вид: f(A, B, C, D) =ABCD* +ACD +ABCD* +BCD + ABCD* + ABD + ABCD* +ABC + ABCD* +BCD +ABCD* Звездочками отмечены те члены, которые поглощаются произведениями, образовавшимися после склеивания. Теперь проведем операцию поглощения. Для каждой импликанты найдем конституенты единицы, т.е. минтермы, которые ею поглощаются, т.е. те конституенты, собственной частью которых является данная импликанта. Например, импликанта ACD поглощает конституенты ABCD, ABCD, импликанта BCD - конституенты ABCD, ABCD и т.д. ABCD* +ACD = ACD(1 + B) =ACD; ABCD* + ABCD* +BCD = BCD(1 + A +A) =BCD; ABCD* +ABC = ABC(1 + D) =ABC; ABCD* +ABCD* +BCD = BCD(1 + A +A) = BCD; Теперь рассмотрим принцип построения и использования импликантной матрицы на примере матрицы, приведенной в Таблице 8.2. Клетки импликантной матрицы, образованные пересечением строк с импликантами и колонок с поглощенными ими конституентами, отметим крестиками. Т а б л и ц а 8.2. Импликантная матрица Чтобы получить минимальную НДФ заданной функции, достаточно найти минимальное число импликант, которые совместно накрывают крестиками все колонки импликантной матрицы. Из таблицы следует, что в минимальную форму обязательно должны войти импликанты ACD и BCD, так как только они накрывают крестиками первую и шестую колонки таблицы. Кроме того, импликанта ACD накрывает вторую, а импликантаBCD - пятую колонки. Поэтому остается накрыть только третью и четвертую колонки таблицы. Для этого можно выбрать пары импликант BCD и ABD; ABD и ABC или одну импликанту ABD. Если выбрать указанные выше пары импликант, члены BCD и ABC оказываются лишними, так как импликанта ABD одна накрывает третью и четвертую колонки таблицы. Таким образом, выбрав импликанту ABD, получим минимальную НДФ заданной функции: f(A, B, C, D) =ACDABDBCD. На основании вышеизложенного сформулируем алгоритм получения минимальных НДФ логической функции. 1. Логическую функцию представляют в совершенной НДФ, применяя либо запись "по единицам" функции, если функция задана таблично, либо применяя операции развертывания, правила де Морганаи и другие формулы алгебры логики, если функция задана в произвольной аналитической форме. 2. В полученной совершенной НДФ проводят все операции неполного склеивания и поглощения. В результате получается сокращенная НДФ заданной функции. 3. Находят минимальные НДФ по импликантной матрице. Если количество членов в сокращенной НДФ невелико, то можно найти тупиковые формы методом испытания членов и выбрать среди них минимальные. Заметим, что в ряде случаев минимальная НДФ совпадает с сокращенной. Например, сокращенная НДФ любой логической функции двух аргументов совпадает с минимальной, в чем нетрудно убедиться, проведя испытание членов в сокращенной НДФ любой функции, приведенной в Таблице 7.2. Для того чтобы найти выражение заданной логической функции, наиболее удобное для синтеза логической схемы, следует, кроме МНДФ функции, получить также ее минимальную НКФ и выбрать из них ту, при технической реализации которой потребуется наименьшее количество логических элементов. Один из алгоритмов получения МНКФ функции практически аналогичен описанному. В этом случае также вначале тем или иным способом формируется СНКФ функции. Далее находится сокращенная НКФ, по которой определяются тупиковые НКФ. Наконец, по ним находится МНКФ заданной функции. Только очевидно, что если функция задана таблично, то СНКФ формируется "по нулям" функции. Во всех же дальнейших процедурах минимизации учитывается, что в этом случае используются макстермы, т.е. элементарные суммы, а не элементарные призведения. Импликанта, в том числе и простая, - также элементарная сумма. Операция неполного склеивания и поглощения для конъюнктивной формы определяется соответственно следующими соотношениями: (x + y)(x +y) = x(x + y)(x +y), x(x + y) = x, а формулы развертывания имеют вид: x = (x + y)(x +y), (x + y) = (x + y + z)(x + y +z). При испытании членов сокращенной НКФ исключают испытываемый член и в оставшееся выражение подставляют такие значения переменных, которые обращают исключенный член в но...

Державний іспит Інші

01.01.1970 03:01-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись