Главная > Помехоустойчивое кодирование > Коды, исправляющие ошибки
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

7.6. Анализ общей линейной переключательной схемы с конечным числом состояний

Ниже дается общее описание произвольной линейной переключательной схемы с конечным числом состояний. Основной результат данного раздела состоит в том, что передаточная функция любой такой схемы является функцией того же типа, который разбирается в предыдущем разделе; таким образом, если рассматривать схему как черный ящик, для которого известны только вход и выход, то

любая линейная переключательная схема с конечным числом состояний неотличима от одной из схем типа, описанного в разд. 7.2.

Рассмотрим произвольную линейную переключательную схему с разрядами, входными линиями и выходными линиями. Тогда выходы разрядов в момент I образуют вектор из компонент, а входы разрядов в момент I образуют следующий вектор выходов Вектор называется состоянием схемы.

Аналогично вход схемы образует -мерный вектор а ее выход — -мерный вектор Вход разрядов является функцией выхода разрядов и входа схемы Так как схема состоит только из сумматоров и устройств умножения на постоянную величину, то эта функция должна быть линейной и может быть поэтому записана в матричной форме

где матрица размерности матрица размерности Аналогично выход схемы есть линейная функция от входа и содержимого разрядов

где матрица размерности матрица размерности

Пример. Для схемы, изображенной на рис. 7.5, а, матрицы имеют вид

если предполагается, что компоненты векторов совпадают с содержимым соответствующих регистров. Для схемы, изображенной на рис. 7.5, б, матрицы те же самые, но

Для схемы, изображенной на рис, 7.7, имеем:

Для схемы, изображенной на рис. 7.9, все матрицы остаются теми же отличается только матрица U:

Во всех случаях матрицы полностью задают соединения в схеме.

Пусть А — невырожденная матрица размерности и пусть

Тогда если известно значение то можно вычислить и наоборот, так что в этом смысле в каждом из них содержится одна и та же информация. Вектор можно рассматривать как представление вектора в другой системе координат. Можно построить переключательную схему, в которей последовательные состояния описываются векторами вместо если подставить выражение для даваемое соотношением (7.30), в уравнения (7.24) и (7.25):

Отсюда, умножая справа на А, находим

и

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

Соотношение между матрицами задаваемое равенствами (7.33), очень важно для дальнейшей теории. Матрицы связанные равенством называются подобными матрицами (см. [1], стр. 83; [3], стр. 297; [431, стр. 112).

Пример. Рассмотрим матрицы, соответствующие схеме, изображенной на рис. 7.7, задаваемые равенствами (7.28). Пусть

тогда

Соответствующая схема показана на рис. 7.16. Она может быть нспользована для деления многочленов, так же как схема, изображенная на рис. 7.7. Частное окажется правильным, поскольку выходы обеих схем совпадают. Однако содержимое разрядов после окончания деления не будет остатком от деления, поскольку содержимое разрядов в этих схемах не совпадает, как показывают соотношения (7.30).

Рис. 7.16. Схема, эквивалентная схеме, изображенной на рис. 7.7.

Рассмотрим теперь поведение схемы с нулевым входом, которое иногда называют автономным режимом. В этом случае и из равенства (7.24) следует, что и вообще

Известно, что любая квадратная матрица размерности удовлетворяет минимальному многочлену степени, не превосходящей с коэффициентами из того же поля (см. [1], стр, 83; [3], стр. 215; 143], стр. 77). Следовательно, существует многочлен такой, что

Отсюда получаем

или

Итак, каждая из компонент вектора (т. е. последовательность символов, попадающих в последовательные разряды схемы) удовлетворяет однородному разностному уравнению, а именно уравнению (7.35). Выходная последовательность есть линейная комбинация символов, содержащихся в разрядах схемы, и поэтому она также является решением уравнения (7.35). Решения этого уравнения полностью описываются теоремой 7.1 из разд. 7.4.

Пример. Пусть задана матрица над полем из двух элементов:

тогда характеристический многочлен этой матрицы равен

Это примитивный и, слетовательно, неприводимый многочлен. Характеристический многочлен должен делиться на минимальный многочлен, следовательно, найденный многочлен должен быть также и минимальным многочленом (см. [1], стр. 84; [43], стр. 79). Матрица соответствует схеме, показанной на рис. 7.17.

Рис. 7.17. Схема, эквивалентная схеме, изображенной на рис. 7.15.

Эта схема обладает той же самой совокупностью возможных выходных последовательностей, что и схема, изображенная на рис. 7.15, поскольку они подчиняются одному и тому же разностному уравнению, однако для нее при том же самом числе компонент требуется на один разряд меньше. Для любого нормированного многочлена существует сопровождающая матрица

(см. [1] стр. 85; [3] стр. 308). Иногда сопровождающая матрица определяется как матрица, транспонированная к матрице (см. [43], стр. 81):

