Xreferat.com » Рефераты по математике » Методы минимизации логических функций

Методы минимизации логических функций

функций" width="44" height="2" align="LEFT" /> __

Методы минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функций X X X1VX2 X1*X2


Методы минимизации логических функций X2 X2

Методы минимизации логических функций

Для аппаратной реализации минимальной ДНФ нам потребуется 3 ИМС серии К155 : одна ИМС К155ЛН1 (элементы НЕ), одна ИМС К155ЛЛ1 (элементы ИЛИ) и одна ИМС К155ЛИ1 (элементы И). Но в них все элементы не используются. Так в ИМС К155ЛН1 не используются 3 элемента НЕ Это можно использовать в том случае, когда один из элементов выйдет из строя и его нечем будет заменить. Надо будет только перепаять контакты на незадействованный элемент. Всего в базисе Буля используются 11 логических элементов.

2. Представление МДНФ в базисе Шеффера. Для того, чтобы реализовать минимальную ДНФ в базисе Шеффера, необходимо перевести базис Буля в базис Шеффера, в котором используется только один логический элемент: И-НЕ.

Формулы перевода из базиса Буля в базис Шеффера записываются следующим образом:

Методы минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функций

НЕ: X = X*X ИЛИ: X1VX2 = X1*X1 * X2*X2

Методы минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функций

И: X1*X2 = X1*X2 * X1*X2


Минимальная ДНФ выглядит так:


Методы минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийf(X1, X2, X3, X4) = X3X4VX2X3VX1X3VX1X2X4VX1X2X4;


Переведем ее в базис Шеффера с помощью указанных выше формул.

Методы минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функций

Методы минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийОбозначим A = X3X4VX2X3VX1X3 = X3·( X4VX2VX1) = X3·X4·X4·X2·X1=

Методы минимизации логических функцийМетоды минимизации логических функций

Методы минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функций= X3·X4·X4·X2·X1·X2·X1.

Методы минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функций

Методы минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийB = X1X2X4VX1X2X4= X1·(X2·X4VX2·X4) = X1·X1·X2·X2·X4·X4·X2·X4.

Методы минимизации логических функций

Методы минимизации логических функцийМетоды минимизации логических функцийОкончательно получим Y = A · B .


Отсюда видно, что для реализации минимальной ДНФ в базисе Шеффера требуется 12 элементов И-НЕ. Соответственно для аппаратной реализации нам потребуется 3 интегральные микросхемы К155ЛА3.

3. Представление МДНФ в базисе Пирса. Для того, чтобы реализовать минимальную ДНФ в базисе Пирса, необходимо как и в предыдущем пункте перевести МДНФ из базиса Буля в базис Пирса, в котором используется только один элемент ИЛИ-НЕ.

Формулы перевода записываются следующим образом:

Методы минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функций

НЕ: X = XVX ИЛИ: X1VX2 = X1VX2 V X1VX2

Методы минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функций

И: X1*X2 = X1VX1 V X2VX2


Переведем МДНФ в базис Пирса. Введем обозначения:

Методы минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функций

Методы минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийA = X3X4VX2X3VX1X3 = X3·X4·X2·X3·X1·X3 = X3VX4VX2VX3VX1VX3.

Методы минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функций

Методы минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийB = X1·(X2X4VX2X4) = X1·(X2·X4·X2·X4) = X1·X2VX4VX2VX4 =

Методы минимизации логических функцийМетоды минимизации логических функций

Методы минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функцийМетоды минимизации логических функций= X1VX2VX4VX2VX4.

Y = A V B.


Чтобы реализовать каждую отдельную логическую сумму нам потребуется 2 элемента ИЛИ-НЕ, т.е. для 4-х логических сумм, которые составляют функцию, нам потребуется 6 логических элементов.

Всего на реализацию МДНФ в базисе Пирса понадобится 16 логических элементов ИЛИ-НЕ, а для аппаратной реализации 4 ИМС серии К155 (К155ЛЕ1).

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


Заключение


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

Иначе выглядит метод неопределенных коэффициентов. Для машинной реализации он подходит больше других, так как в нем мы имеем дело с массивами, для работы с которыми не надо особо сложной логики. И конечно ручное исполнение этого метода крайне нерационально, так как приходиться решать систему из 16-ти уравнений. Это для четырех переменных, а для пяти это будет 32 уравнения. Такой метод для ручного исполнения не подходит.

В задаче курсовой работы также входил синтез логической схемы. Полученная схема МДНФ была реализована в трех базисах: Буля, Пирса, Шеффера. Анализ и оценка аппаратурных затрат также приведена в данной записке.


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


Гаджиев А.А. Методические указания к выполнению курсовой работы по дисциплине “Дискретная математика” для студентов специальности 22.01 (ВМКСиС). Махачкала, 1998 г.

Гаджиев А.А. Методические указания к выполнению лабораторного практикума по дисциплине “Дискретная математика” (часть 2. Математическая логика). Махачкала, 1998 г.


Приложение


Программа для метода Квайна


Uses Crt;

Const

R = 4;

SR = 16;

Type

Diz = string[R];

Var

S :array[1..SR*2] of Diz;

Rez :array[1..SR*2] of Diz;

Flag :array[1..SR*2] of byte;

Y :array[1..SR] of byte;

IndexS : byte;

IndexRez : byte;

i, j, k : byte;

FData : Text;

FRez : Text;

FDSNF : file of Diz;

FSImp : file of Diz;


{Функция формирования дизъюнкта}

Function MakeDiz(Number: byte): Diz;

Var

i : byte;

S : Diz;

C : char;

Begin

S:='';

for i:=0 to R-1 do

begin

C:=chr(((Number shr i) and $01) + 48);

Insert(C, S, 1);

end;

MakeDiz:=S;

End;


{Функция склеивания}

Procedure Stuck(S1, S2: Diz; IndexS1, IndexS2 : byte);

Var

i, k, n: byte;

Begin

k:=0; {кол-во разных}

for i:=1 to R do

if S1[i] <> S2[i] then

begin

k:=k+1;

n:=i;

end;

case k of

0 : begin

Inc(IndexRez);

Rez[IndexRez]:=S1;

Flag[IndexS1]:=1;

Flag[IndexS2]:=1;

end;

1 : if (S1[n]<>'*') and (S2[n]<>'*') then

begin

S1[n]:='*';

Inc(IndexRez);

Rez[IndexRez]:=S1;

Flag[IndexS1]:=1;

Flag[IndexS2]:=1;

end;

end;

End;


{Функция проверки на удаление пустого дизъюнкта}

Function Del(S : Diz): Boolean;

Var

i, k : byte;

Begin

Del:=False;

k:=0;

for i:=1 to R do

if S[i]='*' then

k:=k+1;

if k=R then

Del:=True;

End;


Procedure Clear;

Var

i, j : byte;

Begin

IndexS:=0;

for i:=1 to SR*2 do

begin

Flag[i]:=0;

S[i]:='';

end;

for i:=1 to IndexRez-1 do

if Flag[i]=0 then

for j:=i+1 to IndexRez do

if Rez[i]=Rez[j] then

Flag[j]:=1;

for i:=1 to IndexRez do

if Flag[i]=0 then

begin

Inc(IndexS);

S[IndexS]:=Rez[i];

end;

End;


{Вывод на экран массива Rez}

Procedure PrintRezult(Step: Byte);

Var

i : byte;

Begin

WriteLn('{------------------------------------------------}');

WriteLn(FRez, '{-----------------------------------------}');

if Step=0 then

begin

Write('Исходная ДНФ.');

Write(FRez, 'Исходная ДНФ.');

end

else

begin

Write('Шаг номер :', Step:2, '.');

Write(FRez, 'Шаг номер :', Step:2, '.');

end;

WriteLn(' Количество дизъюнктов :', IndexS:2);

WriteLn(FRez, ' Количество дизъюнктов :', IndexS:2);

for i:=1 to IndexS do

begin

WriteLn(S[i]);

WriteLn(FRez, S[i]);

end;

ReadKey;

End;


{Основная программа}

Begin

ClrScr;

Assign(FDSNF, 'dsnf.dat');

Rewrite(FDSNF);

Assign(FSImp, 'simplimp.dat');

Rewrite(FSImp);

Assign(FRez, 'rezult.dat');

ReWrite(FRez);

{Считать массив Y из файла}

Assign(FData, 'func.dat');

