metod_15.03.04_atppp_oaip_ump_2016 (Методические документы), страница 9

Если условиеоднозначности не является необходимым, то во многих случаях СНФ имеют некоторуюизбыточность, т.е. включают фиктивные переменные, от которых необходимоизбавиться до аппаратной реализации ФАЛ. Минимальная форма представления ФАЛсодержит минимальное количество термов и переменных в термах и более не допускаетникаких упрощений (минимизации). Так при минимизации СДНФ сокращается доминимума количество конъюнкций и число переменных в каждой из них.Минимизация (упрощение) булевых функций производится с помощью теоремалгебры логики и может быть реализована аналитическими методами, графическимиметодами и арифметическими методами с помощью теоремы Квайна-Мак-Класки.Аналитические методы.Наиболее эффективными приемами аналитических методов минимизации являютсявынесение за скобки общих членов, а также применение двойного отрицания, теоремыде-Моргана, законов поглощения и склеивания.

При этом, наряду с полнымсклеиванием, т.е. использованием зависимости AB AB = B или (A  B)( A  B ) = B(склеивание по A) часто применяют неполное склеивание – оба члена склеивания илиодин из них остаются и склеиваются с другими членами СДНФ. Неполное склеиваниеможет рассматриваться как сочетание закона склеивания и идемпотентности. Припреобразовании следует помнить, что логические операции имеют старшинство – впорядке убывания  , , .Пример 1. Упростить выражениеf(x1, x2) = x1 x1x2 = 1x1 x1x2 = x1(x2  x2) x1x2 = x1x2  x1 x2  x1 x2 x1x2 = x1(x2  x2)  x2 ( x1 x1) = x1  x2.Пример. Минимизировать ФАЛ, заданную таблицей истинности.СДНФ этой ФАЛ = AB C ABC  ABC  ABC  ABC ABC  ABC =AC(B + B) + AB (C + C) + AB (C + C) + ABC =A (C + BC) + A = A + B + C.38A00001111B00110011C01010101f (ABC)01111111Пример 2.

Дана таблица истинности. Найти СДНФ и минимизировать ее.x1 x20 00 00 10 11 01 01 11 1x301010101f (x1 x2 x3)00101110Проверка00101110fСДНФ (x1, x2, x3) = x1x2 x3  x1x2x3 x1 x2x3 x1 x2x3 = x1x2 (x3 x3)  x2x3 (x1x1) = x1x2  x2x3 = fминДНФ.Чтобы проверить правильность достаточно вместо переменных в полученнуюфункцию подставить их значения из таблицы.Построение логических схемЭлектронные схемы можно условно разбить на два рода:— схемы первого рода - комбинационные схемы;— схемы второго рода - накапливающие схемы (элементы с памятью).Комбинационные схемы - схемы, выходной сигнал в которых зависит только отсостояния входов (наличия входных сигналов) в каждый момент времени.Накапливающие схемы - схемы, выходной сигнал в которых зависит как от входныхсигналов, так и от состояния схемы в предыдущие моменты времени.Большинство ЭВМ состоит из комбинации схем первого и второго родов разнойсложности.Схемы различают в зависимости от количества входов и выходов.1.

Рассмотрим комбинационные схемы.Для построения логических комбинационных схем используются специальныеграфические изображения логических функций.Задача синтеза электронной логической схемы формулируется следующим образом:при заданных входных переменных и известной выходной функции необходимо39синтезировать логическое устройство, выполняющее эту функцию. При этом обычноналагаются ограничения на используемую систему логических элементов (логическийбазис). В результате решения задачи синтеза возникает логическая схема,воспроизводящая заданную функцию.1. Элемент «НЕ» - инвертор1х2.

Элементх1х«ИЛИ» -дизъюнктор1х1+х2х23. Элемент «ИЛИ-НЕ» - дизъюнктор/инверторx114. Элемент «И» - конъюнкторх1x1+x2&х1*х2х2х25. Элемент «И – НЕ» - конъюнктор/инверторх1&____х1*х2х2При решении задачи анализа и синтеза используют полные базисы функций. Приэтом каждую логическую функцию, входящую в базис, сопоставляют с некоторымфизическим элементом, следовательно, логическую схему можно заменитьструктурной схемой, состоящей из физических элементов.

Этот путь позволяетсоединить математическую задачу синтеза логической схемы с инженерной задачейпроектирования электронной схемы. При разработке электронной схемы за основныекритерии принимают: минимум аппаратуры, минимум типов применяемых элементов,максимум надёжности.С позиций математической логики задача синтеза решается при обеспеченииминимального числа логических операторов, минимального количества типовлогических операторов.

Сформулируем последовательные этапы решения задачисинтеза логической схемы:1) составление математической модели (системы логических уравнений),отображающие происходящие в схеме процессы;2) анализ логических уравнений и получение минимальной формы для каждой изних в заданном базисе;403) переход от логических уравнений к логической (структурной) схеме посредствомприменения логических операторов.

