Принципы построения помехоустойчивых кодов

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Введение

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

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

Помехоустойчивость кода может быть достигнута за счёт избыточности.

Рис. 1. Классификация помехоустойчивых кодов

1. Общие понятия и определения

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

Избыточность корректирующего - кода может быть абсолютной и относительной. Под абсолютной избыточностью понимают число вводимых дополнительных разрядов:

r = n - k.

Относительной избыточностью корректирующего кода называют величину:

Ошибки -- случайные искажения битов сигнала при передаче или хранении.

2. Принципы построения помехоустойчивых кодов

Коды с четным числом единиц.

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

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

Код с удвоением элементов.

Код с удвоением элементов характеризуется введением дополнительных символов для каждой информационной части комбинации, причем единица дополняется нулем и преобразуется в 10, а ноль дополняется единицей и преобразуется в 01. Тогда исходная комбинация, например, 10101 будет представлена в 1001100110. Показателем искажения кода будет появление в «парных» элементах сочетаний вида 00 или 11.

Код позволяет обнаруживать все ошибки, за исключением случаев, когда имеют место две ошибки в «парных» элементах, причём если произошли одиночные ошибки в разных «парных» элементах, то можно однозначно сказать в каких именно «парных» элементах произошли ошибки.

Инверсный код.

В основу построения инверсного кода положен метод повторения исходной кодовой комбинации. Причем в тех случаях, когда исходная комбинация содержит четное число единиц, вторая комбинация в точности повторяет исходную комбинацию. Если же исходная комбинация содержит нечетное число единиц, то повторение производится в инверсном виде. Например, комбинации 01010 и 01110 инверсным кодом представляются как 0101001010 и 0111010001.

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

Блочный ортогональный код.

При m = 3 порождающая матрица G задает ортогональный код (8,3,4) и имеет следующий вид:

помехоустойчивый кодовый дискретный инверсный

Кодовая комбинация получается путем умножения информационных символов ai (i=0ч2) на соответствующие строки порождающей матрицы кода и последующего сложения всех строк по модулю два:

Например, при поступлении информационной комбинации 101 на вход ортогонального кодера будет сформирована следующая кодовая комбинация С:

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

Биортогональные коды.

Биортогональный набор сигналов, состоящий из М сигналов или кодовых слов, получается из ортогонального набора, состоящего из M/2 сигналов, путем дополнения последнего сопряженными значениями каждого сигнала.

Например, набор 3-битовых данных можно преобразовать в биортогональный набор кодовых слов следующим образом:

Рис. 2

В действительности биортогональный набор состоит из двух ортогональных кодов, таких, что для каждого кодового слова в одном наборе имеется антиподное ему слово в другом. Биортогональный набор состоит из комбинации ортогональных и антиподных сигналов. Если использовать коэффициенты zij, введенные в уравнении:

То биортогональные коды можно представить следующим образом:

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

Трансортогональные (симплексные) коды.

Код, получаемый из ортогонального путем удаления первого разряда каждого кодового слова, называется трансортогональным (transorthogonal), или симплексным (simplex) кодом. Такой код описывается следующими значениями zij:

Двоичный сверточный код.

Принцип построения двоичных сверточных кодов рассмотрим на примере простого цепного кода.

Пусть кодированию подлежит последовательность информационных элементов:

Процедура кодирования цепным кодом заключается в том, что каждый проверочный элемент формируется как сумма по модулю 2 двух информационных элементов, отстоящих друг от друга на t = k-i шагов, где t - шаг сложения:

Как видно, каждый информационный элемент участвует в вычислении двух проверочных элементов и в канал связи передаётся непрерывная последовательность, в которой за каждым информационным элементом следует проверочный. Избыточность цепного кода при этом будет равна 1/2.

Итеративный код.

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

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

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

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

Код Рида-Соломона.

Коды Рида-Соломона строятся сначала как коды над некоторым полем GF(q), где q обычно есть степень числа 2, q = 2p. Далее элементы поля GF(2p) представляются как двоичные векторы длины p. Таким образом, код Рида-Соломона хорошо приспособлен для исправления пачек ошибок длины p.

