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

99 -¿»7/^ Г л

* ; ^ / -7 О п

КАЗАНСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ И ОРДЕНА ДРУЖБЫ НАРОДОВ АВИАЦИОННЫЙ ИНСТИТУТ имени А. Н. ТУПОЛЕВА

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

НУРУТДИНОВ ШАМИЛЬ РАЛШЛОВИЧ

УДК 681. 32

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

Специальность 05. 13. 05 —Элементы и устройства вычислительной техники и систем управления

Автореферат, диссертации на соискание ученой стелепи кандидата технических наук

КАЗАНЬ—19€2

- V 1*.

О.

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

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

доктор технических нзук, профессор Р. Г. БУХАРАЕВ

Официальные оппоненты: члсн-корреспондент АН Татарстана,

доктор технических наук, профессор В. А. ПЕСОШИН

кандидат технических наук, с. п. с. Н. С. КИСИЛЕВ

Ведущая организация: Казанский научно-исследовательский

институт радиоэлектроники

Защита диссертации состоится „ ^ " 1992 г.

в ^ час. мпн. на заседании специализированного совета

К С63. 43. 05 при Казанском авиационном институте по адресу: 420111, Казань, ул. К. Маркса, 10, зал заседаний.

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

Автореферат разослан „ " 1992 г.

Учений, секретарь специализированного сэзгта, кандидат, технических наук, дои,екгл

и

в. А. КОЗЛОВ

ООЩАЯ ХАРАКТЕРИСТИКА РА О 01Ы Дзету адыюсть проблемы. Рефорируомая робота поспяамн;! оадачо синтеза однородных цифровых устройств о локл^глпдм.т связями, состоящими из набора малого числя типовых злочиитп!?, выполняемых преобразования вал п-моршмл двоичными нгжторау.;! с использованном аппарата тэории полей Голуя, ¡еп'орио широко применяются да] рошэния шюпк зада'! вичислитмльной тнхгппш, связи и автоматического управления: построения синхрошкгнру.'ицих устройств, очетчжов, кодирования я декодирования сообщений, обнаружения и исправления оишбок при передача сообщений, построояия тестовых наборов, пшоряцин послэдопя'хольиостэй псевдослучайных чисел, сжатия после доват-олыгастей наборов. Для микросхем высокого уровня интеграции (ВМС и СБИС) болклоз значение приобретают морфологические свойства реализуемых схем, их топология. Вэяпш глогут оказаться регулярность структуры, повторяемость ее элементов и связей, минимальность длин соединений и т.п. Указанный причини розко снижают полэзпость ?*инлмизации пэршелшотвльянх функций б традиционном смысла. Последние разработки в области проектирования высоко производительных цифровых схем на основе СБИС-технологии полностью подтаерздзш' это положение. В этой связи вызывают ииторес исследования в области теории полэй Галуо, в результата которых синтезируются одиоредшю вычислительные структур«, производило потоковые прообразовать над п-моршми двоичными векторами. Необходимость реализации вычислений в полях Гэлуа или коночных полях возникла в связи с развитием теории кодирования. Традиционным являотся использование типовых вычис лит&лышх операций в коночных полях для декодирования 74одов БЧХ и Рада-Соломона, вычисления цифровой свертки или дискретного преобразования Фурье. Одним из перспективных направл0!гай является созделшз специализированных устройств в пидо СБИС, которкэ могут рэзлизовытть таловые вычислительные опврзцли в конечных полях. Однако готоды синтеза таких устройств недостаточно изучен«, так как имеются трудности при представлении конечных автоматов однородными вычислитолышул структурами, вшошишцими преобразования над элементами жвачного поля. В этой связи представляется актуальная

выполнение настоящего исследования, в котором изучается возможность и эффективность синтеза однородных вычислительных структур в подо Гвлуа. Такой подход позволяет во многих случаях получать управляете "преобразователи п-троих сигналов, для которых может бить легко использована СБИС технология.

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

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

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

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

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

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

Научная новизна:

- показана непосредственная связь между . векторным' и матричным представлением элементов коночного поля;

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

- исследованы условия представления любого отображения г пола Галуэ в вадэ многочлена от ц- переменных, И . .■ получвкь формулы, с помощь» которых можно вычислить коэффициенты тают многочленов;

разработан подход, тзволязаций жяюльзовап преобразоватаяа над элементами конечного поля ■ для синтез;

п

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

Практическая ценность работа. Работа выполнена и соответствии с планом научно-исследовательских работ кафедры прикладной математики Казанского государственного ушнюрситета, а так:ш в соответствии с комплексной программной по проблеме 1.12.8 "Измерительные процесс» и системы", раздел 1.13.8.3 "Теория я метода построения измерительных информационных систем", тома "Автомвтязироиашшо спитом; проектировании, контроля и диагностики мшсропроцоссорной тохники", Г'Р :01860022457.

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

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

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

- вывод о существовании связи между векторгшм и матричным представлениями элементов конечного ноли;

п

и

- способ "ычислымя коэффициентов многочлена, реализующего-оуображыша коночного''поля в сабя;

- шшд о возмокноета реализации конечного автомата однородной свтъю над егс2">; алгоритм рзалиэадии конечного ' автомата однородной с&тьа над орс2т'э; катод проектирования однородных схем по олисашго конечного автомата;

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

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

- сшсгб 'юстирования цифровых схы>? баз установка в нпчалыюв состоят?'.

/шробацил работ. Материалы диссертации докладывались на итоговых исучннх. кш форшщмях Казанского государственного университета (1Э8В-19Э0), конференциях молодах ученых я специалистов факультета ВПК Казанского государственного университета (1085-198в), ян Всосошной конференции по теоретической кибернетика, Горький,1988, Вес сошной научно--тгттоской конференции "Повышешв' качества и надежности продукции. программного обэсаочадаа ЭВМ и т&хничэсзди срадотв обучения", КуЙ«5ишов,1989, на со мшарах: в Каовнском гос. унив&рситето, Московском гос. у!шв&рситате. Казанском авиационном институто, институте проблем управления АН СССР г.Москва, института проблем информации АН СС-ЛР г.Казань. Работы, вошодшо основу диссертации, вместе с работами Столона Е.Л. и Латипова Р.Х. участвовала в конкурса научинх раОот Казанского гос. университета 19ЙЭ г. (д;шлс?л за трэтьв место), а также во всесоюзном конкурсе научных работ 1990 г. Результаты, полученнио диссертантом, использовались при реализации работ в соотвзтствии с можвузовс.кой деловой научно-технической прохраимой "КНП-2000" по томам:

04.20 "Разработка катодов пос^юения откаэоуотойчивш.

цифровых устройств"; ОБ.48 "Разработка методов построения систем встроенного контроля".

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

Структура и объем работа. Диссертационная работа с приложением изложэпа на 138 страшщзх машинописного текста и состоит из введения, четырех глав, заключения, приложения и списка литературы (G9 наимэиолшшгй); работа содержит 31 рисунок.

СОДЕРЖАНКЕ PA60TU

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

В первой главе вводятся основные понятия, и определения, связанные с темой исследования, ■ проектируется устройство умюгкенпя п конечном поло и синтезируются однородные с/а;"), рзализукцш вычисление значений многочленов над копачним полем.

Многочленом с относительно х> над полем f=gfc?,) называется выражение гсх>=о<о * +- ... + о^х" , где коэффициенты <*А принадлежат полю f. рассмотрим шохество всех многочленов относительно ç над полем f=gfî25, где операнда сложения и умножения^ определены по модула неприводимого многочлена mcçs. Т.е. . acç>=bcç3 в том и только в tdm случав, когда многочлен acçj-bcçj делится па многочлен тсо без остатка. Множество таких многочленов является полем, а многочлен тир называется ыэдулярным многочленом поля. Если степень равна п , то

построенное поле состоит из 2" многочленов, степени которых не превышают п-1, называется полам Галуэ порядка ?/' и

обозначается ofîP/'i .

Имеются различные способы представления элементов поля егсОсновным является описанный ранее способ прадставлешм злэнантов ноля <;кс2"> в виде многочленов но модулю неприводимого многочлена mCxî над gfc2>, степень которого равна л. Обычно вместо многочлена хранят только его коэффициенты , з рейультате чего любой элемент поля GFt2n> мозют быть задан в

1 .4. г» X . Пусть

Г о 0 ... 0 а

I 0 ... 0 а

0 I ... 0 о

. 0 0 I а

