автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Методы, алгоритмы и программы повышения надежности хранения информации на магнитных дисках

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

Кокоулин Андрей Николаевич

МЕТОДЫ, АЛГОРИТМЫ И ПРОГРАММЫ ПОВЫШЕНИЯ НАДЕЖНОСТИ ХРАНЕНИЯ ИНФОРМАЦИИ НА МАГНИТНЫХ

ДИСКАХ

05.13 05 — Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Пермь - 2007

003163808

Работа выполнена в Пермском государственном техническом университете

кандидат технических наук, профессор Кон Ефим Львович, Пермский государственный технический университет

доктор технических наук, профессор Первадчук Владимир Павлович, Пермский государственный технический университет

кандидат технических наук, Котельников Илья Леонидович, начальник отдела стратегического планирования ОАО «Морион»

Ведущая организация - ЗАО «ИВС - сети»

Защита состоится «02» «ноября» 2007 г в 16 часов на заседании диссертационного Совета Д 212 188 04 в Пермском государственном техническом университете по адресу

614600, г Пермь, Комсомольский пр-т ,29, ауд 4236

С диссертацией можно ознакомиться в библиотеке Пермского государственного технического университета

Автореферат разослан « /У » « ÇjôtxiP»JU^u^*- » 2007 г

Ученый секретарь диссертационного совета, доктор технических наук, профессор

Научный руководитель

Официальные оппоненты

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы диссертации Развитие вычислительной техники в значительной мере определяется эксплуатационными характеристиками запоминающих устройств, к которым в первую очередь следует отнести надежностные характеристики

Совершенствование магнитных дисков, в основном, происходит в направлении повышения плотности записи данных на носителе При этом происходит уменьшение размеров элементов хранения информации и увеличение плотности компоновки, что приводит к появлению дефектов при производстве и к повышению интенсивности отказов и сбоев в процессе эксплуатации Анализ многочисленных работ, посвященных повышению надежности хранения информации на стационарных и съемных дисковых накопителях в составе систем хранения данных (СХД) современных ПЭВМ, рабочих станций, интеллектуальных устройств автоматики и бытовой техники, показал, что технологические меры повышения надежности ЗУ не всегда являются достаточными, а используемые методы парирования дефектов носителя за счет введения избыточности либо неэффективны, либо требуют дополнительной аппаратуры Таким образом, целая ниша вычислительной, бытовой и оргтехники, нуждается в экономичных и эффективных методах повышения надежности хранения информации

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

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

токов информации в дисковых накопителях

Объектом исследования является канал хранения и передачи информации на магнитных дисках ЭВМ, в состав которого входят аппаратные и программные блоки, имеющие собственную статистику ошибок, виды дефектов и информационные структуры

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

Для достижения поставленной цели необходимо решить следующие основные задачи диссертационной работы

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

• Исследовать и обосновать возможность и цечесообразность применения двухмерных итеративных кодов для повышения надежности хранения информации на дисках различных типов,

• Разработать систему критериев для оценки эффективности алгоритмов кодирования и исправления ошибок в СНХИ двухмерными итеративными кодами в соответствии с особенностями потоков данных в канале хранения информации на дисковых накопителях,

• Разработать и исследовать метод определения значений критериев,

• Разработать и исследовать эффективные алгоритмы кодирования и декодирования двухмерных итеративных кодов СНХИ в соответствии с выбранной системой критериев,

• Разработать рекомендации по выбору параметров двухмерных итеративных кодов и размещению проверочных разрядов для разных МД,

• Разработать рекомендации по программной реализации СНХИ, использующей предложенные алгоритмы кодирования и декодирования итеративных кодов для разных типов дисков

Предметом исследования являются методы повышения надежности хранения информации на магнитных дисках, алгоритмы кодирования и исправления ошибок данных в СНХИ с использованием алгебраических, и, в частности, итеративных кодов и методы анализа вычислительной сложности алгоритмов

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

Научная новизна работы заключается в следующем

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

• Разработана и исследована четырехуровневая модель КХПИ на МД

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

• Разработаны эффективные алгоритмы кодирования и декодирования двухмерных итеративных кодов для магнитных дисков

Основные положения, выносимые на защиту

• Разработанная и исследованная четырехуровневая модель канала хранения информации на дисковых накопителях,

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

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

• Разработанные эффективные алгоритмы кодирования и декодирования двухмерных итеративных кодов в КХПИ на магнитных дисках, адаптированные к специфике информационных потоков,

• Предложенные рекомендации по программной реализации СНХИ для разных типов дисков и операционных систем

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

Практическая ценность работы

• Разработанные методы и алгоритмы повышения надежности стандартных дисковых ВЗУ в составе ПЭВМ позволяют реализовать надежную,

эффективную и экономичную систему хранения информации на рабочих станциях, ЭВМ общего назначения, интеллектуальных устройств автоматики и бытовой техники,

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

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

Внедрение результатов работы Основные теоретические положения диссертационной работы успешно прошли апробацию при разработке программной системы СНХИ для гибких дисков 3,5" и съемных жестких дисков IOMEGA JAZ емкостью 1Гб Упомянутые программные пакеты прошли промышленные испытания и используются в учреждениях ГУ Банка России РФ по Пермскому краю и Свердловской области

Апробация работы. Основные результаты диссертационной работы докладывались и получили положительную оценку на конференциях XXV Международная конференция «Новые информационные технологии в науке, образовании, коммуникациях» (Украина, Крым, Гурзуф, 1998г), XXXI Международная конференция "Информационные технологии в социологии, экономике, образовании и бизнесе" IT + SE 03 ОСЕННЯЯ СЕССИЯ" и IT + SE'06 ОСЕННЯЯ СЕССИЯ" (Украина, Крым, Ялта-Гурзуф, 30 сентября 2003 г и 5 октября 2006г ), «Годишник на Технический Университет» (ВъВ Варна, 2001) По теме диссертации делались сообщения и доклады на научно-практических и научно-методических конференциях ПГТУ 1997-2007гг

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

Структура и объем диссертации Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы из 121 наименований и двух приложений Основная часть изложена на 122 страницах машинописного текста, иллюстрируется 20 рисунками и 7 таблицами ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность темы диссертации, сформулированы цели и основные задачи диссертационной работы, отражена научная новизна и практическая ценность результатов работы, перечислены положения, выносимые на защиту

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

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

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

2 Использование минимально возможной информационной избыточности при допустимой вероятности ошибки не более 10"14,

3 Обеспечение защиты любых дисковых накопителей, включая съемные диски, без внесения дополнительной аппаратной избыточности,

4 Хранение как полезной, так и избыточной информации на одном дисковом накопителе без нарушения форматов диска,

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

В соответствии с предложенной системой требований показаны принципиальные недостатки существующих методов повышения надежности для каждого этапа преобразования информации в СХИ и обоснована целесообразность использования двухмерных итеративных кодов для повышения надежности хранения информации на МД

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

