Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Разработка алгоритма программы минимизации логических функций (программа с исходниками прилагается) - файл Курсовая (минимизация ФАЛ).docx


Разработка алгоритма программы минимизации логических функций (программа с исходниками прилагается)
скачать (1010.8 kb.)

Доступные файлы (8):

MininizationFAL.exe
MininizationFAL.cbproj
MininizationFAL.cpp
MininizationFAL.res
Unit1.cpp
Unit1.dfm
Unit1.h
Курсовая (минимизация ФАЛ).docx644kb.21.03.2011 17:58скачать

содержание
Загрузка...

Курсовая (минимизация ФАЛ).docx

Реклама MarketGid:
Загрузка...

Министерство образования и науки РФ

Московский Государственный Открытый Университет

Факультет информатики и радиоэлектроники

Кафедра вычислительной техники и программирования

Курсовая работа

по дисциплине: «Организация ЭВМ и систем»

Тема: «Разработка алгоритма программы минимизации логических функций»

Выполнил:

студент 2 курса

спец. 230105

**************

шифр *******

Проверил:

Путилин А.Б.

Москва 20?? г.

Оглавление

 4

1. Минимизация функций алгебры логики 5

1.1 Метод непосредственных преобразований логических функций. 5

 7

1.2 Метод Квайна. 8

1.3 Метод диаграмм Вейча. 11

1.4 Метод Куайна – Мак-Класки. 13

2. Разработка алгоритма программы. 16

2.1 Постановка задачи. 16

2.2 Выбор метода. 16

2.3 Выбор языка программирования. 16

2.4 Описание программы. 16

2.5 Интерфейс программы. 21

 22

2.6 Блок-схема алгоритма. 23

 28

2.7 Листинг. 29

 30

Список литературы 31



^






1. Минимизация функций алгебры логики


Совершенно нормальные формы хотя и дают однозначные представления функции, но являются очень громоздкими. Реализация СНФ программно или схемотехнически является избыточной, что ведет к увеличению программного кода, поэтому существуют методы упрощения логической записи – минимизации.

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

Существуют два направления минимизации:

1. Кратчайшая форма записи (цель – минимизировать ранг каждого терма). При этом получаются кратчайшие формы КДНФ, ККНФ, КПНФ.

2. Получение минимальной формы записи (цель – получение минимального числа символов для записи всей функции сразу).

При этом следует учесть, что ни один из способов минимизации не является универсальным.
^

1.1 Метод непосредственных преобразований логических функций.


При применении данного метода:

а) Записываются ДСНФ логических функций

б) Форма преобразуется и упрощается с использованием аксиом алгебры логики. При этом, в частности, выявляются в исходном ДСНФ так называемые соседние min-термы, в которых есть по одной не совпадающей переменной.
По отношению к соседним min-термам применяется закон склейки, значит ранг min-терма понижается на единицу.

Определение: Min-термы, образованные при склеивании называются импликантами.

Полученные после склейки импликанты по возможности склеивают до тех пор, пока склеивание становится невозможным.



Определение: Не склеивающиеся импликанты называются прослойками.

Определение: Формула, состоящая из простых импликант – тупиковая.

Пример:
















0

0

0

1

0

0

1

1

0

1

0

1

0

1

1

1

1

0

0

0

1

0

1

0

1

1

0

0

1

1

1

0


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

Пример:
Мы получили минимальную СНФ.
^



1.2 Метод Квайна.


Преобразование функции можно разделить на два этапа:

  • на первом этапе осуществляется переход от канонической формы (СДНФ или СКНФ) к так называемой сокращённой форме;

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


Для осуществления первого этапа преобразование проходит два действия:

  1. Операция склеивания;




  1. ^ Операция поглощения.

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




   0   

   0   

   0   

   0   

   0   

   0   

   0   

   0   

   1   

   1   

   1   

   1   

   1   

   1   

   1   

   1   




0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1




0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1




0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1




1

1

1

0

0

0

1

0

0

0

0

0

0

0

1

1


СДНФ, собранная по этой таблице выглядит следующим образом:

        

Конечное выражение достигается за счёт повторного использования операций склеивания и поглощения:



        

Члены этого выражения являются простыми импликантами выражения. Переход от сокращённой формы к минимальной осуществляется с помощью импликантной матрицы.
Члены СДНФ заданной функции вписываются в столбцы, а в строки — простые импликанты, то есть члены сокращённой формы. Отмечаются столбцы членов СДНФ, которые поглощаются отдельными простыми импликантами. В следующей таблице простая импликанта  поглощает члены  и  (в первом и во втором столбцах поставлены крестики).

