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

Абстрактный и структурный конечный автомат. Примеры.

Структурный автомат. В отличие от АА, имеющего один вход и один выход, структурный автомат (СА) имеет р входов ( u ₁ , u ₂ , ..., u _Р ) и ℓ выходов ( v ₁ , v ₂ ,..., v_e ), на каждом из которых сигнал может принимать два значения – 0 или I .

Таким образом, букве х _i входного алфавита АА соответствует вектор, компонентами которого являются нули и единицы – сигналы на входах СА.

31. Описание цифрового устройства булевой функцией. Примеры.

Описание цифрового устройства булевой функцией. Примеры.

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

Составим таблицу истинности для шифратора.

Y1	Y2	X1	X2	X3	X4
0	0	1	0	0	0
0	1	0	1	0	0
1	0	0	0	1	0
1	1	0	0	0	1

Составим СДНФ для Y1, Y2(выбираем строки равные “1”. Если значение переменной равно 0, то она записывается с инверсией. Если значение переменной равно 1, то без инверсии). Y1=X1^ X2^ X3 X4^ + X1^ X2^ X3^ X4. Y2= X1^ X2 X3^ X4^ + X1^ X2^ X3^ X4.

32. Способы задания булевой функции. Примеры.

Функция f, зависящая от n переменных x₁, x₂, ...., x_n, называется булевой, или переключательной, если функция f и любой из ее аргументов X_i, (i E 1..n) принимают значения только из множества {О, 1}. Аргументы булевой функции также называются булевыми.

Произвольная булева функция задается одним из трех способов: матричным (табличным), геометрическим и аналитическим.При матричном способе булева функция f (х₁, ...,х_n) задается таблицей истинности (табл. 1.1 и 1.2), в левой части которой представлены все возможные двоичные наборы длины n, а в правой указывается значение функции на этих наборах. При аналитическом способе булева функция задается формулами, т. е. аналитическими выражениями, построенными на основе операций булевой алгебры. Аналитический способ задания булевых функций занимает особое место в проектировании цифровых автоматов. Фактически, все преобразования над булевыми функциями, необходимые для построения цифровых автоматов, ведутся на аналитическом уровне. При геометрическом способе булева функция f (х₁, ..., х_n) задается с помощью n-мерного куба. В геометрическом смысле каждый двоичный набор у = <y₁, y₂,...,y_n> y_i E {0,1} есть n-мерный вектор, определяющий точку n-мерпого пространства. Исходя из этого, все множество наборов, на которых определена функция n переменных, представляется вершинами n-мерного куба. Отмечая точками вершины куба, в которых функция принимает единичное (либо нулевое) значение, получим геометрическое представление функции. Например, булева функция, заданная табл. 1.1, геометрически представляется 3-мерным кубом (рис. 1).

33.Минимизация булевой функции. Примеры.

Минимизацией называют преобразование заданной булевой функции с целью уменьшения общего числа переменных и операций. Процесс минимизации имеет важное значение при технической реализации дискретных устройств, так как при этом уменьшается общее количество элементов, увеличивается надежность и устройства становятся боле экономичными. Аналитический способ:Путем тождественных преобразований на основе законов алгебры логики. Речь идет о том, чтобы перейти от СДНФ к ДНФ с минимумом слагаемых, при этом количество множителей в каждом слагаемом должно быть также минимальным (избавиться от "совершенства"). Иными словами - максимально уменьшить количество переменных и операций в СДНФ.Упростить функцию можно непосредственно с помощью алгебраических преобразований с использованием выше рассмотренных тождеств (что не всегда просто при большом количестве переменных), а также путем преобразования таблицы состояний функции.Пример: логическая функция представлена в виде СДНФ: Y=A B^ C^+ A B^ C+ A B C+ A B C^ .Элементарные конъюнкции называются соседними (логически смежными), если они отличаются только одной переменной, применение к ним операции «склеивания» понижает их ранг на единицу. Здесь соседние 1 и 2 конъюнкции, а также 3 и 4. Y = A B^ C^+ A B^ C+ A B C+ A B C^ = A B^ (C^ + C) + A B (C + C^) =
A B^ + A B = A ( B^ + B ) = A

Метод карт Карно.

Логическая функция, записанная в СНДФ, может быть представлена в виде специальных таблиц, известных под названием карт Карно или диаграмм Вейча.

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

34. Представление цифрового устройства в виде двоичной решающей диаграммы. Примеры.

Двоичная решающая диаграмма (ДРД) рассматривалась ранее как рекурсивное графическое представление разложения Шеннона

логической функции от n переменных:

Ограничения на ДРД были введены Брайентом. По его определению, ДРД для логической функции f(x1,x2..Xn) – это имеющий корень, направленный, ациклический граф с множеством вершин V, которое содержит два вида вершин – нетерминальные и терминальные. Любая нетерминальная вершина помечена переменной Xi, где i {1,2,…,n} – индекс вершины v (обозначается index(v)), и имеет двух

наследников (к которым направлены две дуги) low(v) V и high(v) V. Каждая терминальная вершина w V помечена значением

value(w) {0,1}. Общее количество вершин (терминальных инетерминальных) определяет размер РД (size(РД)). ДРД называется приведенной, если она не содержит изоморфных подграфов и не содержит вершин v V таких, что low(v) = high(v). ДРД называется упорядоченной (УДРД), если для входных переменных установлен порядок (фактически - подстановка на множестве {1,2,…,n}) так, что ( index ( v )) < ( index ( low ( v ))) и ( index ( v )) < (index(high(v))) для всех нетерминальных вершин v V.

По характеру проявления

а) статические, сопутствующие переходным процессам, которые заканчиваются тем же логическим состоянием сигнала;б)динамические, в результате которых конечное значение сигнала

является противоположным исходному;

По последствиям

а) критические, то есть влияющие на правильность конечного устойчивого состояния;б) некритические, то есть не влияющие на правильность конечного

устойчивого состояния; 4) по вызывающей их причине

а) функциональные (из-за неодновременного изменения входных

сигналов);б) логические (из-за различных задержек распространения

сигналов в цепях схемы).

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

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

Двоичного моделирования .

Двоичная модель логической схемы ЦУ состоит из логических моделей

составляющих схему элементов. Порядок вычисления логических

функций элементов зависит от принятого метода моделирования. !!Сюда же 39!

Метод итераций Зейделя : от метода простых итераций отличается лишь тем, что при моделировании очередного элемента принимаются последние, полученные при моделировании, значения аргументов.

Методы итерационного и событийного моделирования. Примеры. Сравнение по точности и скорости.

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

моделируемого входного воздействия.

Метод событийного моделирования :

Моделируются не все элементы структуры, а только те, на входах которых появилось событие. Под событием понимается

изменение логического состояния сигнала хотя бы на одном из входов.