WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


На правах рукописи

КРЮКОВ Дмитрий Алексеевич

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

Специальность 05.13.15 – Вычислительные машины, комплексы и компьютерные сети

АВТОРЕФЕРАТ

Диссертации на соискание ученой степени кандидата технических наук

Москва – 2012

Работа выполнена на кафедре «Корпоративные информационные системы» федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Московский государственный технический университет радиотехники, электроники и автоматики» (МГТУ МИРЭА).

Научный консультант: Андрианова Елена Гельевна кандидат технических наук, доцент, доцент кафедры «Корпоративные информационные системы» МГТУ МИРЭА

Официальные оппоненты: Бутузов Станислав Юрьевич доктор технических наук, доцент, начальник Учебно-научного комплекса автоматизированных систем и информационных технологий (УНК АСИТ) Академии ГПС МЧС России Дешко Игорь Петрович кандидат технических наук, доцент, директор Центра сетевого управления и телекоммуникаций (ЦСУиТ) МГТУ МИРЭА

Ведущая организация: ОАО «Институт электронных управляющих машин им. И.С. Брука»

Защита состоится «19» декабря 2012 г. в 15-00 на заседании диссертационного совета Д 212.131.05 МГТУ МИРЭА по адресу:

Москва, 119454, пр-т Вернадского, д. 78, Д4

С диссертацией можно ознакомиться в библиотеке МГТУ МИРЭА.

Автореферат разослан «16» ноября 2012 г.

Отзывы на автореферат в двух экземплярах, заверенные печатью, просим направлять по адресу 119454, г. Москва, пр-т Вернадского,78, диссертационный совет Д 212.131.

Ученый секретарь Андрианова диссертационного совета Д 212.131.05 Елена Гельевна кандидат технических наук, доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ



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

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

Конструктивно МКПИ состоят из персональных идентификаторов, интерфейсов (каналов связи) и хост-компьютеров. Компоненты МКПИ выполняют перечисленные функции в системе, ядром которой и определяющим компонентом является персональный идентификатор.

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

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

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

Объектом исследования являются микрокомпьютерные комплексы персональной идентификации (МКПИ), построенные на основе стандартов SMART-карт и технологий радиочастотной идентификации (RFID).

Предмет исследования определяют следующие основные задачи:

1. Провести анализ существующих организаций обработки, хранения и ввода-вывода данных в МКПИ. Определить существенные критерии классификации МКПИ.

2. Рассмотреть перспективы развития методов обработки, хранения и ввода-вывода данных, повышающие надежность МКПИ.

Предложить качественные и количественные параметры для оценки алгоритмов хранения и обработки данных в МКПИ.

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

4. Разработать методы и алгоритмы повышения надежности МКПИ с учетом особенностей аппаратно-программных платформ.

5. Рассмотреть возможность практического применения разработанных методов помехоустойчивого кодирования в реальных МКПИ и включить научные положения в учебный процесс магистерской подготовки.

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

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

Применительно к проблематике диссертации результативно использован комплекс базовых методов сравнения, моделирования и отображения содержания и структуры исследуемых объектов в форме математических символов, методов. Изложены доказательства и условия применимости методов и алгоритмов обработки, хранения и ввода-вывода данных в МКПИ. Проведена модернизация существующих методов хранения информации и ввода-вывода данных.

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

Практическая значимость работы подтверждается:

1. Внедрение результатов работы в системы контроля доступа на базе технологии RFID в ЗАО «Норси-Транс». Разработанные решения используются для выполнения практических задач связанных с повышением надежности систем радиочастотной идентификации. В соответствии с требованиями, предъявленными к системе RFIDидентификации, процедуры кодирования и декодирования данных были полностью перенесены на хост-компьютер. Испытания показали коррекцию ошибок в 80% случаев.

2. Результаты работы использованы в ОАО «ГИРООПТИКА» для решения практических задач связанных с повышением надежности персональных устройств на базе SMART-карт, подтверждающих полномочия доступа к специализированным базам данных. Результаты позволили на 40% повысить надежность SMART-карт с персональными сведениями. В 90% случаев данные в МКПИ были корректированы.

3. Методы и алгоритмы обработки, хранения и ввода-вывода данных в МКПИ использованы в ООО « НТЦКТ «Тор» при разработке и изготовлении идентификаторов для имитаторов стрельбы Малого артиллерийского полигона (МАП), поставляемого в рамках Рособоронзаказа. Решения позволили на 25-30% сократить время восстановления ошибок в имитаторах.

4. Результаты использованы ООО «Аналитик» в электронных ключах и SMART-картах eToken, предназначенных для обеспечения информационной безопасности. Позволили в 80% случаев выявить и исправить ошибки хранения информации и исключить трудозатраты на низкоуровневое восстановление данных.

5. Теоретические результаты использованы в учебном процессе МГТУ МИРЭА на кафедре «Корпоративные информационные системы» магистрами по направлению подготовки 230400.«Информационные системы и технологии».

6. Научные положения диссертации включены в учебный процесс МАИ подготовки бакалавров по направлению 2304«Информационные системы и технологии» по направлению «Конструирование и производство средств вычислительной техники» на кафедре 307 факультета «Системы управления, информатика и электроэнергетика».

Апробация работы. Результаты диссертационного исследования докладывались и получили одобрение на 10-ой научно-практической конференции ФГУП «НИИ «Восход» «Современные информационные технологии в управлении и образовании», 60 и 61-ой Научнотехнической конференции МГТУ МИРЭА, научно-практической конференции ФГУП «НИИ «Восход» «Проблемы функционирования государственной системы изготовления, оформления и контроля паспортно-визовых документов нового поколения» в 2011, 2012 гг.

Публикации. По теме диссертации автором единолично опубликовано 5 печатных работ. При этом основные результаты диссертации изложены в 5 статьях в рецензируемых научных изданиях, определенных ВАК РФ для опубликования результатов кандидатских диссертаций.

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

Основная часть работы изложена на 177 страницах машинописного текста, содержит 47 рисунков и 10 таблиц. Текст работы предваряет развитый глоссарий терминов, относящихся к теме диссертации.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Таблица 1. Персональные идентификаторы в МКПИ Персональный Интегральные Объем памяти Категории идентификатор микросхемы для EEPROM (Кбайт) персональной реализации логики информации SMART-карты Микропроцессор 64-512 Индивидуальная RFID-метки Электронная память, 1-100 Прикладная, программируемый удостоверяющая микропроцессор Магнитные карты Отсутствует <1 Финансовая, удостоверяющая Биометрические Центральный 128-512 Личная, паспорта процессор, сопроцессор социальнозначимая Устанавливаются требования к алгоритмам повышения надежности МКПИ, проводится анализ возможностей повышения надежности путем модификации обработки, хранения и ввода-вывода данных в персональных идентификаторах МКПИ, проводится анализ типичных ошибок и сбоев в блоках электрически программируемого постоянного запоминающего устройства (ЭСППЗУ) и магнитных картах, производится постановка задач исследования.





Во второй главе предлагаются концепции организации ввода вывода в МКПИ для повышения надежности. Установлено, что для МКПИ, имеющих в составе SMART-карты либо биометрические паспорта наиболее подходящей является концепция организации вводавывода, при которой процедуры кодирования и декодирования данных размещаются в персональном идентификаторе. Для карт с магнитной полосой единственной возможной является концепция организации ввода-вывода данных с размещением процедур кодирования, декодирования информации на хост-компьютере. МКПИ на основе технологии RFID удовлетворяют обе концепции, выбор зависит от конкретной задачи.

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

Разработана модель случайного выбора страниц для вводавывода данных в ЭСППЗУ, для чего проведены исследования зависимости числа циклов стирания/записи страниц контроля от распределения процедур записи между страницами данных. Перезапись Pi d i-ой страницы данных, составляет вероятность. События перезаписи страниц данных можно рассматривать как независимые, а вероятность k 1 Pid холостой процедуры записи равна . Зависимые страницы, iперезаписываемые в результате изменения i-ой страницы данных, определяются с помощью матрицы зависимостей , размерности k m, m N k - число страниц контроля. Введены величины id - число где c страниц контроля, зависящих от i-ой страницы данных и - число j страниц данных, от которых зависит j-ая страница контроля.

Доказано утверждение 1. Если код имеет минимальное расстояние Хемминга d между кодовыми словами, то для любых i 0 i k таких, что, выполнены неравенства:

id d 1.

c Для величин всегда выполнены неравенства:

j mc c 1 1, k d 1.

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

c Pic Определен вектор вероятностей Pc P0c,, Pm1 из вероятности того, что при процедуре записи данных произошла перезапись хотя бы одной страницы данных, от которой зависит i-ая страница контроля и c Pic вектор Pc P0c,, Pm1, из вероятностей перезаписи соответствующих Pc Pc страниц контроля. Связь между векторами и имеется с помощью величины – условной вероятности того, что при наступлении события изменения зависимых страниц данных, i-ая страница контроля также изменится.

Доказано утверждение 2 о том, что данные вектора связанны с матрицей зависимости следующим образом ln 1m Pc ln 1k Pd . (1) Pd Pd Так же приведено доказательство утверждения 3: если и два вектора вероятностей для страниц данных такие, что Pd Pd, тогда Pc Pc для соответствующих векторов вероятности и для страниц контроля справедливо неравенство Pc Pc.

Pc Сумма элементов вектора вероятностей интерпретирована как Ec математическое ожидание числа перезаписываемых страниц Ed контроля. Таким же образом определена величина числа записываемых страниц данных:

m1 mcc Ec , (2) P P i i i0 ik d Ed . (3) P i iДля помехоустойчивого кода, задаваемого на страницах памяти, R Pd Pd определена функция от вектора вероятности :

def Ec Pd R Pd . (4) Ed Pd Поведение функции во многом описывает эффективность исследуемого кода в плане использования части памяти для контрольных данных.

Далее определен следующий показатель эффективности кода:

0,, m1 Pc (5) max Pjd Величина характеризует то, насколько чаще происходит перезапись каждой страницы контроля, чем самой нагруженной страницы данных. Параметр является очень важным показателем.

Так как число циклов стирания/записи страниц памяти ЭСППЗУ ограничено, рано или поздно происходит их выход из строя, и величина может охарактеризовать число испорченных страниц контроля до первого выхода из строя страницы данных.

При достижении гарантийного значения числа циклов стирания/записи для i-ой страницы контроля число циклов перезаписи для страниц данных будет не более. Если считать, что при достижении гарантийного числа циклов стирания/записи страница памяти выходит из строя, то в действительности число страниц памяти, i для хранения контрольной информации, равно сумме величин, m округленных до большего целого. Эта величина обозначена :

mm i . (6) iДля анализа избыточности используемого алгоритма кодирования, определены относительный расход памяти и действительный относительный расход памяти :

m m ,. (7) k k Величины и показывают границы применимости кода для рассматриваемого случая.

Рассматривается построение кодов Хемминга для данных, qm 1 qm хранимых в ЭСППЗУ. Рассмотрен код Хэмминга CH , m.

q 1 q Число N страниц памяти ЭСППЗУ, в которых будет размещаться код, в qm общем случае не совпадает с. Но требуемый код C может быть q построен путем применения к коду Хэмминга операции укорочения кода. Защищенность кода CH от ошибок при этом нисколько не уменьшается. Для возможности применения операции укорочения, m параметр кода Хемминга должен удовлетворять неравенству qm m, из которого получена нижняя оценка для числа страниц N q контроля:

m logq N q 1 . (8) Таблица 2 содержит возможные параметры кода CH для страниц m памяти размером 32 байта с минимальными значениями, и относительный расход памяти для каждого кода. В качестве N предложены различные степени двойки как один из наиболее типичных вариантов в ЭСППЗУ.

Относительный расход памяти кода не велик, и уменьшается с q увеличением длины N кодовых слов и мощности алфавита кодирования. Более реалистичную оценку расхода памяти кодом дает действительный относительный расход памяти .

Таблица 2. Коды CH N, N m для 32-битных страниц памяти ЭСППЗУ и алфавита кодирования из двоичных последовательностей длины l.

Мощность q Длина Длина Отн.

Число контр.

кода последовательности расход алфавита символов m N -символа l (бит) памяти кода 128 1 2 8 6.67% 128 2 4 5 4.06 % 128 4 16 3 2.4% 128 8 256 2 (гр. Синглтона) 1.59% 256 1 2 9 3.64% 256 2 4 5 1.99% 256 4 16 3 1.19% 256 8 256 2 (гр. Синглтона) 0.79% 512 1 2 10 1.99% 512 2 4 6 1.19% 512 4 16 4 0.79% 512 8 256 3 0.59% 512 16 65536 2 0.39% 1024 1 2 11 1.09% 1024 2 4 6 0.59% 1024 4 16 4 0.39% 1024 8 256 3 0.29% 1024 16 65536 2 0.2% Матрица зависимостей должна удовлетворять следующим условиям:

1. В каждой строке матрицы не менее двух единиц.

2. Строка, представляющая из себя упорядоченный набор единиц xq 1 x и нулей, встречается в матрице ровно раз, число единиц.

Таким образом, все страницы данных для кода Хемминга qm 1 qm m CH , m имеют от 2 до зависимых страниц контроля. При q 1 q x этом число страниц данных, имеющих зависимых страниц контроля m x1 xx x q 1 Cm qm1 1 q 1 Cmвсего . Каждая страница контроля имеет xc зависимых страниц данных. В случае укороченного кода число i будет меньше.

Операция укорочения кода задается однозначно следующим образом: отбрасываются страницы, имеющие максимальное число зависимых страниц контроля. Выбор удаляемых страниц производится c так, что после их удаления разница между величинами не i c превышает 1 и страницы с меньшим значением при нумерации i страниц данных идут первыми. Исходя из требований к избыточности c кода не более 20%, заключено что.

j Далее доказано утверждение 5: если у кода есть страницы данных, имеющие число зависимостей id 2, то выполнено неравенство m N m cc m 1 m, m 1 N m Иначе выполнено равенство:

m N m cc m 1 m, (9) m 1 N m c c c m 1 CH N, N m где m и - средние величины кодов и j CH N, N m , соответственно.

Для оценки эффективности кода Хемминга произведена так же Pc Pd оценка значений вектора при различных значениях. В качестве iой страницы данных должна выбираться страница с максимальным значением вероятности перезаписи среди еще свободных страниц данных, тогда страницы с наибольшей вероятностью перезаписи будут Pd p1,, pиметь наименьшее число зависимостей. Если и p1 pPd p2,, p векторы вероятностей с вероятностями и такими, что p1 p2, то в силу утверждения 3, если Pd Pd Pd, то для соответствующих векторов вероятностей для страниц контроля Pc выполнено неравенство Pc Pc Pc. Следовательно, зависимость от Pd в значительной степени изучена при исследовании частного случая, p когда все вероятности Pi d равны некоторому значению. В Pic соответствии с формулой (1) все вероятности будут иметь значения:

ic 1 1 p . (10) Ed N m p Тогда, по формулам (2-4): , m ic 1 ic 1 mEc m 1 p m 1 p, 2L i i0 mic m 1 p 1 iR p , 2L N m p R p Интерес представляют графики функции рис. 1, в качестве примера, для первых четырех строк таблицы 1. Так же, в главе c представлена таблица со значениями для представленных в таблице i 1 кодов и показан пример вычисления операции укорочения и c m получения для кода с числом контрольных символов.

i Рис. 1. Графики функций эффективности помехоустойчивого кода для N 1кодов с.

На основании графиков рис. 1 сделан вывод о повышении эффективности кода за счет повышения мощности алфавита кодирования. Более точную информацию об эффективности кода можно получить путем изучения векторной величины (5) и m действительного числа страниц контроля (6), необходимого для обеспечения минимальной целостности. Из графиков рис. 2 можно сделать вывод, что для рассматриваемых кодов приемлемый расход памяти на кодирование начинается при вероятностях не менее 5-20%.

Более наглядно это можно увидеть на графиках действительного относительного расхода памяти (7), приведенных на рис. 3.

Самый эффективный из кодов таблицы 1 имеет приемлемый расход памяти, только начиная с вероятности перезаписи страницы данных около 5%, т.е. при условии, что при каждой процедуре записи в среднем будет перезаписываться не менее 6 страниц данных. В c соответствии с утверждением 5 величины зависимостей j m уменьшаются при увеличении параметра, что влечет большую m эффективность кода с большим значением параметра.

Рис. 2. Графики действительного числа страниц контроля для N 1кодов с.

N 128 N 2Рис.3. Действительный относительный расход памяти (, ).

На основании (9) рост параметра m при отсутствии страниц данных с числом зависимостей более 2 не приведет к существенному R p p изменению функции в окрестности точки. При увеличении q m CH N, N m параметра -значного кода рано или поздно наступит момент, когда все страницы данных будут иметь ровно 2 зависимости, M поэтому, было введено обозначение для минимального значения m q параметра. При достаточно большом значении при N фиксированном, параметр M равен 2. Исходя из (8) можно получить q N 1 условие на q :. Расход памяти в соответствии с (6), (7), (10) 1 1 p Функция является убывающей считаем равным:

p функцией от. В свою очередь является убывающей функцией от параметра M. Следовательно, при уменьшении параметра M действительный относительный расход памяти кода уменьшается.

Уменьшение параметра M может быть достигнуто только увеличением q q параметра кода. Минимальное значение, при котором M становится равным 2, обозначим Q. Таким образом, при малых p значениях вероятности наиболее оптимальным по всем показателям расхода памяти является Q -значный код CH N, N M. Этот код так же p является оптимальным при остальных значениях, поскольку для него достигается граница Синглтона, и потому относительный расход памяти оказывается минимальным.

q В соответствии со структурой проверочной матрицы -кода Хемминга, первая страница контроля получается суммированием по L N модулю 2 всех страниц данных, что составляет побайтовых операций сложения . Для вычисления второй страницы контроля L N также необходимо произвести побайтовых операций , но помимо этого должно быть произведено некоторое количество операций умножения страниц данных на элементы из поля GF q. Для упрощения операции умножения предложено создание в ПЗУ таблиц умножения элементов. С учетом коммутативности операции l2 l lумножения для такой таблицы потребуется около байт памяти.

2 8 l При, размер таблицы будет составлять всего 256 байт памяти, что является допустимым расходом памяти для большинства SMART-карт.

Другое упрощение операции умножения достигнуто при укорачивании qM 1 qM кода Хемминга CH , M до кода CH N, N M. Так как все q 1 q 1 страницы данных при M 2 зависят от всех страниц контроля, приоритет при выборе удаляемой страницы данных может быть отдан любой из них. Удалены должны быть те страницы данных, которым соответствует элемент, умножение на который наиболее трудоемко.

Процедура кодирования для кода SMART-карт значительно упрощена: при кодировании ранее закодированного информационного блока, учитываются только новые данные. Для нахождения нового значения контрольного символа для кодов при характеристике поля равной 2, достаточно прибавить к контрольному символу старое значение информационного символа с соответствующим коэффициентом (при перезаписи страницы данных) и прибавить новое значение с тем же коэффициентом.

Алгоритм декодирования. Для вычисления синдрома достаточно заново вычислить символы контроля и сложить с теми, что есть. Так как число синдромов равно 2, в случае если они не равны оба нулю, SSпервый из синдромов равен величине ошибки, а величина равна Sпозиции ошибки (с единицы). Для выяснения факта наличия ошибки достаточно вычисления только первой контрольной страницы. В случае ошибки на позицию укажет вычисление второй страницы.

CRS q 1,q 1 2t Далее исследуются коды Рида-Соломона для данных, хранимых в ЭСППЗУ. С целью сохранения файловой структуры данных, так же как и в случае кодов Хемминга, было c x i x r x xk r x применено систематическое кодирование , где – i x xm g x остаток от деления многочлена на . Для кодов данного типа также будем выделять в памяти ЭСППЗУ страницы данных и страницы контроля. Кодовые слова построены следующим образом: из каждой t 2t страницы данных выделяется символов, контрольных символов таким же образом размещаются по двум страницам контроля. Тогда, t при любом значении параметра код Рида-Соломона имеет две страницы контроля. Таким образом, каждая страница контроля зависит c c от всех страниц данных, – величины зависимостей и имеют значения q 3. После операции укорочения был получен код CRS N, N m m 2t q 1 Nt , где, удовлетворяющий условию. Также как t и для кодов Хемминга, q 2l, а параметр должен быть таким, чтобы q t t число -символов одной страницы памяти было кратно (т.е.

должен быть степенью двойки).

Детальное изучение расхода памяти для РС-кодов не проводилось, поскольку число страниц контроля всегда равно двум, и они всегда зависят от всех страниц данных. Принципиальные различия между кодами Хемминга и Рида-Соломона проявляются в характеристиках алгоритмов кодирования и декодирования.

Вычислительную сложность процедуры кодирования составляет деление многочлена степени N на порождающий многочлен степени 2t. Ускорение операции достигнуто с помощью создания таблицы умножения. При этом операция умножения будет сводиться не более чем к l2 операций сложения. Таким образом, кодирование одного кодового слова будет составлять l lt 2t l2 N 2t 1 2t N 2t 1 N 2t 1 l2 побайтовых операций 8L сложения . Так как количество кодовых слов равно, суммарная l t трудоемкость вычислений при процедуре кодирования будет составлять 2L N 2t 1 l2 1 операций сложения . При использовании списков логарифмов элементов поля суммарная трудоемкость 2L N 2t процедуры кодирования составит операций сложения и 16L l q операций сложения чисел размером байт по модулю.

N 2t l Может быть использована сокращенная процедура кодирования, учитывающая только обновляемые информационные символы.

Процедура декодирования составлена из четырех этапов:

Si 1. Вычисление компонент синдрома. С использованием l l2 tN 1 tN таблицы умножения составит операций сложения , и в общей сложности трудоемкость первого этапа декодирования составит LNt l2 1 операций сложения . При использовании списка логарифмов 8LNt элементов поля - LNt операций сложения и операций сложения.

l 2. Вычисление коэффициентов многочлена локатора ошибок x, наиболее оптимальный метод – Берлекэмпа-Месси. При использовании таблиц умножения трудоемкость алгоритма составит не более l l 1 l 3 lt t 1 l2 1 операций сложения для одного кодового l l 1 l 3 слова, и не более L t 1 l2 1 операций для второго этапа в целом. При использовании списка логарифмов не более L t 8L операций сложения и t 2 модульного арифметического l сложения.

3. Поиск локаторов ошибок путем нахождения корней многочлена локаторов ошибок. Поиск корней осуществляется с помощью процедуры Чени. При использовании таблицы умножения данная tNl процедура будет занимать не более tl2 t 1 побайтовых операций сложения для каждого кодового слова, и не более LN tl2 t операций сложения для всего этапа. Применение списков LN t логарифмов снижает сложность третьего этапа до операций 8LNt сложения и операций арифметического сложения.

l 4. Поиск значений ошибок с помощью процедуры Форни. Всего не 7t2 3t 7t2 5t более t операций деления, операций умножения, 2 операций сложения в поле для одного кодового слова. Вычислительная L 7t2 5t 4 7t2 3t сложность составит операций t 2 l2 4 l l 1 l 3 t L сложения , при применении списка логарифмов – 7t2 3t 2t 4L побайтовых операций сложения и 7t2 7t 4 операций сложения.

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

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

Рассматривается применение кода продольного контроля избыточности (LRC) для обеспечения надежности SMART-карт аппаратно-программными средствами которых можно обнаружить сбой d i-ой страницы данных. Данный код имеет минимальный вес и требует одну страницу контроля равную сумме по модулю два всех страниц данных. Следовательно, текущий расход памяти на контрольную информацию для этого кода меньше в два и более раз, d чем для кодов с весом.

Рассмотрены возможности повышения модификации алгоритмов хранения данных в магнитных картах. Рассмотрены коды Хемминга с мощностью алфавита кодирования q 251 16 и длиной кодовых слов и 107, и коды Хемминга с q 271 64 и длиной кодовых слов 79. Число необходимых контрольных символов во всех случаях равно трем.

Контрольные символы будут представлять собой 5- или 7-битовые последовательности (см. рис. 4), младшие 4 или 6 битов которых вычисляются в соответствии с кодом Хемминга, а старшие биты как биты четности.

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

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

Рис. 4. Формат кодовых слов для 5-битовых магнитных дорожек.

В целях снижения энергозатрат RFID-устройствами, целесообразен частичный либо полный перенос алгебраически сложной процедуры декодирования на хост-компьютер: в RFID-устройстве осуществляется первый этап декодирования РС-кода, далее хосткомпьютеру передается значения синдромов, а исправление ошибки производится хост-компьютером. Для кодов Хемминга основную часть процедуры декодирования составляет вычисление значения контрольных страниц. Но этот этап может быть сокращен, если при вычислении контрольных страниц использовать только те данные, которые не будут передаваться хосту.

Для поиска наиболее применимого варианта помехоустойчивого кодирования данных в биометрических паспортах была построена модель последовательного выбора страниц для ввода-вывода данных, поскольку в данных устройствах происходит только пополнение памяти ЭСППЗУ новыми данными без перезаписи старых, перезапись является исключительным событием.

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

Определена функция защищенности данных от вероятности сбоя любой страницы памяти Z p. Как было показано ранее, оптимальным вариантом помехоустойчивой страничной организации памяти является наличие двух страниц контроля. Показано, что разбиение блока кодирования на два подблока увеличивает защищенность данных. Z1 p CH n,Защищенность данных для кода Хемминга вычисляется по n n1 nформуле: Z1 p 1 p np 1 p 1 p 1 n 1 p.

При разбиении блока кодирования на два подблока добавляются еще две страницы контроля, а суммарная защищенность Z2 p является произведением защищенностей каждого из побдлоков:

