51. Циклический код. Основные сведения. Способы описания (образующая и пpовеpочная матpицы).

Множество кодовых комбинаций называется циклическим кодом, если циклический сдвиг любой комбинации на любое число разрядов влево или вправо дает комбинацию из этого же множества. Циклический код является частным видом группового кода. Он обладает всеми свойствами, присущими групповому коду. Кроме того, имеет дополнительную особенность − цикличность. Кодовая комбинация β разделимого циклического кода представляется в виде блока длины n = m+ k ,

При описании циклических кодов наиболее удобной является запись дво-ичной комбинации циклического кода β в виде многочлена β(х) некоторой фиктивной переменной х. Двоичная комбинация m-разрядного первичного кода записывается аналогично в виде информационного многочлена m(x).

В теории циклического кодирования над полиномами и соответствующими им комбинациями вводятся операции сложения, умножения и деления.

Операция умножения (деления) многочленов включает их перемножение (деление) по обычным правилам с дальнейшим приведением подобных членов по модулю 2. Например,

Построение циклического кода основано на использовании так называемого образующего или порождающего полинома р(х). Он должен быть неприводимым многочленом, т.е. делиться только сам на себя и на единицу. Образующий полином выбирается в разложении двучлена xn +1 на неприводимые многочлены [8, 9]. Старшая степень р(х) определяется числом контрольных символов k.

называется проверочным. Его высшая степень совпадает с числом информационных разрядов m первичного кода. Кодовые комбинации циклического кода помимо общих для групповых

кодов свойств удовлетворяют двум условиям: 1) без остатка делятся на образующий полином, т.е.β(x) = 0 по модулю р(х) (2.3)

многочлены β(х) и h(x) перемножаются по обычным правилам с приведении ем подобных по модулю 2. Если старшая степень полученного произведения не превышает (n-1), то оно является результатом умножения по модулю(xn +1). В противном случае результат умножения делится на двучлен xn +1 и получившийся при этом остаток является результатом умножения по модулю (xn +1). На названных выше двух свойствах основано обнаружение и исправление ошибок при передаче циклического кода по каналу связи. Эти же свойства лежат в основе его построения и технической реализации кодирующих устройств. Циклический сдвиг кодовой комбинации β на i шагов влево (вправо)

Способы описания. Наиболее целесообразно циклический код представлять в виде разделимого (n,m) кода. Тогда алгоритм кодирования определяется выражением

Умножение на одночлен xk эквивалентно приписыванию k нулей со сто-роны младших разрядов. Данная операция позволяет впоследствии на месте этих нулей размещать контрольные символы. Разделим полученное произведение на образующий полином

где 1101 − информационные символы; 001 − контрольные символы. Циклический код подобно групповому коду можно описать полно и ком-пактно с помощью образующей матрицы

Процесс построения образующей матрицы формализуется следующим образом. Исходя из числа информационных разрядов m, составляется еди ничная матрица Im. К ней справа приписывают матрицу контрольных симво-лов Rm,k , которая находится следующим формальным приемом. Единица с рядом нулей делится на образующий полином в виде кодовой комбинации. Выписываются m промежуточных остатков деления. Эти остатки, записан-ные в обратном порядке, образуют матрицу контрольных символов. Пример 3. Найдем матрицу контрольных символов для условий примера

С помощью образующей матрицы могут быть получены все М кодовые комбинации циклического кода путем суммирования строк матрицы по мо-дулю 2 в различных сочетаниях. Кроме образующей матрицы, циклический код можно описать с помощью проверочной матрицы. В принципе ее можно представить в канони- как для группового кода. Однако эта форма не позволяет использовать свойство цикличности для коррекции ошибок. В этом случае обнаружение и исправление ошибок подобно групповому коду.Наибольшее применение на практике имеет циклическая форма проверочной матрицы H в степени∗ k,n. Ее первая строка зависит от вида проверочного полинома h(x), а остальные строки получаются циклическим сдвигом вправо первой строки. Первая строка проверочной матрицы связана с видом проверочного полинома следующим правилом. Полином h(x) представляется в виде кодовой комбинации. Запись этой комбинации в обратном порядке и приписывание к ней справа (k-1) нулевых символов дает первую строку матрицы H в степени* k,n . Строки проверочной матрицы отражают состав проверок на четность

Состав проверок на четность и уравнения для формирования контрольных символов имеют вид