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

Ценность информации и удельный вес информационных услуг в жизни современного общества резко возросли. Вычислительные системы (ВС) превратились в универсальные средства для обработки всех видов информации, используемых человеком. По мере ускорения научно-технического прогресса повышается зависимость общества от степени достоверности, как работы самих ВС, так и хранимой и обрабатываемой в ВС информации. Актуальность и важность проблемы изучения и использования нетрадиционных методов обеспечения достоверности функционирования ВС обусловлены следующими причинами [6, 28, 47, 49, 53, 56, 68, 70, 82, 91, 92, 104, 110]:

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

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

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

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

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

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

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

Таким образом, в настоящее время возникла существенная необходимость в изучении и использовании новых методов контроля, принципиально отличающихся от традиционных. При этом широкие перспективы, в виду небывалого развития в сфере нейрокомпьютерных технологий, открываются на основе использования новых методов кодирования, таких, например, как система остаточных классов (СОК), позволяющая реализовать системы управления и связи, надежность и живучесть которых приближается к биологическим системам в сочетании с высоким быстродействием. Но если вопросам повышения быстродействия нейрокомпьютеров при использовании СОК в литературе уделяется должное внимание [2, 7, 10, 40, 44, 94, 110, 111], то корректирующие способности остаточных кодов мало изучены [5, 82, 93, 113]. Существующие теоретические оценки корректирующих свойств кодов СОК являются довольно грубыми [82], поэтому особое внимание в диссертационной работе уделено имитационному моделированию, как наиболее мощному средству для решения задачи исследования характеристик кодов в остатках. Акцент в работе делается на использовании особенностей СОК для достижения высокой надежности при сохранении высокого быстродействия и снижении вычислительной сложности используемых алгоритмов обработки.

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

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

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

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

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

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

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

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

4. Разработка математических методов, применяемых для определения появления переполнения в СОК, а также для идентификации одновременного возникновения переполнения и ошибки.

5. Изучение факторов, влияющих на корректирующие способности кодов в СОК. Разработка математической модели зависимости корректирующих способностей кодов в СОК от величины контрольного основания.

Для решения поставленных в работе научных задач использованы основы теории чисел, линейной алгебры, комбинаторики, теории вероятностей, известные положения теории нейронных сетей, теории исследования операций, теории надежности при использовании математического, имитационного и статистического моделирования с применением численных методов. При работе над диссертацией было применено следующее ПО: Microsoft Word 2000, Microsoft Excel 2000, Borland Pascal 7.0, MathCAD 7 Professional. Научная новизна работы заключается в следующем:

1. Систематизированы корректирующие коды и методы контроля ЭВМ. Дано обоснование положения остаточных R-кодов в общей систематизации и доказана их принадлежность к блоковым линейным кодам.

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

3. Определено влияние избыточности на отображение чисел в динамическом диапазоне. Разработаны алгоритмы определения знака числа и выявления переполнений, основанные на применении позиционной характеристики — номер интервала числа в избыточной СОК.

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

5. Предложены математические методы, применяемые для обнаружения переполнения в СОК.

6. Создан пакет программ, позволяющих изучать корректирующие свойства кодов в СОК (программы: перевод чисел из СОК в ПСС [два метода — КТО и ОПС], вычисление проекций числа в избыточной СОК, коррекция ошибок в избыточной СОК [два метода — КТО и ОПС], обработка переполнений, модификации, связанные с особенностями генерации обрабатываемых чисел и ошибок).

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

8. Получена модификация метода проекций, основанная на понятии.

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

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

10. Проанализированы результаты моделирования ситуации возникновения ошибки по старшему модулю при наличии в СОК одного контрольного основания.

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

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

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

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

В главе проанализированы и представлены в алгоритмической форме методы определения ошибок и переполнений в СОК, а также методы локализации и исправления ошибок в СОК.

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

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

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

На защиту выносятся следующие основные положения:

1. Систематизация и сравнительный анализ методов контроля работы ЭВМ, используемых для обнаружения и коррекции ошибок.

2. Математические методы и алгоритмы параллельного типа, применяемые для обнаружения, локализации и исправления ошибок в СОК.

3. Математические методы, применяемые для определения переполнения в СОК и методы, используемые для идентификации ситуации, соответствующей переполнению, возникновению одиночной ошибки или одновременному появлению переполнения и одиночной ошибки в избыточной СОК.

4. Сравнительный анализ алгоритма коррекции ошибок в СОК, выполненного двумя способами. Имитационные модели — пакет программ.

5. Математическая модель зависимости корректирующих способностей кодов в СОК от величины контрольного основания.

6. Обзор экспериментальных данных, полученных при использовании имитационной модели процесса коррекции ошибок.

Апробация работы. Результаты работы докладывались на ХЫУ, ХЬУ научно-методических конференциях «Университетская наука региону» (Ставрополь, СГУ, 1999, 2000гг.), на XXX научно-технической конференции «Вузовская наука — Северо-Кавказскому региону» (Ставрополь, СевероКавказский ГТУ, 1999 г.), на Всероссийской научной конференции.

