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



жүктеу 136.18 Kb.
Дата12.08.2018
өлшемі136.18 Kb.

// Вестник ПГУ им. С.М. Торайгырова. – 2007. – № 1. – С.123-135
УДК 681.3.07
Систематические линейные блочные коды

с контролем четности

Н.Н. Ташатов

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

В статье рассматриваются структурированные последовательности канального кодирования, а именно систематический линейный блочный код (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, код является двоичным и включает двоичные разряды, т.е. биты.

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



Систематические линейные блочные коды. Систематический линейный блочный код (n, k) - это такое отображение k - мерного вектора сообщения в n - мерное кодовое слово, в котором часть генерируемой последовательности совмещается с k символами сообщения. Остальные (nk) бит – это биты четности. Порождающая матрица генератора систематического линейного блочного кода имеет следующий вид [1]:
G = . (1)

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



G = , (2)
где V1, V2 и V3 — три линейно независимых вектора, подмножество восьми кодовых векторов, которые могут сгенерировать все кодовые векторы. Объединяя выраже­ния (1) и (2), получим каждое кодовое слово в следующем виде:


,

где


Для данного kкортежа сообщения т = т1, т2, ... , тk, kкортежа кодовых векторов U = u1, u2, … , uk, систематический кодовый вектор можно записать в следующем виде:



, (3)

где


. (4)

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



(5)

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



Проверочная матрица. Чтобы декодировать полученные вектора, определим матрицу Н, которая называется проверочной. Для каждой порождающей матрицы G существует матрица Н размером (пk)п, такая, что строки матрицы G ортогональны к строкам матрицы Н, т.е. GHT = 0, где HT транспонированная матрица Н, а 0 нулевая матрица размерностью k (пk). Размерность матрицы HT равна п (пk). Чтобы матрица Н удовлетворяла требованиям ортогональности систематического кода, ее компоненты записываются в следующем виде [1], [2]:

Н = (In-k PT). (6)
Тогда матрица HT имеет вид:

HT = (7)

или


HT = . (8)

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



UHT = p1 + p1, p2 + p2, … , pn-k + pn-k = 0, (9)

где биты четности p1, p2, … , pn-k определены в уравнении (4).

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

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

Пусть r = r1, r2, … , rn – принятый вектор, т.е. один из 2n пкортежей, полученный после передачи U = u1, u2, … , ип, т.е. один из 2k пкортежей. Тогда r можно представить в сле­дующем виде:



r = U + е. (10)

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



S = rНT. (11)

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



S = rНT = (U + е) НT = U НT + е НT . (12)

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



S = е НT. (13)

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

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


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

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

Исправление ошибок. Пусть мы обнаружили отдельную ошибку. Тогда контроль с помощью синдромов, выполняемый как на искаженном кодовом слове, так и на соответствующей модели ошибки, дает один и тот же синдром. Этот момент является клю­чевым, поскольку мы имеем возможность не только определить ошибку, но и исправить подобные модели ошибки, т.к. существует взаимно однозначное соответствие между исправимой моделью ошибки и синдромом. Расположим 2n пкортежей, которые представляют собой возможные принимаемые векторы, в нормальной матрице, чтобы первый ряд содержал все кодовые слова, начиная с кодового слова с одними нулями, а первый столбец все исправимые модели ошибки. Заметим, что основным свойством линейного кода является то, что в набор кодовых слов включен вектор, состоящий из одних нулей. Каждая строка сформированной матрицы, именуемая классом смежности, состоит из модели ошибки в первом столбце, называемой образующим элементом класса смежности, за которой следуют кодовые слова, подвергающиеся воздействию этой модели ошибки. Нормальная матрица для кода (n, k) имеет следующий вид:

. (14)
Кодовое слово U1 - это кодовое слово со всеми нулями играет две роли:

  1. оно является кодовым словом,

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

Отсюда r = U.

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

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

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

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



S = rНT = (Ui + еj) НT = Ui НT + еj НT. (15)

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



S = rНT = (Ui + еj) НT = еj НT. (16)

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



Декодирование с исправлением ошибок. Процедура декодирования с исправлением ошибок состоит из следующих этапов.

  1. Синдром r вычисляется с помощью уравнения S = rНT .

  2. Определяются образующие элементы класса смежности (модели ошибки) еj, син­дром которых равен rНT.

  3. Предполагается, что модели ошибки вызываются искажениями в канале.

  4. Полученный исправленный вектор, или кодовое слово, определяется как U = r + еj.

Локализация модели ошибки. Рассмотрим линейный блочный код (6, 3). Составим матрицу из 26 = шести­десяти четырех 6-кортежей, как это показано на рисунке 1. Восемь векторов в первой строке – это правильные кодовые слова, а семь ненулевых образующих элементов классов смежности в первом столбце – это исправимые модели ошибки. Все однобитовые модели ошибки являются исправимыми. Отметим, что после того, как исправляются все однобитовые модели ошибки, еще остаются некоторые возможности для исправления ошибок, поскольку еще не все шестьдесят четыре 6-кортежа учтены. Имеется один образующий элемент класса смежности, с которым ничего не сопоставлено, а значит, остается возможность исправления еще одной модели ошибки. Эту модель ошибки можно выбрать произвольным образом. На рисунке 1 эта последняя исправимая модель ошибки выбрана равной ком­бинации с двумя ошибочными битами 010001. Декодирование будет правильным тогда и только тогда, когда модель ошибки, введенная каналом, будет одним из образующих элементов классов смежности.

000000

110100

011010

101110

101001

011101

110011

000111

000001

110101

011011

101111

101000

011100

110010

000110

000010

110110

011000

101100

101011

011111

110001

000101

000100

110000

011110

101010

101101

011001

110111

000011

001000

111100

010010

100110

100001

010101

111011

001111

010000

100100

001010

111110

111001

001101

100011

010111

100000

010100

111010

001110

001001

111101

010011

100111

010001

100101

001011

111111

111000

001100

100010

010110

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

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

S = еj

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



Таблица 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.


Достарыңызбен бөлісу:


©kzref.org 2017
әкімшілігінің қараңыз

    Басты бет