Конспект лекций по дискретной математике
=( x1vx2vx3 x4)(x1vx5)= SQ=9
_
=x1v(x2vx3)( x2vx4) x5= SQ=9
_ _
= x1v(x2vx3 x4) x5= SQ=8
Оценка эффекта факторизации.
Этот эффект характеризуется разностью цен схемы до и после факторизации.
Можно показать, что для однократной факторизации ее эффект определяется выражением :
DSQ= SQдо - SQпосле=m(k-1)+q-D ,
где m - количество букв, выносимых за скобки;
k - количество термов, из которых происходит вынесение. q - количество термов, в которых после вынесения осталась одна буква (qЈk);
D=1, если вынесение осуществляется из всех термов;
D=2, если не из всех.
Для эффективного решения задачи факторизации необходимо учитывать следующий момент :
При наличии у булевой функции нескольких минимальных форм целесообразно выбрать из них такие, для которых применение факторизации даст выигрыш в цене схемы.
При минимизации не полностью определенной булевой функции может оказаться, что максимальный эффект за счет факторизации дает нормальная форма, не являющаяся минимальной.
Пример :

|10x1 _ _
cmin(f)=|xx10 МДНФ y=x3x4vx1x2x4 SQ=7
|10x1 _ _ _
cmin(f)=|101x ДНФ y=
x1x2x4
vx1x2
x3=
x1x2(x3v
x4) SQ=5
В некоторых случаях максимального эффекта за счет факторизации можно достичь путем расширения термов МНФ с применением законов товтологии
МДНФ y=x1x2x3vx1x2x4vx1x3x5x6vx2x4x5x6= SQ=18
= x1x2(x3v x4)v x5x6(x1x3v x2x4)= SQ=16
= x1x2(x1x3v x2 x4)v x5x6(x1x3v x2x4)= SQ=20
=(x1x3v x2 x4)( x1x2v x5x6) SQ=14
Построение одновыходных схем.
Декомпозиция булевых функций.
Задача декомпозиции булевой функции в общем случае состоит в таком разделении множества ее аргументов на ряд подмножеств, при котором можно выразить исходную функцию f(x) через вспомогательную промежуточную функцию j(z), где zМx.
В частном случае имеет место так называемая простая разделительная декомпозиция, при которой множество аргументов x разделяется на два непересекающихся подмножества (z,w®(zЗw=j;zИw=x)) и приведение исходной функции к виду f(x)=f(j(z,w)).
Пример : f3(x)=V(1,2,4,7)
(f=1)

z=(x2x3) W={x1}
_ _
j(z)=x2x3vx2x3
_ _
f(x)=x1j(z)vx1j(z) SQ=13

SQ=13 T=5t
Схема базиса Жигалкина.

SQ=4 T=2t
Применение декомпозиции там, где он уместно, во многих случаях позволяет уменьшить цену синтезируемой схемы.
_ _ _ _ _ _ _ _ _ _
МДНФ y=x1x2x3x4vx2x5vx3x5vx4x5=x1x2x3x4vx5(x2vx3vx4)
SQ=14
_
j(z)=x2vx3vx4
___ _
f(x)=x1*y(z)vx5*j(z) SQ=10
Синтез многовыходных комбинационных схем.
МКС представляется в виде обобщенного «черного ящика»

Закон функционирования МКС представляется в виде системы булевых функций
|y1=f1(x1...xn)
|y2=f2
|.
|.
|.
|yn=fn
Естественным образом, при решении задачи синтеза МКС применяются методы факторизации и возможной декомпозиции, применительно не к одной функции, а к системе.
Минимизация системы Булевых функций
Задача минимизации применительно к системе Булевых функций решается аналогично как для одной функции и сводится к получению минимального покрытия. Для решения этой задачи система приводится к одной функции путем дополнения множества агументов подмножеством вспомогательных переменных, с помощью которых выделяются отдельные функции системы. Количество вспомогательных переменных kіlog2m, m - количество функций.
Пример:

Раздельная минимизация:
y1
Cmin (y1)=
y2
Cmin (y2)=
МДНФ:

![]()
При построении схемы по этому выражению, она разлагается на две независимые подсхемы, отдельные для реализаций каждой функции.
Совместная минимизация
Пусть V=0 для у1; V=1 для y2
Cmin(y1,y2)=
;
Z=
(общий
терм)
![]()
![]()
Пример:

V1V2=00 y1
V1V2=01 y2
V1V2=10 y3
V1V2=11 y4

