Referats

Вычислительные машины


ЛЕКЦИЯ N 1

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

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

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

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

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

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

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

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

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

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.

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

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

[A] 4пр 0 = 7 *

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

Примеры:

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

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

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

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

[A] 4пр 0 = 7 *

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

где 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).

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

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

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

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

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

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

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

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

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

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

ЛЕКЦИЯ 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 (функция НЕ):

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

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 )

x 5. 0 x = x 7 0

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

x V y = y V x 7 )

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

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

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

(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 )

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 )

1 5. 0 x = x 7 0

1 V x = 1 7 )

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 )

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

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 В называется логическая

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

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

Пример элементарной дизъюнкции: 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, верхняя половина соответствует

b, нижняя b.

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

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трех переменных:

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

M 4i 0 = m

2 5n 0-1-i

Пример: 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 0x 41 0) = x 42 5. 0x 43 5. 01 = x 42 5. 0x 43

т.е. в исходной формуле лишней являлась двоичная переменная x 41 0.

Примечание: произведенная операция называется "склеиванием"

членов формулы.

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

обычно проводятся в следующем порядке:

1) Выявляются группы двоичных переменных исходной формулы, к

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

гебры логики, приводящие выражение к более простой форме.

2) Упрощение исходной формулы путем применения к выявленным

группам соответствующих законов.

3) Преобразование промежуточной логической формулы с целью

образования таких групп переменных, к которым можно применить уп-

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

- группирование членов;

- действия по раскрытию скобок и выносу за скобки;

- добавление фиктивных членов, т.е. таких, совокупность ко-

торых тождественно равна нулю;

- логическое умножение одного или нескольких членов на логи-

ческую сумму переменной и ее отрицания.

4) Упрощение преобразованной промежуточной логической форму-

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

ДНФ.

5) Выявление и удаление из полученной предварительной формы

лишних членов, что дает минимальную форму исходной логической

функции.

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

4_ _ _ _

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

- 2 -

(используем метод умножения всех членов формулы на сумму тех пе-

ременных и их отрицаний, которые отсутствуют в данном члене;)

4_ _ _ _ _ _ _ _

= ab(cVc) V bc(aVa) V bc(aVa) V ab(cVc) =

(в результате, отбросив повторяющиеся члены, получаем СДНФ функ-

ции;)

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

= abc V abc V abc V abc V abc V abc V abc V abc =

L-- L=- L-- L=-

4_ __ _ _ _ __ _

= abc V abc V abc V abc V abc V abc =

(перегруппировываем члены с целью их упрощения)

4_ 9 4 _ _ _ _ _

= b 9c 0(aVa) V ab(cVc) V ac(bVb) =

(окончательно получим)

4_ _ _

= bc V ab V ac.

Однако группирование членов после умножения можно провести и

несколько иначе:

4_ _ _ _ _ _ _ _ _

f(a,b,c) = ab(cVc) V bc(aVa) V ac(bVb) = ab V bc V ac.

Следовательно, данная функция имеет две минимальные формы.

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

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

Кроме того, метод в целом весьма трудоемок, результат минимизации

в сильной степени зависит от квалификации и интуиции человека,

проводящего минимизацию. Поэтому данный метод применяется лишь

для минимизации простых логических формул.

2Метод минимизации с помощью карт Вейча

Данный метод наиболее применим в инженерной практике благо-

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

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

(до 8). Преимущество этого метода состоит в том, что нет необхо-

димости приводить функцию к СДНФ.

Рассмотрим изображение на карте Вейча функции

4__ _ _ _ __ _ __ _

f(a,b,c,d) = cd V abd V abc V abcd V abcd V bcd

- 3 -

При нанесении заданной функции на карту никаких предвари-

тельных преобразований не проводится. Каждый дизъюнктивный член

рассматривается в отдельности, и в соответствующие ему квадратики

вписывается 1 (т.е. дизъюнктивный член развертывается до минтер-

мов).

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

ется в следующей последовательности:

----+---¬

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

¦¦ _1 . ¦ ¦ ¦ _1 . ¦ ¦ _1 . ¦ _1 . ¦ ¦ 1 ¦ ¦ 1 ¦ 1 ¦ ¦ _1 . ¦

b ++---+---+---+---+¬ +---+---+---+---+ +---+---+---+---+

¦¦ ¦ ¦ ¦ ¦¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ _1 . ¦

L+---+---+---+---++ d +---+---+---+---+ +---+---+---+---+

¦ ¦ ¦ ¦ ¦¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦

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

¦ _1 . ¦ ¦ ¦ _1 . ¦ ¦ 1 ¦ ¦ ¦ 1 ¦ ¦ 1 ¦ ¦ ¦ 1 ¦

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

L---T----

4__ 0 c 4 0 4 __ _ __ _ _ _

cd cd V abd cd V abd V abc

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

¦ 1 ¦ 1 ¦ ¦ 1 ¦ ¦ 1 ¦ 1 ¦ ¦ 1 ¦ ¦ 1 ¦ 1 ¦ ¦ 1 ¦

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

¦ ¦ ¦ ¦ 1 ¦ ¦ ¦ ¦ ¦ 1 ¦ ¦ ¦ ¦ ¦ 1 ¦

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

¦ ¦ ¦ ¦ ¦ ¦ _1 . ¦ ¦ ¦ ¦ ¦ 1 ¦ _1 . ¦ _1 . ¦ ¦

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

¦ 1 ¦ ¦ _1 . ¦ 1 ¦ ¦ 1 ¦ ¦ 1 ¦ 1 ¦ ¦ 1 ¦ ¦ 1 ¦ 1 ¦

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

4__ _ _ _ __ _ _ _ __ _ _ _

cd V abd V abc V cd V abd V abc V cd V abd V abc V

4__ _ __ _ __ __ _ __

V abcd V abcd V abcd V abcd V abcd V bcd

Следующий шаг заключается в нахождении на карте простых имп-

ликант, т.е. в склеивании минтермов. Нахождение простых импликант

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

x 41 0x 42 0x 43 0...x 4n 0 V x 41 0x 42 0x 43 0...x 4n 0 = x 42 0x 43 0...x 4n

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

группировки минтермов, отмеченных единицей.

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

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

- 4 -

числа переменных. Группирование выполняется в следующем порядке:

а) группа из восьми членов может быть представлена одной пе-

ременной, если две смежные строки, либо два смежных столбца, либо

две крайние строки, либо два крайних столбца, соответствующих

этой переменной, заполнены единицами;

б) группа из четырех членов может быть представлена посредс-

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

- строка диаграммы,

- столбец диаграммы,

- квадрат из двух строк и двух столбцов,

- концы двух смежных строк,

- концы двух смежных столбцов,

- четыре угла диаграммы;

в) группа из двух членов может быть представлена посредством

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

- два смежных квадратика,

- два противоположных конца одной строки,

- два противоположных конца одного столбца.

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

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

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

переменные. Один и тот же минтерм может входить 2 несколько раз 0 в

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

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

ции. В нашем случае минимизированная функция будет иметь вид:

4__ _ _ _ 0 4_ _ 0 ___

f(a,b,c,d) = cd V abd V abc V abd V bcd V abd.

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

ЛЕКЦИЯ N 8

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

(окончание)

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

помощью одного из методов минимизации, либо используют другой ме-

тод (хотя при наличии у функции нескольких минимальных форм могут

быть получены несовпадающие результаты), либо проверяют на тож-

дественность исходную и минимальную формы методом перебора всех

возможных комбинаций значений переменных (однако уже для 20 пере-

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

В качестве примера проведем минимизацию рассматривавшейся

ранее функции

4_ _ _ _

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

с помощью карты Вейча. Как видно из диаграммы, возможны две мини-

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

----+---¬

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

b ¦ 1 ¦ ¦ _1 . ¦ _1 . ¦

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

¦ 1 ¦ 21 0 ¦ 21 0 ¦ ¦

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

L---T----

4_ _ 0 4_

f(a,b,c) = ac V ab V bc

----+---¬

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

b ¦ _1 . ¦ ¦ 21 0 ¦ _1 . ¦

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

¦ 1 ¦ 1 ¦ 21 0 ¦ ¦

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

L---T----

4_ _ 0 4_

f(a,b,c) = bc V ac V ab

- 2 -

2ЭЛЕМЕНТЫ И УЗЛЫ ЭВМ

===================

2ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ

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

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

ния информации и одинаковый тип межэлементных связей.

Система элементов чаще всего избыточна по своему составу,

что позволяет строить схемы с более простой топологией межэле-

ментных связей и более экономные по количеству используемых эле-

ментов.

Классификация логических элементов:

1) По способу представления информации и типу межэлементных

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

сно-потенциального и динамического типа.

Примечание: в современных ЭВМ применяются потенциальные и

динамические элементы.

2) По функциональному назначению элементы принято разделять

на 2типовые и элементы специального назначения 0. К 2типовым 0 относят-

ся логические, запоминающие и формирующие элементы. Логические

элементы предназначены для преобразования информации, запоминаю-

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

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

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

пям. К элементам 2 специального назначения 0 относятся усилители сла-

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

другие элементы, не изменяющие информационного содержания сигна-

лов.

3) В зависимости от используемых физических явлений логичес-

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

водниковые, электромагнитные и др.

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

Общие технические характеристики:

- температурный диапазон,

- надежность,

- стоимость.

Специфические характеристики:

- функциональные возможности элемента,

- нагрузочная способность,

- быстродействие,

- 3 -

- помехоустойчивость,

- потребляемая мощность.

Функциональные возможности логического элемента характеризу-

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

объединения, т.е. факторами, влияющими на структуры более сложных

схем, построенных с применением данного элемента.

При этом под 2коэффициентом разветвления 0 2n 0 понимают число

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

данной ячейки, а под 2коэффициентом объединения 0 2m 0 - число входов,

которое может иметь ячейка. Величины m и n ограничиваются услови-

ями сохранения нормального электрического режима ячейки.

2Нагрузочная способность 0 в общем случае определяется током,

который может быть отдан ячейкой во внешние цепи (нагрузку). В

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

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

2Быстродействие 0 логического элемента определяется скоростями

его перехода из состояния "0" в состояние "1" и обратно. Переход-

ные процессы изменения состояния элемента состоят из двух этапов:

задержки и формирования фронта или спада сигнала. Длительность

задержек и фронтов зависит от динамических свойств логического

элемента.

Однако для оценки быстродействия часто используют обобщенную

характеристику - 2 среднее время задержки 0. В этом случае моментом

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

сигналом некоторого определенного уровня (например, 0,5 от уста-

новившегося значения). Моментом появления сигнала на выходе также

считают момент достижения выходным сигналом этого уровня.

Так как длительности переходных процессов при включении и

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

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

Время задержки при формировании спада

t 4сп

t 5' 4з 5 0= t 4з.сп 0+ 4 0--- ,

а время задержки при формировании фронта

t 4фр

t 5" 4з 5 0= t 4з.фр 0+ 4 0--- .

Среднее время задержки на один каскад схемы

t 5' 4з 0 + t 5" 4з

t 4з.ср 0 = --------- 5.

- 4 -

Одна из важнейших характеристик элемента - его 2помехоустой-

2чивость 0. Различают статическую и динамическую помехоустойчивость.

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

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

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

ной длительности. Устойчивость элемента к воздействию длительной

помехи меньше, чем к воздействию кратковременной помехи при оди-

наковых амплитудах. Устойчивость к воздействию динамической поме-

хи тем ниже, чем выше быстродействие элемента.

