- •Челябинск
- •Оглавление
- •Основные понятия. Передача кодовых комбинаций
- •Системы счисления и математические операции с двоичными числами
- •Классификация кодов
- •Число-импульсный код
- •Код Морзе
- •Код Бодо́
- •Международный телеграфный код
- •Код Грея
- •Помехозащищенные (корректирующие) коды Основные понятия
- •Коды с обнаружением ошибок Код с четным числом единиц
- •Код с удвоением элементов
- •Инверсный код
- •Код с постоянным числом единиц и нулей в комбинациях (код с постоянным весом)
- •Распределительный код Сln
- •Код с проверкой на четность
- •Код с числом единиц, кратным трем
- •Код с удвоением элементов (корреляционный код)
- •Коды Хемминга
- •Циклические коды
- •Итеративные коды
- •Библиографический список
Циклические коды
Циклические коды характеризуются тем, что при циклической перестановке всех символов кодовой комбинации данного кода образуется другая кодовая комбинация этого же кода.
- комбинация циклического кода;
- также комбинация циклического кода.
При рассмотрении циклических кодов двоичные числа представляют в виде многочлена, степень которого (п - 1), п - длина кодовой комбинации.
Например, комбинация 1001111 (п=7) будет представлена многочленом
При таком представлении действия над кодовыми комбинациями сводятся к действиям над многочленами. Эти действия производятся в соответствии с обычной алгебры, за исключением того, что приведение подобных членов осуществляется по модулю 2.
Обнаружение ошибок при помощи циклического кода обеспечивается тем, что в качестве разрешенных комбинаций выбираются такие, которые делятся без остатка на некоторый заранее выбранный полином G(x). Если принятая комбинация содержит искаженные символы, то деление на полином G(x) осуществляется с остатком. При этом формируется сигнал, свидетельствующий об ошибке. Полином G(x) называется образующим.
Построение комбинаций циклического кода возможно путем умножения исходной комбинации А(х) на образующий полином G(x)с приведением подобных членов по модулю 2:
если старшая степень произведения не превышает (п - 1), то полученный полином будет представлять кодовую комбинацию циклического кода;
если старшая степень произведения больше или равна п, то полином произведения делится на заранее выбранный полином степени п и результатом умножения считается полученный остаток от деления.
Таким образом, все полиномы, отображающие комбинации циклического кода, будут иметь степень ниже п.
Часто в качестве полинома, на который осуществляется деление, берется полином G(x)= +1. При таком формировании кодовых комбинаций позиции информационных и контрольных символов заранее определить нельзя.
Большим преимуществом циклических кодов является простота построения кодирующих и декодирующих устройств, которые по своей структуре представляют регистры сдвига с обратными связями.
Свойства циклического кода:
1) циклический код обнаруживает все одиночные ошибки, если образующий полином содержит более одного члена. Если G(x)=x+1, то код обнаруживает одиночные ошибки и все нечетные;
2) циклический код с G(x)=(x+1)G(x) обнаруживает все одиночные, двойные и тройные ошибки;
3) циклический код с образующим полиномом G(x) степени r = n - k обнаруживает все групповые ошибки длительностью в r символов.
Итеративные коды
Идея итеративных кодов принадлежит Элайесу. Суть предложенного им метода построения кодов легче всего пояснить на примере. Сначала информационные символы aij =0, 1, выписываются в виде таблицы:
|
Информационные символы |
Проверка по строкам |
|
a11, a12, … a1j, … a1m a21, a22, … a2j, … a2m . . . . . . . . . . . ak1, ak2, … akj, … akm |
. . . . . . .
|
Проверка по столбцам |
… |
Проверка проверок |
Затем к каждой строке и к каждому столбцу дописываются проверочные символы, представляющие собой сумму по модулю два информационных символов данной строки или столбца соответственно. (Проверка проверок находится как сумма по модулю два символов последней строки и последнего столбца).
Приведенный код является простейшим двухстепенным итеративным линейным кодом с d=4, причем число комбинаций такого веса при l=m :