РЕФЕРАТЫ И ШПАРГАЛКИ

ОСНОВЫ МАШИННОЙ АРИФМЕТИКИ

Системы счисления и способы перевода чисел из одной системы в другую.

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

В зависимости от способа изображения чисел с помощью цифр системы счисления делятся на “позиционные” и “непозиционные”.

В “непозиционных” системах любое число определяется как некоторая функция от численных значений совокупности цифр, представляющих это число. Цифры в непозиционных системах счисления соответствуют некоторым фиксированным числам. Пример непозиционной системы - римская система счисления. В вычислительной технике непозиционные системы не применяются.

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

В позиционной системе счисления любое число записывается в виде последовательности цифр:

A =  7+ 0 a 4m-1 0 a 4m-2 0 ... a 4k 0 ... a 40 0 , a 4-1 0 ... a 4-l 0 (I)

Позиции, пронумерованные индексами k (-l < k < m-1) называются разрядами числа. Сумма m+l соответствует количеству разрядов числа (m - число разрядов целой части числа, l - дробной части).

Каждая цифра a 4k 0 в записываемой последовательности может принимать одно из N возможных значений. Количество различных цифр (N), используемых для изображения чисел в позиционной системе счисления, называется основанием системы счисления. Основание N указывает, во сколько раз единица k+1 -го разряда больше единицы k -го разряда, а цифра a 4k 0 соответствует количеству единиц k –го разряда, содержащихся в числе.

Таким образом, число может быть представлено в виде суммы:

(A) 4N 0 =  7+ 0(a 4m-1 0N 5m-1 0 + a 4m-2 0N 5m-2 0 +...+ a 40 0 + a 4-1 0N 5-1 0 +...+ a 4-l 0N 5-l 0) (II)

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

В двоичной системе счисления используются только две цифры: 0 и 1. Любое двоичное число может быть представлено в следующей форме:

(A) 42 0 =  7+ 0(a 4m-1 02 5m-1 0 + a 4m-2 02 5m-2 0 + ... + a 40 0 + a 4-1 02 5-1 0 + ... + a 4-l 02 5-l 0)

Например, двоичное число (10101,101) 42 0 = 1*2 54 0+0*2 53 0+1*2 52 0+0*2+1+1*2 5-1 0+0*2 5-2 0+1*2 5-3 0 = (21,625) 410

В восьмеричной системе счисления для записи чисел используется восемь цифр (0,1,2,3,4,5,6,7), а в шестнадцатеричной - шестнадцать (0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F).

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

Двоичные числа ¦ Восьмеричные числа ¦ Десятичные числа ¦ Шестнадцатеричные числа

0,0001 ¦ 0,04 ¦ 0,0625 ¦ 0,1

0,001 ¦ 0,1 ¦ 0,125 ¦ 0,2

0,01 ¦ 0,2 ¦ 0,25 ¦ 0,4

0,1 ¦ 0,4 ¦ 0,5 ¦ 0.8

1 ¦ 1 ¦ 1 ¦ 1

10 ¦ 2 ¦ 2 ¦ 2

11 ¦ 3 ¦ 3 ¦ 3

100 ¦ 4 ¦ 4 ¦ 4

101 ¦ 5 ¦ 5 ¦ 5

110 ¦ 6 ¦ 6 ¦ 6

111 ¦ 7 ¦ 7 ¦ 7

1000 ¦ 10 ¦ 8 ¦ 8

1001 ¦ 11 ¦ 9 ¦ 9

1010 ¦ 12 ¦ 10 ¦ A

1011 ¦ 13 ¦ 11 ¦ B

1100 ¦ 14 ¦ 12 ¦ C

1101 ¦ 15 ¦ 13 ¦ D

1110 ¦ 16 ¦ 14 ¦ E

1111 ¦ 17 ¦ 15 ¦ F

10000 ¦ 20 ¦ 16 ¦ 10

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

В двоичной системе очень просто выполняются арифметические и логические операции над числами.

Таблица сложения:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 10

Таблица умножения:

0 * 0 = 0

0 * 1 = 0

1 * 0 = 0

1 * 1 = 1

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

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

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

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

Пример перевода числа 30,6 из десятичной системы в двоичную:

Перевод целой части Перевод дробной части

Последовательное Остатки Целые части - Последовательное

деление разряды переведенной дроби умножение

0, 6

X

2

30 / 2 0 ------¬ -------------------

15 / 2 1 -----¬¦ ----- 1, 2

7 / 2 1 ----¬¦¦ ¦ X

3 / 2 1 ---¬¦¦¦ ¦ 2

1 / 2 1 --¬¦¦¦¦ ¦ -------------------

0 ¦¦¦¦¦ ¦---- 0, 4

¦¦¦¦¦ ¦¦ X

¦¦¦¦¦ ¦¦ 2

¦¦¦¦¦ ¦¦ -------------------

¦¦¦¦¦ ¦¦--- 0, 8

¦¦¦¦¦ ¦¦¦ X

¦¦¦¦¦ ¦¦¦ 2

¦¦¦¦¦ ¦¦¦ -------------------

¦¦¦¦¦ ¦¦¦-- 1, 6

¦¦¦¦¦ ¦¦¦¦

Результат: 11110,1001

Если при переводе дробной части получается периодическая

дробь, то производят округление, руководствуясь заданной точ-

ностью вычислений.

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

 1Перевод целой части Перевод дробной части

0, 0100

X

1010

_111110| _1010 . -------------------

 _1010  . |110 --------¬ ------ 10, 1000

1011 ¦ ¦ X

 _1010 . ¦ ¦ 1010

10 ------------+¬ ¦ -------------------

¦¦ ¦---- 101, 0000

¦¦ ¦¦

Результат: 62,25

- 5 -

Примечание 1: 1010 - основание десятичной системы счисления

в двоичной записи.

Примечание 2: десятичные эквиваленты разрядов искомого числа

находим по таблице.

При переводе чисел из любой системы счисления в десятичную

удобнее пользоваться непосредственно формулой (II):

(775) 48 0 = 7*8 52 0 + 7*8 + 5 = (509) 410

Для осуществления автоматического перевода десятичных чисел

в двоичную систему счисления необходимо вначале каким-то образом

ввести их в машину, Для этой цели обычно используется двоично-де-

сятичная запись чисел или представление этих чисел в кодах ASCII.

При двоично-десятичной записи каждая цифра десятичного числа

заменяется четырехзначным двоичным числом (тетрадой):

(983,65) 410 0 = (1001 1000 0011, 0110 0101) 42-10

При записи чисел в кодах ASCII цифрам от 0 до 9 поставлены

в соответствие восьмиразрядные двоичные коды от 00110000 до

