Русская логика – индикатор интеллекта (стр. 3 )

a = x7x6’x1’ b = x7’x6x2.

На рисунке даны примеры фигур, не являющихся прямоугольниками Карно. Фигуры k, m и n не являются прямоугольниками Карно в силу нарушения принципа симметрии. Фигура n не симметрична относительно горизонтальной оси симметрии 2-го ранга, фигура m не симметрична относительно вертикальной оси симметрии 3-го ранга. Фигура k симметрична относительно оси симметрии 3-го ранга, но её половина не симметрична относительно оси 2-го ранга.

Поразительно, что за 30 лет никто из преподавателей и «учёных» так и не освоил моего алгоритма. До сих пор плодятся неграмотные методы работы с картами Карно, в которых утверждается, что достаточно убедиться, что в фигуре покрытия 2n клеточек, чтобы считать её ПК. Фигура m на Рис. 1.11 содержит 8 клеточек, но не является прямоугольником Карно.

Алгоритм «НИИРТА» графической минимизации булевых функций.

1. Заполнить карту Карно нулями и единицами в соответствии с таблицей истинности или заданным алгебраическим выражением.

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

3. Проверить каждую фигуру покрытия на соответствие принципу симметрии Лобанова. В противном случае изменить контур фигуры покрытия в соответствии с указанным принципом симметрии так, чтобы она превратилась в прямоугольник Карно.

4. Каждому прямоугольнику Карно соответствует одна импликанта, причём если в границах прямоугольника Карно какая-либо переменная принимает значения как 0 , так и 1 , то эта переменная не войдёт в импликанту.

Применим карту Карно для решения задачи 1. На рисунке дан единственный минимальный вариант решения (иногда их бывает несколько).

f = x4x1 + x4x2 + x4x3 + x3x2x1

Эти выражения представляют собой пример дизъюнктивной нормальной формы (ДНФ).

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

f = x4(x1 + x2 + x3) + x3x2x1

Кстати, полученный результат f = x4(x1 + x2 + x3) + x3x2x1 наводит на печальные размышления. На русский язык эта формула переводится так: «Абитуриент будет принят в учебное заведение, если за него проголосуют 3 члена комиссии или председатель вместе хотя бы с одним членом комиссии». Но ведь этот ответ мы могли бы получить и эвристически, на основе здравого смысла, просто немного подумав. Не пришлось бы рисовать таблицу истинности, заполнять карту Карно и т. д. Формальное решение логических задач иногда превращает нас в «мартышек с арифмометром», отвращает от мышления. Аналогичная опасность грозит и программистам, и микропрограммистам, т. е. схемотехникам.

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

Вполне естественно, что результат минимизации не изменился:

f = x4(x1 + x2 + x3) + x3x2x1

1.6. Оценка сложности реализации булевых функций

Приблизительную оценку сложности реализации логической функции можно дать по ДНФ, подсчитав коэффициент сложности Кс, равный общему количеству переменных, входящих в ДНФ, плюс количество импликант. Например, для СДНФ к задаче 1 Кс = 32+8=40, а для отминимизированной функции Кс = 9+4=13.

Для того, чтобы перейти от логической функции (ЛФ) к электронной схеме, построенной на интегральных микросхемах (ИМС) типа И-НЕ, достаточно преобразовать ЛФ по правилу де Моргана. Например:

f = x4x1 + x4x2 + x4x3 + x3x2x1 = [(x4x1)’ & (x4x2)’ & (x4x3)’ & (x3x2x1)’]’.

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

При использовании базиса И-НЕ обе функции примут вид, представленный на рисунке. Из рисунка видно, что реализация функции по СДНФ потребовала 5 корпусов ИС, по минимальной форме - 1,58 корпуса ИС, по скобочной форме - 1,16 корпуса. Таким образом, минимизация по карте Карно дала нам трёхкратный выигрыш по корпусам ИС относительно реализации по СДНФ. Реализация по скобочной форме уменьшила объём оборудования ещё на 30%. Кстати, оценка экономии по Кс даёт приблизительно такой же результат: 40/13 = 3,08.

1.8. Формы задания булевых функций.

Об одной форме задания булевых функций мы уже говорили - это таблица истинности. Иногда применяется более компактная запись, использующая восьмеричные, десятичные или шестнадцатеричные эквиваленты наборов. Например, набор x4x3x2’x1’ может быть представлен обобщённым кодом 1100 , десятичным эквивалентом которого является число 12. Удобнее всего 8-чные и 16-чные коды.

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

program nabor;

uses crt;

type stroka = string[4];

txt = file of stroka;

var f1:txt;

x, y,i, j,n, m,b:integer;

st:stroka;

----

function intchar(m:integer):char;

var

ch:char;

begin

case m of

0..9: ch:=chr(m+ord('0'));

10..35: ch:=chr(ord('A')+m-10);

else

begin

writeln('Ошибка ввода');

halt;

end;

end{case};

intchar:=ch;

end;

-----

function int10(a:longint;b:integer):string;

{Пеpевод целого 10-ичного числа в (2..36)-ичные системы}

{a, b - исх. 10-ичн. число и основание сист. счисл. соотв-енно}

var s:string;

m, i,j:integer;

chrarr:array[0..30] of string;

begin

i:=0;

for j:=0 to 30 do chrarr[j]:=' ';

repeat

m:=(a mod b);

chrarr[i]:=intchar(m);

a:=a div b;

i:=i+1;

until (a=0);

s:=chrarr[i];

for j:=i-1 downto 0 do

s:=s + chrarr[j];

int10:=s;

end;

{=================================================}

begin

{$I-} {Внутр. проверка правильности операции с файлом отключена}

writeln('******');

writeln('* Фоpмиpование файла случайных *');

writeln('* 2-pазpядных 4,8,16-ичных чисел для каpт Каpно *');

writeln('* Pезультиpующий файл - rnd. txt *');

writeln('* *');

writeln('******');

writeln;

write('Введите длину файла n и количество пеpеменных m(4,6,8) ');

readln(n, m);

assign(f1,'rnd. txt');{Связь f1 с pезультиpующим файлом }

{$I+} {Включить внутр. проверку}

rewrite(f1); {Открыть файл для записи}

case m of

4: begin b:=4; x:=15; end;

6: begin b:=8; x:=63; end;

8: begin b:=16;x:=255; end;

end;{case}

randomize;

for i:=1 to n do

begin

y:=random(x);

st:=int10(y, b);

write(st:8);

write(f1,st);

end;

close(f1);

writeln;

writeln('Файл rnd. txt сфоpмиpован');

writeln('Нажмите клавишу пpобела');

repeat until keypressed;

end.

Задача 3.

Полностью определённая булева функция от 4-х переменных задана десятичными рабочими наборами: РН(4) = 5, 6, 7, 8, 9, 10, 11.Число в скобках указывает количество переменных. Найти минимальную форму этой функции.

Решение.

Так как функция является полностью определённой, то запрещёнными наборами ЗН(4) являются наборы 0 - 4,Исходя из этой информации, составляем таблицу истинности и осуществляем минимизацию по карте Карно.

Таблица 4.

РН(4)	x4 x3 x2 x1	f
5		1
6		1
7		1
8		1
9		1
10		1
11		1

ЗН(4)	x4 x3 x2 x1	f
0		0
1		0
2		0
3		0
4		0
12		0
13		0
14		0
15		0

По карте Карно получаем результат:

f = x4x3’ + x4’x3(x1 + x2)

Задание 1.

Найти минимальную форму полностью определённых булевых функций, заданных 10-чными рабочим наборами:

1-1) РН(4) = 0, 1, 5, 7 - 9, 13, 15. (Кс = 6)

1-2) РН(5) = 4, 6, 8, 10, 13, 17, 24, 30. (Кс = 28)

1-3) РН(6) = 1 - 8,,Кс = 32)

1-4) РН(7) = 7 - 15,,,Кс = )

1-5) РН(8) = 7 - 15, Кс = )

1.9. Минимизация недоопределённых булевых функций

Функция от n переменных называется недоопределённой, если она задана не на всех 2n наборах.

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

Этот алгоритм был опубликован автором в 1977 году, но до сих пор его не освоили "логики".

Задача 4.

Найти минимальную форму функции y, представленной на рисунке 1.16.

Решение.

Функция задана только на 5 наборах. Добавим к трём рабочим наборам ещё пять, а именно: 0000, 0011, 1000, 1011, 1010. Все оставшиеся наборы доопределим как запрещённые. В результате такого доопределения получим прямоугольник Карно, состоящий из 8 элементарных квадратов Карно. Этому прямоугольнику соответствует функция: y = x3’.

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