Пусть a - примитивный элемент поля GF(q), q = 2p. Рассмотрим элементы a, ..., a2t и многочлены (x - a), ..., (x - a2t) как многочлены с коэффициентами из поля GF(q). Тогда, произведение g(x) = (x - a)Ч ...Ч(x - a2t) можно выбрать в качестве порождающего многочлена для кода, слова которого имеют длину n = q - 1 и состоят из элементов поля GF(q). Данный код является циклическим (n, n-2t)-кодом.

Представим теперь каждый символ из поля GF(q), q = 2p, двоичным вектором длины p. Получим двоичный код длины pn, который имеет 2tp проверочных символов и исправляет любую комбинацию из tp или менее ошибок, если эти ошибки произошли только в двоичных наборах, которые заменяют t символов из поля GF(q).

Пусть нам нужно передать кодовое слово С, состоящее из двух чисел - 3 и 1 именно в такой последовательности, т.е. нам нужно передать вектор С=(3,1). Допустим, мы хотим исправить максимум две ошибки, не зная точно, где они могут появиться. Для этого нужно взять 4 избыточных символа. Запишем их нулями в нашем слове, т.е. С теперь равно (3,1,0,0,0,0). Первые два символа - информация, последние четыре - избыточные и всегда равны 0. Запишем кодовое слово С в виде полинома:

Далее делаем обратное дискретное преобразование Фурье, возьмём поле GF(7), где примитивный элемент равен 5. Находим значения полинома С для примитивного элемента z разных степеней. Формула для обратного дискретного преобразования Фурье : cj=C(zj). То есть, находим значения функции С(zj), где j - элементы поля Галуа GF(7). Мы рассчитываем до j=N-ni=6-2=4 степени.

Таким образом из С(3,1,0,0,0,0), получим с(4,1,0,2,5,6) - эту кодовую комбинацию мы и передаём.

Ошибка представляет собой еще одно слово, которое суммируется с передаваемым. Например, ошибка f = (0,0,0,2,0,6). Если сделать с + f, то получим сf(4,1,0,4,5,5).

На приемнике мы получили слово с+f = сf(4,1,0,4,5,5). Известно, что мы кодировали информацию с помощью обратного дискретного преобразования Фурье в GF(7). для вычисления синдрома ошибки, необходимо выполнить дискретное преобразование Фурье.

Формула для дискретного преобразования Фурье:

Сk=N-1*c(z-kj),

по-прежнему используется примитивный элемент равный 5 поля GF(7).

В итоге получим из сf(4, 1, 0, 4, 5, 5), Cf(2, 1, 2, 1, 0, 5), выделенные символы были бы нулями, если бы ошибки не было. Видно, что ошибка была и в данном случае, символы 2, 1, 0, 5 называют синдромом ошибки.

БЧХ-код.

БЧХ - код является циклическим кодом, который задается порождающим многочленом g(x). Для построения кода БЧХ необходимо найти этот порождающий многочлен.

Для того, чтобы найти порождающий многочлен БЧХ, надо выполнить следующие шаги:

1) выбрать основание -- простое число p;

2) выбрать число членов поля q = pk, над которыми будет построен код БЧХ, где k - натуральное число;

3) определить длину кода n, дина кода n определяется из формулы, где m, s - натуральные числа;

4) задать желаемое минимальное расстояние для кода d, значение минимального расстояния кода d должно быть меньше длины кода n;

5) построить поле GF(q).

6) построить поле GF(qm), где m -- параметр кода БЧХ, см. п. 3);

7) найти примитивный элемент б поля GF(qm);

8) найти степень примитивного элемента в = бs, где s -- параметр кода БЧХ, см. 3);

9) найти d - 1 последовательные степени в: вl, вl +1, вl +2, … вl +d-2, где l - произвольное натуральное число;

10) найти нормированный многочлен g(x) минимальной степени над полем GF(q), корнями которого являются все d - 1 подряд идущих степеней вl, вl +1, вl +2, … вl +d-2.

Заключение

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

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

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

Размещено на Allbest.ru