Research of cognitive data processing in radio communication systems with permutation decoding

Full Text

Введение

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

Одной из первых работ, связанных с процедурой обучения декодера избыточного кода по полученной случайным образом в результате сортировки принятых символов по убыванию градаций надежности их мягких решений и заменой процедуры решения системы линейных уравнений на тривиальный поиск необходимого решения по списку, была статья [1]. В последующем представленное техническое решение получило свое развитие в работах [2–7]. Следует отметить, что в указанных публикациях не рассматривается тонкая структура когнитивных карт (КК), не приводятся экспериментальные данные по выявлению частоты возникновения производительных перестановок нумераторов (ППН) и непроизводительных перестановок нумераторов (НПН) для кодов с различной избыточностью. Более того, не рассматриваются возможности гибкого использования когнитивных карт в условиях их взаимоувязанности.

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

1. Общая классификация перестановок и их статистические свойства

Считается, что принципы перестановочного декодирования (ПД) избыточных кодов известны из источников [7–9]. Учитывая специфику практического использования БС, для исследования были выбраны короткие избыточные коды (7, 4) – код Хэмминга; два кода БЧХ (15, 5) и (15, 7); совершенный код Голея (23, 12) и его укороченный аналог (18, 7). С использованием специально разработанной программы методом прямого перебора всех возможных перестановок нумераторов для указанных кодов были получены достаточно неожиданные данные по процентному соотношению ППН и НПН, которые приведены в таблице 1. Если для кода (7, 4) значение ППН существенно превосходит показатель НПН, что важно с практической точки зрения, то для других кодов это соотношение становится практически равным. Принципиально это означает, что в половине случаев процедура ПД оказывается под угрозой срыва, что недопустимо. Предлагается оценить закономерности записей априорных вычислений для КК, позволяющих снизить объем данных, вносимых в память процессора с указанием пути рационального преобразования перестановок типа НПН, и таким образом сделать более совершенной работу декодера на борту БС.

 

Таблица 1. Процентное соотношение производительных и непроизводительных перестановок по результатам статистических испытаний

Table 1. Percentage of productive and unproductive permutations according to the results of statistical tests

Хэмминга код (7, 4, 3)		Код БЧХ (15, 5, 7)		Код БЧХ (15, 7, 5)		Код Голея (23, 12, 7)		Код Голея – укороченный (18, 7, 7)
ППН	НПН	ППН	НПН	ППН	НПН	ППН	НПН	ППН	НПН
80	20	62	38	51	49	52	48	52	48

 

В количественном отношении общее число перестановок оценивается выражением $N=C_n^k.$

Общее количество перестановок, требующих записи в КК декодера, приведено в таблице 2. В комбинаторике циклические сдвиги перестановок объединяются в орбиты. Во главе орбиты находится образующая комбинация орбиты (ОКО). Это означает, что объем памяти КК может быть уменьшен в $n$ раз, но в таком случае, занося в память только значение ОКО, приходится вводить процедуру поиска в орбите требуемой записи [8–13]. Это означает, что простой поиск данных в некотором числовом массиве будет заменен вычислительным процессом, требующим определенных энергетических затрат. Более того, из-за замкнутости цикла перестановок, формируемых ОКО, в общей орбите переставленных по циклу комбинаций оказываются перестановки, формат которых может совпадать с форматом ОКО. Это становится ясным из анализа состава двух орбит, представленных на рис. 1.

 

Таблица 2. Объем выборки кодовых комбинаций для некоторых кодов

Table 2. Sample size of code combinations for some codes

Код	Объем перестановок	Общее количество ОКО	Объем выборки ОКО ППН	Машинное время составления КК
1	2	3	4	5
15,7,5	6435	3003	1512	150 с
15,5,7	3003	1001	616	70 с
23, 12, 7	1352078	705432	362880	900 с
18, 7, 7	31824	12376	6384	210 с

 

Рис. 1. Пример структуры орбит для двоичных кодов

Fig. 1. Example of orbit structure for binary codes

 

