автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Теоретические основы вычислений в полиномиальной системе классов вычетов, ориентированных на построение отказоустойчивых систем

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

Калмыков Игорь Анатольевич

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ВЫЧИСЛЕНИЙ В ПОЛИНОМИАЛЬНОЙ СИСТЕМЕ КЛАССОВ ВЫЧЕТОВ, ОРИЕНТИРОВАННЫХ НА ПОСТРОЕНИЕ ОТКАЗОУСТОЙЧИВЫХ СИСТЕМ

Специальность 05.13.17 - Теоретические основы информатики Специальность 05.13.15 — Вычислительные машины и системы

АВТОРЕФЕРАТ

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

Ставрополь 2006

Работа выполнена в Ставропольском военном институте связи Ракетных войск на кафедре «Информатики и информационных технологий в системах управления»

Научный доктор технических наук, профессор

консультант: Червяков Николай Иванович

Официальные доктор технических наук, профессор Амербаев Вильжан оппоненты: Мавлютинович

(Государственное унитарное предприятие НПЦ «СПУРТ» г. Зеленоград)

доктор технических наук, профессор Коханенко Игорь Константинович

(Ростовский военный институт Ракетных войск, г. Ростов-на-Дону)

доктор технических наук, профессор Макаревич Олег Борисович

(Таганрогский государственный радиотехнический университет, г. Таганрог) Ведущая Научно-производственное объединение «Импульс»,

организация: ФГУП (г. Санкт-Петербург)

Защита состоится 31 августа 2006 года в 14.20 на заседании диссертационного совета Д 212.259.02 в Таганрогском государственном радиотехническом университете по адресу:

347928, г. Таганрог, ГСП-17А, пер. Некрасовский, 44, ауд. Д-406.

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

дарственного радиотехнического университета.

,—-г- ^....

Автореферат ]

адЭслац?V ¿V июня. ЗООб^ч

........ч

Ученый секштайк дйс^т^иоНадгосао^1: доктор "пя

5абенко Л.К.

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

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

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

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

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

Наиболее перспективным путем разрешения данной проблемы является придание процессорам свойства устойчивости к отказам в процессе функционирования. Вычислительная система является отказоустойчивой (Fault-tolerant system), если при возникновении отказа сохраняет свои функциональные возможности в полном (fail-safe) или уменьшенном (faii-soft) объеме. При этом fail-safe устойчивость к отказам (с амортизацией отказов) характеризует способность ПС обеспечивать обслуживание, несмотря на возникновение отказа, хотя и с понижением качества, то сеть, находясь в состоянии постепенного снижения эффективности. Именно в таком контексте рассматривается понятие отказоустойчивость и устойчивость к отказам вычислительных устройств.

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

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

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

Предметы исследования:

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

4

2. Корректирующие коды полиномиальной системы классов вычетов.

3. Методы и алгоритмы поиска и локализации ошибки в кодах Г1СКВ и их схемная реализация.

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

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

В интересах решения научная проблема разбита на пять частных проблем:

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

2. Разработка концепции построения корректирующих кодов ПСЖВ для реализации отказоустойчивых непозиционных процессоров.

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

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

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

Научную новизну работы составляют:

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

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

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

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

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

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

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

Методы исследования базируются на использовании математического аппарата теории кодирования, теории полей Галуа, теории чисел, теории вероятности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация результатов работы.

1. Основные результаты диссертационной работы использованы в Управлении начальника войск связи и военно-научным комитетом РВСН, в научно-производственном объединении «Импульс», ФГУП (г. Санкт-Петербург) при выполнении научно-исследовательских работ, при разработке ЛРМ «Оператор» в ООО «Моби», что подтверждается актами реализации.

2. Основные результаты диссертационной работы использованы в учебном процессе:

- на кафедре «Информатики и информационных технологий в системах управления» Ставропольского военного института связи РВ, что подтверждается актом реализации

- на кафедре «Защиты информации» Северо-Кавказского государственного технического университета, что подтверждается актом реализации.

Апробация работы:

Результаты работы обсуждались на конференциях: Международная конференция «Нейрокомпьютеры и их применение - 2002», Москва 2002; V Международная научно-практическая конференция, Таганрог, 2003; II Международная научно-техническая конференция «Физика и технические приложения волновых процессов», Самара, 2003; III Санкт-Петербургская межрегиональная конференция «Информационная безопасность регионов России», Санкт-Петербург, 2003; II Международный Форум по проблемам науки, техники и образования, Москва, 2003; VI Международная научно-практическая конференция, Таганрог, 2004; III Международный Форум по проблемам науки, техники и образования, Москва, 2004; I Международная научно-практическая конференция Ставрополь, 2004; IV Международная научно-техническая конфе-

ренция «Проблемы информатики и моделирования», Харьков, 2004; VII Международная научно-практическая конференция «Информационная безопасность», Таганрог, 2005; Международная конференция Российской академии естествознания «Новые информационные технологии и системы», Москва, 2005.

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

Структура и объем диссертации. Диссертационная работа изложена на 346 страницах машинописного текста, иллюстрируется 36 рисунками и 31 таблицей и состоит из введения, 6 разделов, списка используемых источников из 212 наименований.

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

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

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

SJA, W,G,p',(z),p'(z),F,0)^max

t* <T О О d*™ > V <У ' ^

ikm ' \iùon ' min mm ' ПСКЯ HCC

где ô\ - коэффициент запаса работоспособности процессора ПСКВ; А, б {А} -алгоритм выполнения задания; е {И'} - пространственно-временное распределение процесса; (7у е{(7}- форма представления входных данных; F(l е {/•'} -алгоритм обнаружения и локализации ошибки; Оу е {о} методов реконфигурации структуры процессора; и Тд0„ - время выполнения задания и предельно допустимое значение; Q^ и Q,io„ - точность выполнения задания и предельно допустимое значение; d^ и d'^ - минимальное кодовое расстояние кода дегра-дирусмого процессора и предельно допустимое; У иски и Уцсс - схемные затраты необходимые на реализацию отказоустойчивого непозиционного процессора и позиционного процессора, использующего метод «2 из 3».

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

Вторая глава посвящена математическим основам построения полиномиальной системы классов вычетов. В данной главе рассмотрены методы и алгоритмы выполнения модульных операций в ПСКВ. Если в качестве оснований алгебраической системы выбрать минимальные многочлены p,(z) поля GF(р"), то любой полином A(z), удовлетворяющий условию A(z)e где

- [ [p,(z), можно представить в виде А(z) = {al(z),a1(z),...,ajz)), где

a,(z) = rest{A(z)jpt(z)\ i = 1,2.....п.

Так как сравнения по одному и тому же модулю можно почленно складывать, то для суммы двух полиномов A(z) и B(z), имеющих соответственно коды (al(z).aj(:),...,ajz)) и (pi(z),p,(z),...,pjzj) справедливы соотношения:

ArMU,.....

( v Р)

где ф - операция суммирования по модулюр; a,(z)- +.... + X,z' + Л0 и

Pt(z)- x'.,rlz~"' +... + y\z' + y0 - полиномиальное представление операндов.

Аналогично получаем для операции вычитания в ПСКВ

\А(*>-=(кг*; - .....- =,)=

С V (3)

=(4 •г.'.егд;,-, .....Е^-.-уил-"]

где о - операция вычитания (обратная операции суммирования) по модулю р.

В силу дистрибутивности операции умножения операндов над кольцом на элементы этого кольца относительно операции сложения имеем

■ в<*х«„=\а><*>- ас .....км •

л,.-> (4)

где я',- линейная свертка; з = 0,...,2т1 - 2;/= 0,...,л.

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

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

а,( 2)-

ЪМгЧпЫрХг)

(5)

где а\ = а, тос{р/г), /'= 1,2,3,..,п,

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

Наряду с прямым преобразованием из позиционного кода в модулярный существует и обратный перевод, позволяющий по величине л-мерного вектора A(z ) = (a,(z),...,am(z)) получить двоичное представление полинома. В настоящее время известны два основных способа перевода:

- на основе китайской теоремы об остатках (КТО);

- на основе перевода в обобщенную полиадическую систему (ОПС). Задача перевода л-мерного представления полинома A(z) е GF(p") к

позиционному виду на основе КТО представляется следующим образом:

М*) = ~ta,(z)B,(^)-K(z)P(z) = ±ai(z)B/z)modP(z), (6)

i-i ¡.I

где Вf(2) - ортогональные базисы системы; Р( z )~Y\ Р,( 2 ) ~ полный диапазон

i-i

ПСКВ; K(z) - ранг полинома.'

В ходе выполнения диссертационной работы была разработана схемная реализация преобразователя ПСКВ-ПСС. Учет отсутствия межразрядных связей при выполнении преобразования позволил свести выражение (6) к виду

A(z)-

¿1

(7)

где у - разряд / -го остатка а ¡(г) по модулю р,(г).

При этом устройство преобразования из кода ПСКВ в ПСС, характеризуется отсутствием выходного сумматора по модулю Р(г) = \[р1(г) = г" ' + /, а, сле-

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

Промежуточная система ОПС составляет основу второго способа перевода из ПСКВ в ПСС, при этом число А изображается в виде

где ак - цифры в ОПС; д1[ = - вес цифры в ОПС.

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

А=(а,(г). а,(г)..... а.(г)) = [а,(г). а,(г), .... а.(г)1. (9)

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

А=а,(2)\г'1(2),г'1(2).....+ О..........(10)

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

X «/г)г'(г)

,1 = 1,2.....п. (И)

I

Схемная реализация данного устройства представлена в работе.

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

Ы! Ну—С"

)тос12, (12)

рш('>

где / = оте? р,( г)', а',(г) - у- ый разряд ¿- го остатка; л' - количества оснований

ПСКВ; Р(г^ = П Р,(2) - полный диапазон ПСКВ;

г=/

Проведенные исследования показали, что схемная реализация алгоритма, определяемого (12) характеризуется меньшими аппаратурными и временными затратами по сравнению с ранее известными алгоритмами.

Особое место среди немодульных операций занимает расширение системы оснований. Задача расширения оснований заключается в нахождении остатка а^/г) по модулю р1л,(2) числа Л = {а,(г), аг(г), .... аг^гД представленного в системе оснований р,(2).р2(г),..., р1(г). При этом

а1„1(г)&Л(г)тос1 рк„(2). (13)

В диссертационной работе был разработан алгоритм определения остатка akll(z) по заданному вектору A = (at(z),a2(z ),...,at(z)), обладающий параллельной организацией вычисления. Для расширенной системы оснований p,(z),p,(z),...,pt„(z) справедливо

A(z) = Y.al(z)B^(z)-Kt"(z)P(Z)PkJz), (14)

i-I

где B¡"'(z), K*''(z) - ортогональный базис и ранг полинома в расширенной

*

системе оснований ПСКВ; P(z) = Y\p,(z) " полный диапазон ПСКВ.

í-i

Если положить условие, что A(z)sP(z), то есть \A(z)¡ P(z)\~0

где Rl(z)^\B4-(z)lP(z)\ K(z)Á±al(z)B¡(z)¡P(z)

L f

; B/z)з B}"(z)modP(z)

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

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

г-/

Многочлен А (г) с коэффициентами из поля р) будет считаться разрешенным в том и только том случае, если он является элементом нулевого интервала полного диапазона Рмт(а), то есть А(г)е Р/К1б(г). Второе подмножество

СР(р''), определяемое произведением г = п-к контрольных оснований

задаст совокупность запрещенных комбинаций. Если А(.:) является элементом второго подмножества, то считается, что данная комбинация содержит ошибку. Таким образом, местоположение Л (г) относительно двух данных подмножеств позволяет однозначно определить, является ли кодовая комбинация А(г) = (а1(г),а1(2),...,аклг(2)) разрешенной, или она содержит ошибки.

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

Теорема 1. Если в упорядоченной системе оснований р/(г), ПСКВ с одним контрольным основанием поля Галуа полином С'(г) й/^„(г), то модулярный код данного полинома содержит как минимум одну ошибку.

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

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

о,<1ркл1(2)> огс1 (рк(-)рк. ,(•)). (18)

Теорема 3. Если в упорядоченной избыточной ПСКВ расширенного поля Галуа С Р(р'), для которой справедливо оп/ Р1(:)< огс! р2(?)<... < о г с! Рк(х), для двух контрольных основанийи Рт(г) имеет место соотношение

огс!Рк^(2)+ оп!рк,г(г)>оп!рк(2) I оп!рк.,(г), (19)

то они позволяют определить место и величину ошибки по любому основанию.

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

Теорема 4. Пусть в системе ПСКВ с основаниями р1(2).р2(2),...,рк^1(2), существует / оснований, таких, что

0п1(\\р/2))<0гс1рк11(г)+0п1р11,!(2), (20)

У-'

то любой полином А (г), в котором ошибочны значения разрядов по данным основаниям или по части из них, то такой полином является неправильным.

Доказана возможность применения кодов ПСКВ для реализации процедур обнаружения и коррекции ошибок на основе проекции.

Теорема 5. Для того чтобы в избыточной ПСКВ с двумя контрольными основаниями исправить полином А (2)^(01(2), .... а ,(2), ак>2(2)), со-

держащий ошибку по ¿-му модулю, необходимым условием является правильность его проекции А'(г) по основанию р,(2).

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

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

(0,а',(г).а',(г)....,а^1(г).....а'^/г)), затем - (0.0,а/(г).....а1,(г).....а1„(г)), и

так далее. Продолжая данный процесс в течение к итераций, получается (0,0,...,у^1(г),...,ук„(г)). Если в результате нулсвизации получаются нулевые значения, уки(г)-0,...,у^г(г) = 0, то код ПСКВ не содержит ошибки. На основе доказанной теоремы был разработан метод параллельной нулевизации. Применение псевдоортогональных полиномов, у которых ортогональность нарушена по контрольным основаниям, позволило реализовать данный метод параллельно, согласно

= y'ti,( z))mod pk1,(z )

rt„(z) = (akJz)-Yl Y'kJz))modptir(z)

при меньших временных и схемных затратах.

Особое место среди позиционных характеристик кода ПСКВ занимает интервальный номер полинома l„,„(z), значение которого определяется

!m(z) = [A(z)/RrJz)\. (22)

Если lm„(z) = 0, то полином A(z) не содержит ошибки, в противном случае — A(z) запрещенный полином. В работе разработан алгоритм вычисления интервального номера. Используя КТО и сравнимость ортогональных базисов избыточной и безизбычной систем B/zJ = В' mod P^/z), получаем

Za/z)R,(z) + K*(zJ

где Rl(z) = [Bl(z)/Plim,(z)\\ K'(z) =

(23)

.....<-)=- \\p,(z)

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

lk"(z) =

шии \ s

Y.(ccl(z)B'(z)) mod Plk,/z)+ £a,(z)R,(z)

J^(aj(z)B](z)) mod P^z) + ^a,(z)R,(z)

(24)

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

Теорема 6. Если в ПСКВ, содержащей £ информационных и / избыточных оснований, в результате нулсвизации А(г) получен нормированный след (0,0,0,...,0,у1<1(г),у1<1(г),...,уклг(г)),то номер интервала, в который попадет

ошибочный полином A'(z), определяется lum(z) =

^R/zfrJz)

(25)

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

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

Л(г) = а1(г) + ... + а^г)Р^(2) + ... + а,(г)Р^(г)р^г)...р^1(2). (26) Таким образом, если полином А(г) е Р^ (г), то старшие коэффициенты ОПС

акц(:)..........соответствующие контрольным основаниям ркц(?),..., Рк+,(г),

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

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

•: (27)

где а{2) = /(а/2).....ал(~)); / ~ к + !,..., к + г; f— алгоритм вычисления остатков по рабочим основаниям; сс1<1(г),ам(г),...,аклг(г) - исходные значения.

Теорема 7. В упорядоченной ПСКВ с рабочими р^г), р2(г),..., рк(г) и контрольными /н,1(2).....ри,(2) основаниями, полином А(2) = (а1(г),...,акл,(г)) не

содержит ошибок, если выполняется условие

\а/2)-а](г1(!)=0, (28)

гд са\(г) =

С/2) +

р,<=)

К „(г) - ранг полинома А (г) в безубыточной ПСКВ. В работе разработан алгоритм, согласно которому (27) принимает вид

сЧ/2) = |а/2) -(Х[а,(2) + 1\а,(2) +... + (29>

гдеЯ^- константы системы ПСКВ;у'=£+/,...,к+г.

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

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

Теорема 8. Если полином' А(г) = (а1(г), а/г), ...,ак,г(г)) принадлежит нулевому подмножеству полного диапазона расширенного ноля Галуа С/'У р"), то корни конгрольных оснований рк1,(х), у = 1,2,...,г., определяемые над данным полем СР(р"являются корнями интервального полинома.

Если осуществить над интервальным полиномом (г) преобразование аналогичное ДПФ, то последний из временной области переносится в частотную - Л ('/.). Прн этом задание корней многочлена в одной области эквивалентно выбору нулевыми соответствующих компонентов в другой области.

Теорема 9. Полином Л(г) = (а1(г),а1(-),.является элсмсн-

*

том рабочего диапазона' Ргац(г)=\\р,(г) поля Галуа СР(ру) сели у'-й спек-

1-1

тральный элемент интервального полинома равен нулю, то есть Ь)(Х) = 0, где _/- показатель степени корня контрольного основания рк^(г),..., рк<г(г).

Появление ошибки в «-мерной комбинации полинома Л(2) приводит к смещению последнего во временной области вдоль оси па величину Аа1(2)В1(г)тос1(2' '' + 1), где Ла^х)- глубина ошибки по /'-му основанию. Данное смещение приводит к изменению спектральных составляющих кода.

Следствие 1. Величина смещения в частотной области спектра полинома А(г), представленного в ПСКВ, при возникновении ошибки по /-му модулю:

а) рабочее основание: Щр) = ""¿((Асс!(г)();(г))тос1 рк„(г)/3'), (30) где б/г/= Я/г; + [Аа,(г)В;(х

б) контрольное основание: и,(р)~ 2_,((йа!( 2)^(2)) той ¡\,,(-)/!')■ (31)

Для проведения процедур поиска и исправления ошибок в кодовых комбинациях ПСКВ была разработана схемная реализация, а также осуществлены расчеты аппаратурных и временных затрат.

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

где Кор - схемные затраты; I/ — алгоритм обнаружения и коррекции ошибок в ПСКВ; £> — пространственно-временное распределение алгоритма; N - набор модулей ПСКВ; К" и А",™ - количество и минимально допустимое количество исправленных ошибок; Т°'" - временные затраты на процедуру поиска и коррекции ошибки; Т„с^„с,- — временные затраты на преобразование ПСКВ-ПСС.

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

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

Теорема 10. В избы точной ПСКВ с попарно простыми основаниями р/г), 1=1, 2, ..., к+г при возникновении ошибки поу'-ому рабочему основанию значение интервального номера ошибочного полинома определяется из условия

К'" (V ,1),М )> К2„Г"' (и )<Г,

нскв-тх;

(32)

¡и=) = р]'(г)(Аа)(2)1\р1(2)-'^р/г)

Iш1

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

Значения ортогональных базисов Bf(z), i-I,...,k+r определяются

B/z) = mXz)PMJz)lPl(z) = X\m,(z)pt(z), (34)

i-i

' ы

где m,(z)~ p-,'(z)mod p((z) - вес 1-го основания ПСКВ.

Следовательно, для пересчета значений ортогональных базисов необходимо знать значения работоспособных оснований p/(z) и их веса т,(г). В работе представлена схемная реализация данного метода, а так же произведен расчет схемных затрат, необходимых для пересчета ортогональных базисов ПСКВ.

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

О, если j < i

i-r

a'j(z) = \Y\m'j(z)modpl(z), если j = i. (35)

<Tf44(z) + a1,,, )m'; '(+ ... + <, )m';'(z))mod Pj (z) если j > i

Анализ выражения (35) показывает, что данная процедура описывается формулой Горнера и может быть успешна реализована на основе применения параллельно-конвейерной организации вычислений. Следовательно, данный метод может быть положен в основу работы устройства поиска и коррекции ошибок процессоров ПСКВ с деградируемой структурой.

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

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

= ч>;.....и'£}3е= ->Р(ц>,)<-> Р(Б)]. (36)

2 этап. Осуществляется выбор оптимального состава информационных основании Г1СКВ. В результате решения задачи

где У„ск„ - схемные затраты необходимые на реализацию СП ПСКВ; 0,„ск, и О.аоп - точность обработки данных в ПСКВ и предельно допустимая точность; становится известен ансамбль рабочих оснований {рк,(г)\ ПСКВ. Затем выбираются контрольные основания. В результате решения задачи

¡КжЦр'Ыр'М})-*»»» [К„сЛр1 !>'(=)})*

где /V,™ и ,ЧЬ„ - количество отказов, парируемых при обрабатываемых данных

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

становится известен набор избыточных оснований \р'(г)} кода ПСКВ.

3 этап. На данном этапе осуществляется выбор алгоритма перевода из позиционного кода в ПСКВ. В результате решения задачи

ПСС-ШкН ({я

• ИСКИ

({р*

где л-. <= .У ~ [л,, л,,..., -у'-ый алгоритм преобразования ПСС-ПСКВ из множества 5; Т„«.„„„~ временные затраты на реализацию перевода ПСС-ПСКВ; становится известен алгоритм немодульной операции преобразования двоичного кода в остатки и его схемная реализация.

4 этап. На данном этапе осуществляется выбор реализации немодульной операции - обратного перевода из ПСКВ в ПСС. В результате решения задачи

где и, еУ = , и2,..., ¡^] - 1-ый алгоритм обратного преобразования ПСКВ-ПСС; Т„сы-,„<■ - временные затраты немодульной операции ПСКВ-ПСС,

становится известен алгоритм выполнения процедуры перевода модулярного кода в позиционный код и его схемная реализация

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

где Vt = У1КП.1КХ + У^ - суммарные схемные затраты на выполнение операции поиска и коррекции ошибки и преобразования из ПСКВ-ПСС; Л/j,,,, - предельно допустимое количество отказов; NIICKIIi^pk(z),pr(z)\.nl,J\l) - количество парируемых отказов с использованием алгоритма fd ; /, е F = \ffM J - совокупность алгоритмов поиска и коррекции ошибок;

становится известен алгоритм поиска и коррекции ошибки в модулярном коде и его схемная реализация.

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

S.{{pk(z)-p'(",ах

■Tjb'fzJ.p'wU.o.UT^ , (42)

Q,„, ({/>* (z), p' (2)}, u,jd.0i)>

r«e Trr^pi(z),p,(z)\u,,o„\ Q,„№(z).P'(z)\»,.f*.o.) ' время, и точность выполнения задания процессором ПСКВ при реализации выбранного оа -го алгоритма реконфигурации; о„ еО = [о1,ог,...,он ] - совокупность возможных методов реконфигурации;

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

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

23

дискретизации - 50 кГц; разрядность входного вектора - 31 бит; формат представления операндов — с фиксированной точкой; минимально допустимая разрядность входного слова - 11 бит. На основании исходных данных и для обеспечения требуемого уровня спектрального разрешения при реализации ортогонального преобразования речевого сигнала выбрано поле Галуа вГ(Г) с использованием функции «окна» с длиной N-31 отсчет. В ходе реализации методики была разработана структура процессора ГГСКВ, используемого для ЦОС. Для оценивания пригодности разработанной методики проведен сравнительный анализ синтезированного вычислительного устройства (1) с процессором, функционирующий в поле Галуа СР(25) с 3 контрольными основаниями (2), а так же нспозиционный процессор ПСКВ, обрабатывающий 11-разрядные данные и использующий метод маскирования отказов «2 из 3» (3). На рисунке 1 приведены в графическом виде обобщенные результаты сравнительного анализа отказоустойчивости этих процессоров.

«5«

Рисунок 1 - Изменение коэффициента запаса работоспособности процессора при накоплении отказов а = 1, 2,...

Анализ результатов показывает, что применение методики позволяет разработанному процессору ПСКВ, реализующему ЦОС в поле Галуа СР'(2!), сохранять коэффициент запаса работоспособности равный единице при возникновении 3 отказов. Таким образом, процессор способен функционировать даже при последовательном возникновении 3 отказов за счет снижения в допустимых пределах такого показателя качества как точность вычислений. При этом реализация непозиционного процессора, использующего корректирующие коды ПСКВ, обеспечивает сохранение работоспособного состояния при двух отказах, а применение метода «2 из 3» позволяет парировать только один отказ.

На основе разработанного процессора IICKH была реализована мультипроцессорная система для осуществления ЦОС. Для оценивания эффективности данной многопроцессорной системы проведен сравнительный анализ с позиционной вычислительной системой ЦОС, выполняющей ортогональные преобразования сигналов в поле комплексных чисел на основе БПФ.

Проведенные исследования показали, что схемные затраты необходимые на реализацию вычислительной системы ЦОС, построенной на основе отказоустойчивого непозиционного процессора ИСКИ, составляют 79 процентов от аппаратурных затрат позиционной процессорной системы БПФ, реализующей метод маскирования отказов «2 из 3». Применение полиномиальной системы классов вычетов позволяет повысить скорость обработки данных более чем в 1,74 раза даже по сравнению с быстрыми алгоритмами обработки сигналов в позиционной системе счисления.

Основные выводы и результаты

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

2. Независимость и параллельность обработки данных в вычислительных трактах ПСК13 служат идеальной основой для построения корректирующих модулярных кодов. Разработана концепция построения корректирующих кодов полиномиальной системы классов вычетов. Проведены исследования корректирующих способностей модулярных кодов Г1СКВ. Доказанные теоремы и следствия позволяют использовать коды ПСКВ для процедур поиска и коррекции ошибок в процессе функционирования вычислительных устройств.

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

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

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

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

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

данный метод может быть положен в основу процедур выявления ошибок при работе устройства обнаружения и коррекции ошибок в кодах ПСКВ.

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

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

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

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

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

12. Разработанная методика построения устойчивых к отказам непозиционных процессоров, функционирующих в ПСКВ позволяет синтезировать более надежные вычислительные устройства по сравнению с ранее с известными вычислительными системами, реализующими метод маскирования отказов «2 из 3». Для оценки пригодности данной методики был проведена разработка структуры отказоустойчивого процессора цифровой обработки сигналов, функционирующего в полиномиальной системе классов вычетов.

13. Применение методики позволяет процессору ПСКВ, реализующему ЦОС в расширенном ноле Галуа ОГ(25), сохранять коэффициент запаса работоспособности равный единице при возникновении 3 отказов. Таким образом, процессор обеспечивает функционирование даже при последовательном возникновении 3 отказов за счет снижения в допустимых пределах такого показателя качества как точность вычислений. При этом реализация непозициоиного процессора, использующего корректирующие коды ПСКВ, обеспечивает сохранение работоспособного состояния при двух отказах, а применение метода «2 из 3» позволяет парировать только один отказ.

14. Проведенные исследования показали, что схемные затраты необходимые на реализацию вычислительной системы ЦОС, построенной на основе отказоустойчивого непозиционного процессора ПСКВ, составляют 79 процентов от аппаратурных затрат позиционной процессорной системы БПФ, реализующей метод маскирования отказов «2 из 3». Применение полиномиальной сис-

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

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

Публикации но теме диссертации

1. 1 Калмыков И.Л. Математические модели нсйросстсвых отказоустойчивых вычислительных средств, функционирующих в полиномиальной системе классов вычетов/Под ред. Н.И. Червякова- М: Физматлит, 2005.-276 с

- 2. Элементы компьютерной математики и нейронопнфроматнки /Червяков Н.И., Калмыков И.Л., Галкина В.Л., Щелкунова Ю.О., Шилов Л.Л.; Под ред. Н.И. Червякова. - М.: Физматлит, 2003. - 216 с.

3. Калмыков И. Л. Метод пересчета коэффициентов обобщенной полиадической системы для спецпроцессоров с деградируемой структурой/Известия ТРТУ. Таганрог: Изд-во ТРТУ, 2005. №4, С. 35-42.

4. Калмыков И.Л. Математическая модель нейронной сети для исправления ошибок непозиционного кода поля Галуа в частотной области/ Нейрокомпьютеры: разработка и применение. №5-6, 2004, с.71-78;

5. Калмыков И.А. Метод пересчета ортогональных базисов для модулярного спецпроцессора с деградируемой структурой/Зб!рник наукових прац. Выпуск 5 (45). «Системи обработки шформацп», 2005, С. 18-27.

6. Калмыков И.Л. Коррекция ошибок на основе нсйросстсвых алгоритмов вычисления номера интервала/3б1рник паукових прац. Харк^вського ушвсрситету Повпряних Сил. Выпуск 5 (6), 2005, С.65-68.

7. Калмыков И.А. Многоступенчатая полиномиальная система классов вычетов и ее нейросетевая рсализация/Збфник наукових прац. 2005 - Кшв, Нацюнальна Академ!я Наук Укрши, Выпуск № 33, с. 53-62.

8. Калмыков И.А. Обнаружение и коррекция ошибок в полиномиальной системе классов вычетов на основе проекций/ Материалы I Международной научно-технической конференции «Инфотелскоммуникационные технологии в науке, производстве и образовании». - Ставрополь, 2004. - С.270-275.

9. Калмыков И.А. Разработка метода контроля и коррекции ошибок для непозиционного спецпроцессора с деградируемой структурой/Збфник нау-

кових праць 2004 - Knie, Нацюнальна Академ1я Наук Укрши, Вып№ 25,с. 65-78.

10. Калмыков И.Л. Методика разработки математической модели и структуры нейросетевого устойчивого к отказам спецпроцессора ЦОС, функционирующего в ПСКВ и способного сохранять работоспособное состояние на основе реконфигурации структуры. — М: НС РВСН, 2004. — 54 с.

11. Калмыков И.А. Устройство для вычисления сумм парных произведений/ Патент № 2012041. - 1994. Бюл. № 8.

12. Калмыков И.А., Бережной В.В., Оленев A.A. Систолический процессор Д11Ф с коррекцией ошибки/ Патент № 2018950. - 1994. - Бюл. № 16.

13. Калмыков И.А., Оленев A.A. Систолический отказоустойчивый процессор ДПФ/ Патент № 2029437. - 1994. Бюл. № 16.

14. Калмыков И.А., Лободин М.В., Алексишин Е.В., Щелкунова IO.O. Нейронная сеть для вычисления коэффициентов ОПС, представленных в расширенных полях Галуа GF(2V)./Патент № 2258956. Бюл. №23 от 20.08.2005.

15. Калмыков И.А., Емельяненко C.B., Лисицын A.B. Устройство для обнаружения и исправления ошибок в полиномиальной системе класса выче-тов./Патент № 2267808. Бюл. № 01 от 10.01.2006.

16. Калмыков И.А., Емельяненко C.B., Лободин A.B. Устройство для вычисления сумм парных произведений в полиномиальной системе классов вычетов. Решение о выдаче патента (№2004101990/09) от 22.01.2004.

17. Калмыков И.А., Лисицын A.B., Лободин A.B., Гахов В.Р. Нейронная сеть для преобразования из позиционной системы счисления в код полиномиальной системе классов вычетов. Решение о выдаче патента (№2004113904/09). Приоритет от 05.05.2004. Бюл. №30 (II). с.491.

18. Калмыков И.А., Червяков Н.И., Щелкунова Ю.О., Бережной В.В. Математическая модель нейронных сетей для исследования ортогональных преобразований в расширенных полях Галуа/Нейрокомпьютеры: разработка, применение. №6, 2003. с.61-68.

19. Калмыков И.А., Червяков Н.И., Щелкунова Ю.О., Бережной В.В. Архитектура отказоустойчивой нейронной сети для цифровой обработки сигналов/Нейрокомпьютеры: разработка, применение. №12, 2004. с.51-60.

20. Калмыков И.А., Щелкунова Ю.О. Математическая модель спектрального анализа ошибок в отказоустойчивых системах цифровой обработки

информации, функционирующих в полях Галуа 6>7/У)/Матсрнали II Между-' народной научно-технической конференции «Физика и технические приложения волновых процессов», г.Самара, 2003, С. 127-132.

21. Калмыков И.А., Червяков Н.И., Щелкунова Ю.О., Бережной В.В., Шилов A.A. Нсйросетсвая реализация в полиномиальной системе классов вычетов операций ЦОС повышенной разрядности/ Нейрокомпьютеры: разработка и применение, 2004, №5-6, с.94-101.

22. Калмыков H.A., Червяков Н.И., Щелкунова Ю.О., Бережной В.В. Математическая модель нейронной сети для коррекции ошибок в пепознцнон-ном коде расширенного поля Галуа/ Нейрокомпьютеры: разработка, применение. №8-9, 2003. С. 10-16.

23. Калмыков И.А., Щелкунова Ю.О., Гахов В.Р., Шилов A.A. Математическая модель коррекции ошибок в ПСКВ на основе определения корней интервального полинома/Волновые процессы. №5, т.6, Самара, 2003 - С.30-34.

24. Калмыков H.A., Щелкунова Ю.О., Гахов В.Р., Гордснко Д.В., Новиков В.И. Модель и структура нейронной сети для реализации ЦОС в расширенных полях Галуа/Збфник наукових прац. Выпуск 1. «Систсмп обработки ¡нфор-мацп», 2003, С.29-41.

25. Калмыков H.A., Щелкунова Ю.О., Малофсй А.О., Рыбальчснко М.С. Спектральное обнаружение и локализация ошибок в полиномиальной системе классов вычетов/Математическое моделирование М 2005.Т. 17, №3,С.67-74

26. Калмыков И.А., Гахов Р.П. Математическая модель пересчета коэффициентов обобщенной полиадической системы для спецпроцессора с дегра-дирусмой структурой/ Материалы IV Международная научно-техническая конференция «Проблемы информатики и моделирования», Харьков, 2004, С 68.

27. Калмыков И.А., Чипига A.A., Лисицын A.B. Разработка нейронного преобразователя из позиционного кода в ПСКВ/ Труды Международного Форума по проблемам науки, техники и образования - М.: Академия паук, 2004. -С.135-136.

28. Калмыков И.А., Хайватов А.Б.. Устройство для обнаружения и исправления ошибок в ПСКВ/Материалы I Международной научно-технической конференции «Инфотелекоммуникационные технологии в науке, производстве и образовании». - Ставрополь, 2004. - С. 152-155.

29. Калмыков И.Л., Велигоша A.B. Повышение отказоустойчивости процессоров ЦОС путем реконфигурации структуры/ Деп. в/ч 11520, Сб. рефератов депонированных рукописей. Вып. 25, Сер. Б, инк.№ 2318, 1993.

30. Калмыков И.А., Чипига А.Ф. Структура нейронной сети для реализации цифровой обработки сигналов повышенной разрядности/Вестник Ставропольского Государственного Университета, 2004, № 38 с. 46-50

31. Калмыков И.Д., Шилов A.A., Чипига A.A. Разработка метода пересчета ортогональных базисов в ПСКВ и его нейросетсвая реализация/Материалы VI Международной научно-практической конференции «Информационная безопасность». - Таганрог, 2004. - с.152-154.

32. Калмыков H.A., и др. Применение корректирующих кодов полиномиальной системы классов вычетов для построения спецпроцессоров цифровой обработки сигналов/ Труды Международного Форума по проблемам науки, техники и образования. Том1./ Под ред.: В.Г1. Савиных, В.В.Вишневского. - М.: Академия наук, 2004. - С.133-135.

33. Калмыков И.Л., Гахов В.Р., Владимиров A.A. Перевод из одной системы оснований полиномиальной системы классов вычетов в другую/ Материалы 1 Международной научно-технической конференции «Инфотелекомму-никационные технологии в науке, производстве и образовании». - Ставрополь, 2004. - С. 143-147.

34. Калмыков H.A., Хайватов А.Б.. Устройство для обнаружения и исправления ошибок в ПСКВ/Материалы I Международной научно-технической конференции «Инфотелекоммуникационные технологии в науке, производстве и образовании». - Ставрополь, 2004. — С. 152-155.

35. Калмыков И.А., Шилов A.A., Гахов В.Р., Щелкунова Ю.О. Применение полиномиальной системы классов вычетов для ортогональных преобразований сигналов в расширенных полях Галуа Труды Международного Форума по проблемам пауки, техники и образования. Том 1./Под ред.: В.П. Савиных, В.В.Вишнсвского. - М.: Академия наук, 2003. - С.77-78.

36. Червяков Н.И., Бережной В.В., Гончарова E.H., Калмыков H.A. Локализация и исправление арифметических ошибок в модулярных нейрокомпьютерах/Нейрокомпьютеры: разработка, применение. №7, 2003. С. 28-32.

Подписано в печать 31.05.2006 г. Формат 60x84 1/16. Усл. п. л. - 2.0. Уч.-ичд. л. - 1,3. Бумага офсетная. Печать офсетная. Заказ 393 Тираж 100 экз. ГОУВПО «Северо-Канкачскин государственный технический университет» 355029, г. Ставрополь, пр. Кулакова, 2

Издательство Северо-Кавказского государственного технического университета Отпечатано в типографии СевКавГТУ

ВВЕДЕНИЕ

1 АНАЛИТИЧЕСКИЙ ОБЗОР ОБЕСПЕЧЕНИЯ УСТОЙЧИВОСТИ К ОТКАЗАМ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ ОБРАБОТКИ ДАННЫХ.

1.1 Анализ основных тенденций развития и применения вычислительных систем.

1.2 Основные методы обеспечения устойчивости к отказам вычислительных устройств.

1.2.1 Обеспечение отказоустойчивости во время функционирования вычислительных устройств.

1.2.2 Обеспечение устойчивости к отказам на основе применения корректирующих способностей кодов.

1.3 Выбор и обоснование показателей и критериев оценки отказоустойчивости процессоров.

1.4 Постановка проблемы исследований.

Выводы.

2 МАТЕМАТИЧЕСКИЕ ОСНОВЫ ПОЛИНОМИАЛЬНОЙ СИСТЕМЫ КЛАССОВ ВЫЧЕТОВ ПОЛЕЙ ГАЛУА.

2.1 Реализация модульных операций в полиномиальной системе классов вычетов в полях Галуа СР(ру).

2.2 Прямое преобразование из двоичного кода в код полиномиальной системы классов вычетов.

2.3 Перевод из полиномиальной системы классов вычетов поля С/7^") в позиционный код.

2.3.1 Перевод непозиционного кода на основе китайской теоремы об остатках.

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

2.4 Алгоритмы вычисления ранга полинома, представленного в полиномиальной системе классов вычетов.

2.5 Реализация операций по расширению системы оснований в полиномиальной системе классов вычетов.

2.6 Основы построения многоступенчатой полиномиальной системы классов вычетов в расширенных полях Галуа.

Выводы.

3 КОНЦЕПЦИЯ ПОСТРОЕНИЯ КОРРЕКТИРУЮЩИХ МОДУЛЯРНЫХ КОДОВ ПОЛИНОМИАЛЬНОЙ СИСИТЕМЫ КЛАССОВ ВЫЧЕТОВ.

3.1 Связь между ошибками в коде полиномиальной системы классов вычетов и распределением полиномов по диапазону.

3.2 Корректирующие коды полиномиальной системы классов вычетов с одним контрольным основанием.

3.3 Корректирующие модулярные коды с двумя контрольными основаниями.

3.4 Обнаружение и коррекция ошибок на основе реализации процедур проекций.

3.5 Оценка корректирующих способностей кодов полиномиальной системы классов вычетов.

Выводы.

ГЛАВА 4 МЕТОДЫ И АЛГОРИТМЫ КОНТРОЛЯ И КОРРЕКЦИИ ОШИБОК В КОДАХ ПОЛИНОМИАЛЬНОЙ СИСТЕМЫ КЛАССОВ 178 ВЫЧЕТОВ

4.1 Методы и алгоритмы коррекции ошибок на основе вычисление позиционных характеристик во временной области.

4.1.1 Метод параллельной нулевизации полинома, представленного в полиномиальной системе классов вычетов.

4.1.2 Контроль и коррекция ошибки на основе вычисления интервального номера.

4.1.3 Поиск и коррекция ошибок на основе вычисления коэффициентов обобщенной полиадической системы.

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

4.2 Обнаружение и коррекция ошибок в частотной области.

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

4.2.2 Спектральный метод контроля и коррекции ошибок в кодах полиномиальной системы классов вычетов.

4.3 Сравнительная оценка методов контроля и коррекции ошибок в кодах полиномиальной системе классов вычетов.

Выводы.

ГЛАВА 5 РЕКОНФИГУРАЦИЯ СТРУКТУРЫ ПРОЦЕССОРА ПОЛИНОМИАЛЬНОЙ СИСТЕМЫ КЛАССОВ ВЫЧЕТОВ ПРИ ВОЗНИКНОВЕНИИ ОТКАЗОВ.

5.1 Определение местоположения и глубины ошибок при деградации структуры модулярного процессора.

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

5.3 Метод пересчета коэффициентов обобщенной полиадической системы для процессоров с деградируемой структурой.

Выводы.

ГЛАВА 6 МЕТОДОЛОГИЧЕСКИЕ ОСНОВЫ И ПРИНЦИПЫ ПОСТРОЕНИЯ НЕПОЗИЦИОННЫХ ПРОЦЕССОРОВ УСТОЙЧИВЫХ

К ОТКАЗАМ.

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

6.2 Построение отказоустойчивого непозиционного спецпроцессора цифровой обработки сигналов.

6.3 Оценивание пригодности методики в инженерной практике.

Выводы.

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

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

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

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

Все множество вычислительных систем, согласно принятой классификации, можно разбить на четыре основные группы в зависимости от архитектурных решений [14]. Применение 8180-архитектуры (одиночный поток команд и одиночный поток данных) обеспечивает доминирующее положение классической фон-неймановской архитектуры. В таких машинах обработка данных идет последовательно, команды выполняются друг за другом, при этом каждая команда инициирует одну скалярную операцию. Даже введение параллельной работы устройств ввода-вывода, информации и процессора, совмещение операций, выполняемых отдельными блоками арифметико-логического устройства (АЛУ), не позволяют эффективно реализовать параллельные вычислительные системы реального масштаба времени. Следовательно, возможности по быстродействию современных ЭВМ, базирующихся на классической архитектуре последовательного выполнения операторов, практически достигли своего предельного значения.

Вычислительные системы второй группы - М180-архитектуры (множественный поток команд и одиночный поток данных) большой практической реализации не получили. Задачи, в которых несколько процессоров могли бы эффективно обрабатывать один поток данных, в науке и технике пока неизвестны [14].

Основу третьей группы вычислительных систем составляют устройства, разработанные на основе БПУГО-архитектуре (одиночный поток команд и множественный поток данных). Применение 81МО-архитектуры позволяет реализовать высокоскоростные системы реального масштаба времени. С их помощью эффективно решаются задачи матричных исчислений, задачи решения систем алгебраических и дифференциальных управлений, задачи теории поля. Среди множества задач, решаемых вычислительными системами с такой архитектурой, особое место занимают задачи цифровой обработки сигналов (ЦОС), которые являются наиболее оптимальными для 81МГ) - структуры. Данная архитектура вычислительной системы ориентирована на параллельно-конвейерное выполнение наиболее трудоемких вычислительных операций. Обеспечение предельной для данного уровня технологии производительности вычислительной системы возможно только за счет применения нетрадиционной арифметики, в которой процесс распараллеливания осуществляются на уровне арифметических операций [115].

Альтернативным решением проблемы решения задач повышенной вычислительной сложности в реальном масштабе времени является применение

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

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

Важнейшими резервами повышения производительности вычислений являются использования специализированных процессоров (СП), архитектура которых адекватна алгоритму задачи, реализация потока данных вместо потока управляющих команд, применение принципов распараллеливания на всех уровнях [14].

Концепция параллелизма давно привлекала внимание специалистов своими потенциальными возможностями повышения производительности и надежности вычислительных систем. Проводимые теоретические, экспериментальные и промышленные разработки в этом направлении позволили обосновать основные принципы построения параллельных вычислительных систем. Именно с подобными системами связывается в настоящее время перспектива дальнейшего наращивания вычислительной мощности [93].

Основные принципы, положенные в основу построения параллельных вычислительных систем, достаточно полно отражены в работах [14,82,91,92]. Среди них можно выделить следующие:

- модульность построения вычислительной системы;

- способность системы к адаптации, к самонастройке и самоорганизации;

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

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

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

Одним из наиболее перспективных направлений решения данных проблем является переход к вычислениям в нетрадиционной арифметике с нетрадиционным представлением операндов[80,103,105,129] . В настоящее время из множества нетрадиционных арифметик, развитых теоретически, наибольшее применение в вычислительных системах нашли четыре:

- арифметика в знакологарифмической системе счисления;

- модулярная арифметика в системе остаточных классов (СОК);

- модулярная комплексная арифметика Гаусса (в квадратичных остатках);

- арифметика в кольце полиномов.

Анализ методов и математического аппарата нетрадиционных арифметик, а так же их реализаций [81,85,88,95, 145-147,168,169,174,185,195-201], показал, что наибольшее применение нашли вычислительные устройства, использующие непозиционные модулярные коды. Особое место среди последних занимает модулярная полиномиальная система классов вычетов (ПСКВ), определяемая над расширенным полем Галуа а7(2У), где V - положительное целое число [32,34,69,166]. Если в качестве оснований новой алгебраической системы выбрать минимальные многочлены р/г) поля ру), то любой полином А(г) можно представить в виде вектора А(г) = (а1(2),а2(г),.,ап(г)), где а,(г) = геэ((А(2)/р,(г)), / = 7,2,.и.

Так как сравнения по одному и тому же модулю можно почленно складывать, вычитать и умножать [1,2,34,69,166], то операции суммирования, вычитания и умножения сводятся к соответствующим операциям над остатками. При этом выполнение операций над операндами в расширенном поле Галуа С/^ру) производятся независимо по каждому из модулей р/г), что указывает на параллелизм данной алгебраической системы. При этом порядок обрабатываемых операндов уменьшается в несколько раз, что является базовой предпосылкой для построения высокоскоростных вычислительных устройств.

Существующая в последние годы в вычислительной технике тенденция к распараллеливанию вычислений связана с непрерывном ростом требований к производительности вычислительных средств. В то же самое время процессоры, составляющие значительную часть аппаратной реализации вычислительной техники, относятся к числу наименее надежных устройств, доля отказов и сбоев которых составляет более 50 процентов от общего числа отказов и сбоев аппаратуры. При этом среднее время ликвидации последствий последних, как правило, на 6-8 порядков превышает среднюю продолжительность выполнения одной задачи [82,137,146].

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

Наиболее перспективным путем разрешения данного противоречия является придание процессорам свойства устойчивости к отказам в процессе функционирования. Согласно [135] вычислительная система является отказоустойчивой (Fault-tolerant system), если при возникновении отказа сохраняет свои функциональные возможности в полном (fail-safe) или уменьшенном (fail-soft) объеме. При этом отказоустойчивость (ОУ) обеспечивается сочетанием избыточности системы и наличии процедур обнаружения и устранения ошибок. Во втором издании английского толкового словаря по вычислительным системам, выпущенным издательством Oxford University Press, fail-safe устойчивость к отказам (с амортизацией отказов) характеризует способность вычислительной системы обеспечивать обслуживание, несмотря на возникновение отказа, хотя и с понижением качества, то есть находясь в состоянии постепенного снижения эффективности. Именно в таком контексте будет рассматриваться далее понятие отказоустойчивость и устойчивость к отказам.

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

Основным методом, который широко применяется при построении отказоустойчивых вычислительных устройств и систем является резервирование [31,82,100,111,123,136,140]. Существует большое количество различных способов резервирования, но для любого из них характерна очень высокая избыточность. Даже при коррекции одиночных ошибок чаще всего приходится увеличивать объем оборудования как минимум в три раза. Столь высокая избыточность объясняется тем, что при применении резервирования практически полностью игнорируются все специфические свойства вычислительного устройства, защищаемого от ошибок или отказов.

Качественным скачком в направлении обеспечения отказоустойчивости вычислительных устройств является широкое применение кодов, способных обнаруживать и корректировать возникающие ошибки [8,13,82,85,89,90,156,169,196]. Характерной чертой таких кодов является наличие двух взаимозависимых частей: информационной и контрольной.

Проведенный анализ известных помехоустойчивых позиционных кодов показал неравноправность данных частей кода относительно арифметических операций. Неарифметичность алгоритмов получения проверочных разрядов не позволяет контролировать результаты арифметических операций [89,99]. Таким образом, очевидно, что применение позиционных корректирующих кодов в вычислительных системах является нецелесообразным.

Данного недостатка лишены непозиционные модулярные коды. Применение полиномиальной системы классов вычетов позволяет обеспечить отказоустойчивость вычислительных устройств, функционирующих в расширенных полях Галуа СР(2У) [34,41,69,166]. Внутренний параллелизм, присущий арифметике ПСКВ, позволяет широко использовать перспективные принципы организации вычислительного процесса и использовать в разработке параллельных спецпроцессоров. Кроме этого, ПСКВ обладает следующими достоинствами:

- независимость разрядов обуславливает возможность построения автономных вычислительных трактов (каналов) по каждому основанию и позволяет считать последние независимыми элементами;

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

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

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

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

Предметы исследования:

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

2. Корректирующие коды полиномиальной системы классов вычетов.

3. Методы и алгоритмы поиска и локализации ошибки в ПСКВ и их схемная реализация.

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

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

Частные научные проблемы:

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

2. Разработка концепции построения корректирующих кодов ПСКВ для реализации отказоустойчивых непозициоппых процессоров.

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

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

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

Научную новизну работы составляют:

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

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

3. Методы и алгоритмы поиска и коррекции ошибок в непозиционных кодах ПСКВ, реализованные на основе вычисления позиционных характери

15 стик во временной области, которые, в отличие от ранее известных, характеризуются минимальными аппаратными и временными затратами.

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

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

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

Методы исследования базируются на использовании математического аппарата теории чисел, теории кодирования, теории полей Галуа, теории вероятности.

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

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

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

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

Четвертая глава посвящена развитию и разработке методов и алгоритмов коррекции ошибок при обработке данных в непозиционных системах. В данной главе рассмотрены вопросы использования позиционных характеристик для обнаружения и коррекции ошибок. Представлены схемные реализации данных методов и алгоритмов. Доказана возможность реализации процедур поиска и коррекции ошибки в частной области. Разработан метод «спектрального анализа» кодовой комбинации модулярного кода ПСКВ. Представлена схемная реализация данного метода. Решена задача выбора оптимальной структуры устройства обнаружения и коррекции ошибки для модулярного кода ПСКВ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация результатов работы.

1. Основные результаты диссертационной работы использованы в Управлении начальника войск связи и военно-научным комитетом РВСН, научно-производственном объединении «Импульс», ФГУП (г. Санкт-Петербург) при выполнении научно-исследовательских работ, при разработке АРМ «Оператор» в ООО «Моби», что подтверждается актами реализации.

2. Основные результаты диссертационной работы использованы в учебном процессе:

- на кафедре «Информатики и информационных технологий в системах управления» Ставропольского военного института связи РВ, что подтверждается актом реализации

- на кафедре «Защиты информации» Северо-Кавказского государственного технического университета, что подтверждается актом реализации.

Апробация работы.

Результаты работы обсуждались на международных конференциях:

Международная конференция «Нейрокомпьютеры и их применение - 2002», Москва 2002;

V Международная научно-практическая конференция «Информационная безопасность», Таганрог, 2003;

II Международная научно-техническая конференция «Физика и технические приложения волновых процессов», Самара, 2003;

III Санкт-Петербургская межрегиональная конференция «Информационная безопасность регионов России», Санкт-Петербург, 2003;

II Международный Форум по проблемам науки, техники и образования, Москва, 2003;

VI Международная научно-практическая конференция «Информационная безопасность», Таганрог, 2004;

III Международный Форум по проблемам науки, техники и образования, Москва, 2004;

I Международная научно-техническая конференция «Инфотеле-коммуникационные технологии в науке, производстве и образовании», Ставрополь, 2004;

IV Международная научно-техническая конференция «Проблемы информатики и моделирования», Харьков, 2004;

VII Международная научно-практическая конференция «Информационная безопасность», Таганрог, 2005.

Международная конференция Российской академии естествознания «Новые информационные технологии и системы», Москва, 2005.

Публикация.

1. Основные результаты работы представлены в монографии

- Математические модели нейросетевых отказоустойчивых вычислительных средств, функционирующих в полиномиальной системе классов вычетов/ Под ред. Н.И. Червякова. - М.: ФИЗМАТЛИТ, 2004. - 276 с

- Элементы компьютерной математики и нейроноинфроматики /Червяков Н.И., Калмыков И.А., Галкина В.А., Щелкунова Ю.О., Шилов A.A.; Под ред. Н.И. Червякова. - М.: ФИЗМАТЛИТ, 2003. - 216 с.

2. Основное содержание диссертационной работы опубликовано: а) в журналах:

- «Электронное моделирование» 1994, №1, с. 56-60;

- «Радиоэлектроника» 1995, №8, с. 11-20;

- «Нейрокомпьютеры: разработка и применение» 2003, №6, с.61-68.

- «Нейрокомпьютеры: разработка и применение» 2003, №7, с.61-68;

- «Нейрокомпьютеры: разработка и применение» 2003, №8-9, с.23-34;

- «Нейрокомпьютеры: разработка и применение» 2004, №5-6, с.61-68;

- «Нейрокомпьютеры: разработка и применение» 2004, №5-6, с.61-68;

- «Нейрокомпьютеры: разработка и применение» 2004, №12, с.61-68;

- «Нейрокомпьютеры: разработка и применение» 2005, №4, с.37-45;

- «Известия ТРТУ» 2005. Тематический выпуск №4, с. 35-42;

- «Физика волновых процессов и радиотехнические системы» 2003, №5 с.31-34;

- «Математическое моделирование» 2005, Том 17, №3, С.67-74;

- «Вестник Ставропольского государственного университета», 2004, Выпуск №38 с. 16-24.

- «Вестник Ставропольского государственного университета», 2004, Выпуск № 38 с. 46-50. б) в сборниках статей:

- Системы обработки информации. Сборник научных трудов. Выпуск 1. Харьков 2003г. С 29-41;

- Зб1рник наукових праць. Нацюнальна Академ1я Наук Укрши. Выпуск № 25 - Кшв, 2004. с. 65-78.

- Системи обробки шформацн. Зб1рник наукових праць. Випуск 9(37). Харюв, 2004. с.40-53;

- Системи обробки шформацн. Зб1рник наукових праць. Випуск 5(45). Харюв, 2005. с. 18-28;

- Зб1'рник наукових праць Хар1вського ушверситету Повпряних Сил. Випуск 6(6). Харюв, 2005. с.65-68;

- Зб1рник наукових праць. Нацюнальна Академ1я Наук Укрши, Выпуск №33.-Кшв,2005. с. 53-63.

3. Отражено в отчете о НИР.

4. Получено 5 патентов на изобретение и два положительных решения на выдачу патента.

Автор выражает глубокую благодарность д.т.н., профессору Червякову Н.И. основателю школы компьютерной ускоренной модулярной арифметики, который направлял автора к решению рассматриваемых в работе проблем и способствовал их внедрению.

Выводы

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

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

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

4. Применение методики позволяет процессору ПСКВ, реализующему ЦОС в расширенном поле Галуа CFf2'5y), сохранять коэффициент запаса работоспособности равный единице при возникновении 3 отказов. Таким образом, процессор обеспечивает функционирование даже при последовательном возникновении 3 отказов за счет снижения в допустимых пределах такого показателя качества как точность вычислений. При этом реализация непозиционного процессора, использующего корректирующие коды ПСКВ, обеспечивает сохранение работоспособного состояния при двух отказов, а применение метода «2 из 3» позволяет парировать только один отказ.

5. Проведенные исследования показали, что схемные затраты необходимые на реализацию вычислительной системы ЦОС, построенной на основе отказоустойчивого непозиционного процессора ПСКВ, составляют 79 процентов от аппаратурных затрат на многопроцессорное позиционное устройство ЦОС, реализующего метод маскирования отказов «2 из 3». Применение полиномиальной системы классов вычетов позволяет повысить скорость обработки данных более чем в 1,74 раза даже по сравнению с быстрыми алгоритмами обработки сигналов в позиционной системе счисления.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

12. Разработанная методика построения устойчивых к отказам непозиционных процессоров, функционирующих в ПСКВ позволяет синтезировать более надежные вычислительные устройства по сравнению с ранее с известными вычислительными системами, реализующими метод маскирования отказов «2 из 3». Для оценки пригодности данной методики был проведена разработка структуры отказоустойчивого процессора цифровой обработки сигналов, функционирующего в полиномиальной системе классов вычетов.

13. Применение методики позволяет процессору ПСКВ, реализующему ЦОС в расширенном поле Галуа С/7^, сохранять коэффициент запаса работоспособности равный единице при возникновении 3 отказов. Таким образом, процессор обеспечивает функционирование даже при последовательном возникновении 3 отказов за счет снижения в допустимых пределах такого показателя качества как точность вычислений. При этом реализация пепозиционного процессора, использующего корректирующие коды ПСКВ, обеспечивает сохранение работоспособного состояния при двух отказов, а применение метода «2 из 3» позволяет парировать только один отказ.

14. Проведенные исследования показали, что схемные затраты необходимые на реализацию вычислительной системы ЦОС, построенной на основе отказоустойчивого непозиционного процессора ПСКВ, составляют 79 процентов от аппаратурных затрат на многопроцессорное позиционное устройство ЦОС, реализующего метод маскирования отказов «2 из 3». Применение полиномиальной системы классов вычетов позволяет повысить скорость обработки данпых более чем в 1,74 раза даже по сравнению с быстрыми алгоритмами обработки сигналов в позиционной системе счисления.

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

1. Акушский И.Я., Юдицкий Д.М. Машинная арифметика в остаточных классах. - М.: Сов. радио, 1968. - 440с.

2. Амербаев В.М. Теоретические основы машинной арифметики. Алма-Ата: Наука, 1976.-324 с.

3. Акушский И.Я., Пак И.Т. Вопросы помехоустойчивого кодирования в непозиционном коде//Вопросы кибернетики. 1977, Т.28. С.36-56.

4. Арутюнов П.А. Теория и применение алгоритмических измерений. -М.: Энергоатомиздат, 1990. 256 с.

5. Айерленд К. Классическое введение в современную теорию чисел. -М.: Мир, 1987.- 416 с.

6. Акушский И.Я., Бурцев В.М. Вычисление позиционной характеристики (ядро) непозиционного кода/Теория кодирования и оптимизации сложных систем. Алма-Ата: Наука, 1977. С. 17-25.

7. Белоус А.Н. и др. Микропроцессорный комплекс БИС серии К1815 для цифровой обработки сигналов. М.: Радио и связь, 1992. - 256 с.

8. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986. - 536 с.

9. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1989.-448 с.

10. Ю.Боревич З.Н. Теория чисел. М.: Наука, 1972. - 495 с.

11. Быстрые алгоритмы в цифровой обработке изображепий/Под ред. Т.С.Хунга. М.: Радио и связь, 1984. - 221 с.

12. Бурый Е.В., Асеф Джафар Распознавание двумерных контрастных изображений объектов по инвариантным признакам. Нейрокомпьютеры в системах обработки изображений. М.: Радиотехника, 2003. - С.23-31.

13. Витерби А.Д., Омура Дж.К. Принципы цифровой связи и кодирования:326

14. Пер.с англ./Под ред. К.Ш. Зигангирова. М.:Радио и связь, 1982. - 536 с.

15. Воеводин В.В., Воеводин Вл. В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. - 608 с.

16. Вариченко JI.B. Абстрактные алгебраические системы и цифровая обработка сигналов. Киев: Наука думка, 1986. -.247 с.

17. Виноградов М.М. Основы теории чисел. М.: Наука, 1981. -176 с.

18. Галкина В.А., Червяков Н.И., Шапошников A.B., Сахнюк П.А. Нейронный цифровой фильтр с модулярной обработкой данных. /Нейрокомпьютеры: разработка, применение. №11, 2002, С.20-28.

19. Галушкин А.И. Теория нейронных сетей. Книга 1/Общая ред. А.И. Галушкина. М.: ИПРЖР, 2000. - 416 с.

20. Галушкин А.И. Теория нейронных сетей М.: ИПРЖР, 2000.-416 с

21. Галушкин А.И. Нейрокомпьютеры. Книга З/Общая ред. А.И. Галушкина. М.: ИПРЖР, 2000. - 528 с.

22. Галуев Г.А., Тараненко A.C. Нейросетевая система автоматической идентификации номерных знаков автотранспортных средств для задач комплексного обеспечения информационной безопасности/ Нейрокомпьютеры: разработка и применение. 2004, №5-6, с. 19-36.

23. Гамулин P.M., Ильясов Б.Г., Мугаттаров М.Г. Применение нейронных сетей в задачах распознавания трехмерных объектов. Нейрокомпьютеры в системах обработки изображений. М.: Радиотехника, 2003. - С.32-39.

24. Голд Б. и др. Цифровая обработка сигналов./Пер с англ. М.: Сов. радио, 1973.- 368 с.

25. Глухов М.М., Елизаров В.П., Нечаев A.A. Алгебра. В 2-х томах. М.: Гелиос АРВ, 2003.

26. Дагман Э.И., Кухарев Г.А. Быстрые дискретные ортогональные преобразования. Минск: Беларусь, 1984. - 145 с.

27. Дадаев Ю.Г. Арифметические коды, исправляющие ошибки. М.: Сов.327радио, 1969.- 168 с.

28. Даджион Д. Цифровая обработка многомерных сигналов/Пер. с англ. -М: Мир, 1989.-480 с.

29. Долгов A.M. Диагностика устройств, функционирующих в системе остаточных классов. М.: Радио и связь, 1982. - 64 с.29.3адирака В.К. Теория вычислений преобразований Фурье. Киев: Наука думка, 1983.-216 С.

30. ЗО.Зубчук В.И., Сигорский В.П., Шкуро А.Н. Справочник по цифровой схемотехнике. К.: Тэхника, 1990.-448 с.

31. Иыуду К.А. Надежность, контроль и диагностика вычислительных машин и систем. М.: Высш. шк., 1989. - 216 с.

32. Калмыков H.A. Организация нейронной сети с деградируемой структурой для ортогональных преобразований сигналов/Нейрокомпьютеры: разработка и применение. № 4, 2005, с.37-45.

33. Калмыков H.A. Математическая модель нейронной сети для исправления ошибок непозиционного кода поля Галуа в частотной области/ Нейрокомпьютеры: разработка и применение. №5-6, 2004, с.71-78.

34. Калмыков И.А., Червяков H.H., Щелкунова Ю.О., Бережной В.В. Математическая модель нейронных сетей для исследования ортогональных преобразований в расширенных полях Галуа/Нейрокомпыотеры: разработка, применение. №6, 2003. с.61-68.

35. Калмыков H.A., Червяков H.H., Щелкунова Ю.О., Бережной В.В. Архитектура отказоустойчивой нейронной сети для цифровой обработки сигиа-лов/Нейрокомпыотеры: разработка, применение. №12, 2004. с.51-60.

36. Калмыков H.A. Многоступенчатая полиномиальная система классов вычетов и ее нейросетевая реализация/Моделювания та шформацшш технологи. Зб1рник наукових праць. Нацюнальна Академ1я Наук Укрши. Выпуск № 33 -Кшв,2005. с.53-62

37. Калмыков И.А., Червяков Н.И., Щелкунова Ю.О., Бережной В.В., Шилов A.A. Нейросетевая реализация в полиномиальной системе классов вычетов операций ЦОС повышенной разрядности/ Нейрокомпьютеры: разработка и применение, 2004, №5-6, с.94-101.

38. Калмыков И.А. Коррекция ошибок в модулярных кодах на основе нейросетевого алгоритма вычисления номера интервала/3б1рник наукових праць XapißCbKoro ушверситету Повпряних Сил. Випуск 6(6). XapKÍB, 2005. с.65-68.

39. Калмыков И.А., Червяков Н.И., Щелкунова Ю.О., Бережной В.В. Математическая модель нейронной сети для коррекции ошибок в непозиционном коде расширенного поля Галуа/ Нейрокомпьютеры: разработка, применение. №8-9, 2003. С. 10-16.

40. Калмыков H.A., Щелкунова Ю.О., Гахов В.Р., Гордепко Д.В., Новиков В.И. Модель и структура нейронной сети для реализации ЦОС в расширенных полях Галуа/3б1рник наукових прац. Выпуск 1. «Системи обработки шфор-мацп», 2003, С.29-41.

41. Калмыков И.А., Щелкунова Ю.О., Шилов A.A., Чипига A.A. Разработка нейронной сети для определения интервального номера числа/ Материалы329

42. I Санкт-Петербургская межрегиональная конференция «Информационная безопасность регионов России (ИБРР-2003)», часть 2,Санкт-Петербург, 2003, С.54.

43. Калмыков И.А., Щелкунова Ю.О., Гахов В.Р. Повышение устойчивости функционирования биометрических систем защиты на основе применения полиномиальной системы класса вычетов/Известия ТРТУ №4, 2003. С. 166-169.

44. Калмыков И.А., Щелкунова Ю.О., Гахов В.Р. Применение полиномиальной системы класса вычетов для повышения отказоустойчивости биометрических систем аутентификации/Известия ТРТУ №4, 2003. С. 151-155.

45. Калмыков И.А., Шилов A.A. Математическая модель нейронной сети для определения интервального номера числа/Известия ТРТУ №4, 2003. С. 171.

46. Калмыков И.А., Щелкунова Ю.О., Гахов В.Р., Шилов A.A. Математическая модель коррекции ошибок в полиномиальной системе класса вычетов на основе определения корней интервального полинома/Волновые процессы. №5, т.6, Самара, 2003 С.30-34.

47. Калмыков И.А. Разработка метода контроля и коррекции ошибок для непозиционного спецпроцессора с деградируемой структурой/Зб1рник наукових праць 2004 Кшв, Нацюиальиа Академ1я Наук Укрши, Выпуск № 25, с. 65-78.

48. Калмыков И.А., Чипига А.Ф. Структура нейронной сети для реализации цифровой обработки сигналов повышенной разрядности/Вестник Ставропольского Государственного Университета, 2004, Выпуск № 38 с. 46-50.

49. Калмыков И.А., Бережной В.В. Многоступенчатая полиномиальная система классов вычетов в расширенных полях Галуа и ее нейросетевая реализация/Вестник Ставропольского Государственного Университета, 2004, Выпуск №38 с. 16-24.

50. Калмыков И.А., Чипига A.A. Методика пересчета коэффициентов ОПС для живучих систем биометрической аутентификации пользователя/ Материалы VI Международной научно-практической конференции «Информационная безопасность». Таганрог, 2004. - с. 144-146.

51. Калмыков И.А. Математические модели нейросетевых отказоустойчивых вычислительных средств, функционирующих в полиномиальной системе классов вычетов/ Под ред. Н.И. Червякова. М.: ФИЗМАТЛИТ, 2005. - 276 с.

52. Калмыков И.А., Велигоша A.B., Тынчеров К.Т. Анализ распределения одиночных ошибок в полном диапазоне при использовании СОК/ Деп. в/ч 1 1520. Сб. рефератов депонированных рукописей. Вып. 27, Сер. Б, инв.№ 2491, 1994.

53. Калмыков И.А., Велигоша A.B. Использование системы счисления в остаточных классах при разработке цифровых фильтров/ Деп. в/ч 1 1520. Сб. рефератов депонированных рукописей. Вып. 26, Сер. Б, инв.№ 2449, 1994.

54. Калмыков И.А., Велигоша A.B. Преобразователь двоичного кода в код СОК на основе ПЗУ для высокоскоростных цифровых фильтров/ Деп. в/ч 11520. Сб. рефератов депонированных рукописей. Вып. 26, Сер. Б, инв.№ 2458, 1994.

55. Калмыков И.А., Велигоша A.B. Повышение отказоустойчивости процессоров ЦОС путем реконфигурации структуры/Деп. в/ч 11520. Сб. рефератов депонированных рукописей. Вып. 25, Сер. Б, инв.№ 2318, 1993.

56. Калмыков И. А. Метод пересчета коэффициентов обобщенной полиадической системы для спецпроцессоров с деградируемой структурой/Известия ТРТУ. Тематический выпуск. Таганрог: Изд-во ТРТУ, 2005. №4, С. 35-42.

57. Калмыков И.А., Щелкунова Ю.О., Малофей А.О., Рыбальченко М.С. Спектральное обнаружение и локализация ошибок в полиномиальной системе классов вычетов/Математическое моделирование. М. 2005. Том 17, №3, С.67-74

58. Кормен Т., Лейзерсон Ч., Риверст Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000.-960 с.

59. Кнут Д. Искусство программирования для ЭВМ. Т.2.: Получисленные алгоритмы. -М.: Мир, 1977.-674 с.

60. Кун С. Матричные процессоры на СБИС./Пер с англ. М.: Мир, 1991.671 С.

61. Круглов В.В., Борисов В.В. Искусственные нейронные сети. Теория и практика. М.: Горячая линия, 2001. -380 с.

62. Каппелини В., Эмилиани П. Цифровые фильтры и их применение. -М.: Энергоатом из дат, 1989. 360 с.

63. Коляда А.П., Пак И. Т. Модулярные структуры конвейерной обработки цифровой информации. Минск: Университетское, 1992. -256 с.

64. Коляда A.A. О ядре числа в системах остаточных классов/ Кибернетика. №2, 1982. С.123-125.

65. Коляда А. А. О нормированном ядре числа в системе остаточных классов и его вычислениях/Вест. Бел. университета. Сер. 1. 1983. №3. С.12-16.

66. Клязник B.B. и др. Применение СОК при построении цифровых фильтров/Вычислительные средства в технике и системе связи. 1978. №3. С.69-78.

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

68. Касами Т. Теория кодирования. М.: Мир, 1978. - 576 с.

69. Кухарев Г. А. Алгоритмы и систолические процессоры для обработки многозначных данных. Минск: Наука и техника, 1990. -295 с.

70. Кочемасов В.Н. Акустоэлектронные Фурье-процессоры. М.: Радио и связь, 1987.- 166 с.

71. Каляев В.А. Многопроцессорные вычислительные системы. Таганрог: Наука, 1990.-205 с.

72. Кухарев Г.А., Тропченко А.Ю. Систолические процессоры для обработки сигналов. Минск: Беларусь, 1988. - 127 с.

73. Касаткин В.Н. Новое о системах счисления. Киев: Виша школа, 1982.96 с.

74. Куприянов М.С., Матюхин Б.Д. Цифровая обработка сигналов: процессоры, алгоритмы, средства проектирования. СПб.: Политехника, 1999. -367 с.

75. Каллан Р. Основы концепции нейронных сетей: Пер с англ. М.: «Вильяме», 2001.-288 с.

76. Карелов H.H. Реализация алгоритмов цифровой обработки сигналов на основе нейроподобной сети/ Нейрокомпьютеры в системах обработки сигналов. Книга 9.- М.: Радиотехника, 2003, С. 15-21.

77. Краснобаев В. А. и др. Помехоустойчивое кодирование в АСУ. Харьков: ХВВКИУ РВ, 1990. 154 с.

78. Краснобаев В. А. и др. Методы повышения надежности специализированных ЭВМ систем и средств связи. Харьков: ХВВКИУ РВ, 1990. - 172с.

79. Космиков Ю.Ы. Принципы построения графического нейросетевого процессора/ Нейрокомпьютеры в системах обработки изображений. М.: Радиотехника, 2003. - С.47-55.

80. Коротаев Г.А. Анализ и синтез речевого сигнала методом линейного предсказания // Зарубежная радиоэлектроника.-1990- №3- С. 31-50.

81. Лужецкий В.А. Машинная арифметика ЦВМ в кодах Фибоначчи и золотой пропорции. М.: Научный Совет АН СССР по, комплексной проблеме "Кибернетика", 1981.-64 с.

82. Моделирование сложных систем/А.П. Бусленко и др. М.: Наука, 1978.-339с.

83. Маклеллан Дж. и др. Применение теории чисел в цифровой обработке сигналов./Пер с анлг. М.: Радио и связь, 1983. - 264 с.

84. Морнл С. Цифровой спектральный анализ и его применения/Пер с англ. М.: Мир, 1990.-584 с.

85. Нейрокомпьютеры в системах обработки изображений/Под общ. ред. А.И. Галушкина. М.: Радиотехника, 2003. - 192 с.

86. Нуссбаумер Г. и др. Быстрые преобразования Фурье и алгоритмы сверток./Пер с англ. М.: Радио и связь, 1985. - 248 с.

87. Наумов К.П., Ушаков В.Н. Акустооптические сигнальные процессоры. М.:САЙНС-ПРЕС, 2002. - 80 с.

88. Наумов К.П., Егоров Ю.В., Ушаков В.Н. Акустооптические процессоры. М.: Радио и связь, 1991. - 324 с.

89. Надежность и эффективность в технике: Справочник/Ред. совет: B.C. Авдуевский (пред.) и др. М.: Машиностроение, 1987 - (В пер.)

90. Оссовский С. Нейронные сети для обработки информации. М.: Финансы и статистика, 2002. - 344 с.

91. Пелед Б. Цифровая обработка сигналов. Теория, проектирование и реализация. Киев: Виша школа, 1979. - 263 с.

92. Полард Дж. Быстрые преобразования Фурье в конечном поле/ Применение теории чисел в цифровой обработке сигналов. М.: Радио и связь, 1983.-С.147- 156.

93. Применение нетрадиционных арифметик в аппаратуре цифровой обработки сигналов/Романихип A.B., Кухарев Г.А. М.: РУМБ, 1991. -44 с.

94. Плекин В.Я. Цифровые устройства селекции движущихся целей. -М.: САЙН-ПРЕСС, 2003. 80 с.

95. Плекин В.Я. Алгоритмы и цифровые устройства селекции движущихся целей. М.: Издательство МАИ, 2002. - 124 с.

96. Рабинер Л., Голд Б. Теория и применение цифровой обработки сигналов./Пер с англ. М.: Мир, 1978. - 848 с.

97. Радиолокационные станции с цифровым синтезированием апертуры антенны/Под ред. В.Т. Горяинова. М.: Радио и связь, 1988. - 304 с.

98. Рейклитис Г и др. Оптимизация в технике: В 2-х книгах. М.: Мир,1986.

99. Раскин АЛ. Анализ сложных систем и элементы теории оптимального управления. М.: Сов. радио, 1976. - 344 с.

100. Рамишвили Г.С. Автоматическое опознавание говорящего по голосу. М.: Радио и связь-1981- 224 с.

101. Согомонян Е.С., Слабаков Е.В. Самопроверяемые устройства и отказоустойчивые системы. М.: Радио и связь, 1989. - 208 с.

102. Самсонов Б.Б. и др. Теория информации и кодирования. Ростов-на-Дону: Феникс, 2002. - 288 с.

103. Сверхбольшие интегральные схемы и современная обработка сигналов/Под ред. Г.Куна. М.: Радио и связь, 1989. - 472 с.

104. Справочник по цифровой вычислительной технике/ Малиновский Б.Н., Александров A.B. Киев: Техника, 1974. - 512 с.

105. Самсонов Б.Б., Плохов Е.М., Филоиепков А.И. Компьютерная ма338тематика (основание информатики). Ростов-на-Дону: Феникс, 2002. - 512 с.

106. СБИС для распознавания образов и обработки изображений/ Под ред. К.Фу. М.: Мир, 1988. - 247 с.

107. Стахов В. Г. Применение кодов золотой пропорции. М.: Радио и связь, 1984. - 152 с.

108. Сахпо И.В., Харченко A.B., Гаврилов Д.А. Применение нейропро-цессора Л1879ВМ1 для цифровой обработки сигналов PJIC обзора земной поверхности/Нейрокомпьютеры: разработка, применение. №5-6, 2004, С.84-90.

109. Сложные технически системы (оценка характеристик)/И.Г. Желез-нов и др. Под ред. И.Г. Железнова. -М.: Высшая школа, 1984. 119 с.

110. Содерстэнд М. Недорогой быстродействующий рекурсивный фильтр на основе арифметики остаточных классов// ТИИЭР. 1977. Т.65. №7. С.95-99.

111. Татузов АЛ. Эффективная организация нейросетевых вычислений при поиске объектов на изображении/ Нейрокомпьютеры: разработка и применение. №5-6, 2004, С.37-44.

112. Толковый словарь по вычислительным системам/В. Иллингуорт: Пер с англ.; Под ред. Е.К. Масловского. М.: Машиностроение, 1990. - 560 с.

113. Торгашев В.А. Система остаточных классов и надежность ЦВМ. -М.: Сов. радио, 1973.- 1 18 с.

114. Ткаченко А. В. Отказоустойчивые структуры в корректирующих счислениях/ Автоматика и телемеханика. 1993. №1. С. 154-165.

115. Ушакова Г.Н. Аппаратный контроль и надежность специализированных ЭВМ. М.: Радио и связь, 1982. - 372 с.

116. Физические основы акустооптики/ В.И. Балакший, В.Н. Парыгин, JI.E. Чирков. -М.: Радио и связь, 1985.-354 с.

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

118. Цифровая обработка сигналов: Справочник/ Под ред. Л.М. Голь-депберга. М.: Радио и связь, 1985. - 312 с.

119. Цифровая обработка сигналов/Под ред. А.Б. Сергиепко. СПб.: Питер, 2002. - 608 с.

120. Цифровая обработка сигналов на основе теоремы Уиттекера-Котельникова-Шеннона./М.А. Басараб М.А. и др. М.: Радиотехника, 2004. -72 с.

121. Червяков H.H. Отказоустойчивые непозиционные процессоры/ Управляющие системы и машины. 1988. №3. С.3-7.

122. Червяков H.H. Надежность и живучесть систем управления и связи, функционирующих в СОК. Ставрополь: СВВИУС, 1986. - 58 с.

123. Червяков H.H. Применение системы остаточных классов в цифровых системах обработки и передачи информации. Ставрополь: СВВИУС, 1985.- 68 с.

124. Червяков Н.И., Краснобаев В.А. Функциональные блоки и узлы отказоустойчивых и высокопроизводительных систем. Ставрополь: СВВИУС, 1989.-95 с.

125. Червяков Н.И., Бережной В.В., Оленев A.A., Калмыков И.А. Минимизация избыточности кода системы остаточных классов с одним контрольным основанием/ Электронное моделирование. 1994. №1. Т. 16. С.56-61.

126. Червяков Н.И. Преобразователи цифровых позиционных и непозиционных кодов в системах управления и связи. Ставрополь, СВВИУС. 1985. -63 с.

127. Червяков H.И., Калмыков И.А., Велигоша A.B., Иванов П.Е. Цифровые фильтры в системе остаточных классов/Радиоэлектроника. Т.38. №8, 1995,С. 11-20.

128. Червяков Н.И., Шапошников A.B., Сахнюк П.А., Лавриненко C.B. Применение нейронных сетей Хопфилда для коррекции ошибок в модулярных нейрокомпьютерах/Нейрокомпьютеры: разработка, применение. №11, 2002, С.10-16.

129. Червяков И.И., Шапошников A.B., Сахнюк П.А. Иерархическая модульная нейронная сеть с деградируемой структурой, функционирующая в СОК/Нейрокомпыотеры: разработка, применение. №2, 2000, С.63-71.

130. Червяков Н.И., Шапошников A.B., Сахнюк П.А. Оптимизация структуры нейронных сетей конечного кольца/Нейрокомпьютеры: разработка, применение. №10, 2001, СЛ 3-18.

131. Червяков Н.И., Бережной В.В., Гончарова E.H., Калмыков И.А. Локализация и исправление арифметических ошибок в модулярных нейрокомпьютерах/Нейрокомпьютеры: разработка, применение. №7, 2003. С. 28-32.

132. Червяков Н.И., Шапошников A.B., Сахнюк П.А., Калмыков И.А. Применение модулярных вычислений для нейрообработки сигналов/Материалы международной конференции «Нейрокомпьютеры и их применение 2002», Москва, 2002.

133. Червяков Н.И., Сахнюк П.А., Шапошников A.B., Ряднов С.А. Модулярные параллельные вычислительные структуры нейропроцессорных систем. М.: ФИЗМАТЛИТ, 2003. 288 с.

134. Червяков Н.И., Шапошников A.B., Сахнюк П.А. Применение нейронных сетей в задачах цифровой обработки сигналов/Нейрокомпыотеры в системах обработки сигналов. Книга 9.- М.: Радиотехника, 2003, С.6-14.

135. Червяков Н.И., Шапошников A.B., Сахнюк П.А. Модель структуры нейронной сети для реализации арифметики остаточных классов

136. Нейрокомпьютеры в системах обработки сигналов. Книга 9.- М.: Радиотехника, 2003, С. 22-31.

137. Червяков H.H., Шапошников A.B., Сахнюк П.А., Макоха А.Н. Нейрокомпьютеры в остаточных классах. М.: Радиотехника, 2003. - 272 с.

138. Шварцман В.О. Истоки и перспективы компьютерной телефонии/ Вестник связи. №4, 1999, С. 30-45.

139. Шелухип О.И., Лукьянцев Н.Ф. Цифровая обработка и передача речи/Под ред. О.И. Шелухипа. М.: Радио и связь, 2000. - 456 с.

140. Шаракшанэ A.C., Железнов И .Г., Ивницкий В.А. Сложные системы. М.: Высшая школа, 1977. - 243 с.

141. Шуба IO.A. Оценка целесообразности применения системы остаточных классов в аппаратуре обработки сигналов/Радиотехника, т.25 . 1980. №1. С.75-76.

142. Щелкунова Ю.О., Калмыков И.А. Применение полиномиальной системы класса вычетов для цифровой обработки сигналов/Материалы IV Межрегиональной научной конференции, г. Ставрополь, 2003, С.34-37.

143. Beckmann P.E., Musicus B.R. Fast fault-tolerant digital convolution using a polynomial residue number system./IEEE Trans, on Signal Processing, pp.2300-2313, July 1993.

144. Barzi F. Error correcting properties of redundant residue number systems / IEEE Trans. Comput.1973. vol. c-22, № 3, P.307-3E5.

145. Bayoumi M. Models for VLSI implementation of RNS arifmetic modules/Proc. of IEEE 6th Symp. on Comp. Arifmetic. June 1983. P. 174-182.

146. Chiang C. Residue arifmetic and VLSI/ IEEE IICD-83; Institute of Electrical and Electronics Conferences on Computer Design. 1983, № 3. P.80-83.

147. Fortes J.A. Gracefully degradable processor arrays// IEEE Trans. Corn-put. November 1995, P. 1033-1044.

148. Etzel M. The design of specialized residue classes for efficient recursive digital filter realization / IEEE Trans. Acoust. Signal Processing, vol. ASSP-30, 1982, № 6. P.370-380.

149. Gosentino R. Fauld tolerante in a systolic residue arithmetic processor array / IEEE Trans. Comput. 1988. vol.C-37, № 7. P.886-890.

150. Gregory R. Base conversion in the RNS / BBT. 1977. vol.17. P. 286302.

151. Haykin S. Neural Networks. A Comprehensive Foundation. New York: Macmillan College Publishing Company

152. Hopfield J. Neurons with graded response have collective computational properties like those of two-state neurons. Proceedings of the National Academy of Sciences, 81, p 3088-3092.

153. Hedlund K.S. Wafer scale integration of Configurable Highly Parallel (CHiP) processors. In Conference on Parallel Processing, pp/262-264, 1992.

154. Huang K.H, Abraham Y.A. Algorithm-based fault-tolerance for matrix operations. IEEE Tpransactions on Computers, pp. 518-528, Yull 1984.

155. I.Y. Iou, J.A.Abraham. Fault-tolerant matrix arithmetic and signal processing on lightly concurrent computing structures. Proc.IEEE, pp. 732-741, May, 1996.

156. Jullien J. A VLSI implementation of RNS-Based architectures / Inter343national Symposium on Circuits and Systems, Japan, 1985.

157. K.O'Keefe A digital signal processor with uses the RNS / Int. Conf. Systems, Networks and Computers. Mexico. 1971. vol.-2. P.669-673.

158. Key E.I. Digital signal processing with RNS/ IEEE IICD-86; Institute of Electrical and Electronics Conferences on Computer Design. 1983, № 3. P.204-207.

159. Miller D. An implementation of the IMS algorithm in the RNS / IEEE Trans.on Circuits and Syst. 1984. vol.CAS-31, № 5. P.452-461.

160. Moore W.R. A review of fault-tolerant techniques for enhancement of integrated circuit yield// Proc. IEEE P.684-698. May 1986.

161. Moore W.R. and A. McCade. Systolic Arrays. Adam Hilger, 1997.

162. Radindo G.R. System level reliability in convolution computa-tions./IEEE Trans. Acoust., Speech, Signal Processing, vol. 7, p.p.1241-1252, 1989.

163. Ramachadran V. Sniggle residue error correction in RSA/IEEE Trans. Comput. 1983. vol.32, May. P.504-507.

164. Salown Salam Binary-to-residue and residue-to-binary converters / In J. Electronic. 1986. vol.61, J6 1. P.79-84.

165. Shenoy M. Accurate RNS scaling technique for high-speed signal processor/IEEE Trans. Acoust. Signal Processing, vol. 37, 1988, № 6. P.929-937.

166. Siewiorek D.P. The Theory and Practice of Reliable System Design. Digital Press, 1993.

167. Tsend B. Implementation of DFT structures using RNS / IEEE Trans. Comput. 1984. voI.C-28, № 2. P.138-149.

168. Taylor J. A compression of DFT algorithms using residue architecture/ Computer and Electrical Engineering (England), Sept. 1981, Vol.8, p. 161 -171.

169. Taylor J., Jullien G. Residue number scaling and other operations using ROM arrays/ IEEE Trans. Comput., 1978, Vol. 27, № 4, p. 325-336.

170. Yoccoro J. Asistolic discret fourier transform using RNS/IEEE Proc/ ICASSP-86. 1986,vol.2, May. P.l 157-1160.

171. Uandelbaum D. Error correction in residue arithmetic / IEEE Trans. Comput. 1972. vol.C-21, № 6. P.538-545.

172. Ulman Z. Sign detection and implicit conversion of number in residue arithmetic/ IEEE Trans. Comput., 1983, Vol. C-32, № 6, p. 590-595.

173. Wilmhoft R. On hard errors in RNS architecture/ IEEE Trans. Acoust. Signal Processing, vol. ASSP-32, 1984, № 5. P.772-774.

174. Woods J. Stability of 2-D causal digital filters, using the residue theorem /IEEE Trans. Acoust. Signal Processing., 1983, vol.31, № 3. P.774-772.

175. Zhang C. Parallel designs for Chinese remainder conversion/ Proc. Int. Conf. Parallel Process (17-21.Aug. 1987). Univesity Park, 1987. P.557-559.

176. Zhang D. Parallel VLSI neural sections designs New York: Spingen, 1998, p 257.

177. Калмыков И.А. Устройство для вычисления сумм парных произведений/ Патент № 2012041/ Открытия. Изобретения. 1994. Бюл. № 8.

178. Калмыков И.А., Оленев А.А. Систолический отказоустойчивый процессор дискретного преобразования Фурье/ Патент № 2029437/ Открытия. Изобретения. 1994. Бюл. №16.

179. Калмыков И.А., Бережной В.В., Оленев А.А. Систолический процессор ДПФ с коррекцией ошибки/ Патент № 2018950 /Открытия. Изобретения. 1994.-Бюл. № 16.

180. Калмыков И.А., Лободин М.В., Алексишин Е.В., Щелкунова 10.0. Нейронная сеть для вычисления коэффициентов обобщенной полиадической системы, представленных в расширенных полях Галуа GF(2v)./naTenT № 2258956. Бюл. №23 от 20.08.2005.

181. Калмыков И.А., Емельяненко С.В., Лисицын А.В. Устройство для обнаружения и исправления ошибок в полиномиальной системе класса выче-тов./Патент № 2267808. Бюл. №01 от 10.01.2006.

182. Калмыков И.А., Емельяненко С.В., Лободин А.В. Устройство длявычисления сумм парных произведений в полиномиальной системе классов вычетов. Решение о выдаче патента (№ 2004101990/09(001852). Приоритет от 22.01.2004.

183. Копытов В.В, Малофей О.П., Малофей А.О., Малофей Ю.О., Царев Д.Б. Устройство коррекции ошибок с расширенным набором решающих правил/ Патент № 2152129 от 27.06.2000. БИ № 18, 20.07.98.

184. Малофей О.П., Малофей Ю.О., Авдеев В.Г., Якименко А.И., Якименко И.Л. Устройство коррекции ошибок с расширенным набором решающих правил и учётом сигнала стирания/ Патент № 2208907 от 20.07.03.

185. Зайлер Т.М. (СН). Управляемая компьютером отказоустойчивая система. Решение о выдаче патента (№ 2003132274/09(002166). Приоритет от 23.01.2003. Бюл. №19 (II). с.568.

186. Третья редакция рейтинга 50 самых мощных компьютеров СНГ Тор50 (11.2005). http://www.supercomputers.ru/7page-rating.