СПОСОБ ДЕКОДИРОВАНИЯ ЦИКЛИЧЕСКОГО ПОМЕХОУСТОЙЧИВОГО КОДА Российский патент 2006 года по МПК H03M13/15 G06F11/00 

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

Заявленное техническое решение расширяет арсенал средств аналогичного назначения за счет возможности декодирования циклических помехоустойчивых кодов с изменяемыми параметрами.

Известен способ декодирования циклического кода [Кларк Дж. мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи: пер. с англ. - М.: Радио и связь, 1987. сс.179-190], в котором на первом этапе принятая кодовая комбинация, описываемая многочленом S(x), делится на известный порождающий многочлен g(х). Затем вычисляется и анализируется остаток от деления r(х). Если остаток от деления r(х)=0, то принятая кодовая комбинация считается неискаженной. Если остаток от деления r(х)≠0, то принятая кодовая комбинация стирается и формируется сигнал "ошибка".

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

Также известен способ декодирования, реализованный в устройстве декодирования двоичного циклического кода [авторское свидетельство СССР № 1339901, кл. Н 03 М 13/02. Устройство для декодирования двоичного циклического кода. / С.В.Беззатеев, Е.Т.Мирончиков и Н.А.Шехунова, зарегистрировано 23.09.87], в котором на первом этапе определяют компоненты синдрома и вычисляют многочлен синдрома. С помощью полученных данных решают ключевое уравнение, определяют многочлен локатора ошибок и позиции ошибочных символов.

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

Наиболее близким к заявленному является способ (прототип) декодирования циклического помехоустойчивого кода [патент РФ 2231216 / Способ декодирования циклического помехоустойчивого кода / Квашенников В.И. / опубликованный 10.02.2004], заключающийся в том, что на передающей и приемной стороне предварительно задают параметры циклического помехоустойчивого (n, k) кода, такие как длина кодовой комбинации (n), число информационных символов (k) и проверочный многочлен h(х), а также вид синхронизирующей последовательности, на передающей стороне кодируют информационную последовательность циклическим помехоустойчивым кодом с заданными параметрами, рекуррентно продолжают кодовое слово циклического помехоустойчивого кода до длины n1>n и формируют выходную последовательность, представляющую собой сумму по модулю два циклического помехоустойчивого кода и синхронизирующей последовательности, на приемной стороне формируют циклические продолжения принятой последовательности, умножают принятую последовательность на известный проверочный многочлен помехоустойчивого кода h(х) и вычисляют синхронизирующую последовательность, распознают уникальную комбинацию синхронизирующей последовательности и определяют начало комбинации помехоустойчивого кода, вычитают синхронизирующую последовательность из принятой последовательности и, получив кодовое слово циклического помехоустойчивого кода, определяют комбинации ошибок в кодовом слове и исправляют ошибки в информационной части кодового слова циклического помехоустойчивого кода.

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

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

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

Поставленная цель достигается тем, что в предложенном способе декодирования циклического помехоустойчивого кода на передающей стороне задают параметры циклического помехоустойчивого (n, k) кода, такие как длина кодовой комбинации n, число информационных символов k и порождающий многочлен g(х), кодируют информационную последовательность циклическим помехоустойчивым кодом с заданными параметрами и передают сформированную последовательность по каналу связи на приемную сторону. На приемной стороне задают диапазон предполагаемых длин кодовых комбинаций [n_min-n_max] и выбирают предполагаемую фазу начала кодовой комбинации f. С фазы f в принятой кодовой последовательности выделяют несколько предполагаемых кодовых комбинаций S_i и формируют из выделенных комбинаций пары кодовых комбинаций согласно условию S_i≠S_k. Вычисляют N наибольших общих делителей (НОД), представленных многочленами, для различных пар кодовых комбинаций и выбирают среди вычисленных многочленов, являющихся НОД, многочлен наименьшей степени, который отождествляют с порождающим многочленом g(х) циклического помехоустойчивого кода. Если НОД равен "1", увеличивают длину предполагаемой кодовой комбинации n на единицу. Изменяют фазу предполагаемого начала кодовой комбинации на единицу, если наибольший общий делитель, отличный от "1", не найден при всех n∈[n_min-n_max]. Определяют комбинации ошибок в кодовом слове и декодируют выделенные кодовые комбинации.

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

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

Заявленный способ может быть реализован следующим образом.

Декодирование циклического помехоустойчивого кода базируется на теории помехоустойчивого кодирования [Блейхут Р.Э. Теория и практика кодов, контролирующих ошибки: Пер. с англ. - М.: Мир, 1986. - 576 с.] и может осуществляться в режиме обнаружения или исправления ошибок.

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

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

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

Суть предлагаемого способа заключается в следующем.

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

На приемной стороне задают диапазон предполагаемых длин кодовых комбинаций [n_min-n_max]. В принятой кодовой последовательности задают предполагаемую фазу начала кодовой комбинации f_н, выбирают длину кодовой комбинации n=n_min и выделяют несколько кодовых комбинаций S_i, i=1,2,..., длины n с фазы f_н.

Из выделенных кодовых комбинаций формируют пары согласно условию S_i≠S_j, j=1,2,... и i≠j. Для выделенных пар кодовых комбинаций вычисляют наибольшие общие делители (НОД). Вычисление НОД осуществляют с помощью алгоритма Евклида, который сводится к итеративному алгоритму деления, суть которого заключается в следующем.

