4.5. Декодирование циклических кодов на основе кластерного подхода

Циклические коды нашли широкое применение в современных системах обмена данными. Особенно удачно эти коды используются для оценки достоверности информации  размещенных в заголовках пакетов данных.  Применение циклических кодов в современных технологиях представлено в табл. 4.10.

Табл.4.10 Сведения о циклических кодах современных технологий обмена данными

Тип циклического кода	Порождающий многочлен	Тип технологии
CRC-4		ISDN
CRC-8		ATM
CRC-12		IBM
CRC-16		IBM
CRC-16		HDLC  и  LAPD
CRC-32		HDLC

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

,

где  – коэффициенты из .

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

,

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

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

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

Следует отметить важное для декодера свойство: при  разбиении пространства кодовых векторов  двоичного циклического кода на кластеры  значения координат кодовых векторов остаются неизменными в пределах каждого кластера при условии, что сохраняется заданная конфигурация следования номеров символов, определяющих признак кластера. Пусть для кода БЧХ (15,5) при  признак кластера определяется разрядами , а оставшиеся разряды, разбитые на две части, определяют координаты векторов  на плоскости кластера. Если в качестве признака кластера в новых условиях выбрать разряды  или , то координаты векторов кластеров не претерпят никаких изменений.  Указанный признак следует из свойств цикличности кода.

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

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

и далее до завершения цикла.

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

            …   .

Назовем полученную на основе комбинации порождающего полинома последовательность номеров кластеров базовой и обозначим ее как . Циклическое смещение номеров  базовой последовательности кластеров  приведет к новой комбинации кластеров, принадлежащей данному коду. Она будет иметь вид

          …     .

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

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

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

 

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

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

 

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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