Теоретические основы вычислительной техники 4 страница

1. Перейти от МДНФ к МКНФ при помощи правила Де Моргана.

2. Использовать клетки КК содержащие нули.

Составление МКНФ заключается в объединении конъюнкциями дизъюнкций, соответствующих всем выделенным группам. В дизъюнкцию включаются все переменные, значения которых не изменяются в пределах группы. Причём, если переменная в пределах группы равна 0, то она входит в дизъюнкцию без инверсии, а если равна 1, то с инверсией.

Пример. Дана карта Карно для функции 4-х переменных. Получить МКНФ этой функции.

Задание 60. Получить МКНФ для функции F₄ заданной в таблице 4.

Задание 61. Получить МКНФ для функции F₃ заданной в таблице 4.

В. Минимизация неполностью определённых функций.

Неполностью определённые функции это такие функции, которые определены не на всех 2ⁿ наборах аргументов.

На карте Карно неопределённое условие обозначается прочерком (-). Клетки с прочерком могут произвольным образом включаться в группы, как при построении МДНФ, так и при построении МКНФ. Более того, их можно вообще никуда не включать (игнорировать).

Пример. Дана карта Карно для функции 4-х переменных. Получить МДНФ и МКНФ этой функции.

Задание 62. Получить МДНФ для функции F₅ заданной в таблице 4.

Задание 63. Получить МДНФ и МКНФ для функции F₆ заданной в таблице 4.

Минимизация методом Морреля.

В основе метода лежит теорема разложения.

Теорема разложения. Любую логическую функцию от n переменных можно свести к двум функциям от (n-1) переменных, проведя разложение вида

Сущность метода заключается в последовательном разложении функции по переменным и в анализе остаточных функций на равенство их нулю или единице.

Если остаточная функция равна нулю, то член, её включающий, равен нулю и исключается из разложения. Если остаточная функция равна единице, то переменная или конъюнкция переменных, связанных с ней, входит в тупиковую форму, а член из дальнейшего рассмотрения исключается. Все оставшиеся после анализа остаточные функции разлагаются по следующей переменной и снова анализируются и т. д. Минимизация заканчивается когда все остаточные функции будут равны 0 или 1.

Для получения формы, наиболее близкой к минимальной, Моррель предложил в формулу разложения добавить так называемый «терм Морреля», который добавляется всякий раз при разложении по любой переменной.

Формула разложения примет вид:

Покажем, что терм Морелля не изменит функцию:

.

При анализе остаточных функций на каждом этапе разложения проверяются условия поглощения термом Морреля других остаточных функций.

Минимизацию методом Морреля удобно проводить над функцией представленной в строчной форме (т. к. метод реализуем на ЭВМ). Разложение функции, представленной в строчной форме, по переменной х_i означает её разбиение на две части. В первую часть входят те наборы, на которых х_i=0, а во вторую – на которых х_i=1.

Пример. Пусть задана функция F(A,B,C,D) в строчной форме.

. Выполнить разложение функции по переменной А.

.

Теперь получим терм Морреля и добавим в разложение.

Следовательно,

Пример. Минимизировать методом Морреля функцию

.

Таким образом, получим F(A,B,C,D)=A+C.

Задание 64. Выполнить разложение функции F₁ (таблица 3) по переменной х₁.

Задание 65. Минимизировать функцию F₂ (таблица 3) методом Морелля.

Задание 66. Минимизировать функцию методом Морреля.

1.4. Синтез и анализ комбинационных схем.

Устройство, осуществляющее дискретное преобразование информации ЭВМ, называется автоматом. Существуют два основных вида дискретных автоматов: комбинационные автоматы (схемы) и конечные автоматы.

Введём: Х(t)={x₁, x₂, …, x_i, …, x_n} – множество входных дискретных сигналов; .

Y(t)={y₁, y₂, …, y_j, …, y_m} – множество выходных дискретных сигналов; .

Здесь t – дискретное время, определяется моментами перехода автомата из одного состояния в другое.

Определение. Если совокупность выходных сигналов (выходного слова) Y(t) зависит только от совокупности входных сигналов (входного слова) X(t) и не зависит от внутренних состояний автомата, то такой автомат называется комбинационным автоматом (комбинационной схемой).

Структурная схема комбинационного автомата:

Здесь Р – функция преобразования.

Закон функционирования комбинационной схемы определяется заданием соответствия между её входными и выходными словами Y(t)=P[X(t)] и может быть дан таблицей истинности, в аналитический форме и др.

1.4.1. Алгоритм синтеза комбинационной схемы.

1. Задать закон функционирования комбинационной схемы.

2. Провести минимизацию функции преобразования Р, получить Р_МДНФ и Р_МКНФ.

3. Преобразовать Р_МДНФ и Р_МКНФ в соответствии с заданным базисом логических функций (используемыми логическими элементами) и выбрать наиболее компактную форму представления Р.

4. Построить функциональную схему устройства.

5. Выполнить схемотехническую коррекцию схемы с учётом характеристик и параметров используемых логических элементов:

- коэффициента объединения (количество входов элемента),

- коэффициента разветвления (характеризует нагрузочную способность – максимально допустимое количество элементов подключаемых к входу),

- уровня логических 0 и 1,

- помехозащитности и др.

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

1.4.2. Функциональные схемы логических элементов.

Приведём лишь функциональные схемы, реализующие простейшие логические функции.

дизъюнкция («или»)

конъюнкция («и»)

инверсия («не»)

(здесь и в дальнейшем будет употребляться закрашенный кружок в обозначении инверсии вместо не закрашенного как принято)

стрелка Пирса («или-не»)

штрих Шеффера («и-не»)

Свести 3-х и 4-х входовые логические схемы к 2-х входовым можно следующим образом:

«3 и»

«3 или»

«4 и»

«4 или»

«3 и-не»

«3 или-не»

«4 и-не»

«4 или-не»

1.4.3. Пример синтеза полного одноразрядного двоичного сумматора.

Пример. Синтезировать схему полного одноразрядного двоичного сумматора используя двухвходовые логические элементы, реализующие логическую функцию «и-не».

Представим сумматор в виде:

a и b – одноразрядные двоичные слагаемые.,

с – перенос из младшего разряда,

S – сумма,

Р – перенос в старший разряд.

S=F₁(a,b,c), P=F­₂(a,b,c).

При синтезе реализуем последовательно этапы алгоритма.

1. Зададим закон функционирования сумматора в виде ТИ.

2. Проведём минимизацию функций S и Р методом Карно. По ТИ составим карты Карно:

Проверим предварительное построение схем сумматора непосредственно по выражениям S_МДНФ и Р_МДНФ без преобразования их к заданным двухвходовым элементам «и-не».

3. Преобразуем полученные выражения в соответствии с задуманными логическими элементами «и-не».

.

Для построения S_МДНФ и S_МКНФ на двухвходовых элементах «и-не» потребуется соответственно 20 и 21 логический элемент. Поэтому для построения части схемы, реализующей S, выберем S_МДНФ.

,

.

Для реализации P_МДНФ необходимо 6 двухвходовых элементов «и-не», а для Р_МКНФ – 7 (с учётом того, что уже получены в S_МДНФ).

Для построения части схемы, реализующей Р, выберем Р_МДНФ.

4. Построим функциональную схему сумматора используя выражения, выбранные на третьем шаге алгоритма.

; .

В данном случае построение частей схемы, реализующих S и Р проводилось независимо друг от друга.

5. На этапе схемотехнической коррекции ограничимся лишь оценкой выполнения требований по коэффициентам объединения К_о и разветвления К_р. К₀ был задан равным двум, а К_р для логических схем равен . Зададим К_р=5. Схема показывает, что для всех элементов К₀=2, а К_р<4 и, следовательно, требования по К_о и К_р удовлетворены.

6. Проведём тестирование схемы сумматора только на одном наборе аргументов. Пусть а=1, b=0, c=1. По ТИ этому набору соответствуют S=0 и Р=1. Расположим на всех входах и выходах элементов схемы соответствующие логические значения (0 или 1) и убедимся в правильности реализации функции S и Р на данном наборе аргументов (см. схему). Если выполнить аналогичные действия для всех наборов аргументов их ТИ, то тестирование будет полным.

Обратим внимание на то, что полученная схема, в соответствии с заданием, содержит только двухвходовые элементы «и-не».

Задание 67. Синтезировать комбинационную схему, закон функционирования которой задан функцией F₄ (таблица 4), используя логические элементы «и-не».

Задание 68. Синтезировать комбинационную схему полного одноразрядного сумматора на двухвходовых логических элементах «или-не» и протестировать её на наборе a=1, b=1, c=0.

