СКАЧАТЬ:  zadanie-6-mnk-kombinacionnye-shemy.zip [137,94 Kb] (cкачиваний: 59)

ОТЧЁТ

по лабораторной работе №1

по дисциплине: «Устройства цифровой автоматики»

на тему: «Минимизация логической функции

методом неопределённых коэффициентов»

МИНИМИЗАЦИЯ ЛОГИЧЕСКОЙ ФУНКЦИИ

МЕТОДОМ НЕОПРЕДЕЛЁННЫХ КОЭФФИЦИЕНТОВ

Цель работы: изучение метода неопределённых коэффициентов; синтез логической схемы по заданной логической функции.

Сведения из теории:

На основании теоремы Жегалкина любую логическую функцию единственным образом можно представить в виде полинома Жегалкина:

                                      (1)

где  – неопределённые коэффициенты, принимающие значения 0 или 1.

Теорема доказывается следующим образом. Заметим, что различных булевых функций от n переменных  штук. При этом конъюнкций вида существует ровно 2n, так как из n возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует  различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.

Запишем полином Жегалкина для функции трёх переменных. Например, для функции :

Заменяя сложение по модулю два дизъюнкцией, преобразуем его в нормальную форму:

               (2)

         Следовательно, для состояния  можем записать:

         Делая аналогичные выводы для всех состояний A, B, C можем записать систему уравнений:

                    (3)

         Очевидно, что в любом уравнении системы (3), где функция равна нулю, все коэффициенты, входящие в это уравнение, также равны нулю.

         На этом основании можно сделать вывод, что можно упростить функцию, определив нулевые коэффициенты в выражении (2) и записав его, опустив слагаемые с этими нулевыми коэффициентами. Окончательно минимизировать функцию можно, оставив в уравнениях системы (3), в которых функция равна единице, только коэффициенты с минимальным рангом, а остальные приравнять к нулю, так как на результат суммы, и, следовательно, на значение исходной функции это не повлияет.

         На основании вышеизложенных соображений можно сформулировать следующий алгоритм минимизации логической функции:

1. Записать систему уравнений (3), подставляя значения исходной функции в правую часть уравнений;
2. Вычеркнуть все коэффициенты в уравнениях, где исходная функция равна нулю;
3. Просмотреть уравнения, в которых исходная функция равна единице, и вычеркнуть в них все коэффициенты, встречающиеся в уравнениях, где функция равна нулю;
4. Переписать все уравнения, где остались невычеркнутые коэффициенты;
5. В этих уравнениях вычеркнуть максимально возможное количество коэффициентов так, чтобы ранг остающихся коэффициентов в каждом уравнении был минимальным;
6. Записать выражение (2) подставив полученные значения коэффициентов.

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

Также отметим, что критерием минимальности в данном методе является минимальное количество аргументов в записи НДФ.

Задание: Найти минимальную форму для логической функции

с помощью метода неопределённых коэффициентов.

1)                Запишем исходную функцию в форме СДНФ:

2)                Минимизируем данную логическую функцию методом неопределённых коэффициентов. Перепишем систему уравнений (3) для заданной функции и вычеркнем все нулевые коэффициенты:

После вычёркивания коэффициентов можем записать:

Оставляя в уравнениях только коэффициенты с минимальным рангом, получим:

Запишем окончательный результат:

Сделаем проверку. Приведём минимизированную функцию в форму СДНФ:

         Функция минимизирована правильно.

3)                Минимизируем исходную функцию непосредственно:

         Таким образом, в результате использования метода неопределённых коэффициентов получили не самую простую форму для синтеза логической схемы форму, так как критерием минимальности в этом методе является не минимальное количество операций в минимизированном выражении, а минимальное количество аргументов в записи НДФ.

4)                Запускаем программу EWB. Открыв логический преобразователь, вводим в него таблицу истинности заданной функции:

Преобразуем таблицу истинности в логическое выражение:

Минимизируем функцию:

Реализуем логическое выражение в виде логической схемы, добавляем в него генератор слов и логический анализатор и создаем соответствующие связи:

В генераторе слов задаем следующую последовательность:

Запускаем схему на выполнение и исследуем его с помощью логического анализатора:

         Выводы: в ходе этой лабораторной работы мы изучили метод неопределённых коэффициентов и минимизировали с его помощью логическую функцию, а также убедились, что данный метод не всегда приводит к самому простому для синтеза логической схемы выражению. Затем, исследуя данную логическую функцию на программе EWB, мы убедились в правильности выполненной минимизации, реализовали на этой программе исходную логическую функцию в виде логической схемы и исследовали его работу.