1.10. Минимизация системы булевых функций.

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

Задача 5.

Построить преобразователь двоичного кода, получаемого на выходе делителя частоты на 12, в двоично-десятичный код. Условие задачи отражено в таблице. Делитель работает в коде 8-4-2-1. Такой делитель и преобразователь используются в электронных часах.

Решение.

Для каждой функции yi заполняем карту Карно, производим доопределение и осуществляем минимизацию. Весь процесс отражён на рисунке.

В результате минимизации получаем систему функций:

y1 = x1; y2 = x4’x2; y3 = x3;

y4 = x4x2’; y5 = x4x2 .

Задача 6.

Построить один разряд многоразрядного сумматора.

Решение.

Пусть ai и вi - значения i-ых разрядов слагаемых а и в, Pi и Si - значения переноса и суммы на выходе i-го разряда, Pi-1 - значение переноса на выходе предыдущего разряда, тогда работу сумматора можно описать с помощью таблицы истинности.

Имеем систему полностью определённых булевых функций. Производим раздельную минимизацию (см. рисунок).

Si = ai’вi’Pi-1 + ai’вiPi-1’ + aiвi’Pi-1’ + aiвiPi-1 = Pi-1(ai~вi) + Pi-1’(ai Å вi) =

= Pi-1 ~ (ai~вi).

Pi = вiPi-1 + aiPi-1 + aiвi

Для реализации лучше Pi = aiвi + Pi-1(ai~вi)’ , так как может быть использован общий для Si и Pi сомножитель (аi~вi)’. Схема сумматора представлена на рисунке. Здесь же дано условное обозначение одноразрядного сумматора, где А и В - одноразрядные слагаемые, P0 и P1 - входной и выходной переносы, S1 - сумма.

На этом же рисунке изображён двухразрядный сумматор, выполненный на микросхеме 133ИМ2. Здесь А1, В1, А2, В2 - соответственно значения первых и вторых разрядов слагаемых А и В; S1 и S2 - 1-ый и 2-ой разряды суммы; P0 - входной перенос для первого разряда,

P2 - выходной перенос.

Задание 2.

2-1. Построить 2/(2-10) преобразователь для делителя частоты на 24 , работающего в коде . Этот преобразователь использовался на заре цифровой схемотехники в радиолюбительских электронных часах.

2-2. Построить 4-входовой сумматор для суммирования одноразрядных двоичных чисел.

Глава вторая

МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ МЕТОДОМ ОБОБЩЁННЫХ КОДОВ.

В СДНФ функции от n переменных каждый набор &xi можно заменить последовательностью нулей и единиц. Такая последовательность носит название обобщённого кода.

Метод обобщённых кодов был разработан в конце 60-х годов на 21-й кафедре Академии им. Дзержинского д. т. н. Мавренковым Леонидом Трофимовичем. Дальнейшее развитие метода и доведение его до инженерных методик было выполнено сотрудниками этой кафедры к. т.н. , к. т.н. и к. т.н. (см. "Вопросы оборонной техники", 1972 г.). Этот метод до сих пор является самым эффективным методом минимизации логических функций.

Я понимаю, что доходчиво изложить метод Мавренкова очень непросто. Вполне допускаю, что не все читатели освоят этот метод. Для решения подавляющего большинства задач вполне достаточно знания карт Карно. Метод Мавренкова должен быть реализован на ЭВМ.

Например, набору x4x3’x2x1’ соответствует обобщённый код 1010. Для ДНФ обобщённый код (ОК) имеет прочерки на местах отсутствующих переменных. Например, для функции от 5 переменных набору x5x2’ соответствует ОК = 1--0-.

Методом обобщённых кодов удобно работать с функциями, заданными таблицами истинности. Причём рабочим наборам соответствуют рабочие обобщённые коды (РОК), запрещённым наборам - запрещённые обобщённые коды (ЗОК).

Введём понятие оценочной функции. Оценочная функция F0p(F1p) определяет количество нулей (единиц) для одного разряда всех РОК. Оценочная функция F0з(F1з) определяет количество нулей (единиц) для одного разряда всех ЗОК.

Функция вида F0 = F0р + F1з называется нулевой оценочной функцией.

Функция вида F1 = F1р + F0з называется единичной оценочной функцией.

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

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

2.1. Общий алгоритм определения МОК.

