Вычислительные машины презентация

S – основание; i – номер разряда; n+1 (n, n-1, …, 1, 0) – количество целых разрядов; m – количество дробных разрядов; n - старший разряд; -m - младший разряд; ai - разрядные коэффициенты; Si - вес i-го разряда.

Пример. 71,25 = 7×101 +1×100,+2×10−1+5×10−2

Сложение
0+0=0;
0+1=1;
1+0=1;
1+1=10

Вычитание
0-0=0;
1-0=1;
1-1=0;
10-1=1

Умножение
0⋅ 0=0;
0⋅ 1=0;
1⋅ 0=0;
1⋅ 1=1

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

1) перевод 1101111001.11012 в восьмеричное
001 101 111 001 . 110 100 = 1571.648;
1 5 7 1 6 4
 
2) перевод 11111111011.1001112 в шестнадцатеричное
0111 1111 1011 . 1001 1100 = 7FB.9C16.
7 F B 9 C

Следовательно, 4310 ==>1010112; 4310 ==> 2В16.

Следовательно, 0,37510 ==>0,0112; 0,375 10 ==>0,616.

Перевод (8) ? (10)
X=

Перевод (10) ? (2)

340/2=170(ост 0); 170/2=85(0); 85/2=42(1); 42/2=21(0); 21/2=10(1); 10/2=5(0); 5/2=2(1); 2/2=1(0). Целая часть 101010100
0,75x2=1,5; 0,5x2=1,0. Дробная часть 0,11
X=101010100,11

X=

Перевод (10) ? (8)
340/8=42(4); 42/8=5(2);
0,75x8=6,0
X=524,6

и функция y

принимает значение 0,1 из множества B={0,1}.

Булевой (логической) функцией называется двоичная функция от двоичных аргументов.
Булева функция задает отображение булева пространства (состоящего из

двоичных векторов) в множество {0,1}:

элементов – n-компонентных

Имеется 16 булевых функций от двух аргументов:

Функции (двухместные логические операции) дизъюнкции , коньнкции и отрицания (инверсии) образуют булеву алгебру.

Умножение на константу

Сложение с константой

Идемпотентность

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

Пример СДНФ и таблицы истинности

На рисунке показано, как реализовать функцию ИЛИ на элементах И-НЕ

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

Дублирование элементарных конъюнкций

=

=

Например, при n=4 в группу с i=1 включаются конъюнкции вида

в группу с i=2 конъюнкции вида

Попарное сравнение при этом можно проводить только между соседними по номеру группами, поскольку склеивающиеся конъюнкции могут содержаться только в соседних по номеру группах. В остальном минимизация по методу Квайна-Мак-Класки совпадает с минимизацией по методу Квайна.

В случае целых чисел минимальным по модулю отличным от нуля числом будет Аmin = 00…01, = 1, а максимальным, которому соответствуют единицы во всех n разрядах, – Amах = 11…11, = 2n - 1, т. е. диапазон представления чисел в этом случае 1 ≤ |A| ≤ 2n - 1.

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

где M – мантисса числа; r – основание системы счисления; p – порядок числа. Мантисса |М| < 1, т.е. является правильной дробью, а порядок р – целое число.

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

В случае представления числа с плавающей запятой со смещенным порядком к его порядку p прибавляется целое число – смещение 2q, где q – число двоичных разрядов, используемых для представления модуля порядка,
pсм = p + 2q.

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

а наибольшее по модулю число с плавающей запятой

Абсолютная погрешность перевода десятичной дроби в систему с основанием r при использовании усечения (младшие цифры справа отбрасываются) определяется следующим выражением

Для двоичной системы счисления r = 2, и максимальное значение этой погрешности получается при ai = 1

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

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

Для представления чисел в форме с фиксированной запятой абсолютное значение машинного изображения правильной дроби находится в диапазоне

2-n ≤ |A|Ф ≤ 1 - 2-n.

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

В современных ЭВМ, как правило, n = 16…64, поэтому 1>>2-n, откуда

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

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

Пример. n = 4
A1 = +1011; [A1]пр = 0.1011.
A2 = - 1011; [A2]пр = 1.1011.

Пример. n = 4
A1 = +0,1010; [A1]пр = 0,1010.
A2 = - 0,1010; [A2]пр = 1,1010.

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

A = +00…00; [A]пр = 0.00…00.
A = - 00…00; [A]пр = 1.00…00.

[A]доп = 2n+1 + A = 2n+1 - |A| = 2n + 2n - |A| = 2n + 2n - 1 - |A| + 1

код знака

дополнение A′

инверсия числа

[A]доп = 2 + A = 2 - |A| = 1 + 1 - |A| = 1 + 1 – 2-n - |A| + 2-n

Пример. Записать дополнительный код числа A = - 0,101101, n = 6.
10,000000 2 1,000000 1,000000
- 0,101101 |A| - 0,101101 |A| - 0,000001 2-n
1,010011 [A]доп 0,010011 A′ 0,111111
+ 1,000000 - 0,101101 |A|
1,010011 [A]доп 0,010010 инверсия |A|
+ 0,000001 2-n
0,010011 A′
+ 1,000000
1,010011 [A]доп

Нуль в дополнительном коде имеет одно представление: 0.00…00.

[A]обр = 2n+1 - 1 + A = 2n+1 -1 - |A| = 2n + 2n - 1 - |A|

Пример. Записать обратный код числа A = - 101101, n = 6.
10.000000 2n+1 1.000000 2n
- 1 - 1
1.111111 0.111111
- 101101 |A| - 101101 |A|
1.010010 [A]обр 0.010010 A" = инверсия |A|
+ 1.000000 2n
1.010010 [A]обр

[A]обр = 2 - 2-n + A = 2 - 2-n - |A| = 1 + 1 - 2-n - |A|

Пример. Записать обратный код числа A = - 0,101101, n = 6.
10,000000 2 1,000000
- 0,000001 2-n - 0,000001 2-n
1,111111 0,111111
- 0,101101 |A| - 0,101101 |A|
1,010010 [A]обр 0,010010 A" = инверсия |A|
+ 1,000000
1,010010 [A]обр

Нуль в обратном коде имеет два представления:
A = +00…00; [A]обр = 0.00…00.
A = - 00…00; [A]обр = 1.11…11.

где aj – j-я десятичная цифра,

– i-й разряд j-ой тетрады,
n – количество десятичных цифр.

Количество различных Д-кодов определяется количеством возможных сочетаний по 10 из 16 комбинаций, которые допускает тетрада.

(i = 0, 1, 2, 3);

Коды, обладающие таким свойством, называют самодополнительными.

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

где σ3, σ2, σ1, σ0 – веса соответствующих разрядов тетрады.

Стандарт определяет 32-битовый (одинарный) и 64-битовый (двойной) форматы

+ 1 циклический перенос
0.0100 [A + B]доп = [A + B]пр
Ответ: A + B = +100.

Пример. Сложить два числа в дополнительных кодах: A = +1001, B = -101, n = 4.
Решение. [A]доп = 0.1001; [B]доп = 1.1011
0.1001 [A]доп
+ 1.1011 [B]доп

10.0100 [A + B]доп = [A + B]пр
Ответ: A + B = +100.

отбрасывается

10.1000 [A + B]доп переполнение.

отбрасывается

Пример. Сложить два дробных отрицательных числа в дополнительных кодах:
A = -0,1011, B = -0,0101, n = 4.
Решение. [A]доп = 1.0101; [B]доп = 1.1011
1.0101 [A]доп
+ 1.1011 [B]доп

11.0000 [A + B]доп переполнение.

отбрасывается

а)

б)

.

110.1001 [A + B]доп комбинация 10 указывает на переполнение.

отбрасывается

Алгоритм умножения включает следующие шаги:
обнуление СЧП0;
анализ младшего разряда множителя: если b0 = 1, выполняется сложение ЧП0 = A с СЧП0 и переход к п. 3; если b0 = 0, сразу переход к п. 3;
сдвиг множимого влево;
анализ очередного разряда множителя: если b1 = 1, выполняется сложение ЧП1·21 с СЧП1 и переход к п. 5; если b1 = 0, непосредственно переход к п. 5;
сдвиг множимого влево;
анализ очередного bi разряда множителя и т.д. После анализа старшего bn-1 разряда множителя осуществляется последнее сложение ЧПn-1·2n-1 с суммой частичных произведений СЧПn-1 (если bn-1 = 1), и процесс прекращается. Результирующая СЧПn является искомым произведением.

Применив схему Горнера, выражение для произведения можно записать следующим образом:

Выражения в скобках в формуле представляют собой последовательные значения СЧПi, определяемые рекуррентной формулой

Алгоритм умножения включает следующие шаги:
обнуление СЧП0;
сдвиг СЧП0 влево;
анализ старшего разряда множителя: если bn-1 = l, выполняется сложение ЧПn-1 = A с СЧП0·21 и переход к п. 4; если bn-1 = 0, сразу переход к п. 4;
сдвиг СЧП1 влево;
анализ очередного bn-2 разряда множителя и т.д. После анализа младшего b0 разряда множителя выполняется последнее сложение ЧП0 = A с СЧПn-1 (если b0 = 1), и процесс прекращается.

– множимое, сдвинутое влево на n разрядов.

Алгоритм умножения включает следующие шаги:
обнуление СЧП0;
сдвиг множимого вправо;
анализ старшего разряда множителя: если bn-1 = 1, выполняется сложение ЧПn-1·2-1 с СЧП0 и переход к п. 4; если bn-1 =0, сразу переход к п. 4;
сдвиг множимого вправо;
анализ очередного разряда bn-2 множителя и т.д. После анализа младшего разряда b0 множителя осуществляется последнее сложение ЧП0·2-1 с СЧП (если b0 =1), и процесс прекращается.

Применив схему Горнера к методу 3, выражение для произведения можно записать следующим образом:

Алгоритм умножения включает следующие шаги:
обнуление СЧП0;
анализ младшего разряда множителя: если b0 = 1, сложение ЧП0 = V с СЧП0 и переход к п. 3; если b0 = 0, непосредственно переход к п. 3;
сдвиг СЧП1 вправо;
анализ очередного разряда b1 множителя и т.д. После анализа старшего разряда bn-1 множителя осуществляются последнее сложение ЧПn-1 с СЧП n-1 (если bn-1 = l) и последний сдвиг СЧПn вправо, после чего процесс прекращается.

Ответ: A×B = 1001011.

Ответ: A×B = 1001011.

Ответ: A×B = -130

Величина коррекции -A·24 = [-A]доп·24 = 1.0011·24.

Ответ: A×B = -130.

2m + 2m-1 + … + 2k = 2m+1 – 2k,
где m и k – номера крайних разрядов в группе из последовательных единиц. Например, 011110 = 25 - 21. Это означает, что при наличии в множителе групп из нескольких единиц (комбинаций вида 011110), последовательное добавление к СЧП множимого с нарастающим весом (от 2k до 2m) можно заменить вычитанием из СЧП множимого с весом 2k и прибавлением к СЧП множимого с весом 2m+1.

Алгоритм Бута.

Ответ: A×B = 10010.

, S = Z - QD, S < D, где Z – делимое, D – делитель.

Операция выполняется за n итераций и может быть описана следующим образом:

Частное от деления 2n-разрядного числа на n-разрядное может содержать более чем n разрядов. В этом случае возникает переполнение, из-за чего перед выполнением деления необходима проверка условия

В общем случае для определения (n-i)-й цифры частного анализируется частичный остаток. Если ЧОi-1 ≥ 0, он сдвигается влево и из него далее вычитается Дт, в результате чего получается остаток ЧОi. Если же ЧОi-1 < 0, то сначала восстанавливается предыдущий положительный (сдвинутый) остаток, для чего к ЧОi-1 прибавляется Дт. Далее восстановленный остаток сдвигается влево, из него вычитается Дт, и в результате получается остаток ЧОi. При ЧОi ≥ 0 (n-i)-я цифра частного равна единице, при ЧОi <. 0 – нулю.

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

Компараторы

и принимает нулевое значение при

Основными отношениями считаются два – «равно» и «больше». Остальные отношения выражаются через них следующим образом:

Компараторы строятся на основе поразрядных операций над одноименными разрядами обоих слов. Слова равны, если попарно равны все одноименные их разряды. Признак (условие) равенства i-х разрядов сравниваемых слов А и В формируется следующим образом:

Условие неравенства i-x разрядов:

P = ab

Обозначением полусумматора служат буквы HS (half sum – полусумма).

Уравнения, описывающие работу полного двоичного сумматора, представленные в совершенной дизъюнктивной нормальной форме (СДНФ), имеют вид:

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

P = ab + ap + bp

S = a ⊕ b ⊕ p

D/0 - функция генерации выходного переноса из четырехразрядной секции.
F/0 - функция распространения переноса через четырехразрядную секцию.

а

б

в

A={a0,a1, …, am} – множество состояний (алфавит состояний), содержащее не менее двух элементов;
Z={z1,z2, …, zF} – множество входных сигналов (входной алфавит), F>1;
W={w1,w2, …, wG} – множество выходных сигналов (выходной алфавит), G>1;
d - функция переходов, реализующая отображение пары “состояние – входной сигнал” в некоторое состояние автомата, т.е. d(ai,zj)=as;
l -функция выходов;
а0 – начальное состояние автомата.