^ Импликантная матрица

  ^ Простая импликанта












































































































Вторая импликанта поглощает первый и третий члены СДНФ (указано крестиками) и т. д. Импликанты, не подлежащие исключению, образуют ядро. Такие импликанты определяются по вышеуказанной матрице. 

Для каждой из них имеется хотя бы один столбец, перекрываемый только этой импликантой.

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

Для получения минимальной формы достаточно выбрать из импликантов, не входящих в ядро, такое минимальное их число с минимальным количеством букв в каждом из этих импликант, которое обеспечит перекрытие всех столбцов, не перекрытых членами ядра. В рассматриваемом примере необходимо импликантами, не входящими в ядро, перекрыть третий и четвёртый столбцы матрицы. Это может быть достигнуто различными способами, но так как необходимо выбирать минимальное число импликант, то, очевидно, для перекрытия этих столбцов следует выбрать имликанту .
^ Минимальная дизъюнктивная нормальная форма (МДНФ) заданной функции:

(а)


Рис 1. Структурная схема, соответствующая этому выражению.
Переход от сокращённой схемы к МДНФ был осуществлён путём исключения лишних членов — импликант  и . Покажем допустимость подобного исключения членов из логического выражения.
Импликанты    и    становятся равными лог. 1 соответственно при следующих наборах значений аргументов:

 =0, =0, =0 и  =1,  =1, =0.

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

   ;

при  = 1,  = 1,  = 0

;
^

1.3 Метод диаграмм Вейча.


Метод позволяет быстро получать минимальные ДНФ булевой функции f небольшого числа переменных. В основе метода лежит задание булевых функций диаграммами некоторого специального вида, получившими название диаграмм Вейча. Для булевой функции двух переменных диаграмма Вейча имеет вид :
Каждая клетка диаграммы соответствует набору переменных булевой функции в ее таблице истинности. В (табл. 4.4.1) это соответствие показано, В клетке диаграммы Вейча ставится единица, если булева функция 

принимает единичное значение на соответствующем наборе. Нулевые значения булевой функции в диаграмме Вейча не ставятся. Для булевой функции трех переменных диаграмма Вейча имеет следующий вид:
Добавление к ней еще такой же таблицы дает диаграмму для функции 4-х переменных :
Таким же образом, т. е. приписыванием еще одной диаграммы 3-х переменных к только что рассмотренной, можно получить диаграмму для функции 5-ти переменных и т. д., однако диаграммы для функций с числом переменных больше 4-х используются редко. Для приведенных диаграмм характерно следующее:

  • каждой клетке диаграммы соответствует свой набор;

  • соседние наборы расположены рядом в строке либо в столбце.

Соседними наборами называются наборы, отличающиеся одной компонентой. Напомним, что конституенты, соответствующие таким наборам, склеиваются (см. метод Квайна- Мак-Класки). Например, для функции, заданной таблицей
конституенты, соответствующие паре единиц в левой части таблицы, склеиваются и порождают элементарное произведение из 2-х букв:

х1х23 v x1x23 = x1x2


О паре единиц в правой части диаграммы можно сказать то же самое:



1х23 v /x1/x2/x 3 = /x1/x3


Отметим, что получающееся элементарное произведение легко определить сразу по диаграмме: это произведение переменных, принимающих одно и то же значение в обеих клетках.

Еще одно важное замечание: столбцы, расположенные по краям диаграммы, тоже считаются соседними. Для нашего примера это означает, что имеет место еще одно склеивание, в результате которого, следуя указанному правилу, получаем элементарное произведение x2/x3 Из рассмотренных ранее методов нам известно, что возможно дальнейшее склеивание получаемых элементарных произведений. На диаграммах Вейча они тоже располагаются рядом. Общее правило склеивания на диаграммах Вейча можно сформулировать следующим образом: склеиванию подлежат прямоугольные конфигурации, заполненные единицами и содержащие число клеток, являющееся степенью 2. Получающееся новое элементарное произведение определяется как произведение переменных, не меняющих своего значения на всех склеиваемых наборах. Число m оставшихся переменных в элементарном произведении определяется легко:

m = n - log2M

где n - число переменных функции, М - число склеиваемых наборов. Метод широко используется на практике, благодаря простоте и удобству. Минимизация булевой функции заключается в нахождении минимального накрытия всех единиц диаграммы Вейча блоками из единиц (указанной конфигурации), расположенных в соседних клетках диаграммы. При этом всегда считается, что левый край диаграммы Bейча 4-х переменных примыкает к ее правому краю, а верхний oкрай диаграммы примыкает к нижнему ее краю. После получения минимального накрытия всех единиц диаграммы Вейча, минимальная ДНФ булевой функции записывается как дизъюнкция элементарных конъюнкций, соответствующих выделенным блокам единиц в диаграмме.




Пример. Булева функция f имеет следующую СДНФ:

f=х1х2х3 v х12х3 v /х123 v /х123 v х1х23.


Найти минимальную ДНФ с помощью диаграммы Вейча. Минимальное накрытие всех единиц диаграммы возможно только блоками по две единицы. Каждому такому блоку соответствует своя конъюнкция.
Следовательно, минимальная ДНФ функции имеет вид:

f = х1х2 v /х12 v х1х3.

^

1.4 Метод Куайна – Мак-Класки.


Метод Куайна - Мак-Класки является модификацией метода Куайна. Недостатком метода Куайна является необходимость полного попарного сравнения всех минтермов на этапе нахождения первичных импликант. С ростом количества минтермов резко увеличивается число необходимых сравнений. При использовании метода Куайна - Мак-Класки минтермы представляются в виде двоичных номеров а затем группируются по количеству единиц. Имеет смысл сравнивать только группы отличающиеся на одну единицу.
Пример:

Минимизируем функцию четырёх переменных F (a, b, c, d), заданную таблицей истинности.

1. Сгруппируем минтермы по количеству единиц в них:



2. Произведём первое объединение строк каждых предыдущих и последующих групп:


3. Объединим строки с совпадающими позициями
"крестиков":
4. Из двух строк с одинаковыми значениями переменных оставляем только одну (любую):

5. Обратим внимание на то, что первый минтерм избыточен, так как 0-я и 4-я строки уже вошли в комбинацию со 2-ой и 6-ой (второй минтерм), а 1-я и 5-я - с 

9-ой и 13-ой соответственно (третий минтерм). Пятый минтерм также избыточен, так как 4-я; 5-я; 12-я и 13-я строки уже сгруппированы с 6-ой и 0-ой (четвёртый и второй минтермы); с 13-ой (третий минтерм); с 14-ой (четвёртый минтерм) и с 5-ой (третий минтерм) соответственно. Поэтому удаляем первую и пятую строки из таблицы и записываем минимальную

Окончательно: F(a, b, c, d)= a'd'+ c'd+ bd'.
^

2. Разработка алгоритма программы.

2.1 Постановка задачи.


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

2.2 Выбор метода.


Наиболее подходящим методом минимизации для программной интерпретации является метод Куайна – Мак-Класки. К основным достоинствам которого можно отнести сравнительно небольшое количество операций сравнения, а так же то, что все представлено в виде чисел, с которыми легко оперировать.
^

2.3 Выбор языка программирования.


В качестве языка программирования я выбрал С++ поскольку это универсальный высокоуровневый объектно-ориентированный язык программирования пригодный для задач любой сложности.
^

2.4 Описание программы.


Программа реализована на основе классов со своими методами. Основной класс это fal (функция алгебры логики):

Class fal{

public:



minterm *mdnf; //массив элементов типа minterm

int size,param; //размер массива и число переменных в функции

class Table;

class Row;

fal(); // конструктор по умолчанию

fal(const AnsiString s,int param_); // конструктор от строки коэффициентов и числа параметров

fal(const Table &t,int param_);

~fal(); // деструктор

AnsiString print(); // метод для вывода функции на экран;

int count(); // возвращает количество минтермов в функци

};
В классе fal используется класс minterm который представляет минтерем:
class minterm {

public:

int a[4]; // массив из 4-х элементов в котором каждый элемент это переменная (1-переменная, 0-переменная с отрицанием,-1 – отсутствие переменной)

int size; // количество переменных
minterm();// конструктор по умолчанию

minterm(int A,int B,int C,int D); //конструктор от четырех переменных

void fill(int A,int B,int C,int D); // изменение минтерма

bool operator == (const minterm &m); // перегрузка оператора равно

bool operator != (const minterm &m); // перегрузка оператора не равно

bool not_void(); // проверка на существование (не пустой ли он)

bool include(const minterm &m); // не включает ли минтерм m

int count_1();// подсчет единиц

bool positions_coincide(const minterm &m); // совпадают ли позиции -1?



bool can_be_united(const minterm &m); // могут ли быть склеены?

void glue(const minterm &m); // склеиваание

AnsiString print();// вывод

};
Таблица используемая в методе Куайна – Мак-Класки реализована классами Table (таблица) и Row (строка), находящимся в области видимости класса fal:

class Row

{

public:

int index; // уникальный индекс строки

int index_arr[8]; // массив индексов строк в таблице СДНФ которые включают эту строку;

minterm m; // минтерм

int n; // количество единиц в минтерме

bool united; // участвовали в склейке или нет

Row();// конструктор

Row(int index_,minterm m_); // конструктор от индекса и минтерма

Row(const Row &r); // конструктор копирования
Row *Unite(Row &r); // функция объединения строк

void print();// вывод

bool find_in_index_arr(int n); // поиск вхождения индекса в index_arr[]

};

class Table

{

public:

Row **row; // указатель на массив указателей на Row



int size,real_size; // количество заполненных строк и реальный размер таблицы(аллоцированный в памяти)
Table(int size) // конструктор таблицы заданного размера

Table(const fal &sdnf); // создание таблицы по fal

~Table();// деструктор

void print();//вывод

Table &operator = (const Table &t); // перегрузка оператора присвоения

bool shorten(); // функция сокращающая СДНФ и приводящая его к виду КДНФ, возвращает 1 если были произведены изменения иначе 0

void remove_eq_rows(); // удаляет одинаковые строки в таблице

bool find(int n, int r);

bool find_in_core(int n, int r);

Row *find_and_add_in_core(int n, int r);

void minimize(); // окончательно минимизирует функцию и приводит КДНФ к виду МДНФ

};

Рассмотрим основные функции относящиеся непосредственно к алгоритму минимизации:

Во-первых это shorten() приводящий функцию к КДНФ

bool shorten()

{

bool changes=false;

Table *new_table;

int new_size=0;

new_table=new Table(3*size); // создание новой таблицы

for (int i=0; i < size; i++) {

for (int j = 0; j < size; j++) {

if((row[i]->index!=row[j]->index &&

row[i]->n==(row[j]->n+1) &&

row[i]->m.can_be_united(row[j]->m) &&

row[i]->m.positions_coincide(row[j]->m)))



//если индексы строк не равны и число единиц в минтермах отличается на 1 и позиции “крестиков” совпадают

{

new_table->row[new_size]=

row[i]->Unite(*row[j]);

//объединить i-тую строку c j-той

new_table->row[new_size]->index=new_size;

new_size=new_size+1;

//инкрементирование new_size

changes=true;

}

}

}

for (int i=0; i < size; i++)

{

if(!(row[i]->united))

{

new_table->row[new_size]=row[i];

new_table->row[new_size]->index=new_size;

++new_size;

}

} //добавление в таблице строк не участвовавших в склеивании

*this=*new_table;

size=new_size;

return changes;

}
Во-вторых это minimize() приводящий функцию к МДНФ

void minimize()

{

Table *new_table;

Row *new_row=0;

int new_size=0;

new_table=new Table(size);

for (int i=0; i < size; i++)

for (int n=0; n < 8; n++)

if(!this->find(row[i]->index_arr[n],i)){

row[i]->united=1;

new_table->row[new_size]=new Row(*row[i]);

++new_size;

break;

}

for (int i=0; i < size; i++)

for (int n=0; n < 8; n++)

if(row[i]->united!=1 && row[i]->index_arr[n]!=0)



if(!this->find_in_core(row[i]->index_arr[n],i))

{

new_row=this->find_and_add_in_core(row[i]->index_arr[n],i);

if(new_row)

{

new_table->row[new_size]=new_row;

++new_size;

}

}

*this=*new_table;

size=new_size

}
^

2.5 Интерфейс программы.






2.6 Блок-схема алгоритма.


Общая схема:



Функция shorten() :


Функция remove_eq_rows() :



Функция minimize() :

^



2.7 Листинг.





Список литературы


    1. А.Я. Совельев “Арифметические и Логические основы цифровых автоматов” учебник. – М.: Высшая школа, 1980.

    2. А.Я. Архангельский программирование в С++ builder 6

Москва, издательство «БИНОМ» , 2003.

Сайты:

  1. http://www.kaf403.rloc.ru/ сайт кафедры «Электронно-вычислительные средства и информатика» Московского авиационного иститута

  2. http://ru.wikipedia.org

  3. http://www.codenet.ru

CodeNet / Языки программирования / C / C++ / Borland C++ Builder / Справочники и учебники




Скачать файл (1010.8 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации