Preview

Вестник Концерна ВКО «Алмаз – Антей»

Расширенный поиск

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

https://doi.org/10.38013/2542-0542-2020-4-95-100

Полный текст:

Аннотация

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

Для цитирования:


Светлов Г.В., Суменков Н.А., Костров Б.В., Гринченко Н.Н., Трушина Е.А. Построение ортогонального базиса на основе псевдослучайных последовательностей. Вестник Концерна ВКО «Алмаз – Антей». 2020;(4):95-100. https://doi.org/10.38013/2542-0542-2020-4-95-100

For citation:


Svetlov G.V., Sumenkov N.A., Kostrov B.V., Grinchenko N.N., Trushina E.A. Construction of an orthogonal basis based on pseudorandom sequences. Journal of «Almaz – Antey» Air and Space Defence Corporation. 2020;(4):95-100. https://doi.org/10.38013/2542-0542-2020-4-95-100

Задача обеспечения помехоустойчивого кодирования в системах цифровой передачи информации остается и будет еще долго оставаться весьма актуальной. Снижение вероятности передачи ошибочных бит позволяет снижать мощности передающих устройств, уменьшать габариты систем. Особенно это актуально в системах, допускающих определенную вероятность ошибки передачи, не влияющую на потребительское качество получаемой информации. В системах передачи изображений [1][2][3], например, можно допустить определенные искажения, не влияющие на их восприятие. В таких системах применяют протоколы сжатия и помехоустойчивое кодирование на основе ортогональных преобразований с кусочно-постоянными базисными функциями [4][5][6]. Несмотря на простоту и понятность использования таких преобразований, они обладают и рядом недостатков. В качестве основного можно привести неравномерное распределение энергии по базису преобразования, что приводит к существенным пульсациям энергии в канале передачи.

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

Исходной информацией для построения ПСП является образующий многочлен

где aN, a1 = 1; ai ∈ {0,1}; N – число разрядов регистра сдвига.

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

Любому образующему полиному можно поставить в соответствие генератор Фибоначчи [7]

где gi(t) – состояние i-го разряда регистра сдвига на такте 

В матричном виде алгоритм формирования последовательности будет

Рассмотрим пример.

M(x) = x3 + x2 +1.

В соответствии с (2) можно записать:

Или в матричном виде:

Таблица состояний разрядов регистра, построенная в соответствии с (4) и (5), приведена ниже.

Таблица

Состояния разрядов регистра сдвига

Как видно из таблицы, полный цикл последовательности состоит из 8 тактов, 7 из которых не повторяются, 8-й такт является началом нового периода. ПСП снимается с разряда g3. Ее период равен 2N – 1, N – число разрядов.

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

1. Период ПСП, формируемый в соответствии с образующим полиномом M(x), равен

M = 2N – 1 (6)

2. Для заданного M(x) существует M различных ПСП, полученных путем цикличного сдвига исходной последовательности.

3. Число единичных символов на периоде ПСП равно 2N – 1, а нулевых 2N – 1 – 1.

4. В ПСП серии из одного символа встречаются 2N – 2 раз, из двух одинаковых символов – 2N – 3 раз и так далее. Серии из N – 1 нулей и N единиц присутствуют только один раз.

5. Автокорреляционная функция полученной последовательности определяется выражением:

6. Децимация последовательности по четному индексу j = M – 1 приводит к инверсии исходной последовательности, которая соответствует последовательности, порождаемой полиномом M–1(x), обратным M(x). {bi} = {c–i}, где bi – инверсная ПСП, ci – прямая.

Рассмотренные ПСП принято называть последовательностями максимального периода, или М-последовательностями.

Количество различных полиномов M(x) порождающих М-последовательность, зависит от ее периода M = 2n – 1. Оно быстро возрастает с увеличением n. Для n = 8 количество порождающих полиномов равно 16 [8]. Конкретный вид получаемой последовательности будет зависеть еще и от начальных условий, заданных для инициализации формирования последовательности. При n = 8 количество начальных условий равно 255. Таким образом, при заданном n = 8 количество разновидностей М-последовательностей составляет 16 (2n – 1) ≈ 4000. С увеличением n это число быстро возрастает (при n = 10, например, до 60 000).

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

Рассмотрим процесс формирования матрицы преобразования. Как следует из свойства 2, необходимое количество строк матрицы может быть получено путем цикличного сдвига исходной последовательности. Количество строк в такой матрице будет равно периоду M = 2n – 1, и матрица будет иметь размер M × M. Все строки и столбцы данной матрицы будут представлять собой М-последовательности. Пример формирования такой матрицы представлен на рисунке 1а. Данная матрица обладает свойством симметричности строк и столбцов в соответствии со свойством 5. Автокорреляционная функция при совпадающих строках и столбцах равна 1. Однако при несовпадении строк и столбцов значение автокорреляционной функции равно –1/M. Результат произведения матрицы M на MT, где MT – транспонированная матрица, приведен на рисунке 1б. Результат умножения не является единичной матрицей, что не соответствует признакам ортогонального преобразования.

Для выполнения условий ортогональности необходимо:

  • выровнять количество нулевых и единичных символов на периоде ПСП, сделав его равным 2n – 1;
  • внести знакопеременность в ПСП для обеспечения нулевой постоянной составляющей в строках и столбцах матрицы.