(Логический оператор схемы - элементарнаялогическая функция, с помощью которой описывается работа схемы).В общем случае задача синтеза имеет множество решений, которые зависят отвыбранной системы логических элементов. Если за критерий оптимальности схемывзять минимальное количество логических связок, то это потребует нахожденияминимальной формы для функции алгебры логики. В случае сложных схем, имеющихнесколько выходов, можно решить задачу синтеза путём декомпозиции частных схем содним выходом.Пример:Синтезировать схему ( с двумя выходами), задаваемую таблицей в базисе И-ИЛИНЕ (двоичный сумматор):ai00001111bi00110011Пi-101010101ci01101101Пi00010111Здесь аi, вi - слагаемые i-го разряда, операндов а и в; сi - сумма cлагаемых i- горазряда; Пi и Пi -1- соответственно переносы из i-го и (i-1)-го разрядов.Синтезируемую схему можно рассматривать как схему, состоящую из двух частей:(1)- схемы, для получения поразрядной суммы Сi;(2)- схемы, для получения переноса Пi.Временные булевы функцииКроме комбинационных схем, называемых схемами первого рода, различают, какупоминалось выше, накапливающие схемы, включающие элементы с памятью.Основной особенностью схем с памятью является тот факт, что алгоритм их работызависит от времени.

Поэтому в число переменных для функций, описывающихнакапливающие схемы, должно входить время t. Однако время не является двоичнойпеременной. Поэтому вводится так называемое автоматное время, принимающеедискретные целочисленные значения 0, 1, 2, ... , и т.д. Это означает, что работа схемы спамятью распадается на ряд интервалов, в течение которых автоматное время условнопринимает постоянное значение.Определение. Временная булева функция (ВБФ) это логическая функцияy=φ(х1,х2, ...

,хn,t), принимающая значение {0,1} при 0≤t≤s-1, где s- количествоинтервалов автоматного времени:0 1s-141│ ││ │ ││││t0 12 ...s-1 sСуществует теорема о том, что любая периодическая временная булева функцияможет быть представлена в аналитическом виде следующим образом:y = φ(х1,х2, ... ,хn,t) = φ0τ0 + φ1τ1 + ... + φs-1τs-1,где φ i- конъюнктивный терм (или их дизъюнкция) от переменных х1,х2, , ... ,хn;τi- вспомогательная функция, принимающая значение из множества {0,1} в моментвремени ti.Такая форма представления временных логических функций позволяет применить кфункциям » все методы упрощения и минимизации ФАЛ.Пример: преобразовать функцию, представленную таблицей, в аналитический вид.х1001100110011х2010101010101t000011112222φ(х1, х2, t)001001100011Решение.

Функция определена на трёх интервалах времени и поэтому представляемеё совокупностью трёх логических функций φ 0(x1,x2,t), φ 1(x1,x2,t) и φ2(x1,x2,t),которые для значений функции, равных 1, могут быть представлены следующимобразомφ 0(x1, x2, t) = х1х2, для t = 0;φ 1(x1, x2, t) = х1 х2 + х1х2, для t = 1;φ 2(x1, x2, t)= x1x2+ x1 x2 = x1, для t = 2.Определяем значение временного параметра ВБФ для каждого временногоинтервала:для t = 0 – только τ0 = 1;для t = 1 - только τ1 = 1;для t = 2 – только τ2 = 1;Следовательно, аналитическое выражение таблично заданной ВБФ:y = x1x2 τ0+ (x1x2+ x1x2) τ1+ x1τ2.42Схема для полученной формулы строится аналогично с построениемкомбинационных схем плюс элемент-дешифратор, имеющий вид:012CD123….nnгде τ i - выход i-й функции, принимающей значение, равное 1 в ti; все остальные τ вданный момент равны 0.Если ВБФ зависит ещё и от своих предшествующих значений, то она называетсярекуррентной булевой функцией (РБФ):Y = φ[x1(t), x2(t), ...

, xn(t),y(t-1),y(t-2), ... ,y(t-k)],где хi (t)- текущее значение i-й переменной; y(t-k)- значение функции в моментвремени t-k.Если, например, для функции y справедливо соотношение y(t+1)=x(t), то этоозначает, что значение выходного сигнала схемы в момент времени t+1 равензначению входного сигнала в момент времени t. Таким образом, схема выдаёт значениевхода с задержкой на один интервал времени. Если такое соотношение справедливодля всех моментов времени, на которых определена функция y, то соответствующая ейсхема называется элементом (схемой) задержки. Логический оператор,соответствующий элементу задержки, обозначается следующим образомx(t)x(t-1)DЛюбая РБФ может быть реализована с помощью набора логических операторов,представляющих обычные функции алгебры логики и операторов схем задержки.Пример.x(t)1f=(x(t) + x(t-1))x(t-1)D5.ИНФОРМАЦИОННЫЕ ПРОЦЕССЫПод информационными процессами понимаются любые действия, выполняемые синформацией. Существует три основных типа информационных процессов, которые43как составляющие присутствуют в любых других сложных информационныхпроцессах.Информационные процессыХранениеПередачаПамять(носитель)ВнутренняяИсточникВнешняяКаналОбработкаПриемникВиды обработкиХарактеристикиканалаХарактеристикипамятиЭто хранение, передача и обработка данных.5.1.