хранения и передачи данных, считанных с магнитного диска в пользовательскую программу

Сформулированы задачи диссертационной работы и выделены основные этапы разработки и исследования МНХИ

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

• прикладной уровень Произвольный формат данных,

• уровень файловых операций Обработка файловых объектов,

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

• физический уровень Обработка битовых последовательностей

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

С учетом того, что при движении информации между уровнями происходит ее структурное преобразование, а именно разделение битовой последовательности, считанной с диска на физическом уровне модели на служебную информацию и пользовательскую информацию, в работе показано, что спектр ошибок смещается в сторону коррелированных ошибок Обнаруженная и не исправленная аппаратным контролем цечостности информации ошибка для всех последующих уровней будет соответствовать пакету стираний длиной 1 сектор Расчеты показали, что вероятность возникновения пакетов стираний длиной в 1 сектор достигает 10'7 С учетом этого, код должен обеспечить исправление любой конфигурации пакетов стираний не менее чем в трех сбойных секторах кодовой группы для допустимой вероятности ошибки на выходе СНХИ не более 10'14

В ходе исследования уровней КХПИ сделан вывод о наибольшей эффективности размещения СНХИ на уровне дисковых операций

• возможна программная реализация МНХИ Интеграция в существующие структуры КХПИ прозрачна и не вызывает конфликтов,

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

• обеспечивается защита всей полезной поверхности диска,

• на уровне дисковых операций операционная система использует стандартный для всех дисковых накопителей программный интерфейс, что позволяет разработать универсальный по типу накопителя МНХИ,

• возможно косвенное использование результатов декодирования и/или исправления ошибок кодом стандартного аппаратно реализуемого контроля целостности информации, что позволяет максимально эффективно использовать избыточность для коррекции ошибок

Для повышения надежности хранения информации на магнитных дисках рекомендовано использование двухмерных итеративных кодов, т к эти коды декоррелируют пакеты ошибок или стираний и обладают простыми в реализации алгоритмами кодирования и декодирования Код столбца предлагаемого итеративного кода является кодом ГСК (пьШьс!]) с <1ш1п1^3 Разряды кодовых групп кода столбца набираются из ,]-х бит секторов, объединенных в одну кодовую группу итеративного кода Кодек кода столбца реализуется программно Кодом строки является код (п2,ш2,ё2) аппаратно реализуемого контроля целостности информации (СЯС/ЕСС), чаще всего используется код Рида-Соломона с <ЗтШ2>4, обладающий высокой обнаруживающей способностью

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

• структура КХПИ и принципы хранения, обработки и передачи информации функциональных блоков одинаковы для всех типов дисковых накопителей,

• разработанный МНХИ, и реализующие его алгоритмы, могут быть использованы на магнитных дисках с широким диапазоном показателей надежности Настройка параметров СНХИ будет заключаться в выборе параметров двухмерного итеративного кода, используемого для повышения надежности,

• разработанный МНХИ предполагает прозрачную и бесконфликтную интеграцию в структуру различных файловых и операционных систем

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

вании этих рекомендаций вносится минимальная задержка в процессе кодирования и записи на диск в СХИ

• Целесообразно объединять все сектора одной дорожки съемного диска в одну кодовую группу

• Длина кодовой группы жесткого диска должна быть кратна размеру кластера, чтобы минимизировать время записи на диск

В третьей главе анализируются критерии эффективности алгоритмов кодирования и исправления ошибок СНХИ и предлагается метод расчета значений критериев

Процедура кодирования информации выполняется каждый раз при записи новых данных на диск Снижение быстродействия обусловлено необходимостью выполнения дополнительных операций над данными Поэтому усовершенствование и адаптация алгоритма кодирования должно проводиться в сторону уменьшения времени кодирования, пропорционального количеству дисковых операций N^0 (более значимый критерий) и инструкций процессора (ключевых операций) N^0 (менее значимый)

Процедура исправления ошибок выполняется только при возникновении ошибки и является относительно редким событием Поэтому, в работе предложено в качестве наиболее значимого критерия выбрать реализуемую исправляющую способность алгоритма Б. а остальные критерии, имеющие меньшую значимость - количество дисковых операций N<^0 и количество команд (ключевых операций) при декодировании, предлагается оптимизировать в последнюю очередь

1) В работе была рекомендована следующая поэтапная методика выбора эффективного алгоритма кодирования СНХИ

• Исследовать пути уменьшения количества дисковых операций при различных вариантах записи кодовых групп Мкдо, составить список возможных алгоритмов

• Для каждого варианта определить численные значения критерия Выбрать из списка алгоритм, обеспечивающий минимальное Ыклп,

• Исследовать пути уменьшения числа ключевых операций, необходимых для вычисления проверочных разрядов Мкк0, составить список возможных вариантов реализаций алгоритмов

• Определить численные значения критерия N^0 Выбрать вариант (совокупность вариантов) реализации алгоритма, который позволяет минимизировать параметр

2) Рекомендована поэтапная методика выбора эффективного алгоритма декодирования

• Исследовать методы максимизации реализуемой исправляющей способности 8, составить список возможных алгоритмов

• Определить численные значения критерия Б Выбрать из списка алгоритм с наилучшим значением Б в качестве основы алгоритма декодирования двухмерного итеративного кода СНХИ

• Исследовать варианты реализации, позволяющие ускорить процесс исправления ошибок по метрикам N¿,,0 и составить список возможных вариантов реализаций алгоритмов

• Определить численные значения критерия N^0 и М^о Выбрать вариант (совокупность вариантов) реализации алгоритма, который позволяет минимизировать параметры N^0 и МсК0

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

Критерий 8 (реализуемая исправляющая способность) вычислялся в соответствии с формулами теории помехоустойчивого кодирования

Выбор методики определения численных значений метрик критериев Ыкко и N¿„0 проводился в соответствии с требованиями степень адекватности поставленной задаче получаемых с помощью вычислительной модели оценок, трудоемкость представления алгоритмов и независимость модели от архитектуры и механизмов управления ресурсами операционной системы Были оценены следующие вычислительные модели и методы оценки вычислительной сложности

• Машины Тьюринга,

• Метод сводимости задачи,

• Метод оценки сложности с использованием граф-схем алгоритмов, Показано, что метод построения граф-схем алгоритмов, является

единственным методом, позволяющим получить точные значения критериев Мкк(1 и Ыйко, и описать мельчайшие отличия близких по структуре алгоритмов, поэтому в работе был выбран данный метод

В четвертой главе диссертационной работы, с использованием предложенной методики и системы критериев, проведена разработка и исследование оригинальных алгоритмов кодирования и исправления ошибок

СНХИ, позволяющих существенно улучшить ряд важнейших характеристик по сравнению со стандартными (базовыми) алгоритмами

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

Утверждение Изменение значения любого информационного разряда а1 на а,' в кодовой группе ГСК-кода вызовет следующие изменения проверочных разрядов с„ 1<1<П]-т1 Лс^к^а^')

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