над» ч ■■ мерного вектора о элокэнташ! из егс25. Другой способ :¡шичп/,атая и щюдагашюит всех ненулевых элементов поля от.) пенями некоторого алементо с, называемого примитивным алпминтс.м ислн с.гс2п>. Следу щий способ представления элементов конечного поля 6рс2г,з осуществляется при помощи матриц. Для ат'НЧ) выбурим произвольный примитивный многочлен >аСх>= «о + «(х

( . . . Ч в

'"* П П . . Л о

и 1

г

г>- 1

его еопрсшоздащзя матрица. Степени этой матрицы а, а% ... ,

а2 ' будут различными и вместе с нулевой матрицей образуют ноле, изоморфное пол» егс2"э.

Леша 1.1 Пусть <. о, 1, а, к2, ... , а2 ~2 > - пола г , элементы которого имиот .матрачноа представление, где а -сопровождающая матрица многочлена »пСм>, тогда вектор с ри, р1 , .,.' , р _ >, соответотвуяэдий элементу с1 поля г равен первому столбцу матрицы .а1 и матричном представлении ноля г, о < х < 2п-2.

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

Теореиа 1.1 Пусть элемента поля ерс2г,э представлены в видо 38кто|юп, соответствующих многочленам по модулю примитивного многочлена п>сх> над е(Ч2:>. степени и. Тогда для любых

«•р=ап1рт+а ... +э

О 4 Г»- I

ГДе а=Сао,а4,... ,а(ч_1>, Ь^^ , . , . »Ь_4 ) - 2ЛВМ0НТЫ ПОЛЯ

егс2г'5, а - сопровоздзщня матрица мяохтлвна тсх>.

Следствие. Операция умнсшения двух произвольных элементов' поля ерс2п> мояют быть реализована однородной ном&шащошой схемой, состоящпй из одао'гкппых цифровых блоков. Для реализации схемы требуется не болев г»2си-1> сумматоров по модулю два, к2 элементов И, а вромя умножения двух произвольных элементов поля егс2п> не больше од2»1+1.

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

.два. Наибольший вшггрыш получается, когда существует приштшяшй многочлен - вид') и-х(-х". Тогда требуется о.- 1)г сумматоров по модулю два.

•Исследована всзтжнэоть реализация любого отображении, заданного лад элвкентами шли, многочленом от одно:* или лзсколысих порайонных. Показано, как вычислить козМицие.мп многочлена по заданному отображатго е>. Для этох'о внедиш* сл&дуздие обозначении. Пусть у - матрица псрядла И пуг.тч знак * означаот, что соответствуиций индекс избегает игл, значения от верхней до нижней грашщи. Гели при записи алиме.чтн матрицы заменить нвкоторнй индекс зннком в остнлытн индексы зафиксировать, то получим вектор из племантов исходной матриц». Назовем этот вектор сочаниом.

Теороиа 1.2. Пусть е-ерс2г':>. Если е - произвольная Функция от а пврвмэншх, отобракпщая в3 в б , то иогкМиционти многочлена г, реализующего эту функции, могут бить вычислены с помощью системы

' .....^».^»¿Гг.....1в = о.г

.*,2>с11,»,...,1в>=с1 у' .........^¿г;

у * " с14 , . . . ( ,*>-С~* УС * - 1 1 о ^ , . . . , 1 в 4 ,#> , --оТ,.....! ^ ( о. ,

где у - матрица порядка 5 из значений Функции р иг, .элементах поля о:

уо,о.....о-г«0.0,...,0>;

* »•••• 1 -1 I -1. А

1 1 * •* .....С е >.

С-приштивный элемент поля в, .,1 =».»-, г-?/' I. Матрица

с"1 нож»т быть один раз вычислена для ко}1крэтного п. Матрица

а=|а. . I — содержит значения коэффициентов

Л Л1* ,2'**» в'. ■ »• г'"* •

многочлэна.

Следствие'. При 5=2 коэффициенты многочлена вычисляется но формула: •

а=с"1усс"* jt,

где у - матрица, содержащая значения функции * на алиментах поля о.

При э=2 коБффяцкбНты многочлена вычисляются по формуле:

где у -- матрица, содержащая зяьченая функция р на элементах поля е. ■

Прьдлозан способ реализации вычислений значений многочленов в бгс2г'5. Покав-ано, как могут быть вычислены бньчонля многочленов в точках ег(2"'> при пошщн параллельной алл последовательной вычислительной структуры.

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

Работу цифрового устройства мэзаю описать с помощь» конечного автомата (х, х), гдэ х и V - входной и выходной

алфавиты, О - млозшство состояний, а - фу}пщия переходов, в л -функция выходов. Под однородной сетьэ будем понимать сеть автоматов - (х^ »х^ >, 1=»Тй, обмен информацией мэзду

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

й . Часть входов и выходов автоматов га., 1=1 Г«

являются входами и выходами сети. Пусть к - входной алфавит и V - выходной алфавит сети, функционирование сети описывает

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

Предложен способ реализации комбинационной схемы при помощи многочлена от одной переданной над орс2п). Пусть автомат к является комбинационной схемой. Эта схема определяется отображением х: х -> у. Пусть п наименьшее из натуральных чисел, для которых выполнены неравенства 2т'г(х|, 2">}у[ . Пусть о=огс2г,5. Закодируем элементы мяожэств х и у элэм&нташ поля е. Будем считать, что отображение х определено на подмножестве

о со значениями в е. Зададим отображение х с помощью многочлена от одной пэр&машгсй над ползи о:

I -. о 1

Такой многочлен моашо построить с помощьи теоремы 1.2. Таким образом построен автомат, модвлируиций исходный автомат 5)1. На основе результатов I главы получена реализация исходной комбинационной схемы в виде однородной вычислительной сети. Рассмотрен способ .реализации комбинационной схемы при псмоцл многочлена от нескольких церемонных пад полем

Далео исслодован случай роализацил автомата с памятью. Ограничимся случай-! автомата без выходов. Такой автомат описывается тройкой (х,о,з). Выберем яаимэньшео так чтобы выполнялись неравенства ?/'>|х{, 2г';-\а \. Элементы шюжоств х и о закодируем элементами поля о=оксЯГ|>. Получим, что отображение а(х,ч) определено на подмножества е*<з со значениями о е. Представим его в виде многочлена

Л(*»ч)- У а х'ч1, г=2Г'-1,

~1 * 1 *

V . ) =0

Тогда автомат шхот быть реализован параллельной

схемой. Кэаднй пз блоков П. . в схема вычисляет произведение } 1 -

а. <Т -

Исследована возможность минимизации количества элементов сети,- реализующей автомат с памятью. Задача минимизации количества процессорный элементов, требуемых для реализация конечного автомата, в общем случае является к?*-полней задачей. Позточу рассматривается некоторая схема реализации конечного автомата с паыятьв, которая позволяет в определенной мере решить зту задачу. Пусть (х,<1,г) - автомат без выходов, определений хз поле Галуа , где х-ег (2'")---«. - множество входных сигналов, о«-ег(2к)=г • - множество состояний, отображению г:с<гчк, ллн где хео, чс=г. Отображение а моено

представить в вида многочлена от двух переменных над полем

СР (?/'), ГД9

о

«(м)--[ х,ч,а. .еек(2") (I)

I , ) - о

При реализации многочлена однородной последовательной или пзрзллелыюй схемой потребуется «•* блоков, г.-=2"-1. То же самое отноконив « может быть представлено в виде многочлена от одной нерйМ'Лпюй. Для этого отобрсясашю ь определим как отображение ь% ;GK(гf')ч<зF(2,'), г=«и-к. Или е-(*)=-', г,2-'еог(2''}, при атом Представим отобрэж&ниэ в- в виде многочлена

от одной переменной:

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

1г}юизв0лыш8 енг:ч85шя. поэтому отображбюш 5 можно постввить в соответствие на одно птображэяме в*, а семейство д отображаний вида г•:

л: (х,ч)т+(х' .сз- )т , где хеХ, ч,ч'«0 а Ух'ебГ(2г"). Семейство содержит 2'" отображений вида а •, по одному для каздого значения . В множество л можно выделать отображение, для которого многочлен (2) имеет минимальную степень. Построена формальней система, позволяющая сделать это за конечное число шагов.

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

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

(2).

Предяокш процесс проектировании однородной вычислительной структуры на 'примере однородшга последовательной и параллельной структур, реэлизувдих коночный автомат. ПосцюьгШ типовые элемента, ¡гз которых состоят синтезируемые однородные структуры.

Синтезирована последовательна!» вычислительная структур.:. Она состоит из одинаковых блоков (процессорных элементов), выполняющее следующие операции:

где все операции выполняются над полем «г(2"). Предложена функциональная схема процессорного элемента.

Синтезирована параллельная вычислительная структура. Основу тзкой структуры составляет процессорные элементы, вычисляющие выражение а х' у', а. х ,у<=ОР(2'). Для вычисления выражения э-к'-у' построен автомат 5п=(х,о,в) над вг(2г'), где х - входной алфавит, о - множество состояний, г - функция перехода в новое состояние, причем ч, кех, чео.

Автомат т реализован схемой, отличащейся от схемы, выполняющей операция умножения в поле ег 12г') тем, что в линию обратной связи включен п-разрядный регистр Рг, предназначенный для хранения внутреннего состояния автомата т. Добавим. что построенный автомат ж гюзволяьт вычислить выражение вида

а-* 1-к23-...-*к , а,х1,х2,...,х1(е<3р(2г') ЗЭВрЭМЯ 1 г +12+. . .+1 к .

Предложены алгоритмы синтеза последовательных и парэлл&лышх вычислительных структур по описанию конечного автомата. Как пример разработки представлен управляемый гешратор случайных кодов. Задача синтеза генератора случайности является задачей синтеза некоторого детерминированного преобразователя исходного случайного процпоса или случайного кода в требуемый случайный код. Такой преобразователь построен на основе представления коночного автомата боз пьмяти однородной вычислительной структурой с управляющими входами. Значв;тя управляющих входов определяют :со1Лфетшо преобразования исходного случайного кода в

( к » I )

I к >

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

1 х ... * t i

х: f~i ¡г тт: • 1 <\=г ■

il -

ПуСЛ'Ь Pt=—-, ГДЭ .г\ - Ц8ЛЫ8, И пусть Г>=та.ч п.. Пр8ДСТ8В1Ш

2 ' '

таблицу в виде отображения поля gf<2"> на себя. Для этого закодируем значения переменной « зл&мзнтами поля о=игс2г'э. Затем построил! отображение подмножеств поля s на его элементы»

n-r».

Мощность подмяозшств е. определим из условий [g. j=h.-2 \

1-m. Ввиду универсальности синтезируемой однородной структуры

распределение .адамантов шля s- по лоданозшстааи ____,et

производится произвольным обрезом. Полученное отображение, которое задано вей даоет значения в е, представлено в виде многочлене от одной переменной пад о. Вычисление знзчэняя многочлена в точках е реализовано, однородной последовательной вычкелитзлъной структурой. Она состоит из 2" одинаковых блоков. Исследована воэноиюсть умзньюэяия показателя поля -Гадуs, в котором производятся преобразования. 'СШГТвЗНрСВЗН многоканальный гозэрятор случайной величины » являвшейся ■ композицией независимых случайная вадагаяи.'--Пусть ' п=?,», тогда

1 -мерную дискрзтную случайную величину х можно представить в вида х=х1+хг2,п, где ^ ,х2 - т-мэрнне случайные езлгшш. Пуста и хг - независимые даокретянв случайные, величины. Зная матрицу распределения системы двух дискретных-олучайныхвеличия (х х ). можао найти закон 'распрэдэлэняя отдельных'.- случайных величия * и -<г, входяадп в слстсму. йсходя- из этого прэдаокэя алгоритм синтеза однородной вачислитаяькоЯ . структуры,.-являвшейся гояэрртором дтекрэтаой случайной . вбл-гшиа. -, пр&дстявлешюй в вздо композиции. двух независимых дискретных спу-айлнх вэлимш • х и к •. Идеи, лолежэшаш в основу оинтзза '

2-х канального генератора, использованы при проектировании

Г о

Л .J

f-кабального генератора, f>2.' Предложен алгоритм синтеза гьнорвтора случайной величины, являющейся композицией зависимых случайных величин. Пусть п=2>п и п-мерная дискретная случайная валичша х представлена в вида х=х +* х^ и *2 - т-мерныа дискретные случайные величины. Если случяйша величины, •образующий систему зависимы, то дач восстановления

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

В четвертой главе рассматриваются схемы пстроошюго контроля и метода, позволяйте повысить отказоустойчивость проекта руегагх однородных цифровых схем. Лредложоьы схемы генераторов тестовых последовательностей, а также схэмы для снятия выходной последовательности диагностируемых устройств (ДУ). Рассмотрен случай контроля цифровых схим с-памятью,которую нельзя установить я начальное состоят«».

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

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

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

г■}

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

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

Ь нрилсшпши приведены сведения о внедрении результатов исследования.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И вывода РАБОТЫ

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

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

2. Иредлоашн и обоснован способ умножения двух произвольных элементов конечного поля, позволяющий при схемной реализации использовать однотипные элементы „ и получать однородные схемы с локальными; связями. На основа подученных теоретических результатов разработана цифровая схема из однотипных элементов с однородными связями для умножения двух произвольных элементов ноля огс2г'з (з.с. 1672438).

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

4. Исследован случай, при котором возможна минимизация количества элементов однородной сети, реализующей конечный

Х4

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

5. Предложены схемы встроенного тестирования ци^ювых схем, учитывающие структуру диаграмм; состояний, и также схем с памятью, которые нельзя установить в начальное состояние (л.с. 1302285, I39792Q, пол.реи. по заявке #4804827/24(12542) и по заявке Ä4661293/24(035080)).

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

Основное содержание диссертации изложено в работах:

I- Нурутдопов Ш.Р. Исследование инвариант автономного генераторов,!отвриалн 5 пэучн.конф. мол. ученых фак.вичксл. матом, и киборнет.Казан.ун-та,Казань,17 июня ХЗвб^Казан-ун-т. Казань,1935.-Дэп.в ВИНИТИ 1986.J592-B36.

2. A.c. 1302285. Устройство для контроля цифровых блоков. •"Латыпов Р.Х.,Мэнсуров P.M..Нурутдипов Ш.Р.,Столов Е.Л. Опубл. в В.И. 1987.Я 13.

3. Нурутдаяов Ш.Р. Сигнатурный анализатор с нелинейными обратными связями" Некоторые проблемы вычислительной математики, математической физики и программного обеспечения. -Ц. :Изд-во [ЛГУ,1968.0.82-83.

4. Нуругдшюв Ш.Р. Реализация комбинационной схемы при помощи многочлена от нескольких параманных над конечным полем/^Тезясы докладов vin Есесоазпой конференции по теоретической кибернетика. Горький, 1988. Часть Я.С.61-62.

5.. Лэтшов Р.Х.,Нурутдинов Ш.Р.,Столов Е.Л.,Фараджев Р.Г. Применений теории линейных последоватвльностных машин в системах даагностирсватая^АиТ. I9S8.J£8 .С.3-27.

6. A.c. ,1397920. Устройство, для встроенного контроля цифровых блоков. / Баранов A.IL,Комаров Ю.С.,Латыпов Р.Х.,Нурутдинов Ш.Р..Столов Е.Л. - Опубл. в Б.И. 1988.

7. Нурутдинов IL'.Р. .Столов Е.Л. Реализация автомата асинхронной сатьв^^Киборнэтака,Кизв,198В,М.О.108-109.

О. Нурутдинов ¡"-Р. Контролзпригодный ушюжитоль в поло ti'i?/' //^-Тезисы . докладов Всесоюзной научно-технической

кол^йрвшуш "поиижшиэ кзч8ствэ 0 нздэшюсти продукции,

программного обеспечения ЭВМ и технических средств обучения"» КуабышЕш.поллтех.гаьт.Куйбн.зов, 1939.С. 181-183.

Р. Нурутдинов Iii.Р. Обеспечение» отказоустойчивости сетевой модели бьтомвтв" Исследования по прикладной математика. Eijii.iSIG. :Изд-во Казан.ун-та ,1563.0.138-144. ^ 10. i.e. Ifi?243ö. Устройство для умножения двух элементов коночного поля GF(2n)/ Нуругданэв Iii.Р.,Столов Е.Л. - Опубл. в Ь.И, 1991, J63I.

.' II. Латшгов Р.Х. ,Н.урутдишн Ш.Р.,Столов Е.Л. Устройство для контроля двоичных последовательностей. Положительное ротанге о выдаче A.c. .V32-04--II9 от 7.02.SC по заявке 4304827/-24 (12542).

12. Латипов Р.Х..Нурутдинов Iii.Р.,Столов Е.Л. Устройство для контроля логических блоков. Положительное решзнио о выдаче A.c. .422-04/42 от 21.03.90 по заявке» J5466I2KV24 (035080).

■О-

; .. Подписано к печати ЮЛУ.92. Тир.юо' : ... зак.ш-s;

Лаборатория офсетной пе^атк Казанского гсспединсп.-ута 1С 420015, г.Казань, уп.ПуппияаД.