Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,899

МОДИФИКАЦИЯ АЛГОРИТМА ВЫЧИСЛЕНИЯ ПОЗИЦИОННО-ИНТЕРВАЛЬНОЙ ХАРАКТЕРИСТИКИ МОДУЛЯРНЫХ КОДОВ ДЛЯ КОРРЕКЦИИ ОШИБОК

Чистоусов Н.К. 1 Чипига А.Ф. 1 Калмыков И.А. 1 Ефременков И.Д. 1 Калмыкова Н.И. 1
1 ФГАОУ ВО «Северо-Кавказский федеральный университет»
Для обеспечения более высокой имитостойкости систем опознавания «свой – чужой» надо сокращать время, которое тратится на аутентификацию претендента. В этом случае у нарушителя уменьшается вероятность правильного подбора сигнала ответчика. Для достижения такой цели в ряде работ предлагалось выполнять протоколы аутентификации с использованием параллельных вычислений. В этом случае наибольшее распространение получили параллельные арифметические коды, в частности модулярные коды. Среди данных кодов особое место занимают коды системы классов вычетов (СОК). Высокая скорость вычисления достигается за счет параллельного выполнения арифметических операций. Это происходит благодаря тому, что данные операции выполняются над малыми остатками. При этом в ходе выполнения данных операций обмен промежуточных результатов между модулями кода СОК не осуществляется. Следовательно, при возникновении ошибки она не будет оказывать влияния на другие остатки кода СОК. Значит, при введении избыточных модулей код СОК можно использовать для коррекции ошибок в остатках. При этом данная процедура базируется на вычислении позиционно-интервальной характеристики (ПИХ). Очевидно, что снижение схемных затрат на вычисление ПИХ повышает эффективность алгоритма вычисления ошибок в коде СОК. Поэтому модификация алгоритма вычисления позиционно-интервальной характеристики модулярных кодов для коррекции ошибок является актуальной задачей.
протоколы опознавания «свой – чужой»
параллельные модулярные коды
позиционно-интервальная характеристика
коррекция ошибок в СОК
1. Пашинцев В.П., Ляхов А.В. Применение помехоустойчивого протокола аутентификации космического аппарата для низкоорбитальной системы спутниковой связи // Инфокоммуникационные технологии. 2015. № 2. С. 183–190.
2. Калмыков И.А., Чипига А.Ф. Алгоритм коррекции ошибок, возникающих при вычислении ответа на запрос отказоустойчивой системы опознавания спутника // Современные наукоемкие технологии. 2021. № 3. С. 96–100. DOI: 10.17513/snt.38069.
3. Чистоусов Н.К., Калмыкова Н.И. Разработка протоколов аутентификации низкоорбитальных космических аппаратов на основе параллельных кодов систем остаточных классов // Инженерный вестник Дона. 2021. № 4. [Электронный ресурс]. URL: ivdon.ru/ru/magazine/archive/n4y2021/6912 (дата обращения: 10.08.2021).
4. Червяков Н.И., Коляда А.А., Ляхов П.А. Модулярная арифметика и ее приложения в инфокоммуникационных технологиях. М.: ФИЗМАТЛИТ, 2017. 400 с.
5. Рокотянский М. Стоимость операций в тактах ЦП. [Электронный ресурс]. URL: https://habr.com/ru/company/otus/blog/343566 (дата обращения: 10.08.2021).
6. Ananda Mohan Residue Number Systems. Theory and Applications. Springer International Publishing Switzerland, 2016. 351 р.
7. Omondi A., Premkumar B. Residue Number Systems: Theory and Implementation. Imperial College Press. UK, 2007. 296 р.
8. Yones D. Comparative Study on Different Moduli Sets in RNS. International Conference on Computer System and Industrial Informatics (ICCSII), 2012. P. 1–6.
9. Mohan P.V. Residue Number Systems. Algorithms and Architectures. Springer Science + Business Media New York, 2002. 254 р.
10. Бабенко Л.К., Ефременков И.Д., Мирошников Д.А. Использование избыточных модулярных кодов при разработке отказоустойчивых запросно-ответных систем распознавания спутника // Фундаментальные исследования. 2017. № 12–2. С. 292–296.

В настоящее время реализацию таких глобальных отечественных проектов, связанных с освоением природных богатств, расположенных на шельфе Северного Ледовитого океана, невозможно представить без использования низкоорбитальных систем спутниковой связи (НССС). Однако по мере увеличения числа группировок НССС возрастает вероятность навязывания приемнику спутниковой связи, который располагается на необслуживаемом объекте управления (НОУ), ретрансляционной помехи. В качестве такой помехи выступает ранее перехваченный правильный сигнал управления, который передавался с космического аппарата (КА) приемнику НОУ. Чтобы предотвратить попытку навязывания перехваченного сигнала в работе [1], предлагается использовать систему опознавания КА. Для обеспечения высокой скорости определения статуса спутника в работах [2, 3] предлагается реализовать протоколы аутентификации с использованием параллельных кодов системы остаточных классов (СОК). Однако избыточные коды СОК можно также применять для коррекции ошибок, которые могут возникнуть при вычислениях в протоколах аутентификации. Для достижения данной цели коды СОК используют позиционно-интервальную характеристику (ПИХ). Поэтому модификация алгоритма вычисления позиционной интервальной характеристики модулярных кодов для коррекции ошибок является актуальной задачей.

