У. Питерсон - Коды, исправляющие ошибки (1267328), страница 45

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 45)

7.4, сводится к схеме деления, изображенной на фиг. 7.8, если й (Х) = — н(Х) + д„Х', (7.15) а выход умножается на у„-' и используется одновременно как частное и вход аз(Х). Тогда уравнение (7.14) можно записать в виде Ь (Р) = 8;-' (Ь*(й) а, (Р) + ( — а'(Р) + аД и, (Р)) (7.16) а~ (Р) = Ь (Р). (7.17) Подставляя последнее равенство в выражение (7.!6) и приводя подобные члены, находим искомое разностпое уравнение й" (Р) а, (Р) = 8" (Р) Ь (й). (7.18) Деля формально обе части его на д*(й), для того чтобы разрешить уравнение относительно Ь(й), получаем Ь(й) = а*!ц и'(Р) Частное Ь*(й)~д'*(Р) называется передаточной гЬункцией рассматриваемой схемы.

Необходимо отметить, что для схемы, показанной на фиг. 7.8, степени обоих многочленов й(Х) и гт(Х) должны быть равны га. Равенства (7,18) и (7.19) выполняются н для других случаев, если только д*(Х) выбирается как Х"д(Х вЂ” '), а 64(Х) — как Х"Ь(Х-'). При4иер. Передаточная функция схемы, изображенной на фиг.

7.7, равна п4 В) пв и'(1+и-'+п-4+п-'+п ) в'+в'+и'+в+1' Для схемы, изображенной на фиг. 7.9, передаточная функция равна и'+ в'+ и в'0 + и-'+ и-') П'(1+ П-'+ П-'+ П + В-') В'+ Пз+ Пт+ П+ 1 а для схемы, изображенной на фиг. 7.10, пю(1 1 и — 5+и-9+ и — м) и" +и'+и+~ и'" (п — '+ п — '+ п-'+ п — '+ в ") и'+ в4 + п'+ п+ 1 Поскольку схема, изображенная на фиг. 7.8, может быть по- строева для произвольных многочленов 6(Х) и д(Х), то такую схему можно построить для любой заданной передаточной функции. Тем самым решается проблема синтеза для произвольной передаточной функции. Выход схемы может быть отличен от нуля, когда входная последовательность состоит только из нулей.

