конечные автоматы ч.3 (561951)
Текст из файла
1Элементарные автоматыЭлементарный автомат – устройство с памятью, имеющее два устойчивых состояния иобладающее полнотой переходов и выходов.Триггеры с одним входомD-триггер: Q(t+1) = D(t).СTTQ(t)D(t)01Q_QDУсловное обозначение010101101D10таблица переходовQ(t+1)10граф переходовQQ(t)00111диаграмма КарноQ(t+1)0101D0101матрица переходовT-триггер: Q(t+1) = (QT + Q T)t1QСTQ(t)TTT01QУсловное обозначение0101100001таблица переходовграф переходовQ(t+1)Q11Tдиаграмма Карноасинхронный T-триггер1Q(t)0011Q(t+1)0101T0110матрица переходовсинхронный Т- триггер.2Триггеры с двумя входамиR-S-триггерSCRR(t)S(t)00110110TTУсловное обозначение0100V10011RТаблица переходов00V01Граф переходов01000V100111000V01Матрица переходовQ(t+1) = (S+Q R )t ,Q(t+1) = R (t) (S(t)+Q(t)),_1S_Диаграмма КарноQ(t+1)Q(t)110QQ(t)0 10 11 1- 0 0Q(t)ÆQ(t+1)R(t)S(t)0Æ0b100Æ1011Æ0101Æ10b2Табличное представлениеRS=0;RS=0.S-триггер при S=1 и R=1 переходит в состояние 1SCRTTQQа)R(t)S(t)00110110Q(t)0011011110б)01V1100V10010в)00V01V111г)Q(t)ÆQ(t+1)R(t)S(t)0Æ0b100Æ1b211Æ0101Æ1b3b*3а- условное обозначение;б- таблица переходов;представление матрицы переходовв- граф переходов; г- табличноеQ(t+1) = (S + Q R )t = ((S + R )(S+Q))tДля построения матрицы перехода определяем значения вспомогательной функции Xjk:переход 0→0; X00 = R S + R S = S , откуда S=0; R= b1; переход 0→1; X01 = R S + R S = S ,откуда S=1; R.
= b2; переход 1→1; X11 = R S + R S +R S= R +S = b3 + b*3 ≡ 13R-триггер при R=1 и S=1 переходит в состояние 0Q(t+1) = R (t) (S(t)+Q(t))E-триггер при R=1 и S=1 сохраняет предыдущее состояниеQ(t+1) =( R S+Q R +QS)t .J-K-триггерSJCKRМатрицы переходов R- и E- триггеровRтрEтрQ(t)→Q(t+1)R(t) S(t) R(t) S(t)b1*b1*b1b10→00→101011→01b2101→10b3b2b*2при R=1 и S=1 изменяет состояние на противоположное (K ≡ R, J ≡ S)TT01V1100V10Q_Q00V101010V11R(t)S(t)00110110Q(t)0011011100Q(t)→Q(t+1)0→00→11→01→1R(t)b1b210S(t)01b3b4Q(t+1)=(Q K + Q J)tОпределение функций возбуждения ЭАФункции возбуждения входов Pi элементарных автоматов Qi , i = 1, n Q , определяются врезультате решения уравнений:GGfi (Qi (t ), Pi ) = ϕi (Q(t ), C (t ))Здесь fi - функция переходов триггера, на котором реализуется элементарный автомат;φi – функция внешних переходов элементарного автомата.Pi= Di или Ti для одновходовых триггеров D и T соответственно.Pi=< Ri, Si > или < Ki, Ji > для двувходовых триггеров.Методы решения уравнения (1):1.
Аналитические; 2. Табличные; 3. Сравнения.(1)4Аналитический методопределения функций возбуждения.GGОбозначим через ν = (Q( t ), C( t ))D триггер.D i = ϕ i (ν)T триггер.Ti Q i + T i Q i = ϕ i ( ν) . Решая его, получимTi = Q i mod 2 ϕ i ( ν)R-S триггер.⎧Si + R i Q i = ϕ i ( ν),⎨RS=0⎩ i iСистема приводится к виду ϕ i ( ν) mod 2 (Si + R i Q i ) + R iSi = 0 . Решая уравнение, получим:S i = Q i ϕ i ( ν ) + h 1 ( ν )ϕ i ( ν )R i = Q i ϕi ( ν ) + h 2 ( ν ) ϕi ( ν )J-K триггер.K i Q i + J i Qi = ϕ i ( ν) .
Решая его, получим:J i = Q i ϕ i ( ν ) + h 1 ( ν )Q iK i = Q i ϕi ( ν ) + h 2 ( ν ) QiS триггер.Si + Q i R i = ϕ i ( ν) . Решая его, получим:S i = Q i ϕ i ( ν ) + h 1 ( ν )ϕ i ( ν )R i = Q i ϕi ( ν ) + h 2 ( ν ) Q i + h 1 ( ν ) h 2 ( ν )R триггер.R i (Si + Q i ) = ϕ i ( ν) . Решая его, получим:Si = Qi ϕ i ( ν) + h1 ( ν)R i = Q i ϕ i ( ν ) + ( h 1 ( ν ) + h 2 ( ν )) ϕi ( ν )E триггер.R iSi + R i Q i + Si Qi = ϕ i ( ν) .Решая его, получим:S i = Q i ϕ i ( ν ) + h 1 ( ν )( Q i + ϕ i ( ν ))R i = Q i ϕi ( ν ) + ( h 1 ( ν ) + h 2 ( ν )) ϕi ( ν ) + h 1 ( ν ) h 2 ( ν )Q iGGЗдесь h1 ( ν), h 2 ( ν) - неопределённые функции аргументов ν = (Q( t ), C( t )) . В частности, еслиположить h1 ( ν) = h 2 ( ν) = 0 , получим для всех двухвходовых триггеров:S i ( J i ) = Qi ϕ i ( ν )R i ( K i ) = Q i ϕi ( ν )Более простые выражения получаются путём доопределения неопределённых функций h1 , h 2 .5Пример.
Для автомата S2 функция внешних переходов элементарного автомата Q1 (рис. 9,раздат. материал 6) имеет вид:ϕ1 (Q1 , Q 2 , C1 , C2 ) = C1C2 .Тогда функции возбуждения J-K триггера, в соответствие с полученными ранее уравнениями,определяются следующим образом:J 1 = Q1 C1 C2 + h 1 ( ν )Q1K 1 = Q i ( C1 C2 ) + h 2 ( ν ) Q1 Доопределивh 1 ( ν ) = C1 C 2 , h 2 ( ν ) = C1 C 2получим:J1 = Q1C1C2 + C1C2Q1 = C1 C 2K1 = Qi C1C2 + C1C 2Q1 = C1C2 = C1 + C2Табличный метод получения функций возбуждения.Предположим, что функция переходов элементарного автомата Qi задана диаграммой КарноДиаграмма для функции переходовДиаграмма для функции возбужденияk-го входа, i-го триггераДиаграмма Карно функции возбуждения триггера может быть получена путём замены нулей иединиц диаграммы Карно функции внешних переходов значениями входных сигналовсоответствующего входа, полученными из матрицы переходов этого триггераQiÆQt+10Æ00Æ11Æ01Æ1DтрD0101TтрT0110R-SтрR Sb1 00 11 00 b2SтрR Sb1 0b2 11 0b3 b*3RтрR Sb*1 b1011b20b3EтрR Sb*1 b10110b2 b*2J-KтрK Jb1 0b2 11 b30 b4Неопределённые коэффициенты bi, b*j внутри одной таблицы доопределяются независимо.Зависимые коэффициенты bi, b*i в соседних таблицах для разных входов доопределяются в*соответствие с уравнением связи: b i + b i ≡ 1,i = 1, 2 .6Пример применения табличного методаОпределим функции возбуждения K1 и J1 элементарного автомата Q1 на J-K триггере автоматаМили S2, функции внешних переходов которого изображены на рис.
9 разд. материала 6 .Метод сравнения.Приравниваются коэффициенты в левой и правой частях уравнения (1.) при Q i и Qi .ПримерОпределить функции возбуждения K1 и J1 элементарного автомата Q1 из предыдущего примера:Имеем:K1Q1 + J 1 Q1 = C1 C2K1Q1 + J 1 Q1 = C1 C2 Q1 + C1 C2 Q1Отсюда:K1 = C1 C2K1 = C1 + C 2J 1 = C1 C2Определение функций выходов.Функции выходов определяются из таблиц выходов структурного автомата.Для рассмотренного выше автомата Мура S1 из таблицы выходов получим диаграммы Карно дляполучения выходных сигналов Z1 и Z2.Для автомата Мили S2 из таблицы выходов аналогично определяем выходные сигналы Z1 и Z2..
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