Основным достоинствам кодов СОК является параллельное выполнение модульных аддитивных и мультипликативных операций [4, 5]. Высокая скорость достигается за счет отсутствия обмена промежуточными результатами между основаниями СОК. Тогда ошибка, возникшая в остатке по одному основанию, не будет оказывать влияния на другие остатки кода СОК. Это свойство используется при построении избыточных модулярных кодов, в которых для коррекции ошибочного остатка необходимо вычислить позиционно-интервальную характеристику.

Целью работы является снижение схемных затрат на коррекцию ошибочного остатка СОК за счет модификации алгоритма вычисления ПИХ.

Материалы и методы исследования

Основные принципы построения кодов СОК достаточно полно раскрыты в работах [4–6]. В коде СОК кодовая комбинация представляет собой кортеж остатков:

missing image file (1)

где missing image file; mi – основание кода СОК; missing image file; missing image file.

Произведение оснований кода СОК определяет размер рабочего диапазона:

missing image file (2)

Так как коды СОК представлены в алгебраической системе «кольцо», то справедливо:

missing image file (3)

missing image file (4)

missing image file (5)

где missing image file; missing image file; missing image file.

В протоколе аутентификации [3], который обеспечивает минимальное время опознавания КА за счет кода СОК, используются: W – секретный ключ КА, а также числа С и В для генерации и проверки времени применения n-го сеансового ключа С(n) и B(n), где missing image file. Протокол представлен в таблице.

Протокол аутентификации в коде СОК

Ответчик

 

Запросчик

Секретные параметры в СОК

missing image file

m1,…., mk – модули

missing image file

 

missing image file

Исходный статус КА

 

missing image file

Изменение секретных параметров протокола

 

missing image file

Измененный статус

 
 

Вопрос

missing image file

Окончание таблицы

Ответчик

 

Запросчик

missing image file

Вычисляются ответы

 
 

Проверка ответов

missing image file

missing image file – КА «свой»

Использование модулярных кодов позволяет повысить скорость проводимых вычислений. В работе [5] показано, что для выполнения операции умножения двух 128-битовых операндов максимально требуется 7 CPU Clock Cycles (тактов центрального процессора). Если исходные данные представить в виде 4×32бит, то потребуется 5 тактов CPU Clock Cycles, что в 1,4 раза меньше. Таким образом, очевидно, что применение модулярных кодов позволяет сократить время на опознавание спутника.

Для построения кодов СОК, способных исправлять ошибки в одном остатке, используются два контрольных основания [6–9], для которых истинно неравенство:

missing image file (6)

В результате получается полный диапазон кода СОК:

missing image file (7)

Тогда комбинация кода СОК считается разрешенной, если выполнено условие:

missing image file (8)

Для проверки условия (8) можно использовать обратное преобразование из СОК в позиционный код (СОК-ПК) с использованием Китайской теоремы об остатках (КТО):

missing image file (9)

где missing image file – ортогональный базис для кода СОК, состоящего из k+2 оснований; missing image file; ui – вес ортогонального базиса; missing image file; missing image file.

Условие (8) показывает, что для исправления ошибочного остатка по одному из оснований необходимо определить позицию числа missing image file относительно рабочего диапазона. Поэтому для достижения поставленной цели в кодах СОК используются позиционно-интервальные характеристики. Непозиционные избыточные коды СОК характеризуются многовариантностью по использованию ПИХ. В работе [8] для исправления ошибки в одном основании предлагается использовать метод проекции, в котором поочередно из избыточной комбинации СОК удаляются остатки. Полученную комбинацию переводят в позиционный код и сравнивают с Mk. Условие (8) будет выполнено только при удалении ошибочного остатка. В качестве недостатка метода проекции можно отметить последовательный характер определения ошибочного остатка. Кроме того, необходимо выполнять перевод СОК-ПК при изменяющемся кортеже оснований, что требует пересчета ортогональных базисов для выполнения (9). В работе [9] предлагается использовать вычисления следа числа. Для определения ошибочного остатка необходимо из кодограммы СОК последовательно в течение k итераций вычитать константы нулевизации. Если код СОК не содержит ошибки, то в конечном результате должна получиться нулевая комбинация. В противном случае вычисленные остатки missing image file. По величине полученного следа можно однозначно определить и исправить ошибочный остаток. Однако данный алгоритм не может быть реализован параллельно, так выбор констант нулевизации зависит от результата, полученного на предыдущей итерации.

