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

= и Ои

' 1Г:Р ".БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

ГАЛЕЦКИИ ВЛАДИМИР МИХАИЛОВИЧ

АШ1АРАТНО-ОРИЕНТИРОВАННЫЕ МЕТОДЫ КОНТРОЛЯ ГЕНЕРАТОРОВ ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

Специальность 05.13.05 - Элементы и устройства вычислительной техники и систем управления

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

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

МИНСК 1994

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

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

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

доктор технических наук, доцент Орлов М. А.

кандидат технических наук Быков С. В.

Ведущая организация - Минское высшее военное инженерное

заседании специализированного совета К 056.05.01 Белорусского государственного университета информатики и радиоэлектроники из адресу: 220027, Минск, ул. П. Бровки, 6.

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

училище

Защита состоится "21 " апреле 1994г. в 14 час, на

Автореферат разослан

Ii

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

совета К056.05.01, к.т.н., доцен' I. П.Пашкевич

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

Актуальность. Широкое применение вычислительной техники на современном этапе развития производства предопределило значительное повышение требований к ее надежности: Невозможность создания идеально надежного цифрового устройства требует использования испытательного оборудования - автоматизированных систем контроля и испытаний САСКЮ. Вопросам разработки средств испытаний посвящен ряд теоретических и практических работ советских ученых А. П. Го-ряшко, В.А.Гуляева , А. Е. Леусенко, И. П. Литикова, А. Н. Морозевича, П.П.Пархоменко, Е. С. Согомоняна, В. Н. Ярмолика В.Н. , и др., а также ведущих специалистов зарубежных фирм Hewlett Packard, Tracor Northeen, Datarest (США), Derritron, Ling (Великобритания), Bruel & Kjaer (Дания), Instrument Со Ltd, Shinken (Япония).

Перспективным методом, используемым для синтеза испытательных воздействий в АСК, является аппаратурный метод их получения с использованием генераторов псевдослучайных.чисел (ГПСЧ).

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

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

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

Впервые задача контроля ГПСЧ м концепция ее решения сформулирована А. Н. Морозевичем совместно с А.Е. Леусенко и опубликована в 1983г. С тех пор появились публикации - авторские свидетельства на изобретения, в которых предлагались частные решения задачи контроля работы ГПСЧ. Однако до сих пор отсутствует ре-

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

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

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

Цель работы достигается решением следующих задач;

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

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

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

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

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

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

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

Разработаны оригинальные схемотехнические роаонай

контроля генераторов псевдослучайных чисел.

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

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

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

Диссертационная работа выполнялась в рамках госбюджетных научно-исследовательских работ ГБ-42-9101, ГБ-65-8701; межотраслевой программы "Персей-12" N 293/60/264; договора N 3/92/42 о творческом содружестве.

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

Апробация работы. Материалы в полном объеме обсуждены на совместном заседании Кафедр радиэлектроники и вычислительной техники Минского высшего военного инженерного училища, на совместном заседании лабораторий электрических и магнитных измерений и физических и химических основ микроэлектроники Института электроники, а основные результаты диссертационной работы обсуждены на XX научно-технической конференции молодых ученых и специалистов НПО "Агат" "Проблемы создания систем управления и средств автоматизации" (Минск, 1989), на семинаре "Практика автоматизации настроеч-но-регулировочных и контрольно-испытательных работ в производстве изделий радиоэлектроники, приборостроения и связи" (Ленинград, 1991), на XXV Юбилейной научно - технической конференции Минского высшего военного инженерного училища "Проблемы совершенстования и эксплуатации радиоэлектронного и радиотехнического вооружения и автоматизированных систем управления" (Минск, 1993).

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

Структура и сбьем работы. Диссертация состоит из введения,

четырех глав и заключения, включает список литературы из 94 наименований С 9 страниц) и приложения с результатам! экспериментальных исследований и актами внедрения основных результатов диссертационной работы (17 страниц 3. Основное содержание работы изложено на 158 страницах машинописного текста и иллюстрировано 37 рисунками С39 страниц) и 9 таблицами С9 страниц).

Автор защищает:

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

2. Методы контроля ГПСЧ, основанные на сравнении контролируемых параметров с их эталонными значениями и динамическим прогнозом.

3.. Оригинальные схемотехнические решения средств контроля ГПСЧ. ' ■

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

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

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

Анализ областей использования ГПСЧ показал, что одним из основных требований,' обеспечивающих эффективное применение генераторов является их устойчивость к отказам различного типа.

Показано, для исследования влияния отказов элементов генераторов, можно использовать два вида описаний ГПСЧ:

конечным автоматом;

рекуррентным логическим выражением.

Описание ГПСЧ как конечного автомата С Яковлев В. В., Федоров Р.Ф. и др.) с матрицей переходов размерностью 2П х 2" позволяет получать качественные характеристики функционирования реального ГПСЧ, однако оно громоздко.

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

С учетом отказов элементов функционирование ГПСЧ монет быть представлено в следующем виде: л

Ф\/Ф Ф - V

а (к+1) = С ИЛИ 0„ л 0 ) л к 5 (к) л у _(к) О л 0„

1 О II 1

• й = 5 С[а,(к) л о*л О* ] Л ^ о«л о«) (1)

1 =1 1 1 В1 1 В1 1

а, Ск+1) = а. Ск) л ы ^ Б.Ск) л х,, Ск) 1 1 11 1

где:

N = { N , Нг,..., > - вектор сигналов, характеризующих правильную работу 1-тых элементов памяти СЭП), 1=1, п; БСк) = < Ск), 5гСк),... ,БпСк)) - вектор сигналов факта сбоя 1-го ЭП в к-том такте работы;

ХдСк) = < Х3Ск), Х3Ск)..... Х3(к) > - вектор сигналов, учитываю-

1 г п

щих состояние 1-тых ЭП в момент сбоя;

О = { 0], 0в..... 0п > - вектор сигналов, учитывающих факт отказа константного типа 1-го ЭП;

О0= { Ов , Ов ..... 0В > - вектор сигналов, учитывающих виды от» а п

каэов константного типа в ¡.-том ЭП;

И!'= ( Н*, И*,..., Я* ) - вектор сигналов, характеризующих правильную работу 1-тых элементов Й;

0* = { 0* , 0* ,... .О* ) - вектор сигналов, учитывающих виды от-

1 2 П

казов константного типа 1-го элемента И;

04= { О*, О*..... О* > - вектор сигналов, учитывающих факт отказов константного типа х-го элемента И;

№= { ГР, И"..... > - вектор сигналов правильной работы 1-тых

входов элемента М2 в цепи обратной связи;

0а= { О", О",..., 0® ) - вектор сигналов факта отказа константного типа 1-го входа элемента М2;

0°= { 0" , 0® ,..., > - вектор сигналов, учитывающих виды - от-

1 г п

казов константного типа 1-тык входов элемента М2;

И®- сигнал, характеризующий правильную работу выхода элемента М2;

О® - сигнал отказа константного типа выхода элемента М2;

О®- сигнал вида отказа константного типа на выходе элемента М2.

Моделирование на ЭВМ отказов с использованием рекуррентного выражения (1), а также исследование отказов на физических ГПСЧ позволило выявить два вида проявления отказов: геп?'р5тор вуяой^единиц;

нарушение порядка чередования кодовых наборов.

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

Вышеизложенное ориентирует исследование на:

- разработку методов оценки влияния отказов элементов ГПСЧ на формирование выходной последовательности;

- выявление общих принципов построения устройств, минимизирующих влияние отказов;

- использование разработанных методов для определения необходимости применения специальных средств для подтверждения правильности формирования выходных последовательностей ГПСЧ;

- разработку методов контроля ГПСЧ, удовлетворяющих требованиям оперативности, достоверности и дополнительным затратам оборудования.

Во второй главе разработаны методы оценки влияния отказов элементов ГПСЧ на формирование выходной последовательности.

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

. В результате отказа элементов ГПСЧ на его выходе может возникнуть ошибка. Под ошибкой будем понимать инвертирование выходного сигнала, который появился бы на выходе ГПСЧ ь данном такте при идеальной работе элементов.

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

Предложено оценку влияния отказов осуществлять на основе описания генератора конечным автоматом по следующему алгоритму:

1. Определяются матрицы £ - переходных вероятностей ЭП и 5 -началъных вероятностей ошибок сигнала из соотношений:

Б Я

II 12

5 Б г; г г

Г£<5 р •• вероятность сбоя ЭП;

1-р р

Р Ь'Р

SoiCl,i) 1

So2Cl,i) 0

3 Cl.i) =

где индекс 1 в выражении ЗоС1Д) указывает на первый такт работы; 1 = ГТп , п - число ЭП ГПСЧ.