Алгоритм 1.

1. Присвоить индексу МОК значение 1, т. е. i :=1.

2. Подсчитать по таблице истинности F0 и F1 для всех разрядов РОК и ЗОК.

3. В качестве базы МОКi (БМОКi) или дополнение к БМОКi выбрать переменную с максимальной F0 или F1 . Если F0 = max, то переменная входит в БМОКi нулём. Если F1=max, то переменная входит в БМОКi единицей. Если несколько переменных имеют максимальные оценочные функции, то выбрать в качестве БМОК ту переменную, у которой соответствующая запрещённая оценочная функция (F0з, F1з) имеет минимальное значение; в противном случае в качестве БМОК взять любую переменную с максимальной оценочной функцией.

4. Выписать все РОК и ЗОК, покрываемые базой МОКi. Если БМОКi не покрывает ни одного РОК или покрывает все ЗОК, то приравнять нулю оценочные функции F0 и F1 для данного разряда и перейти к п.3. Если покрываемых ЗОК нет, то перейти к п.6.

5. Подсчитать F0 и F1 для всех разрядов РОК и ЗОК, покрытых данной базой, кроме тех разрядов, которые образуют БМОКi. Присоединить к БМОКi переменную (дополнение к БМОКi) с максимальной оценочной функцией в соответствии с требованиями п.3. Считать этот ОК новой базой МОКi. Если новая БМОКi покрывает столько же ЗОК, сколько и на предыдущем шаге, то приравнять нулю оценочные функции для дополнения к БМОКi, отбросить присоединённую переменную и добавить к БМОКi переменную с максимальной оценочной функцией в соответствии с требованиями п.3, считать полученный ОК новой БМОКi. Если БМОКi покрывает хотя бы один ЗОК, перейти к п.4.

6. Принять в качестве МОКi базу МОКi.

7. Если все РОК из исходной таблицы истинности покрыты минимальными обобщёнными кодами, перейти к п.9.

8. Выписать из исходной таблицы истинности все ЗОК и те РОК, которые не покрыты минимальными обобщёнными кодами. Считать вновь полученную таблицу исходной таблицей истинности. Увеличить индекс МОК на единицу, т. е. i :=i+1. Перейти к п.2.

9. Конец.

Поясним положение пп.4 и 5 алгоритма 1. Пусть таблица истинности состоит из одного РОК 1110 и трёх ЗОК: 1010, 0110 и 1111.

После подсчёта оценочных функций оказалось, что для второго разряда F0 = 3 = max. Если в соответствии с максимумом оценочной функции взять в качестве БМОК код --0- , то этот код не покроет ни одного РОК, что недопустимо, т. к. БМОК обязательно должна покрыть хотя бы один РОК.

Несколько иная ситуация складывается в том случае, когда БМОК, найденная по максимуму оценочной функции, покрывает часть РОК и все ЗОК. Пусть функция задана пятью РОК и одним ЗОК.

Если в соответствии с максимумом взять в качестве БМОК код --1-, то мы покроем ЗОК, что недопустимо. Поэтому в качестве БМОК можно, например, взять ---1.

Проиллюстрируем выполнение алгоритма 1 примерами.

Задача 7.

Построить МДНФ булевой функции y, заданной таблицей, по методу ОК.

Решение.

1. Выбираем в качестве БМОК1 переменную x3 , т. е. БМОК1 = -1--. Эта БМОК1 покрывает все РОК и один ЗОК.

2. Выписываем эти РОК и ЗОК (см. след. таблицу).

3. По максимальному F0 = 5 определяем вторую переменную базы МОК1. Это переменная x1. Она входит в БМОК инверсным значением, т. е. БМОК1 = -1-0.

4. Так как БМОК1 = -1-0 не покрывает ни одного ЗОК и покрывает все РОК, то минимизацию считаем законченной и принимаем МОК1 = БМОК1 = -1-0 , т. е.

y = x3x1’ .

Такой же результат получается и по карте Карно.

Задача 8.

Построить МДНФ функции, заданной таблицей.

Решение.

1. Принимаем БМОК1 по F1 = 10 (можно по F0 =10).

БМОК1 =

БМОК1 покрывает один ЗОК и все РОК.

2. Выписываем все РОК и ЗОК, покрываемые БМОК1. После подсчёта оценочных функций оказывается, что максимум F0 приходится на x1, поэтому

БМОК1 =

МОК1 = БМОК1 =

3.Непокрытым оказался только один РОК. Выписываем этот РОК и все ЗОК в таблицу.

4. Находим БМОК2 =

МОК2 = БМОК2 =

Результат минимизации выглядит так:

y = x6x1’ + x3

Такой же результат получен и по карте Карно.

Задание 3.

Найти минимальную форму функций, указанных в задании 1, методом обобщённых кодов.

2.2. Алгоритм соседнего определения базы МОК (алгоритм Мавренкова).

Алгоритм 1 требует раздельного размещения РОК и ЗОК. Приведение таблицы истинности к такому виду усложняет метод ОК.

Процесс минимизации методом ОК может быть существенно упрощен, если определение БМОК производить с использованием приводимого ниже алгоритма.

Алгоритм 2.

1. Присвоить индексу МОК значение 1, т. е. i := 1 .

2. Присвоить индексу РОК значение 1 , т. е. j := 1.

3. Взять РОК из исходной таблицы истинности и, сравнивая его со всеми ЗОК, определить переменные, по которым РОК может быть склеен с ЗОК. Эта совокупность переменных и будет базой МОКi. Перейти к п.7.

4. Если РОКj не имеет соседних ЗОК, то j := j + 1 и перейти к п.3. Если в таблице истинности нет ни одного РОК, соседнего хотя бы с одним ЗОК, то перейти к п.5.

5. Подсчитать по таблице истинности F0 и F1 для всех разрядов.

6. В качестве базы МОКi (БМОКi) или дополнения к БМОКi выбрать переменную с максимальной F0 или F1. Если F0 = max, то переменная входит в БМОКi нулём. Если F1 = max, то переменная входит в БМОКi единицей. Если несколько переменных имеют одинаковые оценочные (максимальные) функции, то выбрать в качестве БМОКi ту переменную, у которой соответствующая запрещённая оценочная функция ( F0з или F1з ) имеет минимальное значение, в противном случае в качестве БМОКi взять любую переменную с максимальной оценочной функцией F0 или F1 .

7. Выписать РОК и ЗОК, покрываемые базой МОКi. Если БМОКi не покрывает ни одного РОК или покрывает все ЗОК, то приравнять нулю оценочные функции F0 и F1 для данного разряда и перейти к п.6. Если покрываемых ЗОК нет, то перейти к п.9.

8. Подсчитать F0 и F1 для всех разрядов РОК и ЗОК, покрываемых данной базой, кроме разрядов (переменных), образующих БМОКi. Присоединить к БМОКi переменную (дополнение к БМОКi) с максимальной оценочной функцией в соответствии с требованиями п.6. Считать полученный ОК новой базой МОКi. Если новая БМОКi покрывает столько же ЗОК, сколько и на предыдущем шаге, то приравнять нулю оценочные функции или дополнения к БМОКi, отбросить присоединённую переменную и добавить к БМОКi переменную с максимальной оценочной функцией в соответствии с положениями п.6, считать полученный ОК новой БМОКi. Если БМОКi покрывает хотя бы один ЗОК, перейти к п.7.

9. Принять в качестве МОКi базу МОКi.

10. Если все РОК из исходной таблицы истинности покрыты минимальными обобщёнными кодами, перейти к п.12.

11. Выписать из исходной таблицы истинности все ЗОК и те РОК, которые не покрыты минимальными обобщёнными кодами. Считать вновь полученную таблицу исходной таблицей истинности. Увеличить индекс МОК на единицу, т. е. i := i+1. Перейти к п.2.

12. Конец.

Задача 9.

Произвести минимизацию булевой функции, заданной таблицей.

Решение.

1. По алгоритму 2 пп. 1-3 для РОК2 находим соседний ЗОК, т. е. находим БМОК1 = .

2. По алгоритму 2 пп. 7-9 находим

МОК1 =

Так как МОК1 покрывает все РОК, то в соответствии с п.10 алгоритма 2 получаем

y = x5’x2’

Сущность алгоритма 2 заключается в том, что отыскиваются в первую очередь « необходимые « МОК, т. е. МОК для тех РОК, развязывание которых с ЗОК максимально затруднено, так как они развязываются только по тем переменным, по которым возможно склеивание данного РОК со всеми ЗОК. Под развязыванием понимается процесс выявления тех переменных в РОК, которые не встречаются в ЗОК.