С увеличением степени интеграции элементов ЭВМ все большую

роль начинает играть такой параметр, как 2 рассеиваемая мощность 0.

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

вень рассеивания мощности (P 4з 0), а открытому - другой (P 4о 0). Обычно

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

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

ваемую мощность следующим образом:

P 4з 0 + P 4о

P 4ср 0 = ------- .

Рассеиваемая мощность может зависеть как от нагрузки, так и

от схем, включенных на входе.

1Классификация логических элементов по типу радиокомпонентов,

1на которых реализуются логические функции 2.

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

данный момент типы логических элементов:

- транзисторно-транзисторная логика с диодами Шотки (ТТЛШ);

- КМОП-логика (логика на базе комплементарных полевых тран-

зисторов со структурой металл-окисел-полупроводник);

- КМДП-логика (логика на базе комплементарных полевых тран-

зисторов со структурой металл-диэлектрик-полупроводник);

- интегральная инжекционная логика (ИИЛ, И 52 0Л, I 52 0L).

Следует отметить также некоторые типы элементов, которые в

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

низкого быстродействия или большой рассеиваемой мощности.

- резисторно-транзисторная логика (РТЛ, RTL);

- резисторно - конденсаторная транзисторная логика (РКТЛ,

RCTL);

- диодно-транзисторная логика (ДТЛ, DTL);

- транзисторно-транзисторная логика (ТТЛ, TTL);

- транзисторная логика с эмиттерными связями (ЭСЛ, TECL).

- транзисторная логика с непосредственными связями (DCTL).

- МОП-логика;

- МДП-логика (MDS).

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

ЛЕКЦИЯ N 9

2ЭЛЕМЕНТЫ И УЗЛЫ ЭВМ

===================

2ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ

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

машинным словом, называют 2узлом 0 ЭВМ. Многие узлы ЭВМ строятся на

базе логических элементов.

Общие требования к проектируемому устройству:

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

ональному назначению, т.е. выполнять заданные в ТЗ функции;

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

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

ность, давление, вибрация, удары, статическое электричество,

внешние магнитные поля, электромагнитные помехи и пр.) должны со-

ответствовать заданным в ТЗ параметрам;

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

чить высокое быстродействие и надежность, а также низкую себесто-

имость.

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

наборов логических элементов, особенно в случае различной техно-

логии изготовления (ТТЛ и ТТЛШ, ТТЛ и КМОП, ТТЛ и ЭСЛ и т.п.),

необходимо тщательно проверить эти наборы на совместимость во

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

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

Требуется проверить:

- соответствие по номинальному напряжению питания;

- соответствие по входным и выходным характеристикам логи-

ческих элементов, особенно по уровням 0 и 1;

- соответствие элементов по быстродействию;

- соответствие по переходным процессам.

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

2Амплитудная передаточная характеристика 0 U 4вых 0= 4 0f(U 4вх 0) опре-

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

тойчивость, амплитуду и уровни стандартного сигнала. Вид характе-

ристики зависит от типа логического элемента (ЭСЛ, ТТЛ и т.д.) и

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

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

пературы окружающей среды.

2Входная характеристика 0 I 4вх 0 = f(U 4вх 0) и 2выходная характеристи-

2ка 0 U 4вых 0 = f(I 4вых 0) позволяют определить нагрузочную способность

элемента, режим его работы и способ согласования переходных про-

- 2 -

цессов в линиях связи.

2Импульсная (динамическая) помехоустойчивость 0 - это зависи-

мость допустимой амплитуды импульсной помехи от ее длительности

U 4пом 0 = f(t 4пом 0).

2ТРИГГЕРЫ

Практически все устройства ЭВМ совмещают функции переработки

и хранения информации. Неотъемлемая часть таких устройств - эле-

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

ния информации чаще всего используют элемент с двумя устойчивыми

состояниями - 2триггер 0.

Структуру триггера можно представить в виде запоминающей

ячейки и схему управления:

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

--------¬ 4S 0 ---------¬

E 41 0 ---+-+ Схема +-----+ Запоми-+-+--- Q

C -----+ управ-¦ 4R 0 ¦ нающая ¦ 4 _

E 42 0 ---T-+ ления +-----+ ячейка +-T--- Q

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

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

4_ 0 2Запоминающая ячейка 0 - это схема, которая имеет два выхода Q

и Q 4, 0 сигналы на которых всегда противоположны (если на одном 0,

то на другом 1), и два входа - вход установки S (set) и вход

сброса R (reset).

2Переключающий 0 сигнал по входу S устанавливает запоминающую

ячейку в состояние "1", а по входу R - в состояние "0". В зависи-

мости от типа элементов, из которых построена запоминающая ячей-

ка, переключающим сигналом может являться либо "0", либо "1". За-

поминающую ячейку называют также 2 асинхронным RS-триггером 0.

2Схема управления 0 преобразует информацию, поступающую на вхо-

ды E 41 0 и E 42 0 в сигналы, которые подаются на установочные входы за-

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

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

показаны пунктиром.

Как правило, триггеры, применяемые в потенциальной системе

элементов, имеют еще один вход - вход для синхронизирующих сигна-

лов C. Импульсы, поступающие на вход C, не несут логической ин-

формации, но определяют момент приема триггером входной информа-

ции.

- 3 -

1Классификация триггеров

В основу классификации триггерных устройств положены два ос-

новных признака: функциональный признак и способ записи информа-

ции в триггер.

Функциональная классификация - это классификация триггеров

по типам схем управления. По функциональному признаку различают

RS, S, R, E, T, D, TV, DV, RST и JK триггеры.

Классификация по способу записи информации характеризует

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

записи информации в триггер:

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

¦ Потенциальные триггеры ¦

L------------T------------

----------------+--------------¬

-------+------¬ ------+------¬

¦ Асинхронные ¦ ¦ Синхронные ¦

L------T------- L-----T-------

¦ ¦

-------+------¬ -------+------¬

-------+-----¬ ------+-----¬ -------+-----¬ ------+-----¬

¦С внутренней¦ ¦Управляемые¦ ¦С внутренней¦ ¦Управляемые¦

¦ задержкой ¦ ¦уровнем ¦ ¦ задержкой ¦ ¦уровнем ¦

L------------- ¦входного ¦ L------------- ¦синхроим- ¦

¦сигнала ¦ ¦пульса ¦

L------------ L-----T------

-----+----¬

----+---¬ ----+---¬

¦ Одно- ¦ ¦Много- ¦

¦тактные¦ ¦тактные¦

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

2Временная диаграмма 0 - это диаграмма, отображающая зависи-

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

протекающих в нем переходных процессов от времени и сигналов на

входах этого устройства.

Отличительной особенностью 2асинхронных 0 триггеров является

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

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

Запись информации в 2 синхронные тактируемые 0 триггеры осущест-

вляется только при подаче разрешающего импульса ( 2синхроимпульса 0)

на синхронный вход C. Синхронные триггеры подразделяются на две

категории: триггеры, срабатывающие по переднему фронту синхроим-

пульса (" 2по 0 2уровню 0"), и триггеры, срабатывающие по заднему фронту

- 4 -

синхроимпульса (" 2по спаду 0").

Синхронные триггеры могут быть однотактными и многотактными.

Многотактные триггеры характеризуются тем, что формирование ново-

го состояния триггера завершается с поступлением n-го синхроим-

пульса. Наибольшее распространение получили двухтактные синхрон-

ные триггеры.

Законы функционирования триггеров задаются таблицами перехо-

дов или составленными в соответствии с этими таблицами логически-

ми уравнениями.

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

C - вход синхронизации;

S (set) - вход установки триггера в 1;

R (reset) - вход сброса триггера в 0;

D (delay) - "задержка";

T (trigger) - "защелка";

J - вход установки JK-триггера в 1;

K - вход установки JK-триггера в 0;

V - управляющий вход DV-триггера.

Выходы триггеров: Q - прямой выход, Q - инверсный выход.

_Асинхронные триггеры

Асинхронные триггеры редко непосредственно используются в

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

все триггерные схемы.

1Асинхронный RS-триггер

RS-триггер имеет два информационных входа R и S. При поступ-

лении на эти входы сигналов S=1 и R=0 триггер принимает состояние

Q=1, при S=0 и R=1 состояние Q=0, а при S=0 и R=0 триггер сохра-

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

входы нулевых сигналов. Подача единичных сигналов на оба входа R

и S запрещена.

- 5 -

Полная таблица переходов RS-триггера:

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

¦ Q(t) ¦ R(t) ¦ S(t) ¦ Q(t+1) ¦

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

¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦

¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦

¦ 0 ¦ 1 ¦ 0 ¦ 0 ¦

¦ 0 ¦ 1 ¦ 1 ¦ X ¦

¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦

¦ 1 ¦ 0 ¦ 1 ¦ 1 ¦

¦ 1 ¦ 1 ¦ 0 ¦ 1 ¦

¦ 1 ¦ 1 ¦ 1 ¦ X ¦

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

Минимизированная таблица переходов RS-триггера:

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

¦ R(t) ¦ S(t) ¦ Q(t+1) ¦

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

¦ 0 ¦ 0 ¦ Q(t) ¦

¦ 0 ¦ 1 ¦ 1 ¦

¦ 1 ¦ 0 ¦ 0 ¦

¦ 1 ¦ 1 ¦ X ¦

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

Логические уравнения RS-триггера имеют вид:

7( 4 ____

72 0 Q(t+1) = S(t) V R(t) 5. 0Q(t)

72 0 R(t) 5. 0S(t) = 0

Асинхронный RS-триггер на элементах ИЛИ-НЕ:

----¬

R -----+1 ¦

¦ 7@ 0---T-- Q

---+ ¦ ¦

¦ L---- ¦

L---------¬¦

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

¦ ----¬ ¦

L--+1 ¦ ¦ 4 _

¦ 7@ 0--+--- Q

S -----+ ¦

L----

- 6 -

Условное графическое изображение такого триггера:

--T---¬

--+S¦T +--

¦ ¦ ¦

--+R¦ 7@ 0--

L-+----

Асинхронный RS-триггер на элементах И-НЕ:

4_ 0 ----¬

S -----+& ¦

¦ 7@ 0---T-- Q

---+ ¦ ¦

¦ L---- ¦

L---------¬¦

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

¦ ----¬ ¦

L--+& ¦ ¦ 4 _

4_ 0 ¦ 7@ 0--+--- Q

R -----+ ¦

L----

Условное графическое изображение такого триггера:

--T---¬

-- 7@ 0S¦T +--

¦ ¦ ¦

-- 7@ 0R¦ 7@ 0--

L-+----

или

--T---¬

¦ 4_ 0¦ 7 0¦

--+S¦ 7T 0 +--

¦ ¦ ¦

¦ 4_ 0¦ ¦

--+R¦ 7@ 0--

¦ ¦ ¦

L-+----

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

ЛЕКЦИЯ N 10

2ТРИГГЕРЫ

1Синхронный однотактный RS-триггер

Синхронные RS-триггеры имеет на каждом входе дополнительные

схемы совпадения:

----¬ S ----¬

S ------+& 7@ 0------+& ¦

¦ ¦ ¦ 7@ 0---T-- Q

---+ ¦ ---+ ¦ ¦

¦ L---- ¦ L---- ¦

¦ L---------¬¦

C ---+ ¦¦

¦ ----------+-

¦ ----¬ ¦ ----¬ ¦

L--+& ¦ 4_ 0 L--+& ¦ ¦ 4 0 4_

¦ ¦ R ¦ 7@ 0--+--- Q

R ------+ 7@ 0------+ ¦

L---- L----

Если на входе C "ноль", то на выходах схемы совпадения также

будут нулевые значения при любых сигналах на входах R и S. При

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

входов R и S инвертируется и передается на входы асинхронного

триггера.

Графическое обозначение синхронного однотактного RS-триггера:

--T---¬

--+S¦T +-- Q

--+C¦ ¦ 4 _

--+R¦ 7@ 0-- Q

L-+----

- 2 -

Синхронный триггер может иметь дополнительные асинхронные

входы R 4а 0 и S 4а 0:

S 4а 0 --------------¬

4_ 0 ¦ ----¬

----¬ S L--+& ¦

S ------+& 7@ 0------+ 7@ 0---T-- Q

¦ ¦ ---+ ¦ ¦

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

¦ L---- L---------¬¦

C ---+ ¦¦

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

L--+& ¦ 4_ 0 ¦ ----¬ ¦

¦ ¦ R L--+& ¦ ¦ 4 _

R ------+ 7@ 0------+ 7@ 0--+---- Q

L---- ---+ ¦

4_ 0 ¦ L----

R 4а 0 ---------------

Графическое обозначение синхронного однотактного RS-триггера

с асинхронными входами:

4_ 0 --T---¬

S 4а 0 -- 7@ 0S¦T +-- Q

+-+ ¦

--+S¦ ¦

--+C¦ ¦

--+R¦ ¦

4_ 0 +-+ ¦ 4 _

R 4а 0 -- 7@ 0R¦ 7@ 0-- Q

L-+----

1Синхронные 0 1двухтактные триггеры

Синхронные двухступенчатые (двухтактные) триггеры построены

по принципу "master-slave" (ведущий-ведомый). Триггерная схема

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

в которые запрещен. Для построения первой и второй ступеней ис-

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

во вторую ступень только после ее приема в первую ступень и окон-

чания синхроимпульса, разрешающего запись информации в первую

ступень. Такая последовательность приема информации достигается

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

- 3 -

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

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

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

E 41 0 ---+----+E 41 0¦T +-----+S¦T +-+--- Q

C ------T-+C ¦ ¦ ---+C¦ ¦ 4 _

E 42 0 ---T--+-+E 42 0¦ +--+--+R¦ +-T--- Q

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

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

¦ ---¬ ¦

L----+ 51 0 7@ 0-----

L---

Наиболее широкое применение в устройствах вычислительной

техники находят двухтактные триггеры типов RS, T, D и JK.

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

----¬ ----¬ Q' ----¬ ----¬

S ------+& 7@ 0-----+& 7@ 0--T------+& 7@ 0-----+& 7@ 0--T--- Q

---+ 41 0¦ ---+ 44 0¦ ¦ ---+ 46 0¦ ---+ 48 0¦ ¦

¦ L---- ¦ L---- ¦ ¦ L---- ¦ L---- ¦

¦ L--------¬¦ ¦ L--------¬¦

C ---+ ¦¦ ¦ ¦¦

¦ ---------+- ¦ ---------+-

¦ ----¬ ¦ ----¬ ¦ 4_ 0 ¦ ----¬ ¦ ----¬ ¦

+--+& ¦ L--+& ¦ ¦ 4 0Q' +--+& ¦ L--+& ¦ ¦ 4 _

R ---+--+ 42 7@ 0-----+ 45 7@ 0-+----+--+ 47 7@ 0-----+ 49 7@ 0-+---- 4 0Q

¦ L---- L---- 4_ 0 ¦ L---- L----

¦ ----¬ C ¦

L-----T-+& 7@ 0------------

L-+ 43 0¦

L----

Рассмотрим идеализированную временную диаграмму работы двух-

тактного RS-триггера (предполагаем форрму импульсов прямоугольной

и не учитываем разброс времени задержки элементов схемы):

- 4 -

¦ ------¬ ------¬ ------¬ ------¬

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