Поняття про інформацію та її види. Три підходи до вивчення теорії інформації. Порівняння аналогової та цифрової обчислювальної техніки
Інформацію назив. відомістю, які можна отримати, передати, керувати, обробляти, зберігати.
Інформація є міра різноманітності або однорідності в матеріалі , речовині та енергії у просторі та часі.
Порівняння АТ та ЦТ
1. Точність АТ=102/1=103/1=104/1
Відношення Сигнал/Завада ЦТ=1010/1
2. Швидкодія
АТ властивий паралельний алгоритм роботи.
3. Універсальність
ЦОМ – універсальні,спеціалізовані ,а АОМ – спеціалізовані
4. Вартість
EMBED Visio.Drawing.11



3 підходи до вивчення теорії інформації:
1. Структурна теорія інформації
2. Статистична (поняття ентропії)
3. Семантична (Акад. Маркевич О.О. Вартість інфи тим вища, чим більше змін робиться в сфері керування)




Поясніть, у чому полягає зміст та значення теореми Котельникова.
При дискретизации сигналов приходится решать вопрос о том, как часто следует производить отсчеты функции, т.е. каков должен быть шаг дискретизации.
Кожний процес має обмеження на частоту спектра Fm.
Согласно теореме В.А.Котельникова, если функция s(t) не содержит частот выше некоторой Fm, то она полностью определяется своими мгновенными значениями в моменты времени, отстоящими друг от друга на величину 1/(2Fm ), т.е.
EMBED Equation.2 ,
где k - порядковый номер отсчета функции; ?t = 1/(2Fm) - шаг дискретизации по времени,sk = s(tk) - мгновенные значения сигнала s(t) в k-ой отсчетной точке tk = k?/?m = k/(2Fm) = k??t.
Из этой теоремы следует, что для однозначного представления функции с ограниченным спектром на интервале времени Т достаточно иметь некоторые n значений этой функции, где
n = T / ?t = 2FmT.
При выполнении этого равенства (условия) непрерывная и дискретная функции обратимы между собой, т.е. тождественны. Таким образом, произвольный сигнал, спектр которого не содержит частот выше Fm может быть представлен в виде последовательности импульсов, амплитуда которых равна значению исходного сигнала в дискретные моменты времени k??t= а интервалы между ними ?t = 1/(2Fm).
Из приведенной выше формулировки теоремы Котельникова однозначно следует, что для выбора оптимального шага дискретизации необходимо предварительно провести количественные оценки всех значащих гармоник спектрального разложения исходного непрерывного сигнала, для нахождения величины Fm, т.е.?m.




Основні ознаки алгоритму. Навести підхід до формального визначення алгоритму. Універсальні формальні алгоритмічні системи. Основна гіпотеза теорії алгоритмів.
Совокупность правил перехода автомата из одного состояния в другое в зависимости от входной информации и внутренних состояний автомата называется алгоритмом преобразования (переработки) информации. Вообще алгоритмом называется конечная совокупность точно сформулированных правил решения какойто задачи.
Можно привести еще одно определение понятия алгоритма. Алгоритм - это строго формальное описание конечной последовательности некоторых "элементарных" действий или процедур, которую надо выполнить над исходными данными и над промежуточными результатами, возникшими в ходе выполнения этих операций, для того чтобы прийти к информации, являющейся результатом обработки исходных данных.
Ознаки алгоритму:
Справа з даними (вхідні, провідні, вихідні)
Пам'ять для зберігання
Алгор. виконується по кроках, к-ть яких скінченна
Алгор. мусить бути детермінований
Результативність
Більш строге визначеня можна дати в рамках теорії Формальних Алгор. Системах (ФАС):
Рекурсивні ф-ції
Машина Тюрінга
Машина Поста
Нормальні алгор. Маркова
Схема Колмагорова
Цифрові автомати Мілі та Мура
Сист Черкаського
Основна гіпотеза теорії алгоритмів: будь-який алгор.. може бути використаний із допомогою ФАС.
Перечисленные, в этой главе понятия относятся к абстрактной теории цифровых автоматов, в которой рассматриваются автоматы, имеющие один вход и один выход. Поэтому применить все это к ЭВМ можно только в самом общем виде, ограничивая круг рассматриваемых устройств устройствами, входящими в состав процессора, или же в случае когда рассматривается вообще некоторый узел ЭВМ, предназначенный для достаточно элементарной обработки цифровой информации. В самом деле, в зависимости от команд, подаваемых устройством управления процессора, арифметическо-логическое устройство осуществляет соответствующие действия (изменение внутренних состояний) с выдачей необходимых результатов. Однако изменение внутренних состояний всей ЭВМ в целом носит настолько сложный характер, что этот процесс невозможно отобразить в аналитическом виде. Поэтому понятие цифрового автомата целесообразно использовать применительно к алгоритмам, реализующим некотору. программу или последовательность операций. При этом каждая операция представляется как элементарное действие, осуществляемое в процессе переработки информации.
Автомат. Класифікація автоматів. Поняття про модель цифрового автомата типу Мілі та Мура.
Цифровой автомат это устройство, характеризующееся набором некоторых внутренних состояний A = {a1(t), a2(t), ..., an(t)}= в которые оно попадает под воздействием входных сигналов и команд программы решения задачи.
Пусть имеется автомат с одним входом и одним выходом:
A = {ai(t)}
z(t) ?(t)
Рис.1.3. Цифровой автомат
Цифровые автоматы могут быть с "жесткой", или схемной, логикой и с логикой, хранимой в памяти. Различают два класса автоматов: асинхронные и синхронные.
Синхронный автомат характеризуется тем, что функционирует под управлением тактовых (или синхронизирующих) сигналов - ТС, с постоянной длительностью tТС и постоянной частотой fТС, если квантование времени равномерное. Такт (квант) времени ti совмещается с фронтом i-того сигнала ТС. Входные сигналы могут воздействовать на автомат лишь при наличии сигнала ТС и не изменяются в течение tТС. Период следования сигналов ТС должен быть больше или равен времени, которое необходимо реальному автомату для перехода из одного состояния в другое. Когда рассматривается абстрактный автомат, то считается, что изменение внутренних состояний автомата происходит в интервалы времени между смежными ТС, а выходные сигналы формируются по фронту очередного ТС.
В асинхронных автоматах длительность интервала времени, в течение которого остается неизменным состояние входных сигналов, является величиной переменной и определяется временем, которое необходимо автомату для установки соответствующих выходных сигналов и завершения перехода в новое состояние. Следовательно, асинхронный автомат должен формировать каким-нибудь подходящим способом сигнал о завершении очередного такта, по которому текущие входные сигналы могут быть сняты, после чего может начаться следующий такт, т.е. возможно поступление новых входных сигналов.
Как отмечалось в главе 1, абстрактный автомат с одним входом и одним выходом можно представить следующим образом:

A
X Y
Для задания конечного автомата фиксируются три конечных множества (алфавита):
- множество возможных входных сигналов:
X = {x1, x2, ..., xm};
- множество возможных выходных сигналов:
Y = {y1, y2, ..., yk};
- множество возможных внутренних состояний автомата:
A = {a0, a1, ..., an}.
На этих множествах задают два логических оператора:
- функцию переходов f, определяющую состояние автомата a(t + 1) в момент дискретного времени t + 1 в зависимости от состояния автомата a(t) и значения входного сигнала x(t) в момент времени t:
a(t + 1) = f[a(t), x(t)]; (10.1)
- функцию выходов ?, определяющую зависимость выходного сигнала автомата y(t) от состояния автомата a(t) и входного сигнала x(t) в момент времени t:
y(t) = ? [a(t), x(t)]. (10.2)
Кроме того, на множестве состояний автомата фиксируют одно из внутренних состояний а0 в качестве начального состояния.
Понятие состояние автомата используется для описания систем, выходные сигналы которых зависят не только от входных сигналов в данный момент времени, но и от некоторой предыстории, т.е. сигналов, которые поступали на входы системы ранее. Следовательно, цифровые автоматы относятся к последовательностным схемам, которые, как уже отмечалось, обладают памятью. Понятие состояние автомата соответствует некоторой памяти о прошлом, поэтому ввод этого понятия позволяет устранить время как явную переменную и выразить выходные сигналы как функцию состояний и входных сигналов.
Работу абстрактного автомата следует рассматривать применительно к конкретным интервалам времени, т.к. каждому интервалу дискретности t будет соответствовать свой выходной сигнал y(t). Следовательно, функционирование автомата рассматривается через дискретные интервалы времени конечной продолжительности. В абстрактной теории цифровых автоматов считается, что входные сигналы воздействуют на синхронный автомат в момент начала каждого i-того интервала (кванта) времени, выделенного соответствующим синхроимпульсом (тактом), а изменение внутренних состояний автомата происходит в интервалы времени между смежными синхроимпульсами, когда нет воздействия входных сигналов.
Операторы, описывающие работу автомата, обычно задают таблицей переходов и таблицей выходов.
В таблице переходов показывают в какое состояние попадает автомат от того или иного входного сигнала. В таблице выходов показывают какой выходной сигнал генерирует автомат в зависимости от типа входного сигнала и текущего состояния автомата.
К примеру, рассмотрим таблицы переходов и выходов некоторого автомата.
Таблица переходов автомата
Таблица выходов автомата
В клетку таблицы переходов, находящуюся на пересечении столбца с буквой аi и строки с буквой xj, записывается состояние автомата, в которое он переходит из состояния аi при подаче на вход сигнала xj. В аналогичную клетку таблицы выходов записывается выходной сигнал yi, который формируется автоматом при таком переходе.
Операторы переходов и выходов могут быть заданы одной таблицей, по которой однозначно определяются переходы и выходы автомата.
Таблица переходов и выходов автомата
большую наглядность обеспечивает задание конечных автоматов с помощью графов или диаграмм состояний.
Граф автомата состоит из узлов, соединенных ветвями. Узлы (кружки на схеме графа) отождествляют внутренние состояния автомата. Каждая ветвь графа, т.е. ориентированная линия, стрелка которой указывает следующее состояние автомата, отмечается входным сигналом, вызывающим в автомате соответствующий данной ветви переход, и выходным сигналом, который возникает при этом переходе. Входной и соответствующий ему выходной сигналы разделяются на чертеже запятой или косой чертой. Если некоторый входной сигнал не меняет состояния автомата, то соответствующая ветвь замыкается на кружке (узле), из которого она выходит.
Поскольку таблица состояний и граф (диаграмма) состояний несут одну и ту же информацию, их можно преобразовать друг в друга. Каждое состояние представляется кружком, а каждый элемент таблицы преобразуется в отрезок ориентированной линии, соединяющей соответствующие кружки. Процедура обратного преобразования очевидна.
В настоящее время в классе синхронных атоматов рассматривают, в основном, два типа автоматов: автомат Мили и автомат Мура.
Графа атомата Мили, заданного вышеприведенными таблицами, отражен на рис. 10.1. Закон функционирования автоматов Мили может быть задан следующим образом:
a(t + 1) = f[a(t), x(t)];
y(t) = ? [a(t), x(t)],
где t = 1, 2, .....
Отличительная особенность автоматов Мили состоит в том, что их выходные сигналы в некоторый момент времени не зависят как от состояния автомата, так и от значения входного сигнала в этот же момент времени.

Рис. 10.1. Граф автомата Мили.
У автоматов Мура выходные сигналы в момент времени t однозначно определяются состоянием автомата в этот же момент времени и в явном виде не зависят от значения входных сигналов xi(t).
Функции переходов и выходов автомата Мура, заданного на множестве входных сигналов X, множестве внутренних состояний A = {a0, a1, ,an} и множестве выходных сигналов Y, можно записать в виде
a(t + 1) = f[a(t), x(t)], (10.3)
y(t) = ? [a(t)]. (10.4)
эти операторы удобно задавать отмеченной таблицей переходов.
Такие таблицы строятся так же, как и таблицы переходов автомата Мили, но над символами каждого внутреннего состояния записываются выходные сигналы, которые выдает автомат в данном состоянии.

Отмеченная таблица переходов автомата
Граф автомата Мура, заданного этой таблицей, приведен на рис. 10.2.
На этом рисунке состояния автомата обозначаются сиволами bi.
На графах автомата Мура значения выходных сигналов записываются около узлов.

Рис. 10.2. Автомат Мура.
Между автоматами Мили и Мура существует соответствие, позволяющее преобразовать закон функционирования одного из них в другой или обратно. Автомат Мура можно рассматривать как частный случай автомата Мили, имея в виду, что последовательность состояний выходов автомата Мили опережает на один такт последовательность состояний выходов автомата Мура, т.е различие между автоматами Мили и Мура состоит в том, что в автоматах Мили состояние выхода возникает одновременно с вызывающим его состоянием входа, а в автоматах Мура - с задержкой на один такт, т.к в автоматах Мура входные сигналы изменяют только состояние автомата.
Помимо автоматов Мили и Мура выделяют еще, так называемый, совмещенный автомат - С-автомат. Абстрактный С-автомат можно представить в виде устройства с одним входом, на который поступают входные сигналы X, и двумя выходами, на которых появляются выходные сигналы Y и U.
A
Y рис. 10.3
X
U
Здесь X - входной алфавит; A - множество состояний; Y - выходной алфавит первого типа; U = {u1(t) ... um(t)} - выходной алфавит второго типа.
Отличие С-автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов ?1 и ?2, каждая из которых характерна для этих моделей в отдельности. Этот автомат можно описать следующей системой уравнений:
a(t+1) = f [a(t), x(t)]; (10.5)
y(t) = ?1[a(t), x(t)];
u(t) = ?2[a(t)].
Выходной сигнал u = ?2(as) выделяется все время, пока автомат находится в состоянии as. Выходной сигнал yk = ?1(as, xn) выдается во время действия входного сигнала xn при нахождении автомата в состоянии as. От С-автомата легко перейти к автоматам Мили или Мура (с учетом возможных сдвигов во времени на один такт), так же как возможна трансформация автомата Мили в автомат Мура и наоборот.
Буква, слово, алфавіт. Переваги, фізична реалізація та форми представлення дволітерних алфавітів.
Буква – сигнал, який поступає на вхід ЦА в момент часу ti (проміжна, вихідна)
Слово – послідовність вхідних букв.
Алфавіт – це множина всіх букв, які відрізняються.

A
X Y
Для задания конечного автомата фиксируются три конечных множества (алфавита):
- множество возможных входных сигналов: X = {x1, x2, ..., xm};
- множество возможных выходных сигналов: Y = {y1, y2, ..., yk};
- множество возможных внутренних состояний автомата:A = {a0, a1, ..., an}.
Причини застосування двозначного алфавіту:
У внутрішньому алфавіті кожна буква з двох являє зоною чи смугою.
EMBED Visio.Drawing.11
Відрізняються стани не тільки кількісно, але і якісно.
Арифметичні та логічні операції виконуються простіше в двохбуквених алфавітах.
Простіше реалізовуються пристрої памяті.
Фізичне представлення

Форми представлення
EMBED Visio.Drawing.11
EMBED Visio.Drawing.11
Потенціальна (статична) 4. Фазова

EMBED Visio.Drawing.11
EMBED Visio.Drawing.11
Імпульсна (динамічна)
EMBED Visio.Drawing.11

EMBED Visio.Drawing.11
EMBED Visio.Drawing.11
Частотні

Алгебра логіки. Поняття про аналіз і синтез. Операції суперпозиції та перестановки.
Логической основой цифровых автоматов или компьютеров является алгебра логики (булева алгебра) - одна из основных частей математической логики. Теория логических основ цифровых автоматов чрезвычайно насыщена достаточно специфическими терминами, понятиями. Поэтому в этой главе и во всех последующих будет приведено много определений этих понятий. Причем, нередко для одного и того же понятия будет использовано несколько определений для более четкого понимания его сущности и взаимосвязи с другими специфическими понятиями теории логических основ цифровых автоматов. Итак, приведем первый вариант определения понятий логической переменной и логической функции.
Функция f(x1, x2, ..., xn) называется логической (переключательной), или булевой, если она, так же как и ее аргументы xi, может принимать только два значения: 0 или 1.
Логическая (булева) переменная эта такая величина x, которая может принимать только два значения: 0 или 1.
Таким образом, логические функции, их аргументы и просто логические переменные могут принимать только два значения 0 или 1. Причем, в этих случаях цифры 0 и 1 являются символами состояния, а не числами. Алгебра логики является алгеброй состояний, а не алгеброй чисел, поэтому эту алгебру называют также алгеброй высказываний.
Совокупность значений аргументов логической функции называется набором (или точкой) и может обозначаться, в частности, как х1, х2,..., хn, где xi равно нулю или единице (i = 1, 2, ..., n). Очевидно, что набор значений аргументов фактически представляет собой некоторое двоичное число. Каждому набору значений аргументов приписывается номер, равный двоичному числу, которое соответствует значению данного набора. Например, для четырех аргументов 0, 0, 0, 0 - нулевой набор; 0, 0, 0, 1 - первый набор;0, 0, 1, 0 - второй набор; 1, 0, 1, 0 - десятый набор и т.д.
Суперпозиція
Подстановка в логическую функцию вместо ее аргументов других логических функций называется суперпозицией.
x?y?z=x? (y?z), xyz=x(yz), x?y?z?x?(y?z)
Перестановка
x?y= y?x, x?y=y?x, x?y?y?x
Змінна, набір, функції алгебри логіки (ФАЛ) нуля, однієї та двох змінних
Совокупность значений аргументов логической функции называется набором (или точкой) и может обозначаться, в частности, как х1, х2,..., хn, где xi равно нулю или единице (i = 1, 2, ..., n). Очевидно, что набор значений аргументов фактически представляет собой некоторое двоичное число. Каждому набору значений аргументов приписывается номер, равный двоичному числу, которое соответствует значению данного набора. Например, для четырех аргументов 0, 0, 0, 0 - нулевой набор; 0, 0, 0, 1 - первый набор;0, 0, 1, 0 - второй набор; 1, 0, 1, 0 - десятый набор и т.д.
Таким образом, логическая функция (функция алгебры логики) это функция f(x1, x2, ..., xn) которая принимает значение 0 или 1 на наборе логических переменных x1, x2, ..., xn. Каждой логической функции данного набора аргументов, также принято приписывать номер: 0, 1, 2,.......
Любая логическая функция n аргументов определена на 2n наборах, т.е. может иметь 2n наборов. Число различных логических функций n аргументов конечно и равно 2 EMBED Equation.2 .
Неполностью определенная логическая функция n переменных, это функция, заданная на числе наборов меньшем 2n. Для наборов, на которых функция не определена, ее значение можно принять произвольным.
Например, для одного аргумента имеем 21, т.е. 2 набора и 22 , 4, т.е. четыре логические функции от одной переменной, которые приведены в таблице 7.1.
Т а б л и ц а 7.1
В связи с тем, что функция f0(x) равна единице при любых значениях аргумента, то эта функция называется абсолютно истинной (константа единицы), тогда функция f1(x) - абсолютно ложная функция (константа нуля). Функция f2(x), повторяющая абсолютное значение логической переменной, - тождественная функция: f2(x) ? x.
Функция f3(x), принимающая значение, обратное значению x, - логическое отрицание (инверсия), или функция НЕ (NOT), которая обозначается одним из следующих способов:
f3(x) = ? x = ?x.
Логическое отрицание или инверсия некоторой логической переменной, например переменной А, это также логическая переменная, принимающая значение обратное значению переменной А, и обозначаемая как ?А. Если А =1, то ?А = 0, если же А = 0, то ?А = 1. Но нужно учесть, что часто посредством отрицания, т.е. инверсии переменной просто обозначают случай, когда ее значение равно нулю.
ФАЛ 2-х
Дизъюнкция (логическое сложение) или функция ИЛИ (OR) - это функция f7(x1, x2), которая истинна тогда, когда истинна хотя бы одна из ее переменных. Условные обозначения этой функции:
f7(x1, x2) = x1 + x2 = x1 ? x2 = x1 ! x2
Это читается следующим образом: функция истинна, т.е. равна единице, когда аргумент x1 = 1, т.е. истинен, или аргумент x2 = 1, или же оба аргумента истинны одновременно.
Т а б л и ц а 7.2
Конъюнкция (логическое умножение) или функция И (AND) - это функция f1(x1, x2), которая истинна тогда, когда все ее переменные одновременно истинны. Эту функцию условно обозначают следующим образом:
f1(x1, x2) = x1 ? x2 = x1 ? x2 = x1 & x2
Это читается следующим образом: функция истинна, т.е. равна единице, когда оба аргумента одновременно истинны, т.е. равны единице.
Функция (штрих) Шеффера или функция И-НЕ - это функция f14(x1, x2), которая ложна тогда, когда все переменные истинны. Условное обозначение этой фнкции:
f14(x1, x2) = x1/x2
Это читается следующим образом: функция ложна, т.е. равна 0, когда оба аргумента одновременно истинны, т.е. равны единице, и функция истинна, т.е. равна единице, когда или оба аргумента одновременно ложны, или же хотя бы один из них ложен.
Функция (стрелка) Пирса (Вебба) или функция ИЛИ-НЕ - это функция f8(x1, x2), которая истинна только тогда, когда все переменные ложны. Условное обозначение этой функции:
f8(x1, x2) = x1 ? x2 = x1 O x2.
Это читается следующим образом: функция ложна, т.е. равна 0, когда хотя бы один из ее аргументов истинен, или же оба одновременно истинны, т.е. равны единице, и функция истинна, т.е. равна единице, когда оба аргумента одновременно ложны.
Импликация или функция ЕСЛИ-ТО (IF-THEN) это функция f13(x1, x2), которая ложна тогда и только тогда, когда x1 истинно и x2 ложно. Аргумент х1 называется посылкой, а х2 - следствием. Ее условное обозначение
f13(x1, x2) = x1 ? x2.
Исключающее ИЛИ (XOR) - это функция f6(x1, x2), которая обозначается знаком ?. Эта операция, как видно из таблицы, реализует функцию неравнозначности, т.е. фактически реализуется процедура суммирования по модулю 2, которая обозначается знаком ?:
f6(x1, x2) = x1 ? x2 = x1 ? x2
Все рассмотренные функции являются элементарными.
Из всех приведенных выше определениий ясно, что в алгебре логики все знаки действий: ? или &, ? или +, ?, ? и т.д, в отличии от обыкновенной алгебры, являются знаками логических связок, т.е. логических действий, а не знаками арифметических действий.
Введем еще три специфических понятия алгебры логики.
Две функции считаются равносильными друг другу, если они принимают на всех возможных наборах своих аргументов одни и те же значения.
Логическая переменная xi действительна, если значение логической функции f(x1, x2, ..., xn) изменяется при изменении xi. В противном случае эта переменная для данной функции фиктивна, т.е. не является ее аргументом.
Необходимость ввода этих двух последних понятий возникла по следующей причине. При анализе некоторой неизвестной логической функции (логической схемы), для которой необходимо сформировать аналитическое выражение, не все подключаемые для этого анализа логические переменные могут быть аргументами этой функции, что и выявляется в итоге проведенного анализа.
Как будет показано в дальнейшем, любые логические операции над логическими переменными можно свести к определенной совокупности элементарных логических функций, например, таких как И, ИЛИ, НЕ и исключающе ИЛИ.
Элементарные логические операции в компьтерах выполняются также над двоичными числами, по разрядно. Рассмотрим несколько простых примеров выполнения логических операций над двумя двоичными числами:
И ИЛИ Искл. ИЛИ НЕ
01011010 0101010 0101010 01011010
11110000 1111000 1111000 10100101
01010000 1111010 1010010
Подстановка в логическую функцию вместо ее аргументов других логических функций называется суперпозицией.
Система логических функций называется функционально полной, если с помощью функций, входящих в эту систему, применяя операции суперпозиции и подстановки, можно получить любую сколь угодно сложную логическую функцию.
Основні властивості ФАЛ за Постом. Методи виявлення ФАЛ із цими властивостями.
Для побудови ПС(повна система) ФАЛ(Функція Алгебри-Логіки) яка має хоч би одну функцію, яка не зберігає константу 0, не зберігає константу 1, нелінійна, немонотонна, несамодвоїста.
Якщо функція на нульовому наборі змінних дорівнює 0, то ф-ція зберігає конст. 0.
Якщо функція на одиничному наборі змінних дорівнює 1, то ф-ція зберігає конст. 1.


ФАЛ назив. монотонною, якщо при будь-якому зростанні кількості 1 у послідовності сусідніх( тобот на тих, які відрізняються тільки в одному розряді) на наборі змінних значення функції не змінюється або збільшується.


ФАЛ назив. самодвоїстою, якщо на кожній парі протилежних наборів (х0,х1,..) та (#х0, #х1,..) вона приймає протилежні значення.
EMBED Equation.3
ФАЛ назив. лінійною , якщо її можна зобразити поліномом 1 порядку в базисі Жегалкіна без добутків змінних ВС?АС?1 – нелінійна
А?С?1 - лінійна
EMBED Equation.3
Приклад
нелінійна
лінійна
Базис Жегалкіна. Основні тотожності. Синтез комбінаційних схем на прикладі однорозрядних суматорів на два та на три входи.
EMBED Equation.3
{&, ?, 1}
Реалізація комбінаційних схем
Однорозрядний суматор на 2 входи
EMBED Visio.Drawing.11
EMBED Visio.Drawing.11
S=A?B
P=AB




Однорозрядний суматор на 3 входи
S=A?B?C
P=?ABC?A?BC?AB?C?ABC=(A?1)BC?A(B?1)C?AB
EMBED Visio.Drawing.11
(C?1) ?ABC=ABC?BC?ABC?AC?ABC?AB?ABC=
=BC?AC?AB

EMBED Visio.Drawing.11



Базис Буля. Основні тотожності.
EMBED Equation.3
{&, ?, ?}
Рассмотрим основные законы, аксиомы и теоремы алгебры логики
Некоторые законы обычной алгебры применимы и к алгебре логики. Например:
Закон коммутативности:
для умножения АВ = ВА
для сложения A ? B = B ? A
Закон ассоциативности:
для умножения A(BC) = (AB)С
для сложения A ? (B ? С) = (A ? B) ? С
Закон дистрибутивности умножения по отношению к сложению:
A(B ? С) = AB ? AC
В алгебре логики действует также закон дистрибутивности сложения по отношению к умножению:
A ?BС = (A ? B)(A ? С)
Алгебра логики имеет ряд специфических аксиом и теорем, основные из которых, необходимые для анализа и синтеза логических цепей или схем, приведены ниже.

В алгебре логики широко используется также специфический закон склеивания:
Форми завдання ФАЛ у базисі Буля. Класифікація аналітичних форм завдання ФАЛ у базисі Буля.
Таблиці
Скорочені Квадратні таблиці


2. Аналітичний
EMBED Visio.Drawing.11
Досконала – будь-які нормальні форми можуть бути дизюктивними та конюктивними, кожний терм має усі змінні.
Мінімальна – яка має мінімальну к-ть букв.
Скорочена – коли хоча б 1 терм не має всіх змінних.
Найкоротша – має мінімальну к-ть термів, змінних, букв.

Например, если некоторая, заданная таблично, функция f(x1, x2, x3) принимает значение единицы на наборах с номерами 0, 3, 4 и 6, то ее можно представить следующим образом:
f(x1, x2, x3) = ?F(0, 3, 4, 6),
1
или f(x1, x2, x3) = ? F(0, 3, 4, 6),
Если эта же функция на наборах 1, 2, 5, 7 - принимает значение 0, то ее можно представить так:
f(x1, x2, x3) = ?F(1, 2, 5, 7),
0
или f(x1, x2, x3) = ? F(1, 2, 5, 7)
Такую форму записи называют числовой.
Первый вид такой формы используют когда функция представляется в СНДФ, а второй - когда в СНКФ.
Многие преобразования, выполняемые над логическими функциями, иногда удобно интерпретируются с использованием их геометрических представлений. Например, функцию двух переменных можно интерпретировать как некоторую плоскость, заданную в системе координат х1, х2. Если отложить по каждой оси единичные отрезки х1 и х2, то получится квадрат, вершины которого соответствуют комбинациям переменных.
x1?x2 x1 x1x2
?x2 x2

?x1?x2 ?x1 ?x1x2
Отсюда следует, что две вершины, принадлежащие одному и тому же ребру и называемые соседними, "склеиваются" по переменной, меняющейся вдоль этого ребра. Например,
?x1?x2 + x1?x2 = ?x2,
т.к, как нам уже известно, из свойств логических функций, что
?x1?x2 + x1?x2 = (?x1 + x1)?x2 = 1??x2 = ?x2
Для функций трех переменных геометрическое представление выполняют в виде трехмерного куба. Ребра куба поглощают вершины. Грани куба поглощают свои ребра и, следовательно, вершины.
В случае же четырех переменных - "четырехмерного" куба. В геометрическом смысле каждый набор переменных x1, x2, x3,...., xn можно рассмаривать как n-мерный вектор, определяющий точку n-мерного простанства. Поэтому все множество наборов, на которых определена функия n переменных, представляется в виде вершин n-мерного куба. Координаты вершин куба указываются в порядке, соответствующем порядку перечисления переменных в записи функции. Отмечая точками вершины, в которых функция принимает значение, равное единице, получаем геометрическое представление ФАЛ.
Проблема мінімізації у базисі Буля. Канонічна та загальна задачі мінімізації. Огляд методів розв’язання.
EMBED Equation.3
EMBED Visio.Drawing.11
1.
EMBED Visio.Drawing.11



2. Карта Карно
EMBED Equation.3

EMBED Visio.Drawing.11
EMBED Equation.3


EMBED Equation.3
3.
4. Метод глобального винесення за дужки:
EMBED Equation.3
11 букв
9 букв
8 букв
Чим більше винесення за дужки, тим менша швидкодія
5.Введення надлишковості з глобальним винесенням за дужки:
x1x2x3?x1x3x4x5?x1x2x4x6?x4x5x6 = – 14 букв
=x1x2(x1x3?x4x6) ?x4x5(x1x3?x4x6)=(x1x3?x4x6)(x1x2?x4x5) – 8 букв

Особливості застосування методу мінімізації Квайна-Мак-Класкі-Петріка в базисі Буля.
Метод получения сокращенной дизъюнктивной нормальной формы логической функции называется методом Квайна.
При минимизации по методу Квайна в базисе 1 предполагается, что исходная функция задана в СНДФ.
Напомним, что импликанта функции - это некоторая логическая функция, обращаемая в ноль при наборе переменных, на которых сама функция также равна нулю.
Поэтому любой минтерм в составе СНДФ, или группа минтермов, соединенных знаками дизъюнкции, являются импликантами исходной НДФ.
Первичная или простая импликанта функции - это импликанта типа элементарной конъюнкции некоторых переменных, никакая часть которой уже не является импликантой данной функции.
Дизъюнкция простых импликант, ни одну из которых исключить нельзя, называется тупиковой НДФ заданной функции. Некоторые функции имеют несколько тупиковых форм. Тупиковые формы, содержащие наименьшее количество букв, будут минимальными.
Задача минимизации по методу Квайна состоит в попарном сравнении всех импликант, входящих в СНДФ, с целью выявления возможности поглощения какой-то переменной:
Fxi ? F?xi = F
Таким образом, удается снизить ранг термов. Эта процедура проводится до тех пор, пока не останется ни одного члена, допускающего поглощение с каким-либо другим термом. Термы, подвергшиеся поглощению, отмечаются. Неотмеченные термы представляют собой первичные импликанты.
Полученное логическое выражение не всегда оказывается минимальным. Поэтому исследуется возможность дальнейшего упрощения. Для этого составляется таблица, в строках которой записываются найденные первичные импликанты, а в столбцах указываются термы исходного уравнения. Клетки этой таблицы отмечаются в случае, если первичная импликанта входит в состав какого-либо терма. После этого задача упрощения сводится к тому, чтобы найти такое минимальное количество первичных импликант, которые покрывают все столбцы.
В этом методе используются операции неполного склеивания (полным склеиванием, как нам известно, будет:xy ? x?y = x) и поглощения (x ? xy = x). Применяемая в методе Квайна операция неполного склеивания определяется формулой: xy ? x?y = x ? xy ? x?y. Заметим, что в правой части равенства, кроме члена ч, полученного в результате полного склеивания, остаются оба члена, участвующие в склеивании.
Теорема Квайна. Если в совершенной дизъюнктивной нормальной форме логической функции провести все операции неполного склеивания и затем все операции поглощения, то в результате получается сокращенная дизъюнктивная нормальная форма этой функции, т.е. дизъюнкция всех ее простых импликант.
Метод Квайна выполняется в несколько этапов и сокращенную НДФ удобно находить в следующей последовательности.
Провести в СНДФ функции все возможные операции склеивания конституент единицы. В результате этого образуются произведения, содержащие (n - 1) букв. Подчеркнем, что склеиваться могут только произведения с одинаковым числом букв. Поэтому после этой процедуры производится операция поглощения, а затем выполняются все возможные склеивания членов с (n - 1) буквой.
После этого проводится поглощение членов с (n - 1) буквой и вновь выполняется операция склеивания членов с числом букв, равным (n - 2), и т.д.
Пример. Найти сокращенную дизъюнктивную нормальную форму логической функции, заданной таблично.
Представим функцию в совершенной дизъюнктивной нормальной форме
f(x, y, z) =?xyz ? x?y?z ? x?yz.
В правой части полученного выражения можно выполнить только одно склеивание: второго члена с третьим по переменной z. При этом получим
f(x, y, z) = x?y ??xyz ? x?y?z ? x?yz.
Произведение x?y поглощает члены x?y?z b x?yz:
f(x, y, z) = x?y ??xyz.
Это выражение является сокращенной дизъюнктивной нормальной формой заданной логической функции, так как дальнейшее применение склеивания и поглощения невозможно.
Теперь рассмотрим процедуру минимизации более сложной функции с использованием импликативных матриц.
Предположим, что требуется найти минимальную НДФ логической функции, СНДФ которой определяется выражением:
f(A, B, C, D) =?ABCD ??A?BCD ? A?BCD ? A?B?CD ? A?B?C?D ??A?B?C?D
Построим для этой функции импликантную матрицу, представляющую собой таблицу, в вертикальные и горизонтальные входы которой записываются все конституенты единицы, т.е. все минтермы, и все простые импликанты заданной функции соответственно.
Для нахождения простых импликант мы должны провести вначале процедуру неполного склеивания. Чтобы быстрее находить члены, которые склеиваются друг с другом, напомним, что склеиваться могут только соседние члены, т.е. такие члены, у которых число переменных с отрицаниями отличается на единицу. Проведем операции склеивания в следующем порядке:
- выполним все возможные склеивания 1-го члена с остальными;
- выполним все возможные склеивания 2-го члена с остальными, кроме 1-го;
- выполним все возможные склеивания 3-го члена с остальными, кроме 1-го и 2-го и т.д.
Запишем результат:
1* - 2* =?ABCD ??A?BCD = ?ACD(?B?B) =?ACD (по B);
2 - 3* =?BCD (по A);
3 - 4* = A?BD (по C);
4 - 5* = A?B?C (по D);
5 - 6* = ?B?C?D (по A).
Получили простые импликанты. После процедуры неполного склеивания выражение примет следующий вид:
f(A, B, C, D) =?ABCD* +?ACD +?A?BCD* +?BCD + A?BCD* + A?BD + A?B?CD* +A?B?C + A?B?C?D* +?B?C?D +?A?B?C?D*
Звездочками отмечены те члены, которые поглощаются произведениями, образовавшимися после склеивания. Теперь проведем операцию поглощения. Для каждой импликанты найдем конституенты единицы, т.е. минтермы, которые ею поглощаются, т.е. те конституенты, собственной частью которых является данная импликанта. Например, импликанта ?ACD поглощает конституенты ABCD, ?A?BCD, импликанта ?BCD - конституенты ?A?BCD, A?BCD и т.д.
?ABCD* +?ACD = ?ACD(1 + B) =?ACD;
?A?BCD* + A?BCD* +?BCD = ?BCD(1 + A +?A) =?BCD;
A?B?CD* +A?B?C = A?B?C(1 + D) =A?B?C;
A?B?C?D* +?A?B?C?D* +?B?C?D = ?B?C?D(1 + A +?A) = ?B?C?D;
Теперь рассмотрим принцип построения и использования импликантной матрицы на примере матрицы, приведенной в Таблице 8.2.
Клетки импликантной матрицы, образованные пересечением строк с импликантами и колонок с поглощенными ими конституентами, отметим крестиками.
Т а б л и ц а 8.2. Импликантная матрица
Чтобы получить минимальную НДФ заданной функции, достаточно найти минимальное число импликант, которые совместно накрывают крестиками все колонки импликантной матрицы.
Из таблицы следует, что в минимальную форму обязательно должны войти импликанты ?ACD и ?B?C?D, так как только они накрывают крестиками первую и шестую колонки таблицы.
Кроме того, импликанта ?ACD накрывает вторую, а импликанта?B?C?D - пятую колонки. Поэтому остается накрыть только третью и четвертую колонки таблицы. Для этого можно выбрать пары импликант ?BCD и A?BD; A?BD и A?B?C или одну импликанту A?BD. Если выбрать указанные выше пары импликант, члены ?BCD и A?BC оказываются лишними, так как импликанта A?BD одна накрывает третью и четвертую колонки таблицы. Таким образом, выбрав импликанту A?BD, получим минимальную НДФ заданной функции: f(A, B, C, D) =?ACD?A?BD??B?C?D.
На основании вышеизложенного сформулируем алгоритм получения минимальных НДФ логической функции.
1. Логическую функцию представляют в совершенной НДФ, применяя либо запись "по единицам" функции, если функция задана таблично, либо применяя операции развертывания, правила де Морганаи и другие формулы алгебры логики, если функция задана в произвольной аналитической форме.
2. В полученной совершенной НДФ проводят все операции неполного склеивания и поглощения. В результате получается сокращенная НДФ заданной функции.
3. Находят минимальные НДФ по импликантной матрице. Если количество членов в сокращенной НДФ невелико, то можно найти тупиковые формы методом испытания членов и выбрать среди них минимальные.
Заметим, что в ряде случаев минимальная НДФ совпадает с сокращенной. Например, сокращенная НДФ любой логической функции двух аргументов совпадает с минимальной, в чем нетрудно убедиться, проведя испытание членов в сокращенной НДФ любой функции, приведенной в Таблице 7.2.
Для того чтобы найти выражение заданной логической функции, наиболее удобное для синтеза логической схемы, следует, кроме МНДФ функции, получить также ее минимальную НКФ и выбрать из них ту, при технической реализации которой потребуется наименьшее количество логических элементов.
Один из алгоритмов получения МНКФ функции практически аналогичен описанному. В этом случае также вначале тем или иным способом формируется СНКФ функции. Далее находится сокращенная НКФ, по которой определяются тупиковые НКФ. Наконец, по ним находится МНКФ заданной функции. Только очевидно, что если функция задана таблично, то СНКФ формируется "по нулям" функции. Во всех же дальнейших процедурах минимизации учитывается, что в этом случае используются макстермы, т.е. элементарные суммы, а не элементарные призведения. Импликанта, в том числе и простая, - также элементарная сумма.
Операция неполного склеивания и поглощения для конъюнктивной формы определяется соответственно следующими соотношениями:
(x + y)(x +?y) = x(x + y)(x +?y),
x(x + y) = x,
а формулы развертывания имеют вид:
x = (x + y)(x +?y),
(x + y) = (x + y + z)(x + y +?z).
При испытании членов сокращенной НКФ исключают испытываемый член и в оставшееся выражение подставляют такие значения переменных, которые обращают исключенный член в ноль. Если при этом оставшееся выражение также будет равно нулю, то испытываемый член является лишним. Таким образом получают тупиковые НКФ, из которых выбирают МНКФ. Если полученная сокращенная НКФ содержит большое число членов, то МНКФ получают с помощью импликантных матриц по методике, аналогичной используемой для получения МНДФ.
Но можно использовать и другой способ получения МНКФ. Предварительно находится МНДФ функции. Потом от полученной МНДФ берется отрицание и после преобразования по формулам де Моргана получают МНКФ заданной функции.
Особливості та додаткові можливості застосування методу карт Карно.
Карты Карно (их разновидностью являются карты Вейча, которые строятся как развертки куба на плоскости), являются графическим представлением таблиц истинности. Поэтому они строятся или по таблице истинности анализируемой функции, или же по ее СНДФ.
Напомним, что каждая строка таблицы истинности, для которой функция равна единице, соответствует конкретному минтерму функции, представленной в СНДФ. Строка, для которой функция равна нулю является определенным макстермом функции, представленной в СНКФ.
Карта Карно представляет собой прямоугольник, разбитый на квадраты, число которых равно общему числу наборов для данной функции n переменных, т.е. оно равно 2n. Так, для функции четырех переменных квадратов будет 16, для пяти переменных - 32 и т.д. Каждый квадрат соответствует определенному набору или терму, причем наборы располагаются так, чтобы соседние наборы или термы, как по горизонтали, так и по вертикали, отличались бы только значением одной переменной: в одном квадрате она с инверсией, а в другом, соседнем - без. Функцию в СНДФ наносят на карту, отмечая, например, знаком 1 квадраты, соответствующие тем наборам, на которых функция равна единице, т.е. в СНДФ функции есть соответствующий минтерм. Остальные квадраты отмечаются знаком 0. Иногда в углу квадрата ставят номер набора. Такой способ используется, если функция задана числовым образом, но он неудо-бен для процедуры минимизации.
Логическая функция двух переменных, где а) - таблица истинности; а б) - карта Карно.
а б
В итоге карту Карно можно оформлять любым подходящим образом, но только так, чтобы каждый квадрат соответствовал определенному набору или терму и они, как уже отмечалось, располагались бы таким образом, чтобы соседние наборы или термы, как по горизонтали, так и по вертикали, отличались бы только значением одной переменной: в одном квадрате она с инверсией, а в другом, соседнем - без. Причем, надо учесть, что квадраты, расположенные на противополжных концах каждой строки или столбца, также являются соседними.
Перечислим последовательность действий, выполняемых для минимизации функции по методу Карно.
1) Исходная функция, подлежащая минимизации, должна быть представлена в НДФ. Затем ее надо представить в СНДФ. Или же составляется таблица истинности минимизируемой функции.
Как уже отмечалось, между строками таблицы истинности и клетками (ячейками) на карте Карно существует взаимно однозначное соответствие. Когда карта Карно составляется по СНДФ минимизируемой функции, то очевидно, что каждая переменная без отрицания заменяется ее значением 1, а с отрицанием - 0.
2) Затем строится карта Карно по принципу, описанному ранее. Представим систему координат, в которой, например, для функции двух аргументов по горизонтальной оси откладываются значения одного аргумента, а по вертикали - другого. На пересечении соответствующих координат получаем ячейку, куда записывается значение функции (0 или 1), соответствующее данному набору. Если функция представлена в СНДФ, то в ячейке соответствующей существующему минтерму записывается 1, а в ячейке несуществующего минтерма - 0.
3) После этого объединяются в группы смежные ячейки, в которых записаны единицы, следующим образом: объединяется обязательно четное количество соседних ячеек с единицами как по вертикали, так и по горизонтали. Причем, каждая ячейка с 1 может попасть одновременно в две группы, полученные в результате объединения единиц как по вертикали, так и по горизонтали.
4) Каждой такой группе ставится в соответствие новый минтерм для изображения исходной функции в форме минимальной НДФ.
5) Изображение каждого нового минтерма формируется по следующему алгоритму:
а) переменная, которая в каждой ячейке образованной группы имеет значение только 0, изображается ее инверсией;
б) переменная, которая в каждой ячейке группы имеет значение только 1, изображается без инверсии;
в) переменная, которая в пределах образованной группы меняет свое значение, не изображается, т.е. отбрасывается.
Таким образом, карту Карно можно рассматривать как графическое представление совокупности всех (сушествующих и не существующих) минтермов функции в СНДФ данного числа логических переменных.
На основании закона дистрибутивности и теорем (F +?A) = 1 и A??A = 0= а также A + 0 = A и A?0 = 0, два минтерма, находящиеся в соседних клетках, могут быть заменены одним новым минтермом, содержащим на одну переменную меньше. Если соседними являютя две пары минтермов, то такая группа из 4 минтермов может быть заменена новым минтермом, который содержит на две переменные меньше и т.д. В общем случае наличие единиц в 2n соседних клетках позволяет исключить n переменных.
При формировании на базе карты Карно новых минтермов для представления функции в минимальной НДФ, или же в минимальной НКФ, значения соответствующих переменных, равных 1, заменяются изображением переменных без отрицания, а при значениях равных 0 - с отрицанием.
Рассмотрим процесс минимизации на примере функции, заданной следующим логическим уравнением:
F(A,B,C,D) = BCD + ?ABD + ?BCD + A?B?C + A?CD + ?B?CD + ?ABC + ?A?B?C
Представим эту функцию в СДНФ:
F = BCD(A + ?A) + ?ABD(C + ?C) + ?BCD(A + ?A) + A?B?C(D + ?D) +A?CD(B + ?B) +
+ ?B?CD(A + ?A) + ?ABC(D + ?D) + ?A?B?C(D + ?D) = ABCD +?ABCD + ?AB?CD +
+ A?BCD + ?A?BCD + ?A?B?CD + A?B?C?D + AB?CD + ?A?B?C?D + ?ABC?D + ?A?B?CD.
Ниже изображена карта Карно, соответствующая рассматриваемой функции.
(?ABC)
(?A?B?C)
Минтермы функции образуют в карте четыре группы:
1) (?A?B?C); 2) (A?B?C); 3) (D); 4) (?ABC).
Следовательно
F = ?A?B?C + A?B?C + ?ABC + D = ?B?C(A + ?A) + ?ABC + D = ?B?C + ?ABC + D.
Но надо иметь в виду, что в общем случае функция может иметь несколько минимальных форм.
Пример. Найти минимальные дизъюнктивные и конъюнктивные нормальные формы функции:
f(A, B, C) = AB?C ? ABC ? A?BC ??A?B?C ??A?BC.
Карты Карно для данной функции выглядят следующим образом:
а) б)
Объединить единицы можно двумя вариантами (а и б). Этим вариантам соответствуют две минимальные дизъюнктивные формы:
f(A, B, C) = AB ? AC ??A?B,
f(A, B, C) = AB ??BC ??A?B.
Для получения минимальной конъюнктивной нормальной формы следует объединить нули логической функции. Две конституенты нуля, соответст-вующие клеткам, обведенным пунктирной линией (а), склеиваются по пере-менной С и представляются импликантой A ??B, а оставшийся ноль - конституентой?A?B?C. Поэтому минимальная НКФ заданной функции будет
f(A, B, C) = (A ??B) (?A ? B ? C).
Заметим, что минимальная НКФ функции содержит меньше букв, чем минимальные НДФ.
Как уже отмечалось, для того чтобы найти выражение заданной логической функции, наиболее удобное для синтеза логической схемы, следует, кроме минимальных дизъюнктивных нормальных форм, получить также минимальные конъюнктивные нормальные формы и выбрать из них ту, при технической реализации которой потребуется наименьшее количество элементов. Существует несколько методов получения минимальных конъюнктивных нормальных форм. Один из наиболее распространенных и удобных методов был продемонстрирован в предыдущем примере.
При наличии уже сформированной минимальной НДФ функции минимальную НКФ можно также, в частности, найти следующим образом:
берется от найденной минимальной НДФ отрицание и производится преобразование по формуле де Моргана. Тем самым получается минимальная НКФ функции. Например,
если МНДФ функции равна
f(A, B, C) =?AB + A?C,
то проведя отрицание и применив теорему де Моргана, получим МНКФ:
f(A, B, C) =?AB + A?C = (A +?B)(?A + C).
Каждая строка таблицы истинности, или ячейка на карте Карно, соответствует определенному значению логической функции для соответствующей комбинации значений аргументов, т.е. для соответствующего набора. В некоторых случаях известно, что какой-то набор появиться не может или же если он появится, то это значение функции, по тем или иным причинам, не существенно. Для таких случаев нет необходимости определять это значение функции по таблице истинности. В таких случаях говорят о неопределенных условиях. Карты Карно позволяют строить МНДФ и МНКФ и в этих ситуациях.
На карте Карно неопределенное условие обозначается прочерком в соответствующей ячейке. Такие ячейки могут произвольным образом включатья в группы при построении минимальных макстермов или минтермов. Любую из них можно включить как в группу единичных, так и в группу нулевых ячеек, или же вообще никуда не включать.В заключение обзора методов минимизации логических функций нужно отметить, что в настоящее время разработано много программ, позволяющих производить процедуру минимизации на компьютерах различными методами.
Позиційні цілочисленні СЧ. Порівняння та класифікація. Двійкова СЧ. Правила дії. Основні переваги.
Непозиционная система счисления - это система, для которой значение символа, т.е. цифры, не зависит от его положения в числе. К таким системам относится, в частности, римская система (правда с некоторыми оговорками). Здесь, например, символ V всегда означает пять, вне зависимости от места его появления в записи числа. Есть и другие современные непозиционные системы.
Позиционная система счисления - это система, в которой значение каждой цифры зависит от ее числового эквивалента и от ее места (позиции) в числе, т.е. один и тот же символ (цифра) может принимать различные значения.
В позиционной системе счисления справедливо равенство:
Aq = anqn + an-1qn-1 + ... + a1q1 + a0q0 + a-1q-1 + ... + a-mq-m, (2.1)
или
EMBED Equation.2 =
где Aq это произвольное число, записанное в системе счисления с основанием q; ai - коэффициенты ряда, т.е. цифры системы счисления; n, m - количество целых и дробных разрядов соответственно.
Например, согласно (2.1)
1961,3210 = 1?103 + 9?102 + 6?101 + 1?100 + 3?10-1 + 2?10-2,
124,5378 = 1?82 + 2?81 + 4?80 + 5?8-1 + 3?8-2 + 7?8-3,
1001,11012 = 1?23 + 0?22 + 0?21 + 1?20 + 1?2-1 + 1?2-2 + 0?2-3 + 1?2-4.
Выбор системы счисления
При выборе системы счисления для ЭВМ необходимо учитывать, что во-первых, основание системы счисления определяет количество устойчивых состояний, которые должен иметь функциональный элемент, выбранный для изображения разрядов числа; во-вторых - длина числа существенно зависит от основания системы счисления; в третьих - система счисления должна обеспечить простые алгоритмы выполнения арифметических и логических операций.
Если имеется n разрядов для изображения числа в q-ичной системе счисления, то тогда максимальное число М, которое можно изобразить в пределах данной разрядной сетки, будет равно:
M = qn - 1 ? qn
Для оценки экономичности системы счисления с точки зрения затрат оборудования цифрового автомата вводится соответствующий показатель:
N = qn
Из приведенных равенств следует, что N = q?lnM / lnq. Используя полученную зависимость, можно найти основание системы счисления, при которой требуется минимум оборудования. Определив dN/dq и приравняв ее к нулю, получим экстремум при q = e. Но е не целое число, поэтому нужно использовать системы с q = 2 или q = 3. Эти системы практически равноценны, т.к.
N2 / N3 = 2ln3 / 3ln2 ? 1.056
Подобное сравнение десятичной и двоичной систем счисления показывает, что десятичная в 1.5 раз менее экономична двоичной.
Наиболее удобны условия реализации двоичных цифр, т.к. физических процессов, имеющих два устойчивых состояния, гораздо больше, чем процессов с числом четко различимых состояний больше двух. К тому же в процессах с двумя устойчивыми состояниями различие между этими сотояниями носит качественный, а не количественный характер, что обеспечивает надежную реализацию двоичных цифр.
Таким образом, простота арифметических и логических действий, минимум используемого оборудования для представления чисел и наиболее удобные условия реализации только двух устойчивых состояний определили применение двоичных систем счисления практически во всех существуюющих и проектируемых цифровых вычислительных машинах.
Формальные правила двоичной арифметики
Перед тем, как рассмотреть формальные правила двоичной арифметики подчеркнем общий принцип сложения и вычитания чисел представленных в любой позиционной системы счисления.
В общем случае процедуры сложения и вычитания двух чисел
A ? B = C в любой позиционной системы счисления начинаются с младших разрядов.
Код суммы каждго i-того разряда сi получается в результате сложения ai + bi +1, где единица соответствует переносу из младшего (i - 1)-разряда в i-тый, если в младшем разряде код суммы получился больше или равным основанию системы счисления.
Код разности каждого i-того разряда получается в результате вычитания ai - bi -1, где единица соответствует заему, если он был, в младшие разряды величины, равной основанию системы счисления.
Следовательно, правила и методы сложения и вычитания в любой позиционной системы счисления в принципе остаются такими же, как в десятичной системе.
Теперь рассмотрим правила арифметики с числами, представленными в двоичном коде.
Сложение двух чисел выполняется поразрядно, начиная с младшего разряда. В каждом разряде выполняется сложение двух цифр слагаемых и единицы переноса из соседнего младшего разряда:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0 и осуществляется перенос 1 в старший соседний разряд.
Например:
01012 = 510
+00112 = 310
10002 = 810
Вычитание также производится поразрядно, начиная с младшего разряда. При вычитании в данном разряде из нуля единицы необходимо занять единицу из соседнего старшего разряда, которая равна двум единицам данного разряда:
0 - 0 = 0
1 - 0 = 1
1 - 1 = 0
0 - 1 =1 после заема единицы из соседнего старшего разряда.
Например:
01102 = 610
-00112 = 310
00112 = 310
Суммирование двоичных чисел в компьютерах осуществляется при помощи двоичных сумматоров, а вычитание - двоичных вычитателей. Но как будет показано в дальнейшем, вычитание можно организовать также при помощи процедуры сложения, т.е. при помощи двоичных сумматоров, если вычитаемое представить в "дополнительном" или "обратном" коде и тем самым исключить необходимость в двоичных вычитателях.
Умножение двоичных чисел производится путем образования про-межуточных произведений и последующего их суммирования. Промежуточные поразрядные произведения формируются по следующим правилам:
0 x 0 = 0 101 510 x 310 = 1510
0 x 1 = 0 11
1 x 0 = 0 101
1 x 1 = 1 + 101
1111
Деление чисел в двоичной системе производится по правилам умножения и вычитания.
Например:
110 : 11 = 10 610 : 310 = 210
11
00
00
0
Помимо арифметических операций в цифровых автоматах реализуются также логические операции, которые подробно рассматриваются в последующих главах.
Кроме этих операций в цифровых автоматах, компьютерах, выполняется еще одна операция над двоичными числами - это сдвиг числа по разрядной сетке влево или вправо. В случае сдвига влево фактически осуществляется умножение двоичного числа на 2?, а при сдвиге вправо - деление на 2?, где ? - количество разрядов, на которое сдвигается двоичное число. Например: 0000112 = 310 сдвинем влево на 2 разряда, получим 0011002 = 1210, т.е. 3х4(22) = 1210, а теперь 0010002 = 810 сдвинем на 2 разряда вправо, получим 0000102 = 210, т.е. 8:4(22) = 210.
В компьютерах часто используется циклический сдвиг, при выполнении которого разрядная сетка, отведенная для операнда, представляется замкнутой в кольцо. Тогда при сдвиге влево содержимое старшего разряда попадает в младший разряд операнда, а при сдвиге вправо - наоборот.
Перевод числа из одной позиционной системы счисления в другую
Как уже отмечалось, любая обработка информации в компьютере обычно осуществляется в двоичной системе счисления. В то же время, при обмене информации между компьютером и пользователем для большей наглядности представления данных используются десятичная, двоично-десятичная, восьмеричная или шестнадцатеричная системы. Каждый разряд числа в восьмеричном и шестнадцатеричном коде эквивалентен трем и четырем двоичным разрядам соответственно. Поэтому, представление чисел в этих системах счисления получается более компактным и наглядным.
Для перевода восьмеричного (шестнадцатеричного) числа в двоичную форму достаточно заменить каждую цифру этого числа соответствующим трехразрядным (четырехразрядным) двоичным числом, при этом отбрасывают ненужные нули в старших разрядах.
Например
( 3 0 5 . 4 )8 = 11000101.100(2);
011 000 101 . 100
( 7 B 2 . E )16 = 11110110010.1110(2).
0111 1011 0010 . 1110
Для перехода от двоичной к восьмеричной (шестнадцатеричной) системе поступают так: двигаясь от точки влево и вправо, разбивают двоичное число на группы по три (четыре) разряда, дополняя, при необходимости, нулями крайние левую и правую группы. Затем группу из трех (четырех) разрядов заменяют соответствующей восьмеричной (шестнадцатеричной) цифрой.
Например:
1) перевод 1101111001.11012 в восьмеричное
001 101 111 001 . 110 100 = 1571.648;
1 5 7 1 6 4
2) перевод 11111111011.100111(2) в шестнадцатеричное
0111 1111 1011 . 1001 1100 = 7FB.9C(16).
7 F B 9 C
Двоично-десятичный код (D-код) ориентирован на наиболее удобную для человека десятичную систему счисления. В нем для записи чисел используются только двоичные цифры 0 и 1. Двоично-десятичный код образуется заменой каждого десятичного разряда в десятичном числе 4-х битовым двоичным представлением этого разряда.
Например,
0001 1001 1000 0100(D) = 1984(10)
0001 1001 1000 0100
1 9 8 4
Для реализации машинных алгоритмов перевода из одной системы счисления в другую существуют различные методы. Так, например, для перевода целого десятичного числа в его двоичный (восьмеричный, шестнадцатеричный) эквивалент используется деление на 2 (8, 16), т.е. выполняется деление на основание новой системы счисления. В процессе такого деления последовательно, начиная с младшего разряда 2-го (8-го, 16-го) эквивалента, записывается остаток, если он получается на очередном этапе деления десятичного числа. В противном случае записывается ноль. Далее результат очередного деления опять делится на 2 (8, 16), если этот результат больше или равен 2 (8, 16). Если же результат меньше, то он прямо переписывается в старший разряд:
1) 53:2 = 26:2 = 13:2 = 6:2 = 3:2 = 1
(мл. раз.) 1 0 1 0 1 1 (ст. раз.) 53(10) = 110101(2).
2) 128:8 = 16:8 = 2
0 0 2
12810 = 2008
3) 128:16 = 8
0 8
12810 = 8016
Для дробных чисел (или дробных частей вещественных чисел) требуется отдельная процедура перевода. В случае неправильной дроби процедура преобразования для целой и дробной частей числа выполняется отдельно. Результат получают путем записи двоичных эквивалентов этих частей соответственно слева и справа от двоичной запятой (точки). Следовательно, при переводе неправильной десятичной дроби целая и дробная части числа переводятся в двоичный эквивалент по разным алгоритмам.
Процедуру преобразования десятичной дроби в двоичную рассмотрим на примере преобразования числа 0,375.
1. Преобразование осуществляется умножением дроби на основание системы счисления, в которой дробь должна быть представлена. В данном случае умножаем на 2: 0,375 х 2 = 0.75. Окончательный результат формируется поразрядно, начиная со старшего разряда, к примеру, в некотором трехразрядном регистре С = 0.XXX, где XXX - разрядная сетка мантиссы этого регистра.
2. Если результат <1, то старшему значащему разряду присваивается значение 0; если больше 1, то присваивается 1. Поскольку 0,75<1, то в старший разряд регистра С записывается 0, т.е. С = 0,0XX.
3. Результат предыдущей операции умножения снова умножаем на 2. Заметим, что если бы результат предыдущей операции умножения был больше 1, то в данной операции умножения участвовала лишь его дробная часть. В данном случае 0,75 x 2 = 1,5.
4. Так как результат больше 1, то следующему значащему разряду регистра С присваивается значение 1, т.е. С = 0,01X.
5. Шаги описанной процедуры повторяются до тех пор, пока либо результат умножения не будет точно равен 1, либо не будет достигнута требуемая точность. В нашем примере после выполнения очередного шага результат равен 0,5 x 2 = 1,0. Поэтому очередному значащему разряду регистра С присваивается 1, т.е. окончательно получена двоичная дробь С = 0.0112.
Надо отметить, что не всегда путем повторения операций умножения можно достичь результата, точно равного 1. В таком случае процесс останавливается по достижению необходимой точности, а целую часть результата последней операции умножения присваивают младшему значащему разряду.
Расмотрим еще пример: переведем число 0,3437510 в двоичное
2 x 0,34375 = 0,6875 0 (старший разряд - СЗР, результата перевода)
2 x 0,6875 = 1,375 1
2 x 0,375 = 0,75 0
2 x 0,75 = 1,5 1
2 x 0,5 = 1,0 1
2 x 0 = 0 0 (младший разряд - МЗР, результата перевода)
Ответ: 0,01011(2)
Для перевода десятичной правильной дроби в восмеричную (шестнадцатеричную) надо умножать ее на 8 (16). Если очередное произведение правильная дробь, то, начиная со старшего разряда результата записываются 0. Если произведение целое и меньше 8 (16), то оно прямо переписывается в соответствующий разряд результата.
Например:
1) 0,0625 x 8 = 0,5 0
0,5 x 8 = 4 4
0,062510 = 0,048
2) 0,875 x 16 = 14(E)
0,87510 = 0,E16
Перевод двоичного числа в десятичный его эквивалент можно выполнить при помощи формулы (2.1):
1) 110101(2) = 1?25 + 1?24 + 0?23 + 1?22 + 0?21 + 1?20 =
1?32 + 1?16 + 0?8 + 1?4 + 0?2 + 1?1 = 32 + 16 + 4 + 1 = 53(10).
2) 2008 = 2?82 + 0?81 + 0?80 = 12810
3) 1F16 = 1?161 + 15?160 = 3110
Таким образом, при переводе числовой информации из одной позиционной системы счисления в другую все действия должны выполняться по правилам арифметики исходной системы счиления.
Алгебраїчне додавання у зворотному та в доповняльному кодах. Модифіковані коди.
При сложении двух чисел, представленных в обратном или дополнительном коде, их знаковые разряды складываются аналогично цифровым, причем возможен перенос единицы из старшего цифрового разряда в знаковый.
Если оба операнда представлены в прямом коде и имеют одинаковые знаки, то над такими операндами выполняется процедура сложения и результату присваивается знак исходных операндов.
Рассмотрим примеры:
1) 210 + 410 = 610 2) -210 - 410 = -610
0. 0010 а) 1. 1110 б) 1. 1101
+ 0. 0100 + 1. 1100 + 1. 1011
0. 0110 = 610 1 ? 1. 1010 = -610 1 ? 1. 1000
+1 коррекция
1. 1001 = -610
Во втором примере оба отрицательных слагаемых представлены либо в дополнительном коде (а), либо в обратном коде (б). В первом случае результат получен в дополнительном коде, а во втором, после коррекции, - в обратном.
Если же операнды имеют разные знаки, то должна выполняться процедура вычитания. Но, как уже отмечалось, процедуру вычитания заменяют процедурой сложения, отрицательный операнд (вычитаемое) представляют в обратном или дополнительном коде, а положительный операнд - в прямом коде.
Например:
1) 410 - 210 = 210
а) 0. 0100 б) 0. 0100
+ 1. 1110 + 1. 1101
1 ? 0. 0010 = 210 1? 0. 0001
+1 коррекция
0. 0010 = 210
2) 410 - 410 = 0
а) 0. 0100 б) 0. 0100
+ 1. 1100 + 1. 1011
1? 0. 0000 = 010 1. 1111
+1 коррекция
1? 0. 0000 = 010
3) 210 - 410 = -210
а) 0. 0010 б) 0. 0010
+ 1. 1100 + 1. 1011
1. 1110 = -210 1. 1101 = -210 коррекции нет.
В примерах 1а) и 2а) единица, выходящая за разрядную сетку, не учитывается ("теряется").
Как видно из примеров процедура алгебраического сложения с дополнительными кодами проще, чем с обратными кодами, т.к. в последнем случае при возникновении единицы переноса за пределы разрядной сетки, выделенной для числа в формате с фиксированной запятой, приходится корректировать результат с помощью дополнительной процедуры прибавления единицы к результату. Нулевой результат получается или в прямом коде или же в обратном, что также требует коррекции результата. Поэтому в настоящее время на практике для представления отрицательных операндов используется в основном дополнительный код.
Таким образом, перед выполнением самой процедуры алгебраического сложения в дополнительном коде нужно проанализировать знаки слагаемых. Если они разные, то выполняется алгебраическое сложение (фактически вычитание) без проверки на переполнение результата, т.к. его в этом случае просто не может быть. Но контролируется чтобы в результате не появился запрещенный отрицательный ноль. Если же у исходных операндов знаки одинаковы, то такой же знак предварительно присваивается результату и выполняется само сложение. Если знак окончательного результата не совпадает с предварительно присвоенным знаком, то это является признаком переполнения и следовательно, неправильного результата.
Еще раз подчеркнем, что результат алгебраического сложения операндов представленных в обратном и дополнительном кодах получается также в обратном и дополнительном коде соответственно.
Модифицированный прямой, обратный и дополнительный код
Эти коды отличаются от обычных прямых, обратных и дополнительных тем, что имеют по два знаковых разряда. При выполнении арифметических действий над двоичными числами эти два знака позволяют легко определить переполнение разрядной сетки. Если содержимое этих двух разрядов совпадает, то значит переполнение отсутствует. В противном случае в компьютере вырабатывается управляющий сигнал (сигнал переполнения) либо на останов компьютера, либо на устранение переполнения разрядной сетки.
Примеры.
1) Сложить два числа в модифицированном коде:
X = 00. 01012, Y = 00. 00112 , X + Y = 510 + 310 = 810
00. 0101
+ 00. 0011
00. 1000 = 810
2) Сложить X = -510 = -01012 = 11. 0101 , Y = -810 = -10002 = 11. 1000
X + Y = -1310
11. 1011
+ 11. 1000
? 1 11. 0011 = -1310
3) Сложить X = 0,1101 , Y = 0,1101, X + Y = 2610
00. 1101
+ 00. 1101
01. 1010 различные знаковые разряды свидетельствуют о переполнении разрядной сетки.
4) -8 - 8 = 0
11. 1000
+ 11. 1000
? 1 11. 0000 .
В последнем примере получился отрицательный ноль, поэтому компьютер генерирует сигнал сбоя. Надо отметить, что в машинах 3-го и 4-го поколений модифицированный код не используется.
Двійково-кодовані СЧ. Порівняння найбільш розповсюджених двійково-кодованих СЧ. Особливості виконання операції додавання у двійково-десяткових кодах.
Рутисхауер в 1951р. запропонував 5 вимог, до яких кожний код може виконувати, а може не виконувати:
Єдність
Впорядкованість
Парність (непарність)
Доповняльність
Вагомість
20(10)=10100(2)=0010 0000(2-10)
15(10)=1111(2)=0001 0101(2-10)
19(10)+5(10)=24(10)
0001 1001(2-10)
0000 0101(2-10)
0001 1110
0000 0110 - корекція додавання 6
0010 0100(2-10)= 24(10)
Непозиційні СЧ. Поняття про СЧ у залишкових класах.
Залишкові класи
Найменший залишок від ділення члена на кожну основу.
Переведення число 13 в систему 532
13 : 2 = 6 залишок 1
13 : 3 = 4 залишок 1
13 : 5 = 2 залишок 3
13(10)=311(532)
Основна перевага : додавання та множення виконується порозрядно
Недолік : складність з операцією порівняння (порівняння чисел існують проблем из виходом за межі розрядної сітки), проблеми з представленням відємних чисел.
Форми представлення чисел. Порівняння методів фіксованої та плаваючої коми.
Необходимость в указании положения запятой отпадает, если место запятой в разрядной сетки машины заранее фиксировано раз и навсегда. Такая форма представления чисел называется представлением с фиксированной запятой (точкой).
Так как числа бывают положительные и отрицательные, то формат (разрядная сетка) машинного изображения разбивается на знаковую часть и поле числа. В поле числа размещается само изображение числа, которое мы будем условно называть мантиссой числа. Для кодирования знака числа используется самый старший разряд разрядной сетки, отведенной для изображения двоичного числа, а остальные разряды отводятся под мантиссу числа. Положение запятой в разрядной сетке строго фиксируется, обычно или правее самого младшего разряда мантиссы, или левее самого старшего. В первом случае число представляется как целое, во втором - как правильная дробь. В настоящее время в подавляющем большинстве в компьютерах в формате с фиксированной точкой представляются целые числа.
В знаковую часть записывается информация о знаке числа. Принято, что знак положительного числа "+" изображается символом 0, а знак отрицательного числа "-" изображается символом 1.
Например, в двоичном коде, используя 6-разрядную сетку, число 7 в форме с фиксированной запятой можно представить в виде:
0.001112,
где цифра левее точки это знак числа, а пять цифр правее точки - мантисса числа в прямом коде. Здесь подразумевается, что запятая фиксирована правее младшего разряда, а точка в изображении числа в данном случае просто разделяет знаковый бит от мантиссы числа.
В дальнейшем часто будет использоваться в примерах такой вид представления числа в машинной форме. Можно использовать и другую форму представления числа в машинной форме:
[0]001112,
где знаковый разряд выделяется квадратными скобками.
Количество разрядов в разрядной сетке, отведенное для изображения мантиссы числа, определяет диапазон и точность представления числа с фиксированной запятой. Максимальное по абсолютной величине двоичное число изображается единицами во всех разрядах, исключая знаковый, т.е. для целого числа
|A|max = (2(n-1) - 1),
где n - полная длина разрядной сетки. В случае 16-разрядной сетки
|A|max = (2(16-1) - 1) = 3276710 ,
т.е. диапазон представления целых чисел в этом случае будет от +3276710 до -3276710 .
Для случая, когда запятая фиксируется правее младшего разряда мантиссы, т.е. для целых чисел, числа, у которых модуль больше, чем (2(n-1) - 1) и меньше единицы не представляются в форме с фиксированной запятой. Числа, по абсолютной величине меньше единицы младшего разряда разрядной сетки, называются в этом случае машинным нулем. Отрицательный ноль запрещен.
В некоторых случаях, когда можно оперировать только модулями чисел, вся разрядная сетка, включая самый старший разряд, отводится для представления числа, что позволяет расширить диапазон изображения чисел.
Форма представление чисел с плавающей запятой
В общем случае число в форме с плавающей запятой представляется в виде:
A = ? m?q? p ,
где m - мантисса числа, q - основание системы счисления, q? p - порядок числа, который для упрощения в примерах будем иногда изображать как ?P. Тогда очевидно, что p - это показатель степени порядка, который обычно называют просто порядком числа, т.к. в основном всегда q = 2. Следовательно предыдущее выражение можно записать в следующем виде:
A = ? mA??PA,
имея в виду, что в компьютерах обычно q = 2.
Так, например, число 1984 в форме с плавающей запятой в десятичной системе счисления можно записать следующим образом:
1984,0?100 0,1984?104
19,84?102 198400?10-2
и т.д.
Число с плавающей запятой принято представлять в так называемом нормализованном виде для максимально точного представления числа. Если выполняется неравенство
q-1? |m| <1,
а в случае двоичной системы счисления:
0.5? |m| <1,
то считается, что число представлено в нормализованном виде. Например, 0,1984?104 является нормализованным видом числа 1984 в форме с плавающей запятой в десятичной системе счисления.
Таким образом, у двоичного нормализованного числа в форме с плавающей запятой мантисса - правильная дробь и в старшем разряде мантиссы всегда стоит 1. Операция приведения числа к нормализованному виду называется нормализацией. Нормализация чисел в компьютере выполняется или автоматически или же по специальной программе.
Так как система счисления для заданного цифрового автомата (компьютера) остается постоянной, то при представлении числа в формате с плавающей запятой нет необходимости указывать ее основание, достаточно лишь представить показатель степени порядка числа.
Для представления двоичного числа в форме с плавающей запятой в разрядной сетке, выделенной для этой цели, отводится по одному разряду для представления знака числа Sm и знака показателя степени порядка SP; определенное число разрядов для представления значения самого показателя p, а также разряды для размещения значения модуля мантиссы m. Например, возможен следующий вариант:
т.е.
[A] = Sp pASmmA
Обычно в формате с плавающей запятой вместо показателя p используют так называемую характеристику ("смещенный порядок"):
r = ? p + l,
де l - избыток (смещение), значение которого подбирается таким образом, чтобы при изменении значения показателя от некоторого минимального значения -|pmax| до максимального +|pmax|, характеристика r менялась от 0 до rmax. Следовательно, характеристика не меняет своего знака. В таком случае отпадает необходимость в отображении знака порядка Sp. Для этого принимается, что
l = 2k-1,
где k - число разрядов, выделеных для представления порядка числа в формате с плавающей запятой.
Тогда формат числа с плавающей запятой можно представить, в частности, следующим образом:
т.е.
[A] = Sm r mA
Такой формат и используется, в основном, в настоящее время.
Рассмотрим несколько примеров представления чисел в форме с плавающей запятой. Предварительно напомним, что показатель степени двойки в разрядах разрядной сетки длиной n, отведенной для представления целых чисел, изменяется от 0 до n-1, а в случае правильных дробных чисел - от -1 до -n.
Если для представления показателя порядка выделены 4 разряда, то l = 23 = 810 = 10002. Для этого случая в таблице 3.1 приведены значения показателя порядка, характеристики и мантиссы для некоторых чисел, представленных в форме с плавающей запятой.
Т а б л и ц а 3.1.
Например, в 16-ти разрядных компьютерах для представления двоичного числа в форме с плавающей запятой с обычной точностью отводится 4 байта, т.е. 2 16-разрядных слова:
Разряды 14?7 старшего слова числа используются для представления характеристики числа. В остальных разрядах старшего слова и во всем младшем слове размещается модуль мантиссы числа. 15-й разряд старшего слова используется под знак числа.
Единица самого старшего разряда нормализованной мантиссы обычно является "скрытой", т.е подразумевается и не отражается в формате числа. 7-ой разряд старшего слова, в котором должна была быть отражена эта единица, используется в качестве младшего разряда характеристики, что позволяет увеличить диапазон представления чисел в формате с плавающей запятой.
Таким образом, мантисса в таком варианте отображается, начиная с разряда, следующего после самого старшего. При всех операциях с мантиссой числа это обстоятельство надо учитывать и перед началом этих операций восстанавливать старший разряд мантиссы в тех регистрах, куда загружается мантисса числа для выполнения над ней каких-то процедур.
После завершения этих процедур во время формирования отображения нормализованного числа в отведенной для него разрядной сетке машинных слов, старшая единица мантиссы опять отбрасывается.
8-разрядное поле порядка позволяет изменять показатель порядка в пределах от -12810 до +12710, причем показатель порядка записыватся с избытком l = 2008 или 12810.
В отличие от показателя порядка, как уже отмечалось, характеристика не меняет своего знака и в данном случае изменяется от 0 (при p = -12810) до 3778 (при p = +12710), причем r = 2008 при p = 0. Исключение составляет число 0: ноль с обычной и двойной точностью выражается нулевой характеристикой и нулевой мантиссой.
Комбінаційні та послідовнісні структури. Наведіть їх переваги та недоліки.
EMBED Visio.Drawing.11
EMBED Visio.Drawing.11



Преобразование информации в ЭВМ производится электронными устройствами (логическими схемами) двух классов: комбинационными схемами и цифровыми автоматами.
В комбинационных схемах (КС) совокупность выходных сигналов (выходное слово У) в любой момент времени однозначно определяется входными сигналами (входным словом X), поступающими на входы в тот же момент времени.
Реализуемый в этих схемах способ обработки информации называется комбинационным, так как результат обработки информации зависит только от комбинации входных сигналов и вырабатывается сразу при подаче входной информации.
Закон функционирования КС определен, если задано соответствие между ее входными и выходными словами, например, в виде таблицы.
Это соответствие может быть задано и в аналитической форме с использованием булевых функций.
Другой, более сложный класс преобразователей дискретной информации составляют цифровые автоматы. Цифровой автомат в отличие от комбинационной схемы имеет некоторое конечное число различных внутренних состояний.
Под воздействием входного слова цифровой автомат переходит из одного состояния в другое и выдает выходное слово. Выходное слово на выходе цифрового автомата в такте определяется в общем случае входным словом, поступившим в этот такт на вход автомата, и внутренним состоянием автомата, которое явилось результатом воздействия на автомат входных слов в предыдущие такты.
Комбинация входного слова и текущего состояния автомата в данном такте определяет не только выходное слово, но и то состояние, в которое автомат перейдет к началу следующего такта.
Цифровой автомат содержит память, состоящую из запоминающих элементов (ЗЭ) — триггеров, элементов задержки и др., фиксирующих состояние, в котором он находится. Комбинационная схема не содержит ЗЭ. Поэтому ее называют автоматом без памяти или примитивным автоматом.
Выходное слово вырабатывается в КС, причем входными переменными для нее служат буквы входного слова и состояния ЗЭ — состояние автомата. Выходные сигналы КС переводят автомат (его ЗЭ) в новое состояние, при этом входными переменными для этой схемы служат буквы входного слова и состояния ЗЭ. Одновременность появления новых значений входных сигналов на всех входах устройства достигается с помощью актирующих сигналов, называемых также синхросигналами, обеспечивающих передачу информации с ЗЭ на входы комбинационной схемы одновременно с сигналами, поступающими на ее входы с других устройств.
В ряде случаев при анализе автомата его заменяют автоматом с одним эквивалентным входом и одним эквивалентным выходом и считают, что эквивалентные входной сигнал x(t) и выходной сигнал y(t) принимают значения из соответствующим образом преобразованных алфавитов Р и S входных и выходных сигналов.
Для задания цифрового автомата должны быть указаны:
входной алфавит Р = {р1, р2,...,рn};
выходной алфавит S = {s1, s2, ...,sm};
алфавит состояний Q = {Q0, Q1, ...,Qr};
начальное состояние автомата Q0;
функции перехода A(Q, x) и выходов B(Q, x), однозначно определяющие зависимость соответственно состояния автомата Q(t + 1) в такте (t + 1) и выходного сигнала y(t) от состояния автомата Q(t) и входного сигнала x(t) в такте t.
Класифікація тригерів. Поняття про тригери типу D, T, RS, JK, MS, RST.
Тригер – це однорозрядний елемент пам’яті. Взагалі тригером називається пристрій, який може знаходитись в одному з двох стійких станів і переходить з одного стану в інший під впливом вхідного сигналу. Стан тригера визначається за вихідним сигналом Q. Як правило, тригери реалізуються з двома виходами – прямим Q та інверсним EMBED Equation.2 . Стану тригера 1 відповідає лог.1 на виході Q та лог.0 на виході EMBED Equation.2 і навпаки.Тригер є базовим елементом пристроїв пам’яті і дозволяє зберігати один біт інформації.
Входи тригера поділяються на інформаційні та допоміжні (керуючі). Сигнали, що надходять на інформаційні входи, керують станом тригера. Сигнали на допоміжних входах використовуються для попереднього встановлення тригера в потрібний стан і для синхронізації. Допоміжні входи можуть використовуватись і в якості інформаційних. Число входів тригера залежить від його структури та призначення.
За способом прийому інформації тригери поділяються на асинхронні та синхронні. Асинхронні тригери сприймають інформаційні сигнали та реагують на них в момент їх появи на входах тригера. Синхронні тригери реагують на інформаційні сигнали при наявності дозволяючого сигналу на спеціальному керуючому вході C, який називається входом синхронізації. Синхронні тригери поділяються на тригери із статичним та динамічним керуванням по входу C. Тригери із статичним керуванням сприймають інформаційні сигнали при подаванні на C-вхід рівня лог.1 (прямий C-вхід) або лог.0 (інверсний C-вхід). Тригери з динамічним керуванням сприймають інформаційні сигнали при зміні сигналу на C-вході від 0 до 1 (прямий динамічний C-вхід) або від 1 до 0 (інверсний динамічний C-вхід).
За принципом побудови тригери із статичним керуванням можна поділити на одноступеневі та двоступеневі. Одноступеневі тригери характеризуються наявністю однієї ступені запам’ятовування інформації. В двоступеневих тригерах є дві ступені запам’ятовування інформації – спочатку інформація записується у першу ступінь, потім переписується в другу і з’являється на виході.
За функціональними можливостями розділяють:
тригери із роздільним встановленням станів 0 та 1 (RS-тригери);
тригери із прийомом інформації по одному входу D (D-тригери або тригери затримок);
тригери із лічильним входом T (T-тригери);
універсальні тригери з інформаційними входами J і K (JK-тригери).
На рис.5.1 наведені умовне графічне позначення та монтажна схема асинхронного RS-тригера з інверсними входами. Цей тригер побудований на двох логічних елементах І-НІ. В табл.5.1 наведена таблиця станів цього тригера.
Рис.5.1.
Умовне графічне позначення (а) та монтажна схема (б) RS-тригера.
Тригер повинен реалізувати функцію
EMBED Equation.3
Таблиця 5.1.
Синхронний RS-тригер із статичним керуванням (RSC-тригер), наведений на рис.5.2, відрізняється від асинхронного наявністю C-входу, на який подаються синхронізуючі (тактові сигнали). Синхронний тригер складається з асинхронного RS-тригера та комбінаційного цифрового пристрою з трьома входами S, C, R і двома виходами. При C=0 вхідні логічні елементи блоковані, сигнали на їх виходах дорівнюють 1 і не залежать від сигналів нв входах S і R. В табл.5.2 наведена таблиця станів RSC-тригера.

Рис.5.2. Умовне графічне позначення (а) та монтажна схема (б) RSC-тригера.
Таблиця 5.2.
D-тригер або тригер із затримкою має один інформаційний вхід D та один вхід для синхронізації C. D-тригер, наведений на рис.5.3, побудований на основі RSC-тригера шляхом з’єднання входів R і S через інвертор для отримання входу D. Інформація, що надходить на вхід D, записується в тригер по додатньому перепаду сигналу на вході C. В табл.5.3 наведена таблиця станів D-тригера.
Тригер повинен реалізувати функцію
EMBED Equation.3
Таблиця 5.3.

Рис.5.3. Умовне графічне позначення (а) та монтажна схема (б) D-тригера на базі RSC-тригера.
JK-тригери є найбільш універсальними. На рис.5.4 наведені умовне графічне позначення та монтажна схема найпростішого JK-тригера, побудованого на основі RSC-тригера за допомогою двох додаткових зворотніх зв’язків. Він працює аналогічно RSC-тригеру за виключенням того, що в нього відсутні заборонені комбінації входів. Нижче наведена таблиця станів JK-тригера.


Рис.5.4. Умовне графічне позначення (а) та монтажна схема (б) JK-тригера на базі RSC-тригера.
Тригер повинен реалізувати функцію
EMBED Equation.3
Таблиця 5.4.
Т-тригер Може бути построєний з використанням двухтактного синхронного RS-тригера. Т-тригер повинен реалізувати функцію
EMBED Equation.3

Несинхронізуючий
EMBED Visio.Drawing.11
EMBED Visio.Drawing.11


Синхронізуючий
EMBED Visio.Drawing.11
EMBED Visio.Drawing.11


Таблиця двохтактного синхронного RS-тригера




Синтез однорозрядних суматорів на три входи в базисі Буля в нормальних формах.
Однорозрядний суматор на 3 входи

S=?A?BC??AB?C?A?B?C?ABC
P=? ABC?A?BC?AB?C?ABC









S=?A?BC??AB?C?A?B?C?ABC
P=AB?BC?AC







Аномальні форми
S=(AB)C?((A?B) ?C)?(AB?C(A?B)
P=AB?С(B?A)





S=?C(A?B??AB) ?C? (A?B??AB)
P=AB?C(A?B??AB)




Код Грея. Особливості побудови та області застосування.
Наступне число відрізняється від попереднього лише 1 розрядом
Код формується так:
Візьмемо число в коді 8421 , запишем під ним такеж число тільки зсунуте на 1 розряв вправо,крайній розряд знищується.Здійснюється додавання по mod2
7(10)=0111
EMBED Equation.3
0111
00111
0100 ? 7 записана в коді Грея
Порогова та мажоритарна функції і логіки.
Всі ф-ції мали входи з одними ваговими коефіцієнтами. А тут різні.
EMBED Visio.Drawing.11

EMBED Equation.3
мажоритарна ф-ція (1 там, де більше одної одиниці)


Однофункціональні базиси. Методи синтезу комбінаційних схем у цих базисах.
Перед тем как перейти к примерам синтеза композиционных логических схем рассмотрим способы использования универсальности вентилей И-НЕ и ИЛИ-НЕ.
Свойство универсальности вентиля ИЛИ-НЕ(NOR):

Свойство универсальности вентиля И-НЕ(NAND):

Схемы с одним выходом и несколькими входами относятся к наиболее простым схемам. Основная сложность при синтезе этих схем состоит в том, чтобы найти выражение для выходной функции в заданном базисе.
Рассмотрим некоторые простые примеры перехода от логических уравнений к логическим цепям, т.е. примеры синтеза простых логических цепей. В частности, рассмотрим переход от представления функции в НДФ (ДНФ) к ее реализации на элементах И-НЕ и ИЛИ-НЕ.
НДФ имеет вид: F = ?A?B?D + AB?D + ?C.
Рассмотрим реализацию этого уравнения с помощью элементов И-НЕ. В общем случае на элементах И-НЕ НДФ функция реализуется посредством двух ступеней логики. На первой ступени получаются инверсные значения логических произведений и однобуквенных членов. На второй ступени выполняются операции И-НЕ, т.е. НЕ-ИЛИ, над полученными инверсиями.
Действительно, посредством применения двойного отрицания можно привести заданную функцию к виду:
F = ?A?B?D + AB?D + ?C = ?A?B?D ? AB?D ? C
Схема, соответствующая данному уравнению, приведена ниже.

В приведенной схеме для элементов первой и второй ступени применены различные, но эквивалентные условные обозначения. При реализации НДФ функции посредством элементов И-НЕ такой прием позволяет вести проектирование схем, пользуясь операциями И, ИЛИ и НЕ.
По рассмотреным ранее правилам из вышеприведенной карты Карно, может быть найдена минимальная НКФ заданной функции:
F = (?C +?D)(A +?B +?C)(?A + B +?C)
Отсюда, взяв двойное отрицание и применив теорему Де Моргана, получим
EMBED Equation.3
На элементах И-НЕ КНФ функции реализуется с помощью трех ступеней (соответствующая схема приведена ниже). На первой ступени посредством операции И-НЕ над инверсными значениями переменных, входящих в КНФ, образуются логические суммы. На второй ступени выполняется операция И-НЕ над логическими суммами и однобуквенными членами (если они имеются), тем самым образуется инверсное значение функции. На третьей ступени выполняется инверсия и получается искомая функция.

При минимизации логических функций для логических схем, которые предполагается строить на базе элементов И-НЕ или ИЛИ-НЕ, необходимо кроме собственно минимизации стремиться также к тому, чтобы структурная формула была представлена в виде комбинации из элементов И-НЕ или ИЛИ-НЕ. Тогда переход от структурной формулы к функциональной схеме не будет сложным. В любом случае при построении логической схемы в базисе И-НЕ на основе логической функции, представленной в МНДФ, необходимо везде вместо элементов И и ИЛИ ставить элемент И-НЕ. При построении логической схемы в базисе ИЛИ-НЕ на основе логической функции, представленной в МНКФ, необходимо везде вместо элементов И и ИЛИ ставить элемент ИЛИ-НЕ. Однако надо учесть, что есть точка зрения, по которой считается, что наиболее удобным для решения синтеза схем цифровых автоматов является базис И, ИЛИ, НЕ.
Теперь рассмотрим способы формирования схемы, реализующей функцию суммирования по модулю 2 (функция f6), в различных базисах. Логическая функция f6, как известно, в аналитическом виде представляется в виде: F = A?B +?AB, и имеет следующую таблицу истинности:
В базисе И, ИЛИ, НЕ схема, реализующая функцию f6, имеет вид:

M2
F
A
B
В базисе ИЛИ-НЕ:
F = ?AB + A?B = A +?B +?A + B = A +?B +?A + B

В базисе И-НЕ:
F = ?AB + A?B = ?AB ? A?B

Шифратори та дешифратори.
Задача синтеза схемы с n входами и k выходами отличается от задачи синтеза k схем с n входами и одним выходом тем, что при решении необ-ходимо исключить дублирование в k схемах синтезируемых функций.
Примером схем с несколькими входами и выходами может служить схема дешифратора. Принцип работы дешифратора прост: при заданном наборе входных сигналов на выходе возбуждается один выход или несколько выходов в соответствии с заданной зависимостью. Например, предположим, что необходимо синтезировать дешифратор с четырьмя входными переменнымиx1 - x4, у которого, при любой комбинации значений входных переменных, должен возбудиться только один выход из десяти.
Синтез такой схемы может быть осуществлен, если рассматривать раздельно каждую выходную функцию y0 - y9|
y0 = ?x1?x2?x3?x4; y1 = x1?x2?x3?x4; y2 = ?x1 x2?x3?x4; y3 = x1 x2?x3?x4;
y4 = ?x1?x2 x3?x4; y5 = x1?x2 x3?x4; y6 = ?x1 x2 x3?x4; y7 = x1 x2 x3?x4;
y8 = ?x1?x2?x3 x4; y9 = x1?x2?x3 x4;
Реализация этих выражений в виде конъюнктора дает возможность создать логическую схему дешифратора.
Рассмотрим упрощенную схему такого дешифратора и его таблицу истинности. Здесь A0 - A3 - входные переменные. Значения ?A0 -?A3 фор-мируются в самом дешифраторе после первых инверторов. Дешифратор преобразует четырехразрядный двоичный код в десятичный. На выходах дешифратора логической единице соответствует низкий уровень сигнала, а на входах - высокий.
Комбинационная таблица дешифратора выглядит следующим образом:
Т а б л и ц а 9.1.
Схему дешифратора можно реализовать, например, так:




Шифратори
CD(Шифратори) – призначені для перетворення сигналу, що поступає на один з входів(m) в код адреси отримуваного коду(n). m=n2
EMBED Visio.Drawing.11
155ИВ1 – 8 вх
555ИВ3 – 10 вх
EMBED Equation.3
GS=EI(x0?x1?…?x7)







Комутатори. Мультиплексори та демультиплексори.
EMBED Visio.Drawing.11
Мультиплексор(колектор)
EMBED Equation.3


Демультиплексор(селектор)
пристрій, призначений для передачі інформації з інформаційного входів на вихід, що визначається адресою. Є аналогом електромеханічного перемикача.
Якщо виходів m, то адресних входів n=log2m або m=n2
EMBED Equation.3
EMBED Visio.Drawing.11








Наведіть та порівняйте такі основні програмовані матричні структури, як програмовані логічні матриці, програмовані запам’ятовуючі пристрої, програмовані матриці вентилів.
Програмована матрична логіка (ПМЛ)
EMBED Visio.Drawing.11
EMBED Visio.Drawing.11



556РП1
ПЛМ і ПМЛ мають матриці І та АБО. Основна відмінність між ними, що в ПМЛ матриця АБО фіксована, а в ПЛМ програмуються дві матриці, що забезпечує їй більшу гнучкість порівнянно з ПМЛ
ПЗП (програмовані запам’ятовуючі пристрої)
ROM – read only memory
PROM – programmable read only memory
EPROM – erasable programmable read only memory (ультрафіолетом)
EEPROM – electrically erasable programmable read only memory
EMBED Visio.Drawing.11

556РП4
556РП5
556РП6

ПМВ(програмовані матриці вентилів)
EMBED Visio.Drawing.11
EMBED Equation.3



TOC \o "1-1" \h \z \u HYPERLINK \l "_Toc74760685" Поняття про інформацію та її види. Три підходи до вивчення теорії інформації. Порівняння аналогової та цифрової обчислювальної техніки PAGEREF _Toc74760685 \h 1
HYPERLINK \l "_Toc74760686" Поясніть, у чому полягає зміст та значення теореми Котельникова. PAGEREF _Toc74760686 \h 2
HYPERLINK \l "_Toc74760687" Основні ознаки алгоритму. Навести підхід до формального визначення алгоритму. Універсальні формальні алгоритмічні системи. Основна гіпотеза теорії алгоритмів. PAGEREF _Toc74760687 \h 3
HYPERLINK \l "_Toc74760688" Автомат. Класифікація автоматів. Поняття про модель цифрового автомата типу Мілі та Мура. PAGEREF _Toc74760688 \h 4
HYPERLINK \l "_Toc74760689" Буква, слово, алфавіт. Переваги, фізична реалізація та форми представлення дволітерних алфавітів. PAGEREF _Toc74760689 \h 9
HYPERLINK \l "_Toc74760690" Алгебра логіки. Поняття про аналіз і синтез. Операції суперпозиції та перестановки. PAGEREF _Toc74760690 \h 10
HYPERLINK \l "_Toc74760691" Змінна, набір, функції алгебри логіки (ФАЛ) нуля, однієї та двох змінних PAGEREF _Toc74760691 \h 11
HYPERLINK \l "_Toc74760692" Основні властивості ФАЛ за Постом. Методи виявлення ФАЛ із цими властивостями. PAGEREF _Toc74760692 \h 14
HYPERLINK \l "_Toc74760693" Базис Жегалкіна. Основні тотожності. Синтез комбінаційних схем на прикладі однорозрядних суматорів на два та на три входи. PAGEREF _Toc74760693 \h 15
HYPERLINK \l "_Toc74760694" Базис Буля. Основні тотожності. PAGEREF _Toc74760694 \h 16
HYPERLINK \l "_Toc74760695" Форми завдання ФАЛ у базисі Буля. Класифікація аналітичних форм завдання ФАЛ у базисі Буля. PAGEREF _Toc74760695 \h 17
HYPERLINK \l "_Toc74760696" Проблема мінімізації у базисі Буля. Канонічна та загальна задачі мінімізації. Огляд методів розв’язання. PAGEREF _Toc74760696 \h 19
HYPERLINK \l "_Toc74760697" Особливості застосування методу мінімізації Квайна-Мак-Класкі-Петріка в базисі Буля. PAGEREF _Toc74760697 \h 20
HYPERLINK \l "_Toc74760698" Особливості та додаткові можливості застосування методу карт Карно. PAGEREF _Toc74760698 \h 25
HYPERLINK \l "_Toc74760699" Позиційні цілочисленні СЧ. Порівняння та класифікація. Двійкова СЧ. Правила дії. Основні переваги. PAGEREF _Toc74760699 \h 29
HYPERLINK \l "_Toc74760700" Алгебраїчне додавання у зворотному та в доповняльному кодах. Модифіковані коди. PAGEREF _Toc74760700 \h 35
HYPERLINK \l "_Toc74760701" Двійково-кодовані СЧ. Порівняння найбільш розповсюджених двійково-кодованих СЧ. Особливості виконання операції додавання у двійково-десяткових кодах. PAGEREF _Toc74760701 \h 37
HYPERLINK \l "_Toc74760702" Непозиційні СЧ. Поняття про СЧ у залишкових класах. PAGEREF _Toc74760702 \h 38
HYPERLINK \l "_Toc74760703" Форми представлення чисел. Порівняння методів фіксованої та плаваючої коми. PAGEREF _Toc74760703 \h 38
HYPERLINK \l "_Toc74760704" Комбінаційні та послідовнісні структури. Наведіть їх переваги та недоліки. PAGEREF _Toc74760704 \h 42
HYPERLINK \l "_Toc74760705" Класифікація тригерів. Поняття про тригери типу D, T, RS, JK, MS, RST. PAGEREF _Toc74760705 \h 43
HYPERLINK \l "_Toc74760706" Синтез однорозрядних суматорів на три входи в базисі Буля в нормальних формах. PAGEREF _Toc74760706 \h 47
HYPERLINK \l "_Toc74760707" Код Грея. Особливості побудови та області застосування. PAGEREF _Toc74760707 \h 49
HYPERLINK \l "_Toc74760708" Порогова та мажоритарна функції і логіки. PAGEREF _Toc74760708 \h 50
HYPERLINK \l "_Toc74760709" Однофункціональні базиси. Методи синтезу комбінаційних схем у цих базисах. PAGEREF _Toc74760709 \h 50
HYPERLINK \l "_Toc74760710" Шифратори та дешифратори. PAGEREF _Toc74760710 \h 53
HYPERLINK \l "_Toc74760712" Комутатори. Мультиплексори та демультиплексори. PAGEREF _Toc74760712 \h 55
HYPERLINK \l "_Toc74760713" Наведіть та порівняйте такі основні програмовані матричні структури, як програмовані логічні матриці, програмовані запам’ятовуючі пристрої, програмовані матриці вентилів. PAGEREF _Toc74760713 \h 57