Содержание к диссертации
Введение
Глава 1. Анализ методов, используемых для повышения достоверности работы ЭВМ 13
1.1. Аналитический обзор методов контроля технических средств вычислительных систем 13
1.2. Анализ математических основ построения корректирующих кодов 19
1.3. Арифметические остаточные коды, исправляющие ошибки 27
1.4. Постановка задачи исследования 41
Выводы 49
Глава 2. Разработка методов и алгоритмов обнаружения, локализации и коррекции ошибок в системе остаточныхклассов 51
2.1. Распределение ошибок в диапазоне представления чисел в избыточной системе остаточныхклассов 51
2.2. Разработка методов определения ошибок в СОК 62
2.3. Разработка алгоритмов для локализации ошибок в СОК 69
2.4. Разработка алгоритмов для исправления ошибок в СОК 72
2.5. Разработка методов определения переполнения динамического диапазона в СОК 79
Выводы 85
Глава 3. Разработка математических моделей коррекции ошибок в системе остаточных классов 87
3.1. Алгоритм метода проекций с использованием для обнаружения ошибки метода выхода за диапазон (КТО) 87
3.2. Анализ сложности алгоритма метода проекций (КТО) и его альтернативные реализации 94
3.3. Алгоритм коррекции ошибок на основе метода проекций с использованием для обнаружения ошибки метода перехода из системы остаточных классов в обобщенную полиадическую систему счисления 112
3.4. Анализ сложности алгоритма метода проекций (ОПС) 115
3.5. Сравнительный анализ алгоритма коррекции ошибок, выполненного двумя способами 119
Выводы 126
Глава 4. Экспериментальное исследование корректирующих способностей кодов в системе остаточных классов 128
4.1. Математическая модель влияния на корректирующие способности кодов величины контрольного основания 128
4.2. Теоретико-вероятностный подход к оценке возможности появления ошибки по одному из модулей системы с последующим моделированием наиболее вероятной ситуации 135
4.3. Статистическое моделирование при изучении факторов, влияющих на корректирующие способности кодов в СОК 142
4.4. Определение одновременного появления ошибки и переполнения при использовании избыточной СОК 148
4.5. Оценка результатов коррекции ошибок в избыточной системе остаточных классов 154
Выводы 158
Заключение 160
Библиографический список использованной литературы 163
Приложение 174
- Анализ математических основ построения корректирующих кодов
- Разработка алгоритмов для локализации ошибок в СОК
- Анализ сложности алгоритма метода проекций (КТО) и его альтернативные реализации
- Теоретико-вероятностный подход к оценке возможности появления ошибки по одному из модулей системы с последующим моделированием наиболее вероятной ситуации
Введение к работе
Ценность информации и удельный вес информационных услуг в жизни современного общества резко возросли. Вычислительные системы (ВС) превратились в универсальные средства для обработки всех видов информации, используемых человеком. По мере ускорения научно-технического прогресса повышается зависимость общества от степени достоверности, как работы самих ВС, так и хранимой и обрабатываемой в ВС информации. Актуальность и важность проблемы изучения и использования нетрадиционных методов обеспечения достоверности функционирования ВС обусловлены следующими причинами [6, 28, 47, 49, 53, 56, 68, 70, 82, 91, 92, 104, ПО]:
Резкое увеличение вычислительной мощности современных компьютеров при одновременном упрощении их эксплуатации. Высокие темпы роста парка ЭВМ, находящихся в эксплуатации в самых разных сферах деятельности и все чаще применяемых в качестве источников и получателей информации.
Расширение круга важных трудоемких задач, связанных с колоссальным объемом математических расчетов над большими массивами данных в реальном масштабе времени и предъявляющих все более жесткие требования к производительности и отказоустойчивости ВС.
Сложность схематической реализации традиционных методов контроля работы ЭВМ и существенные временные затраты, связанные с их применением для обеспечения достоверности результатов вычислений в ЭВМ.
Бесперспективность развития ЭВМ с фон-неймановской архитектурой, в том числе и многопроцессорных, для многих важных вычислительных задач.
Небывалый взрывной рост и распространение технологии получившей название нейрокомпьютинг, охватывающей параллельные, распределенные, адаптивные системы обработки информации, способные «учиться» обрабатывать информацию, действуя в информационной среде. Массовый характер применения нейрокомпьютеров (НК), как ВС с параллельной вычислительной архитектурой, для решения различных научно-технических задач. Распространение общей фундаментальной стратегии теоретических исследований, характерной чертой которых является применение подходов, базирующихся на интенсивном использовании различных форм параллелизма на алгоритмическом, программном и аппаратном уровнях.
На протяжении всего периода существования ЭВМ главными целями процесса развития вычислительных средств, в конечном счете, были и остаются повышение их производительности и надежности. Основными путями к достижению этих целей является совершенствование технологии производства средств вычислительной техники и внедрение новых, более эффективных способов организации и проведения вычислений, т.е. новых вычислительных структур. Анализ известных подходов, используемых при разработке высокопроизводительных и надежных вычислительных структур, показывает, что все они имеют одну общую отличительную особенность, суть которой состоит в широком применении тех или иных форм параллельной обработки. В этой связи особый интерес представляют исследования по теории и приложению нейрокомпьютерных технологий с параллельной обработкой данных, так как именно такие системы наилучшим образом приспособлены для параллельных вычислений. Наиболее привлекательными в этом отношении являются модулярные нейрокомпьютеры, обладающие максимальным уровнем внутреннего параллелизма. Другое важное достоинство модулярных нейрокомпьютеров, привлекающее к себе постоянное внимание специалистов по проектированию средств быстрой и достоверной переработки цифровой информации, заключается в высокой эффективности корректирующих кодов модулярных систем счисления. Алгебраическая структура остаточных кодов при введении избыточности позволяет обнаруживать, локализовать и исправлять ошибки с гибким изменением корректирующих свойств без изменения способов кодирования. Благодаря своей арифметичности, избыточные модулярные коды позволяют обнаруживать и корректировать как одиночные ошибки, так и пакеты ошибок не только при хранении и передаче числовой информации, но при выполнении арифметических операций.
Проблема обеспечения надежности модулярных нейрокомпьютерных систем является в настоящее время актуальной ввиду усложнения структуры самих нейрокомпьютеров и увеличения сложности выполняемых ими функций. Особенно остро проблема повышения надежности стоит для НК, разработанных в аэрокосмических и астрофизических системах, системах защиты, в контурах управления ответственными процессами или объектами, функционирующими в реальном масштабе времени и др.
Таким образом, в настоящее время возникла существенная необходимость в изучении и использовании новых методов контроля, принципиально отличающихся от традиционных. При этом широкие перспективы, в виду небывалого развития в сфере нейрокомпьютерных технологий, открываются на основе использования новых методов кодирования, таких, например, как система остаточных классов (СОК), позволяющая реализовать системы управления и связи, надежность и живучесть которых приближается к биологическим системам в сочетании с высоким быстродействием. Но если вопросам повышения быстродействия нейрокомпьютеров при использовании СОК в литературе уделяется должное внимание [2, 7, 10, 40, 44, 94, 110, 111], то корректирующие способности остаточных кодов мало изучены [5, 82, 93, 113]. Существующие теоретические оценки корректирующих свойств кодов СОК являются довольно грубыми [82], поэтому особое внимание в диссертационной работе уделено имитационному моделированию, как наиболее мощному средству для решения задачи исследования характеристик кодов в остатках. Акцент в работе делается на использовании особенностей СОК для достижения высокой надежности при сохранении высокого быстродействия и снижении вычислительной сложности используемых алгоритмов обработки.
Следовательно, возможность реализации на основе СОК систем, обладающих надежностью, живучестью и быстродействием, малая изученность корректирующих способностей кодов СОК, легкость и эффективность переноса алгоритмов арифметики СОК на быстро развивающуюся в последнее время нейросетевую структуру обосновывают актуальность исследований кодов, исправляющих ошибки, в системе остаточных классов.
Объектом диссертационных исследований является ЭВМ, а предметом -корректирующие избыточные коды в СОК.
Цель диссертационной работы заключается в повышении достоверности и надежности функционирования ЭВМ при использовании избыточных кодов СОК, исправляющих арифметические ошибки.
Научная задача исследований состоит в разработке математических методов и алгоритмов, применяемых при коррекции ошибок в СОК.
Для решения поставленной общей научной задачи разобьем ее на ряд частных задач:
Систематизация и анализ методов контроля ЭВМ и кодов, используемых для коррекции ошибок. Обоснование положения остаточных кодов в общей систематизации.
Разработка и анализ алгоритмических структур параллельного типа, применяемых для обнаружения, локализации и исправления ошибок в СОК.
Выявление оптимального метода коррекции ошибок. Разработка имитационной модели процесса коррекции ошибок и получение при ее использовании экспериментальных данных, т.е. создание пакета программ, позволяющих изучать корректирующие свойства кодов в СОК.
Разработка математических методов, применяемых для определения появления переполнения в СОК, а также для идентификации одновременного возникновения переполнения и ошибки.
Изучение факторов, влияющих на корректирующие способности кодов в СОК. Разработка математической модели зависимости корректирующих способностей кодов в СОК от величины контрольного основания.
Для решения поставленных в работе научных задач использованы основы теории чисел, линейной алгебры, комбинаторики, теории вероятностей, известные положения теории нейронных сетей, теории исследования операций, теории надежности при использовании математического, имитационного и статистического моделирования с применением численных методов. При работе над диссертацией было применено следующее ПО: Microsoft Word 2000, Microsoft Excel 2000, Borland Pascal 7.0, MathCAD 7 Professional. Научная новизна работы заключается в следующем:
Систематизированы корректирующие коды и методы контроля ЭВМ. Дано обоснование положения остаточных R-кодов в общей систематизации и доказана их принадлежность к блоковым линейным кодам.
Проведен сравнительный анализ свойств различных способов аппаратного контроля: резервирования, контроля по модулю и методов, основанных на использовании корректирующих кодов, функционирующих в СОК и в позиционной системе счисления (ПСС).
Определено влияние избыточности на отображение чисел в динамическом диапазоне. Разработаны алгоритмы определения знака числа и выявления переполнений, основанные на применении позиционной характеристики - номер интервала числа в избыточной СОК.
Разработано два алгоритма коррекции ошибок в СОК: один основан на применении Китайской теоремы об остатках (КТО), другой - на переходе в обобщенную позиционную систему счисления (ОПС). Проведенный сравнительный анализ результатов работы алгоритмов позволил предложить улучшение алгоритма метода КТО.
Предложены математические методы, применяемые для обнаружения переполнения в СОК.
Создан пакет программ, позволяющих изучать корректирующие свойства кодов в СОК (программы: перевод чисел из СОК в ПСС [два метода - КТО и ОПС], вычисление проекций числа в избыточной СОК, коррекция ошибок в избыточной СОК [два метода - КТО и ОПС], обработка переполнений, модификации, связанные с особенностями генерации обрабатываемых чисел и ошибок).
Получена новая аналитическая зависимость, позволяющая сократить объем вычислений и исправлять одиночную ошибку при наличии в системе одного или двух контрольных оснований.
Получена модификация метода проекций, основанная на понятии At . суженного диапазона и предположении, что проекция тш соответствует ошибочному разряду, позволяющая исправлять ошибки при одном контрольном основании и разделяющая ошибки на гарантированно исправленные и исправленные без гарантии.
С применением численных методов получена математическая модель зависимости корректирующих свойств кодов от величины контрольного основания.
Проанализированы результаты моделирования ситуации возникновения ошибки по старшему модулю при наличии в СОК одного контрольного основания.
Рассмотрена проблема выявления одновременного появления переполнения и ошибки и предложены критерии для идентификации данной ситуации с последующим ответом на вопрос, что произошло: положительное, отрицательное переполнение, ошибка или переполнение и ошибка одновременно.
Работа состоит из введения, четырех глав, заключения и приложений.
В первой главе на базе анализа основных существующих методов контроля работы ЭВМ проведено обоснование целесообразности исследований кодов СОК. Результатом проведенного обоснования является постановка задачи исследований.
Представлен обзор существующих методов контроля работы ЭВМ, выполнена их систематизация и сравнительная оценка свойств. Предложена классификация и рассмотрена математическая база построения основных корректирующих кодов. Показано, что на сегодняшний день корректирующие коды в остатках являются одними из наиболее эффективных корректирующих кодов с легкой процедурой кодирования (в случае целых чисел) и сравнительно легкой процедурой декодирования. Проанализирована концепция помехоустойчивого кодирования и приведены аспекты ее реализации в СОК.
Вторая глава посвящена анализу распределения в полном диапазоне избыточной СОК положительных, отрицательных и ошибочных чисел, а так же чисел, полученных в результате переполнения. Показана эффективность применения интервального метода, основанного на использовании позиционной характеристики - номер интервала числа, для определения ошибки, переполнения (положительного, отрицательного), знака числа в избыточной СОК.
В главе проанализированы и представлены в алгоритмической форме методы определения ошибок и переполнений в СОК, а также методы локализации и исправления ошибок в СОК.
Третья глава конструктивна. В ней с использованием математических методов, применяемых в избыточной СОК для обнаружения, локализации и исправления ошибок, разработана модель процесса коррекции ошибок и обработки переполнений, реализованная двумя способами. Первый способ базируется на методе выхода за диапазон, с переходом из СОК в ПСС с применением КТО. Алгоритм второго способа отличается от предыдущего только тем, что почти все вхождения метода выхода за диапазон были заменены методом перехода в ОПС. В главе предложен анализ вычислительной сложности рассмотренных алгоритмов и сравнительный анализ их эффективности, выполненный при использовании разработанных на основе разбираемых алгоритмов программ и проведенный по трем параметрам: быстродействие, качество обнаружения и коррекции ошибок.
Четвертая глава является, по сути, экспериментальной частью диссертации. В ней приводятся и анализируются результаты экспериментов, проводимых при помощи имитационных моделей, разработанных на основе алгоритмов, предложенных в третьей главе. Построена математическая модель влияния на корректирующие способности кодов величины контрольного основания. При помощи статистического моделирования дается оценка корректирующих способностей некоторых R-кодов СОК. Проведен анализ результатов обработки переполнений при наличии в системе модулей одного и двух контрольных оснований. Предложен интервальный метод установления факта произошедшего переполнения, возникшей ошибки или ситуации, соответствующей одновременному появлению переполнения динамического диапазона и одиночной ошибки при наличии в системе двух контрольных оснований.
В заключении обобщены итоги и результаты проведенных исследований. В приложениях приводятся листинг и результаты работы программ, примеры и таблицы.
На защиту выносятся следующие основные положения:
Систематизация и сравнительный анализ методов контроля работы ЭВМ, используемых для обнаружения и коррекции ошибок.
Математические методы и алгоритмы параллельного типа, применяемые для обнаружения, локализации и исправления ошибок в СОК.
Математические методы, применяемые для определения переполнения в СОК и методы, используемые для идентификации ситуации, соответствующей переполнению, возникновению одиночной ошибки или одновременному появлению переполнения и одиночной ошибки в избыточной СОК.
Сравнительный анализ алгоритма коррекции ошибок в СОК, выполненного двумя способами. Имитационные модели - пакет программ.
Математическая модель зависимости корректирующих способностей кодов в СОК от величины контрольного основания.
Обзор экспериментальных данных, полученных при использовании имитационной модели процесса коррекции ошибок.
Апробация работы. Результаты работы докладывались на XL IV, XLV научно-методических конференциях «Университетская наука региону» (Ставрополь, СГУ, 1999, 2000гг.), на XXX научно-технической конференции «Вузовская наука - Северо-Кавказскому региону» (Ставрополь, Северо-Кавказский ГТУ, 1999г.), на Всероссийской научной конференции «Математическое моделирование в научных исследованиях» (Ставрополь, СГУ, 2000г.), на XIII научно-технической конференции «Внедрение новых информационных технологий в процессы управления войсками и оружием, подготовку офицерских кадров в Вузах» (Ставрополь, ФРВИ РВ, октябрь 2000 г.), на Международной школе-семинаре по геометрии и анализу памяти Н.В.Ефимова (Абрау-Дюрсо, МГУ, РГУ, 2002г.), на региональной научной конференции «Теоретические и прикладные проблемы современной физики» (Ставрополь, СГУ, сентябрь 2002г.). Полученные результаты изложены в 9 статьях, в 6 тезисах докладов и одном отчете НИР.
Реализация результатов. Исследования проводились в рамках Федеральной целевой комплексной программы (Постановление правительства РФ №945-95 от 28.08.96 г.). Теоретические и практические результаты диссертационной работы использованы при выполнении НИР «Новый класс нейронных цифровых фильтров с параллельной обработкой данных», номер Государственной регистрации №01.02.00105057 по гранту Министерства образования РФ ТОО-3.3-292 и реализованы в проектно-конструкторской деятельности федерального государственного унитарного предприятия особого конструкторского бюро «ИКАР» г. Краснодар (НИР по специальной теме Моторалли - И), а также в учебном процессе СГУ.
Автор выражает искреннюю благодарность научному руководителю -заслуженному деятелю науки и техники РФ, доктору технических наук профессору, академику МАИ Н.И. Червякову, кандидату физико-математических наук, доценту А. Н. Макохе, а также коллективам кафедр алгебры и прикладной математики и информатики СГУ за помощь и поддержку, оказанную при написании диссертации, и критические замечания, высказанные при ее обсуждении.
Анализ математических основ построения корректирующих кодов
Теория кодирования - довольно молодая ветвь дискретной математики, возникшая 50 лет назад из практической задачи об исправлении ошибок в цифровой информации [37]. Основная математическая задача формулируется просто - найти в и-мерном кубе максимальное число Ain d) вершин таких, что для любых двух вершин кратчайший путь состоит из, как минимум, d ребер. Или, равносильно, найти множество С л-мерных двоичных векторов таких, что d(x,y) = \xryi\+...+\xn -у„\ d для любых двух векторов х и у из С (множество С называется кодом, и код способен исправить t ошибок при 2t d).C основными понятиями теории кодирования можно познакомиться, используя литературу [2, 18, 22, 36, 73, 117]. Большинство результатов теории кодирования с небольшими изменениями можно использовать при введении аппаратурной кодовой избыточности. Интенсивная реализация методов помехоустойчивого кодирования в ЭВМ началась с памяти. Практически во всех выпускаемых машинах введено исправление одиночных ошибок и обнаружение двойных ошибок в оперативной памяти с помощью кода Хэмминга. В различных устройствах внешней памяти для обнаружения и исправления пакетов ошибок используются циклические коды. Коды Хэмминга применяются и в сверхоперативной памяти. Для обнаружения и исправления ошибок в работе исполнительных устройств были созданы специальные коды, которые принято называть арифметическими (АК) [23 - 25].
Итак, управление правильностью или помехозащищенностью обработки и передачи информации выполняется с помощью помехоустойчивого кодирования [22, 26, 29, 61, 79]. Различают коды, обнаруживающие ошибки, и корректирующие коды, которые дополнительно к обнаружению еще и исправляют ошибки. В настоящее время существует огромное количество кодов, обнаруживающих и исправляющих ошибки [2 - 4,9,11,14,18,22 - 26,36,37, 62, 64, 65, 69, 73, 75, 78, 80, 82, 86, 87, 116]. Некоторым отражением всего существующего многообразия корректирующих кодов является классификация, приведенная на рис. 1.3. Из рис. 1.3 видно, что все коды делятся на алгебраические и AIDC - коды. AIDC - коды включают в себя коды, относящиеся к технологиям, объединяемым понятием - автоматическая идентификация. Обладающие корректирующими свойствами двумерные коды [62] - технология, имеющая по всем оценкам огромные перспективы, предполагающая, что все символы представлены в двумерной форме кодирования информации. Наряду с возможностью переноса большего объема и более высокой плотности информации отличительной чертой, присущей недавно появившимся символикам является наличие контроля ошибок (защита и исправление).
Под алгебраическими кодами будем понимать корректирующие коды, которые в [72] определяются как специальные коды, позволяющие обнаруживать и исправлять определенные ошибки, возникающие при передаче и обработке информации в вычислительных машинах, телемеханических системах и линиях связи.
Из схемы (рис. 1.3) видно, что алгебраические коды делятся на одномерные, двумерные, ...,т- мерные итеративные коды.
Помехоустойчивые алгебраические одномерные коды можно подразделить на два больших класса блочные (без памяти) [36, 73] и непрерывные. В случае блочных кодов, при кодировании, каждому дискретному сообщению ставится в соответствие отдельный блок кодовых символов, называемый кодовой комбинацией. Непрерывные (неблоковые) коды образуют последовательность символов неразделяемых на кодовые комбинации. Для неблокового кодирования свойственно наличие памяти и характерен эффект размножения ошибок [18]. Существует много способов введения памяти, что отражается в названиях соответствующих методов (цепные коды, коды с зацеплением, древовидные, сверточные коды).
Блоковым кодом С длины п объема М называется произвольное множество из М букв алфавита Ап, т.е. произвольное множество из М различных п -блоков [18].
Для блокового кодирования присуще отсутствие памяти. Блоковые коды делятся на линейные и нелинейные. Линейные коды лучше изучены и отличаются многообразием подмножеств. Введем понятие линейного кода.
Совокупность всех векторов длины п с координатами из конечного поля GF(q) называют векторным пространством V над GF(q), если определены операции суммирования любых двух векторов и умножение вектора на любой элемент из GF(q). В общем случае кодом называется любое подмножество векторов. Среди этих подмножеств важную роль играют линейные подпространства [18, 51, 53].
Множество С векторов называется линейным подпространством, если: 1) для любых двух векторов этого множества х, у є С, х + у є С; 2) для любого вектора х е С и любого элемента а є GF{q) вектор ах є С. Векторное пространство Vможно задать с помощью базиса из п векторов:
Это означает, что любой вектор из V может быть однозначно представлен как линейная комбинация этих векторов с коэффициентами из GF(q).
Аналогично, любое линейное подпространство С можно задать с помощью базиса из к линейно независимых векторов (1 к п):
Число к называют размерностью подпространства. Очевидно, что число различных векторов в -мерном подпространстве равно дк. Линейным {п, к) -кодом называют -мерное линейное подпространство. Линейные коды играют важную роль в теории кодирования, прежде всего потому, что для них проста процедура кодирования. Для нелинейного кода объемом М = qk необходимо помнить все qk кодовых последовательностей. Для линейного кода можно ограничиться хранением лишь к векторов g\, g2,..., g „ или эквивалентной им порождающей матрицы кода
Для кодирования достаточно задать блок информационных символов а = {а\, а2, ..., ак). Тогда кодовый вектор получаются путем умножения этого вектора на порождающую матрицу G: Линейный код можно задать и по-другому. Пусть Н - матрица размера гхп с линейно-независимыми строками, где г = п-к, такая, что
Тогда любое кодовое слово g удовлетворяет уравнению Это легко проверить, умножив (1.11) слева на вектор а и воспользовавшись (1.10). Таким образом, линейный код можно определить как множество решений (1.12). Матрица Н называется проверочной матрицей кода. Оба способа задания линейного кода - с помощью порождающей матрицы G и с помощью проверочной матрицы Н- эквивалентны.
К числу эффективных кодов, обнаруживающих одиночные, кратные ошибки и пачки ошибок, относятся циклические коды. Положительными свойствами циклических кодов являются малая вероятность не обнаружения ошибки и сравнительно небольшое число избыточных разрядов.
Линейный код С называется циклическим, если циклический сдвиг кодового вектора х = (х0, хь ..., хп.\), т. е. вектор х = {х\, ..., хп.\, хо), также является кодовым.
Разработка алгоритмов для локализации ошибок в СОК
Метод проекций базируется на операции сокращения набора оснований [112], и при г = 2 его алгоритм сводится к следующему: для корректируемого числа находим проекции путем последовательного отбрасывания из системы модулей по одному основанию pt и соответствующему остатку в представлении числа. Проекция от числа А, представленного в СОК своими остатками (а\, (Z2,..., а„), обозначающаяся как А{ =(al,...,ai_l,aM,...,an) при /-й ошибочной цифре, может рассматриваться как число, входящее в альтернативную совокупность чисел, анализ которой позволяет сделать вывод о правильности отдельных цифр. Два избыточных модуля позволяют локализовать ошибочную сбойную цифру, которая преобразовала А в А, со 100% гарантией. Локализация ошибок основана на том факте, что при г = 2 в случае одиночной ошибки одна из проекций корректируемого числа - At, где / є {1, ...,k+r}, оказывается разрешенной и является правильным числом, а другие проекции Aj, для jФ i, j = l,k + r являются не разрешенными [82].
Механизм изоляции ошибочной цифры, заключается в нахождении разрешенной проекции А{. Отсюда следует, что если At - разрешенная проекция числа, то ошибка произошла в /-й цифре и At является правильной величиной числа А. К тому же правильная величина остаточной цифры а, будет правильной цифрой в представлении числа по модулю /?,-, что позволяет откорректировать /-ю секцию для последующих просчетов.
Проиллюстрируем рассмотренный метод. В приложении 2 приводится текст программы project.pas, являющейся имитационной моделью метода проекций. Она позволяет для заданного в ПСС числа находить его представление в СОК, генерировать в этом представлении ошибки, определять вес базиса и базис, находить проекции для полученного ошибочного представления данного числа в СОК. Работа программы организованна при помощи меню:
При выборе пунктов 1 и 2 осуществляется ввод системы модулей (с клавиатуры или при помощи программы), числа, заданного в ПСС и оговаривается количество генерируемых ошибок. После этого программа обрабатывает полученные данные (находит величину проекций в ПСС) и все результаты не только выводит на экран, но и помещает в файл. Посмотрим на примере, какая именно информация хранится в файле, формируемом в ходе работы программы. Получено неверное число. В десятичной системе счисления оно равно: 103212.
Таким образом, просмотрев файл, узнав из него значения рабочего диапазона и проекций, можно сделать вывод: ошибка произошла по второму модулю, и теперь ее можно легко исправить. Кроме того, хочется отметить тот факт, что значение проекции А2 есть ни что иное, как правильная величина числа А в ПСС.
Предположим теперь, что, перебрав все основания, мы не смогли локализовать ошибку. Это означает, что ошибка не является одиночной. Тогда начнем исключать различные пары модулей, тройки и т.д. (при условии, что минимальное расстояние кода достаточно велико). Если при исключении какой-либо комбинации из t модулей (t k) число А попадет в интервал [0,R), то можно утверждать, что именно в этих модулях произошли ошибки. В [82] отмечается, что быстродействие рассмотренного метода локализации ошибок относительно не велико, т.к. для оценки величины числа в каждой из сокращенных СОК требуется выполнять п модульных операций. Эффективность алгоритма можно увеличить, если использовать для определения принадлежности проекций к интервалу [0,R] позиционную характеристику - номер интервала числа, хотя стоит учитывать, что недостатком данного метода является большая величина модуля преобразования, равного —.
Вычисление истинных значений искаженных символов можно осуществить любым из методов, предложенных в следующем параграфе.
Анализ сложности алгоритма метода проекций (КТО) и его альтернативные реализации
Разработка эффективных алгоритмов не менее важна, чем разработка быстрой электроники [44]. Руководствуясь этим замечанием, остановимся подробнее на анализе сложности приведенного выше алгоритма. Говоря о сложности, будем иметь в виду временную сложность алгоритма.
Временем работы алгоритма называется число элементарных шагов, которые он выполняет [39, 44]. Под элементарными шагами будем понимать такие базисные операции, как сложение, умножение, замены, безусловные передачи управления и вызовы подпрограмм.
При анализе сложности алгоритма будем пользоваться функцией времени вычислений - ТА (п), которой в [2] дается следующее определение: «Пусть А -алгоритм и S - множество допустимых значений входа для А. Целое число ТА (п) для п є S - число базисных операций, выполняемых алгоритмом А при значении входа п, - называется функцией времени вычислений, ассоциированной с А и определенной на S».
Анализируя алгоритм, можно стараться найти точное количество выполняемых им действий. Но в большинстве случаев игра не стоит свеч, и достаточно оценить асимптотику роста времени работы алгоритма при стремлении размера входных данных к бесконечности. Если у одного алгоритма асимптотика роста меньше, чем у другого, то в большинстве случаев он будет эффективнее для всех входов, кроме совсем коротких. (Хотя бывают и исключения) [44]. В [7] дается следующее определение: «Время, затрачиваемое алгоритмом, как функция размера (меры количества входных данных) задачи, называется временной сложностью этого алгоритма. Поведение этой сложности в пределе при увеличении размера задачи называется асимптотической временной сложностью».
Для обозначения порядка сложности алгоритма будем использовать О-обозначение, которое применяется чаще, из используемых при анализе алгоритмов асимптотических обозначений (0, О, Q, о, со) и имеет точное определение.
В (3.7) заключено правило, состоящее в том, что вычисление является «легким», если мы имеем дело с полиномиальным по времени алгоритмом, т. е. с функцией вида ТА (п) = О (п), и «сложным», если мы имеем дело с экспоненциальным по времени алгоритмом (ТА (п) = 0(2 ")) [2].
Итак, вернемся к алгоритму метода проекций, реализованного с использованием КТО. Программа, написанная на основе рассматриваемого алгоритма, включает в себя 27 подпрограмм: 7 функций и 20 процедур.
Функции: перевод в двоичную систему счисления целого десятичного числа, нахождение минимума среди элементов целочисленного массива, тест простоты числа, поиск наибольшего общего делителя двух чисел щ и п2, решение сравнений первой степени, контроль над вычисленными базисами, вычисление величины числа (представленного в СОК) в ПСС.
Процедуры: вычисление полного диапазона СОК Р и рабочего диапазона R, перевод числа из ПСС в СОК, вычисление веса базиса, вычисление базиса, перевод числа из СОК в ПСС, генерация ошибки в представлении числа в СОК, 5 процедур ввода данных, локализация ошибок, исправление ошибок, перемещение ошибочных разрядов в конец представления числа в СОК, 5 процедур для работы с файлами и процедура выполнения всего процесса, сопровождаемого помещением результатов в файлы.
Анализ сложности процедур ввода данных и работы с файлами, функции перевода целого десятичного числа в двоичную систему счисления и процедуры генерации ошибки в представлении числа в СОК не представляют интереса, поскольку, если и участвуют непосредственно в самом процессе коррекции ошибки, то носят второстепенный характер и имеют, как правило, сложность не выше О (п). п - разрядность СОК, которая в соответствии с понятием оптимального набора модулей, изменяется в пределах двух десятков, т.е. довольно мала.
Сложность алгоритмов вычисления полного диапазона Р СОК, рабочего диапазона R и ортогональных базисов, алгоритмов перевода числа из ПСС в СОК, контроля над подсчитанными базисами и нахождения минимума среди элементов целочисленного массива вычисляется без особого труда и равна О (п), Т.К. СООТВеТСТВеННО 7caIcPPRR(w) = 6л-2, TcalcBasisO) = 5л-4, Ткотег(п) = 2и-2, 7Vest(«) = Зи+3, Tmin(n) - Зи+1. Здесь п также разрядность СОК, являющаяся неизменной величиной на протяжении всего алгоритма и характеризующаяся следующим сравнением: п « R и, тем более п « Р, где R - рабочий, а Р -полный диапазон СОК. Следовательно, сложность перечисленных 17-ти подпрограмм можно оценить как О (1).
Функция Prim булевского типа проверяет простоту числа. Используется только для проверки простоты оснований СОК. Наибольшее число итераций произойдет при вызове Prim(/?n), где рп - последний модуль из упорядоченных по возрастанию оснований системы модулей СОК. Но рп « Р, следовательно, порядок сложности функции Prim так же равен О (1).
Далее рассмотрим тесно связанные между собой подпрограммы, от эффективности реализации которых зависит эффективность метода в целом.
Теоретико-вероятностный подход к оценке возможности появления ошибки по одному из модулей системы с последующим моделированием наиболее вероятной ситуации
Ошибки, возникающие при работе ЦВМ, носят характер несхожий с ошибками, возникающими при передаче информации по каналам связи, так как машина в большей степени защищена от внешних воздействий. И здесь наиболее вероятными оказываются одиночные ошибки. Представляет интерес вопрос: по какому модулю в случае появления сбоя с большей вероятностью произойдет ошибка? Для того чтобы ответить на этот вопрос, воспользуемся элементами теории вероятностей и решим ряд вспомогательных задач. Задача 1. В ходе вычислений, проводимых при обработке данных в СОК, была получена цифра а/ є {0, 1, ...,р„}. Найти вероятность того, что a) была получена верная цифра; b) произошла ошибка. Решение. Обозначим через А - событие - получена верная цифра, А - произошла ошибка. Решим сначала задачу для конкретного модуля рь а потом рассмотрим общий случай. Пусть р\ 3, тогда лишь одна из цифр 0, 1, 2 - верна. Воспользуемся классическим определением вероятности, в соответствии с которым вероятность события А вычисляется по формуле где т - число элементарных исходов, благоприятствующих событию А; п число всех возможных элементарных исходов испытания. В нашем случае т = 1, п =3, следовательно, Р(А) = -, а Р\А)= —. Переходя от частного к общему, имеем: каким бы ни было значение модуля ph число исходов благоприятствующих событию А всегда будет одинаково и равно 1, а число всех возможных элементарных исходов испытания - величине р{. Следовательно, в общем случае: Задача 2. Какова вероятность того, что сбойными окажутся т из п модулей СОК? Решение. 1 Имеем п модулей независимых между собой. Следовательно, можно воспользоваться схемой независимых испытаний Бернулли. Таким образом, что бы определить вероятность того, что сбойными окажутся га из и модулей СОК, достаточно воспользоваться формулой Решим частную задачу. Задача 3. Найти вероятность события, состоящего в том, что сбойными окажутся 0 модулей из 7-ми, 1 из 7-ми, 2 из 7-ми,..., 7 из 7-ми модулей. Решение. Очевидно, что для решения задачи достаточно воспользоваться
Т.е., придерживаясь теоретико-вероятностного подхода, можно заключить, что в случае неполадок вероятнее всего сбойными окажутся 3-4 модуля из семи или примерно половина из имеющихся оснований. Но как уже отмечалось при работе ЦВМ, наиболее вероятными оказываются одиночные ошибки. Задача 4. Вероятность того, что сбойным окажется один из семи модулей, равна (см. задачу 3). СОК задана модулями: {3, 5, 7, 11, 13, 17, 19 (или 79)}. 128 Вероятность того, что в случае сбоя ошибка произойдет по первому модулю, Решение. Пусть А - событие, состоящее в появлении ошибки по одному из семи модулей при наличии одного сбойного модуля. В\ гипотеза, состоящая в появлении ошибки по первому модулю; В2 гипотеза, состоящая в появлении ошибки по второму модулю; В7 гипотеза, состоящая в появлении ошибки по седьмому модулю; Воспользовавшись формулой полной вероятности, найдем вероятность события А. Итак, мы подошли к задаче, решение которой будет являться ответом на поставленный ранее вопрос: по какому модулю в случае появления сбоя с большей вероятностью произойдет ошибка? Задача 5.
Произошел сбой по одному из модулей. Определить по какому модулю из семи {3, 5, 7, 11, 13, 17, 19 (79)} с большей вероятностью произойдет ошибка, если вероятность появления ошибки по одному модулю при наличии одного сбоя при р7 = 19 равна 0.331, а при р7 = 79 - 0.333. Решение. Для решения этой задачи воспользуемся формулой Байеса. вероятность появления ошибки при сбое по / - ому модулю, причем P(Bj) = для любого / є{1, 2, ..., 7}, А - событие, состоящее в появлении ошибки по одному модулю при одном сбое. Таблица 4.6 Из табл. 4.6 видим, что в случае появления сбоя, ошибка с большей вероятностью произойдет по разряду, соответствующему последнему, седьмому модулю, который в ходе проводимых экспериментов являлся контрольным. Задача 5 является частной задачей, т.е. решена она для конкретной СОК, но из ее решения, а точнее по результатам табл. 4.6 можно сделать общие выводы. Очевидно, что с увеличением значения контрольного модуля уменьшается вероятность получения ошибки по какому—либо информационному модулю, но увеличивается вероятность возникновения ошибки по контрольному основанию. Кроме того, легко видеть, что, чем больше величина основания, тем больше вероятность появления ошибки по разряду, соответствующему этому основанию. Таким образом, в случае появления сбоя, ошибка с большей вероятностью произойдет по разряду, соответствующему контрольному модулю.
Посмотрим, как изменятся корректирующие способности кодов в СОК, если формировать ошибку по старшему, контрольному модулю (г = 1, г = 2). Подвергнем небольшой модификации программы КТО, ОПС (приложение 3, 4), таким образом, чтобы генерируемая ошибка возникала только в последнем контрольном разряде, т.е. смоделируем ситуацию, соответствующую отказу последнего модуля. При помощи полученных программ - КТОрп, ОПСрп заполним таблицы (приложение 5 табл. П.5.7, П.5.8, П.5.9, П.5.10) и проанализируем, как исследуемый нюанс отразится на обнаруживающих и исправляющих способностях R-кода. Определим постоянный набор информационных модулей: (3, 5, 7, 11, 13, 17), т.е. R = 255255. Будем изменять контрольное основание и количество сгенерированных ошибок. Для каждого полученного, таким образом, варианта проведем 4 испытания и вычислим среднее значение всего количества исправленных ошибок, а также среднее количество ошибок, исправленных с гарантией. В каждом испытании будем обрабатывать массив из 1000 целочисленных элементов, сформированных генератором псевдослучайных чисел в диапазоне от 0 до 255255. По данным табл. П.5.6, П.5.7, П.5.8 построим точечную диаграмму с использованием средств Microsoft Excel (рис. 4.4). На рис. 4.4 данные, полученные при моделировании ситуации стопроцентного возникновения ошибок по последнему модулю (КТОрп, ОНСрп), показаны в сопоставлении с результатами, полученными ранее при равномерном распределении ошибок по разрядам системы и использовании программ КТ02 и ОПС1 (приложения 3, 4).