Сформированная таким образом матрица преобразования M80 и соответствующее ей произведение на транспонированную M8T приведены на рисунке 2.


Рис. 1. Матрица получения сдвигом влево последовательности при M(x) = x3+x2+1 и начальном состоянии 100(4) (а) и результат умножения на транспонированную матрицу (б)

Рис. 3
. Использование ортогонального преобразования для передачи спутникового изображения по каналу с шумами: исходное изображение (а), результат воздействия шумов (СКО = 40) при передаче без преобразования (б) и результат передачи с преобразованием (СКО = 2,55) (в)

Как видно из рисунка 2, матрица M80, построенная для примера, приведенного выше, соответствует требованиям ортогональности и может быть использована для преобразования сигналов. Количество таких матриц зависит от необходимого числа n и соответствует количеству М-последовательностей, которые могут быть построены на основе разнообразных образующих полиномов. В общем случае можно записать пару преобразования:

где Fnc – матрица (матрица-строка) коэффициентов преобразования сигнала; Bnc – матрица (матрица-столбец) сигнала; Mn0T – транспонированная матрица преобразования.

На рисунке 3 представлен результат использования данного подхода для моделирования процесса передачи спутниковых изображений [10][11][12] по каналу связи. Образующий полином M(x) = x7+ x5+ x4+ x3+1, начальное состояние 10101101(173). В качестве сигнальной матрицы Bnc выступает матрица яркостей изображения. Поскольку матрица M0 – симметричная, то в операции транспонирования необходимости нет.

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

Список литературы

1. Гонсалес Р., Вудс Р., Эддинс С. Цифровая обработка изображений в среде MATLAB. М.: Техносфера, 2006. 616 с.

2. Злобин В. К., Костров Б. В., Саблина В. А. Место и роль методов секвентного анализа в обработке аэрокосмических изображений // Радиотехника. 2012. № 3. С. 64-72.

3. Костров Б. В., Саблина В. А. Адаптивная фильтрация изображений со структурными искажениями // Цифровая обработка сигналов. 2008. № 4. С. 49-53.

4. Ахмед Н., Рао К. Р. Ортогональные преобразования при обработке цифровых сигналов / под ред. И. Б. Фоменко. М.: Связь, 1980. 248 с.

5. Злобин В. К., Костров Б. В., Свирина А. Г. Спектральный анализ изображений в конечных базисах. М.: КУРС: ИНФРА, 2016. 172 с.

6. Костров Б. В., Бастрычкин А. С. Сжатие изображений на основе ортогональных преобразований // Известия Тульского государственного университета. Технические науки. 2016. Вып. 9. С. 113-118.

7. Гарифуллина З. Р., Иванов М. А., Рябков В. Е., Чугунков И. В. Способ формирования нелинейных М-последовательностей // Безопасность информационных технологий. 2011. № 2. С. 31-36.

8. Захаров И. Д., Ожиганов А. А. Использование порождающих полиномов М-последовательностей при построении псевдослучайных кодовых шкал // Известия вузов. Приборостроение. 2011. Т. 54. №. 6. С. 49-55.

9. Костров Б. В., Соломенцева Н. И. Моделирование канала связи // Известия Тульского государственного университета. Технические науки. 2017. Вып. 2. С. 95-100.

10. Костров Б. В. Особенности формирования аэрокосмических изображений радиотехническими системами // Проектирование и технология электронных средств. 2011. № 1. С. 4143.

11. Костров Б. В., Гринченко Н. Н., Степанов Д. С., Упакова А. Г. Алгоритм передачи изображения с восстановлением постоянной составляющей // Известия Тульского государственного университета. Технические науки. 2013. Вып. 9. Ч. 1. С. 244-249.

12. Костров Б. В., Упакова А. Г. Квазидвумерная фильтрация синхронных помех на изображении // Проектирование и технология электронных средств. 2012. № 1. С. 32-35.


Об авторах

Г. В. Светлов
Рязанское производственно-техническое предприятие Гранит, акционерное общество
Россия

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

Рязань


Н. А. Суменков
Рязанское производственно-техническое предприятие Гранит, акционерное общество
Россия

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

Рязань


Б. В. Костров
Рязанское производственно-техническое предприятие Гранит, акционерное общество
Россия

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

Рязань


Н. Н. Гринченко
Рязанское производственно-техническое предприятие Гранит, акционерное общество
Россия

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

Рязань


Е. А. Трушина
Рязанский государственный радиотехнический университет
Россия

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

Рязань


Для цитирования:


Светлов Г.В., Суменков Н.А., Костров Б.В., Гринченко Н.Н., Трушина Е.А. Построение ортогонального базиса на основе псевдослучайных последовательностей. Вестник Концерна ВКО «Алмаз – Антей». 2020;(4):95-100. https://doi.org/10.38013/2542-0542-2020-4-95-100

For citation:


Svetlov G.V., Sumenkov N.A., Kostrov B.V., Grinchenko N.N., Trushina E.A. Construction of an orthogonal basis based on pseudorandom sequences. Journal of «Almaz – Antey» Air and Space Defence Corporation. 2020;(4):95-100. https://doi.org/10.38013/2542-0542-2020-4-95-100

Просмотров: 86


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2542-0542 (Print)