Кодирование в системах ПДС

Классификация кодов.

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

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

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

Различают два метода формирования проверочной группы: поэлементной и в целом; последний характерен для широко распространенных полиномиальных кодов (и их разновидности – циклических). Среди систематических кодов большое применение нашли коды Хэмминга. Эти коды, обеспечивающие d₀=3, позволяют исправить одну ошибку. Помехоустойчивые коды могут иметь основание (значность) и больше 2. Однако в связи со сложностью построения кодирующих и декодирующих устройств они на практике применяются значительно реже двоичных.

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

Широкое распространение получил класс линейных кодов которые называются циклическими. Название этих кодов происходит от их основного свойства: если кодовая комбинация a₁, а₂,......, a_n-1, a_n принадлежит циклическому коду, то комбинации a_n, a₁, а₂,........, a_n-1; a_n-1, a_n, a₁, а₂,......., а_n-2 и т.д., полученные циклической перестановкой элементов, также принадлежат этому коду.

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

Поскольку любое число в произвольной системе счисления можно записать в виде a_n-1×х^n-1+a_n-2×x^n-2+...+ а₀×х⁰, где х-основание системы счисления, a_n-1,...,a₀ – цифры этой системы, то переход от двоичного числа к записи в виде многочлена осуществляется следующим образом:

11011® 1×x⁴ + 1×х³ +0×х²+1×x¹ +1×x⁰=x⁴+x³+x+1

KK ЦК описываются полиномами обладающими определенными свойствами. Последние определяются свойствами и операциями той алгебраической системы, к которой принадлежит множество полиномов. Например, в алгебраической системе, которая носит название поля Галуа (GF(x)), действие над коэффициентами полиномов (сложение, вычитание) производится по модулю два. Умножение полиномов должно производиться по модулю некоторого полинома Р_r(х). Эти два условия определяют замкнутость указанных операций: их применение не приводит к кодовым комбинациям, длина которых больше длинны заданного кода n.

В циклических кодах разрешенными KK являются те, которые делятся на образующий полином без остатка, из всех возможных полиномов степени n (2ⁿ) только 2^K полиномов (к=n-r) имеют нулевой остаток при делении. Они и образуют множество различных КК ЦК.

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

3.2.1 .Построение KK ЦК

Пример:

Дано:

1.Исходная KK, поступающая от источника А(х), содержит k элементов.

2. Дан производящий полином P(x)=x^r+1, где r -число проверочных элементов.

Задание: сформировать KK ЦК.

Формирование KK производится по следующему алгоритму:

1 .А(х)умножается на х^r.

2. Полученное произведение делим на Р(х). В результате получим:

3. У множим правую и левую части на Р(х). В результате:

А(х)×х^r=Q(х)×P(x)+R(x) (суммирование производится по модулю два)

4. Перенесем A(x)×x^r в правую часть уравнения, a Q(x)×P(x) в левую, в результате:

Q(x)×P(x)=A(x)×x^r+R(x) (суммирование по мод. 2)

Левая часть делится на Р(x) без остатка , а следовательно, должна делится без остатка и правая часть.

Существует два способа формирования КК ЦК:

1.Умножение исходной КК на Р(х). Недостатком этого способа является получение неразделимого ЦК, т.е. нельзя выделить отдельно информационные и проверочные элементы.

2. Деление на производящий полином (способ, алгоритм которого описан выше). В этом случае код получается разделимым.

3.2.2. Обнаружение и исправление ошибок в ЦК.

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

Возможность исправления одиночной ошибки связана с выбором образующего полинома Р_r(х). Точно так же, как и в обычных линейных кодах вид синдрома в ЦК зависит от места, где произошла ошибка. В данном случае в качестве синдромов рассматриваются различные остатки R(x) от деления полинома ошибки на образующий полином Рг(х). Среди множества полиномов Р_r(х) существуют так называемые примитивные полиномы, для которых существует зависимость n=2^r-1. Это означает, что при возникновении ошибки в одном из n разрядов КК число различных остатков то же будет равно n.