§ 1.1. Пороговое декодирование линейных кодов

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

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

а. Линейные коды и проблема декодирования [8]

Нас будут интересовать в основном линейные коды в систематической форме. Множество кодовых слов такого кода есть подмножество множества всех последовательностей длины вида

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

где множество коэффициентов являющихся элементами поля полностью определяется данным кодом. (Все операции над этими символами, если не сделано специальных оговорок, выполняются в поле

Предположим теперь, что после передачи по некоторому каналу полученная последовательность отличается от переданной

«шумовой последовательностью»

где также принадлежат полю и все операции выполняются в этом поле. Тогда из (3) следует, что для определения переданной последовательности достаточно знать принятую и шумовую последовательности.

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

Пусть два кодовых слова; тогда, согласно (2), их сумма

представляет собой последовательность где

и совпадает с последовательностью, которая получится, если в качестве информационных символов выбрать Таким образом, первая групповая аксиома удовлетворена; легко проверить, что удовлетворяются и другие аксиомы.

Для линейного систематического кода, описываемого системой (2), мы всегда будем пользоваться обозначением -код.

Систему (2) можно переписать в виде

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

Мы назовем проверкой на четность сумму в (5), образованную на приемном конце, т. е.

Используя (3) и (5), проверки можно переписать в виде

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

для которых определены Общее решение системы (7) может быть сразу записано в виде

Это общее решение включает произвольных постоянных, именно значения

Рис. 2. Модель источника шума для двоичного симметричного канала.

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

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

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