Reset(FData);

for i:=1 to SR do

Read(FData, Y[i]);

Close(FData);

{Получить массив S}

for i:=1 to SR do

S[i]:=MakeDiz(i-1);

{Преоразовать S: оставив только те элементы, для которых Y=1. Результата в Rez}

IndexRez:=0;

for i:=1 to SR do

if Y[i]=1 then

begin

Inc(IndexRez);

Rez[IndexRez]:=S[i];

end;

for i:=1 to SR*2 do

S[i]:=Rez[i];

IndexS:=IndexRez;

for i:=1 to IndexS do

Write(FDSNF, S[i]);

PrintRezult(0);

{склеивание}

for i:=1 to R do

begin

IndexRez:=0;

{------------------------------------------------------------}

for j:=1 to SR*2 do {подготовка массива Flag под склеивание}

Flag[j]:=0;

{------------------------------------------------------------}

for j:=1 to SR*2 do {склеивание}

Rez[j]:='';

for j:=1 to IndexS-1 do

for k:=j+1 to IndexS do

Stuck(S[j], S[k], j, k);

{------------------------------------------------------------}

for j:=1 to IndexS do {копирование несклеившихся компонент}

if Flag[j]=0 then

begin

Inc(IndexRez);

Rez[IndexRez]:=S[j];

end;

{------------------------------------------------------------}

Clear; {удаление одинаковых дизъюнктов}

{------------------------------------------------------------}

PrintRezult(i); {вывод результата на экран}

end;

{Удалить все дизъюнкты вида '****'}

IndexRez:=0;

for i:=1 to IndexS do

if not Del(S[i]) then

begin

Inc(IndexRez);

Rez[IndexRez]:=S[i];

end;

for i:=1 to IndexS do

Write(FSImp, S[i]);

PrintRezult(R+1);

Close(FSImp);

Close(FDSNF);

Close(FRez);

End.


Результаты работы программы (файл rezult.dat).

{----------------------------------------------------------------}

Исходная ДНФ. Количество дизъюнктов : 9

0000

0010

0011

0101

0110

0111

1010

1011

1111

{----------------------------------------------------------------}

Шаг номер : 1. Количество дизъюнктов :11

00*0

001*

0*10

*010

0*11

*011

01*1

011*

*111

101*

1*11

{----------------------------------------------------------------}

Шаг номер : 2. Количество дизъюнктов : 5

0*1*

*01*

**11

00*0

01*1

{----------------------------------------------------------------}

Шаг номер : 3. Количество дизъюнктов : 5

0*1*

*01*

**11

00*0

01*1

{----------------------------------------------------------------}

Шаг номер : 4. Количество дизъюнктов : 5

0*1*

*01*

**11

00*0

01*1

{----------------------------------------------------------------}

Шаг номер : 5. Количество дизъюнктов : 5

0*1*

*01*

**11

00*0

01*1


Программа для метода Петрика.

Uses Crt;

Type

string4 = String[4];

string16 = String[16];

TImpArray = array[1..16] of string4;


Var

DSNF : TImpArray; {ДСНФ}

SimpleImp : TImpArray; {Простые импликанты}

IndexDSNF : Integer;

IndexSImp : Integer;

QM : array[1..16, 1..16] of integer; {матрица покрытия}

S16Min : string16;


Procedure Input;

Var

FData : file of string4;

i : integer;

Begin

{ввод матрицы ДСНФ}

Assign(FData, 'dsnf.dat');

Reset(FData);

i:=0;

while not eof(FData) do

begin

Inc(i);

Read(FData, DSNF[i]);

end;

IndexDSNF:=i;

Close(FData);

{ввод простых импликант}

Assign(FData, 'simplimp.dat');

Reset(FData);

i:=0;

while not eof(FData) do

begin

Inc(i);

Read(FData, SimpleImp[i]);

end;

IndexSImp:=i;

Close(FData);

{конец ввода}

End;


Function Metka(n, m: integer): boolean;

Var

i, S : integer;

Begin

Metka:=False;

S:=0;

for i:=1 to 4 do

if SimpleImp[n, i]='*' then

S:=S+1

else

if SimpleImp[n, i]=DSNF[m, i] then

S:=S+1;

if S=4 then

Metka:=True;

End;


Procedure FormMatrix;

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: