Факультет информатики. Локальные и глобальные сети Локальные и глобальные сети

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

Имеются следующие разновидности систематических кодов. Кодами Хемминга  называются обычно 1) коды с расстоянием d=3, исправляющие все одиночные ошибки, 2) коды с расстоянием d=4, исправляющие все одиночные ошибки и обнаруживающие двойные.

Операции кодирования и декодирования сводятся к умножению и делению полиномов по правилам двоичной арифметики.

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

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

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

Практическая реализация групповых кодов. Простые (n, n1)коды с проверкой на четность.

Классификация кодов представлена на рис.19.6. Все корректирующие коды можно разделить на два класса блочные коды и непрерывные коды.

Блочные коды коды, в которых каждому сообщению (или элементу сообщения) сопоставляется блок из n символов (кодовая комбинация, кодовый вектор). Возможны неравномерные блочные коды, имеющие блоки различной длины; такие коды возникают при статистическом кодировании, но за последнее время ими мало занимаются основное внимание уделено равномерным кодам. Возможность обнаружения и исправления ошибок основана на том, что число кодовых векторов меньше, чем N0=mn, где m основание, nзначность кода, т.е. длина блока. Ошибка обнаруживается, если принятый вектор не принадлежит коду.

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

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

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

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

Число кодовых векторов равно 2k.

Неразделимые коды образуют в настоящее время не многочисленную группу. К ней относятся коды с постоянным весом и коды Плоткина. Коды с постоянным весом простые блочные коды, широко применяемые на практике. Суть дела определяется названием: все кодовые векторы этих кодов имеют одинаковый вес, т.е. одинаковое число единиц. Изменение этого числа указывает на наличие ошибки. Эти коды могут служить лишь для обнаружения ошибок. Примером является известный код “3” из “7” семизначный код с постоянным весом.

Коды Плоткина отличаются тем, что по эффективности достигают теоретического предела Плоткина. Эти коды получаются из матриц Адамара. Матрица Адамара квадратичная матрица из элементов 1 и 1 с ортогональными строками. С помощью этих матриц могут быть построены коды с большим кодовым расстоянием, а именно (в зависимости от четности):

Если d = 2p, 2d = n= 4p, то возможное число кодовых векторов равно 2n = 8p. Такой код образуется строками матрицы Адамара порядка n при замене 1 на 0, а затем строками, получаемыми заменой всех единиц нулями, а нулей единицами. Если n= 4p =2r, то код является групповым и совпадает с кодом РидаМюллера первого порядка. Если n=p не является степенью двух, то код не является групповым. Порядок m матриц Адамара должен быть кратен четырем, т.е. m=4k. Значения m, для которых доказано существование таких матриц (до m=1000), имеются в литературе.

Коды Плоткина имеют высокую исправляющую способность (большое d). Однако нет практических методов кодирования и декодирования, так что прикладное значение этих кодов невелико.

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

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

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

Метод построения систематических кодов основан на применении производящей матрицы, строки которой линейнонезависимые базисные векторы. Все кодовые векторы получаются как линейные комбинации строк производящей матрицы (по модулю 2).


На главную