БЛОЧНО-ВЕКТОРНЫЕ АЛГЕБРАИЧЕСКИЕ КОДЫ

ВВЕДЕНИЕ

В современных системах для более достоверной передачи информации используются различные виды помехоустойчивого кодирования, которые можно разделить на два больших класса: блочные и непрерывные. Сама идея помехоустойчивого кодирования заключается во введении умеренной избыточности в передаваемый цифровой поток. Вводимая избыточность делает возможным обнаружение и исправление ошибок, возникающих из-за влияния помех [2, с. 9].

В данной статье предлагается рассмотреть альтернативную - векторную реализацию кода Хэмминга – кода (7, 4). Код Хэмминга является разновидностью блочных кодов: в скалярной реализации кодирование происходит блоками, состоящих из четырёх бит. В процессе кодирования передаваемый 4-х битовый блок превращается в 7-ми битовый путём введения трёх избыточных бит. Избыточность такого кода составляет 3/4.

В рассматриваемом векторном варианте реализации кода рассматриваемый бит был заменён символом (вектором), состоящим из 3-х бит (составляющих вектора).

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

ВЕКТОРНАЯ РЕАЛИЗАЦИЯ КОДЕКА

Структура реализованного векторного кодека подобна структуре классического кодека. Главным их отличием является то, что вместо битов используются символы (векторы). В результате такого преобразования возрастает число информационных битов, а так же размер кодового символа. Структурная схема векторного кодера представлена на рисунке 1.

Рисунок 1. Структурная схема векторного кодера

Опишем принцип работы блочно-векторного кодера. Т.к. кодирование является блочным, то весь информационный поток разделяется на блоки. С помощью демультиплексора происходит формирование 3-х битовых символов. Далее с помощью операции сложения по модулю 2 определённых информационных символов (i) происходит образование проверочных символов (r), так же состоящих из 3-х битов. Данной схеме соответствуют следующие проверочные выражения [3, с. 52]:

Процесс кодирования осуществляется с помощью генерирующей матрицы G, которая имеют структуру [1, с. 7]:

где  I_kxk – единичный блок; I_kx(n-k) – проверочный блок.

Приведённая выше генерирующая матрица G соответствует систематическому коду [3, с. 57]. На выходе кодера 4 символа превращаются в 7 символов по 3 бита.

В рассматриваемом кодеке для декодирования принятых символов используется синдромный способ декодирования. Структурная схема декодера представлена на рисунке 2.

Рисунок 2. Структурная схема декодера

Принятая последовательность на входе декодера представляет собой сумму по модулю 2 переданных кодовых символов и вектора ошибок:

,                                                                    (1)

где  – принятая последовательность;  – переданная последовательность;  – вектор ошибок.

В основе синдромного способа декодирования лежит вычисление контрольного вектора – синдрома. Синдром является нулевым, если кодовая комбинация была принята без ошибок и, соответственно, синдром отличен от 0, если ошибки произошли. В двоичных кодах вычисленный синдром укажет не только на наличие ошибки в принятой комбинации, но и на место её возникновения, поэтому по вычисленному синдрому можно определить вектор ошибки и произвести их исправление [3, с. 62].

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

Т.к. используемый код является двоичным, то для исправления ошибки достаточно знать место её возникновения (ведь символ может принимать лишь одно из двух значений: 0 или 1).

Сам процесс декодирования происходит с использованием проверочной матрицы H, структура которой определяется из условия ортогональности порождающей и проверочной матриц [1, с. 7]:

                                                                 (2)

Тогда матрица Н будет иметь следующую структуру:

Для нахождения синдрома необходимо принятую кодовую комбинацию умножить на транспонированную проверочную матрицу Н^Т.

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

ПРИМЕР ИСПОЛЬЗОВАНИЯ ВЕКТОРНОГО КОДЕКА

Допустим, что передавались следующие 4 трёх битовых символа:

Запишем соответствующие генерирующую и проверочную матрицы:

Произведём кодирование, используя генерирующую матрицу:

В результате получим 7 трёх битовых символов.

Допустим, что при приёме ошибок не произошло. Произведём декодирование:

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

Соответственно, вектор ошибки имеет вид:

ВЫВОДЫ

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

В модели исследования были использованы 2 детектора ошибок: один из них показывает число ошибок, возникающих в тракте передачи, а второй – число ошибок после декодера. Их применение показало, что примерно на 50 ошибок канала передачи, приходится одна ошибка декодера.

Использование кодека дало энергетический выигрыш ~3,45 дБ по сравнению с системой без кодирования.

Модельный эксперимент показал, что энергетический выигрыш векторного кодирования по сравнению со скалярным незначительный и находится в пределах погрешности. Предполагается проведение дополнительного эксперимента с модемом на основе 8PSK, когда появление кратных ошибок более вероятно.

Исправляющая способность кода характеризуется числом разных синдромов. Общее число синдромов, которое может быть получено составляет 2⁹=512. Этими синдромами покрываются все однократные ошибки (12 ошибок), 68,2 % двух кратных и 56,2 % трёхкратных.

Список литературы:

1. Кологривов В.А., Алишери А.А. Помехоустойчивое кодирование и синдромное декодирование блоковых кодов [Электронный ресурс]: Учебно-методическое пособие. – Томск: ТУСУР, 2018. – 21 с. Режим доступа: https://edu.tusur.ru/publications/7541.
2. Королёв А.И. Коды и устройства помехоустойчивого кодирования информации. – Минск, 2002. –286 с.
3. Лузин В.И., Никитин Н.П., Гадзиковский В.И. Основы формирования, передачи и приёма цифровой информации. – М.: СОЛОН-Пресс, 2014. – 316 с.