3.2.4. Метод случайного выбора

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

Алгоритм случайного выбора для групповых кодов был предложен Омурой [18] в 1969 г. Выполнение этого алгоритма начинается

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

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

В подразд. 3.2.4.1-3.2.4.3 мы прежде всего подробно обсудим алгоритм Омуры. Вначале рассмотрим вычислительную сложность алгоритма, единственное отличие которого от алгоритма Омуры состоит в том, что перестановки производятся без всякого привлечения информации о положении ошибок. Эту модель будем использовать в качестве стандарта, с которым будем сравнивать результаты моделирования алгоритма Омуры. Наконец, рассмотрим модификацию алгоритма Омуры, которая в некоторых случаях позволяет сократить число вычислений. Для большей конкретизации рассмотрим декодирование квадратично-вычетного -кода, исправляющего пять ошибок. Этот код особенно интересен тем, что метод перестановочного декодирования является единственным известным методом исправления всех комбинаций из пяти ошибок. В подразд. 3.2.3 отмечалось, что для покрытия всех комбинаций из пяти ошибок требуется 92 фиксированных проверочных множества. Здесь будет показано, что при декодировании данного кода среднее число просматриваемых проверочных множеств мало. Однако существуют отдельные комбинации ошибок, требующие сравнительно большого числа проверочных множеств.

3.2.4.1. Некоторые детали, относящиеся к алгоритму Омуры. Основные шаги алгоритма Омуры таковы:

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

матрица в канонической форме, отвечающая проверочному множеству

2. Вычисляем синдром и выбираем вектор ошибки для которого

Заметим, что если

то

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

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

5. Если вес вес меньше или равен поиск заканчивается. В противном случае переходим к шагу 2, используя Если после достаточно большого числа итераций вес остается большим то принимаем последний вектор в качестве вектора ошибок с минимальным весом.

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

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

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

Рассмотрим, например, -код, исправляющий две ошибки, в котором произошли ошибки в позициях 3 и 4. Тогда

Проверим столбец 1:

Проверим столбец 2:

Проверим столбец 3:

Проверим столбец 4:

(см. скан)

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

(см. скан)

Проверим столбец 2:

(см. скан)

Проверим столбец 3:

(см. скан)

Проверим столбец 4:

(см. скан)

Проверим столбец 7:

(см. скан)

Вновь ни один из вариантов выбора не является приемлемым. Следующим шагом логично было бы переставить столбцы 2 и 8. Если сделать это, то можно убедиться, что не получится комбинации ошибок меньшего веса. Для экономии места рассмотрим перестановку столбцов 4 и 8. Она дает

(см. скан)

Проверим столбец 2:

(см. скан)

Проверим столбец 4:

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

3.2.4.2. Свойства полностью случайного алгоритма декодирования. Рассматривая полностью случайный алгоритм декодирования, можно глубже понять процесс сходимости алгоритма Омуры к истинной комбинации ошибок. При таком рассмотрении случайный алгоритм является стандартом, с которым можно сравнивать поведение алгоритма Омуры. Для большей конкретности рассмотрим -код, исправляющий пять ошибок, и предположим, что вес комбинации ошибок известен и равен 5. Будем считать, что декодер работает так же, как при алгоритме Омуры, за исключением того, что при определении завершения операции декодирования используется только вес синдрома. Таким образом, вычисление градиентной функции происходит, как и раньше, однако проверяется лишь, равен ли вес 5. Если он равен 5, то производятся соответствующая перестановка и декодирование ошибки. Если он не равен 5, значение веса не принимается во внимание и осуществляется случайная перестановка столбцов.

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

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

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

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

а в частных случаях

Все остальные вероятности равны 0. Равенство вытекает из того, что декодер, попадая в состояние (в данном примере состояние 4), на следующем шаге всегда декодирует правильно. Декодер можно рассматривать как послед довательный автомат и представить диаграммой на рис. 3.8. На этом рисунке приведены также вычисленные значения начальных вероятностей и переходных вероятностей. Такой декодер может характеризоваться двумя параметрами. Один из них — среднее число итераций, необходимых для успешного декодирования, а другой — вероятность декодирования за или меньшее число итераций как

Рис. 3.8. Диаграмма состояний случайного декодера при декодировании комбинации пяти ошибок в -коде

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

где матрица переходных вероятностей

Таким образом, вероятность успешного декодирования за или меньше итераций

а среднее число необходимых для декодирования операций

Эти величины легко вычисляются с помощью График зависимости от изображен на рис. 3.9, а .

Рис. 3.9. Зависимость от вероятности не закончить декодирование за шагом для алгоритма случайного поиска

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

3.2.4.3. Модифицированный алгоритм Омуры. Существует метод, позволяющий увеличить скорость, с которой декодер находит ошибку минимального веса. Заметим прежде всего, что если решение уравнения имеющее минимальный вес, то любой другой вектор ошибки вида также будет решением при произвольном кодовом слове С. Более того, все 2 возможных решений можно записать в таком виде. Предположим, что

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

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

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

1. Начинаем с матрицы Н в канонической форме, соответствующей синдрому Соответствующим информационным множеством является а проверочным

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

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

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

и а другой лежал в множестве и не лежал в множестве Если в нет общих элементов, то выбираем произвольный элемент из Если любой элемент из I лежит в то полагаем пустым и выбираем любой элемент из

5. Используя элементарные операции над строками, порождаем новую матрицу Н, соответствующую новым информационному и проверочному множествам. Вычисляем новый синдром и переходим к шагу 3.

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

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

Улучшение, достигаемое при использовании данного алгоритма по сравнению с алгоритмом Омуры, зависит от того, насколько часто удается найти комбинацию минимального веса, которая приводит к правильному, «свободному от ошибок», множеству. Распределение числа перестановок, необходимых для декодирования большого числа комбинаций ошибок веса 5 в -коде. показано на рис. 3.10. Среднее число итераций равно примерно 16, и общий вид кривой примерно совпадает с видом кривой при случайном выборе перестановок. При использовании того же алгоритма для декодирования случайно порожденного хорошего -кода распределение числа вычислений примерно совпадает с распределением для алгоритма Омуры. Различие возникает из-за числа ближайших соседей и из-за того, что некоторые комбинации из пяти ошибок не декодируются случайным -кодом. В квадратично-вычетном коде имеется 17 196 кодовых слов веса 12. Это число достаточно велико для того, чтобы для сравнительно большой доли пятикратных ошибок существовали одна, две или три комбинации ошибок веса 7, которые могут быть найдены очень

Рис. 3.10. Зависимость от вероятности не закончить декодирование за шагов для модифицированного алгоритма Омуры (при ) и случайного алгоритма (2)

быстро, что приводит к нахождению комбинации наименьшего веса за небольшое число итераций. B заметном числе случаев истинная комбинация ошибок была найдена даже без нахождения комбинации веса 7. Хотя иногда такое событие оказывается чисто случайным, для некоторого вектора ошибок веса 5, по-видимому, нельзя найти кодовое слово веса 12, которое в сумме с этой комбинацией ошибок дает слово веса 7.

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

Методы случайного поиска являются примерами алгоритмов с переменным временем декодирования. Распределение числа итераций, показанное на рис. 3.9 и 3.10, справедливо лишь для комбинаций из пяти ошибок. Аналогичные распределения для других комбинаций ошибок можно вычислить такими же методами, и требуемый объем вычислений существенно уменьшается для комбинаций малой кратности. Можно вычислить среднее распределение числа итераций, усредняя все распределения с весами, равными вероятностям появления ошибок данной кратности (которые являются функциями вероятности ошибок в канале). В типичных случаях среднее распределение числа итераций будет существенно лучшим, чем показанное на рис. 3.9, 3.10.

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