00111001.

ЭВМ, предназначенные для обработки экономической информации,

например IBM AT, позволяют производить арифметические операции в

десятичной системе счисления над числами, представленными в дво-

ично-десятичных кодах и кодах ASCII.

Шестнадцатеричная и восьмеричная системы счисления использу-

ются только программистами и операторами ЭВМ, так как представле-

ние чисел в этих системах более компактное, чем в двоичной, и пе-

ревод из этих систем в двоичную и обратно выполняется очень прос-

то (основания этих систем представляют собой целую степень числа

2).

Для перевода восьмеричного числа в двоичное достаточно каж-

дый восьмеричный разряд представить тремя двоичными (триадой), а

для перевода шестнадцатиричного числа - четырьмя (тетрадой):

(376,51) 48 0 = (011 111 110, 101 001) 42

(1AF8) 416 0 = (0001 1010 1111 1000) 42

ПЕРВЫЙ СЕМЕСТР

ЛЕКЦИЯ N 2

 2ОСНОВЫ МАШИННОЙ АРИФМЕТИКИ

 2Формы представления чисел в ЭВМ.

Разряд двоичного числа представляется в ЭВМ некоторым техни-

ческим устройством, например, триггером, двум различным состояни-

ям которого приписываются значения 0 и 1. Группа таких устройств,

предназначенная для представления в машине многоразрядного числа,

называется регистром.

Структура двоичного регистра, представляющего в машине

n-разрядное слово:

----T---T---T---T---¬

¦n-1¦n-2¦...¦ 1 ¦ 0 ¦

L---+---+---+---+----

Отдельные запоминающие элементы пронумерованы от 0 до n-1.

Количество разрядов регистра определяет точность представления

чисел. Путем соответствующего увеличения числа разрядов регистра

может быть получена любая точность вычислений, однако это сопря-

жено с увеличением количества аппаратуры (в лучшем случае зависи-

мость линейная, в худшем - квадратичная).

В ЭВМ применяются две основные формы представления чисел:

полулогарифмическая с плавающей запятой и естественная с фиксиро-

ванным положением запятой.

При представлении чисел с фиксированной запятой положение

запятой закрепляется в определенном месте относительно разрядов

числа и сохраняется неизменным для всех чисел, изображаемых в

данной разрядной сетке. Обычно запятая фиксируется перед старшим

разрядом или после младшего. В первом случае в разрядной сетке

могут быть представлены только числа, которые по модулю меньше 1,

во втором - только целые числа.

Для кодирования знака числа используется старший ("знако-

вый") разряд.

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

бями могут получаться двоичные числа, по абсолютной величине

больше или равные единице, что называется 1 переполнением разрядной

 1сетки. 0 Для исключения возможности переполнения приходится масшта-

бировать величины, участвующие в вычислениях.

Диапазон представления правильных двоичных дробей:

2 5-(n-1) 0  7, 0 ¦(A)¦ 7 , 0 1 - 2 5-(n-1) 0 .

.

- 2 -

Числа, которые по абсолютной величине меньше единицы младше-

го разряда разрядной сетки, называются  2машинным нулем 0.

Диапазон представления целых двоичных чисел со знаком в

n-разрядной сетке:

0  7, 0 ¦(A)¦ 7 , 0 2 5n-1 0 - 1 .

Использование представления чисел с фиксированной запятой

позволяет упростить схемы машины, повысить ее быстродействие, но

представляет определенные трудности при программировании. В нас-

тоящее время представление чисел с фиксированной запятой исполь-

зуется как основное только в микроконтроллерах.

В универсальных ЭВМ основным является представление чисел с

плавающей запятой. Представление числа с плавающей запятой в об-

щем случае имеет вид:

A =  7+ 0m * N 5+p 0 ,

где N - основание системы счисления,

p - целое число, называемое порядком числа A,

m - мантисса числа A (¦m¦<1).

Так как в ЭВМ применяется двоичная система счисления, то

A =  7+ 0m * 2 5+p 0 ,.

причем порядок и мантисса представлены в двоичной форме.

Двоичное число называется нормализованным, если его мантисса

удовлетворяет неравенству

1/2  7, 0 ¦ m ¦ 7  0< 1 .

Неравенство показывает, что двоичное число является нормали-

зованным, если в старшем разряде мантиссы стоит единица. Напри-

мер, число 0,110100*10 5100 0 - нормализованное, а 0,001101*10 5110 0 -

ненормализованное.

Ситуация, когда в процессе вычислений получено число с ¦m¦ 7. 01

называется переполнением разрядной сетки.

Нормализованное представление чисел позволяет сохранить в

разрядной сетке большее количество значащих цифр и, следователь-

но, повышает точность вычислений. Однако современные ЭВМ позволя-

ют, при необходимости, выполнять операции также и над ненормали-

зованными числами.

.

- 3 -

Диапазон представления нормализованных двоичных чисел, взя-

тых по абсолютному значению, удовлетворяет неравенству:

2 5-1  0* 5  02 5-(2k-1) 7 , 0 ¦(A)¦  7, 0 (1 5  0- 5  02 5-l 0) 5  0* 5  02 52k-1 0 ,

где l - число разрядов мантиссы;

k - число разрядов порядка;

2 5-1 0 - наименьшее значение нормализованной мантиссы;

1-2 5-l 0 - наибольшее значение нормализованной мантиссы.

Широкий диапазон представления чисел с плавающей запятой

удобен для научных и инженерных расчетов. Для повышения точности

вычислений во многих ЭВМ предусмотрена возможность использования

формата двойной длины, однако при этом происходит увеличение зат-

рат памяти на хранение данных и замедляются вычисления.

 2Представление отрицательных чисел в ЭВМ.

Для кодирования знака двоичного числа используется старший

("знаковый") разряд (ноль соответствует плюсу, единица - минусу).

Такая форма представления числа называется  2прямым кодом 0.

Формула для образования прямого кода правильной дроби имеет вид:

 7(

 72 0 A, если A 7. 00,

[A] 4пр 0 = 7 *

 72 0 1-A, если A<0.

 79

Примеры:

A = 0,110111 --> [A] 4пр 0 = 0,110111

A = -0,110111 --> [A] 4пр 0 = 1 - (-0,110111) = 1,110111

Прямой код целого числа получается по формуле:

 7(

 72 0  5  0 A, если A 7. 00,

[A] 4пр 0 = 7 *

 72 010 5n-1  0- 5  0A, если A<0.

 79

где 10 - число 2 в двоичной системе счисления,

n - количество позиций в разрядной сетке.

Например, при n=8

A = 110111 --> [A] 4пр 0 = 00110111

A = -110111 --> [A] 4пр 0 = 10000000 - (-110111) = 10110111

В ЭВМ прямой код применяется только для представления поло-

жительных двоичных чисел. Для представления отрицательных чисел.

применяется либо дополнительный, либо обратный код, так как над

- 4 -

отрицательными числами в прямом коде неудобно выполнять арифмети-

ческие операции.

Формула для образования дополнительного кода 4  0дроби:

[A] 4доп 0 = 10 + A.

Формула для образования обратного кода 4  0дроби:

[A] 4обр 0 = 10 - 10 5-(n-1) 0 + A.

Например, при n = 8, для A = -0,1100001

[A] 4доп 0 = 10 + (-0,1100001) = 1,0011111

[A] 4обр 0 = 10-10 5-7 0+(-0,1100001) = 1,1111111-0,1100001 = 1,0011110.

Формула для образования дополнительного кода 4  0целого числа:

[A] 4доп 0 = 10 5n 0 + A.

Формула для образования обратного кода 4  0целого числа:

[A] 4обр 0 = 10 5n 0 - 1 + A.

Например, при n = 8, для A = -1100001

[A] 4доп 0 = 100000000 + (-1100001) = 10011111

[A] 4обр 0 = 100000000-1+(-1100001) = 11111111-1100001 = 10011110.

Таким образом, правила для образования дополнительного и об-

ратного кода состоят в следующем:

- для образования дополнительного кода отрицательного числа

необходимо в знаковом разряде поставить единицу, а все цифровые

разряды инвертировать (заменить 1 на 0, а 0 - на 1), после чего

прибавить 1 к младшему разряду;

- для образования обратного кода отрицательного числа необ-

ходимо в знаковом разряде поставить единицу, а все цифровые раз-

ряды инвертировать.

Примечание: при данных преобразованиях нужно учитывать раз-

мер разрядной сетки.

Прямой код можно получить из дополнительного и обратного по

тем же правилам, которые служат для нахождения дополнительного и

обратного кодов.

Замена вычитания двоичных чисел A 41  0- 4  0A 42 0 сложением с дополне-

ниями [A 41 0] 4пр  0+ 4  0[-A 42 0] 4доп 0 или [A 41 0] 4пр  0+ 4  0[-A 42 0] 4обр 0 позволяет опериро-

вать со знаковыми разрядами так же, как и с цифровыми. При этом

перенос из старшего знакового разряда, если он возникает, учиты-

вается по разному для обратного и дополнительного кодов:

- при использовании дополнительного кода единица переноса из

- 5 -

знакового разряда отбрасывается;

- при использовании обратного кода единица переноса из зна-

кового разряда прибавляется к младшему разряду суммы (осуществля-

ется так называемый циклический перенос).

Пример: складываем числа A 41 0=0,10010001 и A 42 0=-0,01100110

При использовании обратного кода получим:

[A 41 0] 4пр  0 = 0,10010001

+

[A 42 0] 4обр 0 = 1,10011001

-----------

10,00101010

L------- +1

-----------

Результат: 0,00101011

При использовании дополнительного кода получим:

[A 41 0] 4пр  0 = 0,10010001

+

[A 42 0] 4доп 0 = 1,10011010

-----------

Результат: 0,00101011

Если знаковый разряд результата равен нулю, то в получено

положительное число, которое представлено в прямом коде. Если в

знаковом разряде единица, то результат отрицательный и представ-

лен в обратном или дополнительном коде.

Для того, чтобы избежать ошибок при выполнении бинарных опе-

раций, перед переводом чисел в обратные и дополнительные коды не-

обходимо выравнивать количество разрядов прямого кода операндов.

При сложении чисел, меньших единицы, в машине быть получены

числа, по абсолютной величине большие единицы. Для обнаружения

переполнения разрядной сетки в ЭВМ применяются 2 модифицированные

прямой, обратный и дополнительный коды. В этих кодах знак кодиру-

ется двумя разрядами, причем знаку "плюс" соответствует комбина-

ция 00, а знаку "минус" - комбинация 11.

Правила сложения для модифицированных кодов те же, что и для

обычных. Единица переноса из старшего знакового разряда в модифи-

цированном дополнительном коде отбрасывается, а в модифицирован-

ном обратном коде передается в младший цифровой разряд.

Признаком переполнения служит появление в знаковом разряде

суммы комбинации 01 при сложении положительных чисел (положитель-

ное переполнение) или 10 при сложении отрицательных чисел (отри-

цательное переполнение). Старший знаковый разряд в этих случаях

- 6 -

содержит истинное значение знака суммы, а младший является стар-

шей значащей цифрой числа. Для коррекции переполнения число нужно

сдвинуть в разрядной сетке на один разряд вправо, а в освободив-

шийся старший знаковый разряд поместить цифру, равную новому зна-

чению младшего знакового разряда. После корректировки переполне-

ния мантиссы результата необходимо увеличить на единицу порядок

результата.

ПЕРВЫЙ СЕМЕСТР

ЛЕКЦИЯ N 3

 2ОСНОВЫ МАШИННОЙ АРИФМЕТИКИ

 2Формы представления чисел в ЭВМ 0

 2(продолжение)

Система вещественных чисел, применяемая при ручных вычисле-

ниях, предполагается бесконечной и непрерывной, т.е. не существу-

ет никаких ограничений на диапазон используемых чисел и точность

их представления.

Однако в компьютерах реализация такой системы на аппаратном

уровне была бы нецелесообразной, хотя программно может быть реа-

лизована любая точность вычислений. Нецелесообразность аппаратной

реализации вычислений с произвольной точностью вызвана тем, что

такие вычисления требуют неоправданно большого расхода основных

машинных ресурсов: памяти и процессорного времени.

Во всех компьютерах размеры регистров и ячеек памяти фикси-

рованы, что ограничивает систему представления чисел. Ограничения

касаются как диапазона, так и точности представления чисел, т.е.

система машинных чисел оказывается конечной и дискретной.

В любой универсальной ЭВМ существует несколько различных

форматов представления как для чисел с фиксированной, так и для

чисел с плавающей запятой. На некоторые из форматов имеются меж-

дународные стандарты, и поэтому такие форматы являются общими для

ЭВМ, построенных различными фирмами на различной элементной базе.

Следует отметить, что нестандартные форматы обычно являются неяв-

но специализированными для определенных областей применения, при-

чем разработчики аппаратуры могут не указать в документации, для

чего был предназначен тот или иной формат.

С точки зрения программиста важно, какие из форматов данных

обрабатываются аппаратными средствами данной ЭВМ, а какие - толь-

ко программными средствами. Операции над данными любого формата,

который не поддерживается аппаратурой, выполняются очень медлен-

но. Любой формат данных, который превышает размер регистров про-

цессора, не пригоден для быстрых вычислений.

Для представления  2целых чисел 0 в ЭВМ обычно применяются 8-,

16-, 32- и 64-битовый стандартные форматы, причем интерпретация

чисел как знаковых или беззнаковых обычно возлагается на програм-

миста или на компиллятор с языка высокого уровня.

.

- 2 -

Для представления 2 чисел с плавающей запятой 0 также существует

несколько стандартных форматов, различающихся по точности, но

имеющих одинаковую структуру следующего вида:

n-1 n-2 0

----T---T---T-----T---T---T---T-----T---¬

¦ ¦ ¦ ¦ ... ¦ ¦ ¦ ¦ ... ¦ ¦

L---¦---+---+-----+---¦---+---+-----+----

¦ L--------T---------L--------T--------

¦ смещенный модуль

знак порядок мантиссы

мантиссы

Порядок p задается в так называемой смещенной форме: если

для задания порядка выделено k разрядов, то к истинному значению

порядка прибавляют смещение, равное (2 5k-1 0 - 1). Использование

смещенной формы позволяет производить операции над порядками, как

над беззнаковыми числами, что упрощает операции сравнения, сложе-

ния и вычитания порядков. Кроме того, использование смещенного

порядка упрощает операцию сравнения нормализованных чисел с пла-

вающей запятой, сводя ее к операции сравнения целых чисел.

Следует отметить, что вещественный формат с m-разрядной ман-

тиссой позволяет абсолютно точно представлять m-разрядные целые

числа, т.е. любое двоичное целое число, содержащее не более m

разрядов, может быть без искажений преобразовано в вещественный

формат.

 2Форматы представления чисел в ПЭВМ IBM AT

Рассмотрим стандартные и нестандартные форматы, используемые

для представления чисел в ПЭВМ IBM AT.

В дальнейшем будем использовать на диаграммах следующие

обозначения:

S - знаковый разряд;

E - поле порядка;

M - поле мантиссы;

X - неиспользуемая область;

D - цифра упакованного десятичного целого числа, представ-

ленная в двоично-десятичном коде.

Примечание: основной процессор эффективен только при опера-

циях с целыми числами, разрядность которых не превышает разряд-

ности его внутренних регистров; в остальных случаях более эффек-

тивен математический сопроцессор.

.

- 3 -

 1Форматы представления 0  1двоичных целых чисел

1) 8-разрядное целое число без знака (поддерживается всеми

процессорами серии 80x86)

7 0

----------------¬

¦ ¦

L----------------

2) 7-разрядное целое число со знаком (поддерживается всеми

процессорами серии 80x86)

7 6 0

--T-------------¬

¦S¦ ¦

L-+--------------

3) 16-разрядное целое число без знака (поддерживается всеми

процессорами серии 80x86)

15 0

--------------------------------¬

¦ ¦

L---------------+----------------

4) Word Integer (целое слово) - 15-разрядное целое число со

знаком (поддерживается всеми процессорами серии 80x86 и математи-

ческим сопроцессором)

15 0

--T-----------------------------¬

¦S¦ ¦

L-+-------------+----------------

5) 32-разрядное целое число без знака (поддерживается всеми

процессорами серии 80x86, но операции с этим форматом выполняются

эффективно только 32-разрядными микропроцессорами, т.е. начиная с

i386SX)

31 0

----------------------------------------------------------------¬

¦ ¦

L---------------+---------------+---------------+----------------

6) Short Integer (короткое целое) - 31-разрядное целое число

со знаком (поддерживается всеми процессорами серии 80x86 и мате-

матическим сопроцессором, но операции с этим форматом выполняются

эффективно только 32-разрядными микропроцессорами)

.

- 4 -

31 0

--T-------------------------------------------------------------¬

¦S¦ ¦

L-+-------------+---------------+---------------+----------------

7) 64-разрядное целое число без знака (частично поддержива-

ется 32-разрядными микропроцессорами)

64 0

----------------------------------------------------------------¬

¦ ¦

L-------+-------+-------+-------+-------+-------+-------+--------

8) Long Integer (длинное целое) - 63-разрядное целое число

со знаком (поддерживается математическим сопроцессором и частично

поддерживается 32-разрядными микропроцессорами)

64 0

--T-------------------------------------------------------------¬

¦S¦ ¦

L-+-----+-------+-------+-------+-------+-------+-------+--------

 1Форматы представления 0  1десятичных целых чисел

1) Неупакованное 1-разрядное десятичное целое число без зна-

ка в двоично-десятичном коде (поддерживается всеми процессорами

серии 80x86)

7 4 3 0

--------T-------¬

¦0 0 0 0¦ D ¦

L-------+--------

2) 1-разрядное десятичное целое число без знака в коде ASCII

(поддерживается всеми процессорами серии 80x86)

7 4 3 0

--------T-------¬

¦0 0 1 1¦ D ¦

L-------+--------

3) Packed Decimal - упакованное 2-разрядное десятичное целое

без знака (поддерживается всеми процессорами серии 80x86)

7 4 3 0

--------T-------¬

¦ D 41 0 ¦ D 40 0 ¦

L-------+--------

4) Packed Binary Coded Decimal - упакованное 18-разрядное

десятичное целое число со знаком (поддерживается математическим

сопроцессором)

- 5 -

79 0

--T----T-----------------------------------------------------¬

¦S¦ X ¦D 417 0D 416 0 ... D 41 0 D 40 0¦

L-+----+-----+-----+-----+-----+-----+-----+-----+-----+------

 1Форматы представления вещественных чисел

1) Single Format (обычный формат)  1  0или  1  0Short Real (короткое

вещественное) - короткое вещественное нормализованное число со

знаком, 8-разрядным смещенным порядком и 24-разрядной мантиссой

(так как старший бит мантиссы нормализованного числа всегда равен

1, то он не хранится в памяти, и размер поля, выделенного для

хранения мантиссы, составляет только 23 разряда).

31 30 23 22 0

--T---------------T---------------------------------------------¬

¦S¦ E ¦ M ¦

L-+-------------+-+-------------+---------------+----------------

2) Double Format(двойной формат) или Long Real (длинное ве-

щественное) - длинное вещественное нормализованное число со

знаком, 11-разрядным смещенным порядком и 53-разрядной мантиссой

(так как старший бит мантиссы нормализованного числа всегда равен

1, то он не хранится в памяти, и размер поля, выделенного для

хранения мантиссы, составляет только 52 разряда).

63 62 52 51 0

--T---------T---------------------------------------------------¬

¦S¦ E ¦ M ¦

L-+-----+---+---+-------+-------+-------+-------+-------+--------

3) Extended Format (расширенный формат) или  1  0Single Extended

(обычный расширенный формат) - вещественное число в расширенном

формате со знаком, 15-разрядным смещенным порядком и 64-разрядной

мантиссой. Этот формат позволяет хранить ненормализованные числа

и соответствует стандарту IEEE 754.

79 78 64 63 0

--T---------T-----------------------------------------------¬

¦S¦ E ¦ M ¦

L-+---+-----+-----+-----+-----+-----+-----+-----+-----+------

ПЕРВЫЙ СЕМЕСТР

ЛЕКЦИЯ N 4

 2ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ УЗЛОВ ЭВМ

 2Физические формы представления информации

Вся информация в ЭВМ кодируется совокупностью цифр. В свою

очередь цифры отображаются квантованными по двум уровням сигнала-

ми.

Следует отметить, что в цифровых устройствах сигналы изменя-

ются не непрерывно, а в дискретные моменты времени, обозначаемые

целыми числами (t = 0, 1, ... n). Временной интервал между сосед-

ними моментами дискретного времени называется 2 тактом 0. Эти интер-

валы являются одинаковыми для синхронных устройств и неодинаковы-

ми для асинхронных устройств.

На физическом уровне сигналы могут быть представлены одним

из трех основных способов: потенциальным, импульсным или динами-

ческим.

При  2потенциальном 0 способе 0 соответствует низкий уровень

напряжения, а 1 - высокий. Потенциальный сигнал характеризуется

амплитудами низкого (U 40 0) и высокого (U 41 0) уровней напряжения, а

также временами нарастания и спада сигнала, которые именуются пе-

редним (t 4п 0) и задним (t 4з 0) фронтами соответственно.

При  2импульсном 0 способе 0 и 1 соответствуют импульсы различ-

ной полярности, либо 0 соответствует отсутствие, а 1 - наличие

импульса. Импульсный сигнал характеризуется амплитудой импульса

U 4m 0, шириной (продолжительностью импульса по основанию) t 4и 0, и пе-

редним t 4п 0 и задним t 4з 0 фронтами импульса. В идеальном случае им-

пульсные сигналы должны появляться в тактовые моменты. В действи-

тельности имеет место запаздывание импульсного сигнала относи-

тельно тактового момента на время 7 t 0.

При 2 динамическом 0 способе представления информации двум воз-

можным значениям переменной соответствует наличие либо отсутствие

серии импульсов.

В электронных схемах и устройствах, входящих в состав ЭВМ,

применяется потенциальный способ представления информации, а для

передачи информации между ЭВМ, а также при работе с магнитными

носителями информации применяются импульсный и динамический спо-

собы.

 2Математические модели схем ЭВМ

Наиболее общей моделью любой схемы, узла или устройства ЭВМ

является многополюсный черный ящик с  2l 0 входами и  2m 0 выходами. На

входы модели поступают, а на выходах появляются сигналы, кванто-

ванные по двум уровням.

.

- 2 -

-----------¬

x 41 0 -----+ +----- y 41

x 42 0 -----+ +----- y 42

. ¦ Черный ¦ .

. ¦ ящик ¦ .

. ¦ ¦ .

x 4l 0 -----+ +----- y 4m

L-----------

где x 4i 0 (i = 1, 2, ..., l) - входные сигналы,

y 4j 0 (j = 1, 2, ..., m) - выходные сигналы.

Множество значений, которые может принимать переменная x 4i 0,

называют 2 алфавитом 0 переменной x 4i 0. В современных ЭВМ алфавит вход-

ных и выходных сигналов состоит из двух букв: 0 и 1.

На входы модели поступают в каждый тактовый момент упорядо-

ченные наборы букв, называемые 2 словами 0. Множество всех допустимых

наборов слов называется  2входным алфавитом 0 X данной схемы. Анало-

гично множество всех допустимых комбинаций, образуемых выходными

сигналами, называется  2выходным алфавитом 0 Y.

Математические модели отражают зависимость между входными и

выходными переменными схемы посредством системы уравнений:

y 4j 0(t) = f{x 41 0(t),x 42 0(t)...,x 4l 0(t), q 41 0(t),q 42 0(t),,...,q 4s 0(t)} (I)

где j = 1,2,...,m, а переменные q 41 0,q 42 0,...,q 4s 0 отражают внутренние

состояния схемы.

Если переменные y 4i 0 не зависят от внутреннего состояния схе-

мы, то одинаковым наборам входных переменных соответствует один и

тот же набор выходных переменных. Такие схемы называются  2комбина-

 2ционными 0.

При этом система уравнений может быть записана в виде:

y 4j 0(t) = f{x 41 0(t),x 42 0(t)...,x 4l 0(t)}, где j = 1,2,...,m. (II)

Функции такого вида могут принимать только конечное число

значений, и зависят от аргументов, также принимающих конечное

число значений. Такие функции называются 2 переключательными 0.

В дальнейшем мы будем рассматривать переключательные функ-

ции, которые могут принимать только два значения - 0 и 1, и аргу-

менты которых также могут принимать только одно из этих двух зна-

чений. Такие переключательные функции получили название 2 булевых

 2функций 0.

Если выходные переменные y 4i 0(t) зависят не только от входных

переменных, но и от внутреннего состояния схемы, то для полного

ее описания необходимо указать еще одну систему уравнений:

- 3 -

q 4n 0(t+1) =  7f 0{x 41 0(t),x 42 0(t)...,x 4l 0(t), q 41 0(t),q 42 0(t),,...,q 4s 0(t)}, (III)

где n = 1,2,...,s.

Эта система отражает зависимость внутреннего состояния схемы

в (t+1) такте от ее состояния и входных сигналов в такте t.

Схемы, описываемые уравнениями I и III, получили название

 2цифровых автоматов 0.

Для задания цифрового автомата должны быть указаны:

1) входной алфавит слов X;

2) выходной алфавит слов Y;

3) алфавит внутренних состояний Q;

4) начальное состояние автомата q 40 0;

5) функция переходов A(q,x);

6) функция выходов B(q,x).

 2Функция переходов 0 определяет зависимость состояния автомата

q(t+1) в момент времени t+1 от состояния автомата q(t) и входного

сигнала x(t) в момент t.

 2Функция выходов 0 определяет зависимость выходного сигнала

y(t) от состояния автомата q(t) и входного сигнала x(t).

Автомат, описываемый системой уравнений

 7(

 72 0 q(t+1) = A{q(t),x(t)},

 7*

 72 0 y(t) = B{q(t),x(t)}

 79

называется  2автоматом Мили 0.

Автомат, выходной сигнал которого y(t) в тактовый момент t

зависит только от состояния автомата q(t) и не зависит от входно-

го сигнала, называется 2 автоматом Мура 0 и описывается системой:

 7(

 72 0 q(t+1) = A{q(t),x(t)},

 7*

 72 0 y(t) = B{q(t)}.

 79

ПЕРВЫЙ СЕМЕСТР

ЛЕКЦИЯ N 5

 2ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ УЗЛОВ ЭВМ

Если для двух любых состояний q 4i 0 и q 4j 0 автомата имеется вход-

ной сигнал, переводящий автомат из состояния q 4i 0 в q 4j 0, то такой

автомат называется автоматом с  2полной системой переходов 0. Автомат

Мура имеет  2полную систему выходов 0, если выходные сигналы различны

для всех его состояний.

При построении схем ЭВМ в качестве элементов памяти исполь-

зуются элементарные автоматы.  2Элементарный автомат 0 - это автомат

Мура с двумя внутренними состояниями, двумя различными выходными

сигналами и несколькими входами, обладающий полными системами пе-

реходов и выходов.

 2ТЕОРИЯ БУЛЕВЫХ ФУНКЦИЙ

Булевыми функциями называют переключательные функции, кото-

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

0 и 1.

Булевы функции могут быть заданы в виде формул или таблиц.

Формулы позволяют представлять функции в более компактном виде,

чем таблицы, так как таблица для функции от n аргументов будет

содержать 2 5n 0 строк (или столбцов, в зависимости от формы табли-

цы). С другой стороны, таблицы дают наглядное представление для

простых функций.

Приведем в качестве примера наиболее часто встречающиеся

функции от одной и двух переменных:

1) Переменная x:

f(x) = x

2) Инверсия переменной x (функция НЕ):

 4_

f(x) = x

3) Константа нуля:

f(x) = 0

4) Константа единицы:

f(x) = 1

.

- 2 -

5) Дизъюнкция (функция ИЛИ):

f(x 41 0,x 42 0) = x 41 0 V x 42

Может встречаться другое обозначение: f(x 41 0,x 42 0) = x 41 0 | x 42 0.

Таблица истинности (соответствия) для этой функции имеет вид:

------T-----T---------¬

¦ x 41 0 ¦ x 42 0 ¦ x 41 0 V x 42 0 ¦

+-----+-----+---------+

¦ 0 ¦ 0 ¦ 0 ¦

¦ 0 ¦ 1 ¦ 1 ¦

¦ 1 ¦ 0 ¦ 1 ¦

¦ 1 ¦ 1 ¦ 1 ¦

L-----+-----+----------

6) Конъюнкция (функция И):

f(x 41 0,x 42 0) = x 41 0  5. 0 x 42

Может встречаться другое обозначение: f(x 41 0,x 42 0) = x 41 0 & x 42 0.

Таблица истинности для этой функции имеет вид:

------T-----T---------¬

¦ x 41 0 ¦ x 42 0 ¦ x 41 0  5. 0 x 42 0 ¦

+-----+-----+---------+

¦ 0 ¦ 0 ¦ 0 ¦

¦ 0 ¦ 1 ¦ 0 ¦

¦ 1 ¦ 0 ¦ 0 ¦

¦ 1 ¦ 1 ¦ 1 ¦

L-----+-----+----------

7) Функция ИЛИ-НЕ:

 4_______

f(x 41 0,x 42 0) = x 41 0 V x 42

Таблица истинности для этой функции имеет вид:

------T-----T---------¬

¦ x 41 0 ¦ x 42 0 ¦ x 41 0 V x 42 0 ¦

+-----+-----+---------+

¦ 0 ¦ 0 ¦ 1 ¦

¦ 0 ¦ 1 ¦ 0 ¦

¦ 1 ¦ 0 ¦ 0 ¦

¦ 1 ¦ 1 ¦ 0 ¦

L-----+-----+----------

.

- 3 -

8) Функция И-НЕ:

 4_______

f(x 41 0,x 42 0) = x 41 0  5. 0 x 42

Таблица истинности для этой функции имеет вид:

------T-----T---------¬

¦ x 41 0 ¦ x 42 0 ¦ x 41 0 V x 42 0 ¦

+-----+-----+---------+

¦ 0 ¦ 0 ¦ 0 ¦

¦ 0 ¦ 1 ¦ 1 ¦

¦ 1 ¦ 0 ¦ 1 ¦

¦ 1 ¦ 1 ¦ 1 ¦

L-----+-----+----------

9) Функция ИСКЛЮЧАЮЩЕЕ ИЛИ (сумма по модулю 2):

f(x 41 0,x 42 0) = mod2(x 41 0,x 42 0)

Таблица истинности для этой функции имеет вид:

------T-----T-------------¬

¦ x 41 0 ¦ x 42 0 ¦ mod2(x1,x2) ¦

+-----+-----+-------------+

¦ 0 ¦ 0 ¦ 0 ¦

¦ 0 ¦ 1 ¦ 1 ¦

¦ 1 ¦ 0 ¦ 1 ¦

¦ 1 ¦ 1 ¦ 0 ¦

L-----+-----+--------------

 2Аксиомы алгебры логики

В алгебре логики определено отношение эквивалентности (=) и

три операции: дизъюнкция, конъюнкция и отрицание.

Отношение эквивалентности удовлетворяет следующим свойствам:

x=x - рефлексивность; если x=y, то y=x - симметричность; если x=y

и y=z, то x=z - транзитивность. Из отношения эквивалентности сле-

дует 2 принцип подстановки 0: если x=y, то в любой формуле, содержа-

щей x, вместо x можно подставить y, и будет получена эквивалент-

ная формула.

Алгебра логики определяется следующей системой аксиом:

x = 0, если x  7- 0 1 7 )

 78 0 (1)

x = 1, если x  7- 0 0 7 0

1 V 1 = 1 7 )

 78 0 (2)

0 5 . 0 0 = 0 7 0

- 4 -

0 V 0 = 0 7 )

 78 0 (3)

1  5. 0 1 = 1 7 0

0 V 1 = 1 V 0 = 1 7 )

 78 0 (4)

0 5 . 0 1 = 1 5 .  00 = 0 7 0

 4_

0 = 1 7 )

 4_ 0  78 0 (5)

1 = 0 7 0

Аксиома (1) утверждает, что в алгебре логики рассматриваются

только двоичные переменные, аксиомы (2)-(4) определяют операции

конъюнкции и дизъюнкции, а аксиома 5 - операцию отрицания.

Если в аксиомах (2)-(5), заданных парами утверждений, произ-

вести взаимную замену операций дизъюнкции и конъюнкции, а также

элементов 0 и 1, то из одного утверждения пары будет получено

другое. Это свойство называется принципом двойственности.

 2Теоремы алгебры логики

С помощью аксиом алгебры логики можно доказать целый ряд те-

орем и тождеств. Одним из эффективных методов доказательства тео-

рем является 2 метод перебора 0 всех значений переменных: если теоре-

ма истинна, то при подстановке любых значений переменных в обе

части выражения, формулирующего утверждение теоремы, должно полу-

читься тождество.

Методом перебора можно убедиться в справедливости следующих

теорем:

идемпотентные законы

x V x = x 7 )

 78

x  5. 0 x = x 7 0

коммутативные законы

x V y = y V x 7 )

 78

x  5. 0 y = y  5. 0 x 7 0

ассоциативные законы

(x V y) V z = x V (y V z) 7 )

 78

(x  5. 0 y)  5. 0 z = x  5. 0 (y  5. 0 z) 7 0

.

- 5 -

дистрибутивные законы

x  5. 0 (y V z) = x  5. 0 y V x  5. 0 z 7 )

 78

x V y  5. 0 z = (x V y) 5. 0(x V z) 7 0

законы отрицания 4 _

x V x = 1 7 )

 4_ 0  78

x  5. 0 x = 0 7 0

0 V x = x 7 )

 78

1  5. 0 x = x 7 0

1 V x = 1 7 )

 78

0  5. 0 x = 0 7 0

законы двойственности (теоремы де Моргана)

 4_____ _ _

x V y = x  5.  0y 7 )

 4_____ 0  4_ 0  4_ 0  78

x  5. 0 y = x V y 7 0

закон двойного отрицания 4  0  4 _____

 7( 0  4_ 7 )

 72 0 x 7 2 0 = x

 79 0

законы поглощения

x V x  5. 0 y = x 7 )

 78

x 5. 0(x V y) = x 7 0

операции склеивания 4 _

x  5. 0 y V x  5. 0 y = x 7  0  7)

 4_ 0  78

(x V y) 5. 0(x V y) = 7  0x  70

операции обобщенного склеивания

 4_ _

x 5. 0y V x 5. 0z V y 5. 0z = x 5. 0y V x 5. 0z  5  7)

 4_ 0  5  4_ 5  0  78

(x V y) 5. 0(x V z) 5. 0(y V z) = 7  0(x V y) 5. 0(x V z)  70

 4_

x V x  5. 0 y = x V y 7 )

 4_ 0  78

x 5. 0(x V y) = x 7  5. 0 y  70

ПЕРВЫЙ СЕМЕСТР

ЛЕКЦИЯ N 6

 2МЕТОДЫ УПРОЩЕНИЯ (МИНИМИЗАЦИИ) БУЛЕВЫХ ФУНКЦИЙ

Сложные булевы функции могут быть построены из более прос-

тых.

 2Элементарными функциями 0 называются функции, образованные пу-

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

И, только операции ИЛИ и т.д.

Для представления сложных логических функций можно использо-

вать не все элементарные функции, а только ту или иную часть их,

называемую системой. Система элементарных функций f 41 0, ..., f 4k 0 на-

зывается функционально полной, если любую сложную булеву функцию

можно записать в виде формулы через функции f 41 0, ..., f 4k 0.

Так, любую функцию можно представить с помощью одних только

операций И-НЕ или только операций ИЛИ-НЕ.

В цифровых устройствах часто применяется в качестве базовой

система из трех функций: И, ИЛИ и НЕ.

Используя законы алгебры логики, можно упрощать сложные ло-

гические выражения. Упрощение заключается в уменьшении количества

букв и количества отрицаний в выражении, что позволяет упростить

схему устройства с жесткой логикой или программу устройства с

программируемой логикой. Такое упрощение позволяет уменьшить се-

бестоимость и увеличить быстродействие устройства.

Рассмотрим функцию

 4_________

 7(  4_ 7 ) 4 _

f(a,b.c) = a 5. 72 0b V a 5. 0c 72 0 V a 5. 0b

 79 0

Используя законы алгебры логики, можно привести эту функцию

к виду:

 4_  0  5  0  4_  0  4 _  0  4_ __ _  0  4_ _

f(a,b.c) = a 5. 0(b 5. 0(a 5  0V 5  0c)) V a 5. 0b = ab V abc V ab = ab V ab

 4применяем  0  4  0  4 применяем

 4законы де Моргана  0  4 закон поглощения

Одной и той же логической функции может быть поставлено в

соответствие неограниченное количество различных эквивалентных

формул. Наиболее удобными для практического использования являют-

ся так называемые  2нормальные формы 0 представления сложных логичес-

ких функций.

 2Элементарной конъюнкцией 0 Q называется логическое произведе-

ние переменных и их отрицаний, причем каждая переменная должна

встречаться в произведении только один раз.

.

- 2 -

 4_ _

Пример элементарной конъюнкции: Q = x 41 0x 42 0x 43 0x 44 0x 46 0.

Аналогично  2элементарной дизъюнкцией 0 В называется логическая

сумма переменных и их отрицаний, причем каждая переменная должна

встречаться в сумме только один раз.

 4_

Пример элементарной дизъюнкции: D = x 41 0 V x 43 0 V x 44 0.

Формула, эквивалентная заданной и представляющая собой логи-

ческую сумму элементарных конъюнкций, называется  2дизъюнктивной

 2нормальной формой 0 (ДНФ) заданной формулы. Дизъюнктивная нормаль-

ная форма существует для любой логической функции.

Аналогично считается, что логическая функция задана своей

 2конъюнктивной 0  2нормальной формой 0 (КНФ), если она выражена посредс-

твом логического произведения элементарных дизъюнкций. КНФ также

существует для любой логической функции.

Например, для функции  4_________

 7(  4_ 7 ) 4 _

f(a,b.c) = a 5. 72 0b V a 5. 0c 72 0 V a 5. 0b

 79 0

ДНФ будет иметь вид

 4_ _

f(a,b.c) = ab V ab,

КНФ будет иметь вид

 4_ _

f(a,b.c) = (a V b)(b V c).

Одна и та же функция путем эквивалентных преобразований мо-

жет быть представлена различными КНФ и ДНФ. Из всей совокупности

нормальных форм, представляющих данную функцию, выделяют одну КНФ

и одну ДНФ, именуемые совершенными.

 2Минтермом 0 (m) n аргументов называется логическое произведе-

ние этих аргументов, причем каждый аргумент может входить в про-

изведение в прямой или инверсной форме.

Минтермы могут быть пронумерованы, причем номер минтерма оп-