Если степень многочлена, описывающего кодовую комбинацию S₁, больше либо равна степени многочлена, описывающего кодовую комбинацию S₂, то последовательность вычислений имеет вид

Процесс останавливают, как только получается остаток, равный нулю.

Таким образом, необходимо первую кодовую комбинацию S₁ (делимое) разделить на вторую кодовую комбинацию S₂ (делитель) и получить остаток от деления r₁. Затем делитель, используемый на первом этапе (делимое на втором этапе), необходимо разделить на полученный на первом этапе остаток r₁ (делитель на втором этапе). Процесс повторяется до получения нулевого остатка, при этом НОД равен делителю r_n, при котором получился нулевой остаток.

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

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

Случай, когда НОД равен единице, свидетельствует об отсутствии общего делителя у выделенных кодовых комбинаций. При этом осуществляют выбор следующей длины кодовой комбинации n=n_min+1 из заданного диапазона и повторяют процесс нахождения НОД.

Если при переборе всех возможных длин кодовых комбинаций из заданного диапазона n∈[n_min-n_max] НОД не обнаружен, то смещают предполагаемую фазу начала кодовой комбинации в принятой кодовой последовательности и осуществляют поиск НОД для новой фазы f=f_H+1.

Диапазон изменения фазы начала предполагаемой кодовой комбинации определяется выражением f∈[f_H,f_H+n_max].

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

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

Изобретение относится к области техники связи, в частности к системам передачи данных для декодирования циклических помехоустойчивых кодов без предварительного фазирования. Техническим результатом является разработка способа декодирования циклического помехоустойчивого кода в условиях адаптации помехоустойчивого кода к качеству канала передачи информации. При декодировании циклического помехоустойчивого кода определяют диапазон предполагаемых длин кодовых комбинаций [n_min-n_max] и задают предполагаемую фазу начала кодовой комбинации (f), с фазы f в принятой кодовой последовательности выделяют несколько предполагаемых кодовых комбинаций S_i и формируют из выделенных комбинаций пары согласно условию S_i≠S_k, вычисляют N наибольших общих делителей (НОД), представленных многочленами, для различных пар кодовых комбинаций и выбирают среди вычисленных многочленов многочлен наименьшей степени, который отождествляют с порождающим многочленом g(x) циклического помехоустойчивого кода, если НОД равен "1", то увеличивают длину предполагаемой кодовой комбинации n на единицу, изменяют фазу предполагаемого начала кодовой комбинации на единицу, если наибольший общий делитель, отличный от "1", не найден при всех n∈[n_min-n_max], определяют комбинации ошибок в кодовом слове и декодируют выделенные кодовые комбинации. 2 з.п. ф-лы.

1. Способ декодирования циклического помехоустойчивого кода, заключающийся в том, что предварительно на передающей стороне формируют информационную последовательность и задают параметры циклического помехоустойчивого кода, включающие длину кодовой комбинации n, число информационных символов k и порождающий многочлен g(x), с помощью которого кодируют информационную последовательность и передают ее по каналу связи на приемную сторону, принимают переданную закодированную информационную последовательность, определяют начало кодовой комбинации циклического помехоустойчивого кода и комбинации ошибок в кодовой комбинации, после чего декодируют выделенные кодовые комбинации, отличающийся тем, что на передающей стороне комбинация циклического помехоустойчивого кода b_k формируется путем перемножения информационной последовательности a_k на порождающий многочлен g(x), а на приемной стороне перед началом декодирования определяют порождающий многочлен циклического помехоустойчивого кода, для чего задают диапазон предполагаемых длин кодовых комбинаций [n_min-n_max], выбирают предполагаемую фазу начала кодовой комбинации f, выделяют из принятой закодированной информационной последовательности несколько предполагаемых кодовых комбинаций S_i, где i=1,2,..., выбирают из числа выделенных кодовых комбинаций N пар кодовых комбинаций, удовлетворяющих условию S_i≠S_j, где j=1,2,... и i≠j, для каждой пары кодовых комбинации вычисляют наибольший общий делитель, причем, если наибольшие общие делители указанных N пар кодовых комбинаций равны единице, то увеличивают предполагаемую длину кодовой комбинации на единицу, и повторяют процесс нахождения наибольших общих делителей, если при переборе всех возможных длин кодовых комбинаций из заданного диапазона [n_min-n_max] наибольшие общие делители, отличные от единицы, не обнаружены, изменяют предполагаемую фазу начала кодовой комбинации на единицу и осуществляют поиск N наибольших общих делителей для новой фазы начала кодовой комбинации, после чего из многочленов, являющихся наибольшими общими делителями, выбирают многочлен наименьшей степени и отождествляют его с порождающим многочленом циклического помехоустойчивого кода g(x), причем осуществляют поиск порождающего многочлена g(x) на различных участках реализации и решение об истинности порождающего многочлена принимают по мажоритарному принципу.2. Способ по п.1, отличающийся тем, что вычисление наибольшего общего делителя осуществляют с помощью алгоритма Евклида.3. Способ по п.1, отличающийся тем, что число N наибольших общих делителей выбирают равным двум.