У. Питерсон - Коды, исправляющие ошибки (1267328), страница 46
Текст из файла (страница 46)
! ! После этого уже известными методами может быть синтезирована схема с этой последовательностью в качестве импульсного отклика или синтезирован генератор с регистром сдвига и этой последовательностью в качестве последовательности на выходе. Знаменатель передаточной функции будет равен г!(В), где Ь(Х) = = (Х вЂ” Х,) (Х вЂ” Хз) ... (Х вЂ” Хх), и степень его будет минимальной. Остается лишь вопрос о том„как решать нелинейные уравнения (7.24). Как ни странно, эти уравнения совпадают с уравне- пнями, которые используются при исправлении ошибок для БЧХ- кодов. Методы решения этих уравнений описываются в равд. 9.4 — 9 7.
7.б. Анализ общей линейной переключательной схемы с конечным числом состояний Ниже дается общее описание произвольной линейной переключательной схемы с конечным числом состояний. Основной результат данного раздела состоит в том, что передаточная функция любой такой схемы является функцией того же типа, который обсуждается в предыдущем разделе; таким образом, если рассматривать схему как черный ящик, для которого известны только вход и выход, то любая линейная переключательная схема с конечным числом состояний неотличима от одной из схем типа описанных в равд.
7.2. Точнее, посредством линейного преобразования распределения состояний первоначальная схема преобразуется в эквивалентную ей схему, которая является схемой типа описанной в равд. 7.2 нли, возможно, комбинацией нескольких схем такого типа. Необходимому преобразованию распределения состояний соответствует преобразование подобия для матрицы, которая представляется в рациональной канонической форме, и, следовательно, метод выполнения этого преобразования хорошо известен. Рассмотрим произвольную линейную переключательную схему с г ячейками памяти, а входными линиями и «выходными линиями.
Тогда выходы г ячеек в момент «образуют вектор ч, из г компонент, а входы ячеек в момент «образуют следующий вектор выходов ч«+ь Вектор ч; называется состоянием схемы. Аналогично входы схемы образуют з-мерный вектор н;, и ее выходы — «-мерный вектор вь Вход ч,+, ячеек памяти является функцией выхода ч; этих ячеек и входа схемы пь Так как схема состоит только из сумматоров и устройств умножения на постоянную величину, то эта функция должна быть линейной и может быть поэтому запи.
сана в матричной форме (7.25) ч,+, — — ч,Т + и;$3, где Т вЂ” матрица размерности гХг, а Ю вЂ” матрица размерности з Х г. Аналогично выход схемы тг; есть линейная функция от входа и содержимого ячеек: «7 уб1 тч, = ч;К+ и;$, где К вЂ” матрица размерности г Х«, а 8 — матрица размерности аХ«. Пример. Для схемы, изображенной на фиг. ?.5, а, матрицы имеют вид 010000 00!000 000100 000010 000001 оооооо !.! = (1 о о о о о), 11г=(11100 Ц, 5=(ц, $3 =(10011 Ц, !(г=(00000 Ц. (7.27) Для схемы, изображенной на фиг.
7.7, имеем 010000 ОО(ООО Й~=(00000 Ц, (7.28) 5 =(0) 000001 100111 Для схемы, изображенной на фиг. 7.9, все матрицы остаются теми же, изменяется только матрица 1). Здесь !! =(1 1ооо ц. (7.29) Во всех случаях матрицы полностью задают соединения в схеме.
Пусть А — невырожденная матрица размерности гХг и (7.30) Тогда, если известно значение ть то можно вычислить то и наоборот. Вектор и,' можно рассматривать как представление векгора я; в другой системе координат. Можно построить переключательную схему, в которой последовательные состояния описываются векторами т', вместо ть если подставить выражение для ть даваемое соотношением (7.30), в уравнения (7.25) и (7.26): т,'+,А '= т,'.А 'Т+ и,(). если предполагается, что компоненты векторов я; совпадают с содержимым ячеек памяти, расположенных в том же порядке, как на фиг. 7.5,а. (Кт обозначает транспонированную матрицу К.) Для схемы, изображенной на фиг.
7.5,б, матрицы Т и 8 те же самые, но Отсюда, умножая справа на А, находим т,'.+,= и,'.А 'ТА+и,!!А=в;.Т'+ и,!!' и тт, = и,'А 'К + и,8 = т,'.й' + и,. $'. (7.31) (7.32) При заданном входе новая схема будет давать тот же самый выходной сигнал, что и старая, хотя внутренние соединения и векторы состояний схемы будут отличаться. При атом матрицы новой схемы выражаются через матрицы старой: Т'=А 'ТА, !!'=!)А, К'=А 'К, 3'=$. (7.33) Соотношение между матрицами Т и Т', задаваемое равенствами (7.33), очень важно для дальнейшего изложения.
Матрицы Т н Т; связанные равенством Т'= А — 'ТА, называются подобнылти матрицами !77, стр. 83; 237„стр. 297! '). Пример. Рассмотрим матрицы, соответствующие схеме, изображенной на фнг. 7.7, и задаваемые равенствами (7.28). Пусть гогда %1'= й)А = [00000 Ц, (К')г=(А 'ас)~=!1000001, 8' = 8 = !О!. Т'= А 'ТА= Соответствующая схема показана на фиг. 7.19.
Она может быть использована для деления многочленов, так же как схема„изоВхад + + + + эт.т.19.о, В ю ф .~2. ')Б~ Ч ур Р г ' Рй"" кожно найти в любом из подробных учебников по линейной алгебре и теории за рни имеющихся на русском языке. — Прим, ред. 000001 000011 000110 001100 011001 110011 000001 !00000 010000 001001 000101 000011 001111 011110 111100 111000 110000 100000 браженная на фиг. 7.7. Результат будет правильным, поскольку выходы обеих схем совпадают. Однако содержимое ячеек памяти после окончания деления не будет остатком от деления, поскольку, как показывают соотношения (7.30), символы, содержащиеся в ячейках памяти в этих двух системах, не совпадают. Рассмотрим теперь поведение схемы с нулевым входом, которое иногда называют ее поведением в автономном Режиме.
В этом случае и; = О, и из равенства (7.25) следует, что чгы = ч;Т, ч~+з — — чг ыТ = ч~Т и вообще ч,+г=ч,Т . / (7.34) Отсюда получаем т,ч;Т*+т,ч,Т' '+ ... +ги„ч; =О, или тЖ+~ + т -1ч ~+ 8-~ + ° ° . + тсч; = О. (7,35) Итак, каждая из компонент вектора ч; (т. е. символы, последовагельно появляющиеся в одной из ячеек) удовлетворяет однородному разностному уравнению, а именно уравнению (7.35) Выходная последовательность есть линейная комбинация символов, содержащихся в ячейках схемы, и поэтому она также является решением уравнения (7.35). Решения этого уравнения полностью описываются теоремой 7.1 нз равд.
7.4. Пример, Пусть задана матрица над полем из двух элементов; 00100001- 10000000 01000000 00100000 00010000 00001000 00000101 00000010 Известно, что любая квадратная матрица размерности г Х г обращает в нуль свой минимальный многочлен, являющийся многочленом степени, не превосходящей г, с коэффициентами из того же поля (7, стр.
83; 23, стр. 215; 193, стр. 77). Следовательно, существует многочлен т(Х) = т,Х'+ т, ~Х'-'+ ... +т,Х+ та такой, что т(Т) =т,Т'+ т,,Т' '+ ... +те=О. фиг. т.гй. Схема, вхвивелеитиаи схеме, ивобрвжеииой ви фиг. тдб, Тогда характеристический многочлен втой матрицы равен бе! (1Х вЂ” Т! = Хв+ Хв+ Хв+ Хв+ 1, Это примитивный и, следовательно, неприводимый многочлен. Характеристический многочлен должен делиться на минимальный миогочлен, и, следовательно, полученный многочлен должен быть также и минимальным многочленом (7, стр. 84; 193, стр. 791.
Матрица Т соответствует схеме, показанной на фиг. 7.20. Эта схема обладает той же самой совокупностью возможных выходных последовательностей„что н схема, изображенная на фиг. 7.16, поскольку она описывается одним и тем же разностным уравнением, однако для нее при том же самом числе остальных компонент требуется на один сумматор меньше. Для любого нормированного многочлена л(Х) = Х'+ '+д„-1Х '+ ... +де существует сопровождающая матрица (7, стр. 85; 193 стр.
3081 1 0 ... 0 0 1 ... 0 (7.36) О О 0 ... 1 — йо — й1 йв - . йг-ч Иногда сопровождающая матрица определяется как матрица, транспонированная к матрице Т, (193, стр. 811: (7.37) ~ 00...1 — кг-ю Можно показать, что многочлен д(Х) является минимальным многочленом одновременно для обеих матриц Т, и Тв, Матрица Т„ задаваемая равенством (7.36), соответствует схеме, изображенной на фиг. 7.6, с одним исключенным входом, тогда как матрица Та соответствует схеме, изображенной на фиг, 7.!4. Рассмотренные ранее разностные уравнения (уравнения (7.21) н (7.2) соответственно] совпадают с уравнением (7.35).
Если Т вЂ” матрица размерности г Х г и степень ее минимального многочлена т(Х) равна г, то говорят, что Т вЂ” матрица с невырожда>ои(имся уравнением. Каждая матрица с невырождающимся уравнением подобна сопровождающей матрице для ее минимальной функции (193, стр. 123). Это значит, что если Т вЂ” матрица с невырождающимся уравнением, то существует такая матрица А, что А-'ТА= Т„где ҄— сопровождающая матрица для т(Х), минимального многочлена для матрицы Т. Поэтому схема, соответствующая матрице Т„и схема, соответствующая матрице Т, удовлетворяют одному и тому же разностному уравнению.
Эти схемы эквивалентны: они отличатся только способом представления их состояний. Пример, В примере, следующем после равенства (7.33), матрица А переводила матрицу Т в матрицу Т', которая является матрицей, соответствующей сопровождающей матрице в форме (7.37). Заметим, что если в качестве начальных условий в схеме, изображенной на фнг. 7.19, выбран вектор, соответствующий первой строке матрицы А, то последовательные значения символов, появляющихся в ячейках схемы, задаются остальными строками матрицы А. Этот способ нахождения матрицы А для приведения заданной матрицы с невырождающимся уравнением к канонической форме описан в книге 1193, стр.
1221. Любая матрица с невырождающимся уравнением Т подобна некоторой матрице вида М,О ...0 0 М ... О (7.38) 0 0 ... М где М„,— сопровождающая матрица для минимальной функции матрицы Т, а каждая матрица М; при 1( гн — сопровождающая матрица для некоторого многочлена р;(Х). Кроме того, каждый многочлен ргы(Х) делится на р;(Х). Матрица вида (7.38) называется матрицей в рациональной канонической форме 17, стр. 86; !93, гл. 6). В соответствующей схеме нет соединений между ячейками, соответствующими столбцам различных матриц М1 и М,. Поэтому эта схема состоит из изолированных частей, соответствующих матрицам Мь Мь ..., М .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
