У. Питерсон - Коды, исправляющие ошибки (1267328), страница 47
Текст из файла (страница 47)
Каждый выходной символ схемы является линейной комбинацией символов, содержащихся в ячейках нескольких нли всех ее изолированных частей. Далее, минимальный много- Тогда из уравнения (7.26) получаем т г ш,ттрн+) = 2". ш,у(+,Й+ ш,пй+,8 = г-о ! о У О =п,$3зК+и,+,0,К+ ... +и,+,В„,1(+ 2 т)п,+)8. (742) )-Р Это соотношение можно переписать в виде т (Р) тт; = Ь (Р) и;, (7.43) где т'(Р) — многочлен, двойственный минимальной функции дляТ,и г-ч ЦР) = Е В,~В+Вт (Р). (7.44) г=а В этом выражении т (Р) является обычным многочленом, но поскольку 1);К и Ь вЂ” матрицы размерности з Х1, то )т(Р) — это многочлен, коэффициентами которого являются матрицы размерности з Х й Или же Ь(Р) можно рассматривать как матрицу размерности з Х 1, элементами которой являются обычные многочлены Ьгх(Р).
Вход и; в момент 1 представляет собой вектор с з компонентами ин, 1' = 1,2, ..., з, а выход тч~ в момент 1 является вектором с 1 компонентами гад„й = 1, 2, ..., й Тогда (Р) тки ~~ ~Ь)ь (Р) и ь ь-1 что может быть записано в виде С~ л)ь(р) гам=~ — и . ~(р) И ь-! (7.46) Формулы (7.43) — '(7.46) описывают соотношение вход — выход и применимы к совершенно произвольной линейной последовательной переключательной схеме с несколькими входами и вы. ходами. В равд. 7.5 показано, что по заданной передаточной функции такого вида можно синтезировать схему, состоящую из 1 отдельных частей, регистр сдвига каждой из которых содержит г ячеек. Если 1= 1, то для реализации этой передаточной функции будет использоваться наименьшее возможное число ячеек регистров сдвига, но при 1 » 1 это не обязательно.
Число 1» ячеек, необходимое для синтезирования этим методом, может быть либо больше, либо меныпе числа ячеек первоначальной схемы, описываемой соотношениями (7.45) и (7.46), из которой была выведена передаточная функция в (7.46). В случае схемы с одним входом и одним выходом 8 — матрица размерности 1 Р', 1, т. е. скаляр, так же как и матрица 11;К для любого 1. При этом соотношения (7.45) и (7.46) имеют такой же вид, что и соотношения (7.18) н (7.19) соответственно; таким образом, в общем случае соотношение вход в выход характеризуется передаточной функцией. Снова ключевая роль принадлежит матрице Т, поскольку она описывает соединения между устройствами памяти.
Опять «изменение системы координат», задаваемое равенствами (7.30), можно использовать для нахождения матрицы Т', подобной матрице Т, но записанной в специальной канонической форме. Если Т вЂ” матрица с невырождающимся уравнением, то Т' — сопровождающая матрица для минимального многочлена матрицы Т. Основные обратные связи в схеме, соответствующей матрице Т', подобны обратным связям в схеме„изображенной на фиг. 7.6„если используется сопровождающая матрица, задаваемая равенством (7.36), или подобны обратным связям в схеме, изображенной на фнг.
7.14, если используется сопровождающая матрица, задаваемая равенством (7.37). Любая входная линия может быть соединена с любым устройством памяти, и любая ячейка — с любой выходной линией. Если Т вЂ” матрица с невырождающимся уравнением, то число ячеек регистра сдвига является наименьшим возможным для реализации заданной передаточной функции. В случае матрицы с вырождающимся уравнением матрица Т' имеет вид матрицы (7.38), и, как для автономного режима, схема образуется совркупностью схем типа изображенной на фиг. 7.6 или иа фиг. 7.!4. Снова возможны соединения между любой входной линией и любой ячейкой и между любой ячейкой н любой выходной линией, но зато не может быть соединений между отдельными схемами, соответствующими отдельным матрицам, находящимся на диагонали в матрице (?.38).
Необходимо отметить, что в случае одного входа н одного выхода всегда можно реализовать схему с заданной передаточной функцией при помощи такого числа ячеек, которое равно наибольшей из степеней числителя и знаменателя передаточной функции. Для такой реализации Т вЂ” матрица с невырожцающимся уравнением, а схема, соответствующая матрице с вырождающимся уравнением, содержит больше элементов, чем это необходимо для реализации ее передаточной функции. В случае нескольких входов и выходов это уже не обязательно так. Замечания Изучение линейных переключательных схем с точки зрения теории линейных фильтров было начато Хаффменом (147, 148). Равд. 7.5 полностью основывается на его исследованиях„схемы, описанные в равд.
7.2, появились в статье Хаффмена (147). Одновременна Цирлер (340, 3421, Голомб (1201, Бленкеншип, Альберт, а возможно, и другие заинтересовались генераторами с регистром сдвига как средством получения псевдослучайных последовательностей. Позже связь генераторов с регистром сдвига с кодами, исправляющими ошибки (!48), послужила стимулом для дальнейшего изучения этих регистров (72, 85, 98, 140, 337). Теорема 7.1 появилась в работе Питерсона (232); она очень похожа на результаты Холла (137). Метод синтеза генератора регистра сдвига минимальной сложности для частично заданной последовательности на входе принадлежит Месси (211).
Матричный метод анализа, используемый в разд. 7.6, ничем не отличается от методов, примененных в работах (22, 72) при анализе автономных линейных переключательных схем. Это очень естественный метод, и фактически в некоторых из основных работ по циклическим кодам использовался именно этот метод, а не термины алгебры многочленов, как в этой книге.
Альберт (7) при введении сопровождающей матрицы многочлена проводит интересное сравнение этих двух подходов. Задачи 7.1. Постройте три регистра сдвига, действующих подобно регистру, изображенному на фиг. 7.14, с периодамн, равными 7, 2! н 63. (Ответ: период, равный 21, можно получать при помощи мпогочленов Хб+ Х'+ Х'+ Х+ 1 или (Хэ+ Х+ 1) (Х'+ Х+ 1) или двойственных к ним многочленов.) 7.2. Покажите, что если й(Х) — неприводимый многочлен, то все последовательности, порождаемые соответствующим генератором сдвига, имеют один и тот же период.
7.3. Пусть Н,=(1, ап а',, аи,-'~ и Н =(1, а, а~э, ..., а,"-'~, где а, и аЪ вЂ” элементы из расширения поля и а",= — а"=1. Если эти элементы поля выражаются как векторы, состоящие из т, и т, компонент соответственно над 6Г(д) то Н| — матрица размерности т, Ха, а Нэ — матрица размерности тэХ а.
Покажите, что если элементы а, и аэ обладают одной и той же минимальной функцией, то пространства строк матриц Н1 и Н, также совпадают, но если их минимальные функции различны, то в пространстве строк матрицы Н, не найдется ни одного ненулевого вектора, принадлежащего пространству строк матрицы Нь и наоборот. (Указание: воспользоваться теоремой 7.1.) 7.4. [250). Пусть а; — любая последовательность максимальной длины с периодом а — 1 над полем 6Г(д). Умножение векторов определяется следующим образом.
а) О.т=ч О=О. б) Обозначьте через а, вектор (аь а;+ь ..., а!+„, ~) и поло. жите а;ах = а;+л, а,: чэ 0 Ф' ам Покажите, что при таком определении умножения векторы образуют поле. (При таком определении поля последовательные степени а появляются в результате последовательных сдвигов в регистре типа изображенного на фиг. 7.14. Такой регистр сдвига может быть также првспособлен для вычисления значений г(а) способом, аналогичным описанному в равд. 7.3.) 7.6.
Постройте схемы для возведения в квадрат элементов поля бр(2') и извлечения из них квадратного корня, пользуясь представлением элементов поля в табл. 6.1. Заметим, что в 6Р(д ) возведение в степень д и, следовательно. извлечение корня степени 7 являются в соответствии с теоремой 6.14 линейными операциями. Используйте метод, подобный методу, изложенному на стр. 205, для автоматического умножения на аз, которое также является линейной операцией. 7.6.
Г1ри заданных схеме умножения и схеме возведения в квадрат разработайте быструю и простую процедуру делении. 7.7. Синтезируйте двоичную последовательную переключательчую схему, реализующую передаточную функцию л(Г!) = (1+ Г! + + !74И1+ В+ Вз). 7.8. Синтезируйте двоичную последовательную переключательную схему, импульсный отклик которой равен: а) 010111001011100101110 .... б) 000!1100101110010!1100!О!!10 ....
7.9. Синтезируйте двоичную последовательную переключательную схему с двумя входами и; и т; и одним выходом тчь для которой !+и !+в' 1 1+В+!в 3 + 1+!т+Вэ чо 7.10. а. Приведите пример передаточной функции в форме, задаваемой равенством (7,46), для двух входов н двух выходов с т~(Г!) = = 1+ О+Вз, которая не может быть реализована с менее чем четырьмя элементами задержки. б. Приведите пример передаточной функции для схемы с двумя входами и двумя выходами с гп*(Й)=1+В+77', для которой требуется только два элемента задержки.
8 Циклические коды Коды, обсуждаемые в этой главе, могут быть относительно легко реализованы и обладают специфической и довольно хорошо понятой математической структурой. Пожалуй, благодаря этому значительная часть важных линейных блоковых кодов, описанных в гл. 5, эквивалентна циклическим кодам. В этой главе содержатся результаты трех типов. Прежде всего приводятся основные математические свойства циклических кодов. Затем эти свойства используются для создания схем простого кодировании, проведения проверок на четиость и в аекоторых случаях декодирующих схем. Наконец, описывается несколько классов циклических кодов и кодов, связанных с циклическими кодами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