Cmin(S)=
Общие термы:


![]()
При совместной минимизации Булевых функций система в минимальной форме может оказаться, что некоторые термы поглощаются другими, т.е. после получения минимальной формы необходимо исключить поглощаемые термы.
После получения минимального покрытия при записи минимальных форм с начала выделяются термы, общие для нескольких функций и обозначаются вспомогательными функциями (Z1-Z4).
В целях удобства рядом с каждым общим термом рекоммендуется проставить его принадлежность.
Далее выписываются минимальные формы для отдельных функций с учетом их собственных термов и общих термов, принадлежащих данной функции. При наличии незадействованных комбинаций вспомогательных переменных все наборы аргументов для них являются безразличными.
Пример:![]()


Сmin(S)=
Для большого числа функций и их аргументов применение карт Карно для совместной минимизации выглядит затруднительным. В этом случае можно использовать следующие подходы:
Применение машинных методов
Раздельная минимизация и использование карт Карно.
Выделение подмножеств из функций системы для их совместной минимизации.
Факторизация системы Булевых функций
Применительно к системе задача факторизации состоит в выделении общих термов или их частей для отдельных функций системы с целью уменьшения цены схемы. Сходная задача уже решается при совместной минимизации функций системы, но совместная минимизация не исключает применение дальнейшей факторизации. Особенно актуальной задачей факторизации становятся при раздельной минимизации функций системы. Совместная факторизация не исключает рпаздельной минимизации в рамках каждой функции.
МДНФ:
![]()
![]()
![]()
Порядок проведения двух видов факторизации совместной и раздельной в большинстве случаев безразличен.
Декомпозиция системы Булевых функций
Декомпозиция системы Булевых функций - выражение одних функций через другие.
Пример:

|
a |
b |
p |
s |
q |
|
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
0 |
|
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
1 |
|
1 |
0 |
0 |
1 |
0 |
|
1 |
0 |
1 |
0 |
1 |
|
1 |
1 |
0 |
0 |
1 |
|
1 |
1 |
1 |
1 |
1 |
Однофазные входы
Раздельная минимизация



![]()
Раздельная факторизация

![]()
Совместная факторизация
,

![]()

![]()

![]()
![]()
![]()

Совместная минимизация

Cmin=
V=0, S
V=1, q

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

