Систематические линейные блочные коды с контролем четности

Н.Н. Ташатов

Евразийский национальный университет им. Л.Н. Гумилева, г. Астана

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

Мақалада құрылымдық тізбекті каналдық кодтау қарастырылады, соның ішінде сызықтық блоктық код (n, k). Бұл код n-өлшемді кодтық сөздегі k-өлшемді хабарлау векторын көрсетеді, онда тізбектің генерацияланатын бөлігі хабарлаудың k символымен біріктіріледі, ал алған (n - k) бит – жұптылық биті. Артылған разрядтар деректеріне қосу, қатенің анықталған модельдерін табу және/немесе түзету мүмкіншілігін береді.
The structured sequences of channel coding, exactly a regular linear block code (n, k) are considered in the article. This code displays a k-dimensional vector of the message in a n-dimensional code word in which the part of generated sequence is combined with k symbols of the message, and the others (n-k) bats are the bats of parity. The addition to the data of superfluous categories allows to find out and-or correct the certain models of a mistake.
Линейные блочные коды – это класс кодов с контролем четности, которые описываются парой чисел (n, k). Блок из k символов сообщения назовем вектором сообщения, а блок из n символов кодового слова - кодовым вектором. В процессе кодирования блок из k символов сообщения преобразуется в больший блок из n символов кодового слова, образованного с использованием элементов данного алфавита. Если алфавит состоит только из двух элементов 0 и 1, код является двоичным и включает двоичные разряды, т.е. биты.

Набор из 2^k последовательностей сообщения, которые формируются из k - битовые сообщений, называется k –кортежами, или последовательностями k цифр, а из 2ⁿ последовательности могут формироваться n - битовые блоки, которые называются п–кортежами. Процедура кодирования сопоставляет с каждым из 2^k k –кортежей сообщения один из 2ⁿ п–кортежей. Блочные коды представляют собой взаимно однозначное соответствие, отсюда следует, что 2^k k –кортежей сообщения однозначно отображаются во множество из 2ⁿ п–кортежей ко­довых слов. Отображение производится согласно таблице соответствия. Для линейных кодов преобразование отображения является также линейным [1].

Здесь Р – массив четности, входящий в матрицу генератора, р_ij принимает 0 или 1, а I_k – единичная матрица размерностью k k. При использовании этого систематического генератора процесс кодирования еще больше упрощается, поскольку нет необходимости хранить ту часть массива, где находится единичная матрица. Например, в (6, 3) - коде проверочная матрица имеет следующий вид:

где

Для данного k –кортежа сообщения т = т₁, т₂, ... , т_k, k –кортежа кодовых векторов U = u₁, u₂, … , u_k, систематический кодовый вектор можно записать в следующем виде:

где

Например, для кода (6, 3) кодовое слово выглядит следующим образом:

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

или

Произведение UH^T любого кодового слова U, генерируемого с помощью матриц G и H^T, дает нулевую матрицу:

где биты четности p₁, p₂, … , p_n-k определены в уравнении (4).

Таким образом, поскольку проверочная матрица Н создана так, чтобы удовлетворять условиям ортогональности, она позволяет проверять принятые векторы на предмет их принадлежности заданному набору кодовых слов. Множество U будет кодовым словом, генерируемым матрицей G, тогда и только тогда, когда (9) равен 0.

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

Пусть r = r₁, r₂, … , r_n – принятый вектор, т.е. один из 2ⁿ п–кортежей, полученный после передачи U = u₁, u₂, … , и_п, т.е. один из 2^k п–кортежей. Тогда r можно представить в сле­дующем виде:

Здесь е = е₁, е₂, ... , е_п – вектор ошибки или модель ошибки, внесенная каналом. Всего в пространстве из 2ⁿ п–кортежей существует 2ⁿ – 1 возможных ненулевых моделях ошибки. Синдром сигнала r определяется следующим образом:

