Antik (1082243), страница 10
Текст из файла (страница 10)
Тогдафункция F может быть выражена в виде степенного ряда от d,получаемого формальным делением h(d) на q(d).F = h(d)/q(d) =f0 + f1d + f2d2 + f3d3 +...D–1[F] = ft = f(t)65Пример 9.1.4.-1:d3 + d4 + d5 + d6 + d9F==1 + d + d3= d3 + d5 + d6 + d7 + d10 + . . .Соответственно последовательность: 00010111001. . .
.9.1.5. Для любого ненулевого полинома a(d), если h(d)/q(d) –обратимая функция, то ее оригинал такой же, как у функцииa(d)h(d)/(a(d)q(d)).Это означает, что обратимую функцию можно привести к функции вида – нормализовано обратимой, т.е. такой, что h(d) и q(d)взаимно просты и q(0)=1.9.1.6. Пусть последовательность периодическая с предпериодом длины τ и периодом длины Tf(t): a0 a1 ⋅ ⋅ ⋅ aτ–1. aτ aτ+1 ⋅ ⋅ ⋅ aτ+T–1, ⋅ ⋅ ⋅тогда, следуя п.9.1.3 и 9.1.4, получим изображениеF = a0 + a1d +. . .+ aτ–1dτ–1 +aτ + aτ+1d +.
. .+ aτ+T–1dT–1τ+d ×1–dTПосле приведения к общему знаменателю получим изображениев виде обратимого отношения двух полиномов относительно d.9.1.7. И наоборот, пусть изображение представлено обратимым отношением полиномов F=h(d)/q(d), где q(d)≠0. Функцию Fвсегда можно представить в видеF= P(d) + dτ r(d)/q(d),где P(d)- полином относительно d и deg(r) < deg(q). Если r(d)=0,то F является полиномом, а последовательность f(t) имеет конечную длину. Если же r(d) ≠ 0, то, обозначив через T показатель,которому принадлежит q(d), можно записать:q(d)b(d) = 1 – dTF= P(d) + dτ r(d)b(d)/( 1 – dT),где deg(r(d)b(d)) < T.
Это означает, что последовательность f(t)периодична с периодом T.66Пример 9.1.7.-1:d3 + d4 + d5 + d6 + d9F==1 + d + d31+d=d3+d5+d6+ d7×=1 + d + d3243567(1+d+d+d) (1+d)=d +d +d + d ×71+d41+ d + d5=d3+d5+d6+ d7×1 + d7=Получили последовательность в оригиналеf(t): 0001011.1000110,1000110,1. .
.9.2. Передаточная функцияДля двухполюсного ЛА канонические уравнения:s(t) := G s(t–1) + C a(t–1)(9.2')b(t) = D s(t) + e a(t),(9.2")Пусть S обозначает вектор-столбец, i-я координата которого равна изображению i-й координаты вектора состояния s(t), A и B являются изображениями последовательностей a(t) и b(t).
Тогда,применив к (2) D–преобразование, получимS = dGS + dCAB = DS + eA,где из (11) следует, что–dCA = (dG–I)SS = –(dG–I)–1dCAB = (e–D(dG–I)–1dC) AD(dG–I)ПdCB= e–Adet(dG–I)где (М)П матрица, состоящая из алгебраических дополненийdet(M). Отношение B/A, т.е. отношение изображений выходной ивходной последовательностей называется передаточной функцией.()67BD(dG–I)ПdCJ==е–det(dG–I)AФункция представима в видеh0 + h1d + h2d2+ ...
+ hndnJ=1 + q1d + q2d2+ ... + qndnВ тоже время знаменатель этой дробиdet(dG–I) = det(d(G–(1/d)I)) = dndet(G–(1/d)I))является полином двойственным к характеристическому полиному P(x)=det(G–xI), т.е. полиному обратной связи.(Полином [P(x)]*, двойственный полиному P(x) n-й степени, определяется как xnP(1/x).)9.3. Связь структуры ЛА и его передаточной функцииПередаточная функция может быть получена исходя изструктуры автомата.Передаточная функция D-триггера J=d.Если автомат может быть представлен в виде последовательного соединения линейных автоматов с передаточнымифункциями Jk (k=1,2,...,r) (рис.3),aJ1J2JrbРис.3.
Последовательное соединението передаточная функция всей конструкции:J = J1 ⋅ J2 ⋅ ... ⋅ JrВ частности, если путь от входа к выходу в линейном автоматепроходит через сумматоры и D-триггеры, то передаточная функция этого пути J = dk, где k - количество триггеров на этом пути.Для параллельного соединения линейных автоматов (рис.4)J = J1 + J2 + ... + JrВ частности, передаточная функция линейного двухполюсного автомата может быть определена как сумма передаточныхфункций всех путей от входа к выходу.68J1M2J2abJrРис.4. Параллельное соединениеМножество путей, соединяющих вход и выход, может бытьбесконечным, если существует путь, содержащий замкнутыйконтур (рис.5).aM2J1bJ2Рис.5.
Замкнутый контурПередаточную функцию для структуры, представленной нарис.3, можно найти из уравненияB=J1A + J2 J1B Æ J=B/A=J1/(1+J1J2)Пример 9.3.-1: Т-триггер (рис.6), изменяющий свое состояние и значение выходного сигнала только тогда, когда входнойсигнал равен 1, имеет передаточную функцию J = d/(1+d).Рис.6. Т-триггер9.4.Канонические структурыПередаточной функции вида69J=h0 + h1d + h2d2+ ... + hndn1 + q1d + q2d2+ ...
+ qndnгде любые коэффициенты qi и hj могут равняться нулю, соответствуют две канонические реализации в виде регистра сдвига рис.7 и в виде многосумматорного регистра сдвига - рис.8. Нулевое значение коэффициента означает отсутствие связи. Если полиномы не имеют общих делителей, то это реализации с минимальной памятью.Рис.7. Регистр сдвигаРис.8.
Многосумматорный регистр сдвига9.5. Эквивалентные преобразованияАлгебраическими манипуляциями можно, например, Dтриггер заменить некоторым линейным автоматом. Линейный автомат с передаточной функцией L(d) называется примитивным,если любая передаточная функция J(d) может быть реализована спомощью сумматоров и конечного числа автоматов L.Автомат L является примитивным, если существует функция G(x) такая, что G(L(d))=d вида G(x)=a(x)/b(x) причем a(0)=0,b(0)≠0, тогда J(G(L(d)))=J(d), а J(G(x))=J^(x). Заменяя в реализации J^(x) каждый x-элемент структурой L-автомата, получим70конструкцию с искомой передаточной функцией.
Вид функцииG(x) определен так, чтобы получить J^(x) обратимой и, следовательно, реализуемой.Пример 9.5.-1. Т-триггер с передаточной функциейL(d)=d/(1+d) является примитивным автоматом, так как существует определенная выше функцияG(x) = x/(1+x),G(L(d)) = (d/(1+d))/(1+(d/(1+d))) = dПусть определен автомат с реализацией рис.9 и соответственно передаточной функциейJ(d) =1+d21+d+d2+d3+d4В таком случаеJ(G(x)) =1+(x/(1+x))21+(x/(1+x))+(x/(1+x))2+(x/(1+x))3+(x/(1+x))4J^(x) =1+x21+x+x4с реализацией на Т-триггерах, представленной на рис.10.Рис.9. Исходная схема автоматаРис.10.
Автомат на Т-триггерах719.6. Вычисление выходных значений 0ЛАДля вычисления выходной последовательности двухполюсного 0ЛА надо выполнить следующие действия:1. Найти передаточную функцию J линейного автомата.2. ВычислитьизображениевходнойпоследовательностиA=D[a(t)], см. пп.9.1.1-5.3. Вычислить изображение выходной последовательности B=AJ.4. Изображение выходной последовательности представить ввиде B= P(d) + dτg(d)/(1–dT), см.
п.9.1.7 и записать выходнуюпоследовательность по вычисленному изображению b(t)=D–1[B].Задача: Вычислить реакцию 0ЛА на импульсную функцию i(t){=1 при t=0; =0 при t≠0} (какой будет длина предпериода, длинапериода?).9.7. Аннулирующие и аннигилирующие последовательностиРеакция 0ЛА на входную последовательность, состоящую изодних нулей, представляет собой выходную последовательностьодних нулей. Однако, это не так, если память ЛА не нулевая. Дляперевода памяти в нулевое состояние требуется на вход податьпоследовательность, которая называется аннулирующей.Если существует входная последовательность, которая спервого же такта заставляет ЛА с не нулевой памятью выдаватьна выходе только нули, то такая последовательность называетсяаннигилирующей.Аннулирующие и аннигилирующие последовательности полезны при использовании ЛА для исправления ошибок.9.7.1. Аннулирующую последовательность будем искать какконечной длины последовательность u(t), которая, будучи приложена в момент τ, ликвидирует реакцию 0ЛА на произвольнуювходную последовательность y(t) конечной длины, приложеннуюдо момента τ.Пусть ЛА имеет нормализовано обратимую передаточнуюфункцию J=h(d)/q(d).
К входу 0ЛА с момента t=0 и до моментаt=τ–1 приложена последовательность y(t). Представим изображеB = P(d) + dτ r(d)/q(d),ние реакции B =YJ в следующем виде:72где P(d) полином с deg(P)=τ–1 (может быть с нулевыми коэффициентами при старших степенях). Изображение выходной последовательности, совпадающей с b(t) с момента t=τ , будет Bτ=r(d)/q(d).Изображение полной реакции 0ЛА, начиная с момента t=τ,от последовательностей y(t) и u(t) равно:Bτ + UJ =r(d)+q(d)V(d)h(d)q(d)=r(d)+V(d)h(d)q(d)(9.3)где V(d) – полином – изображение искомой последовательностиu(t) (в силу конечности u(t) ).Полином V(d) будем искать, исходя из следующих соображений.
Для h(d) и q(d) выполняется соотношение1= h(d)ah(d)+ q(d)aq(d),которое можно получить, воспользовавшись алгоритмом Евклиданахождения н.о.д. двух полиномов. В этом алгоритме для полиномов p0(x) и p1(x), при deg(p0)≥deg(p1), выполняется цепочка деленийp0(x)= p1(x) e1(x)+ p2(x), deg(p2) < deg(p1),p1(x)= p2(x) e2(x)+ p3(x), deg(p3) < deg(p2),p2(x)= p3(x) e3(x)+ p4(x), deg(p4) < deg(p3),..................................................................................
,до получения остатка равного нулю. Предыдущий остаток является н.о.д.. Если он не содержит x, то исходные полиномы взаимно простые. Последовательной подстановкой можно установить,что, еслин.о.д.(p0(x),p1(x))=p2, то p2= p0(x) – p1(x)e1(x), иначен.о.д.(p0(x),p1(x))= pn= (–1)n [p0(x)–p1(x)(1+e1(x)…en-1(x))]Отсюда следует, поскольку h(d) и q(d) взаимно просты, то1= h(d)ah(d) + q(d)aq(d).Преобразуя1– h(d)ah(d)= aq(d)q(d)и умножив обе части на r(d), получим73r(d) – h(d) r(d)ah(d)= r(d)aq(d)q(d)Установив подобие с последней дробью выражения (3), положим V(d)= –r(d)Заметим, что изображение реакции на обе последовательностиBτ + UJ = r(d)aq(d) является изображением последовательностиконечной длины.Пример 9.7.1.-1: Пусть двухполюсный ЛА над полем GF(2)имеет передаточную функцию2h(d)1+d+dJ==q(d)1 + d + d2 + d3Найдем последовательность u(t) конечной длины, которая будучиприложенной в момент t=2, нейтрализует реакцию на единичныйимпульс.