Асимптотическая оценка процедуры неалгебраического декодирования избыточных кодов

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

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

Известно, что в канале с гауссовским шумом при E b / N 0 ^ да , где E b - энергия сигнала, приходящаяся на бит, N 0 – спектральная плотность гауссовского шума, в случае жестких решений энергетический выигрыш оценивается выражением D h = 10 lg ( R ( t + 1 )) дБ, а при реализации мягкого декодирования определяется соотношением D s = 10lg ⁽ Rd _min ) дБ. В приведенных формулах: R = k / n - скорость кода, где к - число информационных символов в кодовом векторе длины n , t – число, исправляемых кодом ошибок, а d _min — метрика Хэмминга [2-3]. Отсюда следует, что при E _b / N ₀ → ∞ асимптотический выигрыш в случае мягкого декодирования оказывается примерно в два раза выше (на 3 дБ), чем при жестких решениях.

Минимальное расстояние (в смысле метрики Хэмминга) для ( n , к ) - кода над полем GF ( q ) не может превосходить значения n - к + 1, поскольку существуют кодовые слова с одним только ненулевым информационным символом. Коды, для которых d _min = n - k + 1 , получили название максимально разнесенных кодов.

Известно, что нетривиальных двоичных максимально разнесенных кодов не существует, но есть нетривиальные недвоичные коды, к которым в первую очередь следует отнести коды Рида-Соломона (РС) [4]. Именно применение кодов РС на внешней ступени декодирования позволило реализовать замечательные возможности обобщенного каскадного кодирования. Очевидно, что повышение возможностей внутреннего двоичного кода в указанной схеме кодирования (например, декодирование такого кода по принципу максимально разнесенного кода) позволило бы получить некоторый дополнительный выигрыш.

Естественно, что поиск таких методов не должен связываться с метрикой Хэмминга. Подобная задача решается в [5] методом введения ранговой метрики. В данной работе рассматривается способ представления двоичных векторов в формате параллельных групп (кластеров) и уникальных координат каждого вектора в двумерном евкли- довом пространстве в декартовой системе координат [6-7].

Описание метода

Пусть задан двоичный циклический ( n , к ) код с порождающим полиномом вида

g(x) = an-kxn—k + an-k-ixn—k-1 + - + ao , где ai - коэффициенты из GF (2) .

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

b={o, Big,..., Big, b™ ..., Bih ,1}, здесь через Big обозначены представители прямого кода, задаваемые полиномом g(x), а через Bih показаны представители дуального кода, формируемого порождающим полиномом по схеме g(x) = g(x) = h(x).

Назначим произвольно f номеров ( 0 ≤ f ≤ k ) двоичных символов для всего разрешенного множества кодовых комбинаций, которые будут определять признак группы комбинаций (кластера). Тогда число комбинаций такого кода, входящих в кластер одного признака, определяется соотношением 2 ^{k -} f . При f = 0 все кодовые векторы входят в один кластер (система обычного алгебраического декодирования). При выборе f ^ 0 образуется совокупность 2 ^f кластеров.

Из любого циклического кода путем линейных преобразований над строками порождающей матрицы G ( n , к ) - кода можно образовать систематический код с матрицей G = [ I _k : P], порождающей тот же код. В единичной матрице I _k при f <  к матрицы G всегда можно выделить единичную матрицу меньшей размерности I _f . Путем линейных преобразований над строками матрицы I _f , можно получить двоичное поле Галуа степени расширения f , при этом комбинации поля GF (2 f ) будут определять признак кластера или его номер. Поле GF (2 f ) содержится в поле GF (2 k ) ровно 2 k^-f раз, следовательно, число кодовых комбинаций в одном кластере будет определяться этим же соотношением. При f = к число кластеров равно числу разрешенных кодовых комбинаций, то есть в кластер входит только одна кодовая комбинация.

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

Пусть для кода БЧХ (15,5) при f = 3 признак кластера для всего множества разрешенных век- 210

торов определяется разрядами x ; x ; x , а оставшиеся разряды, разбитые на две части, определяют координаты векторов X и Y на плоскости кластера. Если в качестве признака кластера в новых условиях выбрать разряды x ¹⁴ ; x ¹³ ; x ¹² или x ⁷ ; x ⁶ ; x ⁵ , то координаты векторов кластеров не претерпят никаких изменений. Указанный признак следует из циклических свойств кода.

Комбинация кода, содержащая g ( x ) и входящая в G′ , на местах старших разрядов должна содержать k - 1 нулевых символов. Не теряя общности рассуждений предположим, что f = к -1. Тогда номер кластера по первым f разрядам для рассматриваемой комбинации в двоичной системе счисления будет иметь вид g 1 f = ( 0 0 0 0 ) 2 .

Выполним циклический сдвиг данной кодовой комбинации на один двоичный символ влево и вновь, выделяя f разрядов, получим номер кластера в двоичной системе счисления вида g 2 f = (0 0 0 a n - k x ^{n -k} )₂.

Затем g 3 f = (0 0 a n - k x n - k a n - k - , x n - k ^{- 1} ) 2 и далее до завершения всего цикла.

Таким образом, номера кластеров будут упорядочены в соответствии с особенностями распределения единичных и нулевых коэффициентов ai в порождающем полиноме g(x). В окончательном виде результат может быть представлен детерминированной для выбранных f и g(x) последовательностью чисел g1f   g2f g3f g4f … gnf .

Назовем полученную на основе комбинации порождающего полинома последовательность номеров кластеров базовой и обозначим ее как {gif } где i пробегает значения от 1 до n. Циклическое смещение на один шаг номеров базовой последовательности кластеров приведет к новой комбинации кластеров, принадлежащей данному коду. Она примет вид:

g2 _f g 3 _f g4 _f … gn _f g1 _f .

Предположим, что группа векторов веса B1g определят общеечислокодовых векторовданного веса, а другие представители весов прямого кода отсутствуют. Исключим из дальнейшего анализа чисто нулевой вектор, который при любом сочетании из f разрядов определяет номер нулевого кластера, а так же единичный элемент группы, который при любом сочетании из f разрядов однозначно обеспечивает получение кластера с номером 2 f - 1 . Циклические сдвиги вектора веса B1g приведет к образованию n циклически сдвинутых последовательностей номеров кластеров представителя данного веса.

В комбинациях производных от полинома g(x) будет ровно 2f-1 одинаковых номеров клас- теров, а другая половина кластеров с таким же номером будет в составе комбинаций, образованных от циклических трансформаций порождающего полинома дуального кода h(x).

Рассмотрим порождающий полином кода БЧХ (15, 5), заданный в формате 24678. Определим f = 3 и выделим три бита указанной кодовой комбинации, находящиеся в левых разрядах. Тогда получим значение g1 f = 0002. Значение g2 f после смещения на один разряд вправо принима- ет вид g2 f = 0002. Представляя подобным обра- зом другие значения

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

{0 0 1 2 5 2 4 1 3 6 5 3 7 6 4}.     (1)

Важным свойством (1), как было отмечено выше, является строгая зависимость в смене номеров кластеров, зависящая только от структуры порождающего полинома g (x).

Аналогичную последовательность следует получить и для дуального кода, вытекающую из особенностей образования h ( x ) . При этом номера кластеров определяются по модулю числа 2 ^f - 1 , то есть

{7 7 6 5 2 5 3 6 4 1 2 4 0 1 3}. (2)

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

Например, если в канонической системе обмена данными номера кластеров определялись последними правыми разрядами, а надежно приняты позиции последовательности (1), принадлежащие кластеру 6 и находящемуся между 3 и 5 кластерами (выделено жирным), то, выполнив пять шагов вправо, декодер устанавливает, что это был кластер 4. Следовательно, после нахождения кластера группа комбинаций, принадлежащих данному кластеру, устанавливается сразу, а не по алгоритму последовательного анализа комбинация за комбинацией, как это осуществляется при классическом списочном декодировании. Это способствует снижению сложности декодера и повышает скорость обработки данных в разнообразных системах памяти современной вычислительной техники.

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

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

Рассмотрим алгоритм декодирования принятой кодовой комбинации циклического кода по идентификации номера кластера.

Шаг 1. Декодер по мягким решениям определяет k наиболее надежных позиций в принятом кодовом векторе.

Шаг 2. Определяется группа подряд идущих надежных позиций. Если такая группа существует, то декодер приступает к поиску номера кластера, выполняя шаг 4. Если надежные символы следуют в разбивку, декодер выполняет шаг 3.

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

Шаг 4. Используя циклические сдвиги g ( x ) и h ( x ) в кластерном представлении, декодер определяет номер кластера и старшие разряды координат принятого кодового вектора. Декодирование завершается.

Оценка полученных результатов

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

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

В общем случае для двоичных разрядов координат X и Y вес старшего разряда равен 2 ^α-1 . Новая метрика в форме прямоугольной защитной зоны при 2 k^-f = 4 будет определяться уравнени- 2 α -1

-1.

При этом искажение младших разрядов координат кодового вектора не приводит к выходу вектора за пределы защитной зоны. Нарушение защитной зоны произойдет только при искажении старшего разряда любой координаты. Например, для кода (15, 5) целесообразно выбрать f = 3, тогда выполняя поиск номера кластера, декодер в циклической последовательности {gi f } или {hi f } проверяет два следующих номера, например, в {gi f } 6; 5; 2 и точно определяет не только номер кластера, но и выявляет переданный информационный вектор. В совокупности номер кластера и старшие разряды координат образуют ровно k символов. Следовательно, код способен в системе мягкого декодирования восстановить n - k стираний.

При таком подходе асимптотическая эффективность декодера может быть оценена по формуле D_ra = 10lgT?(n - k + 1)дБ , которая демонс -трирует отсутствие какого-либо энергетического выигрыша при передаче безызбыточных сообщений, когда = 1 , то есть n = k .

Асимптотическая оценка энергетического выигрыша представленного способа для кодов БЧХ указывает на возможность получения дополнительного выигрыша до 3 дБ даже по отношению к мягкому декодеру.

Выводы

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

Работа поддержана грантом РФФИ 09-0797001.