Краткие теоретические сведения. Циклические коды являются наиболее распространенными из систематических кодов

 

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

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

где х – основание системы счисления;

,..., – коэффициенты разрядов, принимающие значения от 0

до х – 1.

Переход от записи двоичного числа к записи в виде многочлена осуществляется следующим образом:

.

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

и

, получим

.

Важно отметить, что в результате алгебраических действий над циклическими кодами, степень полученных полиномов не должна превосходить степени исходных полиномов [ ].

Основным свойством циклических кодов, определившим их название, является то, что циклический сдвиг элементов кодового слова на один элемент влево также образует разрешенную комбинацию. Данный циклический сдвиг алгебраически эквивалентен умножению ее на многочлен х.

Т.к. степень многочлена n -элементной комбинации не должна превышать

n - 1, то есть , отсюда

,

т.е. является циклическим сдвигом комбинации. Например,

,

или в численном выражении

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

Среди общего количества комбинаций (n - 1)-разрядного полинома, равного , не все, а только некоторые - могут быть комбинациями циклического кода, да и то только при условии их деления без остатка на некий полином степени r = n - k, называемый образующим. Такие комбинации составляют множество разрешенных кодовых комбинаций циклического кода.

Идея построения циклического кода сводится к тому, что полином, представляющий информационную часть кодовой комбинации разрядностью k преобразуется на передающем конце (умножением на образующий полином) в полином степени n - 1, который при безошибочной передаче по каналу связи делится без остатка на образующий полином на приемном конце системы передачи дискретных сообщений.

Образующий полином циклического кода должен удовлетворять двум условиям:

1) Полиномы должны быть неприводимыми, т.е. не делиться ни на какой другой полином.

2) Двучлен вида должен делиться на без остатка.

Поскольку неприводимый полином не может быть представлен в виде произведения многочленов низших степеней, то проверить это можно простой подстановкой в него корней х = 1 и х = 0. Например, при r = 3

.

Если можно разложить на множители, то это означает, что уравнение имеет корни х = 0 или 1. Прямой подстановкой этих чиссел можно убедиться, что , т.е. этот полином неприводимый.

Для того, чтобы код был циклическим, необходимо и достаточно, чтобы был делителем многочлена . Пусть

а - многочлен, соответствующий циклическому сдвигу. Тогда

 

а или

.

Левая часть выражения делится на по определению, поэтому многочлен , а, следовательно, и делится на - порождающий полином циклического кода.

Обнаружение ошибок в циклическом коде производится делением принятой кодовой комбинации на порождающий полином (вид его должен быть известен на приеме). Остаток от деления R(x) играет роль синдрома. Если R(x) , то считается, что произошли ошибки при передаче. Если R(x)= 0, то комбинация принята правильно.

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

Остаток от деления – синдром циклического кода, не равный нулю, – свидетельствует о наличии ошибки. В кодах с образующим полиномом степени r остаток представляется в виде полинома, максимальная степень которого r. Это означает, что количество различных ненулевых остатков может быть .

Таким образом, для исправления ошибок необходимо обеспечить условие, при котором количество различных ненулевых остатков будет равно количеству элементов n (при исправлении одной ошибки) или числу сочетаний из n по , где - количество ошибок, исправляемых кодом. Например, в коде с n = 15 при = 2 следует иметь остатков, что обеспечивается r = 7 (). Следовательно, нужно выбрать образующий полином с r = 7 и код с n = 15 (15, 7).

Не все неприводимые многочлены позволяют формировать различных остатков. Это присуще только определенному классу многочленов, называемых «примитивными». Например,

- примитивный образующий полином, а

нет [ ].

В таблицах справочников и учебников, посвященных циклическим кодам, приводятся обычно только примитивные полиномы.

Итак, разрешенную кодовую комбинацию циклического кода можно получить умножением исходной кодовой комбинации С(х) на образующий полином . Однако, при таком способе кодирования информационные и проверочные символы не отделены друг от друга. Код получается неразделенным, что затрудняет практическую реализацию процесса декодирования. Например, пусть Q(x) = 0111. Образуем циклический код, исправляющий ошибки. В данном случае или . Так как число информационных элементов k = 4, учитывая, что n = k + r, имеем . Отсюда подбором находим, что k = 3, следовательно, необходим код (7, 4). По таблице образующих полиномов [ ] находим при r = 3 . Умножаем Q(x) на :

 

или в алгебраической форме

.

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

Поэтому на практике применяется другой способ образования циклического кода:

1) представляем информационную часть кодовой комбинации длиной k в виде полинома Q(x);

2) умножаем Q(x) на одночлен , т.е. производим сдвиг k -разрядной кодовой комбинации на r разрядов;

3) делим многочлен на образующий полином , степень которого равна r:

.

При делении получается полином С(х) такой же степени, что и Q(x) и остаток R(x) от деления на .

Умножив обе части выражения на , получим

или .

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

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

Таким образом, можно вместо передачи по дискретному каналу связи циклического кода, образованного умножением исходной кодовой комбинации Q (x) на образующий полином - Q (x)× , передается по сути некая другая комбинация , но поскольку полиномы Q (x)и С (х ) имеют одинаковые степени, то произведения их на делают их разрешенными комбинациями циклического кода, связанными лишь определённым циклическим сдвигом. Понятно, что при безошибочной передаче остаток от деления Q (x)× и будет равен нулю. Но данная подмена дает на приеме возможность разделить информационные и проверочные разряды, т.е. получить разделимый код, где информационные разряды занимают старшие позиции, а остальные n – k разрядов являются проверочными.

Для ранее приведенного примера согласно описанному алгоритму имеем:

 

1)

2) Умножаем Q (x) на , т.к. r = 3.

- нециклическое умножение.

3) Делим Q (x)× на :

Отсюда .

4) Получаем

,

что соответствует кодовой комбинации

На приеме (при безошибочной передаче) снова делим полученную комбинацию на :

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

 

4.2. Практическая программа:

1) запустить на персональный компьютере в составе локальной вычислительной сети (Рис.1) программу перехватывателя пакетов Ethreal;

2

Рис.1 Структурная схема локальной сети кафедры телекоммуникационных систем УГАТУ

 

2) настроить программу Ethreal на перехват данных;

3) запустить броузер “Internet Explorer”;

4) активизировать функцию перехвата данных;

5) найти в составе принятого кадра 2 уровня сети Ethernet проверочную FCS комбинацию IP заголовка;

6) вычислить контрольную сумму IP заголовка посредством суммирования шестнадцатиразрядных слов, кодирующих поля от «версии» до «IP адреса назначения», с переносом в младший разряд и суммированием с ним, цифры переноса, выходящей за пределы шестнадцати разрядов и сравнить полученный остаток с найденным в п.5 значением FCS;

7) повторить пп.5 и 6 для двух других принятых кадров.

 

Список литературы

 

1.. Телекоммуникационные системы и сети:: уч.пособие для вузов. Под ред. В.П. Шувалова. Т.1, Т.2. М.: Горячая линия-Телеком. 2005

2. Галкин В.А., Григорьев Ю.А. «Телекоммуникации и сети». М. Издательство МГТУ им.Н.Э.Баумана. 2003 г.

3. Шувалов В.П. и др. «Передача дискретных сообщений». М. Радио и связь. 1990 г.