В данной ситуации абстрактная алгебра указывает на так называемые тривиальные орбиты (ТО), одна из которых становится образующей комбинацией сборной орбиты (СО). Признаком любой ОКО является наличие единицы в левом разряде перестановки. Для кода БЧХ (15, 5, 7) на рис. 1 приведены образцы двух СО. Для одной такой орбиты определитель перестановки, не равный нулю, дает производительную перестановку в отношении ЭК, в другом случае такой код получен быть не может (определитель перестановки равен нулю). Сравнение СО показывает, что у них много общего, но из-за показателей определителей они должны быть занесены в разные КК: в карты производительных и непроизводительных перестановок соответственно. Целесообразно показатель ОКО для СО определять как наибольшую разницу между нумератором, стоящим на первой позиции (старший разряд в записи слева), и нумератором, стоящим на k позиции (младший разряд в записи справа). Для кода (15, 7), как следует из рисунка 1, это будут комбинации 1 3 4 6 10 и 1 3 6 7 11 соответственно. Перестановки, которые в таблицах выделены серым, являются ОКО ТО. В ходе исследования было выделено несколько свойств орбит перестановок.

Свойство 1. Потенциально каждая ТО может иметь минимум одну перестановку, максимум $\left(n-k\right)$ различных перестановок. В последнем случае при известной ОКО поиск требуемой перестановки во времени может затянуться, если такая перестановка находится в конце списка.

Свойство 2. Численным методом установлено, что в условиях, когда для ОКО СО определитель переставленной матрицы не равен нулю, то определи всех перестановок сборной орбиты также не равны нулю. В противном случае все определители сборной орбиты равны нулю.

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

Недостатком описанного подхода является проявление свойства 1. Для ускорения процесса поиска требуемого решения предлагается совершенно новая характеристика.

2. Понятие интервальных оценок в перестановках. Перестановки ППН

Рассмотрим последовательность нумераторов ОКО СО 1 3 4 6 10. Из рис. 1 (левая таблица) следует, что в ТО, к которой относится данная перестановка, для всех перестановок из состава этой орбиты будет одинаковый интервал между соседними нумераторами. Легко проверить, что для представленного примера это будет последовательность вида 2 1 2 4. Действительно, циклический сдвиг нумераторов по регистру сдвига не меняет расстояния между нумераторами.

Свойство 3. Интервальные оценки являются более информативными относительно свойств своей ТО, при этом оказываются на один байт меньше показателя перестановки.

Свойство 4. Если интервальная оценка не является орбитой ОКО СО, то другие $\left(k-1\right)$ ОКО ТО в составе интервальной оценки имеют маркер, который указывает на шаги циклических изменений проверочной части порождающей матрицы в систематической форме. Образец проверочной матрицы хранится в специальной КК. Принцип преобразования представлен в таблице 3.

 

Таблица 3. Систематическое преобразование поверочной части порождающей матрицы ЭК в зависимости от содержания ОКО ТО с маркером 6

Table 3. Systematic transformation of the verification part of the generating matrix EC depending on the content of forming combination of a trivial orbit with marker 6

1 3 4 6 10	1 7 9 10 12	1 5 11 13 14	1 3 7 13 15	1 2 4 8 14
2 1 2 4	6 2 1 2	4 6 2 1	2 4 6 2	1 2 4 6
1010101101 0101111100 1101001111 1011110110 0110010111	1011101100 0110110101 1110001011 0111111010 1011010111	1111011010 1001011101 1010110110 0111110001 0100111111	1010011111 0111101101 1100101110 0101011011 1011111000	1011111000 1010011111 0111101101 1100101110 0101011011

 

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

Свойство 5. Порождающие матрицы для ОКО ТО формируются на основе сведений о количестве ОКО, формируемых в рамках одной орбиты. Например, для ОКО СО будет сформировано всего пять ОКО. Следовательно, для ОКО ТО с показателем интервальных оценок 6 2 1 2 комбинации в исходной левой колонке должны быть сдвинуты по циклу на пять шагов. Поэтому комбинация 0110010111 преобразуется к виду 01100 10111, и для ОКО ТО с интервальными оценками 6 2 1 2 будет сформирован вектор 1011101100. Сказанное относится ко всем показателям ОКО.

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

Таким образом, матричные преобразования в системе ППН сводятся к циклическим преобразованиям некоторой исходной матрицы к требуемой матрице ЭК для конкретной перестановки.