2. Матрицы вероятностей состояний на выходах 1-тых разрядов ГПСЧ после первого такта работы находятся в соответствии с выражением:

1-p p 1 1-p

S Cl,i) = S * S0ci,i) = К =

p 1-p 0 p

3. Вероятности правильных состояний на выходах i-тых ЭП РС1Д) и вероятности ошибок после первого такта определяются из соотношений:

РС1,1) = PC 1,2) = ... = PCl,n) = 1-p ZC1,1) = ZC1,2) = ... = ZCl,n) = p

4. Вероятности ошибок в сигнале на выходе элемента М2 для второго такта работы определяются в соответствий с выражением:

ZCk+1) = cij* ZCk.i) -

tTi

at* ZCk,i) * aj* ZCk.J) +

t <1 <J <1 —n

jil <J in

c^* ZCk.i) * aj* ZCk.j) * Oj* ZCk,l)

... + С-1)" ' * 2° ' * а * гСк,1) * а * гСк,2) * ... * а * гск.п)

12 П

где к - номер такта, к = 1,2,3...;

коэффициент а4 определяет наличие или отсутствие обратной связи в 1 - том разряде ГПСЧ. Если обратная связь есть, то а = 1, в противном случае а = 0.

5. Матрицы начальных вероятностей сигналов &оС2,1) для ^ых разрядов во втором такте работы генератора определяются в соответствии с выражением:

S Ск+1,1) =

1-ZCk+1) ZCk+1)

Ск+1Д) = 5СкД-1), где J = глТ

6. Матрицы вероятностей состояний сигналов ¡?(2Д) на выходах 1-тах разрядов ГПСЧ во втором такте работы могут быть определены следующего выражения:

S (2,i) = S * S C2,i)

7. Из матриц SC2,i) определяются значения P(2,i) и ZC2,i)..

Для определения вероятностей ошибок в выходной последовательности для других тактов работы ГПСЧ необходимо последовательно повторить шаги 4 ^ 7 данного алгоритма до требуемого числа тактов или до появления заданного значения вероятности ошибки ь определенном разряде или на выходе сумматора по модулю два в цепи обратной связи.

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

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

Пренебрегал вероятностями отказов константного типа можно отметить, что полную группу событий будут составлять события, заключающиеся в нормальной работе N, i-того ЭП и сбое Sj, т. е. выполняется следующее соотношение:

. PCN' ) + PCS,) = 1 или PCN ) = 1 - PCS ), i i i l

где PC7i( )-вероятность того, что i-тый 5П будет работать правильно;

PCSj)-вероятность того, что в i-том элементе памяти наступит сбой.

Следовательно, функционирование такого ГПСЧ в общем виде описывается следующей системой уравнений:

a Ck-fl) = S Ck+1) ® У®с<* a, Ck)

1 1 J С 2)

a^Ck+1) = SjCk+D ® a Ck) . j = 2Tn

Пусть PtСк)-вероятность появления ошибки на выходе i-того ЭП ГПСЧ в к-том такте его работы, a PCS) - вероятность сбоя ЭП.

С учетом того, что вероятности сбоев ЭП равны и остаются постоянными в течение достаточно большого промежутка времени, систему уравнений (Й) можно преобразовать к следующему виду:

. п п

Р Ck+1) = 2°* С PCS) + ]> а * ?i Ck)) - 2'* CPCS) J а* P Ck) + i i

+ У at* PtCk) * Oj* PjCk)) + 22CPCS)) J------a^

i<i<J<n i<l<j<n (3)

* P, Ck) * a,* P.Ck) + У a * P. Ck) * a4* P,Ck) * a,»

1 J J b--- 1 » J J J

1S1 <j a5n

* P, Ck)) -... + C-l)n* 2n* PCS) * a * P Ck) * a * P Ck) *... *

1 t 1 2 S

* a * P Ck)

n n

PjCk+n = PCS) + P t Ck> - 2 * PCS) * j = Z7n

Последнее выражение показывает, что путем итерационной процедуры вычисления для каждого такта к работы ГПСЧ может быть вычислена вероятность появления ошибки Pj Ck) в j-том разряде ГПСЧ.

Представленная оценка влияния сбоев ЭП на формирование выходной последовательности ГПСЧ позволяет учесть влияние структуры обратных связей на достоверность выходных сигналов. Она позволяет дифференцировать структуры по критерию появления ошибки на выходе генератора. Исследования показали, что лучшей структурой ГПСЧ с с точки зрения минимизации вероятности появления ошибки на выходе первого разряда является такая, которая соответствует характеристическому полиному с наименьшим числом ненулевых членов и имеющему наибольшую сумму показателей степеней этих членов. Значение вероятности ошибки непрерывно возрастает с увеличением числа тактов и стремится к своему пределу, равному 0,5. Это обусловлено наличием элемента М2 в цепи обратной связи.

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

константного типа элементов памяти ГПСЧ на его функционирование.

Поведение идеального.ГПСЧ определяется алгебраическими свойствами характеристического многочлена р(х), соответствующего структуре ГПСЧ.

Показано, что в условиях отказов константного типа элементов памяти характеристический многочлен принимает вид:

рСх) = р'Сх) © ГСотк),

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

Функция отказов определяет прямая или инверсная последовательность, соответствующая полиному р'Сх) будет формироваться на выходе отказавшего ГПСЧ. Функция отказов может принимать только два значения - 0 или 1. Значение ГСотк) зависит от числа отказов, их вида и числа обратных связей, попадающих на отказавшую часть ГПСЧ. Одним из условий формирования невырожденной последовательности на выходе отказавшего ГПСЧ является то, что ГПСЧ, образованный в результате отказов и соответствующий по структуре характеристическому многочлену р'Сх) в Момент отказа не должен находиться в запрещенном состоянии. Если ГСотк) = 1, то запрещенным состоянием на момент отказа является единичное состояние ГПСЧ, соответствующего многочлену р'Сх). Если Потк) = 0, то запрещенным состоянием является нулевое состояние ГПСЧ.

Исследования показали; что с точки зрения влияния отказов константного типа есть принципиальная разница, какой разряд ГПСЧ является его выходом. Если выходом ГПСЧ является отказавший разряд, то на выходе генератора будет формироваться вырожденная последовательность символов. Поэтому целесообразно выходную последовательность символов снимать с первого разряда регистра сдвига или с выхода сумматора по модулю два. Чем больше количество обратных связей в ГПСЧ, тем больше вероятность того, что при возникновении отказа полином р'Сх) будет иметь максимальную из возможных разрядностей.

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

вно числу разрядов регистра сдвига ГПСЧ.

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

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

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

На основе сопоставительного анализа методов контроля ГПСЧ разработана обобщенная структурная схема устройств контроля ГПСЧ, использование которой позволяет рационально подходить к выбору параметров разрабатываемого оборудования.

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

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

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

проявляющиеся на полном периоде (длина ПСП, четность числа единиц");

проявлявшиеся на длине меньшей длины ПСП (максимальное число единиц в серии равно п, нулей - п-1 и эти серии встречаются на периоде ПСП один раз)

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

ГПСЧ.

Аддитивно - циклическое свойство последовательности 2 можно записать в виде:

2 = ъпг © дкг

Применяя операций сдвига п раз к обеим частям этого уравне-ненйя, получим:

ъпг = оп2 (ок2 в опг) или

Ъп2 © (.дк2 ф Бп2) = 0 Стой 2)

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

