Antik (1082243), страница 8
Текст из файла (страница 8)
Автомат является IL(B)-автоматом тогда и только тогда,когда для каждого состояния выходные значения различны дляразличных входных значений.Необходимость этого условия следует из следующего рассуждения. Если в некотором состоянии при различных входныхзначениях выходное значение одно и тоже, то в этом случаевходное значение нельзя восстановить однозначно.Достаточность условия следует из возможности однозначного определения входного значения по отличающимся друг отдруга выходным значениям в каждом состоянии автомата.
Построение инверсного автомата очевидно.3.2. Для восстановления входной последовательности IL(E)автомата по выходной, надо эту выходную последовательностьзапомнить и затем, двигаться от финального состояния к началу,вычислять входные значения. Что бы проверить возможность такого вычисления, надо построить тестовую таблицу всех «обратных движений», допускающих однозначное восстановлениевходного значения.Столбцы тестовой таблицы соответствуют всем возможнымвыходам – bi.В первой части тестовой таблицы строки соответствуют отдельным состояниям автомата – sj. Содержимым клетки с координатами (bi,sj) является множество состояний – Sij, предшествующих такому событию, т.е.
все те состояния, у которых в строках автоматной таблицы содержится элемент (bi,sj). При этом, если такой элемент появляется в разных столбцах (при разныхвходных значениях) автоматной таблицы, то однозначное восстановление входного значения невозможно. Делается вывод, чтоэто не – IL(E)-автомат. (Это необходимое условие можно проверить до построения тестовой таблицы. Достаточным условиемявляется единственность каждого из элементов (bi,sj) в автоматной таблице, что так же можно проверить до построения тестовойтаблицы.)Строками второй части тестовой таблицы являются вновь52появившиеся в первой части таблицы множества состояний.Клетка с координатами (bq,Sij) заполняется аналогично множеством состояний, предшествующих событиям из множества {(bq,sk),∀sk∈Sij}. При этом, если элементы этого множества встречаютсяв разных столбцах автоматной таблицы, то делается вывод, чтоэто не – IL(E)-автомат.Последующие части тестовой таблицы строится аналогичновторой.
Процесс построения таблицы естественным образом заканчивается.Можно построить инверсный автомат, который вычислитвходную последовательность по записанной выходной последовательности и финальному состоянию IL(E)-автомата. В IL(E)автомате ориентацию всех дуг изменить на противоположную, вметке каждой дуги поменять местами входы и выходы. При этомможет получиться недетерминированный автомат – источник.Начальное состояние источника соответствует финальному IL(E)автомата.4.Условная синхронизацияНаряду с канонической структурой СЦА (рис.1. гл.I) в некоторых случаях для более экономной реализации комбинационнойчасти автомата возможно использование структуры, представленной на рис.16.Рис.16.
СЦА с условной синхронизациейДля реализации переходов по петлям, т.е. в тех случаях, когда нужно оставить автомат в предыдущих состояниях, достаточно с помощью дополнительной КС запретить синхронизацию па-53мяти автомата. При этом значение на информационных входахRG безразлично. Временные параметры сигнала синхронизациидолжны быть определены так, чтобы на выходе h не было переключений при syn=1.Пример см. гл.I, п.7.2.ГЛАВА III.
ЛИНЕЙНЫЕ АВТОМАТЫЛинейные автоматы (ЛА) используются в аппаратуре и программном обеспечении систем кодирования и декодированияданных, цифровой фильтрации, устройств обнаружения и исправления ошибок, контроля цифровых схем (сигнатурный анализ).1.Основные определенияСинхронный цифровой автомат линеен, если комбинационная логика для вычисления функций перехода и выхода линейна.По определению функция линейна, если она удовлетворяетпринципу суперпозиции. Для булевых функций это означает:f(0,...,0)=0f(x1,x2,...,xn)=f(x1,0,...,0)+f(0,x2,...,)+...+f(0,0,...,xn)Комбинационная логика линейна, если используется единственная булевская операция «сложения по модулю 2». Элемент,ее реализующий (М2), будем называть сумматором.Каждому из одноразрядных выходов КС линейного автомата можно сопоставить один многовходовой сумматор по модулю2 (Σ2). Тогда значения состояний и выходов могут быть заданыуравнениями:nkj =1nj =1kj =1j =1si (t + 1) : = ∑ 2 g ij sj (t ) + ∑ 2 cij a j (t )b i (t )= ∑ 2 d ij sj (t ) + ∑ 2 eij a j (t ) ,(1.1')(1.1")где коэффициенты (gij, cij, dij, eij) равны {0, 1} и означают отсутствие или присутствие булевской переменной на входе сумматора.Эти же уравнения можно рассматривать не как булевскиеуравнения, а как линейные уравнения над полем GF(2).
Коэффи-54циенты и переменные имеют только двоичные значения {0,1}.Сложение и вычитание выполняются по модулю 2 (mod2). Поскольку (–1=1)mod2, то операция вычитания по mod2 может бытьзаменена операцией сложения по mod2, которую и обозначаемзнаком +.Уравнения (1) можно переписать в матричной форме:s(t+1) : = G s(t) + C a(t)(1.2')b(t)= D s(t) + E a(t),(1.2")где a =║ai║k x 1 , s =║si║n x 1 , b =║bi║m x 1векторы входной, состояний, выходной; матрицыG = ║gij║n x n , C =║cij║n x kD = ║dij║m x n , E =║eij║m x kназываются характеристическими (G–называется основной характеристической); n–количество двоичных элементов памяти,k–количество двоичных входов, m–количество двоичных выходов.Для ЛА с одним входом и одним выходом (двухполюсногоЛА) матрицы C и D становятся векторами, матрица Е вырождается в единственный коэффициент равный 0 или 1.2.
Линейные автоматы без потери информацииЕсли ранг матрицы Е равен k (количеству входов), то ЛАявляется автоматом без потери информации, см. п.II-3, по начальному состоянию и выходной последовательности можно однозначно восстановить входную последовательность (IL(B)–автомат). Это утверждение следует из уравнений (2) индукциейпо t.3.Формула полной реакции ЛАМетодом индукции по t можно показать, что для любого t≥0ts(t+1) : = Gt+1 s(0) + ∑ Gt-vC a(v)b(t)v=0t= DGt s(0) + ∑ W(t-v) a(v) ,v=0(3.1')(3.1")55( t − v = 0)⎧Eгде W(t – v) = ⎨t − v −1C ( t − v > 0)⎩DGФормулу (3.1") называют формулой полной реакции ЛА.Из (3.1") следует, что выходной сигнал состоит из двух составляющих: свободного движенияb(t)|своб = DGt s(0) ,получаемого при a(t) = 0 для всех t ≥ 0,и вынужденного движенияtb(t)|вын = ∑ W(t-v) a(v) ,v=0получаемого при s(0) = 0. Для любой заданной входной последовательности a(t) (t = 0, 1, 2, …) и заданного начального состояния s(0) эти составляющие могут быть вычислены отдельно,а затем сложены.Для ЛА с одним входом и одним выходом – двухполюсногоЛА W(t) становится скалярной функцией w(t), а уравнение (3")принимает формуtb(t) = ∑ w(t) a(v) ,v=04.
Изоморфные и эквивалентные линейные автоматыОпределения изоморфизма и эквивалентности (см.I-6.1), разумеется, распространяются и на ЛА.Если ЛА A характеризуется матрицами G, C, D, E,а ЛА à характеризуется матрицамиĞ=PGP-1, Č=PC, Ď=DP-1, Ě=E ,(4.1)где P – некоторая неособенная матрица (detP ≠ 0) над полемGF(2), то A и à изоморфны.Состоянию s автомата A изоморфно соответствует состояние š= Ps автомата Ã. Изоморфизм автоматов проверяется подстановкой в (2).Матрицы G и Ğ называются подобными.
Две матрицы подобны тогда и только тогда, когда у них равны характеристические полиномы (det(M –xI)), с точностью до мультипликативной56константы.Преобразование подобия изменяет матрицы линейных операторов, и соответственно – структуру (схему) линейного автомата. С помощью такого преобразования можно привести матрицу квиду удобному для реализации.Внутренней сетью линейного автомата называется частьреализации, которая определяется только основной характеристической матрицей G.
Внутренняя сеть соединяет между собойэлементы памяти автомата. Среди возможных структур внутренней сети рассмотрим структуры удобные для реализации.Сопровождающей матрицей MP(x) нормированного полинома над полем GF(2)P(x) = p0 + p1x + p2x2 + … + pn-1xn-1 + xnназывается (n, n) – матрица:00100100.MP(x) =(4.2').00p000p100p2.01pn-1Полином P(x) является характеристическим полиномом(P(x)=det(M–xI)) и минимальным аннулирующим полиномом этойматрицы, т.е. полиномом наименьшей степени, для которогоP(M) = 0.
Характеристический полином – всегда аннулирующий.Матрица MP(x) подобна своей транспонированной матрице010001000.M TPP( x ) =p0p1p2(4.2")..001pn-1Внутренняя сеть, реализующая сопровождающую матрицу,называется односумматорным регистром сдвига.57Внутренняя сеть, реализующая транспонированную сопровождающую матрицу, называется многосумматорным регистромсдвига.Рис.1. Односумматорный регистр сдвигаРис.2. Многосумматорный регистр сдвигаПолином P(x) называется полиномом обратной связи, поскольку однозначно определяет скалярные константы в цепях обратной связи регистров сдвига.Если характеристический полином может быть представленкак произведение нормированных полиномов P1(x), P2(x), … ,Pk(x), то матрица М с характеристическим полиномом P(x) подобна матрице блочно - диагонального вида:MP1(x)*M =MP2(x).(4.3)..*MPk(x)Подобие M и M не нарушается, если меняется порядокблоков или любой блок заменяется транспонированным.5.Минимальные линейные автоматыОбщее определение минимальности автоматов (п.I-6.2)справедливо и для ЛА.Линейный автомат, не имеющий эквивалентных состояний –минимальный.Из формулы полной реакции (3.1") следует, что s1 и s2 эквивалентны тогда и только тогда, когда для любого t ≥ 0 и любого а(t)58ttttDG s1 + ∑ W(t-v) a(v) = DG s2 + ∑ W(t-v) a(v)v=0v=0или в том и только в том случае, если для любого t ≥ 0DGt s1 = DGt s2(5.1')tDG (s1–s2) = 0(5.1")или иначеЧтобы установить эквивалентность состояний n–мерногоавтомата с N=2n состояниями, достаточно последовательностидлины N-1 (п.I-6.1); для ЛА достаточно последовательностидлины n.Поскольку для матрицы G минимальный аннулирующийполином степени не выше n, то Gt для любого t ≥ n выражаетсяполиномом относительно G степени не выше n-1 (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
