Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


Кодирование с использованием циклических кодов




И математического аппарата умножения и деления полиномов.

Сигнатурный анализ

Циклический код.

Циклический код обязан своим названием особенности: если некоторая кодовая комбинация принадлежит множеству разрешённых комбинаций, то и комбинация, полученная циклической перестановкой разрядов тоже принадлежит множеству разрешённых комбинаций.

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

G(x3)=x3+x+1.

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

Идея построения циклического кода основана на понятии неприводимого многочлена, который делится только на себя и на единицу:

G(x2)=x2+x+1;

G(x)=x+1;

G(x16)=x16+x9+x7+x4+1.

По существу, используется так называемое поле Галуа – алгебра с двумя операциями: умножением и сложением по модулю 2 (GF(2)).

Умножение полиномов.

Некоторый полином x3+1 можно записать в развёрнутой форме:

Здесь коэффициенты принимают значения из бинарного множества.

Умножение производится по правилам обычной алгебры, например:

3+1)х=х4+х, т.е. получили:

Это сдвиг на один разряд вправо.

С учетом использования операции сложения по модулю 2, одинаковые разряды при сложении уничтожаются.

Рассмотрим пример умножения информационного полинома А=х3+1 на порождающий (образующий) полином G=х3+х+1.

Аналитически процесс умножения можно представить так:

Процесс умножения в развернутом виде показан в табл. 66.

                                                                                           Таблица 66

Умножение A на образующий полином G

  х6 х5 х4 х3 х2 х 1
А×1       х3     1
А×x     х4     х  
А×x3 х6     х3      
А×G х6   х4     х 1

 

Проведем умножение в двоичном коде:

х6пр х5пр х4пр х3пр х2пр хпр 1пр – порядок следования разрядов произведения (пр).

Получим уравнения для произведения многочленов, при условии, что множитель G «жестко задан», а полином А – любой, – степени три:

Амн3мн х2мн хмн 1мн – это переменные множимого (мн)-полинома

третьей степени.

G= 1 0 1 1 – множитель (образующий полином).

Процесс умножения в развернутом виде показан в табл. 67.

                                                                                           Таблица 67

    Å     0 х3мн     0 х2мн   х3мн 0 хмн х3мн х2мн 0 1мн х2мн хмн 0   хмн 1мн     1мн
      х3мн   х2мн   х3мн Å хмн   х3мн Åх2мн Å1мн   х3мн Å хмн   хмн Å1мн   1мн

Умножение A на образующий полином G

           х6пр х5пр        х4пр                       х3пр                       х2пр            хпр      1пр

Т.е. уравнения, описывающие значения разрядов произведения, в зависимости от значения разрядов множимого при условии «жестко заданного» множителя имеют вид:

Эти уравнения позволяют определить вид соответствующего устройства – умножителя полиномов, основанного на D-триггерах и элементах сложения по модулю 2.

Деление полиномов.

По аналогии с умножением вводится операция деления полиномов.

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

Например:

Здесь используется суммирование по модулю 2, поэтому х66=0, аналогично х44=0, х33=0, х+х=0, 1+1=0.

Деление полиномов можно выполнять последовательными вычитаниями по модулю 2.

Можно показать, что если А – делимое (дл), G – делитель, то разряды частного (чст) определяются так:

1чст3длÅх5длÅх6дл

хчст4длÅх6дл

х2чст5дл

х3чст6дл

Остаток:

1ост=1длÅх3длÅх5длÅх6дл

хостдлÅх3длÅх4длÅх5дл

х2ост2длÅх4длÅх5длÅх6дл

Нулевой остаток указывает на отсутствие ошибки. Такие уравнения позволяют построить схемы – делители на образующий полином.





Поделиться с друзьями:


Дата добавления: 2018-10-18; Мы поможем в написании ваших работ!; просмотров: 262 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Начинайте делать все, что вы можете сделать – и даже то, о чем можете хотя бы мечтать. В смелости гений, сила и магия. © Иоганн Вольфганг Гете
==> читать все изречения...

2405 - | 2201 -


© 2015-2025 lektsii.org - Контакты - Последнее добавление

Ген: 0.012 с.