Antik (1082243), страница 11
Текст из файла (страница 11)
В этом случае изображение выходной реакцииB=1 + d + d21 + d + d2 + d3=1 + d2 ×d1 + d + d2 + d3r(d)=dh(d) = q(d)e1(d) + p2(d) == 1 + d + d2 + d3 = (1 + d + d2)d + 1ah(d)=d, aq=1Изображение искомой последовательностиU= V(d)= –r(d)ah(d)= d2Соответственно последовательность u(t), начиная с момента t=2,равна u(t): 0010…Изображение выходной последовательности r(d)aq(d)=d.Соответственно выход, начиная с момента t=2, – 010…9.7.2. Аннигилирующая последовательность, будучи приложенной в момент t=τ, должна мгновенно (в том же такте) установить только нулевые выходные значения.
Поэтому, если такаяпоследовательность существует, тоBτ + U^J =r(d)q(d)+ U^×h(d)q(d)=074U^ = – Bτ/J = – r(d)/h(d)(9.4)Аннигилирующая последовательность u^(t) существует тогда, когда отношение r(d)/h(d) обратимо. Чтобы это отношениебыло обратимо при любых входных воздействиях, должно выполнятся h(0)≠0, т.е. ЛА не должен быть автоматом Мура илииначе выход должен зависеть от текущего значения на входе. Согласно (4) аннигилирующая последовательность u^(t) может неиметь конечной длины, а значит и не сбрасывать память автоматав нулевое состояние.Пример 9.7.2.-1: В условиях предыдущего примера изображение аннигилирующей последовательности u^(t), начинающейся с момента t=2dU^= -r(d) =h(d)1 + d + d2Приведя к виду в соответствии с п.
9.1.7, получим2d+dU^=1 + d3Аннигилирующая последовательность u^(t): 011,011,…10. Умножение и деление линейными автоматамиПродемонстрируем возможность использования линейныхавтоматов для выполнения операций умножения и деления двоичных полиномов. Такие операции выполняются при кодировании и декодировании помехозащищенных кодов и в различныхцифровых фильтрах.10.1. УмножениеРассмотрим линейный автомат с передаточной функциейJ = 1 + h1d + h2d2 + ... + dn,пусть задана входная последовательностьat: a0,a1,...ak,0,...,тогда изображение выходной последовательностиB =J∗A = (1 + h1d + h2d2+ ... + dn)××(a0 + a1d + a2d2+ ...
+ akdk)== b0 + b1d + b2d2+ ... + b(n+k)dn+k75Происходит умножение полиномов.В том случае, если коэффициенты произвольного полиномаследуют, начиная с коэффициента при наивысшей степени, тополученные результаты интерпретируются следующим образом.Один из множителей C(x) фиксирован и задан структурой автомата.
ЕслиJ = 1 + h1d + h2d2+ ... + dn, тоС(x) = xn + h1x(n-1) + ... + h(n-1)x + 1Коэффициенты произвольного полинома степени не выше kзадаются (k+1) цифрами входной последовательности, начиная скоэффициента при старшей степени, после которых должны следовать n нулей. При нулевых начальных значениях триггеров врезультате на выходе будет получена последовательность,(k+n+1) цифр которой интерпретируются как коэффициенты искомого полинома. Первая цифра выходной последовательностиявляется коэффициентом при наивысшей степени x(k+n).Пример 10.1.-1: линейные автоматы с J(d)=1+d+d3 рис.11,рис.12 можно использовать для умножения на фиксированныйполином C(x)=x3+x2+1.Рис.11. ЛА односумматорный для умноженияРис.12.
ЛА многосумматорный для умноженияПусть C(x) умножается на полиномы степени не выше 4.Пример 10.1.-2: A(x) = x2 + x,тогда входная последовательность a : 0 0 1 1 0’0 0 0,и ее изображение A(d) = d2 + d3.Изображение выходной последовательностиB(d) = J(d)∗A(d) = (1+d+d3)∗(d2+d3) = d2+d4+d5+d6,выходная последовательностьb : 00101110,532соответственно B(x) = x + x + x + x.7610.2.
ДелениеПри делении полинома А(x) степени k на полином C(x) степени n ≤ k однозначно определяются частное B(x) - полином степени (k-n) и остаток R(x) - полином степени m (0 ≤ m < n).Рассмотрим линейный автомат с передаточной функциейJ = dn/(1 + q1d + q2d2+ ... + dn).Пусть задана входная последовательность a(t): a0,a1,...ak,0,...Изображение выходной последовательности в виде полинома получаем как разложение в степенной ряд непосредственным делением числителя на знаменатель выражения A(d)∗J(d). Начальныеk+1 значения выходной последовательности будут иметь следующий вид: b : 0,0,...,0,bn,...,b(k-n), при этом bn=a0.Эти результаты должны интерпретироваться следующимобразом. Произвольный полином степени не выше kA(x) = a0xk + ...
+ ak,делится на фиксированный полиномC(x) = xn +q1x(n-1) +...+q(n-1)x +1.При нулевом начальном состоянии за время t=k+1 будет получена выходная последовательность, в начале которой будет nнулей затем значения коэффициентов частного, начиная с коэффициента при x(k-n), и остаток, коэффициенты полинома которогосодержатся в памяти автомата. Коэффициент при x(n-1) - старшейстепени полинома остатка содержит триггер с номером 1 и т.д.Пример 10.2.-1: линейный автомат с J(d) = d3/(1+d+d3)рис.13 или рис.14 можно использовать для деления на фиксированный полином C(x) = x3+x2+1.Рис.13. ЛА односумматорный для деленияРис.14.
ЛА многосумматорный для деления77Предположим, делимое произвольные полиномы степени невыше 6. Например, A(x)=x6+x5+x4+x3+1, тогда входная последовательность a : 1111001, изображение входной последовательностиA(d)=1+d+d2+d3+d6. Вычислим изображение выходной последовательностиd3 + d4 + d5 +d3 + d4 + 0 +0 + d5 +d5 +d5 +d6d600d6d6d6+ 0 + 0 + d9+++++0000d7d7+++++1 + d + 0 + d3d3 + 0 + d5 + d60d8d8 + d90 + d9d8 + 0Ее вид b : 0001011. Это означает, чтоB(x) = x3 + x + 1R(x) = x2 + xПроверим полученный результат B(x) = A(x)/C(x)x6 + x5 + x4 +x6 + x5 + 0 +0 + x4 +x4 +x4 +x3x300x3x3x3+0 + 0 + 1+++++0000x2x2+++++x3 + x2 + 0 + 1x3 + 0 + x + 10xx + 10 + 1x + 0Аналогично можно получить схему, которая умножает наодин полином, а делит на другой.7811.Обобщения11.1. Многоканальный аналог двухполюсного ЛАДвухполюсный автомат имеет один вход (кроме входа синхросигнала) и один выход.
Многоканальный аналог двухполюсного автомата А, обозначаемый А(k), представляет собой автоматс k входами и k выходами (рис.15). Входные и выходные векторасоответствуют входным и выходным последовательностям длиныk автомата А.Рис.15. Двухполюсный ЛА и его многоканальный аналогТаким образом, имея k каналов вместо одного, автомат А(k)работает в k раз быстрее, чем автомат А.
Структура характеристических матриц k–канального аналога линейного автомата Аследует из уравнений (3.1).G(k)= GkB(k)= Gk-1CGk-2C...G2CGC CDDGD(k)= DG2DDGE(k)= DGC:DGk-2C00DG:DGk-3C00D:DGk-4C.........:...000:DCDGk-1000:EРазмерность состояний автомата А(k) осталась такой же, каки у автомата А. Входные и выходные цепи разумеется усложняются.7911.2. Линейные автоматы над конечным полемДо сих пор рассматривались ЛА с двоичными сигналами{0,1}. Если считать, что значения сигналов принадлежат конечному множеству {0,1,...,p-1}, где p - простое число, то операции(сложение и умножение на константу) над сигналами в линейномавтомате должны выполняться по правилам конечного поляGF(p).
Реализация таких автоматов, хотя и возможна в двоичномэлементном базисе, но удобнее программный вариант.11.3. Линейные автоматы над полем ГалуаДостаточно универсальным обобщением, но в тоже времяудобным для реализации в двоичном элементном базисе, являются ЛА над полем Галуа GF(2k) - полем полиномов степени не выше k–1 над полем GF(2).
Теория ЛА справедлива, если 2 заменитьлюбым простым целым числом, но аппаратная реализация эффективна для 2. В этом случае двоичные ЛА, т.е. автоматы надполем GF(2) преобразуются следующим образом - каждая линиясвязи заменяется шиной из k линий, пронумерованных числами0,1,...,k-1. По шинам передаются коэффициенты полинома надполем GF(2)A(x) = a0+a1x+a2x2+...+a(k-1)xk-1Каждый сумматор заменяется k сумматорами (рис.16).Рис.16. Сумматор и память ЛА над полем Галуа80Рис.17. Умножитель ЛА над полем ГалуаВместо умножения на постоянный коэффициент происходит умножение на постоянный полиномC(x) = c0+c1x+c2x2+...+c(k-1)xk-1Это умножение реализуется как произведение Qa входного вектора a на матрицу Q.TP 2TP k-1Q=║qij║k∗k=c0I+c1 M TPP ( x ) +c2( M P ( x ) ) +...+ck-1( M P ( x ) )где M TPP ( x ) матрица (5") транспонированная к сопровождающейнеприводимый полином над полем GF(p)P(x) = p0 + p1x + p2x2 + … + pn-1xn-1 + xn ,порождающий поле GF(2k) (операции над полиномами выполняются в поле по модулю P(x)).
Выбор конкретного полинома P(x)определяется тем приложением, ради которого и строится этотавтомат.Таким образом, умножитель реализуется в виде схемы,представленной на рис.17.81ГЛАВА III. УПРАВЛЯЮЩИЕ АВТОМАТЫПри проектировании вычислительного устройства, выполняющего сложную обработку цифровой информации, одним извариантов декомпозиции является представление синхронноговычислителя в виде композиции двух автоматов операционного иуправляющего - рис.1.Рис.1. Структура вычислителяОперационный автомат (ОА) это, в свою очередь, некотораякомпозиция из автоматов, но если все регистры этих автоматовсинхронизируются одинаково, то ОА можно представлять себекак один автомат Мили.
Для исключения гонок по замкнутымцепям управляющий автомат (УА) должен быть автоматом Мура.Совместная работа этих двух автоматов может быть описанаследующим образом. На границе такта (фронт, синхронизирующий регистры автоматов) изменяется содержимое регистров какОА так и УА и соответственно выходные значения автоматов.Это приводит к тому, что УА формирует новые значения сигналов для ОА (сигналы эти на рис.1 обозначены как микрокоманда).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