Это может быть в том случае, если вначале во всех ячейках были ненулевые элементы. Такая последовательность аналогична переходному отклику электрической цепи. Переходный отклик линейной последовательной схемы с передаточной функцией 6" (Р)/д*(Р) характеризуется следуюшим образом. Предположим, что а (и) (а,п'+а,п4-4+ ... +Ь,) а (и) (и.п4+а,в'-'+ ... +а,) ' Тогда вход а(Р) и выход Ь(Р) этой схемы связаны соотношением д' (Р) Ь (Р) = Ь*(Р) а (Р), (7.20) и поскольку на вход подается ненулевая последовательность, то а"(Р)Ь(Р)= О. Коэффициенты при каждой степени Р в этом произведении должны быть равны О. Таким обрааом, коэффициент при Р'+' имеет вид (7.21) Х,Ь4„= О. ( О Решения этого уравнения характеризуются теоремой 7.1 из равд. 7.4.

Частное решение, которым является последовательность Ь(П), определяется начальными условиями в запоминающем устройстве. Пример. Легко проверить, что схема, изображенная на фиг. 7.7, при начальном условии 1 0 0 ! 1 ! и нулевом входе дает на выходе последовательность 1 0 0 1 1 1 0 О 1 0 0 0 0 0 1 .... При начальном условии 0 0 0 0 0 1 и снова при нулевом входе а(1Э) = 0 последовательность на выходе равна 1 1 0 0 ! 1 1 0 0 1 0 0 0 0 0 1 ....(Заметим„ что обе эти выходные последовательности так же, как и их сумма, являются решениями уравнения (7.21).) Для схемы с заданными начальными условиями может существовать такая входная последовательность, что соответствующая ей последовательность на выходе будет содержать только нули. Зта входная последовательность называется нулевой последовательностью зпданной схемы.

Предположим снова, что передаточная функция схемы равна й*(й)/д*(П). Тогда ее вход и выход связаны разностным уравнением (7.20). Для нулевой последовательности Ь(П) = 0 и, следовательно, Ь' (Р) а (х!) = 0 (7.22) или Х Ь,а,+, —— О. г-о (7.23) Пример. На практике легче найти нулевую последовательность, соответствующую заданному набору начальных условий, чем найти начальные условия, соответствующие заданной нулевой последовательности. Рассмотрим схему, показанную на фиг.

7,5,а, с начальными условиями (! 00000). Тогда если выход равен О, то первый символ входа должен быть равен 1, и после сдвига содержимое регистра равно 110000. Теперь, для того чтобы выход был ранен О, следующий символ на входе должен быть нулем, и после сдвига содержимое регистра должно быть равно 011000„ Аналогичным образом можно найти, что нулевая последователь- Далее, если й'(0)а(П) = О, то и д'(П)Ь(П) = О, а выходная последовательность является переходным откликом схемы. Можно показать, что каждому решению уравнения (7.23) соответствует совокупность начальных условий, для каждого из которых выходная последовательность будет нулевой.

Таким образом, среди решений уравнения (7.23) содержится нулевое решение. Все решения (7.23) описываются теоремой 7.1 нз равд. 7.4. Фнг. 7ая. Схема, импульсный отклик которой равен аеа, ... а„г ... а„, ность должна иметь вид 100111001000001 ..., где данная комбинация символов повторяется с периодом, равным 15. Это та же последовательность, которая была найдена в предыдущем примере, что вполне согласуется с тем фактом, что в обоих случаях последовательности должны удовлетворять одному и тому же разпостпому уравнению. По аналогии с обычными линейными схемами импульсный отклик линейной схемы с конечным числом состояний может быть определен как выходная последовательность, которая получается, если на вход подается последовательность 10000 .... (Предполагается, что все ячейки памяти первоначально содержат нули.) Если импульсный отклик линейной последовательной схемы известен, то можно определить передаточную функцию, и, следовательно, схема может быть сиптезирована следующим образом.

По предположению схема обладает конечным числом элементов и, следовательно, конечным числом состояний, поэтому рано или поздно состояния начнут повторяться, а значит, начиная с этого момента будет периодически повторяться и последовательность. Таким образом, импульсный отклик должен иметь вид а,а, ... а„ ,а„ ты ... а , ...

а„ , ... а„ , ...„ где последние г символов повторяются с периодом г. Схема, изображенная на фнг. 7.16, имеет такой импульсный отклик. Однако эта схема, быть может, не самой простой формы. Передаточная функция для этой схемы равна Ь (В) = а, + а,й + ... + а„„0„, + "" '+' Если числитель и знаменатель имеют общий множитель, то на него можно сократить, и функции й(71), которая при этом получится, будет соответствовать тот же самый импульсный отклик, фкг.

7.17. Схема„вмоульгный отклик которой равен ! ! 10010... причем при этом потребуется минимальное число разрядов в регистре сдвига. Пример. Для двоичной схемы с периодическим импульсным откликом, период которого равен 7, а первые семь символов равны 1 1 1 О О 1 О, передаточная функция 1 + !1+ !02 + Ре 1 + Р— ~-;а — О Эта схема изображена на фиг. 7.17. Аналогичная процедура может быть использована для синтеза регистра сдвига с обратной связью при заданной последовательности на выходе. В самом деле, это можно сделать, синтезируя схему, импульсным откликом которой является требуемая последовательность, затем исключив из схемы ее вход и выбрав начальные условия, согласующиеся с теми, которые возникают, когда на вход подается единственная единица.

Пример. Как показано на фиг. 7.18, генератор с регистром сдвига, выход которого периодичен с периодом 7, а первые семь элементов равны 111 00! О, может быть построен на основе схемы, изображенной на фиг. 7.17, если исключить вход схемы и поместить единицы в те ячейки регистра сдвига, которые давали выходные символы схемы фнг. 7 !7. Предположим теперь, что последовательность задана частично — а именно заданы ее первые з символов — и требуется построить схему с этими з символами в качестве первых з символов импульсного отклика схемы, нли, другими словами, построить ге- !1ЫМод фкг 7.18.

Генератор регистра сдвига, выход которого равен ! 1 ! 00! О, нератор с регистром сдвига с этими з символами в качестве первых з символов последовательности на выходе. Существует много схем, которые будут вырабатывать заданную совокупность з символов, и если не накладывается никаких дополнительных ограничений, то для подбора соответствующей схемы могут быть использованы методы, описанные в предыдущем разделе.

Однако если необходимо найти рекуррентное уравнение, подобное уравнениям (7.2), причем порядок й должен быть минимальным, то эта задача оказывается уже более трудной (21 Ц. Пусть задана последовательность Я„Яо Я„..., Я, и й (х) = Х й,х!. г-о Обозначим через Хь Хь, Хх корни многочлена г!(Х) в расширении поля, в котором ЦХ) может быть разложен на множители. Тогда в соответствии с соотношением (7.8), если заданная последовательность 5ц, Яь ..., Я, удовлетворяет рекуррентным соотношениям (7.2), существуют величины Уь Уь ..., Ум такие, что Х У!Х!=Яо. Х У!Х!=5!~ .- Х У!Х~ =Яа (724) В этих соотношениях Ям Яь ..., Я, заданы, а Х! и У! могут рассматриваться как неизвестные. Разрешая эти соотношения при минимальном А относительно Х! и Уг, можно затем восстановить полностшо последовательность Ям 5„..., Я„Я,+ь ..., используя формулу Я,=ХУ!Х/.

Характеристики

Список файлов книги