Четность

3.3.4. Групповые коды с обнаружением и исправлением ошибок

Коды с обобщенными проверками на четность

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

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

Наиболее важными и полезными границами для кодового расстояния являются граница Хэмминга, граница Плоткина и граница Варшамова - Гилберта.

Граница Хэмминга, выражаемая обычно следующим образом,

, (3.19)

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

Граница Плоткина также является верхней границей для кодового расстояния при данных n и k и может выражаться следующим образом

. (3.20)

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

. (3.21)

Граница Хэмминга обычно близка к оптимальной для высокоскоростных кодов (т.е. для больших значений k/n), а граница Плоткина - для низкоскоростных кодов.

Согласно границе Варшамова - Гилберта, выражаемой как

, (3.22)

существует (n,k)-код с кодовым расстоянием, не меньшим d, и с числом проверок на четность, не превышающим n-k. Таким образом, граница Варшамова-Гилберта является границей существования и дает нижнюю оценку для кодового расстояния «наилучшего» кода.

Приведем пример использования этих границ. Предположим, что требуется найти код длиной n=63 с кодовым расстоянием d=5 и наибольшим возможным значением k. Примером такого кода является (63,51)-код БЧХ. Для оценки того, насколько хорошим является этот код, используем границы Хэмминга и Варшамова-Гилберта. Из (3.19) следует, что 2017£2^n-k , откуда n-k ³11. Граница Варшамова-Гилберта (3.22) «утверждает», что 39774>2^n-k , откуда n-k £16. Таким образом, из границы Хэмминга следует, что не существует кодов, обеспечивающих заданные параметры, с n-k<11, а граница Варшамова-Гилберта гарантирует существование таких кодов с n-k£16. Отсюда можно сделать вывод, что код (63,51) является «хорошим» и дальнейшие поиски могут привести лишь к незначительному улучшению.

Для кодов с d=3 для определения требуемого числа контрольных разрядов можно найти более простое выражение, воспользовавшись следующими рассуждениями. При передаче кодовой комбинации может быть искажен любой из n разрядов комбинации или комбинация принята без искажений. Следовательно, всего может быть n+1 вариантов исхода. Использование контрольных разрядов должно обеспечить возможность различения всех n+1 вариантов. С помощью n-k разрядов можно описать 2^n-k событий, следовательно, должно выполняться условие или

(3.23)

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

1) замкнутость - т.е. сумма по модулю два двух элементов группы всегда лежит в группе;

2) ассоциативность - т.е. (aÅb)Åc=aÅ(bÅc);

3) наличие единичного элемента - для двоичных кодов это нулевая комбинация;

4) каждый элемент группы обладает обратным, для которого а+(-а)=0, для двоичных кодов каждая кодовая комбинация совпадает со своей обратной.

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

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

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

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

u_nu_n-1u_n-2 . . . u₁. Положим, что среди этих n разрядов символы u_r, u_l, u_s - контрольные. Число проверочных уравнений определяется числом контрольных символов:

(3.24)

В этих уравнениях коэффициенты принимают значения 1 или 0 в зависимости от того, используется или нет соответственно для определения значения i-го контрольного разряда j-й информационный разряд.

С помощью этих уравнений могут быть составлены все N_p=2^k разрешенных или рабочих комбинаций кода путем записи информационных разрядов каждой комбинации и вычисления значений контрольных разрядов по уравнениям (3.24) для каждой комбинации информационных разрядов. Таким образом, тот или иной код может быть задан таблицей информационных кодовых комбинаций и системой проверочных уравнений.

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

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

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

Пример.3.7. Построить образующую матрицу (7,4)-кода, имеющего следующие проверочные уравнения

Решение. Сначала целесообразно построить полную таблицу кода в соответствии с проверочными уравнениями.

Выберем образующие кодовые комбинации (выделены жирным шрифтом) и запишем их в виде образующей матрицы .

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

1000011

Å 0100110

0001101

1101000,

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

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

и т.н. дополняющей .

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

(3.25)

Единичная матрица является образующей для равномерного примитивного кода, поскольку с ее помощью могут быть построены все 2^k-1 ненулевых комбинаций этого кода путем суммирования по модулю два ее строк в различных сочетаниях.

Дополняющая матрица, если не заданы проверочные уравнения, может быть получена путем подбора k различных комбинаций, содержащих n-k разрядов. Эти комбинации должны удовлетворять следующим условиям :

1) количество единиц в комбинации должно быть не менее d-1,

2) сумма по модулю два любых двух комбинаций должна содержать не менее d-2 единиц.

Пример.3.8.Построить образующую матрицу систематического кода (7,4) с d=3.

Решение. Начать построение целесообразно с нахождения дополняющей матрицы . В данном случае n=7, k=4, n-k=3, т.е.D_3,4.. Следовательно, надо подобрать трехразрядные комбинации, каждая из которых содержит по d-1=3-1=2 единицы.Поскольку таких комбинаций всего три, а их требуется k=4, то в качестве четвертой выберем, не нарушая первого условия, комбинацию, содержащую три единицы. Тогда дополняющая матрица

и образующая матрица , (3.26)

из которой может быть найдена система проверочных уравнений

(3.27)

Сравнивая примеры 3.7 и 3.8 можно сделать вывод: для каждой образующей матрицы G_n,k существует своя единственная система проверочных уравнений и, наоборот, поскольку то и другое является описанием одного и того же кода.

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

. (3.28)

Пример.3.9.Для кода из примера 3.8- построить проверочную матрицу.