Лекции по теории информации. Фурсов teoria_informacii. Лекции по теории информации под редакцией Н. А. Кузнецова
 Скачать 1.32 Mb.
|
|
13.6 Матричное представление циклических кодов Циклический код является групповым кодом, поэтому он может строиться с использованием матричных представлений так, как описано выше. Однако в данном случае появляются также некоторые дополнительные возможности, связанные со свойством цикличности. Рассмотрим способы построения обра- зующей матрицы циклического кода. Способ 1. Пусть образующий многочлен задан в виде 1 0 m m g x g x g x g Тогда образующая матрица может быть построена путем умножения g x на одночлен 1 , k x k n m и последующим циклическим сдвигом так, что каждая i -я строка образующей матрицы составляется из коэффициентов многочлена k i g x x ( 1, i k ): 116 1 0 1 0 , 1 0 0 0 0 0 0 0 m m m m n k m m g g g g g g g g g M (13.12) Способ 2. Рассматриваются многочлены i Q x , соответствующие коду, со- держащему только один ненулевой разряд: , 1, n i i Q x x i k . Для них вычис- ляются остатки i i r x Q x g x . Каждая i -я строка образующей матрицы формируется путем сложения по модулю два указанных многочленов и соот- ветствующих им остатков. При этом образующая матрица (в данном случае систематического кода) представляется двумя подматрицами: , , n k k k n k M E P , где k E – единичная k k - матрица, а строками матрицы дополнения , k n k P яв- ляются остатки , 1, i r x i k 13.7 Построение проверочной матрицы циклического кода Проверочная матрица в данном случае может строиться так же, как в слу- чае обычного группового кода, например, с использованием проверочных ра- венств и/или матрицы-дополнения. Однако для циклического кода существует еще один способ построения проверочной матрицы, заключающийся в делении многочлена 1 n x на многочлен 1 g x , являющийся дополнением к образую- щему. Многочлен дополнения соответствует кодовой комбинации, которая по- лучается из комбинации, соответствующей образующему многочлену путем перестановки символов в обратном порядке. Предположим, что в результате деления двучлена 1 n x на многочлен до- полнения получен некоторый многочлен: 1 0 1 1 n k k x b x b x b g x (13.13) Из коэффициентов этого многочлена составляется первая строка проверочной матрицы, а остальные строки образуются циклическим сдвигом: 117 1 0 1 0 1 0 0 0 0 0 0 0 b b b k b b b k b b b k H (13.14) В качестве примера построим проверочную матрицу для кода (7,4), порож- даемого образующим многочленом 1 3 x x x g . Соответствующий много- член дополнения 1 2 3 1 x x x g . В результате деления на него двучлена 1 7 x получаем многочлен 1 2 3 4 x x x . Соответствующая этому многочле- ну проверочная матрица имеет вид 1 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 H Нетрудно убедиться, что любая разрешенная комбинация n A , полученная путем умножения некоторого заданного информационного многочлена x a на указанный выше образующий многочлен: x g , в результате умножения на транспонированную проверочную матрицу: T n H A дает синдром, состоящий из одних нулей. 118 Лекция 14 Кодирование линейными последовательными машинами 14.1 Понятие линейной последовательной машины Линейная последовательная машина (ЛПМ) – это система с конечным числом входов , 1, i u i l и выходов , 1, j y j m , сигналы на которых наблюдают- ся в дискретные моменты времени, и выполняющая следующие элементар- ные функции (рис. 14.1) [2]: 1) сложение: 1 l i i y u ; 2) умножение на постоянную: y u ; 3) задержка: 1 y t u t Здесь и далее под аргументом сигнала подразуме- вается номер момента времени. Общая схема ЛПМ может быть представлена в виде, показанном на рис. 14.2. Число задержек оп- ределяет размерность ЛПМ. Запрещаются петли, не содержащие ни одной задержки, т.к. это приво- дит к неопределенности в описании состояний , 1, i s t i k Для ЛПМ размерности k имеют место равенства 1 , 1, i i s t s t i k или в векторном виде ' 1 t t s s , где t s – 1 k -вектор состояний. Множество векторов t s образует простран- ство состояний ЛПМ. 1) 2) 3) Рис. 4.1 – Элементы ЛПМ Рис. 14.2 – Общая схема ЛПМ 119 14.2 Матричное описание ЛПМ В соответствии с общей схемой (рис. 14.2) работу ЛПМ можно описать следующими соотношениями 1 1 1 , 1, k l i ij j ij j j j s t a s t b u t i k , (14.1) 1 1 , 1, k l i ij j ij j j j y t c s t d u t i m (14.2) Равенства (14.1), (14.2) можно представить компактно в векторно-матричной форме: 1 t t t s As Bu , (14.3) t t t y Cs Du , (14.4) где A , B , C , D – k k , k l , m k , m l -матрицы, а u , y – 1 l , 1 m -векторы соответственно. По соотношениям (14.3), (14.4) нетрудно выписать реакцию системы на любом шаге. В частности, при отсутствии входного сигнала ( 0 t u ), выход- ной сигнал на шаге t связан с начальным состоянием ЛПМ соотношением вида 1 0 t t t t y Cs CAs CA s (14.5) 14.3 Каноническая и естественная нормальная форма ЛПМ Аннулирующим многочленом для матрицы A является многочлен x та- кой, что 0 A Аннулирующий многочлен минимальной степени со старшим коэффициентом, равным единице, называется минимальным. Многочлен det x x A E называется характеристическим. По теореме Гамильтона-Кэли всякая матрица удовлетворяет своему характеристическому многочлену, т.е. 0 A 120 Следовательно, характеристический полином всегда является аннулирующим, но не обязательно минимальным. Матрица 0 1 1 0 x k E A (14.6) называется канонической (сопровождающей) матрицей для многочлена\ 1 1 1 0 k k k x x x x Многочлен x может быть разложен на элементарные множители: 1 2 1 2 1 2 r l l l r r x x x x p x p x p x Многочлены , 1, i x i r называют элементарными делителями матрицы x A . С использованием указанного разложения на элементарные делители может быть построена естественная нормальная форма матрицы: 1 2 * 0 0 0 0 0 0 r x x x x A A A A , (14.7) где , 1, i x i r A – матрицы вида (14.6). 14.4 Подобные и минимальные ЛПМ Преобразование 1 ˆ A PAP , где P – невырожденная матрица, называется преобразованием подобия. Преобразование подобия не изменяет собственные значения матрицы, следовательно, подобные матрицы имеют одинаковые эле- ментарные делители. В частности, если x A подобна некоторой матрице ˆ A с элементарными делителями 1 , , r x x , то она также подобна естествен- ной нормальной форме (14.7). 121 Введя в пространстве состояний преобразование координат t t s Ps и умножив (14.3) слева на P , систему (14.3) (14.4) представим в виде 1 1 t t t Ps PAP s PBu , (14.8) 1 t t t y CP s Du , (14.9) Далее введя обозначения ˆ 1 A PAP , ˆ B PB , ˆ 1 C CP , ˆ D D , с учетом того, что в соответствии с используемым преобразованием координат 1 1 t t Ps s , уравнения (14.8), (14.9) можно переписать в виде ˆ ˆ 1 t t t s A s Bu , (14.10) ˆ ˆ t t t y Cs Du (14.11) Системы (14.3), (14.4) и (14.10), (14.11) описывают различные, но совпа- дающие по входу и выходу ЛПМ. Такие ЛПМ называют подобными. Путем преобразований подобия может быть построена ЛПМ, имеющая минимальное число задержек. Такая ЛПМ называется минимальной. Минимальная ЛПМ может быть определена в результате выполнения сле- дующей последовательности шагов [2]. 1. Строится так называемая диагностическая матрица (наблюдаемости) 1 T k K C CA CA 2. Из линейно независимых строк диагностической матрицы формируется матрица T и осуществляется преобразование подобия: ˆ 1 A TAT , ˆ B TB , 1 ˆ C CT , ˆ D D Результатом преобразования будет минимальная ЛПМ. Если ЛПМ с матрицей A имеет подобную ЛПМ с матрицей ˆ A , то она имеет и естественную нормальную форму * A . Каждая подматрица i x A мат- рицы * A , имеющая вид (14.6), соответствует некоторой канонической ЛПМ. 122 Каноническая форма является минимальной ЛПМ. Следовательно, в ре- зультате преобразования подобия исходная ЛПМ всегда может быть представ- лена в виде совокупности ЛПМ, каждая из которых соответствует элементар- ному делителю , 1, i x i r в разложении многочлена x 14.5 Понятие простой автономной ЛПМ Рассмотрим каноническую (минимальную) ЛПМ, имеющую сопровож- дающую матрицу вида (14.6) при 0 t u . ЛПМ с нулевым входным воздейст- вием: называются автономными. Выходные последовательности на всех выхо- дах ЛПМ, являющихся компонентами вектора y , в этом случае формируются по соотношению (14.5) под действием начальных условий. Для автономной ЛПМ можно выполнить преобразование подобия для ка- ждого отдельного выхода (компонента вектора y ) исходной ЛПМ. При этом из ЛПМ с m выходами будет получено m различных ЛПМ с одинаковыми матри- цами A и различными матрицами C , представляющими собой отдельные стро- ки исходной m n – матрицы C Каждая из построенных таким образом m схем называется простой авто- номной ЛПМ (простой АЛПМ), а матрица x A каждой простой АЛПМ имеет вид (14.6) и является сопровождающей для многочлена обратной связи 1 1 1 0 k k k x x x x Матричные соотношения, описывающие соответствующую матрице x A и указанному многочлену x простую автономную ЛПМ при 1,0, ,0 C , имеют вид: 1 1 0 1 1 1 0 1 k k k s t s t s t s t E , 1 1, 0,..., 0 k s t y t s t 123 Приведенные равенства можно представить в виде схемы, показанной на рисунке 14.3. Непосредственно по схеме можно за- писать соотношение для формирования вы- ходной последовательности простой АЛПМ: 1 1 1 1 0 t k k t k t t y y y y (14.12) Нетрудно заметить, что символы выходной последовательности являются ли- нейной комбинацией начального состояния АЛПМ. 14.6 Формирование разрешенных комбинаций циклического кода с помощью АЛПМ В разделе 12.5 мы рассмотрели два способа формирования комбинаций и декодирования циклических кодов. Рассмотрим еще один способ, который наи- более удобно реализуется с помощью АЛПМ. Определим многочлен обратной связи x как частное от деления 1 n x на образующий многочлен. В силу свойств g x такой целый полином сущест- вует: 1 1 1 0 1 n k k k x x x x x g x (14.13) Многочлен (14.13) называют также генераторным полиномом. Для этого поли- нома можно построить сопровождающую матрицу x A вида (14.6) и соответ- ствующую ей АЛПМ. Если начальное состояние АЛПМ (рисунок 14.3) соответствует исходной информационной последовательности, на выходе будет сформирована комби- нация, первые k символов которой информационные, а следующие за ними n k являются линейной комбинацией предыдущих символов: 1 0 , 1, k j k i j i i a а j n k (14.14) Рис. 14.3 – Схема простой АЛПМ |