ЧАСТЬ ВТОРАЯ. ОСНОВЫ ТЕОРИИ ЛИНЕЙНОГО КОДИРОВАНИЯ

ВВЕДЕНИЕ

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

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

(2.0.1)

удовлетворяющая трем аксиомам:

1. тогда и только тогда, когда (расстояние между и равно нулю тогда и только тогда, когда совпадает с ,

2.(аксиома симметрии — расстояние от до равно расстоянию от до .

3.(аксиома треугольника — сторона треугольника меньше, чем сумма двух других его сторон, или равна ей).

Применительно к задачам теории помехоустойчивого кодирования расстояние (2.0.1) желательно задать таким образом, чтобы оно находилось в определенном соответствии с особенностями стохастической матрицы трансформации сложных сигналов, а именно:

1. Если вероятность трансформации комбинации в меньше, чем вероятность , то расстояние между комбинациями и должно быть больше, чем расстояние между и .

2. Если вероятность равна вероятности , то расстояние между и должно равняться расстоянию между и .

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

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

Выберем в две произвольные комбинации:

(2.0.2)

и

(2.0.3)

где .

В теории кодирования в основном исследуется случай, когда расстояние между и находится по формуле

(2.0.4)

где функция определяет метрику пространства и задается в одном из следующих видов:

1. Метрика Хэмминга

(2.0.5)

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

2. Модульная метрика

(2.0.6)

Эта метрика при совпадает с метрикой Хэмминга и имеет ограниченное применение для каналов с амплитудной и частотной модуляциями.

3. Кольцевая метрика

(2.0.7)

Эта метрика при совпадает с метрикой Хэмминга и в какой-то мере отражает статистические особенности каналов с фазовой манипуляцией при числе градаций фазы более трех.

4. Метрика Брауна, которая используется в кодах, предназначенных для контроля за правильностью выполнения арифметических операций [67, 29, 127].

Если в формуле (2.0.4) положить (для всех ), то расстояние определит расстояние «точки» от «начала координат». Число в математике называют нормой , а в теории кодирования — весом комбинации . Наконец заметим, что независимо от вида метрики кодовым расстоянием подмножества множества называют число

(2.0.8)

где минимум разыскивается но всем расстояниям, определенным между элементами подмножества . В частности, кодовое расстояние в всегда равно единице.

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

1. Из множества выбрать заданное число М комбинаций так, чтобы кодовое расстояние d было максимально возможным.

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

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

В защиту и обоснование каждой из указанных постановок можно привести множество аргументов. Однако имеется одно весьма веское обстоятельство, которое позволяет отдать предпочтение третьей из них. Оно заключается в том, что применение для синтеза кода линейных операторов позволяет технически изящно и просто решить задачу синтеза кодирующих и декодирующих устройств. Кроме того, при некоторых несущественных ограничениях, накладываемых на основание кода для отыскания линейных операторов с нужными свойствами, можно использовать целый ряд общих идей высшей алгебры, теории чисел и некоторых других разделов математики. При таком подходе максимум числа d в значительной степени предопределен использованием для преобразований -значных комбинаций в -значные комбинации единого линейного оператора. Однако проблема простоты и надежности аппаратуры в настоящее время стоит столь остро, что с последним фактом можно не считаться. Тем более, как выяснилось, проигрыш по основным параметрам системы оказывается весьма незначительным [90-93].

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

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