1.5.Преобразование дополнительного кода

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

1. Если число, записанное в прямом коде, положительное, то к нему дописывается старший (знаковый) разряд, равный 0, и на этом преобразование заканчивается;

2. Если число, записанное в прямом коде, отрицательное, то все разряды числа инвертируются, а к результату прибавляется 1. К получившемуся числу дописывается старший (знаковый) разряд, равный 1.

Пример. Преобразуем отрицательное число −5, записанное в прямом коде, в дополнительный. Прямой код числа −5, взятого по модулю:

101

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

010

Добавим к результату 1

011

Допишем слева знаковый единичный разряд

1011

Для обратного преобразования используется тот же алгоритм. А именно:

1011

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

0100

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

0101 + 1011 = 10000, пятый разряд выбрасывается.

1.5.1.Преимущества

• Один и тот же регистр может хранить как n-битовое положительное число, так и (n−1)-битовое число со знаком, с общими для обоих форматов операциями сложения, вычитания и левого сдвига.

• Более удобная упаковка чисел в битовые поля.

• Отсутствие числа «минус ноль».

1.5.2.Недостатки

• Дополнительный код неочевиден для новичков.

• В сложных форматах (таких, как плавающая запятая или двоично-десятичный код) большинство преимуществ аннулируются.

• Модуль наибольшего числа не равен модулю наименьшего числа.

№14. Указать основные соотношения между прямым, обратным и дополнительным кодами числа.

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

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

Для представления двоичных чисел в машине применяют прямой, обратный и дополнительный коды. Во всех этих кодах предусматривается дополнительный разряд для представления знака числа, причем знак «+» кодируется цифрой 0, а знак « -- » - цифрой 1.

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

Прямой код (G)пр двоичного числа G = ± 0, г1, г2, … , гn (гi = 1 или 0) определяется условиями:

G при G ? 0

(G)пр =

(1 - G) при G ? 0

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

G+ = + 0, г1, г2, … , гn

в прямом коде представляется в виде:

(G+) пр = 0, г1, г2, … , гn (1)

Аналогично отрицательное двоичное число:

G- = - 0, г1, г2, … , гn (1a)

в прямом коде представляется в виде:

(G-) пр = 1, г1, г2, … , гn (2)

Способы представления чисел (1) и (2) называются прямым кодом соответственно положительных и отрицательных двоичных чисел.

№15. Охарактеризовать модифицированный обратный и дополнительный коды числа. Перечислить преимущества и недостатки модифицированного представления чисел в цифровых автоматах.

№18. Дать понятие логической функции и логического устройства. Провести классификацию логических устройств по способу ввода-вывода кодовых слов и по способу функционирования.

Логическая функция - это функция логических переменных, которая

может принимать только два значения : 0 или 1. В свою очередь,

сама логическая переменная (аргумент логической функции) тоже может

принимать только два значения : 0 или 1. Логический элемент - это устройство, реализующее ту или иную

логическую функцию.

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

На входы устройства последовательного действия символы кодовых слов поступают не одновременно, а последовательно, символ за символом (в так называемой последовательной форме).

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

В устройствах смешанного действия входные и выходные кодовые слова представляются в разных формах. Например: входные слова - в последовательной форме, выходные - в параллельной. Устройства смешанного действия могут использоваться для преобразования кодовых слов из одной формы представления в другую (из последовательной формы в параллельную и наоборот).

По способу функционирования логические устройства (и их схемы) делятся на два класса: комбинационные устройства (и соответственно комбинационные схемы) и последовательные устройства (последовательные схемы).

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

В последовательных устройствах (или автоматах с памятью) выходной сигнал определяется не только набором символов, действующих на входах в данный момент времени, но и внутренним состоянием устройства, а последнее зависит от того, какие наборы символов действовали во все предшествующие моменты времени. Поэтому можно говорить, что последовательные устройства обладают памятью (они хранят сведения о прошлом работы устройства).

№19. Описать способы задания логических функций.

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

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

Таблица истинности функций двух аргументов представлена в табл. 1. Существует всего четыре функции одного аргумента.

ТАБЛИЦА 1:

Если число аргументов функции равно n, то число различных сочетаний (наборов) значений аргументов составляет 2ⁿ, а число различных функций п аргументов-2²ⁿ. Так, при n=2 число наборов значений аргументов равно 2²=4, число функций 2⁴=16. Таблица истинности логических функций двух аргументов представлена в табл. 2.

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

Функции одного агрумента (табл. 1) представляются следующими выражениями:

f1(x) = 0 (константа 0); f2(x)=x;

f3(х) = х; f4(х) = 1 (константа 1).

Устройства, реализующие функции f1(x), f2(x) и f4(x), оказываются тривиальными. Таким образом, из всех функций одного аргумента практический интерес может представлять лишь функция f3(х), которую называют инверсией или логическое НЕ.

Из таблиц истинности функций f0 - f15 (табл. 2) наиболее широко используемыми являются:

f1(x1,x2) = x1*x1 - конъюнкции, логическое произведение, И;

f7(x1,x2) = x1 + x2 - дизъюнкции, логическое сложение, ИЛИ;

f14(x1,x2) = x1 + x2 - логическое И-НЕ;

f14(x1,x2) = x1 * x2 - логическое ИЛИ-НЕ.

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

Свойства конъюнкции, дизъюнкции и инверсии.

Конъюнкция переменных х1 и х2 равна лог. 1 в том случае, когда и x1 и x2 равны лог. 1 (отсюда возникло название операции логическое И).

Дизъюнкция переменных х1 и x2 равна лог. 1, если или х1 или x2 равны лог. 1 (отсюда понятно возникновение названия операции логическое ИЛИ).

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

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

Подобно этому и для сложного логического выражения установлен определенный порядок выполнения операций: вначале выполняются операции инверсии, затем операции конъюнкции и в последнюю очередь операции дизъюнкции. Например, запись логического выражения х1+х2*x3+x4*x2 предполагает, что при вычислении выражения вначале выполняются операции инверсии х3 и затем операции конъюнкции х2*x3 и в последнюю очередь - операции дизъюнкции. А если требуется нарушить это правило, используются скобки. В этом случае вначале выполняются операции в скобках (а если одни скобки вложены в другие, то вначале выполняются операции в самых внутренних скобках).

Операции конъюнкции и дизъюнкции обладают рядом свойств:

сочетательный закон : x1*(x2*x3) = (x1*x2)*x3 x1+(x2+x3) = (x1+x2)+x3;

переместительный закон: x1*x2 = x2*x1 x1+x2 = x2+x1;

распределительный закон: x1+(x2*x3) = (x1+x2) * (x1+x3).

Легко убедиться в справедливости следующих выражений:

1*х=х; х*х=х; 1+x=1; х+х=х; 0*х=0; х * х =0; 0+х=х; х + х = 1 .

Кроме того, существуют так называемые формулы де Моргана:

x1+x2 = x1 * x2 и x1*x2 = x1 + x2

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

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

1.5.3.С х е м а   И

Схема И реализует конъюнкцию двух или более логических значений. Условное обозначение на структурных схемах схемы И с двумя входами представлено на рис. 5.1.

                    Рис. 5.1

Таблица истинности схемы И

x	y	x . y
0	0	0
0	1	0
1	0	0
1	1	1

Единица на выходе схемы И будет тогда и только тогда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет ноль, на выходе также будет ноль.

Связь между выходом  z  этой схемы и входами  x  и  y  описывается соотношением:   z = x ^. y (читается как "x и y"). Операция конъюнкции на структурных схемах обозначается знаком  "&"  (читается как "амперсэнд"),  являющимся сокращенной записью английского слова  and.  

1.5.4.С х е м а   ИЛИ

Схема  ИЛИ  реализует дизъюнкцию двух или более логических значений. Когда хотя бы на одном входе схемы  ИЛИ  будет единица, на её выходе также будет единица.

Условное обозначение на структурных схемах схемы ИЛИ с двумя входами представлено на рис. 5.2.   Знак "1" на схеме — от устаревшего обозначения дизъюнкции как   ">=1"  (т.е. значение дизъюнкции равно единице, если сумма значений операндов больше или равна 1).    Связь между выходом  z  этой схемы и входами  x  и  y   описывается соотношением:  z = x v y  (читается как "x или y").

                    Рис. 5.2

Таблица истинности схемы ИЛИ

x	y	x v y
0	0	0
0	1	1
1	0	1
1	1	1

 

1.5.5.С х е м а   НЕ

Схема   НЕ  (инвертор) реализует операцию отрицания.  Связь между входом   x  этой схемы и выходом   z  можно записать соотношением   z = , x где     читается как   "не x"   или  "инверсия х".

Если на входе схемы  0,  то на выходе  1.  Когда на входе  1,  на выходе  0.  Условное обозначение на структурных схемах инвертора — на рисунке 5.3

                    Рис. 5.3

Таблица истинности схемы НЕ

x
0	1
1	0

 

1.5.6.С х е м а   И—НЕ

Схема И—НЕ состоит из элемента И и инвертора и осуществляет отрицание результата схемы И. Связь между выходом z и входами x и y схемы записывают следующим образом: , где     читается как   "инверсия x и y".   Условное обозначение на структурных схемах схемы   И—НЕ  с двумя входами представлено на рисунке 5.4.

                    Рис. 5.4

Таблица истинности схемы И—НЕ

x	y
0	0	1
0	1	1
1	0	1
1	1	0

 

1.5.7.С х е м а   ИЛИ—НЕ

Схема ИЛИ—НЕ состоит из элемента ИЛИ и инвертора  и осуществляет отрицание результата схемы ИЛИ.     Связь между выходом  z  и входами  x  и  y  схемы записывают следующим образом:   ,  где   ,  читается как  "инверсия  x или y ". Условное обозначение на структурных схемах схемы ИЛИ—НЕ с двумя входами представлено на рис. 5.5.

                    Рис. 5.5

Таблица истинности схемы ИЛИ—НЕ

x	y
0	0	1
0	1	0
1	0	0
1	1	0

№21. Раскрыть сущность понятия "Полная система функций алгебры логики". Указать базисы, используемые при проектировании логических устройств.

12.Полные системы функций Определения. Система функций F называется полной, если всякая функция алгебры логики представила посредством суперпозиций функций из системы F. Система функций F называется базисом, если удаление из множества F любой функции приводит к нарушению полноты. Утверждение 1. Система функций F0={x, xvy} является полной. Это следует из Теоремы о разложении функций алгебры логики от n переменных по k=n переменным. Утверждение 2. Системы функций f1={x&y,x}, f2={xVy, x} являются полными, так как x V y = x & y и x & y = x(vector) V y(vector) Утверждение 3. Системы функций F3={x|y}, F4={x”стрелка вниз”y} - штрих Шиффера и стрелка Пирса, являются полными, так как X”веткор”= x|x , x&y = x|y, x = x “стрелка вниз” x, xVy = x “стрелка вниз” y. Утверждение 4. Система функций F5 = {x&y,x+y,1} является полной, так как x “вектор” = + 1. Замечание. Очевидно, что все приведенные выше системы функций, кроме системы F0, являются базисами.

№22. Описать механизм физического представления логических значений. Дать понятие логического элемента, указать основные параметры логических элементов.

Логический элемент- это устройство, реализующее ту или иную логическую операцию.

1. Коньюнктер (см. конспект)

2. дизъюнктер

3. инвертор

ЭЛЕМЕНТ «И» имеет несколько входов и 1 выход, реализует логическую операцию «И»

 

ЭЛЕМЕНТ «ИЛИ» имеет несколько входов и 1 выход, реализует логическую операцию «ИЛИ» (сумматор)

ЭЛЕМЕНТ «НЕ» имеет 1 вход и 1 выход, реализует логическую операцию «НЕ» так как выходной сигнал всегда противоположен входному элемент «НЕ» получил название «инвертор»

№23. Описать этапы построения СДНФ функции, заданной аналитическим и табличным способами.

Алгоритм перехода от таблицы истинности

логической функции к ее записи в виде СДНФ

1. Выбрать в таблице такие наборы входных переменных, на которых функция

обращается в единицу;

2. Записать минтермы для выбранных наборов входных переменных. При этом

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

переменной в наборе – единичное, то она записывается в прямой форме, если же

значение переменной – нулевое, то – в инверсной форме;

3. Полученные минтермы объединить между собой знаками дизъюнкции.

СДНФ (Совершенная Дизъюнктивная Нормальная Форма) — это такая ДНФ, которая удовлетворяет трём условиям:

• в ней нет одинаковых элементарных конъюнкций

• в каждой конъюнкции нет одинаковых пропозициональных букв

• каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причем в одинаковом порядке.