Таблица 1. Выбор алгоритма кодирования

Алгоритм кодирования Записьполной г руппы Запись неполной группы (V секторов)

количество дисковьк операций Мкдо cн^íжeниe быстродей ствия количество дисковых операций снихвние быстр одейс твич

Стандартный (базовый) П1 («1 ~ »]) П1 (11 - V)

т , V

Учитывающий особености входньк данных 2*П ! (2й1 - жа) ) (2(у + *)-у)

т 1 V

запись V информационных секторов

—базовый

- с учетом вх данных

Рис 1 Снижение быстродействия при использовании алгоритмов кодирования итеративного кода СНХИ с длиной кодовой группы 63 сектора

В таблице 1 показано преимущество разработанного алгоритма, учитывающего особенности потоков данных в КХПИ по сравнению с базовым алгоритмом по критерию К|<ло Для наглядного сравнения алгоритмов введем показатель снижение быстродействия, демонстрирующий относительное увеличение числа дисковых операций при кодировании На рис 1 видно, что доля полезных операции V при использовании алгоритма кодирования, учитывающего особенность входных данных выше Таким образом, производительность СХИ снижается в меньшей степени В работе рекомендуется использовать алгоритм, учитывающий особенности входных данных, при количестве перезаписываемых секторов у=(1 П]/2-к-, ) и базовый алгоритм, при большем количестве секторов

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

В работе предложен оригинальный алгоритм исправления ошибок стирания, использующий свойства укороченного кода ГСК (пг1,гп|-1,с1|), используемого в качестве кода столбца в двухмерном итеративном коде СНХИ, позволяющий наиболее полно реализовать исправляющую способность кода Данный алгоритм позволяет исправлять пакетируемые ошибки стирания общей длиной до пяти секторов в кодовой группе, в то время как стандартная процедура исправления позволяет восстановить всего три сектора Принцип работы алгоритма теоретически обоснован в работе В частности, доказано следующее утверждение

Утверждение Укороченный код (п-1,т-1,с!) может исправлять кроме

ошибок кратности Б=(с1-1) дополнительно

т~п-\-12 и2(6-31}+я(!2л-71)-13+! ЛЛ -г -г---+---

0 комбинаций символов стираний

Применение предложенного принципа, позволяет увеличить корректирующую способность алгоритма исправления ошибок кодов ГСК по сравнению с стандартным (базовым) алгоритмом декодирования Таким образом, в каждой кодовой группе кода столбца могут быть исправлены некоторые комбинации из пяти и менее стираний, и для двухмерного итеративного кода СНХИ возможно исправление до пяти поврежденных секторов в кодовой группе

Определена вероятность ошибки на выходе декодера Ра<\ --{РР^ где _ вероятности появления г стираний на входе декодера, что на порядок меньше вероятности ошибки при использовании

р — 1_р

стандартного алгоритма • <з Экспериментальное исследование подтвердило корректность алгоритма

Таблица 2 Выбор алгоритма исправления ошибок и способов повышения его быстродействия Выбор алгоритма исправления ошибок кода СНХИ_

Алгоритмы Исправляющая способность

Стандартный 3

Основанный на свойствах укороченного кода до 5

Выбор варианта реализацииалгоритма исправления ошибок

Варианты реализации Количество ключевых операций(для 1 поврежденных секторов)

Стандартный от т2Ц2п1к1 >0 т2 1 (ЫС\ (2п1к1 У)

и использованием остаточной информации от т/гл,*^ до 2т/2п,к,)

Вариант реализации с использованием логического значения синдрома / от т21к1 до т2 2 (,\у.С11к1)

Вариант реализации с использованием параллельной обработки нескольких групп ОТ -^-1(2п,к,)л0 ' X (гуС1. (2п.к.)) А 1=1

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

логического значения синдрома, Преимущества разработанных вариантов реализации по сравнению с базовым алгоритмом показаны в таблице 2

В пятой главе рассматриваются вопросы программной реализации предлагаемых в работе алгоритмов и рассматриваются другие области применения методов повышения надежности хранения информации, в том числе, для других носителей информации и в составе сложных информационных систем

Рассмотрены стадии разработки программного обеспечения СНХИ для современных операционных систем, даны рекомендации по использованию средств разработки и по архитектуре ПО СНХИ В качестве программной модели СНХИ рекомендована модель драйвера-фильтра дисковых операций, позволяющая перехватывать и обрабатывать абсолютно все запросы на проведение дисковых операций

Разработана типовая инструкция по проведению приемо-сдаточных испытаний, позволяющая провести разностороннюю оценку корректности работы СНХИ и соответствие СНХИ поставленным требованиям

Приведены результаты приемо-сдаточных испытании программных СНХИ для ОС Windows 9х/2000/ХР (имеются соответствующие акты)

1 СНХИ на гибких магнитных дисках,

2 СНХИ на съемных жестких магнитных дисках IOMEGA JAZ 1 Gb Результаты внедрения разработанных алгоритмов показывают способность СНХИ парировать дефекты накопителя, поражающие до пяти секторов кодовой группы СНХИ обеспечивает вероятность ошибки 10'14

В пятой главе также предлагаются варианты использования методов и алгоритмов СНХИ для защиты дисковых внешних запоминающих устройств других типов, таких как магнитооптические диски, CD, DVD диски, Flash-память, Mai нитные банковские карты, что подтверждает универсальность разработанного метода

Автором предтожены перспективные варианты применения полученных наработок в системах комплексной защиты информации и в составе отказоустойчивых систем, основанных на RAID-технологии

Заключение содержит следующие основные результаты и выводы

1 Разработана четырехуровневая модель КХПИ и показана адекватность модели для решения задач диссертационной работы Обоснован выбор уровня дисковых операций для эффективной реализации СНХИ,

2 Определены требования к разрабатываемым эффективным методам повышения надежности стандартных дисковых накопителей,

3 Обоснован выбор универсального метода повышения надежности хранения данных на МД с использованием двухмерных итеративных кодов,

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

5 Рекомендованы методы оценки численных значений критериев Проведено ранжирование критериев по значимости и предложены методики исследования и разработки эффективных алгоритмов кодирования и исправления ошибок,

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

7 Предложены рекомендации для программной реализации СНХИ, инвариантной к типам дисков и операционных систем На примере съемных жестких дисков IOMEGA JAZ и флоппи-дисков показано определение длин кодовых групп и способы размещения проверочных разрядов двухмерных итеративных кодов,

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

9 Рекомендована методика проведения испытаний СНХИ, демонстрирующая соответствие характеристик реализованной СНХИ поставленным требованиям и теоретическим результатам исследований Метод, алгоритмы и рекомендации по программной реализации успешно реализованы и апробированы в учреждениях ГУ ЦБ РФ Пермской и Свердловской областей для защиты ключевой информации на съемных дисках Эффективность предложенного МНХИ подтверждена актами приемки ПО

В приложении приведены копии документов, подтверждающих

практическое использование и внедрение результатов диссертации

Основные научные результаты диссертации опубликованы в работах

1 Кокоулин А Н Система надежного хранения информации на магнитных дисках // Сборник научных трудов Информационные управляющие системы Пермь, ПГТУ, 1999 - с 64-70

2 Кокоулин А Н, Кон Е JI Особенности реализации кодека помехоустойчивого кода в составе системы обеспечения надежного хранения информации на магнитных дисках (СНХИ) // Информационные управляющие системы, Сб науч трудов Пермь, ПГТУ, 2000 - с 23-29

3 Кокоулин АН Методы защиты интеллектуальной собственности // Го-дишник на Технический Университет, Варна, 2001 - с 338-345

4 Кокоулин А Н, Кон Е JI Анализ вычислительной сложности алгоритмов // Сборник научных трудов Информационные управляющие системы Пермь, ПГТУ ,2001, - с 42-48

5 Кокоулин А Н , Кон Е JI Выбор критериев и методики оценки вычислительной сложности алгоритмов кодирования блоковыми алгебраическими кодами // Сборник научных трудов Информационные управляющие системы Пермь, ПГТУ, 2002, - с 32-39

6 Кокоулин А Н, Кон Е JI Алгоритм исправления ошибок системы надежного хранения информации с оптимальной для исправления ошибок малой кратности проверочной матрицей // Системы мониторинга и управления Сборник научных трудов, Пермь, ПГТУ, 2006 - с 106-109

7 Кокоулин АН Методы и алгоритмы повышения надежности хранения информации на магнитных дисках в системах RAID уровня 2 //Материалы Международной конференции «Информационные технологии в социологии, экономике, образовании и бизнесе IT+SE'06» Украина,Гурзуф 2006 -с 49-50

8 Кокоулин АН Методы и алгоритмы повышения надежности хранения информации на магнитных дисках в системах RAID // «Вестник КГТУ им Туполева», №2 Казань, 2007 - с 159-170

Подписано в печать 27 09 07 Формат 60X90/16 Набор компьютерный. Тираж 100 экз Объем 1,00 уч-изд п л Заказ № 1325/2007

Издательство

Пермского государственного технического университета 614600, г Пермь, Комсомольский пр, 29, к 113 тел (342)219-80-33

Общая характеристика работы

1. Анализ современных технологий и методов повышения надежно- 10 сти хранения информации на дисковых накопителях

1.1. Основные тенденции технологического и структурного развития сис- 10 тем хранения информации современных ПЭВМ

1.2. Требования к методам повышения надежности хранения информации 14 магнитных дисков

1.3. Канал хранения и передачи информации на магнитных дисковых но- 15 сителях ПЭВМ

1.3.1. Структурная схема СХИ на магнитных дисках.

1.3.2. Этап передачи: Магнитный диск (носитель информации) - считы- 18 вающий механизм магнитных головок.

1.3.3. Этап передачи: Считывающий механизм магнитных головок - кон- 22 троллер дискового накопителя.

1.3.4. Этап передачи: Контроллер дискового накопителя - контроллер ин- 26 терфейса ввода-вывода

1.3.5. Этап передачи: контроллер интерфейса ввода-вывода - контроллер 32 DMA.

1.3.6. Этап передачи: Контроллер DMA - ОЗУ (программы-драйверы 33 дисковой системы).

1.3.7. Этап передачи: драйверы дисковой системы - драйверы файловой 34 системы

1.3.8. Этап передачи: драйверы файловой системы - потребитель инфор- 35 мации (программа пользователя).

1.3.9. Результаты анализа структурной схемы СХИ на магнитных дисках.

1.4. Выводы по главе

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

2.1. Разработка многоуровневой модели КХПИ.

2.2. Исследование и расчет статистики ошибок уровня дисковых опера- 42 ций канала хранения и передачи информации

2.3. Анализ ограничений информационной структуры уровней КХПИ. Ре- 46 комендации по выбору длины кодовой группы.

2.4. Выводы по главе

3. Методика оценки эффективности разрабатываемых алгоритмов 51 кодирования и исправления ошибок итеративного кода СНХИ.

3.1. Выбор критериев эффективности алгоритмов кодирования и исправ- 51 ления ошибок итеративным кодом СНХИ.

3.2. Исследование особенностей информационных потоков для кодека 53 итеративного кода СНХИ

3.2.1. Особенности операций записи информации на диск

3.2.2. Считывание информации с диска и исправление ошибок декодером 55 СНХИ

3.3. Метод определения численных значений критериев вычислительной 56 сложности алгоритмов кодирования и декодирования двухмерного итеративного кода СНХИ.

3.3.1. Метод оценки сложности алгоритмов с помощью сигнализирующих 57 функций. Машины Тьюринга.

3.3.2. Оценка сложности алгоритмов с помощью аппарата теории своди- 60 мости.

3.3.3. Оценка сложности с помощью граф-схем алгоритмов.

3.3.4. Выбор метода оценки вычислительной сложности алгоритмов ко- 66 дирования и исправления ошибок МНХИ

3.4. Выводы по главе

4. Разработка эффективных алгоритмов кодирования и декодирова- 68 ния двухмерного итеративного кода СНХИ.

4.1. Разработка эффективного алгоритма кодирования итеративного кода 68 СНХИ.

4.1.1. Базовый алгоритм кодирования итеративным кодом СНХИ.

4.1.2. Алгоритм кодирования итеративным кодом СНХИ, учитывающий 71 возможность частичного обновления информационных разрядов.

4.1.3. Эффективный алгоритм кодирования итеративным кодом СНХИ

4.1.4. Реализация алгоритма кодирования итеративным кодом СНХИ, 76 учитывающая разрядность процессора

4.1.5. Результаты разработки эффективного алгоритма кодирования двух- 78 мерным итеративным кодом СНХИ.

4.2 Разработка эффективного алгоритма декодировании (исправления 79 ошибок) итеративного кода СНХИ

4.2.1. Стандартный алгоритм исправления ошибок итеративным кодом 79 СНХИ.

4.2.2. Алгоритм исправления ошибок СНХИ, основанный на свойствах 82 укороченного внешнего кода.

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

4.2.4. Вариант реализации алгоритма исправления ошибок СНХИ, ис- 87 пользующий логическое скалярное значение синдрома.

4.2.5. Вариант реализации алгоритма исправления ошибок СНХИ, ис- 89 пользующий остаточную информацию для ускорения декодирования

4.2.6. Результаты разработки эффективного алгоритма исправления оши- 90 бок двухмерного итеративного кода СНХИ

4.3. Выводы по главе.

5. Практическая реализация системы повышения надежности хране- 91 ния и передачи информации на магнитных дисках.

5.1. Способ внедрения СНХИ в структуру операционной системы.

5.2. Способ размещения и декларирования проверочных разрядов на дис- 96 ке.

5.3. Разработка вспомогательных средств СНХИ.

5.4. Выбор средств разработки.

5.5. Разработка методики экспериментальной проверки предлагаемого 99 метода повышения надежности магнитных дисков с помощью разрушающих испытаний

5.6. Варианты использования полученных теоретических и практических 102 результатов для создания прочих типов ПО.

5.6.1. Создание отказоустойчивых систем с использованием СНХИ.

5.6.2. Системы комплексной защиты информации

5.7. Выводы.

Актуальность проблемы

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

Основным направлением совершенствования аппаратно-программных средств СХИ, используемых в традиционных сферах применения, включая АСУТП, является увеличение емкости накопителей и разработка высокоскоростных интерфейсов обмена данными. К 2005 году типичный накопитель на магнитных дисках имел плотность записи в пределах 50 Гигабит на квадратный дюйм [94,95,97], и этот показатель постоянно увеличивается.

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

Увеличение емкости накопителей на магнитных дисках происходит за счет значительного уменьшения площади информационных ячеек и увеличения плотности компоновки. По этой причине, появление дефектов при производстве современных дисковых накопителей и повышенная интенсивность отказов и сбоев в процессе их эксплуатации, происходит вследствие приближения к технологическим барьерам. Основным барьером является парамагнитный эффект [92,98,99,109,112], обусловленный нестабильностью намагниченности магнитных доменов. Кроме того, остаются типичные для магнитных носителей проблемы износа движущихся частей, точности позиционирования магнитных головок, присутствие микрочастиц пыли и влаги, вызывающие непрогнозируемое появление областей с нестабильными характеристиками на носителе. По некоторым оценкам, увеличение плотности записи на магнитные носители при сохранении существующих принципов повышения надежности чтения и записи данных серьезно замедлится, поскольку для сохранения допустимого значения вероятности сбоя в системах с низким соотношением сигнал/шум необходимо увеличивать исправляющую мощность помехоустойчивого кода (ЕСС), которым защищается каждый сектор диска [106,111,112].

Эффективные методы повышения надежности дисковых накопителей используются только в дорогостоящих специализированных СХИ, и имеют существенные ограничения по типу оборудования. Как правило, основное внимание в существующих методах защиты, например, в RAID [102,103], уделяется не повышению надежности хранения информации на отдельных накопителях массива, а обеспечению возможности восстановления данных с поврежденного диска, используя проверочные разряды, распределенные по другим накопителям и последующей горячей замене поврежденного диска.

Поэтому, актуальна разработка и исследование методов повышения надежности хранения информации (МНХИ) для тех случаев, когда применение дополнительной аппаратуры для дублирования не оправдано экономически либо невозможно. В данные рамки укладывается вся вычислительная и бытовая техника, для которой стоимость СХИ не должна превышать 10-30% от стоимости всей системы.

Система повышения надежности хранения информации (СНХИ) должна эффективно интегрироваться в существующую иерархическую структуру канала хранения и передачи данных, и с максимальной полнотой использовать обнаруживающую способность существующих (конструкционно заложенных в накопитель) средств контроля целостности информации. Метод защиты должен быть инвариантен к типу диска. Следует заметить, что разрабатываемые МНХИ не противопоставляются существующим методам повышения надежности и отказоустойчивости, в частности, технологиям RAID и SAN/NAS, а могут служить дополнением к этим технологиям, создавая в совокупности многоуровневую систему надежного хранения информации.

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

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

Для достижения поставленной цели необходимо решить следующие основные задачи диссертационной работы:

• Разработать и исследовать многоуровневую модель КХПИ, проанализировать статистику ошибок для каждого уровня канала и выделить уровень для эффективной реализации системы повышения надежности хранения информации (СНХИ), использующей алгебраические коды;

• Исследовать и обосновать возможность и целесообразность применения двухмерных итеративных кодов для повышения надежности хранения информации на дисках различных типов;

• Разработать систему критериев для оценки эффективности алгоритмов кодирования и исправления ошибок в СНХИ двухмерными итеративными кодами в соответствии с особенностями потоков данных в канале хранения информации на дисковых накопителях;

• Разработать и исследовать метод определения значений критериев;

• Разработать и исследовать универсальный метод и эффективные алгоритмы кодирования и декодирования двухмерных итеративных кодов СНХИ в соответствии с выбранной системой критериев;

• Разработать рекомендации по выбору параметров двухмерных итеративных кодов и размещению проверочных разрядов для разных типов МД;

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

Объектом исследования является канал хранения и передачи информации на магнитных дисках ЭВМ, в состав которого входят аппаратные и программные блоки, имеющие собственную статистику ошибок, виды дефектов и информационные структуры.

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

Основные положения, выносимые на защиту:

• Разработанная и исследованная четырехуровневая модель канала хранения информации на дисковых накопителях;

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

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

Разработанные эффективные алгоритмы кодирования и декодирования двухмерных итеративных кодов в КХПИ на магнитных дисках, адаптированные к специфике информационных потоков;

Предложенные рекомендации по программной реализации СНХИ для разных типов дисков и операционных систем.

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

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

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

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

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

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

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

5.7. Выводы.

1. Предложена методика проведения разрушающих испытаний СНХИ. Показаны результаты проведения натурных испытаний ПО СНХИ для гибких магнитных дисков, полностью подтверждающие теоретические расчеты исправляющей способности итеративного кода СНХИ и корректность работы СНХИ. В частности, подтверждено, что алгоритм исправления ошибок, использующий свойства укороченного кода способен исправлять некоторые пакеты стираний длиной до пяти секторов;

2. Рекомендован способ внедрения программной СНХИ в структуру операционной системы в виде драйвера-фильтра защищаемого дискового устройства. Способ интеграции является универсальным по типу ОС;

3. Рекомендован необходимый набор вспомогательных средств и утилит, включающий средства подготовки (разметки) и проверки диска;

4. Рекомендован необходимый и достаточный набор средств разработки, использованный при создании программного обеспечения СНХИ, включающий средства разработки драйверов;

5. Рекомендован способ размещения и декларирования проверочных разрядов в виде псевдофайла в служебных структурах дисковой системы;

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

Заключение

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

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

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

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

Предложена методика проведения сравнительного анализа алгоритмов, в основе которой лежит: о выбор системы критериев; о определение численных значений критериев с использованием граф-схем алгоритмов; о выбор эффективных алгоритмов по предложенным системам критериев. Разработка эффективных алгоритмов кодирования итеративным кодом СНХИ проводилась по критерию число операций при кодировании Nk. Были предложены алгоритмы кодирования и варианты их реализации, позволяющие сократить число требующихся дисковых операций N^o и вычислительных операций NkK0 по сравнению со стандартным (базовым) алгоритмом кодирования.

Разработка эффективных алгоритмов декодирования проводилась по критерию максимизации исправляющей способности S. В результате были предложены алгоритмы, позволяющие исправлять все ошибки практически значимой кратности, по сравнению с базовым алгоритмом, и позволяющие сократить количество ключевых операций N^.

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

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

В промышленную эксплуатацию было введено два типа программных СНХИ, о чем имеются соответствующие акты внедрения (Прил.2.):

1. Система повышения надежности хранения информации на гибких магнитных дисках, работающей в ОС MS-DOS;

2. Система повышения надежности хранения информации на съемных жестких магнитных дисках IOMEGA JAZ 1 Gb, работающей в ОС Windows; Результаты выполнения диссертационной работы:

1. Разработана четырехуровневая модель КХПИ и показана адекватность модели для решения задач диссертационной работы. Обоснован выбор уровня дисковых операций для эффективной реализации СНХИ;

2. Обоснован выбор универсального метода повышения надежности хранения данных на МД с использованием двухмерных итеративных кодов;

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

4. Рекомендованы методы оценки численных значений критериев. Проведено ранжирование критериев по значимости и предложены методики исследования и разработки эффективных алгоритмов кодирования и исправления ошибок;

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

6. Предложены рекомендации для программной реализации СНХИ, инвариантной к типам дисков и операционных систем. На примере съемных жестких дисков IOMEGA JAZ и флоппи-дисков показано определение длин кодовых групп и способы размещения проверочных разрядов двухмерных итеративных кодов;

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

8. Рекомендована методика проведения испытаний СНХИ, демонстрирующая соответствие характеристик реализованной СНХИ поставленным требованиям и экспериментально подтверждающей основные теоретические результаты исследований. Метод, алгоритмы и рекомендации по программной реализации успешно реализованы и апробированы в учреждениях ГУ ЦБ РФ Пермской и Свердловской областей для защиты ключевой информации на съемных дисках. Эффективность предложенного МНХИ подтверждена актами приемки ПО.

Основные положения диссертационной работы отражены в 12 научных публикациях.

1. Сбои полупроводниковых запоминающих устройств при полетах спутников. // Москва: ВИНИТИ Надёжность и контроль качества №27. 1991. - С.25-28;

2. Алексеев В.Б., Сложность умножения матриц. // Кибернетический сборник. М.: Мир, 1988. №25 - С.72-89.

3. Амербаев В.М. под ред. Теория кодирования и оптимизация сложных систем. // М.: Наука, 1977. 217с.

4. Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. //М.: Мир, 1979.-420 е.;

5. Ахо А.В., Хопкрофт Д. Э., Ульман Д.Д. Структуры данных и алгоритмы. // М.: Вильяме, 2001.-356 е.;

6. Баласубраманян В. Синтезирование с помощью компилятора схемы контроля многопроцессорных систем на основе алгоритмов. // Москва: ВИНИТИ. Вычислительная техника №15,1991. С.2-15.

7. Белоусов В.В., Киселёв В.В., Кулагина М.М. Надёжность технических систем. Уч. Пособие. // Пермь: ПГТУ, 1995. - 112 е.;

8. Берлекемп Э., Алгебраическая теория кодирования.//М.: Мир, 1971. 287с.

9. Блох Э. Л., Пинскер М. С. под ред. Некоторые вопросы теории кодирования. // Библиотека Кибернетического сборника. М.: Мир 1970. 310с.

10. Бобровская И. К. Линейные искажения в каналах и трактах многоканальных систем и методы их корректирования.//Ленинград: ЛЭТИ, 1967. -212с.

11. Боровиков В. Отказоустойчивые дисковые массивы. // М.: КомпьютерПресс. №7, 2005. с 57-72.

12. Бородин Л.Ф. Введение в теорию помехоустойчивого кодирования. // М.: Советское радио, 1968. 173 с.

13. Боуз Р.К., Чоудхури Д.К., Дальнейшие результаты относительно двоичных групповых кодов с исправлением ошибок. // М.: Кибернетический сборник №6, 1963. С.34-48.

14. Боуз Р.К., Чоудхури Д.К., Об одном классе двоичных групповых кодов с исправлением ошибок. // М.: Кибернетический сборник №2, 1961. С.25-32.

15. Бояринов И.М. Помехоустойчивое кодирование числовой информации // М.: Наука, 1983.-212 с.

16. Букчин Л.В. Безрукий Ю.Л. Дисковая подсистема IBM-совместимых персональных компьютеров. // М.: Наука, 1993. 349 с.

17. Вентцель Е. С. Теория вероятностей. Уч.пособие //М.:Наука, 1969. 513 с.

18. Виноградов И. М. Основы теории чисел. // М.: Наука, 1965. 394 с.

19. Витерби А.Д., Омура Дж.К. Принципы цифровой связи и кодирования. // М.: Радио и Связь, 1982. 400с.

20. By К., Фухс В. Распределенная общая виртуальная память с восстановлением. // Москва: ВИНИТИ Вычислительная техника №18, 1991. С.8-13.

21. Габидулан Э. М., Афанасьев В.Б. Кодирование в радиоэлектронике. // М.: Радио и связь, 1986. 247 с.

22. Галлагер Р. Теория информации и надежная связь // М.: Советское радио, 1985.-321с.

23. Гёталс Дж.М. Делзарт П. Один класс циклических кодов с мажоритарным декодированием. // М.: Кибернетический сборник №6, 1963. с.46-49;

24. Гилберт И.Н. Синхронизация двоичных сообщений. // М.: Кибернетический сборник №5, Мир,1962. с.4-10.

25. Гольц Г. Рабочие станции и информационные сети. // М.: Машиностроение, 1990.-98с.

26. Гордеев А.В. Молчанов А. 10. Системное программное обеспечение. Уч.пособие. // СПб.: Питер, 2002. 539с.

27. Гутер Р.С., Резниковский П.Т. Программирование и вычислительная математика. //М.: Наука, 1971. 259с.

28. Гэри М., Джонсон Д. Вычислительные машины и труднорешимые задачи. //М.: Мир, 1982.-340с.

29. Дельсарт Ф., Четыре основных параметра кода и их комбинаторное значение. // М.: Кибернетический сборник. №14. Мир, 1977 с.67-79.

30. Домарёв В.В. Безопасность информационных технологий. // М.: Dia Soft, 2002. 670с.

31. Елманова Н.З., Трепалов С.В. Delphi 4. Технология СОМ. // М.:Диалог-МИФИ, 1999.-361с.

32. Ершов IO.JI. Проблемы разрешимости и конструктивные модели // М.: Наука 1980.-211с.

33. Житков М.Ю., Лицын С.Н. Применение кодов в системах телемеханики. Уч.пособие//Пермь: ПГТУ, 1988,- 178с.

34. Замаскированные бэд-блоки Электронный ресурс. / Малинников А.С. -Режим доступа http://fict.narod.ru/about/index.html ■ 19.06.2004 Загл. с экрана;

35. Зубков С.В. Assembler. //М.: Профиздат, 1999. 330с.

36. Иванов E.JI. Периферийные устройства ЭВМ. // М.: Высшая школа, 1987 -471с.

37. Карташевский В.Г., Мишин Д.В. Прием кодированных сигналов в каналах с памятью. // М.: Радио и связь, 2004. 391с.

38. Касами Т., Токура Н., Ивадари Ё., Инагаки Я., Теория кодирования. // М.: Мир, 1978.-346с.

39. Кларк Дж., Кейн Дж., Кодирование с исправлением ошибок в системах цифровой связи. // М.: Радио и связь, 1987. 218с.

40. Кокоулин А. Н., Кон Е. Л. Комплексная защита информации. // Материалы научно-практической конференции, Пермь, ПГТУ, 2000 с.84-92.

41. Кокоулин А. Н. Система надежного хранения информации на магнитных дисках. // Сборник научных трудов. Информационные управляющие системы. Пермь, ПГТУ, 1999 с.64-70.

42. Кокоулин А. Н., Кон Е. Л., Белоусов В. В., Торопицын С.В., Улинич А.С., Черепанов Ю.А. Защита базы данных от несанкционированного копирования и от несанкционированного доступа. // Материалы научно-практической конференции, Пермь, ПГТУ, 1998 с.34-42.

43. Кокоулин А. Н., Кон Е. Л. Выбор критериев и методики оценки вычислительной сложности алгоритмов кодирования блоковыми алгебраическими кодами. // Сборник научных трудов. Информационные управляющие системы. Пермь, 2002, с.32-39.

44. Кокоулин А. Н., Кон Е. Л. Усовершенствование алгоритма сжатия информации LZW для обработки информационных потоков с однородной структурой. // Сборник научных трудов Информационные управляющие системы Пермь, 2003, с.42-48.

45. Кокоулин А. Н., Кон Е. Л. Анализ вычислительной сложности алгоритмов. // Сборник научных трудов Информационные управляющие системы Пермь, 2001,-с.42-48.

46. Кокоулин А. Н., Кон Е. Л. Алгоритм исправления ошибок СНХИ с оптимальной для исправления ошибок малой кратности проверочной матрицей. // Сборник научных трудов Информационные управляющие системы Пермь, 2001, с.56-62.

47. Кокоулин А.Н., Кон Е.Л. Особенности реализации кодека помехоустойчивого кода в составе системы обеспечения надежного хранения информации на магнитных дисках (СНХИ). // Информационные управляющие системы, Сб. науч. трудов. Пермь, ПГТУ, 2000. с.23-29.

48. Кокоулин А.Н., Кон Е.Л. Алгоритм исправления ошибок системы надежного хранения информации с оптимальной для исправления ошибок малой кратности проверочной матрицей. // Системы мониторинга и управления. Сборник научных трудов, Пермь, 2006. с. 106-109.

49. Кокоулин А.Н., Кон Е.Л., Федорищев И.Ф. Использование алгоритмов сжатия в системах информационной безопасности. // Материалы 30-й научно-практической конференции, Пермь, 2003. с.49-50.

50. Кокоулин А.Н. Эффективные алгоритмы кодирования и исправления ошибок в отказоустойчивых системах. // Информационные технологии моделирования и управления, №3., ISDN 1813-9744, Воронеж: Научная книга, с.348-354

51. Кокоулин А.Н. Методы и алгоритмы повышения надежности хранения информации на магнитных дисках в системах RAID. // «Вестник КГТУ им. Туполева», №2. Казань, 2007. с.159-170.

52. Кон.Е.Л. Исследование помехоустойчивости и принципов построения цифровых систем передачи информации, использующих алгебраические коды. // Пермь: ПГТУ, 1989 108с.

53. Конопелько В.К. Теория норм синдромов и перестановочное декодирование помехоустойчивых кодов. // Москва: Наука. ISBN 5354004209. 2006, -210с.

54. Конопелько В.К., Лосев В.В. Надежное хранение информации в ЗУ. // М.: Радио и связь, 1986. 240с.

55. Королёв Л.Н. Микропроцессоры и персональные компьютеры. //Математика и кибернетика. М.: Знание, №5, 1986. с21-38.

56. Котов С.Л., Яковлев О.Е. О концепции оценки качества программного обеспечения. // Академия наук Украины. Управляющие системы и машины, №8,1991. с.58-63.

57. Криницкий Н. А. Алгоритмы вокруг нас. // М.: Наука, 1984. 128с.

58. Криницкий Н.А. Алгоритмы и роботы. // М.: Радио и связь, 1983. 212с.

59. Леверепц С. Организация управления в программном обеспечении. // Москва: ВИНИТИ Вычислительная техника №16,1991. С.2-7.

60. Михайлов Е. В. Помехозащищенность информационно-измерительных систем. // М.: Энергия, 1975. 230с.

61. Новиков Ф. А. Дискретная математика. // СПб.: Питер, 2004. 200с.

62. Овчинников В. Н. Устройства автоматического обмена информацией. // М.: Энергия, 1991.-321с.

63. Орлик С. Секреты Delphi на примерах. // СПб.: Печатный двор, 1999. -302с.

64. П. Нортон. Персональный компьютер IBM PC. // М.: Наука, 1994. 528с.

65. Питерсон У., Уэлдон Э., Коды, исправляющие ошибки. // М.: Мир, 1976. -740с.

66. Питрек М. Руководство программиста по Microsoft Windows 95. Русская редакция. // Microsoft Press, 1997. 580с.

67. Питрек М. Секреты системного программирования в Windows 95. // М.: Диалектика, 1996. 467с.

68. Правиков Д. Идентификация магнитных носителей. Дискеты. // М.: Монитор. №2, 1994.-с. 37-50.

69. Робачевский А. М. Операционная система UNIX. // СПб.: БВХ-Петербург, 1997. 530с.

70. Самойленко С.И., под ред. Кодирование в сложных системах. // М.: Наука, 1974.-260с.

71. Самофалов К.Г., Корнейчук В.И. Структурно-логические методы повышения надежности запоминающих устройств. // М.: Наука, 1970. 204с.

72. Советов Б.Я. Эффективность введения избыточности в системы передачи телемеханической информации. // М.: Наука, 1972. 60с.

73. Солдатов В. П. Программирование драйверов Windows. // М.: Бином, 2004. 430с.

74. Сорокина С. И., Тихонов А. Ю., Щербаков А.Ю. Программирование драйверов и систем безопасности. // СПб.: БХВ-Петербург, 2003. 432с.

75. Стокмейер JI. Классификация вычислительной сложности проблем. // М.: Кибернетический сборник. №26. 1990. с.63-80.

76. Тай Т. Восстановление потерянных данных. // Москва: ВИНИТИ Вычислительная техника №30,1991. С.2-7.

77. Тарьян Р.Э. Сложность комбинаторных алгоритмов. // М.: Кибернетический сборник. №17. Мир, 1980. с.28-40.

78. Тенденции развития и классификация дисковых массивов RAID российского производства. Электронный ресурс. - Режим доступа http://www.rink.ru/index.html -27.11.2004 - Загл. с экрана;

79. Технологии Zip: за и против Электронный ресурс. / Коженевский С. Режим доступа http://www.epos.kiev.ua/pubs/nk/ • 01.06.2004 - Загл. с экрана;

80. Устройства магнитного хранения информации Электронный ресурс. -Режим доступа http://uzh.boom.ru/pcmy/hdd01.htm (34 КБ) • 19.08.2002 -Загл. с экрана;

81. Файзуллина Р.Г. Программные средства резервирования ВЗУ. // Академия наук Украины. Управляющие системы и машины, УСиМ №6, 1988. с.89-95.

82. Файнстейн А. Основы теории информации. // М.: Мир, 1960г. 483с.

83. Фано Р. Передача информации. Статистическая теория связи. // М.: Мир, 1965.-231с.

84. Форни Т.Д. Каскадные коды. // М.: Мир, 1970. 290с.

85. Фролов А.В. Операционная система MS-DOS. // М.: Диалог-МИФИ, т.1. 1992.-220с.

86. Хачиян Л.Г. Сложность задач линейного программирования. // М.: Математика и кибернетика. №10, 1977. с.2-30.

87. Хеллест Т. О радиусе покрытия линейных циклических кодов и арифметических кодов. // М.: Кибернетический сборник. №25. Мир, 1988 с.9-22.

88. Хетагуров Я.А. Повышение надежности цифровых устройств методами избыточного кодирования // М.: Энергия, 1974. С. 22-36.

89. Хетагуров Я.А.,под ред. Надежность автоматизированных систем управления. //М.: Высшая школа, 1979. 232с.

90. Хонекамп Д. Программирование под Windows. // М.: Печатный двор, 1996.-410с.

91. Цыбаков Б.С Некоторые границы для кодов, исправляющих ошибки и дефекты. //М.: Наука, 1997. 102с.

92. Чарари Ф. Теория графов. // М.: Мир, 1973. 214с.

93. Шастова Г.А., Коёкин А.И. Выбор и оптимизация структуры информационных систем. // М.: Энергия, 1972. 140с.

94. Шилдт Г. Программирование на С и С++ для Windows 95. // М.: Печатный двор, 1996.-228с.

95. Шрайбер С. Недокументированные возможности Windows 2000. Библиотека программиста. //Спб.: Питер, 2002. 340с.

96. Шумаков П.В. Фаронов В.В. Delphi 4. Руководство разработчика баз данных. // М.: Знание, 1999. 640с.

97. Элиас П. Безошибочное кодирование. Коды с обнаружением и исправлением ошибок. // М.: Мир, 1956. 210с.

98. Элиас П. Кодирование для двух каналов с шумами Теория передачи сообщений.//М.: Мир, 1957.- 180с.

99. Элспас Б. Теория автономных линейных последовательных сетей. // М.: Кибернетический сборник №7, Мир, 1963. с56-76.

100. Элспас Б. Шорт Р. Об оптимальных кодах, исправляющих пакеты ошибок. Теория кодирования. // М.: Мир, 1964г. 332с.

101. Яблонский С.В. Введение в дискретную математику. // М.: Наука, 1986. -420с.

102. A giant leap for magnetic media. Электронный ресурс. / A. Thompson Режим доступа http://domino.research.ibm.com/comm/ wwwrthinkresearch.nsf/ pages/five#five -12.05.2004 - Загл. с экрана;

103. Abernethy, Dr. Robert В., The New Weibull handbook, Second Edition // John Wiley & Sons, 2003,- 130c.

104. Fault Tolerance Computing Электронный ресурс. / Ying Shi/ Carnegie Mellon University. Dependable Embedded Systems Режим доступа http://www.ece.cmu.edU/~koopman/dess99/faulttolerant/#Fault injection -18.04.1999-Загл. с экрана;

105. IBM sets new disk-drive world record, surpasses 10 billion bits per square inch Электронный ресурс. / IBM Journal of Research and Development Режим доступа http://www.almaden.ibm.com/st/projects/magneto/giantmr/ -01.02.2004 - Загл. с экрана;

106. Introduction to Feedback Control with Applications for HDDs Электронный ресурс. / Almaden Research Center Режим доступа www.almadenresearch .com/review.asp?number= 19832 - 08.10.2005 - Загл. с экрана;

107. Jason S. Goldberg, Prof. Jack K. Wolf. Timing Recovery For Magnetic Recording Using Cross-Correlation. // Center for Magnetic Recording Research. University of California at San Diego, 2005. 96c.

108. Magnetic and Optical Disk Control: Parallels and Contrasts Электронный ресурс. / Danny Abramovitch/ Agilent Labs Режим доступа http://www.labs.agilent.com/personal/Danny Abramovitch/pubs/ - 22.01.2004 -Загл. с экрана;

109. Nelson S., Wayne Т. Applied Life Data Analysis. // John Wiley & Sons, 1982. -382c.

110. On the performance of Turbo Product codes and LDPC Codes over Partial-Response Channels Электронный ресурс. /Jing Li, Erozan Kurtas Режим доступа www.ee.tamu.edu/~kurtas/ldpc.html 10.12.2002 - Загл. с экрана;

111. RAID Levels Электронный ресурс. Режим доступа http://www.raidadvisory.org/ -02.12.2003 - Загл. с экрана;

112. S.M.A.R.T. Self-Monitoring, Analysis and Reporting Technology Электронный ресурс. /Маврицин М. Режим доступа http://pcjs.chat.ru/ -02.12.2003 - Загл. с экрана;

113. Signal Processing for Storage Электронный ресурс. /Borivoje Nikolic/ Department of Electrical Engineering and Computer Sciences. University of California at Berkeley Режим доступа http://www.eecs.berkeley.edu/~bora

114. T.M. Duman, E. Kurtas. Performance of turbo codes over ERP4 equalized high density magnetic recording channels.// Proc. Global Conf. Comm., 1999. 83c.

115. T.Souvigner. Turbo decoding for PR4: parallel vs. serial concatenation. // Proc.Intl.Conf.Comm, 1999. 56c.

116. The future of magnetic data storage technology Электронный ресурс. / D. A. Thompson, J. S. Best/ IBM Journal of Research and Development Режим доступа http://www.research.ibm.com/journal/rd/443/thompson.pdf -01.05.2005 - Загл. с экрана;

117. The Turbo Decoding Algorithm and Its Phase Trajectories Электронный ресурс. / Dakshi Agrawal, T J Watson/ Research Center IBM Corporation -Режим доступа www.ibm.com/cmmresearch/ 12.07.2005 - Загл. с экрана;

118. Timing Recovery Using Cross-Correlation Электронный ресурс. / CMRR Research Review Режим доступа http://www.ece.cmu.edi; /CMRR/reader.asp?idx=211134 - 23.05.2002 - Загл. с экрана;