ределяется как десятичный эквивалент двоичного числа, образован-

ного из значений переменных, входящих в данный набор: если пере-

менная входит в прямой форме, то ей соответствует единица, если в

инверсной - ноль.

 2Макстермом 0 (M) n аргументов называется логическая сумма этих

аргументов, причем каждый аргумент может входить в сумму в прямой

или инверсной форме. Номер макстерма задается аналогично номеру

минтерма.

.

- 3 -

Рассмотрим в качестве примера случай двух аргументов:

------T-----T-------------T--------------¬

¦ a ¦ b ¦ минтерм ¦ макстерм ¦

+-----+-----+-------------+--------------+

¦ ¦ ¦  4_ 0  4_ 0 ¦  4_ 0  4_ 0 ¦

¦ 0 ¦ 0 ¦ m 40 0 = a 5. 0b ¦ M 40 0 = a V b ¦

¦ ¦ ¦  4_ 0 ¦  4_ 0 ¦

¦ 0 ¦ 1 ¦ m 41 0 = a 5. 0b ¦ M 41 0 = a V b ¦

¦ ¦ ¦  4_ 0 ¦  4_ 0 ¦

¦ 1 ¦ 0 ¦ m 42 0 = a 5. 0b ¦ M 42 0 = a V b ¦

¦ ¦ ¦  4  0 ¦ ¦

¦ 1 ¦ 1 ¦ m 43 0 = a 5. 0b ¦ M 43 0 = a V b ¦

L-----+-----+-------------+---------------

Минтермы и макстермы можно геометрически представить на кар-

тах (диаграммах) Вейча. Так, для двух переменных карта Вейча бу-

дет представлять собой квадрат, причем левая половина квадрата

определяется переменной a, а верхняя половина квадрата - перемен-

ной b. Это означает, что левая 4_ 0 половина квадрата соответствует

значению переменной a, правая - a, верхняя половина соответствует

 4_

b, нижняя b.

Карта Вейча для двух переменных:

 4_

 2a a

------T-----¬

¦ ¦  4_ 0 ¦

 2b  0¦ a 5. 0b ¦ a 5. 0b ¦

¦ ¦ ¦

+-----+-----+

 4_ 0 ¦  4_ 0 ¦  4_ 0  4_ 0 ¦

 2b  0¦ a 5. 0b ¦ a 5. 0b ¦

¦ ¦ ¦

L-----+------

.

- 4 -

Карта Вейча для 5  0трех переменных:

 4_

 2a a

 5-------+------¬ -------+------¬

--------T-------T-------T-------¬

¦  4_ 0 ¦ ¦  4_ 0 ¦  4_ 0  4_ 0 ¦

 2b  0¦ a 5. 0b 5. 0c ¦ a 5. 0b 5. 0c ¦ a 5. 0b 5. 0c ¦ a 5. 0b 5. 0c ¦

¦ ¦ ¦ ¦ ¦

+-------+-------+-------+-------+

 4_ 0 ¦  4_ 0  4_ 0 ¦  4_ 0 ¦  4_ 0  4_ 0 ¦  4_ 0  4_ 0  4_ 0 ¦

 2b  0¦ a 5. 0b 5. 0c ¦ a 5. 0b 5. 0c ¦ a 5. 0b 5. 0c ¦ a 5. 0b 5. 0c ¦

¦ ¦ ¦ ¦ ¦

L-------+-------+-------+--------

 4_ 0  5L------T------- 4 _

 2c 0  2c c

 2Свойства минтермов и макстермов:

1) Минтерм является инверсией некоторого макстерма и наобо-

рот: 4 _

m 4i 0 = M

2 5n 0-1-i

 4_

M 4i 0 = m

2 5n 0-1-i

 4_

Пример: m 41 0 = 4  0M 42 0 (заштрихованная площадь соответствует макс-

терму, незаштрихованная - минтерму).

 1-TTT 0T 1-- 0-¬

 1+++++ ¦

 1++++ 0L 1TTT 0+

 1+++++++++

 1L+++++++-

2) Логическая сумма всех минтермов для любого заданного чис-

ла переменных равна 1.

2 5n 0-1

V m 4i 0 = 1.

i=0

3) Логическое произведение всех макстермов для любого задан-

ного числа переменных равно 0.

2 5n 0-1

 7L 0 M 4i 0 = 0.

i=0

- 5 -

4) Два неодинаковых минтерма или макстерма имеют хотя бы од-

ну переменную, входящую в один из них в прямой, а в другой - в

инверсной форме, следовательно

m 4i 5. 0m 4j 0 = 0, если i  7- 0 j;

M 4i 0 V M 4j 0 = 1, если i  7- 0 j.

 2Основная теорема алгебры логики 0: любую булеву функцию от n

переменных можно выразить логической суммой минтермов, которая

называется 2 совершенной нормальной дизъюнктивной формой 0, или логи-

ческим произведением макстермов, которое называется 2 совершенной

 2нормальной конъюнктивной формой 0.

Логические функции отражают не только принцип работы некото-

рых частей ЭВМ, но и их состав, если каждой элементарной функции

соответствует реальный физический элемент. Любая сложная логичес-

кая функция может быть реализована некоторой частью ЭВМ, если эта

часть построена с помощью такого набора элементов, который реали-

зует все функции одной из функционально полных систем. Такой на-

бор называется функционально полным набором логических элементов

Поскольку каждая функция может быть представлена в виде раз-

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

на при помощи различных логических схем. Очевидно, что более

простому логическому уравнению соответствует более простая схема.

Упрощение (минимизация) функции сводится к получению ее минималь-

ной дизъюнктивной или конъюнктивной нормальной формы, т.е. такой

формы, при которой функция содержит наименьшее число переменных и

знаков логических операций.

Существует несколько методов минимизации. В дальнейшем мы

рассмотрим метод непосредственных преобразований и метод диаграмм

Вейча.

ПЕРВЫЙ СЕМЕСТР

ЛЕКЦИЯ N 7

 2МЕТОДЫ МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ

 2Метод непосредственных преобразований

Суть данного метода заключается в том, что минимизация ис-

ходной логической функции производится путем применения к отдель-

ным членам или группам членов формулы, выражающей данную логичес-

кую функцию, основных законов алгебры логики с целью получения

минимальной формы функции, т.е. такой, которая не содержит лишних

переменных или членов.

Лишними переменными или членами являются те, которые не вли-

яют на значение преобразуемой формулы.

Пример:

 4_  5  4_

x 41 5. 0x 42 5. 0x 43 0 V x 41 5. 0x 42 5. 0x 43 0 = x 42 5. 0x 43 5. 0(x 41 5  0V 5