Исследование методов анализа и синтеза логических схем

 

Рисунок 8 – Неполный дешифратор 

Составляем систему  функций для неполного дешифратора: 
 
 
 
 
 
 
 

 

Рисунок 9 – Логическая схема неполного дешифратора 

2 Метод факторизации 

2.1 Теоретическая  часть 

Для упрощения  структурной реализации булевых  функций ставится задача поиска абсолютной минимальной формы функции. Эта  задача заключается в отыскании  формы, содержащая минимальное число  операции заданной функционально полной функции. В общем случае эта задача не решена. Поэтому рассматривают  боле простую задачу – задачу факторизации.

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

2.2 Описание  алгоритма программы 

Блок-схема  алгоритма представлена в приложении А. 

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

Выполнение  программы начинается с инициализации  глобальных переменных и ввода исходных данных (блок 1). Далее выполняется  сохранение всех исходных данных в  массив (блок 2) и вывод результата ввода на экран (блок 3) для подтверждения  правильности введенных пользователем  данных. Затем выполняется установка переменной km в положение «-1» (блок 4) для обозначения того, что далее будет выполнена первая итерация цикла минимизации. После этого, начинает свое выполнение цикл с предусловием (блок 5), внутри которого содержатся операция присвоения значению km максимального числа пересеченных переменных (блок 6) рассматриваемых минтермов, причем если пересечения отсутствуют, то переменная km приравнивается к «0». Затем выполняется проверка условия наличия пересечений (блок 7). В случае выполнения данного условия, реализуются операции сохранения пересеченных переменных (блок 8), сохранение непересеченных элементов (блок 9) и удаления лишней строки основного массива (блок 10), так как выбранная пара пересеченных минтермов в совокупности образует конъюнкцию пересеченных переменных и скобки, содержащей неперсеченные переменные, которые записываются в одну строку. Также внутри условия содержится операция вывода формы функции, полученной на данной итерации (блок 11). По окончанию выполнения цикла, на экран выводится конечный результат (блок 12) в виде минимизированной функции. 

2.3 Кодирование  программы 

Текст программы на языке программирования Pascal представлен в приложении Б.

Для очистки  экрана при запуске программы  используется процедура CLRSCR при подключенном модуле CRT. Ввод данных осуществляется путем записи булевой функции в переменную строкового типа. В последующем выполняется анализ введенных данных и их последующее сохранение в двумерный строковый массив. Пересеченные элементы записываются в одномерный строковый массив, а непересеченные элементы – в переменную строкового типа. Для добавления данных к существующей строке используется функция CONCAT. Для определения длины строки используется функция LENGTH.

 

2.4 Анализ  полученных результатов 

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

Функцию f можно представить множеством f={ABCD}.

A=;

B=;

C=;

D=.

На первом этапе  ищутся все парные пересечения множества  функции.

Выбирается  пара {A,C} и записывается функция f ,вынося общий элемент по отношению к A и C. 
 
 

Функцию f можно представить множеством f={A₁B₁C₁}.

A₁=;

B₁=;

C₁=.

Находятся все  парные пересечения множества функции.

Выбирается  пара {A₁,C₁} и записывается функция f ,вынося общий элемент по отношению к A₁ и C₁. 
 
 

Функцию f можно представить множеством f={A₂B₂}.

A₂=;

B₂=.

Находится парное пересечение множества функции.

Тогда окончательный  вид функция имеет: 
 

Результат выполнения программы находится в приложении В. 

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

 

Заключение 

В данной курсовой работе были изучены основные методы представления ФАЛ, минимизации  ФАЛ, а также синтеза логических схем различных функций и элементов.

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

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

 

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

1) Конспект лекций  по предмету «Математическая  логика и теория алгоритмов»

2) Конспект лекций  по предмету «Теория автоматов»

3) Угрюмов Е.П.  Проектирование элементов и узлов  ЭВМ. Учебное пособие. – М.: «Высшая школа», 1987

4) Фаронов В.В. Турбо Паскаль 7.0. Практика программирования. Учебное пособие. Изд. 7-е, перепаб. – М.: «Нолидж», 2000.- 416 с.,ил. 

 

Приложение А

(обязательное) 
 

 

Приложение Б

(обязательное) 

Текст программы на языке программирования Pascal 

program AAA;

uses CRT;

var n,i,ii,j,k,l,m,mm,km,per:integer;

a:string[1];

b:string;

tabl:array [1..64,1..6] of string[100];

obshee:array [1..6] of string[100];

otl1, otl2:string;

begin

clrscr; 

                 {vvod dannyh}

writeln ('vvedite funkciyu');

readln(b);

                 {zapis' v massiv}

b:=concat(b,'+');

n:=1;

l:=1; 

for i:=1 to length(b) do begin

     if (b[i]='+') then begin

                   while (l<=6) do begin 

                                       tabl[n,l]:='0';

                                       l:=l+1;

                                       end;

                   n:=n+1;

                   l:=1;

                   end; 

 if (b[i]='x') then begin

                   tabl[n,l]:=b[i];

                   tabl[n,l]:=concat(tabl[n,l],b[i+1],b[i+2]);

                   l:=l+1;

                   end;

end; 
 

                 {vyvod ishodnoy funkcii} 

n:=n-1;

writeln;

writeln ('ishodnaya funkciya:');

write('y=');

 for i:=1 to n do begin

                 j:=1;

                 while (tabl[i,j]<>'0') do begin

                 write(tabl[i,j]);j:=j+1;

                 end;

                 if i<>n then write('+');

                 end;

writeln;

                 {metod faktorizacii}

writeln;

writeln('Vychisleniya');

km:=-1;

while (km<>0) do begin

            km:=0;

                 {poisk maksimalnogo peresecheniya}

                 {nahoghdenie maksimalnogo kolichestva peresechennyh peremennyh} 

            for i:=1 to (n-1) do begin

               for m:=i+1 to n do begin

                                 k:=0;

                                 j:=1;

                   while (tabl[i,j]<>'0') do begin

                                      l:=1;

                                      while (tabl[m,l]<>'0') do begin

                                         if tabl[i,j]=tabl[m,l] then k:=k+1;

                                         l:=l+1;

                                      end;

                                      j:=j+1;

                   end;

                   if (k>km) then begin km:=k;

                                      ii:=i;

                                      mm:=m;

                                end;

               end;

            end;

if km<>0 then begin

                 {zapis obshih peremennyh v otdelnyy massiv} 

            for i:=1 to 6 do obshee[i]:='0'; 

            i:=0;

            for j:=1 to 6 do begin

               for l:=1 to 6 do begin

                       if ((tabl[ii,j]=tabl[mm,l])and(tabl[ii,j]<>'0')and(tabl[mm,l]<>'0'))

                           then begin i:=i+1; obshee[i]:=tabl[mm,l];

                           tabl[ii,j]:='0';tabl[mm,l]:='0';

                       end;

               end;

            end; 

                 {zapis ne peresechennyh peremennyh v otdelnuyu stroku} 

            otl1:='0';

            otl2:='0';

            for j:=1 to 6 do begin

               if tabl[ii,j]<>'0' then if otl1='0' then otl1:=tabl[ii,j] else otl1:=concat(otl1,tabl[ii,j]);

               if tabl[mm,j]<>'0' then if otl2='0' then otl2:=tabl[mm,j] else otl2:=concat(otl2,tabl[mm,j]);

            end; 
 

                {zapolnenie ishodnogo massiva poluchennymi dannymi}