Лекция 7. Комбинационные схемы и конечные автоматы
Лекция 7. Комбинационные схемы и конечные автоматы - раздел Информатика, Лекции по дисциплине Информатика Любое Устройство Обработки Дискретной Информации Имеет N Входов И M Выходов. ...
Любое устройство обработки дискретной информации имеет n входов и m выходов. Сигналы на входах соответствуют символам входного алфавита, а выходные – символам выходного алфавита.
Имеются два типа устройств обработки цифровой информации: на основе комбинационных схем и на основе конечных (цифровых) автоматов.
В комбинационных схемах совокупность входных сигналов (входное слово) однозначно определяет совокупность (комбинации) выходных сигналов (выходное слово).
Закон функционирования комбинационной схемы может быть задан несколькими способами. Можно определить таблицу истинности, или систему уравнений булевой алгебры для каждого выхода схемы, или функциональную схему на основе одного из базовых наборов логических элементов.
В отличие от комбинационных схем конечные автоматы имеют конечное число внутренних состояний.
Выходное слово и переход автомата в следующее состояние однозначно определяются состоянием автомата и входным словом.
Функционирование конечного автомата задается:
1. входным алфавитом: X {x0, x1, x2,…, xi,… xn},
2. выходным алфавитом: Y{у0, y1, y2,…, yi,… ym},
3. алфавитом состояний: Q {q0, q1, q2,…, qi,… qr,}, где q0 – начальное состояние автомата,
4. функцией переходов, определяющей переход автомата из qi состояния в следующее qi+1 состояние: qi+1 = d(qi, xi), или как функция времени: Q(t+1) = d [Q(t), X(t)].
5. функцией выходов, определяющей выходные сигналы автомата в состоянии qi: yi = d(qi, xi) или, как функция времени: Y(t) = d [Q(t), X(t)].
Функция выходов (5) соответствует конечному автомату, называемому автоматомМили. Имеется несколько разновидностей конечных автоматов, используемых в устройствах цифровой обработки. Широко используемой альтернативой автомату Мили является автомат Мура.
Особенностью автомата Мура является его функция выходов. В автомате Мура выходные сигналы зависят только от состояния конечного автомата qi.: yi = d(qi) или, как функция времени: Y(t) = d [Q(t)].
Основное отличие устройств на основе цифровых автоматов от комбинационных схем заключается в том, что первые содержат элементы памяти для фиксации состояний. Можно считать комбинационные схемы примитивными цифровыми автоматами с одним состоянием.
Элементы памяти цифровых автоматов – триггеры, в свою очередь являются элементарными цифровыми автоматами (автоматами Мура) с двумя устойчивыми состояниями.
Цифровые автоматы могут задаваться графами или таблицами выходов и переходов.
Измерение информации
Бурное развитие средств и систем связи в 30-х годах нашего столетия привело к необходимости разработки методов оценки количества информации. Основные теоретические положения были сф
Лекция 3. Преобразования логических выражений
Синтез комбинационных схем связан с преобразованиями логических выражений, которые содержат ПФ. Приведем достаточно очевидные формулы для ФПС ПФ, содержащей операции дизъюнкции, конъюнкции и отрица
Логические элементы
Рассмотрим некоторые логические элементы с одним и двумя входами, реализующие ПФ от одного и двух аргументов.
Логический элемент
Построение схем на элементах заданного базиса
Для аналитического представления ПФ используют правило ее записи по единицам:
- в таблице истинности выбирают все наборы, на которых ПФ равна единице;
- выписывают произведения ар
Лекция 4. Системы счисления
В общем случае система счисленияÌ представляет собой совокупность приемов и правил для записи чисел цифровыми знаками. Существуют различные системы счисления. Любая, предна
Метод непосредственного замещения
Перевод чисел этим методом выполняется следующим образом:
- заданное число А(q) представляется в виде (3.1):
A(q)=an-1´qn-1+…+a
Метод последовательного деления на основание
Этот метод используется для перевода только целых чисел.
Пусть число A(q) требуется записать в р-ичной системе. Допустим, что такое представление получено и новое число В
Метод последовательного умножения на основание
Этот метод применяется для перевода из одной системы счисления в другую только правильных дробей.
Пусть правильную дробь A(q) требуется записать в системе счисления с осн
В двоичную и наоборот
Существует особый случай перевода, если основание одной системы счисления является целой степенью основания другой системы. В этом случае перевод чисел существенно упрощается. В ЭВМ наиболее часто
Прямой код
Прямой код соответствует обычной записи числа со своим знаком. Положительное число имеет в знаковом разряде символов 0, отрицательное – 1. Прямой код обозначают [A]пр, а знаковый разряд
Обратный код
Для образования обратного кода коэффициент С в выражении (3.3) выбирается равным максимальному числу, которое может быть записано в регистре с n целыми и m дробными разрядами:
С = 2n
Сложение чисел в обратном коде
Покажем, что при использовании обратного кода вычитание можно заменить сложением в обратном коде. При этом сумма обратных кодов равна обратному коду алгебраической суммы.
Рассмотрим возмож
Дополнительный код
Идея образования дополнительного кода возникла в связи со стремлением избавиться от операции циклического переноса, которая приводит к увеличению времени выполнения операции сложения. Оказывается ,
Лекция 6. Переполнение разрядной сетки
В ЭВМ количество разрядов, используемых для представления чисел, ограничено. Поэтому при сложении двух чисел с одинаковыми знаками их сумма может оказаться больше по модулю, чем мак
Формы представления в ЭВМ числовых данных
В математике широко используются две формы записи чисел: естественная и нормальная.
При естественной форме число записывается в естественном натуральном виде, например: 28759 – цело
D-триггер
D-триггер имеет один информационный вход D и вход синхронизации С. Схема D-триггера и обозначения его на ф
D-триггер с дополнительными RS входами
Реализация D-триггера с использованием RS- триггера связана с увеличением состава схемы на один инвертор, увеличением числа входов (до трех) в схемах И-НЕ. Схема D-триггера, дополненная
Двухтактный D-триггер
Во многих схемах, например, в регистрах сдвига, устойчивая работа триггера возможна только, если занесение в него новой информации осуществляется после передачи информации о его состоянии в следующ
Регистры
Регистры —это набор простейших запоминающих устройств (например, триггеров) для временного хранения двоичной информации в устройствах обработки информации. Регистры можно получ
Счетчики
Счетчики – это устройства, предназначенное для счета числа импульсов, поступающих на его вход с фиксацией результатов. Счетчик, как и сдвигающий регистр, составляется из цепочки триггеров. На рис.
Одноразрядный двоичный сумматор
Одноразрядный двоичный сумматор является комбинационной схемой с тремя входами и двумя выходами (рис.4.15).
Лекция 9. Типовые устройства ЭВМ
Дешифраторы
Дешифратор – это устройство, которое имеет n входов и 2 n выходов, причем каждой i-ой комбинации сигналов на входе соответству
Мультиплексор
Мультиплексор (MX, MUL), (рис. 4.20.) –это электронное устройство, которое имеет несколько информационных D-входов и один выход F, осуществляющее последовательное подключение входов к выходу
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов