4.2. АЛГЕБРАИЧЕСКОЕ ОПИСАНИЕ КОДОВ

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

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

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

Блоковый код длины словами называется линейным кодом, если его кодовые слова образуют -мерное подпространство векторного -мерного пространства Подпространство V порождается базисом из к линейно независимых векторов, которые образуют строки порождающей матрицы кода

Если матрица-строка информационного слова, то кодирование производят по правилу

где матрица-строка кодового слова кода.

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

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

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

Здесь индекс Т — символ транспонирования. Если порождающая матрица задана в форме (4.2), для выполнения условия ортогональности проверочная матрица должна иметь вид

Каждое слово линейного кода также удовлетворяет условию ортогональности

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

Синдром зависит только от вектора ошибок: Поскольку синдром

Если принятое слово принадлежит к множеству кодовых слов. При слово содержит ошибки. По значениям символов синдрома судят о конфигурации вектора ошибок. Этот принцип лежит в основе синдромного декодирования.

Для оценки обнаруживающей и исправляющей способности кода используют минимальное расстояние. Расстояние Хэмминга между словами равно числу символов, в которых они отличаются. Для вычисления расстояния между двоичными словами используют посимвольное сложение по модулю 2. Наименьшее из расстояний между любой парой кодовых слов называется минимальным расстоянием кода Минимальное расстояние линейного кода равно наименьшему весу его ненулевых кодовых слов. При декодировании ошибка может быть обнаружена, если ее кратность (количество ошибочных символов на длине блока) не превышает Ошибка с весом может быть исправлена при

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

С учетом расстояния систематические коды обозначают как Важным параметром кода является кодовая скорость Одна из проблем теории кодирования состоит в поиске кодов, которые при заданной длине блока и кодовой скорости обеспечивают наибольшее расстояние Пределы этих параметров определяются кодовыми границами, сведения о которых можно найти в [74—76].

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

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

вправо. Свойства ЦК удобно изучать, представляя кодовые слова в виде многочленов по степеням формальной переменной коэффициенты которых — символы кодового блока Сложение многочленов производится поэлементно и коэффициенты при одинаковых степенях складывают по модулю 2, а умножение — по модулю многочлена этом случае все возможные многочлены степени и меньше образуют алгебраическое кольцо многочленов

Для построения циклического кода в кольце выбирают подмножество многочленов — идеал Многочлен минимальной степени в этом подмножестве называется порождающим многочленом Все многочлены идеала У, соответствующие кодовым словам делятся на без остатка и правило кодирования имеет вид

Если степень многочлена и равна к степень не превышает то степень порождающего многочлена не превышает Вводят понятие проверочного многочлена

степень которого не превышает

Как и любой линейный код, ЦК представляют порождающей и проверочной матрицами. Первые сдвигов порождающего многочлена образуют линейно независимые строки порождающей матрицы ЦК в несистематической форме:

Используя условие ортогональности матриц (4.3), можно показать, что проверочная матрица

т. e. коэффициенты многочлена представлены в строках матрицы Н в обратном порядке.

Свойство делимости кодовых слов ЦК на порождающий многочлен используют для обнаружения ошибок в принятых

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

Здесь многочлен синдрома, остаток от деления на Он имеет степень не выше отсутствие ошибок