n 11 n np n 1 Z2 p 1 p 11 p 1 p .

1 Поскольку Z2 p Z1 p, защищенность данных от ошибок будет тем больше, чем меньше размеры кодовых блоков.

Коды Рида-Соломона можно применять также как и коды Хемминга, разделяя память на кодируемые блоки, либо увеличивая t параметр. В части расхода памяти оба метода оказываются t равнозначными. Но увеличение параметра приводит к большей защищенности данных, так как данный код будет способен исправлять t ошибок независимо от их места расположения в памяти.

Существенным недостатком данного метода является увеличение t сложности декодирования при увеличении параметра.

Следовательно, применение РС-кодов целесообразно локально, где требуется максимальная защищенность данных, а процедура декодирования не будет требовать больших затрат.

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

Для МКПИ на базе SMART-карт предложено выделять в памяти разделы данных, разделы контроля, состоящие из страниц контроля и резервную память, содержащую незадействованные в работе страницы памяти, которые могут быть использованы для замены вышедших из строя страниц данных и контроля. В памяти данных целесообразно выделить неизменяемую часть, создаваемую на этапе инициализации или персонализации SMART-карты. В эту часть памяти входят операционная система и программное обеспечение, а также могут входить идентификационные и иные данные. Остальную часть памяти данных составляют либо пополняемые данные, либо перезаписываемые в период эксплуатации. Кодирование указанных частей памяти данных должно производиться отдельно друг от друга. Следовательно, в контрольной памяти также будут выделены три подраздела, соответствующие подразделам памяти данных (Рис. 5).

Рис. 5. Логическая структура хранения информации в SMART-карте.

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

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

Для повышения эффективности процедур ввода-вывода предложены направления аппаратно-программной модификации SMART-карт:

аппаратная реализация арифметики конечных полей GF 2l ;

создание в памяти ПЗУ и ЭСППЗУ таблиц умножения или списков логарифмов элементов поля;

программно-аппаратная реализация функции обнаружения сбоев в страницах памяти ЭСППЗУ, модификация позволит использовать в качестве помехоустойчивого кода LRC-код.

Изложен алгоритм ввода-вывода данных, с процедурами контроля и коррекции ошибок (на рис. 6 алгоритм ввода).

Для МКПИ на базе магнитных карт предложено три альтернативных модификации структуры данных, размещаемых в картах с магнитной полосой, позволяющих повысить надежность хранения данных:

1. В конце каждой магнитной дорожки после символа LRC разместить два дополнительных контрольных символа. Для первой магнитной дорожки значения этих символов вычислены с помощью укороченного кода Хемминга CH 79,76 с алфавитом кодирования GF 64.

Для второй магнитной дорожки дополнительные контрольные символы вычислены с помощью кода Хемминга CH 40,37 над GF 16.

Дополнительные контрольные символы третьей дорожки получены с помощью кода Хемминга CH 107,104 с алфавитом кодирования GF 16 ;

2. В конце первой магнитной дорожки после символа LRC разместить три дополнительных контрольных символа. Для вычисления контрольных символов, каждый символ данных на магнитной дорожке делится на три 2-битовые части и один бит четности. Из полученных частей всех символов составляются три информационных слова над полем GF 4. Каждое слово кодируется укороченным кодом Хемминга CH 79,75 с алфавитом кодирования GF 4. В конце второй магнитной дорожки после символа LRC также размещаются три дополнительных контрольных символа. Для их вычисления каждый символ данных на магнитной дорожке делится на две 2-битовые части и один бит четности. Из полученных частей всех символов составляются два информационных слова над полем GF 4, которые далее кодируются укороченным кодом Хемминга CH 40,36 с алфавитом кодирования GF 4. В конце третьей дорожки добавлены четыре дополнительных контрольных символа. Построение также как и для второй дорожки;

3. В конце первой и третьей дорожек разместить дополнительных контрольных символов, в конце второй – дополнительных контрольных символов. Их вычисление осуществляется также как и для второго варианта модификаций, с той разницей, что в качестве алфавита кодирования используется GF 2.

Для МКПИ на базе RFID-устройств, как и на базе SMART-карт, память ЭСППЗУ целесообразно разделить сначала на память данных, контрольную память и резервную память, а затем на информационные блоки. Предложено три способа повышения надежности устройств:

уменьшение размеров информационных блоков, перенос процедур кодирования на хост-компьютер, аппаратная реализация процедур кодирования. Алгоритм ввода-вывода данных для МКПИ RFID в случае размещения алгоритмов в персональном идентификаторе равносилен рис. 6 и на хост-компьютере – в соответствии со схемой, представленной на рис. 7.

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

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

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

Рассмотрена реализация в МКПИ, построенных на основе RFIDустройств. Указаны преимущества к которым ведет применение модификаций методов и алгоритмов в биометрических паспортах.

Определение соответствия между кодовыми блоками и записываемыми данными Последовательная запись данных в имеющиеся кодовые нет блоки с пересчетом их страниц контроля да Число перезаписываемых страниц да нет данных больше половины числа ненулевых страниц данных в кодовом блоке Цикл по нет нет Последовательная перезапись перезаписываемым страниц данных с вычислением страницам данных страниц контроля кодового блока да да Перезапись (запись) Вычисление суммы старой страницы (при страницы данных записи новой страницы данных считать кодового блока нулевой) данных и новой страницы данных нет Цикл по нет Цикл по страницам контроля страницам кодового блока контроля да да Вычисление новой страницы контроля как суммы старой станицы контроля Вычисление страницы с суммой старой и новой страниц данных, умноженной на соответствующий контроля коэффициент (в зависимости от кода и номера страницы данных) Перезапись (запись) Перезапись страницы данных страницы контроля Перезапись страниц контроля кодового блока Последовательная организация новых кодовых блоков да Выбор в резервной памяти страниц памяти для нового кодового блока Запись в служебные страницы памяти информации о новом кодовом блоке Запись страниц данных кодового блока нет Последовательное вычисление контрольных страниц, соответствующих кодовому блоку да Вычисление контрольной страницы Запись контрольной страницы Рис. 6. Алгоритм обработки ввода данных в МКПИ.

Рис. 7. Организация ввода информации на базе алгоритмов обеспечения надежности размещённых на хост-компьютере.

Рис. 8. Логическая структура хранения информации в биометрическом паспорте.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ 1. Рассмотрены современные принципы реализаций микрокомпьютерных комплексов персональной идентификации (МКПИ), методы обработки, хранения, ввода вывода данных в МКПИ.

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

2. Предложены критерии классификации МКПИ по аппаратнопрограммной платформе, особенностям хранимой информации, объему памяти в результате выделены SMART-карты, магнитные карты, RFIDустройства, биометрические паспорта.

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

4. Разработаны математические модели для случайного и последовательного выбора страниц для ввода-вывода данных, позволяющие оценивать алгоритмы помехоустойчивого кодирования информации в МКПИ с позиций формул для расчета эффективности помехоустойчивого кода, коэффициента расхода памяти и степени защищенности данных.

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

6. Рассмотрена применимость кодов Хемминга, Рида-Соломона и продольного контроля избыточности в модели случайного и последовательного выбора страниц для ввода-вывода данных.

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

7. Разработаны методы логической организации данных, модификации алгоритмов хранения и ввода-вывода данных в МКПИ позволившие улучшить их технико-экономические характеристики на 30%, а устойчивость к выявлению и исправлению ошибок до 80%.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ 1. Крюков Д.А. Программное обеспечение восстановления информации с SIM-карт // журнал «Вопросы радиоэлектроники», серия «Электронная вычислительная техника», 2011, вып. 4, стр.

157-164.

2. Крюков Д.А. Идентификация SMART-карт на основе односторонних преобразований // журнал Информационноуправляющие системы 1(56) 2012, стр. 76-79.

3. Крюков Д.А. Модели функционирования персональных систем идентификации с процедурами помехоустойчивого кодирования и декодирования хранимых данных // электронное научно-техническое издание «Наука и образование: научное издание МГТУ им. Н.Э. Баумана», №10, октябрь 2012.

4. Андрианова Е.Г., Крюков Д.А., Петров А.Б. Повышение надежности хранения информации в микрокомпьютерных комплексах персональной идентификации // электронный журнал «Труды МАИ», №59, 2012.

5. Крюков Д. А. Помехоустойчивое кодирование в персональных устройствах идентификации // журнал Промышленные АСУ и контроллеры. Вып. 12, 2012, «Научтехлитиздат», стр. 50-58.

6. Крюков Д.А. Особенности файловой системы SMART-карт используемых в информационно-коммуникационных системах // Труды НПК «Современные информационные технологии в управлении и образовании» часть 2, стр. 141-147. ФГУП НИИ «Восход», 2011.






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.