Задание 69. Синтезировать комбинационную схему, реализующую функцию F₁, заданную в таблице 5. Использовать двухвходовые логические элементы «или-не». Провести тестирование схемы при х₁=0, х₂=1, х₃=1, х₄=0.

Задание 70. Синтезировать комбинационную схему, реализующую функции F₂ и F₅, заданные в таблицах 5 и 6. Использовать двухвходовые логические элементы «и-не». Провести тестирование схем при х₁=0, х₂=1, х₃=1, х₄=1.

Задание 71. Синтезировать комбинационную схему, реализующую функции F₃ и F₆, заданные в таблицах 5 и 6. Использовать логические элементы: «не» и «2и». Провести тестирование при х₁=х₃=х₅=0, х₂=х₄=1.

1.4.4. Односторонние булевы уравнения

Рассмотрим метод решения односторонних булевых уравнений с одним и двумя неизвестными. Уравнения с одним неизвестным:

.

Уравнения с двумя неизвестными:

,

где F₁(…) и F₂(…) – известные (заданные) функции, а Р(…), Q(…), R(…) – неизвестные функции.

Решение этих уравнений будем искать методом подбора значений P, Q, R на всех наборах F₁ и F₂. Таких наборов 4. Составим таблицу решений.

; .

Для получения решений в виде для уравнений с одним неизвестным и , для уравнения с двумя неизвестными, необходимо сначала перейти от формы представления исходных функций F₁ и F₂ к форме представления функций P, Q, R (для этого используется таблица решений), а затем выполнить минимизацию этих функций.

Пример. Решить булевы уравнения и при F₁ и F₂ заданных в строчной форме: , . Выполнить переход от F₁ и F₂ к P, Q, R. Используем таблицу решений односторонних булевых уравнений.

Перейдём от представления P, Q и R к строчной форме к представлению картами Карно и выполним минимизацию:

Проведя минимизацию Р, Q и R получим:

, , .

Задание 72. Решить односторонние булевы уравнения с одним и двумя неизвестными, если известные функции F₄ и F₅ заданы ТИ (таблица 6).

Задание 73. Решить односторонние булевы уравнения с одним и двумя неизвестными, если известные функции F₁ и F₂ заданы ТИ (таблица 5).

1.4.5. Методы синтеза комбинационных схем с многими выходами.

Послу раздельной минимизации булевых функций, описывающих многовыходную схему, применяются различные методы совместной обработки функций.

Рассмотрим два из них:

- метод учёта повторяющихся членов,

- метод последовательного наращивания.

Метод учёта повторяющихся членов.

В данном методе находятся общие для формул нескольких функций члены(функции, отдельные дизъюнкции, конъюнкции и их части). При построении общей комбинационной схемы, реализующей несколько логических функций, фрагменты, соответствующие общим (повторяющимся) членам, формируются только один раз и используются для получения любой функции, куда они входят.

Пример. Синтезировать комбинационную схему, реализующую функции:

, , .

Общими членами в этих выражениях являются: .

Задание 74. Синтезировать комбинационную схему, реализующую функции:

Метод последовательного наращивания.

Логическая схема строится сначала для какого-либо одного выхода, затем для другого, третьего и т. д.

При построении схемы последующего выхода, выходные сигналы уже построенной схемы используются на ряду с общими выходными сигналами схемы. Следовательно, функция этого выхода может быть представлена в виде функции от (n+1) переменной (n – входных сигналов плюс выход предыдущей схемы).

Реализуя данный метод нужно получить специальный блок, преобразующий функцию F_i-1 в функцию F_i. Для этого проведём разложение F_i по новой перемноженной F_i’: .

Таким образом, получаем обычное булево уравнение с двумя неизвестными . Следовательно, при построении многовыходной схемы методом последовательного наращивания необходимо найти решение (n-1) булева уравнения и определить все Q­_i и R_i.

Рекомендации. За исходную функцию F₁ можно брать любую из заданных, но, как правило, лучшие результаты получаются, если взять ту, у которой проще минимальная форма.

Если одна из исходных функций не доопределена, а вторая определена полностью, то неопределённые значения группируются так, чтобы это было наиболее выгодно при минимализации Q_i и R_i.

Структурная схема, реализующая функцию F’_i может быть представлена следующим образом:

.

Пример. Синтезировать комбинационную схему полного одноразрядного двоичного сумматора методом последовательного наращивания. , . В качестве F₁ выбираем Р, как функцию с простой минимальной формой. .