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

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

Григорьев Николай Федорович.

/

МЕТОДУ И СРЕДСТВА СИНТЕЗА ВЫСОКОНАДЕЖНЫХ ИНФОРМАЦИОННО-РАСЧЕТНЫХ СИСТЕМ В СТРУКТУРНЫХ КОДАХ

05.13.05 Автоматизированные, системы управления

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

Краснодар 19Э5

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

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

КЛШКО В. И.

Официальные оппоненты - доктор технических наук, профессор

ПЯАХОТНЮК А.Н. кандидат технических наук ТКАЧЕВ Ю.Г.

Ведущее предприятие - КБ "СЕЛЕНА" (г. Краснодар)

Защита диссертации состоится " 26 " декабря 1995 г. в 14.00 час. на заседании специализированного совета К 063.40.06 Кубанского государственного технологического университета (г.Краснодар, ул.Красная,135, ауд. 80).

С диссертацией можно ознакомиться в библиотеке Кубанского государственного технологического университета - 350072, г.Краснодар, ул. Московская, 2.

Автореферат разослан " 25 " ноября 1995 г.

Ученый секретарь специализированного совета К 063.40.06,к.т.н.доцент

В.И.Лойко

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

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

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

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

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

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

Поставленная цель требует решения следующих частных задач.

1. На основе исследования разнообразия СК выбрать (или впервые синтезировать) класс кодов, наиболее приспособленных для реализации в высоконадежной ИРС.

2. На основе исследования способов образования, преобразования, контроля и коррекции информации разработать метод коррекции информации на основе применения т-СПК различной кратности, позволяющий повысить безотказность работы ИРС.

3. Разработать схемотехнические основы синтеза высоконадежных устройств ИРС.

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

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

1. Расширенная классификация структурных кодов за счет введения ограничений на количество единиц и нулей в пакетах.

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

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

4. Теория нового класса СК - структурных ш-пакетных кодов равной мощности.

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

6. Методика количественной оценки разработанного метода

коррекции информации в га-СЯК различной кратности.

Практическая ценность работы определяется тем, что основные результаты исследования, полученные в ходе выполнения НИР, проводимых в Краснодарском ВВКЙУ РВ и помещенные в 2 отчетах о НИР, внедрены:

КВВКИУ РВ - в учебной дисциплине: "Техническая электроника",

КубГТИ - в учебной дисциплине: "Помехоустойчивость информационных систем",

НВЛ КВВКИУ РВ - в 10 программах, объединенных в пакет научных программ "Исследование естественно - избыточных структурных кодов и разработка естественно - надежных дискретных устройств", используемый при выполнении НИР, курсовом и дипломном проектировании.

КБ "СЕЛЕНА" - при разработке перспективных АСУ ,

ЦНТУ "КОМПЬЮТЕРИЗАЦИЯ"- при разработке перспективных АУ ИРС АСУ ,

НПК "УПРАВЛЕНИЕ" - при разработке перспективных АСУ .

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

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

2. Построение высоконадёжных устройств передачи и хранения информации перспективной ИРС возможно на основе разработанных математических моделей и синтезированных устройств в различных формах представления СК.

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

а

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

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

Апробация и публикации. По основным результатам работы сделаны доклады и получены положительные оценки на 2 научно -технических конференциях РБ {г. Ставрополь, октябрь 1992, г. Краснодар, сентябрь 1995 ).

Основные научные положения работы опубликованы в 4 научных статьях, 2 тезисах докладов и У изобретениях.

Структура работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка использованной литературы и приложения. Работа изложена на 151 странице, включая 5 таблиц и 28 рисунков. Список использованной литературы содержит 8? наименований.

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

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

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

Анализ принципов повышения надежности, проводимый на ос-

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

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

е(п)=з(п)(1-рд+2ртрд), (1)

где Кп)= 2к( РО РО' + Р1 РГ ), г РО, при РСХ0.5

1-РО, при Р0>0.5 ,

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

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

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

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

- б -

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

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

Обнаружение ошибок в общем случае состоит в проверке условий, налагаемых на (Л к Ч\. Для этого достаточно охватить контролем 1И+1 и У1+1 соседних символов СК.

Так функция контроля Е для МФ СК имеет вид:

Е(з)=А(з)(А(з-1) \/ ... V а^-ШПп). (2) В этом случае применяемым методом исправления является метод дешифрации, сигналов контроля (исправление. обнаруженных ошибок) и задается функцией:

•I(з) =Е(Б)(Е(З+1) V ... \/ ЕСБ+ишт)). (3) Наиболее простым методом исправления является . метод дешифрации запрещенных структурных групп, так называемое прямое исправление. Длина исправляемой структурной группы превышает длину контролируемой структурной группы. Например, в МФ СК исправляется единица, окруженная слева и справа менее чем 1Мп нулями. Тогда метод прямого исправления ошибок в б разряде зададим функцией:

I (3) = (А(3-Цшп)\/.,\/А(з~1))А(з) (А(э+-1)\/. .\/А(б+1Шп))

(4). .

Для исправления ошибок как типа переход 0 в 1 так и 1 в О необходимо использовать более сложные формы СК. Высокую исправляющую способность имеет ПОФ СК.

Функция прямого исправления для VI=2 и 1И=Т7з имеет вид: 1(5)=1(з)°~1 V КБ)1-0 V 1(5,з+и1"*0, (5)

где 1(з)0~1=А(б-2)А(з-1)А(з)А(з+1)А(3+2) V А(3-3)А(3-2)А(3) А(Б+2)А(з+3)А(з-1)А(Б+1), (6)

1(5)1"0=А(З)А{3+1)А(5+2)А(З+3)А(2-2)А(5-1) \/ А(3>А(3+1) А(з+2)А(3-3)А(з-2)А(3-1) V А(Б)А(3+1)А(3+2)А(3+3) А(З+-4)А(Б-3)А(Б-2) V А(З)А(Б+1)А(Б+-2)А(З+3)А(З+4) А(З-4)А(5-3) V г(3)А(з+2)А(з+3)АСз-4)А(5-3)А(з-2)

А(з-1) V 5(3)А(3+3)А(3+4)А(3-4)А(3-3)Й(3-2)А(3~1),

(?)

I(3,3+1)1-0=А(з)^(г+1)й(з+2)А(Б+4)А(з-4)2[(з-3)А(3-2)й(з-1) \/ А(5)А(з+1)А(з+2)А(з+3)А(з-2)А(д-1),(8)

причем 1(3,5+1)1-0 - это единичный сигнал исправления ошибки типа переход пакета 1 в 0.

Устройство, реализующее формулы .(5)-(8) приведено на рис Л.

Элементы И 1-10 выделяют запрещенные структурные группы, элемент ЮМ 11 их объединяет, а элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 12 дешифрирует.

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

Преобразование оптимальных и минимальных форм кода ш-СПК определяется выражением:

6(з)=Г(з+т)\/Т<з+П1-1)\Л . .N/7(3+1)4/7(3). (9)

где э.т - натуральные числа, Р(э) - функция б-го входа устройства, 6(з) - функция э-го выхода.

Обратное преобразование ш-СПК в СК МФ и 0Ф определяется

как:

6(5)-Р(5)Р(3-1)...Р(3-И) (10)

Преобразование ш-СПК в к-СПК определяется выражением: 6(з)=Р(з)Р(з-1)... Р(з-тЛ/Р(5+1)Р(з)... Р(Б-т+1Л/..

.. \/Р(э+Ю Р (э+к-1)... Р (э+к-т). (11)

Лемма 1 : Максимальный номер т-СПК ( Шах ) определяется . выражением:

Мтах= У+1МП-1.

Лемма 1 позволяет по виду СГ определить' количество возможных ш-СПК.

РИС.i. Устройство коррекции информации в ПОФ СК

- 9 - -

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

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

Обнаружение ошибок в 2-ОПК будет определяться выражением:

E(s)=A(s)A(s+l)A(s+2)\/A(s)A(s+l)A(s+2)=((A(s)=A(s+2))A(s+l)),

(12)

где = - логическая равнозначность.

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

а) ошибки перехода нуля в единицу, не нарушающей структуры кода;

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

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

Устройство обнаружения ошибок ь 2-СПК имеет наименьшие аппаратурные затраты в сравнении с другими устройствами гс-СПК при т>2, следовательно, вероятность возникновения ошибки в самом устройстве будет минимальной.

Функция преобразования 2-СПК в 3-СПК будет иметь вид: G(s) = F(S) V F(S+1) F(s+2) (13!

Преобразование 3-СПК в 2-СПК с исправлением при каютии сигнала ошибки описывается выражением:

G(s) « ( Fis) F(s+1) F(s+2) V Fis) F(s+1) F(s+2) F(s+3) V

V F(s-l) F(s) F(s+1) \/ F(s-l) F(s) F(s+1) F(s+2) V

V F(S-l) F(s) F(s+1) F(s+2)) /\ E . (14)

Разработанная методика синтеза предполагает иметь базовые блоки устройств СПК.

Так реализация алгоритма преобразования З-СПК в 2-СПК при наличии сигнала ошибки представлена на рис.2. Устройство содержит группу инверторов 1, группу элементов И 2, многовходо-вый элемент ШШ 3 и элемент Л 4.

Под каналом переработки информации в первом приближении подразумевается арифметико-логическое устройство. Однако функции канала намного шире :

- контроль входной информации;

- коррекция входной информации;

- выполнение арифметико-логических операций;

- коррекция выходной информации.

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

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

Блок контроля входных дачных 2 предназначен для контроля 2-СПК и формирования сигнала ошибки ( F(2) ). Работа блока описывается выражением:

F(2) = FC1] V FC2] \/ .. V Fthl V ..\/ FCll], (15)

где Fth] описывается выражением (12), п - разрядность входных данных.

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

Блок коррекции входных данных 5 предназначен для коррекции 2-СПК с помощью З-СПК при наличии сигнала ошибки ( F(2) ).

Работа блока описывается выражением:

Z(5)Eh] = Q[h3 F(2) V МЫ,

(16)

рис.2. Устройство преобразования 3-СПК в 2-СПК при наличии сигйала ошибки

рис.3. Структурная схема канала переработки информации в СПЯ

- 13 -

где 2(5)ЕЫ - функция И - го выхода блока;

ФСМ описывается выражением (14) при условии Е >= Р(2).

Блок коррекции команд 6 и блок коррекции результата 7 предназначены для коррекции 2-СПК с помощью 3-СПК при наличии сигнала ошибки .

Блок кодирования 8 предназначен для передачи данных в 2-СПК и для кодирования 2-СПК в 3-СПК при наличии ошибки (Р(4)). Работа блока описывается выражением:

ХСЬЗ = ЧЕЙ] Р(4) \/ СЕМ Р(4), (17)

где ХСЬ] - функция 11 - го выхода блока;

ССЬЗ - описывается выражением (13).

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

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

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

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

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

В приложении приведены программы построения и анализа

/

математических моделей устройств, работающих в СК.

К основным результатам, полученным в ходе исследований,

можно отнести следущее:

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

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

- сделан вывод о предпочтительном применении СК МФ в каналах хранения и передачи информации, полученный на основании расчётов по выведеным аналитическим зависимостям;

- получены математические модели устройств контроля и коррекции информации различными методами;

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

- разработана теория нового класса СК - структурных ш-па-кетных кодов равной мощности;

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

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

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

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

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

- предложена методика количественной оценки разработонно-го метода коррекции информации в ш-СПК различной кратности;

По материалам диссертации опубликованы следующие работы:

1. Научно-исследовательская работа по х/д N 499 : отчет N 5 МО СССР Руководитель работы Ключко В.31 - Краснодар, 1935,с.141.

2. A.C. 1361554 Устройство для исправления однократны): ошибок р-кодов Фибоначи /А.В.Ткаченко,Н.Ф.Григорьев //Б.И.-1987.- N 47.

3. A.C. 1479932 Устройство для обнаружения и исправления однократных ошибок оптимальных р-кодов Фибоначчи .-/A.B.Ткаченко, Н.Ф.Григорьев// Б.И.-1989.-N 18.

4. Григорьев Н.Ф. Синтез устройств обнаружения и исправления ошибок : Тезисы доклада // Принципы построения устойчивых к сбоям и отказам систем обработки' и передачи информации. -Ставрополь,1991.-С.19-21.

5. Научно-исследовательская работа по х/д N 84/91 : Исследование путей совершенствования управления комплексами/ Руководитель работы Шкребко М. Н. - Краснодар,1991,с.128.

6. A.C. N 1817248 Устройство для исправления ошибок 2-х кодов Фибоначчи /Ткаченко A.B., Григорьев Н.Ф.// Б.И.-1992

7. A.C. Устройство для коррекции 1-кодов Фибоначчи /Ткаченко A.B., Григорьев Н.Ф.// Заявка N 93029600 от 1.06.93. полок. реш. вх. 4/448 3.11.93.

8. Патент по заявке 5039674 Устройство для исправления ошибок 1-кодов Фибоначчи /A.B.Ткаченко,Н.Ф.Григорьев//Решение о выдачи патента вх.- 4/89 24.03.94.

9. Патент по заявке 5042500. Устройство для исправления р-кодов Фибоначчи //Ткаченко A.B., Григорьев Н.Ф.// Решение о выдаче патента вх. 4/137 от 10.05.94.

10. Патент N 2022341 Устройство для исправления ошибок в корректирующей системе счисления /А.В.Ткаченко,Н.Ф.Григорьев/^. И. -1994.- .

11. Григорьев Н.Ф. Обнаружение и коррекция ошибок при цифровой переработке информации в структурных кодах :Тезись' доклада // Принципы построения высоконадежных комплексов /-Краснодар,1995.-С.15-17.

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

- 16 -

13. Григорьев Н.Ф., Рудницкий В.Н., Ключко В.И. Синтез кодов и систем счисления для устройств цифровой переработки информации. Сборник научных трудов "Автоматизация технологических процессов и производств в пищевой и приборостроительной промышленности".Краснодар,1995.-В печати.