Васюков В.Н. - Введение в ТЭС (1275345), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

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

Если информационная последовательность символов источника (возможно, после экономного кодирования) разбивается на сегменты (блоки), кодируемые независимо друг от друга, то код называется блочным (блоковым), если же информационная последовательность кодируется без разбиения, то код называют непрерывным⁶. Блочные коды, как правило, являются равномерными.

Если в кодовом слове можно выделить информационные символы, служащие для передачи сообщения, и проверочные (контрольные) символы, предназначенные только для обнаружения и исправления ошибок, такой код называют разделимым; если такое разбиение осуществить нельзя, код является неразделимым. Примерами неразделимых кодов являются так называемые коды с постоянным весом, в частности, код «3 из 7» (стандартный телеграфный код №3 [1]), а также коды на основе матриц Адамара (коды Рида-Мюллера).

Разделимые коды, в свою очередь, подразделяются на линейные и нелинейные.

В качестве примера рассмотрим один класс помехоустойчивых кодов – линейные блочные коды.

Блочный равномерный код состоит из кодовых слов (комбинаций) одинаковой длины . Элементы кодовых слов выбираются из некоторого алфавита (канальных) символов объемом . Если , код называется двоичным. Далее для простоты считается, что . Поскольку все кодовые слова имеют одинаковую длину, удобно считать их векторами, принадлежащими линейному пространству размерности . Для линейных кодов справедливо утверждение: линейная комбинация кодовых слов является кодовым словом.

Всего можно образовать -мерных векторов с двоичными компонентами (кодовых комбинаций или слов). Из них только , комбинаций являются разрешенными и составляют код, который называется -кодом (отношение называется скоростью кода). Остальные комбинации в кодере образоваться не могут (являются запрещенными), но могут получиться из разрешенных под воздействием помех в канале. Поэтому если в приёмнике имеет место запрещенная комбинация, следовательно, при передаче по каналу произошла ошибка. Разрешенные комбинации, как векторы линейного пространства, должны отстоять друг от друга достаточно далеко. Чем больше расстояние между разрешенными комбинациями, тем меньше вероятность преобразования их друг в друга под действием помех, тем выше способность кода к обнаружению ошибок. Более того, при приёме запрещенной комбинации можно не только обнаруживать, но и исправлять ошибки. Для этого декодер должен принимать решение о переданной комбинации на основе расстояния между принятой запрещенной комбинацией и ближайшей разрешенной. Таким образом, чем дальше друг от друга разрешенные комбинации, тем выше корректирующая способность кода. Алгоритм работы декодера формально сводится к разбиению всего пространства на области , , каждая из которых содержит одну разрешенную комбинацию . Если принятая комбинация принадлежит области , то декодер принимает решение о том, что передавалась разрешенная комбинация .

Для кодирования и декодирования линейных блоковых кодов применяются действия, описываемые операциями над векторами в линейном пространстве над конечным полем целых чисел [4, 5]. Сложение и умножение в конечном поле понимаются как сложение и умножение по модулю . Простейшее из таких полей, называемых полями Галуá – поле по модулю 2, обозначаемое . Сложение и умножение в этом поле описываются следующими таблицами сложения и умножения

Таблица 4 Таблица 5

Таблица сложения в поле Таблица умножения в поле

+	0	1				0	1
0	0	1			0	0	0
1	1	0			1	0	1

Мерой различия между векторами линейного пространства, как известно, может выступать некоторая функция (функционал), называемая метрикой, или расстоянием [4, 5]. В теории кодирования часто используется метрика Хэмминга, определяемая для двух двоичных кодовых векторов и выражением

.

Легко видеть, что расстояние по Хэммингу между двумя двоичными векторами равно количеству несовпадающих элементов (например, для векторов 00011100 и 11000110 расстояние равно 5).

В -мерном пространстве двоичных векторов можно определить скалярное произведение выражением , где сумма понимается как сумма по модулю 2. Если для некоторой пары векторов скалярное произведение равно 0, то векторы являются ортогональными.

Таким образом, множество всех двоичных кодовых слов длины можно рассматривать, как -мерное линейное пространство над конечным полем скаляров . Хотя это пространство содержит лишь конечное множество векторов, а именно , оно удовлетворяет всем аксиомам векторного пространства [4, 5].

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

, ,

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

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

,

где – матрица кодирования (порождающая матрица кода) вида

.

Уравнение можно рассматривать и как систему из линейных уравнений вида

, ,

где сложение понимается по модулю 2.

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

,

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

Пример 6. Систематический код (7,4) порождается матрицей

.

Кодовые слова имеют структуру , где

,

,

(подразумевается сложение по модулю 2).

Реализовать такое кодирование можно при помощи устройства, структурная схема которого приведена на рис. 3.

Устройство включает два сдвиговых регистра на 4 и 3 разряда, а также три сумматора по модулю 2. Информационная последовательность поступает на вход первого регистра и записывается в его разрядах. На выходах сумматоров по модулю 2 формируются проверочные символы, которые запоминаются в разрядах второго сдвигового регистра. Последним шагом формирования кода является считывание вначале четырех информационных символов, а затем – проверочных, при этом на выходе устройства получается семиразрядное кодовое слово. 

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

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

Любое кодовое слово -кода ортогонально любому кодовому слову -кода, следовательно,

Характеристики

Список файлов книги