Лекция 10. Коды с обобщенными проверками на четность

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

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

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

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

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

,

(3.8)

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

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

(3.9)

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

(3.10)

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

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

(3.11)

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

Приведем пример использования этих границ. Предположим, что требуется найти код длиной n=63 с кодовым расстоянием d=5 и наибольшим возможным значением k. Примером такого кода является (63,51)-код БЧХ. Для оценки того, насколько хорошим является этот код, используем границы Хэмминга и Варшамова – Гилберта. Из (3.8) следует, что 2017 £ 2^n-k , откуда n-k ³11.

Граница Варшамова – Гилберта (3.11) «утверждает», что 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.12)

Рассматриваемые (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.13)

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

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

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

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

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

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

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

.

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

Å 0100110

0001101

1101000,

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

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

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

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

(3.14)

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

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

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

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

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

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

и образующая матрица

(3.15)

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

(3.16)

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

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

(3.17)

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

Решение

(3.18)

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

(3.19)

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

Из анализа (3.19) видно, что a₁ входит во все три уравнения, а₂ - в первое и второе, а₃ – в первое и третье, а₄ – во второе и третье. Следовательно, искажение любого а_i нарушит вполне определенные уравнения, т.е. сумма по модулю два в них будет равна не нулю, а единице. По тому, какие именно уравнения нарушены, можно определить, в каком разряде произошла ошибка, и восстановить его истинное значение.

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

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

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

,

а принимается

.

При выполнении проверок на приеме в соответствии с системой (3.19) получается

,

т.е. синдром R=110, нарушены 1 и 2 уравнения, в которые входит а₂, следовательно, ошибка в разряде а₂ и тогда исправляющий вектор Е=0010000, а исправленная кодовая комбинация

.

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

Обобщая, можно сказать, что при ошибке в разряде а₄ синдром будет 011, при ошибке в разряде а₃ – 101, при ошибке в разряде а₁ – 111.

То же самое следует из проверочной матрицы этого кода (3.18), где первый столбец – синдром при ошибке в разряде а₄ и т.д.

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

Методы построения кодеров и декодеров таких кодов исследуются в лабораторной работе №7 «Кодеры и декодеры систематических кодов»[1. с. 70-77].

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

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

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

1) принятая кодовая комбинация Y суммируется по модулю два последовательно со всеми кодовыми комбинациями кода X_i , в результате каждого суммирования вычисляются векторы ошибок e_i = Y+X_i ,

2) подсчитывается число d_i единиц в каждом из векторов ошибки e_i,

3) та из X_i, для которой d_i минимально, считается переданной кодовой комбинацией.

Для некоторых систематических (n,k)-кодов неравенство (3.12)

превращается в строгое равенство

(3.20)

Для таких кодов можно записать и, поскольку , то .

(n,k)-коды вида называются кодами Хэмминга (3.21).

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

Уравнение (3.20) имеет целочисленные решения при k=0,1,4,11,26,57,120, . . , что дает соответствующие коды Хэмминга (3,1), (7,4), (15,11), (31,26), (63,57), (127,120),. . . . Коды Хэмминга относятся к немногим известным т.н. совершенным кодам. С учетом данных ранее определений кодового пространства и кодового расстояния представим некоторый код в виде сфер с центрами во всех разрешенных кодовых комбинациях. Все сферы имеют одинаковый целочисленный радиус. Будем увеличивать его, оставляя целочисленным, до тех пор, пока сферы не пересекутся. Значение этого радиуса равно числу исправляемых кодом ошибок. Этот радиус называется радиусом сферической упаковки кода. Теперь позволим этому радиусу увеличиваться до тех пор, пока каждая точка кодового пространства не окажется внутри хотя бы одной сферы. Такой радиус называется радиусом покрытия кода. Радиус упаковки и радиус покрытия кода могут совпадать. Код, для которого сферы некоторого одинакового радиуса вокруг кодовых слов, не пересекаясь, покрывают все кодовое пространство, называются совершенными. Совершенный код удовлетворяет границе Хэмминга с равенством. Код Хэмминга, имеющий длину , является совершенным.

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

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

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

Укорочение кода состоит в уменьшении длины кодовых комбинаций путем удаления лишних информационных разрядов. Если код задан порождающей матрицей, то это приводит к уменьшению обоих размеров порождающей матрицы на одно и то же число. Так, например, как упоминалось ранее, коды Хэмминга с d=3 могут быть построены с вполне определенным сочетанием n и k. Как поступить в том случае, если требуется код Хэмминга с d=3, для передачи информации достаточно k=8, а на длину кодовой комбинации наложено ограничение n<15. Для выполнения этих требований можно выбрать код Хэмминга (15,11) и прибегнуть к его укорочению. Укорочение производится за счет удаления требуемого числа лишних информационных разрядов, обычно это первые слева разряды. В образующей матрице кода (15,11) полагаются равными нулю столько столбцов слева, сколько разрядов надо удалить, после чего вычеркиваются нулевые столбцы и строки с полностью нулевыми строками единичной матрицы. Относительно проверочной матрицы операция укорочения выражается в удалении соответствующего количества первых слева столбцов, так как число строк проверочной матрицы, равное числу контрольных разрядов, остается неизменным при укорочении. Для приведенных значений k=8 и n<15 из кода (15,11) нужно удалить три лишних информационных разряда, в результате чего получится укороченный код (12,8), который также называется кодом Хэмминга.

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

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

Контрольные вопросы к лекции 10

10-1. На что указывает граница Хемминга?

10-2. На что указывает граница Плоткина?

10-3. На что указывает граница Варшамова – Гилберта?

10-4. Почему систематические линейные коды называются групповыми?

10-5. В чем состоит свойство замкнутости группы?

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

10-7. Что является особенностью группового линейного систематического кода?

10-8. Чем определяется число проверочных уравнений для группового систематического кода?

10-9. Что задает система проверочных уравнений группового систематического кода?

10-10. Какие кодовые комбинации называются образующими или базисными векторами для того или иного группового линейного кода?

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

10-12. Как формируется образующая матрица (n,k)-кода, если задана система проверочных уравнений?

10-13. Как при наличии образующей матрицы можно найти все остальные кодовые комбинации (n,k)-кода?

10-14. Из каких подматриц состоит образующая матрица (n,k)-кода?

10-15. Как может быть сформирована дополняющая матрица (n,k)-кода, если не заданы проверочные уравнения?

10-16. Как, пользуясь образующей матрицей (n,k)-кода, построить систему проверочных уравнений?

10-17. Как, пользуясь образующей матрицей (n,k)-кода, построить проверочную матрицу?

10-18. Как, пользуясь проверочной матрицей (n,k)-кода, построить систему проверочных уравнений?

10-19. Что называется синдромом?

10-20. Какое значение синдрома указывает на наличие ошибки в принятой кодовой комбинации?

10-21. Что называется исправляющим вектором?

10-22. Как можно истолковать содержимое дополняющей подматрицы, пользуясь понятием синдрома?

10-23. Как можно истолковать содержимое единичной подматрицы, пользуясь понятием синдрома?

10-24. Как осуществляется декодирование по максимуму правдоподобия?

10-25. Какие (n,k)-коды называются кодами Хэмминга?

10-26. Что называется радиусом сферической упаковки кода?

10-27. Что называется радиусом покрытия кода?

10-28. Какой код называется совершенным?

10-29. Какой код называется квазисовершенным?

10-30. Как осуществляется укорочение кода?

10-31. Как сказывается укорочение кода на размерах образующей матрицы?

10-32. Как сказывается укорочение кода на размерах проверочной матрицы?

10-33. С какой целью выполняется укорочение кода?

10-34. Как осуществляется расширение кода?

10-35. Как сказывается расширение кода на размерах образующей матрицы?

10-36. Как сказывается расширение кода на размерах проверочной матрицы?

10-37. С какой целью выполняется расширение кода?

10-38. Как образуется расширенный код Хэмминга (8,4) с d=4?

10-39. Как определяется отсутствие ошибок в принятой кодовой комбинации расширенного кода Хэмминга (8,4) с d=4?

10-40. Как определяется наличие двух ошибок в принятой кодовой комбинации расширенного кода Хэмминга (8,4) с d=4?