Достаточно широко используется термин аппаратная поддержка данных. Принято считать что данные некоторого типа и определенных форматов являются аппаратно поддерживаемыми в конкретной ЭВМ если в системе команд процессора имеются команды для обработки данных данного типа в соответствующих форматах. Для нечисловых данных основных типов поддержка осуществляется на уровне системных команд. Для логических значений в которых смысловое содержание относится к каждому биту поддержка осуществляется на уровне логических команд: AND,OR,XOR,NOT.
Символьные данные поддерживаются на уровне команд преобразования символов, а также на уровне команд обработки строк.
В ПЭВМ символьные данные представляются в коде ASCII. Сам по себе этот код является семи битным ,но для удобства он расширен до восьми битного с добавлением в наго букв национального алфавита.
Числовые данные естественно поддерживаются на уровне арифметических команд. В связи с разделением чисел на двоичные и десятичные для их обработки используется соответствующая арифметика. В зависимости от формы представления двоичных чисел используется два вида двоичной арифметики.
Двоичная целочисленная арифметика.
Арифметика с плавающей запятой.
Десятичные числа представляются в двоично-кодированном виде ,в котором любая десятичная цифра представляется в естественном двоичном коде, который принято называть :
8-4-2-1
9 - 1001,8 - 1000,7 - 0111,...,1 - 0001.
В упакованном формате в каждом байте содержится две десятичные цифры ,в не упакованном одна. В ПЭВМ неупакованный формат представляется ASCII-кодом десятичных цифр ,в котором собственно цифра помещается в младшую тетраду ,а старшая тетрада имеет вид 0011.
Пример : 985
Упакованный формат 0000|1001 1000|0101
Не упакованный формат 0011|1001 0011|1000 0011|0101
Десятичные числа используются в ЭВМ на этапе ввода данных и вывода результатов. После ввода они преобразуются в двоичную систему ,в которой реализуется обработка данных. На этапе вывода двоичный результат предварительно преобразуется в десятичную форму. Преобразования десятичных чисел в двоичные и обратно может быть реализовано как на аппаратном так и на программном уровне. На аппаратном уровне предполагается наличие в системе команд процессора соответствующих команд преобразования. Так например в IBM/370 имеется две команды : CBD - преобразование двоичного числа в десятичное , CDB - преобразование десятичного в двоичное. В ПЭВМ подобных команд нет и преобразование реализуется на программном уровне, с использованием стандартных процедур. Общей тенденцией в вычислительной технике при решении вопроса о реализации той или иной функции на аппаратном или программном уровне является: аппаратный уровень ,обладая большей стоимостью реализации, обеспечивает и большую скорость реализации этой функции. Классическая схема обработки - десятичный ввод, преобразование в двоичную систему, двоичная обработка, преобразование в десятичную, десятичный вывод - выглядит неоправданной при решении задач с большим объемом обрабатываемых данных и малым объемом обработки. Более целесообразный путь десятичный ввод, десятичная обработка, десятичный вывод. Для реализации подобной схемы поддерживаемой на аппаратном уровне необходимо использование в системе команд процессора десятичной арифметики.
Двоичные числа с фиксированной запятой.
В зависимости от местоположения фиксированной запятой (справа или слева от числа ) числа с фиксированной запятой делятся на целые и дробные. Дробные числа с фиксированной запятой как таковые в современных ЭВМ не используются ,а используются как часть числа с плавающей запятой в виде его мантиссы . Целые числа делятся на два типа: знаковые и без знаковые. Это разделение определяется способом интерпретации старшего разряда числа. В знаковых он интерпретируется как знак, а в без знаковых числах как старшая цифра числа. Во многих случаях интерпретация целого числа ,как знакового или без знакового возлагается на программиста, хотя на аппаратном уровне может поддерживаться тот или иной способ интерпретации. Примером подтверждающим это может использоваться парные команды умножения MUL,IMUL и деления DIV,IDIV в процессорах INTEL 80X86. Первая команда из этих пар интерпретирует операнды и результат как без знаковое целое ,а вторая как знаковое. Особенностью представления знаковых целых чисел является использование дополнительного кода. Под дополнительным кодом знакового n - разрядного целого числа понимается следующие выражение: мx, при xі0
[x] дк = н
о2x -|x|, при x<0
Например n=6 число 30 представиться в виде [30] дк =011110
[-30] дк =1.000000
011110
100000
В связи с тем ,что значение 2n не представимо в n - разрядном формате можно осуществлять вычитание из нуля. На этом принципе поддерживаются на аппаратном уровне операция изменения знака числа (NEG) с преобразованием его в дополнительный код. В терминологии по поводу прямого и дополнительного кода существуют некоторые разногласия. Авторы некоторых монографий считают что положительные числа представлены в прямом коде ,а отрицательные в дополнительном. Для общности представления ,как положительных ,так и отрицательных чисел в дополнительном коде правильнее считать что дополнительный код положительного числа совпадает с его прямым кодом. Для отрицательных чисел это несправедливо, так как прямой код отрицательного числа в знаковом разряде содержит единицу ,а в цифровых модуль числа. [-30]пр = 111110
Использование именно дополнительного кода в представлении знаковых целых чисел можно объяснить простотой реализации в этом коде операции сложения и вычитания которые являются самыми массовыми при решении задач научного комплекса. Что касается операций умножения и деления то при использовании дополнительного кода по сравнению с прямым усложняет алгоритм их реализации но тем не менее разработаны методы для выполнения этих операций в дополнительном коде.
Диапазон предоставления чисел
Диапазон представления знаковых n-разрядных чисел определяется в виде
-2 n-1Ј Х Ј 2n-1 -1
1 000...0 0 111...1
n-1 n-1
Для стандартного байтного формата (n=8) диапазон :
-128 Ј XцзнЈ127
Максимальное по модулю отрицательное число оказывается по модулю на единицу больше максимального положительного числа.
В связи с этим применение операции изменения знака к максимальному по модулю отрицательному числу приводит к переполнению формата, так как это число не представляется в области положительных чисел.
Формальным приемом изменения знака числа с соответственным преобразованием его из прямого кода в дополнительный или наоборот является инвертирование всех разрядов числа с добавлением единицы в младший разряд.
Для этой цели можно использовать следующее мнемоническое правило : младшие нули и крайняя правая единица прямого кода сохраняются и в дополнительном, а остальные разряды подлежат инвертированию.
Диапазон представления беззнаковых целых чисел в n- разрядном формате имеет вид :
0ЈХцб.знЈ2n-1
Для стандартного байтного формата (n=8) диапазон :
0 Ј XцзнЈ255
Диапазон представления дробных чисел.
Для правильной n-разрядной двоичной дроби диапазон представления имеет вид
2-n ЈAдрпрЈ1-2-n
Неправильная дробь содержит обязательную двоичную единицу в целой части. Для неправильной n-разрядной двоичной дроби диапазон представления имеет вид
1 ЈAдрнепрЈ2-2-(n-1)
Числа с плавающей запятой.
В формате представления чисел с плавающей запятой выделяются 3 части : знак числа (представляется крайне левым битом формата); мантисса числа (представляется в виде правильной или неправильной двоичной дроби); порядок числа (представляется в общем виде как целое число со знаком). Значение числа А с плавающей запятой представляется в виде :
Апз=(sign A)-1*Ma*SPa
где sign A - знак 0 - «+», 1 - «-»
SPa - порядок числа А, S - основание порядка.
Число с плавающей запятой называется нормализованным, если старшая цифра его мантиссы значащая (не 0), в противном случае число называется не нормализованным.
Основными особенностями представления чисел с плавающей запятой в современных ЭВМ являются :
Мантисса числа независимо от его знака представляется в прямом коде
Порядок числа представляется не в явном виде как знаковое целое, а со смещением в виде беззнакового целого числа.
Эта особенность облегчает обработку порядка при выполнении арифметических операций. Величина смещения равна либо весу старшего разряда порядка, либо на единицу меньше.Cмещенный порядок принято называть характеристикой числа.
В качестве основания порядка используется значение S=16 (ЕС ЭВМ) или S=2 (СМ ЭВМ, IEEE).
В подавляющем большинстве случаев принято использование нормализованных чисел с целью повышения их точности.
При использовании основания порядка, равного двум, нормализованное число содержит обязательную единицу в старшем разряде мантиссы.
Это позволяет не представлять его в явном виде в формате, что позволяет увеличить точность числа. Подобное сокрытие старшего разряда мантиссы называется скрытым разрядом (скрытой единицей).
В ЭВМ любого класса для представления чисел с плавающей запятой принято использовать несколько форматов (как правило, чтобы удовлетворить противоречивым требованиям повышения точности чисел и повышения скорости их обработки).
Эти форматы используют наименования :
а) короткий (одинарной точности) - 32 бита;
б) длинный (двойной точности) - 64 бита;
в) расширенный (расширенной точности) - 80 бит для РС и 128 бит для больших ЭВМ.
Переход от короткого формата к расширенному может сопровождаться либо расширением только разрядности мантиссы (ЕС ЭВМ) либо расширением разрядности как мантиссы так и порядка (IEEE).
Диапазон представления чисел с плавающей запятой.
Его принято определять в отношении модуля нормализованного числа. В общем случае этот диапазон представим в виде :
М а мин норм *SРа минЈЅА пл нормЅЈМ Ра макс*S Ра макс
Особенности представления чисел с плавающей запятой в ЭВМ различных классов :
ЕС ЭВМ (IBM/370) - ЭВМ общего назначения (Main Frame) числа представляются в трех форматах :
0 1 7 8 21 (63, 127)
|
знак |
характеристика |
мантисса |
В больших ЭВМ принято нумерацию разрядов в формате производить слева направо. В мини компьютерах и персональных ЭВМ - справа налево.
ХА=РА+d ; d=64
0ЈXAЈ127
-64ЈPAЈ63
В связи с тем, что в качестве основания порядка используют S=16 признаком нормализации числа является наличие значащей шестнадцатиричной цифры в старших разрядах мантиссы. Таким образом признаком нормализации числа является наличие хотя бы одной единицы в старшей тетраде мантиссы.
Диапазон представления нормализованной мантиссы
1/16ЈМАнормЈ1-2-m<1
m - число разрядов мантиссы
В общем случае диапазон представления нормализованной мантиссы в виде правильной дроби при основании порядка S имеет вид :
1/SЈMAH<1
При выполнении арифметических операций при некоторых соотношениях операндов могут возникать ситуации когда результат операции выходит за пределы диапазона.
Выход за праву границу диапазона - получение очень большого по модулю результата классифицируется как переполнение порядка, за левую - как потеря порядка.
В терминологии стандарта IEEE последняя ситуация называется антипереполнением.
Возникновение особых случаев может привести к останову программы (если эти ситуации не являются замаскированными, то есть прерывания по ним разрешены).
СМ ЭВМ (РДР-11, VAX-11)
КФ 31 30