3. Особенности обработки непроизводительных перестановок

Главной отличительной чертой НПН является вырожденность переставленных матриц нумераторов наиболее надежных символов принятых кодовых векторов. И если для кода Хэмминга (7, 4) число таких перестановок составляет всего 20 % от их общего числа, то для кодов (15, 5) и (15, 7) общее число непроизводительных перестановок возрастает до 50 %.

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

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

 

Таблица 4. Структура разниц нумераторов ОКО частных орбит перестановки 1 4 6 8 9

Table 4. Structure of the differences between the numerators of the forming combination of private orbits of the permutation 1 4 6 8 9

Комбинация ОКО	Разница соседних интервалов
1 4 6 8 9	3 2 2 1
1 8 11 13 15	7 3 2 2
1 2 9 12 14	1 7 3 2
1 3 4 11 14	2 1 7 3
1 3 5 6 13	2 2 1 7

 

Описанный алгоритм удобен при использовании кода (7, 4), когда число производительных перестановок составляет 80 % от общего числа возможных перестановок. Для кодов БЧХ (15, 5) и (15, 7) эта пропорция изменяется в сторону увеличения числа непроизводительных перестановок и по этой причине становится невыгодной из-за соотношения ППН к НПН как 50 % к 50 %. При этом вероятность удачной замены символов остается относительно низкой, поскольку новая перестановка после замены символов может вновь оказаться из множества НПН.

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

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

 

Таблица 5. Структура нумераторов ОКО локальных орбит из состава НПН

Table 5. Structure of forming combination numerators for local orbits from the unproductive permutations of numerators

Комбинация ОКО	Разница соседних интервалов	Запрещенные нумераторы
1 2 3 4 6	1 1 2 2	8 9 12
2 12 13 14 15	10 1 1 1	3 4 7
1 3 13 14 15	2 10 1 1	ВСЕ
1 2 4 14 15	1 2 10 1	6 7 10
1 2 3 5 15	1 1 2 10	7 8 11
1 2 3 4 9	1 1 1 5	6 8 12
1 8 9 10 11	7 1 1 1	4 13 15
1 6 13 14 15	5 7 1 1	3 5 9
1 2 7 14 15	1 5 7 1	4 6 10
1 2 3 8 15	1 1 5 7	ВСЕ
1 3 6 7 11	2 3 1 4	9 10
1 6 8 11 12	5 2 3 1	14 15
1 5 10 12 15	4 5 2 3	ВСЕ
1 2 6 11 13	1 4 5 2	4 5
1 4 5 9 14	3 1 4 5	7 8

 

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

Выявлены предпосылки к закономерности, при которой ни один из символов в составе проверочной матрицы не приводит к переводу перестановки, обозначенной термином ВСЕ, в систему ППН. Теоретического объяснения, обоснования этот факт на данном этапе исследований не нашел. Однозначно потребуется специальная программа, которая позволит убедиться в закономерности этого явления или, напротив, в определенной исключительности.

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

Анализ таблицы 4 показывает, что запрещенное число значений нумераторов для разных ОКО из состава НПН различно, но все они имеют термин ВСЕ. Этот факт в теории кодирования вскрыт впервые и пока не нашел своего теоретического объяснения. Заметно, что запрещенные замены в системе НПН носят в зависимости от ОКО системный характер, который может быть использован для организации вычислительного процесса в случае критических значений по объему памяти когнитивных карт.

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

4. Оценка реализации перестановочного декодера в системе беспилотных средств

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

 

Таблица 6. Параметры микропроцессоров, пригодных для формирования ПД

Table 6. Parameters of microprocessors suitable for generating permutation decoding

	ATmega168P	ATmega328P	ATmega32u4	ATmega2560	Atmel SAM3X8E
ПЗУ (EEPROM)	0,5 Кб	1 Кб	1 Кб	4 Кб	16 Кб
ОЗУ (SRAM)	1 Кб	2 Кб	2,5 Кб	8 Кб	96 Кб
Память программ (FLASH)	16 Кб	32 Кб	32 Кб	256 Кб	512 Кб
Частота ЦП	16 МГц	16 МГц	16 МГц	16 МГц	84 МГц
Потребление на 1 МГц в режиме active	0,3 мА	0,3 мА	0,8 мА	3–4,68 мА	1 мА
Размеры	7 мм × 7 мм	7 мм × 7 мм или 34 мм × 7мм	10 мм × 10 мм или 7 мм × 7 мм	14 мм × 14 мм или 7 мм × 7 мм	20 мм × 20 мм или 10 мм × 10 мм

 

Приведенные микропроцессоры обладают высокой энергоэффективностью, что позволяет использовать их от автономного источника питания. Так, при использовании аккумулятора емкостью 5000 мАч и микропроцессора ATmega328P в активном режиме на максимальной частоте (16 МГц) теоретически может проработать свыше 1000 часов. На практике же полная схема обвязки микропроцессора с минимально необходимым набором вспомогательных элементов при активном режиме составляет 30–100 мА. При таком потреблении указанного выше аккумулятора схема может работать непрерывно порядка 166 часов. На практике разряд батареи будет осуществляться несколько иначе, поскольку разряд происходит нелинейно, но порядок будет примерно таким. Следовательно, реализация декодера на микропроцессорах Amel успешно может быть реализована для систем, работающих от автономных источников питания.

Как следует из рис. 2, размеры микропроцессоров не превышают 20 мм × 20 мм, что делает возможным их размещение практически на любой платформе.

 

Рис. 2. Геометрические размеры процессоров для реализации декодера

Fig. 2. Geometric dimensions of processors for decoder implementation

 

Очевидно, что производительности энергоэффективных микропроцессоров, приведенных выше, недостаточно для вычисления необходимых матриц при реализации декодера БЧХ (15, 5) с достаточной скоростью для поддержания приемлемой скорости канала связи. В рамках данной работы вместо сложных матричных вычислений предлагается использовать список готовых решений – когнитивную карту процессора декодера. Минимальный объем памяти для хранения когнитивных карт может быть рассчитан достаточно просто. Например, объем когнитивной карты для кода БЧХ (15, 5) составляет около 28–30 Кб. Эти данные в процессе выполнения программы не изменяются, а потому могут быть размещены в памяти программы (FLASH) микропроцессора.

Однако кроме данных когнитивной карты необходимо учитывать дополнительные ресурсы памяти для основного алгоритма исполняемого кода (работа с массивами, алгебраические операции, чтение и запись данных). Также следует учитывать, что декодер прежде всего является частью приемника, а следовательно, программный код реализации декодера должен работать в одном рабочем цикле с программной реализацией протокола связи. Таким образом, минимально необходимая память микроконтроллера должна превышать объем когнитивной карты минимум в 2 раза (<60 Кб). Из приведенных в таблице 5 микропроцессоров таким объемом программной памяти обладают ATmega2560 и Atmel SAM3X8E.

Заключение

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

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

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

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

About the authors

Dmitry V. Mishin

Povolzhskiy State University of Telecommunications and Informatics

Email: d.mishin@psuti.ru
ORCID iD: 0000-0003-2572-5254

Doctor of Technical Sciences, professor of the Department of Radio Engineering Systems

Russian Federation, 23, L. Tolstoy Street, Samara, 443010

Anatoly A. Gladkikh

Ulyanovsk State Technical University

Author for correspondence.
Email: a_gladkikh@mail.ru
ORCID iD: 0000-0002-0466-9102

Doctor of Technical Sciences, Professor of the Department of Radio Engineering, Telecommunications and Information Security

Russian Federation, 32, Severny Venets Street, Ulyanovsk, 432027

Vladislav I. Kutuzov

Ulyanovsk State Technical University

Email: kutuzovvladislav@mail.ru
ORCID iD: 0009-0003-9925-5889

engineer at ITE Expo International LLC, postgraduate student of the Department of Radio Engineering, Telecommunications and Information Security

Russian Federation, 32, Severny Venets Street, Ulyanovsk, 432027

Aqeel Latif Khudair Attaby

Ulyanovsk State Technical University

Email: aqeel.attaby@gmail.com
ORCID iD: 0000-0002-0836-9254

postgraduate student of the Department of Radio Engineering, Telecommunications and Information Security

Russian Federation, 32, Severny Venets Street, Ulyanovsk, 432027

References

Supplementary files