Показано, что константные отказы.вырождают ГПСЧ в генератор нулей/единиц, проявляющийся в последнем разряде С для последовательного ГПСЧ). Поэтому для контроля константных неисправностей", возникающих в любом разряде генератора, необходимо контролировать последний разряд, что и реализовано в технических решениях, защищенных авторскими свидетельствами на изобретения N1619264, N1667228.

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

Прогнозирование заключается в прогнозировании символов ПСП на 1 тактов, затем по результату сравнения реального символа с прогнозом делается вывод о качестве функционирования ГПСЧ.

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

повлиять на достоверность выходной последовательности ГПСЧ. Однако путем изменения интервала контроля можно регулировать оперативность контроля. Исследована зависимость объема блока памяти для хранения массива эталонных кодов от интервала контроля для ГПСЧ различной разрядности. Предложена структурная схема устройства, реализующего метод. Интервал контроля программируется в счетчике, оперативность контроля равна интервалу контроля. При 1=1 оперативность контроля наилучшая (решение о выдаче авторского свидетельства по заявке N48898553.

При дублировании в качестве блока формирования "эталона" используется аналогичный ГПСЧ.

При отказе одного из ГПСЧ контроль ПСП прекращается, необходима установка обоих ГПСЧ в одинаковое состояние. Дополнительно необходимо применять метод контроля запрещенных состояний регистров сдвига. Этот метод контроля необходим для того, чтобы, если в результате отказа какой-нибудь ГПСЧ установится в запрещенное состояние, то чтобы другой ГПСЧ в результате их установки в эквивалентные состояния тоже не был бы установлен в запрещенное состояние. Поэтому в результате "коррекции" сбившегося ГПСЧ на выходах устройства будет формироваться последовательность кодов ГПСЧ без вырождения. Метод позволяет обнаружить все отказы кроме эквивалентных, которые произошли одновременно в обоих регистрах ГПСЧ.

Аппаратные затраты на реализацию метода определяются разрядностями эквивалентного ГПСЧ, схем дешифрация запрещенных состояний генераторов, а также блока сравнения, который представляет собой схему поразрядного сравнения. Оперативность контроля равна интервалу контроля, 1=1 (A.c. И1758849).

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

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

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

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

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

Приложения содержат: результаты экспериментальных исследований, подтверждающих основные положения диссертационной работы; акты внедрения результатов НИР

ЗАКЛЮЧЕНИЕ

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

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

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

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

чисел.

4. Разработаны методы контроля псевдослучайных последовательностей, основанные на контроле статистических характеристик з» на динамическом прогнозировании символов на заданное число тактов и сравнении реальных символов с прогнозом CA.с. N1619264, A.c. N1667228); разработаны методы контроля ссстояний разрядов генераторов псевдослучайных чисел, основанные на комбинации дублирования с дешифрацией запрещенного состояния и базирующийся на статическом прогнозе СА.с. N1758849, решение о выдаче A.c. по заявке N4889855);

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

5. Разработано, изготовлено и внедрено 5 оригинальных генераторов псевдослучайных чисел с контролем для систем автоматизации контроля и испытаний. Наиболее существенными из внедренных являются: генератор псевдослучайных чисел устройства тестового контроля цифровых модулей ЗН014, генератор тестовых наборов стенда контроля датчиков угловых перемещений; генератор псевдослучайных последовательностей для исследования динамккй гелий-неонового лазера, генератор псевдослучайных чисел автоматизированной системы управления вибрационными и ударными испытаниями (Персей-12).

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

Основные результаты отражены в следующих работах:

1. Галецкий В. М. Оценка влияния сбоев элементов генераторов псевдослучайных чисел на формирование выходной последовательности. Вести АН Беларуси, Сер. физ.-техн. наук, N1, 1992, с. 118-122.

2. Мороэевич А. Н. , Галецкий В. М. Оценка влияния сбоеБ элементов генераторов псевдослучайных чисел на формирование выходной последовательности. Вопросы радиоэлектроники, серия ОВР, 1991, N11, с. 49-56.

3. Галецкий В. М. Отказоустойчивые генераторы псевдослучайных чисел./Тез. докл. XXV Юбилейной научно-технической конференции МВВИУ "Проблемы совершенствования и эксплуатации радиоэлектронного и радиотехнического вооружения и автоматизированных систем управления", Мн., 12-14 мая 1993.

4. Мороэевич А.Н., Галецкий В.М. Аппаратно-ориентированные методы контроля генераторов псевдослучайных чисел./ Тез. докл.

15

XXV Юбилейной научно-технической конференции МВВИУ "Проблемы совершенствования и эксплуатации радиоэлектронного и радиотехнического вооружения и автоматизированных систем управления", Мн., 1214 мая 1993.

5. Разработка на базе . комплексно-моделирующего стенда средств и методов автоматизации процессов испытания, контроля и диагностики комплексов средств автоматизации: Отчет по НИР "Прогресс", кн. 2 / Научк. рук. В. Б. Мосунов, отв. исп. Шилинговский В. И., Галецкий В.М. и др. - Гос. N Y-302402, Мн.; НИИ "Агат", 1986. - 57 с. , ил.

6. Исследование и разработка микропроцессорных систем управления: Отчет / Научн. рук. А. Й. Мороэевич, отв. исп. Б. Б. Трибу-ховский, В.М. Галецкий и др. - Гос. N01880001192, Инв. N 02890031298. - Мн.: АН БССР, 1989. - 93 с. , ил.

7. Исследование и разработка микропроцессорных систем управления: Отчет / Научн. рук. А. Н. Мороэевич, отв. исп. Б. Б. Трибу-ховский, В.М. Галецкий и др. - Гос. N01990001192, Инв. N 02910027319.- Мн.:АН БССР, 1991. - 104 е., ил.

8. Развитие и разработка аппаратных и программных средств профессиональной ориентации для ПЭВМ и методы их проектирования: Отчет/Научн. рук. А.Н.Мороэевич, отв. исп. Б. А.Железко, В.М. Галецкий и др. -Гос. N 01910007195, Инв. N 02920010713. - Мн.: АН БССР, 1992. - 46 с. , ил. '

9. A.c. 1619264 СССР, МКИ G06F 7/58. Генератор псевдослучайной бинарной последовательности. / B.C. Миронов, Е.А. Пищик, В.М. Галецкий, А.Н. Мороэевич ССССР). Опубл. 07.01.91. Бюл. 111. - Зс.: ил.

10. A.c. 1667228 СССР, МКИ НОЗК 3/84. Генератор псевдослучайной последовательности./ В.С. Миронов, В.М. Галецкий, Е.А. Пищик, А.Н. Мороэевич ССССР). Опубл. 30.07.91. Бюл. N28. - Зс. :ил.

И. A.c. 1758849 СССР, МКИ НОЗК 3/84. Устройство для контроля псевдослучайных чисел. / Мороэевич А.Н., Галецкий В.М. ССССР). Опубл. 30.08.92. БЮЛ.Н32. -6с. :ил.

12. Решение о выдаче авторского свидетельства по заявке N4889855 от 13.01.91г. Устройство для контроля последовательности псевдослучайных чисел. Мороэевич А. Н., Галецкий В.М., Миронов B.C., Пищик Е.А ССССР)

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

ГАЛЕЦКИЙ ВЛАДИМИР МИХАИЛОВИЧ

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

Специальность: 03.13.05 - Элементы и устройства вычислительной техники и систем управления

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

Отпечатано на ротапринте БГУИР. 220600, г. Минск, ул. П. Бровки, 6

Подписано в печать 05.03.94 Усл. печ. л. 1.0 У'

Тира* 100 экз.

Уч. изд. л. 1.0

формат бумаги 60x84 1/16 1.0 Заказ П9.

Бесплатно