ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Алгебраические свойства циклических кодовПри работе с циклическими кодами принято связывать с кодовым словом полином степени , определённый так . (1.1) Для двоичного кода каждый из коэффициентов полинома является или нулем, или единицей. Рассмотрим алгебру циклических кодов. Допустим, необходимо перемножить три многочлена (x3+x2+1)·(x3+x+1)·(x+1). Действия производятся также как в обычной алгебре, только сложение проводится по модулю 2. При делении операция вычитания заменяется операцией сложения по модулю 2. Например, необходимо разделить многочлен седьмой степени на многочлен третей степени (x7+x5+x4+x+1) / (x3+x2+1) Операция деления может быть произведена или в виде многочленов или в виде двоичных кодов.
Схема деления реализуется на регистрах сдвига со встроенными сумматорами по модулю 2. Вид схемы определяется многочленом, на который производится деление. В процессе деления с помощью такого устройства находится остаток.
Теперь предположим, мы формируем полином . Этот полином не может представить кодовое слово, так как его степень может быть равна (если ). Однако если мы разделим на , мы получим , (1.2) где . Заметим, что полином представляет кодовое слово , которое как раз образовано из кодового слова циклическим сдвигом на одну позицию. Поскольку представляет собой остаток, полученный делением на , мы говорим, что . (1.3) Аналогичным образом, если представляет кодовое слово в циклическом коде, тогда также является кодовым словом циклического кода. Так что можно написать , (1.4) где остаточный полином представляет кодовое слово циклического кода, a -частное. Мы можем генерировать циклический код, используя порождающий полином степени с двоичными коэффициентами, который является множителем при факторизации полинома . Порождающий полином в общем виде можно записать так . (1.5) Мы также определяем полином информационного сообщения , (1.6) где определяет информационных бит. Ясно, что произведение - это полином степени меньшей или равной , который может представлять кодовое слово. Заметим, что имеется полиномов и, следовательно, имеется возможных кодовых слов, которые можно формировать при заданном . Допустим, что мы обозначим эти кодовые слова так (1.7) Чтобы показать, что кодовые слова в (1.7) удовлетворяют циклическому сдвигу, рассмотрим какое-либо кодовое слово в (1.7), Циклический сдвиг дает (1.8) и, поскольку и и делятся на без остатка, то и делится на без остатка, т.е. можно представить как . Следовательно, циклический сдвиг в кодовом слове , генерируемый согласно (1.7), порождает другое кодовое слово. Из вышесказанного мы видим, что кодовые слова, обладающие циклическими свойствами, можно генерировать умножением сообщений на уникальный полином степени - называемый порождающим полиномом циклического кода, который является множителем при факторизации . Циклический код, генерируемый указанным образом, занимает подпространство векторного пространства . Размерность подпространства равна . Пример 1.1 Рассмотрим код с длиной блока . Полином можно разложить на следующие сомножители . (1.9) Чтобы синтезировать циклический код (7,4), мы можем взять один из двух порождающих полиномов: или (1.10) . Коды, генерируемые порождающими полиномами и , квивалентны. Кодовые слова кода (7,4), генерируемые полиномом даны в табл. 1.1 В общем полином можно факторизовать так: , где - означает порождающий полином для циклического кода, означает проверочный полином степени . Последний можно использовать для генерирования дуального кода. Таблица 1.1 Циклический код (7,4). Порождающий полином
С этой целью можно использовать полином, обратный , определяемый так: (1.11) Ясно, что делится без остатка и на обратный полином. Следовательно, является порождающим полиномом циклического кода. Этот циклический код дуален коду , генерируемому порождающим полиномом . Таким образом, дуальный код образует нуль-пространство циклического кода. Пример 1.2 Рассмотрим циклический код, дуальный коду (7,4), генерированному в примере 1.1 Этот дуальный циклический код (7,3) связан с проверочным полиномом . (1.12) Обратный полином равен . Этот полином генерирует дуальный код (7,3), данный в таблице 1.1 Читатель может убедиться в том, что кодовые слова дуального кода (7,3) ортогональны кодовым словам циклического кода (7,4) из примера 1.1. Желательно показать, как можно получить порождающую матрицу из порождающего полинома циклического кода . Как указано выше, порождающую матрицу для кода можно сконструировать из любого набора линейно независимых кодовых слов. По заданному порождающему полиному легко генерировать набор линейно независимых кодовых слов – это кодовые слова, соответствующие набору линейно независимых полиномов . Таблица 1.2 Дуальный код (7,3). Порождающий полином
Поскольку любой из полиномов степени меньшей или равной , который делится на , можно выразить как линейную комбинацию этих полиномов, набор образует базис размерностью . Следовательно, кодовые слова, связанные с этими полиномами, формируют базис размерности для циклического кода . Не нашли, что искали? Воспользуйтесь поиском:
|