Синдром – это результат проверки четности, выполняемой над сигналом r для определения его принадлежности заданному набору кодовых слов. При положительном результате проверки синдром S = 0. Пусть r содержит ошибки, которые можно исправить. Тогда синдром имеет определенное ненулевое значение, что позволяет отметить конкретную модель ошибки. Декодер, в зависимости от того, использует автоматический запрос повторной передачи ARQ или производит ли он прямое исправление ошибок, посылает запрос на повторную передачу ARQ или участвует в локализации и исправлении ошибки, т.е. производит прямое исправление ошибок. Используя уравнения (10) и (11), а также в силу линейности и ортогональности кодов, представим синдром r следующим образом:

Для всех элементов набора кодовых слов U Н^T = 0. Поэтому

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

Отметим два необходимых свойства проверочной матрицы.

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

1. 
   оно является кодовым словом,
   
2. 
   может рассматриваться как модель ошибки е₁, т.е. комбинация, означающая отсутствие ошибки.
   

В пространстве V_n матрица содержит все 2ⁿ п–кортежей. Каждый п–кортеж упомянут только один раз, причем ни один не пропущен и не продублирован. Каждый класс смежности содержит 2^k п–кортежей. Следовательно, всего классов смежности будет .

Алгоритм декодирования предусматривает замену искаженного вектора, т.е. любого п–кортежа, за исключением указанного в первой строке, правильным кодовым словом, ука­занным вверху столбца, содержащего искаженный вектор. Предположим, что по каналу с помехами передано кодовое сло­во U_i ( i = 1, ... , 2^k), в результате чего принят искаженный вектор U_i + е_j. Если созданная каналом модель ошибки е_j является образующим элементом класса смежности с индексом j = 1, … , 2^n-k, принятый вектор будет правильно декодирован в переданное кодовое слово U_i. Декодирование даст ошибочный результат, если модель ошибки не является образующим элементом класса.

Синдром класса смежности. Название класс смежности (или сомножество) – это сокращение от «множество чисел, имеющих совместные свойства».

Пусть е_j является образующим элементом класса смежности или моделью ошибки j-го класса смежности, тогда вектор U_i + е_j является п–кортежем в этом классе смежности. Синдром этого п–кортежа запишем в следующем виде:

Так как U_i вектор кода и U_i Н^T = 0, то, как и в уравнении (13), можно записать:

Из уравнения (16) видно, что каждый член класса смежности имеет один и тот же синдром. Синдром каждого клас­са смежности отличается от синдромов других классов смежности; именно этот синдром используется для определения модели ошибки.

1. 
   Синдром r вычисляется с помощью уравнения S = rН^T .
   
2. 
   Определяются образующие элементы класса смежности (модели ошибки) е_j, син­дром которых равен rН^T.
   
3. 
   Предполагается, что модели ошибки вызываются искажениями в канале.
   
4. 
   Полученный исправленный вектор, или кодовое слово, определяется как U = r + е_j.
   

Рисунок 1 Нормальная матрица для кода (6, 3)

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

S = е_j

Результаты вычисления приводятся в таблице 1.

Модель ошибки	Синдром
000000	000
000001	101
000010	011
000100	110
001000	001
010000	010
100000	100
010001	111

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

Используя таблицу 1 соответствия синдромов, находим соответствующую модель ошибки, которая является оценкой ошибки. Обозначим ее через ê. Затем декодер прибавляет ê к r и оценивает переданное кодовое слово Û .

Û = r + ê = (U + e) + ê = U + (e + ê ). (17)

Если ê = е, т.е. правильно вычислили ошибку, тогда оценка Û совпадает с переданным ко­довым словом U, а с другой стороны, если оценка ошибки неверна, ê е, то декодер неверно определит переданное кодовое слово и мы получим необнаружимую ошибку декодирования.

1. 
   Скляр Б. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр. : Пер. с англ. – Издательский дом «Вильямс», 2004. – 1104 с. ил.
   
2. 
   Березюк Н.Т., Андрущенко А.Г., Мощицкий С.С. Кодирование информации (двоичные коды). Харьков, издательское объединение «Вища школа», 1978, 252 с.
   
3. 
   Lin S. and Costello D.J. Jr. Error Control Coding: Fundamentals and Applications. Prentice-Hall, Inc., Englewood Cliffs, N. J., 1983.