5.3. ДЕКОДИРОВАНИЕ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ ПО ЕВКЛИДОВУ РАССТОЯНИЮ

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

нованных на декодировании внешних кодов с исправлением ошибок и стираний или только ошибок, так как последние имеют полиномиальный характер роста сложности от длины кода.

Наиболее естественным и простым является алгоритм декодирования СКК с приемом в целом внутренних сигналов и исправлением ошибок внешними кодами. Легко убедиться, что принятое слово будет декодировано правильно, если квадрат расстояния между переданным и принятым словами удовлетворяет неравенству

причем это справедливо как для CKKI, так и для CKKII.

Однако помехоустойчивости жесткого декодирования внешних кодов может оказаться недостаточно, и интерес представляют мягкие алгоритмы декодирования. Как и в случае кодов, возможны различные алгоритмы декодирования внутренним кодом (приема сигналов) [19, 85]. Здесь рассмотрим алгоритм, аналогичный алгоритму декодирования кодов по минимуму обобщенного расстояния [50]. Такой алгоритм для двоичных обобщенных каскадных кодов над хэмминговым пространством изложен в Здесь он будет называться алгоритмом по минимуму евклидова расстояния

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

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

Обозначим через число стираний в векторе Определим декодирование внешнего кода заключающееся в том, что с исправлением ошибок и стираний декодируется вектор

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

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

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

Пусть на шаге алгоритма известны векторы а значит известны и подблоки

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

В результате всех декодирований получаем вектор набор чисел (считаем,

что они упорядочены по убыванию) и векторов

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

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

При декодировании внутреннего кода для нас существенно понятие правильного декодирования

Определение 5.1. Пусть истинный вектор, принятый вектор, а — результат декодирования Тогда скажем, что правильное декодирование, если

В противном случае скажем, что неправильное декодирование.

Каждому вектору апоставим в соответствие число вычисляемое по (5 6), где

Далее алгоритм Чмер ничем не отличается от Чмер. В общем виде независимо от типа конструкции (I или II) алгоритм декодирования будем называть Чмер. Теперь рассмотрим его корректирующие способности.

Утверждение 5.1. Пусть передавалось слово у, а принято слово у. Пусть первые векторов кодов найдены правильно. Тогда если выполняется неравенство

то при использовании алгоритма Чмер строка будет декодирована правильно.

Доказательство утверждения приводится в [19, 85].

Следствие 5.1. Пусть передавалось слово а принято слово у. Декодирование по алгоритму Чер будет правильным, если, квадрат расстояния между переданным и принятым словами удовлетворяет неравенству

Рис. 5.5 Иллюстрация декодирования по алгоритму

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

Пример 5.2 Пусть имеется при с внутренним ансамблем сигналов КАМ16 и внешним корректирующим кодом РМ ( Проиллюстрируем работу алгоритма с Параметры Эта СКК соответствует вектору разбиений и в данном случае не является оптимальной (возможна с вектором разбиений Но данная СКК выбрана потому, что у нее и можно проиллюстрировать все сложности алгоритма

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

В результате декодирования внутренними кодами в алгоритме с реализацией евклидова расстояния получаем и числа

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