11.3. Алгоритмы декодирования Рида

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

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

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

Исходя из этих соображений, Галлагер провел интересное исследование. Используя случайные коды аналогично тому, как это делалось в разд. 4.4, он показал, что существуют коды, совпадающие с нулевым пространством матриц, в столбцах которых низка плотность единиц, причем вероятности ошибки для этих кодов ненамного больше, чем вероятности ошибки, получаемые для произвольных кодов при случайном кодировании. Он описал способ декодирования, являющийся усовершенствованием алгоритма декодирования Рида. Наконец, он наглядно показал осуществимость этих методов, промоделировав на вычислительной машине процесс исправления ошибок для кодов со случайно выбираемыми проверочными соотношениями, достигающими длины 500 символов. Оказалось, что для кодов такой длины при скорости передачи, равной можно исправлять типичные комбинации, содержащие до 40 ошибок, а при скорости передачи, равной можно исправлять комбинации, содержащие около 80 ошибок. Тот факт, что такие большие комбинации ошибок могут быть исправлены в течение не очень большого промежутка времени, действительно весьма удивителен и указывает на то, что эти методы могут оказаться практически применимыми.

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

Параметры этих двух кодов следующие. Случай I:

Случай II:

Каждый из этих кодов — циклический код, порождаемый вектором с. В первом случае образуется 8 классов смежных классов, а во втором — 56. Результаты анализа [631 классов смежных классов сведены в табл. 11.2; аналогичная таблица приводится в работе [64] для -кода. Число в таблице обозначает номер компоненты вектора которая равна

Таблица 11.2 (см. скан) Типы смежных классов для -кода

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

1. Вычислить

2. Вычислить где если если

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

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

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

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

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

Вектор для вектора равен

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

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

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