КОНСПЕКТ ЛЕКЦИЙ 3 страница

Такт 1. Так как число в Рег.3 меньше числа в Рег.1 то производится общий сдвиг влево содержимого Рег.3 и Рег.2. Получим

Такт 2. Теперь число в Рег.3 больше числа в Рег.1, поэтому производится вычитание из содержимого Рег.3 содержимого Рег.1 с записью результата в Рег.3.

а затем выполняется общий сдвиг всего содержимого Рег.3 и Рег.2 и запись 1-цы в младший разряд Рег.2 Получим

Такт 3. Так как сейчас число в Рег.3 больше числа в Рег.1, то действия предыдущего такта повторяются. После вычитания получим

а после сдвига влево в Рег.3 и Рег.2 и записи 1-цы в младший разряд Рег.2 будем иметь

Такт 4. В этом случае число в Рег.3 стало меньше числа в Рег.1, поэтому производится только общий сдвиг влево Рег.3 и Рег.2

Такт 5. Теперь опять число в Рег.3 больше числа в Рег.1. Поэтому выполняется вычитание

сдвиг и запись 1-цы в младший разряд Рег.2

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

1101₍₂₎=13₍₁₀₎, т. е. 143₍₁₀₎:11₍₁₀₎=13₍₁₀₎.

Замечание. Чтобы реализовать операцию вычитания в сумматоре (рис.1) нужно заменить её операцией сложения с числом в дополнительном коде, т. е. к содержимому Рег.3 прибавлять содержимое Рег.1 взятое в дополнительном коде. В рассмотренном примере вычиталось число 1011, следовательно нужно прибавлять число 0101. (Проверить самостоятельно).

Задание 42. Выполнить операцию деления чисел 126₍₁₀₎ и 14₍₁₀₎, реализуя алгоритм работы схемы рис.1.

Задание 43. Выполнить операцию деления чисел 123₍₁₀₎ и -7₍₁₀₎, реализуя алгоритм работы схемы рис.1.

Замечание. При выполнении операции умножения и деления чисел в форме с ПЗ необходимо выполнить:

- умножение или деление мантисс исходных чисел (по алгоритмам рассмотренным выше);

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

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

1.3. Логические основы вычислительной техники.

Комбинационные схемы и конечные автоматы.

Устройство преобразовывающее информацию

Входной и выходной сигналы.

В цифровой вычислительной машине (ЦВМ) время дискретно, т. е. переход от 0 в 1 за момент. Интервал между моментами – такт.

Преобразующее устройство Р:

, где X(t)={x₁, x₂ … x_n} – множество входных дискретных тактиров-х сигналов, Y(t)={y₁, y₂ … y_m} – множество выходных сигналов, Р – функция или функционал преобразования.

Если элементарный сигнал может быть представлен с различными состояниями:

то можно ввести понятие k-значной логики.

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

Поэтому дальше 2-ая (Булева) логика.

Устройство реализующее Р называется в ЦВМ автоматом.

2 вида дискретных автоматов:

1) Если совокупность выходных сигналов (выходного слова) Y(t) зависит от X(t) и не зависит от внутреннего состояния автомата, то это комбинационная схема. Y(t)=P[X(t)].

Структурная схема:

ЭП комбинационный автомат не содержит.

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

Можно задать: таблицей

аналитически (булевыми функциями)

2) Если Y(t)=P[X(t), S(t-1)], то автомат с памятью (конечный).

r+1 внутренних состояний S(t)={S₀, S₁, … S_r}. При подаче X(t) в t-ом такте автомат переходит их S(t-1) в S(t). Структурная схема

КС – комбинационная схема.

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

Элементы теории конечных автоматов в главе 3.

1.3.1. Переключательные (булевы, логические) функции.

I. Основные понятия и определения.

x1	x2	…	xn	f(x1…xn)
…	…	… … … …	…	…

Булевой функцией называется f(x₁, x₂, … x_n), аргументы которой и сами функции принимают значение из множества Е²={0,1}. Они могут быть заданы таблицей. Полная таблица функции от n переменных имеет 2ⁿ строк и n+1 столбцов. Упорядоченная таблица называется таблицей истинности. Другая форма – булевы выражения.

Теорема: число различных переключательных функций n-аргументов равно

Определение: Две переключательных функции называются равными, если на всех наборах аргументов они принимают одинаковые значения.

Определение: Переключательная функция f называется существенно зависимой от x­_i, если выполняется неравенство: . Не все переключательные f существенно зависимы.

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

II. Элементарные логические функции.

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

Логическая функция 1-ой переменной:

- нулевая функция;

- функция повторения аргумента

- функция инверсии аргумента

- единичная функция

Логические функции 2-х переменных:

функции	аргументы х1 0011 х2 0101	обозначение функции	название функции и комментарии
f0(x1,x2)	0 0 0 0		Нулевая
f1(x1,x2)	0 0 0 1	x1 Ù x2	Конъюнкция
f2(x1,x2)	0 0 1 0		запрет по х 2
f3(x1,x2)	0 0 1 1	х1	повторение х1
f4(x1,x2)	0 1 0 0		запрет по х 1
f5(x1,x2)	0 1 0 1	х2	повторение х2
f6(x1,x2)	0 1 1 0		сумма по mod2
f7(x1,x2)	0 1 1 1		Дизъюнкция
f8(x1,x2)	1 0 0 0		стрелка Пирса
f9(x1,x2)	1 0 0 1		эквивалентность (равнозначность)
f10(x1,x2)	1 0 1 0		отрицание х2
f11(x1,x2)	1 0 1 1		импликация от х 2 к х 1
f12(x1,x2)	1 1 0 0		отрицание х1
f13(x1,x2)	1 1 0 1		импликация от х 1 к х 2 ()
f14(x1,x2)	1 1 1 0	x1\x2	штрих Шеффера
f15(x1,x2)	1 1 1 1		Единичная

III. Системы элементарных логических функций.

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

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

Определение: Если исключение любой элементарной логической функции из ФП СЛФ приводит к функциональной неполноте, то исходная ФП СЛФ называется безызбыточной. Иначе ФП СЛФ называется избыточной.

Теорема о функциональной полноте СЛФ (Постников, Яблонский).

СЛФ называется функционально полной в том и только том случае, если она включает хотя бы одну функцию, не принадлежащую к 5 важнейшим замкнутым классам:

1) – класс функций сохраняющих 0,

2) – класс функций сохраняющих 1,

3) – класс самодвойственных функций,

4) – класс монотонных функций,

5) – класс линейных функций.

Рассмотрим классы:

1) f (0, 0, … 0) = 0

2) f (1, 1, … 1) = 1 т. е. если подставить 0-е значение аргументов, то функция =0 или 1

3)

4) Пусть х_­1i=1, a x_1j=0. Тогда x_1i>x_1j. Функция f(x₁, x₂, … x_n) является монолитной, если для всех случаев, когда во всех наборах выполняется неравенство

Например:

видно, что и , то выполняется:

5) Если , где , то f(x₁,x₂,…,x_n) – называется линейной логической функцией

Пример:

		Сохр. «0»	Сохр. «1»	самодвой-ственные	монотонные	линейные
и		+	+	-	+	-
или		+	+	-	+	-
инверсия		-	-	+	-	+
штрих Шеффера	\	-	-	-	-	-

Из таблицы на основании теоремы о ФП СЛФ:

1) - избыточная СЛФ, но наиболее распространённая (каноническая СЛФ)

2)

3) безызбыточные СЛФ, есть другие безызбыточные ФПСЛФ

4) х₁\х₂

Технический аналог булевой функции – комбинационная схема.

Вывод: для синтеза любой комбинационной схемы достаточно иметь лишь технические устройства, соответствующие ФП СЛФ.

Основные законы и правила.

А. Преобразование выражений в булевой алгебре.

№	логическое сложение	логическое умножение	название закона
	х+0=х		-
	х+1=1		-
	х+х=х		закон идемпотентности
			-
		закон двойного отрицания
	х1+х2=х2+х1	х1х2=х2х1	коммутативный закон
	х1+х1х2=х1	х1(х1+х2)=х1	закон поглощения
			закон Де Моргана (правило)
	(х1+х2)+х3= =х1+(х2+х3)= =х1+х2+х3	(х1х2)х3=х1(х2х3)= =х1х2х3	ассоциативный закон
	х1+х2х3= =(х1+х2)(х1+х3)	х1(х2+х3)= =х1х2+х1х3	дистрибутивный закон (распределительный)

примем обозначения:

В. Теорема разложения.

Любую переключательную функцию n аргументов можно представить в следующем виде:

Следствие:

Теорема о СДНФ (совершенная дизъюнктивная нормальная форма):

Всякую переключательную функцию можно представить:

Доказать самостоятельно.

Теорема о СКНФ (совершенная конъюнктивная нормальная форма):

Доказательство:

ч. т. д.

Пример: Пусть переключательная функция f(x₁,x₂,x₃) задана таблицей

таблица истинности избыточна более чем в 2 раза.

Пример. Упростить логическое выражение

используя законы и правила булевой алгебры.

=

Задание 44. Упростить выражение

Задание 45. Упростить выражение

Задание 46. Привести выражение

к виду содержащему лишь операции и дизъюнкции.

Минимизация выражений в булевой алгебре.

Цель – упростить техническую реализацию (комбинационную схему)

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

Если 2 смежные вершины куба заменить ребром, то получим упрощение: возможен алгоритм.

II. Метод Квайна-Мак-Класки.

Определения:

Рангом конъюнкции называется число различных аргументов (с инверсией или без) входящих в конъюнкцию.

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

Кратчайшей ДНФ называют ДНФ с наименьшей, среди всех возможных ДНФ, длинной.

Минимальной ДНФ называется ДНФ у которой наименьший среди всех возможных ДНФ ранг конъюнкции.

Сокращённой ДНФ называется ДНФ состоящая из простейших конъюнкций.

* - отбрасываются члены сокр. ДНФ и проверяется истинность

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

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

Словесное представление логических функций.

Покажем на примере функции конъюнкции. Словесно эту функцию можно представить так: логическая функция принимает значение равное 1 лишь в том случае, когда все её аргументы равны 1.

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

Каждому набору аргументов ставится в соответствие значение функции и представляется таблицей. Если наборы аргументов упорядочены по возрастанию, то такая таблица называется таблицей истинности (ТИ).

Алгебраическое представление логических функций (в СДН и СКН формах).

Примем обозначение , где n – количество аргументов логической функции. Тогда любую логическую функцию (кроме F=0) можно представить в совершенной дизъюнктивной нормальной форме (СДНФ).

или в совершенной конъюнктивной нормальной форме (СКНФ)

Для логической функции, представленной ТИ, СДНФ строится следующим образом:

- выделяются наборы аргументов (строки ТИ) при которых функция равны 1;

- из аргументов каждого выделенного набора формируется соответствующая конъюнкция (аргументы, значения которых в наборе равны 0, входят в конъюнкцию с инверсией);

- сформированные конъюнкции соединяются знаком дизъюнкций.

При построении СКНФ порядок действий следующий:

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

- из аргументов каждого выделенного набора формируется соответствующая дизъюнкция (аргументы, значения которых в наборе равны 1, входят в дизъюнкцию с инверсией);

- сформированные дизъюнкции соединяются знаками конъюнкций.

Пример. Представить логическую функцию F₁(x₁,x₂,x₃), заданную таблицей истинности, в СДНФ и СКНФ.

Задание 47. Логическая функция F₂(x₁,x₂,x₃) задана ТИ. Представить функцию в СДНФ и СКНФ.

Задание 48. Представить логическую функцию таблицей истинности, а также в СКНФ и СДНФ.

Представление логических функций картами Карно.

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

Например, для 2-х переменных ТИ и КК будут выглядеть следующим образом:

Поиск по сайту: