Antik (1082243), страница 9
Текст из файла (страница 9)
п.5). Соответственно DGtu при любом t ≥ n выражается в виде линейнойкомбинации матриц Du, DGu, DG2u, … , DGn-1u. Поэтому, еслиравны нулю все эти матрицы, то DGtu = 0 для всех t ≥ 0.Составим диагностическую матрицу (n, n)H=DDGDG2:DGn-1В силу равенства (7) Hs1=Hs2 или H(s1-s2) = 0. Состояния s1и s2 эквивалентны, если вектор u=s1-s2 принадлежит ядру (нульпространству) матрицы H. Размерность ядра называют дефектом(defekt) матрицы. Если ранг диагностической матрицы H равен r(rangH=r), то defektH = n – r; число классов эквивалентности равно 2r (для общего случая поля GF(p) это число равно pr ).Для автомата A с матрицами G, C, D, E построим минимальный автомат Ã следующим образом: состояниям s автоматаA поставим в соответствие состояния š=Тs автомата Ã, где (r, n)матрица Т составлена из r (r<n, если r=n, то автомат уже минимальный) линейно независимых строк диагностической матрицыH.
Характеристические матрицы автомата Ã определим следующим образом:Ğ=TGR, Č=TC, Ď=DR, Ĕ=E ,где R (n, r)-матрица правая обратная к T (TR=Ir).59Для автомата A, находящегося в состоянии sj , новое состояние определяется из уравнения (2')sf := Gsj+ CaОпределим, в какое состояние перейдет автомат Ã, находящийся в состоянии šj= TsjĞšj + Ča = TGR(Tsj) + TCaРассмотрим состояние ŝ=(RT)s, для которого Tŝ=TRTs=Ts,это означает, что состояния ŝ и s эквивалентны. ПоэтомуTG(RTsj) + TCa = T(Gsj + Ca) = T(sf) = šf,т.е.
автомат Ã оказывается в состоянии эквивалентном состояниюsf автомата A.Выходное значение автомата Ã определяем из (1.2")Ďš + Ĕa = DRTs + Ea = Ds + Ea = bЭто значение такое же, как и в автомате A. Это означает, что автоматы эквивалентны.6. Минимально-канонические и простые каноническиеформыМинимальный ЛА преобразованием подобия может бытьприведен к эквивалентному минимальному автомату с основнойхарактеристической матрицей, имеющей блочно-диагональныйвид. В этом случае внутренняя сеть состоит из взаимнонезависимых регистров сдвига.
Такой ЛА называется минимально-каноническим.Минимальный ЛА с одним выходом можно привести к автомату с основной характеристической матрицей в форме сопровождающей. Такой автомат имеет простейшую выходную схему,выход связан только с одним элементом памяти регистра сдвига.Для произвольного ЛА с более чем одним выходом может бытьпостроен эквивалентный автомат, как минимальный по отношению к каждому выходу отдельно. Структура такого ЛА называется простой канонической.
В общем случае он не является минимальным автоматом, но имеет простые выходные соединения.607.Независимость от состоянийПоскольку ЛА всегда может быть приведен к простому каноническому виду, это означает, что выходное значение можноопределить как функцию только входных и выходных значенийза предыдущие r тактов, т.е. независимо от состояний, см. так жеп.II-2.3. Разумеется, этот результат можно получить и аналитически. Исходя из формулы полной реакции (3.1"), обозначимttz(t) = DG s(0) = b(t) – ∑ W(t-v) a(v)v=0Если минимальный аннулирующий полином матрицы G имеетвид: ΩG = ω0 + ω1x + ω2x2 + … + ωr-1xr-1 + xr , тоDGrs(0) = –ω0Ds(0)–ω1DGs(0)–ω2DG2s(0)–…–ωr-1DGr-1s(0)или z(r) = – ω0z(0) – ω1z(1) – ω2z(2) – … – ωr-1z(r-1),rr−1tv=0t=0v=0тогда b(r) – ∑ W(r-v)a(v) = – ∑ ωt (b(t) – ∑ W(t-v)a(v))r−1rr−1tt=0v=0t=0v=0b(r) = – ∑ ωtb(t) + ∑ W(r-v)a(v) + ∑ ωt ∑ W(t-v)a(v)),b(r) = f(a(0),…,a(r), b(0),…,b(r-1))Частный случай – ЛА без обратных связей.
Выходное значение в этом случае зависит только от входных значений в томже такте и за предыдущие k тактов (k≤r). ЛА обладает этим свойством, если k является наименьшим числом, для которого DGk=0.8.Автономные линейные автоматы (АЛА)ЛА, входы и состояния которых не зависят от входных воздействий, называются автономными линейными автоматами(АЛА). Схема внутренней сети любого ЛА является схемой АЛАи (см. п.6) всегда может быть приведена к каноническому виду.Поэтому, рассматривая схемы АЛА, достаточно ограничитьсятолько схемами регистров сдвига – рис.1 и рис.2.Для этих схем можно записать выходную рекуррентную последовательность:61b(t+n) = pn-1b(t+n–1)+…+p1b(t+1)+p0b(t).Выходная последовательность АЛА однозначно определяется начальным состоянием s(0) и является свободной составляющей полной реакции ЛА (см. п.3).8.1.
Анализ АЛА.Любой неособенный, т.е. не делящийся на x, полином P(x)над полем GF(k) является делителем полинома 1–xi для некоторого целого числа i. Наименьшее такое положительное число i называется показателем, которому принадлежит полином P(x).Если degP=n (степень полинома) и полином принадлежит показателю T, то число T является делителем числа kn-1.Пусть Ψ(х) неприводимый полином над полем GF(k), т.е.
полином, единственными делителями которого являются константаα и Ψ(х). Если полином Ψ(х) принадлежит показателю Т, то полином (Ψ(х))j принадлежит показателю krT, где kr-1<j≤ kr.Пусть P(x)= P1(x)P2(x), а P1(x) и P2(x) взаимно просты и принадлежат соответственно показателям Т1 и Т2, тогда P(x) принадлежит показателю Т=н.о.к.(Т1,Т2).Для строго периодической последовательности(8.1’)bt : b1b2 ... bT, b1b2 ... bT, ...,с периодом Т назовем представляющим полином(8.1")B(x)=b1xT-1+b2xT-2+...+bT-1x+bTПусть АЛА А имеет неособенный полином обратной связиP(x), принадлежащий показателю Т. Тогда полиномϑ(x)=(1–xT)/P(x)называется воспроизводящим полиномом АЛА А.
Если degP=n, тоdegϑ=T–n. Любой полином, принадлежащий векторному пространству с базисом{ xn-1ϑ(x), xnϑ(x), ..., x2ϑ(x), xϑ(x), ϑ(x) },представляет одну из строго периодических последовательностей (с периодом Т), являющихся выходными последовательностями АЛА.Пусть АЛА А имеет неособенный полином обратной связиP(x), принадлежащий показателю Т. Если полином P1(x), принадлежащий показателю Т1, является делителем полинома P(x), то62ϑ1(x)=(1–xT)/P1(x)является полиномом, воспроизводящим в базисе{ xn-1ϑ1(x), xnϑ1(x), ..., x2ϑ1(x), xϑ1(x), ϑ1(x) }строго периодические последовательности с периодом Т1.8.2.
Синтез АЛАДля любого n и любого простого k существует, по крайнеймере, один неприводимый полином n-й степени над полем GF(k),принадлежащий показателю (kn –1). Этот полином называется полиномом, принадлежащим максимальному показателю или короче примитивным полиномом. Если полином обратной связи примитивный, то АЛА называются АЛА максимального периода. Дляnk=2 период выходной последовательности в автомате равен 2 -1.nВсе ненулевые выходные последовательности имеют период 2 -1.Любые n последовательных символов (кроме n нулей) последовательности максимального периода однозначно задают все послеnдующие символы, а первые 2 -1 подпоследовательностей длины nпоследовательности максимального периода составляют множество всевозможных различных ненулевых последовательностейдлины n. За время периода любая ненулевая подпоследовательn-mность длины m<n встречается 2 раз, нулевая такой же длиныn-m2 -1.
Одно из применений последовательностей максимальногопериода – порождение псевдослучайных чисел.Пусть необходимо построить АЛА, воспроизводящий заданное множество строго периодических последовательностейb1(t), b2(t), ..., br(t), причем bi(t) имеет минимальный период Тi.Находим Т=н.о.к.(Т1,Т2, ...,Тr). Последовательности bi(t) дополняем до строго периодических последовательностей периода Т, азатем представим, аналогично (1), в виде полиномов Bi(x).
Найдемϑ(x)=н.о.д.(1–xT, B1(x), B2(x), ..., Br(x)),тогда P(x) = (1–xT)/ϑ(x) будет полиномом обратной связи АЛАнаименьшей размерности, воспроизводящего заданные периодические последовательности.Если в «худшем» случае ϑ(x)=1, или если не стремится к63наименьшей размерности автомата, то всегда можно принятьP(x)=1–xT, что соответствует АЛА в виде кольцевого регистрасдвига с простейшими связями и без сумматоров.
Кольцевой регистр сдвига реализует все периоды равные делителям числа Т.9.Линейные автоматы с нулевым начальным состояниемЛА с нулевым начальным состоянием s(0)=0 обозначим –0ЛА.На выходе 0ЛА образуется только вынужденное движение.Во-первых, это часто применяемый режим работы линейных автоматов, используемых как преобразователи входных последовательностей в выходные. Во-вторых, вынужденное движение является одной из составляющих полной реакции ЛА в дополнениек свободному движению (см. п.3).При s(0)=0 из формул полной реакцииtb(t) = ∑ W(t-v) a(v) ,(9.1)v=0следует, что значение сигнала на каждом выходеkktbi(t) = ∑ ∑ wij(t-v) aj(v) = ∑ bij(t)j =1 v =0j =1равно сумме составляющих, каждая из которых зависит от одноговхода.Поэтому в дальнейшем при изучении 0ЛА достаточно рассматривать двухполюсные автоматы.Для двухполюсного 0ЛА W(t) становится скалярной функцией w(t), а уравнение (1) принимает формуtb(t) = ∑ w(t) a(v) ,v=09.1.
D–преобразованиеДля решения задач анализа и синтеза 0ЛА используется аппарат дискретного преобразования Лапласа (D–преобразования).9.1.1. Дискретное преобразование Лапласа двоичной последовательности f(t) = f(0),f(1),f(2),f(3),... (при t<0 f(t)=0) обозначается D[f(t)] или F и определяется как формальный степенной ряд64над полем GF(2):∞D[f(t)]=F= ∑ f ( t )d t =f(0)+f(1)d+f(2)d2+f(3)d3+...(9.1)t =0Последовательность f(t) и ее дискретное преобразование Fназываются парой соответствия. Последовательность f(t) называется оригиналом, а функция F – изображением.9.1.2. Сдвиг последовательности f(t–k) действует на изображение как умножение на dk.
(По этому d называют операторомзапаздывания.)∞t∞∑ f ( t − k )d = ∑ f ( t ' )dt =kt '=0t '+k∞k= d ∑ f ( t ' )d t ' = dk Ft ' =09.1.3. Пусть f(t) строго периодическая последовательность спериодом T, т.е. f(t)=f(t+T), тогда согласно предыдущему пункту:∞F = ∑ f ( t )d t = (f(0) + f(1)d +. . .+ f(T-1)dT-1) ×t =k× (1 + dT + d2T + . . . ) ==f(0) + f(1)d +. . .+ f(T-1)dT-11 – dT9.1.4. Функцию F называют обратимой функцией, если в результате обратного преобразования D–1[F] может быть полученоригинал:D–1[F] = ft = f(t)Любые обратимые изображения, встречающиеся при изученииЛА, могут быть представлены в виде:F=h(d)/q(d),где h(d) и q(d) полиномы от d, такие, что минимальная степень dв q(d) не превышает минимальной степени d в h(d).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