Устранить данные недостатки можно с помощью алгоритма вычисления ПИХ, приведенного в работе [10]. Однако он обладает недостатком – вычисления ПИХ проводятся по большему модулю missing image file, что увеличивает схемные затраты. Для устранения данного недостатка проведем его модификацию.

Для проверки выполнения условия (8) найдем ПИХ, используя выражение:

missing image file (10)

где [ ] – целая вычисленного частного; missing image file – позиционная характеристика ранг числа Y, которая определяет количество переходов за Mk+2 при выполнении перевода СОК-ПК.

В работе [7] доказано, что ортогональные базисы для полного missing image file и рабочего missing image file диапазонов подобны. Следовательно, для них справедливо:

missing image file (11)

где missing image file.

На основе свойства (11) справедливо равенство:

missing image file (12)

В этом случае выражение (10) можно представить:

missing image file (13)

где missing image file – ранг числа Y в коде СОК, состоящего из k оснований.

Позиционно-интервальная характеристика, определяемая (10), может принимать значения от 0 до missing image file. Значит, используя изоморфизм, порожденный КТО, можно перейти от вычислений по одному модулю missing image file к параллельным вычислениям по контрольным основаниям mk+1, mk+2. Тогда:

missing image file (14)

Для выполнения (13) используется LUT-таблица, содержащая missing image file ячеек памяти запоминающей матрицы. При использовании модифицированного алгоритма вычисления ПИХ потребуется missing image file. Очевидно, что N2 < N1.

Результаты исследования и их обсуждение

Пусть имеем информационные модули m1 = 7, m2 = 17, m3 = 19 и два контрольных m4 = 29, m5 = 31. Диапазоны кода СОК: рабочий Mk = 2261, полный Mk+2 = 2032639, контрольный missing image file. Для данных оснований получаем ортогональные базисы:

missing image file missing image file

missing image file missing image file missing image file

Представим их согласно выражению (12):

missing image file missing image file

missing image file missing image file missing image file

Пусть на вход блока вычисления ПИХ подается код missing image file. Тогда ранг числа Y по информационным модулям равен:

missing image file

Тогда ПИХ равна:

missing image file

Так как ПИХ равна нулю, то комбинация является разрешенной, т.е. Y < Mk.

Пусть в процессе выполнения протокола аутентификации произошла ошибка и на вход блока ПИХ поступила комбинация missing image file. Тогда ранг числа Y* равен:

missing image file

Тогда ПИХ равна

missing image file

Получили: ПИХ равен missing image file), где missing image file, i = 4,5.

Воспользуемся алгоритмом вычисления ПИХ [10]. Получаем:

missing image file

Для этого значения ПИХ вектор ошибки Δкорр = (2,0,0,0,0). Коррекция дает:

Y = Y* – Δкорр = missing image file

Модифицированный алгоритм вычисления ПИХ показал аналогичный результат по сравнению с прототипом, для которого требуется missing image file ячеек памяти LUT-таблицы. При этом для модифицированного алгоритма вычисления ПИХ используется missing image file ячеек памяти запоминающей матрицы LUT-таблицы. Очевидно, что поставленная цель, направленная на снижение схемных затрат, достигнута.

Заключение

В статье показан протокол аутентификации спутника, реализованный в коде СОК. Применение данного кода за счет параллельных вычислений позволяет не только уменьшить время на опознавание КА, но и корректировать ошибки, которые могут возникнуть в процессе работы системы «свой – чужой» для НССС. С целью снижения схемных затрат на реализацию запросно-ответной системы была проведена модификация алгоритма вычисления ПИХ. Поставленная цель достигнута благодаря изоморфизму Китайской теоремы об остатках. В статье рассмотрен пример реализации модифицированного алгоритма вычисления ПИХ. Полученные результаты совпали с результатами прототипа, для которого требуется N1 = 808201 ячеек памяти LUT-таблицы. При этом для модифицированного алгоритма вычисления ПИХ используется N2 = 1802 ячеек памяти запоминающей матрицы LUT-таблицы. Очевидно, что поставленная цель, направленная на снижение схемных затрат, достигнута.

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 20-37-90009.


Библиографическая ссылка

Чистоусов Н.К., Чипига А.Ф., Калмыков И.А., Ефременков И.Д., Калмыкова Н.И. МОДИФИКАЦИЯ АЛГОРИТМА ВЫЧИСЛЕНИЯ ПОЗИЦИОННО-ИНТЕРВАЛЬНОЙ ХАРАКТЕРИСТИКИ МОДУЛЯРНЫХ КОДОВ ДЛЯ КОРРЕКЦИИ ОШИБОК // Современные наукоемкие технологии. – 2021. – № 8. – С. 137-142;
URL: https://top-technologies.ru/ru/article/view?id=38792 (дата обращения: 19.10.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074