Математическое моделирование в научных исследованиях" (Ставрополь, СГУ, 2000 г.), на XIII научно-технической конференции «Внедрение новых информационных технологий в процессы управления войсками и оружием, подготовку офицерских кадров в Вузах» (Ставрополь, ФРВИ РВ, октябрь 2000 г.), на Международной школе-семинаре по геометрии и анализу памяти Н. В. Ефимова (Абрау-Дюрсо, МГУ, РГУ, 2002 г.), на региональной научной конференции «Теоретические и прикладные проблемы современной физики» (Ставрополь, СГУ, сентябрь 2002 г.). Полученные результаты изложены в 9 статьях, в 6 тезисах докладов и одном отчете НИР.

Реализация результатов. Исследования проводились в рамках Федеральной целевой комплексной программы (Постановление правительства РФ № 945−95 от 28.08.96 г.). Теоретические и практические результаты диссертационной работы использованы при выполнении НИР «Новый класс нейронных цифровых фильтров с параллельной обработкой данных», номер Государственной регистрации № 01.02.105 057 по гранту Министерства образования РФ ТОО-3.3−292 и реализованы в проектно-конструкторской деятельности федерального государственного унитарного предприятия особого конструкторского бюро «ИКАР» г. Краснодар (НИР по специальной теме Моторалли — И), а также в учебном процессе СГУ.

Автор выражает искреннюю благодарность научному руководителюзаслуженному деятелю науки и техники РФ, доктору технических наук профессору, академику МАИ Н. И. Червякову, кандидату физико-математических наук, доценту А. Н. Макохе, а также коллективам кафедр алгебры и прикладной математики и информатики СГУ за помощь и поддержку, оказанную при написании диссертации, и критические замечания, высказанные при ее обсуждении.

158 Выводы.

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

Я Л у.

Рп-1.

1. Показано, что для любого Я-кода знание величины позволяет установить лишь гарантируемый минимум числа обнаруживаемых или исправляемых ошибок. Реальные корректирующие способности Я-кодов СОК выше тех, которые определяются теоремами 2.1 и 2.2 [82]. При количестве контрольных модулей г = 1 они зависят от величины степени избыточности Дизб, т.к. при г= 1 Ят5=р", а доказательство влияния изменения величины контрольного основания на корректирующие способности кодов СОК представлено в п. 3.5, 4.1, 4.2, 4.3.

2. Показана гибкость изменения корректирующих свойств кодов СОК без изменения способа кодирования и алгоритма коррекции ошибки.

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

Новые научные результаты главы.

1. Предложена математическая модель влияния на корректирующие способности кодов СОК величины контрольного основания при использовании двух рассматриваемых ранее методов (КТО, ОПС).

2. Показано, что при использовании упорядоченного Я-кода вероятность возникновения ошибки по разряду, соответствующему последнему модулю (рп = max. pi), выше, чем по остальным основаниям системы. При.

1, п моделировании ситуации стопроцентного возникновения ошибок по старшему модулю собраны и проанализированы экспериментальные данные (табл. П. 5.7-П.5.10, п. 4.2 рис. 4.4), позволившие сделать следующий вывод: даже в экстремальных ситуациях обнаруживающие и корректирующие способности остаточных кодов достаточно высоки и превышают гарантируемый теоремами 2.1 и 2.2 [82] минимум.

Согласно указанным теоремам арифметический Я-код может исправлять все совокупности из? и меньшего числа ошибок лишь в том случае, если для минимального расстояния кода с1 выполняется неравенство с1> 2? + 1. Показано, что при ?/ > Г + 1 из всех случаев возникновения пакетов ошибок длины? будут исправлены от 90 до 100% в зависимости от степени избыточности и выбора системы модулей. При выполнении условия с! >? + 1 будут обнаружены все t.

-•100% кратные ошибки и р ошибок кратности от (?+ 1) до п, где п количество модулей системы.

3. При помощи статистического моделирования была получена информация о корректирующих возможностях некоторых Я-кодов (рис. 4.8).

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

Заключение

.

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

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

2. Предложены геометрические интерпретации взаимного расположения ошибочных, положительных и отрицательных чисел, а также переполнений в области полного диапазона избыточной СОК, что позволило разработать алгоритмы определения знака числа и выявления переполнений, основанные на применении позиционной характеристики — номер интервала числа.

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

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

5. Разработан пакет программ (Borland Pascal v7.0), предназначенный для исследования корректирующих свойств кодов в СОК //имитационное моделирование//.

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

7. Проведенное математическое, информационное и статистическое моделирование для случая исправления ошибок в одной и двух, выбранных случайным образом позициях, позволяет сделать вывод: для того, чтобы арифметический Я-код гарантированно исправлял пакеты ошибок длины t необходимо, чтобы для минимального расстояния кода <Л выполнялось неравенство с1> 2t+, но в тоже время есть все основания утверждать, что при d>t+1 из всех случаев возникновения пакетов ошибок длины? будут исправлены от 90 до 100% в зависимости от степени избыточности и выбора системы модулей. Кроме того, при выполнении условия >? +1 будут обнаружены все ¿—кратные ошибки и Р ~~ Л у— -100% ошибок кратности от (?+1) до п, где пколичество модулей системы.

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

Таким образом:

1. Разработаны математические и алгоритмические основы методов коррекции ошибок и выявления переполнений в избыточной СОК.

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

3. При использовании математического, имитационного и статистического моделирования показано, что реальные корректирующие возможности кодов в СОК превышают существующие оценки как минимум в два раза.

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