Алгоритм преобразования из модулярного кода в полиадическую систему оснований для систем обнаружения и коррекции ошибок

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 681. 3
АЛГОРИТМ ПРЕОБРАЗОВАНИЯ ИЗ МОДУЛЯРНОГО КОДА В ПОЛИАДИЧЕСКУЮ СИСТЕМУ ОСНОВАНИЙ ДЛЯ СИСТЕМ ОБНАРУЖЕНИЯ И КОРРЕКЦИИ ОШИБОК
Стрижков Н. С., Калмыков М. И.
Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Северо-Кавказский федеральный университет»,
Ставрополь, e-mail: kia762@yandex. ru
В настоящее время системы контроля и управления доступом (СКУД), использующие биометрическую идентификацию и аутентификацию, нашли широкое применение в различных областях. Как правило, в таких устройствах используют статические образы авторизованного пользователя. Однако данные системы слабо защищены от обмана муляжом. Данного недостатка лишены методы биометрической идентификации пользователя по его динамическим параметрам. Для повышения эффективности таких систем предлагается использовать цифровую обработку сигналов (ЦОС), реализованную на основе полиномиальной системы классов вычетов (ПСКВ). Предлагается алгоритм, позволяющий осуществлять преобразование непозиционного кода ПСКВ в позиционный двоичный код. Использование полиадической системы оснований позволяет также осуществлять процедуру поиска и коррекции ошибок, возникающих в процессе функционирования.
Ключевые слова: остатки, полиномиальная система классов вычетов, коэффициенты обобщенной полиадической системы счисления, обнаружение и коррекция ошибок.
ALGORITHM FOR CONVERTING FROM THE MODULAR CODE THE POLYADIC SYSTEM BASES FOR SYSTEMS ERROR DETECTION AND CORRECTION Strizhkov N.S., Kalmykov M.I.
Federal state Autonomous educational institution higher professional education «North-Caucasian Federal University, Stavropol, e-mail: kia762@yandex. ru
Currently, system access control system (ACS), using biometric identification and authentication are widely used in various fields. Typically, such devices rely on static images of the authorized user. However, these systems are vulnerable to fraud hoax. This deficiency deprived of biometric user identification by its dynamic parameters.
To increase the effectiveness of such systems is proposed to use digital signal processing (DSP) capabilities using polynomial system of residue classes (PSKV). An algorithm is proposed to allow for the conversion code nonpositional PSKV position in binary code. Using polyadic system bases also allows the search procedure and correct errors that occur during operation
Keywords: residues, polynomial system of residue classes, the coefficients of the generalized polyadic notations, detection and correction of errors.
Введение
В настоящее время существует множество методов обеспечения информационной безопасности автоматизированных систем. Одним из перспективных направлений в области защиты информации является биометрическая аутентификация, для которой необходимо использовать цифровую обработку сигнала (ЦОС). Применение методов ЦОС позволяет повысить эффективность работы систем, используемых для биометрической идентификации и аутентификации пользователя. Очевидно, что использование той или иной математической модели ЦОС может оказать существенное влияние на эффективность работы всей системы контроля и управления доступом (СКУД).
Постановка задачи исследований
Биометрическая идентификация и аутентификация пользователя является одним из перспективных направлений защиты ин-
формации от НСД. В настоящее время наибольшее распространение получили системы контроля и управления доступом, базирующееся на статических параметрах пользователя. Однако данные системы слабо защищены от обмана муляжом. Данного недостатка лишены методы биометрической идентификации пользователя по его динамическим параметрам.
Однако для эффективной работы систем контроля управления доступом (СКУД), использующих динамическую биометрию пользователя, необходимо осуществлять первичную обработку образа. Как правило, такая обработка основана на методах цифровой обработки сигналов. Известно, что большинство методов первичной обработки сигналов базируется на ортогональных преобразованиях, определенных в поле комплексных чисел, т. е. дискретном преобразовании Фурье, которое имеет ряд недостатков: низкая скорость обработки сигналов-
аддитивные и мультипликативные погрешности из-за иррациональных значений поворачивающих коэффициентов Ж кп. Кроме того, необходимо, чтобы возникающие при первичной обработки сигналов ошибки, были устранены в процессе этих вычислений [3].
Решить данные проблемы можно за счет применения специальной системы кодирования, которая бы поддерживала математическую модель ЦОС, обладающую свойством кольца или поля, а также была способна обнаруживать и корректировать ошибки. Данным требованиям удовлетворяет полиномиальная система классов вычетов (ПСКВ) [2−5,9]. Если в качестве оснований новой алгебраической системы выбрать минимальные неприводимые многочлены р (г) поля 0?(р'-'), то любой сигнал х (п), представленный в полиномиальной форме Х (г), удовлетворяющий условию
х (г) е Рпол, (1)
где Рпол =ПР. (7) = ^ ~ ^
1=1
можно представить в виде п-мерного вектора
Х (7) = («(г), «2(z),…, «п (г)), (2)
где а1 (г) = rest (A (г)/р1 (г), , = 1,2,…, п.
Если сигнал с выхода аналого-цифрового преобразователя (АЦП) представить в полиномиальной форме, то его можно закодировать в ПСКВ в виде совокупности остатков, полученных в результате деления исходного полинома на минимальные многочлены, определяемые в расширенных полях Галуа. Тогда операции сложения, вычитания, умножения над операциями можно свести к аналогичным операциям над остатками. Переход к выполнению арифметических действий над малоразрядными остатками позволяет повысить быстродействие вычислительной системы [4−8].
Наряду с повышением скорости обработки данных ПСКВ позволяет обеспечить свойство устойчивости к ошибкам, которые возникают в процессе функционирования непозиционного устройства ЦОС [1,4,7−10].
Анализ работ показал, что полином, представленный в ПСКВ, не содержит ошибки, если справедливо
к
А (г) еГраб (г) = П Р, (г), (3)
1=1
где к — количество информационных оснований ПСКВ (к& lt-п).
В противном случае, если в результате выполнения вычислений произошла ошибка, то полином А*(г) будет лежать вне рабочего диапазона.
Для обнаружения и коррекции ошибок в кодах ПСКВ используются позиционные характеристики [1,4,7−10]. Особое место среди таких позиционных характеристик занимают коэффициенты обобщенной полиадической системы (ОПС) [6].
Пусть задана полиномиальная система классов вычетов, состоящая из пяти минимальных многочленов. В данном случае определены следующие полиномиальные основания:
— рабочие р1(г) = г +1, р2(7) = 72 + 7 +1, р3 (г) = г4 + г3 + г2 + г +1-
— контрольные р4(г) = г4 + г3 +1, р5(г) = г4 + г +1.
В обобщенной полиадической системе полином А (г) представляется в виде
А (г) = а1 + а 2 Р1(г) + аз Р1(г)р 2 (г) +
+ а4 (г)Р1 (г)Р2 (г)Рз (г) +
+ а5 (г)Р1 (г)Р2 (г3 (г)Р4 (г) (4)
Если наложить ограничение на количество информационных оснований (к=3), то рабочий диапазон будет равен
рбм (г)=ГГ р,(г) =г 7 +г 6 +г 5+г 2+г+1.
1=1
Тогда равенство (3) можно представить в следующем виде
А (г) = а1 + а2 р1 (г)+ а3 р1 (г)р2 (г) +,
+ а4 (г)Рраб (г) + а5 (г)Рраб Р4 (). (5)
Из последнего равенства наглядно видно, что если полином А (г), представленный в ПСКВ, не содержит ошибок, т. е. удовлетворяет условию
ае§ А (г) & lt- ае§ Рраб (г), (6)
то значения старших коэффициентов ОПС в равенстве (5) должны быть нулевыми. Другими словами, а (г)=0, а (г)=0. В противном случае, полином содержит ошибки.
Для эффективной реализации вычислений коэффициентов ОПС по значениям остатков ПСКВ был разработан алгоритм
перевода из кода ПСКВ в код ОПС, который базируется на китайской теореме об остатках.
А (г) =? а, (г)ВІ (г) т0арпот{z), (7)
і=1
где В, (7) = 1mod р, (г) — ортогональный базис і-го основания ПСКВ- к — количество информационных оснований- г — количество контрольных оснований.
Представив ортогональные базисы в виде коэффициентов ОПС, получаем
А = аі Ігї^-Уі+г ]+…
+"к+гІ, о,…, гк: г, (8)
где уу — коэффициенты ОПС у-го ортогонального базиса.
Тогда, проведя умножение вычетов а. на соответствующие коэффициенты ОПС по-модульно и поразрядно, при этом, учитывая превышение модуля р (г) как перенос единицы при суммировании результата, коэффициенты ОПС могут быть найдены
а =
+
? ау (г)у (г)
У=1 Рі(г)
+
7 + р,(г) '
(9)
где ё. (г) — переполнение, полученное при суммировании по модулю р. (г).
Одним из важнейших свойств кодов ПСКВ, определенных в расширенных полях Галуа 0?(ру), является отсутствие меж-разрядных переносов при вычислении результата по модулю р (г). Это позволяет свести операцию итеративного получения коэффициентов обобщенной полиадической системы к однотактовой процедуре, определяемой выражением
аі (г) =
? ау (г)У (г)
У=1
(10)
, п — количество оснований
где / = 1,2, кода ПСКВ.
На базе данного алгоритма был разработан преобразователь, который осуществляет параллельное вычисление коэффициентов смешанной системы счисления, реализованное с помощью нейроподобных вычислительных устройств [6]. При этом характерной чертой патентованного устрой-
ства является то, что не только обнаруживает и корректирует ошибки, но и осуществляет обратное преобразование из непозиционного кода ПСКВ в позиционный двоичный код.
Предложено для реализации данной процедуры использовать коэффициенты обобщенной полиадической системы (ОПС). Разработана нейронная сеть, позволяющая осуществлять преобразование ПСКВ-ОПС, для поля Галуа О Б (24), с основаниями р1 (г)=г+1-р2(г)=г2+г+1-р3(г)=г4+г3+г2+г+1- р4(г)=г4+г3+1- р5(г)=г4+г+1. Тогда ортогональные базисы ПСКВ, представленные в ОПС равны:
Б1(2)=214+213+212+211+210+29+28+27+26+25+ +г4+г3+г2+г+1=[1 г г3+г г3 г3+г2+г]-
В2(г)=г14+г13+г11+г10+г8+г7+г5+г4+г2+г= =[0 г г3+г2+г г3+г2+1 г3+г2 ]-
В (г)=г14+г13+г12+г11+г9+г8+г7+г6+г4+г3+
+г2+г=[0 0 г2+1 г3+г2+г ]-
г12+г11+г9+
=[0 0 0 г2+г г3+г2+г ]-
В4(г)=г14+г13+г12+г11+г9+г7+г6+г3=
В5(г)=г12+г9+г8+г6+г4+г3+г2+г=[0 0 0 0 г]. Пусть дан полином
А (г)= г6+г5+г4+г+1 =
=(1, г+1, г3+г2+г+1, г3+г2+г, г3+г),
принадлежащий
Рраб (г)=г7+г6+г5+г2+г+1.
Воспользуемся выражением (10). Получаем значения коэффициентов ОПС
а](г)=1, а2(г)=г+1, а3(г)=г3+г2+г+1, а (г)=0, а (г)=0.
Так как старшие коэффициенты равны нулю, то это свидетельствует о том, что данный полином не содержит ошибки.
Пусть в коде ПСКВ произошла ошибка по
первому основанию и ее глубина Аа1 (г) = 1.
Тогда А*(г)=(0, г+1, т3+г2+г+1, г3+2?+г, г3+г).
Воспользуемся выражением (10) и вычислим значения коэффициентов ОПС. В результате старшие коэффициенты ОПС равны соответственно
а4(г) = г3 и а5(г) = г3 + 72 + г.
Таким образом, очевидно, что кодограмма ПСКВ содержит ошибку.
В таблице 1 приведены значения старших коэффициентов ОПС при различных однократных ошибках для выбранного набора оснований ПСКВ.
+
+
+
+
Таблица 1
Зависимость коэффициентов ОПС от ошибки
Коэффициенты ОПС
Величина ошибки a 4 (z) a5 (z)
Да1 = 1 z3 3 2 z +z2 +z
Да2 = 1 z +z + 1 z3 +z 2
Да2 = z z3 +z2 +z z3 + z
Да3 = 1 z2+1 z3 +z2 +z
Да3 = z z3 + z z3 +z2 +z + 1
Да3 = z 2 3 2 z +z2 z3 +z 2
СЛ z = СЛ 8 Д 1 z3 + z
=1 Д 2 z 2 +z 3 2 z +z2 +z
Да4 = z 3, 2 z + z 3 2 z + z + z + 1
Да4 = z 2 1 3 2 z +z2
Да4 = z z 3 z +z + 1
Да5 = 1 0 z
Да5 = z 0 z 2
2 z = «О 8 Д 0 z3
3 z = 8 Д 0 z + 1
Анализ таблицы 1 показывает, что в выбранной системе оснований ПСКВ с двумя контрольными основаниями можно однозначно определить местоположение и глубину ошибки в модулярном коде. При этом характерной чертой данной позиционной характеристики является то, что она может одновременно использоваться при переводе из ПСКВ в позиционный код. Таким образом, при реализации непозиционного СП ЦОС, который используется в СКУД, можно обеспечить сокращение схемных затрат по сравнению с классическим алгоритмом перевода.
Вывод
Современные системы контроля и управления доступом широко используют биометрические средства идентификации и аутентификации пользователя. Повысить эффективность их работы можно за счет
применения алгоритмов ЦОС, реализованных в полиномиальной системе классов вычетов. В работе показана возможность осуществления поиска коррекции ошибок на основе коэффициентов обобщенной полиадической системы. Применение данной позиционной характеристики позволяет сократить схемные затраты по сравнению с классической реализацией СП ЦОС класса вычетов за счет совмещения операций обратного перевода в ПСС и процедур поиска и коррекции ошибок.
Список литературы
1. Гахов В. Р., Емарлукова Я. В., Калмыков И. А. Устройство обнаружения и коррекции ошибок в кодах полиномиальной системы классов вычетов // Патент России № 2 300 801. 30. 06. 2005. Бюл. № 16 от 10. 06. 2007.
2. Емарлукова Я. В., Калмыков И. А., Зиновьев А. В. Высокоскоростные систолические отказоустойчивые процессоры цифровой обработки сигналов для инфо-
телекоммуникационных систем // Инфокоммуникаци-онные технологии. Самара. — 2009. — № 2. — С. 31−37.
3. Калмыков И. А., Бережной В. В., Червяков Н. И., Щелкунова Ю. О., Шилов А. А. Нейросетевая реализация в полиномиальной системе классов вычетов операций ЦОС повышенной разрядности // Нейрокомпьютеры: разработка и применение. — 2004. — № 5−6.
— С. 94.
4. Калмыков И. А., Бережной В. В., Червяков Н. И., Щелкунова Ю. О., Шилов А. А. Архитектура отказоустойчивой нейронной сети для цифровой обработки сигналов // Нейрокомпьютеры: разработка и применение. — 2004. — № 12. — С. 51−57.
5. Калмыков И. А., Чипига А. Ф. Структура нейронной сети для реализации цифровой обработки сигналов повышенной разрядности // Вестник Ставропольского государственного университета. — 2004.
— Т. 38. — С. 46.
6. Калмыков И. А., Лободин М. В., Алексишин Е. В., Щелкунова Ю. О. Нейронная сеть для вычисления коэффициентов обобщенной полиадической системы,
представленных в расширенных полях Галуа О Б (2у) // Патент России № 2 258 956. Бюл. № 23 от 20. 08. 2005.
7. Лободин М. В., Чипига А. А., Калмыков И. А. Устройство спектрального обнаружения и коррекции в кодах полиномиальной системы классов вычетов // Патент России № 2 301 441. Бюл. № 17 от 20. 06. 2007.
8. Петлеванный С. В., Калмыков И. А., Сагдеев А. К., Емарлукова Я. В. Устройство для преобразования числа из полиномиальной системы классов вычетов в позиционный код с коррекцией ошибки // Патент России № 2 309 535. 31. 03. 2006. Бюл. № 30 от 27. 10. 2007.
9. Хайватов А. Б., Калмыков И. А. Математическая модель отказоустойчивых вычислительных средств, функционирующих в полиномиальной системе классов вычетов // Инфокоммуникационные технологии. — 2007. — Т.5. — № 3. — С. 39−42.
10. Червяков Н. И., Калмыков И. А., Щелкунова Ю. О., Бережной В. В. Математическая модель нейронной сети для коррекции ошибок в непозиционном коде расширенного поля Галуа // Нейрокомпьютеры: разработка и применение. — 2003. — № 8−9. — С. 10−17.

ПоказатьСвернуть
Заполнить форму текущей работой