Можно показать, что многочлен является минимальным многочленом одновременно для обеих матриц Матрица задаваемая равенством (7.36), соответствует схеме, изображенной на рис. 7.6, с одним исключенным входом, в то время как матрица соответствует схеме, изображенной на рис. 7.14. Рассмотренные ранее разностные уравнения [уравнения (7,21) и (7.2) соответственно] совпадают с уравнением (7.35).

Если матрица размерности и если степень ее минимального многочлена равна то говорят, что матрица

с невырождающимся уравнением. Каждая матрица с невырождающимся уравнением подобна сопровождающей матрице для ее минимальной функции (см, [43], стр. 123). Это значит, что если матрица с невырождающимся уравнением, то существует матрица А, такая, что где сопровождающая матрица для минимального многочлена для матрицы Поэтому схема, соответствующая матрице и схема, соответствующая матрице удовлетворяют одному и тому же разностному уравнению. Эти схемы эквивалентны: они отличаются только способом представления их состояний.

Пример. В примере на стр. 149 матрица а переводила матрицу в матрицу которая является матрицей, соответствующей сопровождающей матрице в форме (7.37). Заметим, что если в качестве начальных условий в схеме, изображенной на рис. 7,16, выбран вектор, соответствующий первой строке матрицы а, то последовательные значения символов, появляющихся в разрядах схемы, задаются остальными строками матрицы а. Этот способ нахождения матрицы а для приведения заданной матрицы с невырождающимся уравнением к канонической форме описан в работе [43] на стр. 122.

Любая матрица с невырождающимся уравнением подобна некоторой матрице вида

где сопровождающая матрица для минимальной функции матрицы а каждая матрица при сопровождающая матрица для некоторого многочлена Кроме того, каждый многочлен Делится на Матрица вида (7.38) называется матрицей в рациональной канонической форме (см. [1], стр. 86; [43] гл. 6).

В соответствующей схеме нет соединений между разрядами, соответствующими столбцам различных матриц и Поэтому эта схема состоит из изолированных частей, соответствующих матрицам Каждый выходной символ схемы является линейной комбинацией символов, содержащихся в разрядах нескольких или всех ее изолированных частей. Далее, минимальный многочлен для матрицы должен делиться на многочлен при любом и поэтому в соответствии с теоремой 7.1 каждый возможный символ на выходе каждой части схемы является решением уравнения Это значит, что каждая выходная последовательность схемы совпадает с одной из возможных выходных последовательностей схемы, соответствующей только матрице

Таким образом, любая автономная линейная последовательная переключательная схема эквивалентна либо схеме, изображенной на рис, 7.6 (в случае матрицы с невырождающимся уравнением), либо объединению нескольких таких схем, являющихся изолированными, если не учитывать, что выходы отдельных частей могут комбинироваться друг с другом (в случае матрицы с вырождающимся уравнением).

Полученный вывод может быть обобщен на случай ненулевого входа, хотя здесь построения более громоздки:

и вообще

Если минимальный многочлен для матрицы то и

где

Тогда из уравнения (7.25) получаем

В случае схемы с одним входом и одним выходом матрица размерности т. е. скаляр, так же как и матрица для любсго Если преобразовать соотношение (7.42), переписав его, используя символ то оказывается, что это соотношение имеет тот же самый вид, что и соотношение (7.18). Итак, эта схема описывается разностным уравнением типа уравнения (7.18), а в терминах соответствующей передаточной функции — эквивалентным ему уравнением .

Снова ключевая роль принадлежит матрице поскольку она описывает соединения между отдельными разрядами. Снова "изменение системы координат", задаваемое равенствами (7.30), можно использовать для нахождения матрицы подобной матрице но записанной в специальной канонической форме. Если матрица с невырождающлмся уравнением, то сопровождающая матрица для минимального многочлена матрицы Основная обратная связь схемы, соответствующей связи в матрице подобна обратной связи в схеме, изображенной на рис. 7.6, если используется сопровождающая матрица, задаваемая равенством (7.36), или подобна обратной связи в схеме, изображенной на рис. 7.14, если используется сопровождающая матрица, задаваемая равенством (7.37). Любая входная линия может быть соединена с любым разрядом и любой разряд — с любой выходной линией,

В случае матрицы с вырождающимся уравнением матрица имеет вид матрицы (7.38), и, как и для автономного режима, схема образуется совокупностью схем типа изображенных на рис. 7.6 или на рис. 7.14. Снова возможны соединения между любой входной линией и любым разрядом и между любым разрядом и любой выходной линией, но зато не может быть соединений между отдельными схемами, соответствующими отдельным матрицам, образующим диагональ в матрице (7.38).

Необходимо отметить, что всегда можно реализовать схему с заданной передаточной функцией при помощи такого числа разрядов, которое равно наибольшей из степеней числителя и знаменателя передаточной функции. Для такой реализации —матрица с невырождающимся уравнением, а схема, соответствующая матрице с вырождающимся уравнением, содержит больше элементов, чем это необходимо для реализации ее передаточной функции.

<< Предыдущий параграф Следующий параграф >>
Оглавление