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

/

ч

ГРУЗИНСКИЙ ТШШСКИЯ УНИВЕРСИТЕТ

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

ХАИКЕЗИЧ Впльли Харвтоношп

УЖ 601.327.0

ТВОРИ »ПБСКИВ ОСНОВЫ ПОСТРОЕНИЯ 1ШЯ0ИИХ Ш103Ш0ШШ ТИСЛОВУХ ПРЕДСТАВЛЕНИЙ ллл СИНТЕЗА ШСОШ1РОЮВОШШЫШ УСТРОЙСТВ И СТРУКТУР РАСПРЕДЕЛЕННЫХ АСУ

Споштгигышсть 03.13,0" - Эледапти я ус?рсЯот 5!ГО!статолькоЯ гохнша п спстпи упрагшзши

Споцяальнооть 03.13.00 - Авто'^атяяирОЕатшз спатокц уиргшогтя

Автореферат

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

Тбалясн-1992

Работе шшолиеио в Ииотятуте вичгодитвльноА иатеш тика ш, И.Н.Ыуохелишилк Акадешш ааук Республики Груза;,

Офациалыше оппоненты: окадеиак АН Кчявхстааа,

доктор Т0хшиеоквг наук, профоооор Ашрбслй В.и. доктор тезшичеоши иаук, профессор Чховдс а 11.В. доктор тохиическшс наук Каяздадов К.Г.

Водущая оргаииэавдя; ВоеросцДский нвучно-пооладодатодь-

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

Федерации

Защита иооюитоа " 26 " дона 1992 г. о 14 часов на заседает специализированного оовота Д057.01.03 ори Гру-аинсисы технической уимвероатото

Адроо! 380075, Тбюшоа, уд. Костава, 77.

(< даоовртациеЛ ыожио ознакомиться в библиотеке инотл-гуг.1

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

Учения секретарь оцецвализаро-ваниого совета ДО57.01.03

ОЦЩ ХАТ АКТ; КОТИКА РАБОТЫ

Д^уальнооть. Специфика поотроения распределенных АО/ а тенденция юс развития обуолоыываыт наобходимооть иоило-дов&нкй, нрправлошшх на расширение вцбора конфигурации технических оредотв и (¿а то до а для реализации подобных АСУ о условиях возроотания удольного веса ¡истакдартних задач, овяэашшх, как правило, о болышш объемом вычислены и но— вдшошшии требованиями к доотовернооти информации. Ооновиы-ИЗ 001 оцтами цриложения таких иооледовании яаляются:

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

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

- метрологические пэдоиотемн распределенных АСУ, бази-руиднеоя на раосредоточонлих инфоршщионно-изыоритэльиых оиотемах (1ШС){

Веоьма удобным инструментом решзиня этих проблем, оао-бонно в чаоти наховдония формальных алгоритмов дэкомлознции информации, синтеза табличных уотроДотв высокой производительности и повышения достонорноотк данных, является теория цопозицюшшх числовых представлений и оо технические прыло-гения. Корректируьдие огзоЮтва непозиционных чиолових иред-отавленш! били. уопоошо приупнени доя оптимизации подсиотем обмо.л данными распределенных АО/ ,в частности, для поотроеиия йотом сквозного контроля информации. Однако более ыирокое приюнчниэ теории нехизнциэнных чи.злов!а прод-оташши! для оптимизации перечиоленшас вила нодииотом распределенных А';У о вязано о ролюниом обдас задач нахождения т.н. "пультшлшштииш хпгакгериотшс" шэпознццошшх оиотеи а формирования ооответствуищеИ отруктури ^пплов непознциоино кодированной информация.

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

держащих в явной виде информацию о числе в целом. Поэтому одну из основных задач иепозициоиного кодирования составляет иокуоотвенное введение таких характеристик для нопози-циошшх представлений чисел. Вычисления мультипликативных (позиционных) характеристик кодовых ахов являются оамым оуце-отвенным звеном алгоритмов Вилолкения немодулъных оперший к основным« операциями (кроме модульных) в иатзадиошшх оиотемах. К ним сводятся лгхЗц.э другие ыемодулыше операции к от времени, затрачиваемого на выполнение этих вычислений, в методики их выполнения, в конечном счете, зависит производительность, надояшость и метрологическое оОеопеченне оо-ответотвувдих устройств в конфигураций технических, средств АСУ. Известные алгоритмы вычисления позиционных характерио-ткк кодовых слов не всегда отвечают требованиям, предъявившем к набору технических средств при конструирования распределенных АСУ. Некоторые методы определения позиционных характерно тик треОуют значительных временных я аппаратурных затрат, хранения в памяти большого числа параметров. Другие - связанные о алътерцатишшми соотношении:', допускают существование -8 числовом диапазоне областей неопределенности I требувт оривлечэнжя для ее раскрытия дополнительно«! информации.

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

Опвцягжхя декомпозиции информация я высокие требования к доото'зерности в подсистемах обмена данными оооромсаных распредолеиных АСУ определяет актуальность исследований направленных на построе:ше избыточных непозициошшх числовых представлений для расширен«* алгоритмических возможностей в выбора конфигураций технические средств подэоных информационных оиотем.

.:е.ть залоги ооогэит в раз;>*2зтке теоретических однов

построения избыточных нвпозиционных числовых представлений дет расширения выбора конфигураций технических средств, методов докоиаозшда а высокопроизводительных матричных устройств оптииианрувдих подаиотеш* обиена денными, а г шиш 1 этрологичеокнз и вычислительные подоиотеш распределенных АСУ.

Йохозд из поставленной цели в дисаертацнонной работе реваптоя олодушнв ооиовныз задачи:

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

' - разработка теоретических оонов а методов введения всбыточяоотя в цопозиционные числовые предотавлешш для формирования в АСУ фаАлов о заданными алгоритмическими свойствами;

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

■ заддатных преобразований над изоыточншш нвпоэициоцнцыа чно-довыцд представлениями s

- введение опоциалышх поевдодвоичных а поовдонопози-циошшх числовых продотавленнЛ для обеспечения оквозного контроля достоверности данных в распределенных АСУ;

- разработка методов обеспечения бозопаоностн нопози-цкошю кодированных дшишх при эксплуатации распределенных АСУ;

- построение методики использования введенной избыточности для повышения эффективности декомпозиции при обработке п транспортировке информации в АСУ.

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

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

Б рамках проведении.. исследования боли впервые разработаны;

- притуши построения непозиционных шолоаах предо i а; -

ленш! о модульным заданием интегральных О/улыипликатавных) характеристик кода;

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

-теория мил ¡-Оазисного моделирования Оазисных представлений аппозиционных систем;

- специальные непозкцаошше представления информации цля метрологических подметем распределенных АСУ,

Мотоды и алгоритмы построения специальных поевдодвоич-ных и псовдояопозгашонных числовых представлений для сбеспе-чоккя доотоворносгя дяш:ых в распределенных АСУ.

йнодроич9 и практическая понноогь полученных результатов. Основн'Л научные результаты доведены до решений на уровне практических алгоритмов, предназначенных для использования прп пэотроеннк устройств и процедур обработки информации и проектировании распределенных АСУ. Технические аспекты внедрения, вытекающие из разработанных теоретических положений, наядк отражение в разработках ШЭ ЭЛМ, ьТГ "Новин-теко", в 4-х защищенных под научным руководством автора кандидатских диссертациях и одной, готовящееся к защите.

Апробация работы. Эсневные положения диссертация докладывались и оосуглались на П + ХУГ Всесоюзных школах-семинарах пс ьучг.сдителышы евтяч!, 1 Бсесошной конференции по теории кодирования и передачи ин^эрмации, IX и X Всесоюзно« окмпоакуме со проблема избыто шостя в информационных систэ-ках, Всасосзных и Международной конференциях по высокопроизводительные г отелам, ирсхэдивзюс г Тбилиси, Мозкве, Таллине, Алма-Ате, Ш и У1 '¿ездународных симпозиумах по теории информации, на других конференциях к семинарах.

Публик:шд. По теме диссертации опубликованы свшв ЕО печатных работ (в той числе Э Езооретенка) а выполнено S научно-исследовательских отчетов.

Структура ж объем райзты. *1пссертацдон.1ая работа ооото-кт из введения, сомх глав, зашиленкя, списка литературы и Прилохонк»;. Подоргляяе работы изложено на страницах иа-аююпконого текста. Ьаблиэграфия - 141 название.

ОСНОВНОЕ СОДЕРНАНИЕ РАБОТУ

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

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

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

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

Л - а„ л.,, а, (I)

подразумевают, по-оущоотву, операции над соотватствуодшш полиномами вида

' Да)-д" с,, - ♦ Л, (2)

п точко ч'.'р (р - ооноаышо системы сшслания) так и операции над нэпозициошюа кодовой поолодоаатолыюотмо

Л^М.....х.

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

• 'Л 2 и)

называемого базисным представлением чиола Л/ . Здооь кон-отанты . , - базисные числа, Ъ - диапазон пред-

ставления числа в данноя непозицизнноЛ системе очисления. Величина Кн , некоторых случаях называемая "рангом" числа N предотавляет ообо£ коэффициент увязки иазду представлениями (2) и (4} с явлшэтея своеобразным эквивалентом отсутствующих в (3) иаЕПОзицгоцннх связей. (В дальнейшей под коэффициентом увязки будем понимать именно ранг члола

всегда, когда члены последовательности (3) представляют собой наименьшие неотрицательные вычеты по соотвототвуо-Оем основаниям).

То обстоятельство, что г.овффяцЕонт К не яв-лется членом кодовой последовательности (3), отражает основные трудности, вознихаодпо при построении алгоритмов непозкцвоп-соЛ мгшашоа арифметики. Поэтому вахноэ 8качание смеет разработка алгоритмов определения рааллчнше модяфнкаща <ЛН штанам последовательности (3) а мюшизадга вто4 вел пины.

Во втором параграфе расокатривавтся разработанные кото ды построения ряда мэдоЛикацеЛ базкенях представления не-поахцжонных систем.

Пуоть чкола последовательности (3) суть нагмгньако ноэтрпцат дыше вычеты соответственно яо *сг.сарованннм по-парн? взаимно простым основаниям

Р >Р' (5)

Тогда последовательность (3) определяет класс по модулю Ч' 1' с, совзидясаи! со значениями лкнаинэ* функции

щ>а цмцх аначешиа аргумента I . Кодируемое число

А~Ы<0) Пуоть теперь

В^ (7)

Тогда, осла В4 то имеем очо-

ЕДДНО

Я. а -й. а I,«. <8)

При (7) а базисной представление (4) отрана-

ог сзсоотниЗ опоооб решения о йоте «и орлвноши

//а*. {(-1,1,...^) (9)

вытокаадиЛ из т.н. "китайкой теорвш об остатках" и приив-пяэиой р ооогвототвущнх раз налах теории чисел. Однако д ля 700рпн непозиционного кодирования специфическое значении приобретает нахоядонле различии* опсообэв определения иохо-иоа функции (6) непосредственно в точка 1*0 , или по крайней иэри, вычиоленио для кодируемого числа величшш по чденаы послаловательноотя (3). Поэтоцу поя11ляч,.,он цеоб-

ходимость более подробного рассмотрения алгоритмов решения оистеи сравнений по попарно взаишо простым ыодуляа с соответствующих им базисных представление вепозищшных оаогон. Если имеют иеото (7) и (8), то

У/-В, А.*в,(W)

отнооитоя к классу по модуля 1) « cobi адавдоыу со вяачониягш (6), 1.0.

(II)

A^e.^slii.rt.-adi (™JF.)'(i*1,2,..., г) (12)

Упоилнуткг выше чаемый случай "оргонорчировашшй" би-висиоа систеки, когда в (7) kt~î (i*t,2,...,n) соогвогсг-вуот известней нопоовдноииоН системе. счисления s осгототшю: классах (СОК), Обкоо количество подобиях напогнцношш- чго-теи счис-ения и соотлстсгзувадх uu HopioroHaii!i'JXR6£DHCiiHS Светой гида (7) для фиксированной системы осиосал;-;-! {,5},очо~ видно, определяема не фрикции 3Клера ш; f (M* fi, «

Различные базисные представления одного к того ко числа ногу? совпадав со вначеихшки линейной фушщла '$) а размет точках, с,, слодосатольно, для них uoryi инахь kccïo рааличико виачоиг.н коа$фаааеаха Уы . Прс зюа шиакя грзекца иигерге» ла кзаеиоккй цолочйслонпого аргумента. i одипаг.оаа для secs ортогональны: баокоиих сиотеа с сслогзгоаь&иыг йааиоикиа числами к равна дуле, а горгнеа границу, которая ыодот баи. разявчиоД для различных базкегшх састсы, содас! слодувцэо Продлокеаие. Цусгь базисная сия.теиа шсст екд

В*,* (I-,0,0'-.0)

В..**-,".. о.--. - - - -.....-------- {13)

Тогда r»ax Iс - верхняя граница язиоеовжЗ цолочиолое-

еого аргумента в (б) задастся вырахеяяим

«

где: - коэфф*цаонт увязка, л т.н."нориахьвои инверсной

првдотамеами'ЧШШ) некоторого чпода шаеввдго а базисной омшио лад

¿ак показано а рабою, для теории поогроения нопозици-о^ца чиол^аах иредсталленай специфической значение приобретав* цо аолрооц руцеолоаапия ропюния сиотеи сравнений, а цахоадоааа различай» модификаций хаши решений, соотао^стау-вщис различный иди с сан базисных предотылоний и построенный иа IX оиноав иепозициошши оистви&и счисления о залчинииц овоПо.аааи. Такой подход позволил аначимльно распирать кяаоо иецозицяйшшх еиотаи прадот&аленца ииформции и, наряду о этии ввести новый клаосы позлцьоашх систеи. НаЙдоцц ио-дификациа реваиия оистеи сразк$а;-;й первой степени, основанный на лриыен«лШ1 орхогонадьиых, но ив ортоноииировыпшх Оа-аиоаых чисел. ¿льдвно понятие "клана" нилозкционного пред-. отадленая шфорыациь (рассиотренаая в качество базового примера азасотнаа окстыа счисления а осхиточных класоах(СОК) падаете., одной иа кодификаций (но иячу Я-1) в широкой клао-се ьеиоа&циоканх оистей аредог&вдоаьа аафориации, цааваниых "одвйреныии лрадох&лданинии'Ч'Ш}).Найдены неповицдошшп сио-теиц представления аафориацци по другии клнчаи, обладааэда рядоа ирй'лиуаюохл отноои£«ш)но онотеыи очко/еиия а остаточных классах. 'Гаковыии, а частности» яалпзтол гак нииициьиов "нормальное шиерсно^ приотавдение'ЧНШ) чисел но кличу

' $-,....!>,-) . где

и «'•кон ар«/^алдоали »оэ * / Л*/..»)^ соответственно ранги а фориуда восотадоалошш

р, ) ьашшальаы. для ^/лоировшшой оастеиы оснований.

Найдены иитоды поотроаншг варокого кдаоол аоортогиаадь-аых ьазисиох одетой, ци ооиоао коаь^шх яаодены т.и.ислаОо-пол/>ид<1аасклв"оастош счаоления, аашшавадв по ряду оаойста цроыи<|?очиоо полоаоиие уеяду аелоаицииаиыии числовыми прод-оталлаиияал и позлщоа.чой полиадичеоко* сисл-иой нрелставде-а«н числовой иифо^ыадиа. 1«и саииы созвали предпосылки для поспросила едцый юоряи нопоаициошшх и позиционных систик. цшзаниого оч«та.

Пря лоотроевю/ "oiajonoxaajunteoiuuc* чжожожых прелого» ¿e*Ht иопохьауптоя опоциалькыв решения ошвш срававииЯ

Ve я,- (r»oJr>) (i*t~) и соотвоготвусщх оиотеы лилейных алгеОраичеоких уравнений о определителям вида Л * П .Для нахождения таких

кодовых модификация иогут сдувать базисные сиотеш, гдо для некоторых, или для soez O&wmux чиоел, справедливы ооотио» веиия

в. íct<

uá в целом всегда

¿ f?, Л. (mpt)(j-í,2,...,n) Очевидно, что при dtou, в отличие от случая, когда eco Oasaoüüo числа суть ортогональное векторы, овязь иекду л, (i»{JÜ) - членами кодовой последовательности, иогст бить оялшзадаиг-па овязи иеаду разрядаиа позиционного числового прсдспаллсгхйя»

Еудпи задавать характер связи иегду члонаии кодовоЗ последовательности овотоыой лянейшис алгобраячеокях jpnauoiuiS, где»

¡^ = Б ) e^Lj^Pj

¿да ревенкя снстеци'в цешх числах достаточно, чтобы со определитель A' -Í . ¿«ому уоловпо отвечает ортояораш-рованная оаоисиол опстоии, однако ухо для других ортох'оиал!— них (но не оргоыорыярогашшг) базаоиыг ci:ckúu яраходооя совать рееокия as сравневка вида

И -77 (r»jdf>h) (i* i, при Л - • С другой czopouu, прияхиая в ваде

Оаэасных чиоед соотвотстаусаие веоа разрядов полкадичоокого представлении чпоол такио получаем определитель систокы вида Коо-- - о

)„и ..О я Ь , ... у

........ л/" (16)

Л- .Л-

Естественно, поэтому искать аналогичный реиеини дхя во«х опециалышх кодовых пооледоватвльаоогви, харахтеркауеюгх ов-педелжтилен (16). При этой, maco ортогональных базжених ево— тек соответствует случае, когда в (16) влоиеиты отличим от

пусз еогу* Оыть toüco на главной диагонали« Basen osajuoj йдаоои, ооотввтопусздв одучаяи, когда а (16) злаыоати, от-&ШШЭ о? аула, иогут выть поолодохахвило аа одной! на двух а аа ( г ■ I ) сдохлых дааговалях, пршшкасззх в глииса.

Сподкадьлоа цалочаолваиов рааояав опотоки, олродолдвиоЗ (Ю) прнам dut

^"JVH ~

....... • • • 117)

К ~ ^ А;*««

Т.о. ортогонадышо Оааиоиыз свдтвил яддятоа чвотнии олучаои Оодео оОцзго рйавкия ешзтеи сравиоиаЭ.

Ори ааднчаи а (16) влвыовтов но раамих кудв только аа одной днагоиада, сьогаоЗ о главной, auoeu иекоторуо 1слаОо-> подаадачеокув" Оаааснуо оиотеиу, где Оаааошо чяода

а.- <?, . .., 0)

"Г0-/«»/»»

К-'. ■ »/<*■•><"-1» i у.- им

В,

п (17) аврепкаетоа;

А« Л» ~ л.»

- /» л\ - Яп

Аля ниорт (гинальши Оааисша eueren одна» аа нотодоа ьшшииаьцла ко^Мацмента иоват одувыть вавдеиио лроиеду-точшх коафф*ш»енгоа увааки Ч; (< > (,2,..., * ) вычисление которых üü связано о оорииоткоа чисел, кратных tCUu/ диииа-аоау, как ото иш-ат u<joto для "Yv , Ошачены корректируете доаиоааооти наорт сгоавльанх Оазисных иредставдвниа, ис-которыи аа которых стада аридматок рассиотрениа, выаолшш-всВ иод руководили кзтори лййдилитог.иЛ дисиортаца*. Гио-автрИйскаа интириратацна Онаисиих ир.гдита1ле.ч*а лешоаиця-

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

Сиотвма п линейно цевалвсиыых п -мерных лекторол составляет оа&яв пространства Р* и лоОой вектор из Р» иояет быть еднистлэааыы ооразои виражей лянойрой коыоянацлай лекторов данного базяоа. Тогда ооэект, определяема ливейшш ооотноЕвнием вида

А = В,а,-»В,А.,* • + является гиперплоскости с пространстве К .

Сметена п единичных п-кериих векторов является баев* оои пространства ^ , поскольку она двяейно хеаалясниа, т.о.

ТОЛЬКО прк •■ • »«^«»О .

Очевидно, что люОые " лекторов, ооралуеиых яа и столбцов матрицы (16) путей нулевжзацдк каких-либо влеыеп-гов, кроме влеьенгов главной диагонали, ооразуыт оистеи/ л»* жВио независимых векторов. Т.о. отодбци дсОой ив особенной т^в/гадьной матрицы, не нулевые элементы которой цехочкехеаа в /¿оялотлоржат наралежстлам _

".и*»")

овралуёт Оявяо простронсгва ^ .

Сладоватехьво, ыоаао рапемтрялагь яярокяй кдаоо оазве-жых сясте»„ хянвйкоа комбинацией векторов ко горух нохат бить хм^&жея лчСоШ штор яа , т.е. х^Оое яодир/еысв число яа яято|ваха [О«?). Очалядяо» что оргонориироранный, как я ортогокалышй оазисы пространства К является частный* оду* чажмяопределясяей патрицы (16). С /четок специфических особенностей лекторов, сытежавджх ял оОраОоткж ях кожясяент по правши и яалозяцяохиой аряфнетякя, базисом пространства Рц может, 'ст. ого говоря, быть хсОая сояокуцность яа п . а-иер-хых лекторов, обраа/омх матрицу, определитель которой есть ирожлведемхв лломеятол ее гхалной дяагояалл. Одяахо лажио ааиоти.ь, что а отхячяв от ортогоялд«ямх( все сстахыые оа-лясн состоят ял лвкгорал-сгрМцол, порядковый вскер которых невозможно арожллохлжа менять я* жар/жая ляяейяо!

иззапаспроста оаотецы, г.а. ото приводят в изменению знаковая а вада определителя рассмотренной матрица. Ото оботоатель-отвл играет оущоотвоннуи роль а опредплоциа правые снчеоких л яорроатарущнх возцоаноотеЛ кодов, донотрунруеыих на оо-иовэ различных цодкфшщиа базисных с истец. Т.о. для задач кодирования а ыашашпй арифметика непозицвонных кодов наряду о вопрооаиа оущеотвованил базиса ваянуа роль игршит вопросы потровшщ конкретных вычислительных методов для зыраао-ная лннеаноа коибинациеН векторов Оазиса кодовых слов ну £0,Р), По оузеству а отоцу сводятся задача декодирования ио-позацзошшх кодов.

•

Глава П пс^вящена синтезу полнношшлышх копоэнцион-ццх ссот<ш представления ннфор1эдин, основанных на щдшено-ша ¡шторподяцнонного шюгочлана Лагршгая для дикоииозацда гзшшнных операнд, а введенного масса ортогональных, но не ортонорц"ровашшх Оазисных представ/эчаа неноиицлошшх статей. Анализ ируи.тоя т.н. "антегральннь характеристики" баэио-шд продотавлэшЫ нопозшшошшх састиц и о-нвится з;иа:1а на-20ДД8НШ1 ШШШКЗВрОВаШЩХ фэрЫ ИНТвГраЛЬНЫХ ХаракТОрИСТИК.НО» дучеиных при вычиолонкз значонка нозашоиных р от друга £71!кцш1. На это.; основа выдвигается идеи построения сонрд*еи-ша по интегральный хгцмк-о/мтикаи Оазисных предативлоша, позволяющих в ряде случаев заменить обработку интигральных характеристик основной енот ш обработкой соогватстиуицих характеристик сопряженного о ней вспомогательного базисного представленья чисел. Раооиатрииьится полынокаалыша представления чаозл, образу<Аие клаоо поэндаошпп систои сшолоших, еоторие, разно как а некоторые нвпозш донные числовые пиелв-дзглтельнэоти, иогут быть оаисшш теорией интьрцолнровашщ а радой таорпи о сиодотвал полияоаэз. Е1а основе пршенеаия гаггераоляцкошюго шогочлаиа Лпгранхп строятся некоторые поевдо^&засниа продставлвнся чисел вспомогательно:! шщишгав-ро ванн аз оэдтвый, сопряхошша о соотватгтвуксшз кодв.{аклцл-

кип бмашшх представлений oonoauoü окотекы. Прн «той, фор-вьгегрвл»ныо характеристик* вваоакциоаных шш&шщж опврьнд еквьриокпш отиоонтодьио лвоого воаювиого аредста®-гония чпсла в фирне подкаоиа. Цродлохеиы ревраОоташше катоды вяпиийввикя соярядишшх оввеошз овстви,

a получений оадий üopajxi воосгаиовдвииа операнду

N-sLtUK^fli^U]

входящая s правув чисть водичина

йввивсетой svcom чксла // ао кхьчу & пиляетсп йнтсгредъ~ СО& ££раК1бр£СТЗД0Б числа, EiflUCJiflOlíUS aS5ÜB"0ill¡U от его ранга ш чтoii базисной придсталдииии. аао чиоли tf a базисное арвдотаадвквв ао вокотороиу клвчу инваркайгок отяосв-тедьво лооого вовиогиого продотавдеаая чиода в форио иолаао-

авлгчйд*

2 *

пьооаси относительный »есом чиоде Л/ по мочу Кс , в СОК

К," i * всегда S„* ' . С затону фориуяа воса чвсха для СОК вримегаид

Т.о., ив чаем N » Опасном представлена« во веко» тороцу iac4j К» р&вск раааоств »еаду его весов в СОК в оноентеивым весом о« данному клочу

w^ * ■

¿окавая ряд теорем о своКлвах вооа к а&Ддево

•го осеадоОавасаое аредстаадевво вада

где - дедов число,

соорахеаиоа ао paary о oeiacnm npeictaxxeuua« «нс/а N по

• &*о позволяет * некоторых случаях nopeit» api определввив раита «вода А' от ооотвоаиая

я сиотковевая

Дохавиваотоа, что /u,t */t,¿ . H-t) т.о. базиоиоо представление сопряженное о основной базисной сиотоиой по вориамному клочу имеет шшшалАНО зозиожаые базиоиые «воха. и&Ьдвшше закономерности кш возможное» но только уилиыши» «еднчшш ооярвхешиа базионых чиоел вила

/»,; • AJi^i-J

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

Другой споосб заключаема э нахоадеинц, путей подбора ооотаетствуоцего клвчв Kt » таг"эй оопряжешюИ базионоО система ^j»,..., гАв вое бавионые чиола иио-

от наибольший целитель о величиной ']) , Т.е. долвса быть В&Дден такой клсч Kt , при котором вое Мч ,киг-

да ф, причеи, делитель Д ааибольиав воэио*иий для втой оиотоыы оснований. Практически эта задачи сводится к реиенап ряда днафантозых уравнений,для находдециа разрядов клоча Кл .

Найденные зйконоиариооти каавт парное значение для построения о помоцьв солрпхошшх Оазисных представлений алгоритмов полипной арифштакн. Яаеоте о тии покиасно, что азо-даиая при приыиноаии яолиноцлальиих оотаточиих классои избыточность не каоет з себе ицфориацг.о, достаточную для коы-аоиааццц aovepHuajJ jpA ¿слиииоалциа интегральных характеристик кода» 'jor.püoau ааед*иия подооиой избыточности и построило более удойных для алгоритмического оОеоночьцяя аи-тоиитизаро: иших оистои переработки информации оонрядоииих бвзисиых предо:азлвииИ чист иоовдцит глава 1У диссертации.

• Раннео в ;:ерьоЛ глпбь была исследованы {'ункцмоиальйыв возможности неиэбыточних базисных прсдставдиал& неиозицаон-HiiX систем, определлш граничные соитносшния параметров, оо-аовные правила арифметики непозиааонных шхверсиых предота*-яьаий чисел. Обоснован выбор структур» цеиоаициошшх парь-иетрачес&и оистси 3-го и 4-го порядков и клича иэдовоа модификации, предназначенное для матричных комионешт ьстоииги-знрованних овотим аерориботкй информация. для указанных на-

ракетряческях ояотем накдеям /доОнма о точкя лреххя

реализации {юрк/ш кодовых ореобрааовакл! в яда

С » Т К ♦ Г, ), С'- А -*., С. 8 « ГД» с, г 2 1 ( fctf* ¿ 1 2 ) (еие%л{ иии о),

_ Го, •*» »0

^ ' [ «Г., ■<,

В третьей главе в первой параграфе раосиатрилаютоа пеко*©-^dd раврвоотанныв яетоды я матричные алгоритм олределеняя поэнционных характеристик для ояотем низкого порядка. Входе» но поиятио "спектра" авполедионного чяохолого представления и доказали ооотвотстз/вхле творены, повлолясвдо реализован табличные аадавия оаектра кодовых операнд а мяохашшх ыа вен адгорятноя ьаяинвой арифметики. В чаотности, для пара* ватрячеркой оиотпш! 3-го порядка p^l'-i, A*?*, раовярояяоа нормальное яклврсяоо продотчвхеннв числа А/ иа Р, Р,) моает быть оходувщш обрааоы лапяоаао а баэаоаои

♦ ( К -л К У*■ Р. A í'Wí •£,) *■ % 'Г* ^ j

Савктроц продотаххаихя «хода А/ тогда <$удет поохадояатед»-аоо» tje *í, w^« ©С« V

Т.к. "кацонхчмкяа" спектр для ато! сяствиы инее* вяд .,■•■"

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

А

о

0 2

1

0

1

Д V

0

1 X 1 о

0

1

0

1

/1

2 2 О О

С и • к г р £м

40,0,0)

41,0,0),(0,0,1) (0,0,0) (1,0,0,),(0,0,1) (1,0,0),(0,0,1) (0,0,0)

i0.0,0)

-- т

(0,0,0) (0,0,0)

йдосы

- 19 -

А ж S 0 • *» у Л , Í "»

Соответс/вующмв оивчеша /и приведены в таблица]:.

tío второй Барографе втой главы дано дальнойиае раавнтаз пшщю! в первой чаоти диссертации идем поотроекда опоци-алыш* оопрпшшшх друг о другой оазисных представлений, преднвзиачеиных для оптимизации алгоритмов иеяоаиционних он-отен. ЯазраОотаны теоретические ооновы поотроениа тан называвши "инниОааисных ыодалеИ" оезиокых представлений непоаицн-ошшл оиотеи, донизан ряд теорьи о структура а свойстве* подобных вспомогательна* воевдоОавмоши лродотав/ений, оиирс-аенных о основными, ^аиеыатрилаетоа возыоинооть учхоаденип целочиолишшй дшюНноа функции

аргумент которой в «очко Т» оовпадает о аргументом

линейной фуикцин

лрнаанавцеВ значения аоконого кльсср по нодулю р; , Кодируемо^ в нииоэацшлш^й Orfcvuuj чаоли Af-Nlf) .величина зинипит (при ^икоировиияыл основаниях) от выбора Оьалоиой оастоиы, т.е. от К« клоча оазигчого представления числа.

Поскольку основный нодоститкои иряиого вычиолиинн аргумента функции (1*) в точка i » являютоя ооишив величины непольаусиых при атом uaüuuuui оперинд, переход к мадоразрад-нны операндам в (Ib) очевидно допуокаот иолольаовавие во»-мохности пряного вычисления ив

bfT.)-^ d. C¿U>

для нвхолданаи иекохорых'отаоснтельао простыл методов по-оуровняя малинных алгоритмов выполнения цультиплшштивцых (мемодульных) операций в вычислительных уотройотваз непови-циоиного очаги. Tuk4u йбриаоа ара иоерроаали (ib) 0y;'90iBuu-

- го -

вна ввдяетоя требована« h « < N в, соответственно, l<<5,è. «<ßn ввиду чего естественно наввать (20) мнибаввоно! кодеин (МШ) бааюного првдохавдоадя, а чао* до и с г> (о) - шишформол чмолл А/ • Тогда "о&дохоа" бавмоно! овотемн ао к«ячдг К « навозе« аоомдовахммоох» цедых чяоед S, * ( S.,, S»,S) охвечамдо одедумрш требовавши » I* Сунеотвует неохрнцатедьяов 5* » sадов, «го

Ь#| s О (m9j $) \

2. » fcgagei

3. оф,. -Cil* (*.

Аналогично - f, "сндувх" периода ff . «¿окахвихо сндуэта* 1 -го бавнсного часда в периода $ - состветотаоиао,»»» Двины л 5., « - в a ¿J Sç = Sj - Т Сндувх чдсда А/ Sí% е Z S,. .Coosíerct-

вевво Л 5,И î I -"вск£*вн1в свдуеха «ком"»

Тогда

Ь » С с Л где •*' . '

«J, ш (oí ь «с^Л V

а «>

* é»t »•••» Л»

-шмябаввсше 4«ода МШ.

Иесдедувгся подучечыа соотноаваня вида

. « í -d s« ?» Пл I «Х"*"' £ * Д V

На основе uuHttOflSricaoro ицдеддров&аи paapúOoioaa но-sодвка ir зтроенля алгоритмов бисхрого дикидлрозаьая в ноко-хормх адгорвхы&л нопозпцлэино* маенуаэн йра^&та.чн. в поо-ладней параграф фвгыИ ¿дави кххибахлс.шд кодел н.сиохт-втвуоо»а, основаишм на адх авгордпи psocuJ-.piufoTiB в ар»-аоаанив в зпицхадыи» авраиехрвчискдн систлга* >>гч>,4-го рядков, а частносхм, а оасхомв >-го аоря» ь с рсгудяриыч неямодудыши («ссхояннеи а * / м>Т, Г] isa" Чксда

SüjnJT3^! » где £»jj - OTapaafl двоичные разряд оунмы ,

»ft-M'»I*<f>> UI)

С R = « £ = О « ш I - экачеаая соотавтстауодего элемента треугольной иахршй» переполнений). Одновременно вычнолпет-са нормальный ранг г^равзна «лоду переполнена! ара вычиоле-наа ojhuü (¿i), йроведеаа сравнительная оценка традиционных нетодоз декодирования, алгорзтмоз непоэициончоа наваиноЗ орпф-вехака а доходов, влгорзхаоа ооаовананх на иинибазнсиои иоде* даровании, показавшая ярэаауевехао последних.

Ч.'гачргая глава в ссновноа поовяаена вопросам заедания ааошичйосхй в наиозадаошшз ародохавленал чисел,достаточной ao ocneuj а структуре дез £срзырогагмя заданных алторйгаото-ках свойств непозициозазх впаянных операнд. Аналаааруетоя возможность введения подобней агбыточаоота при работе о приближенным* числами в азтоаахиааровашшх овотемах лереработка информации«

йродполагаехся, чхо'всв оаарации а АСУ ароводятоя над округдеанииа праблнаезлузя ггзлаып, которые анвох в яд Ji ч О. . . . . fCtn , Oí Такое аредсхазленвэ знсва позволяет яря нааиаяой реализации» но ¡рохтлвая ^зктгягскоа разрядности рагаотроа чаола дслоднихь осаоануо скстзау основания р., pt (• • ■ ря пгбытач-аиь оеноааияеы * анназ слояааа,0ныслецноп приписать я

ьапаоа пасла разряд* assjrsaü дсяоднательнуа анЗормащш. Однако нааОолвв псролектвгина представляется найденный на ооаоза теория ниадоазисхигй иодзяярозаниякпод иодульаого задавал рангов шивл а состава азазаазаонных вааиядиз операнд. Доказывается, чю ослы даз сгстева сснозанпЗ р ■Ро - > Р» построено янверовое продеталзйиаз (kfo) во вл^чу Лк)огаечао5в-

ej уоловаяз

■ пг„а tttu^• ■ -в т,»-з С стДб*)

а айвах г.з.о = С (»т.еАЗ*) , то для аавх целая "Г пз

i««*) "..с з X" í^f'A-c" 1 »п.- aeí. i -ro Oia.icHcro

... í 44CJia»íai, "í/, , - eowxJc.'C?auH«o ¿«tura - a

Еоди , ТО РыЪ • ИО;*вЛЫШЙ

ранг числа Ъ,, - равен результату осерагчй по т)J * над шшыаиъишмв неотрицательными впатамх по етоцу иодулю <*,, в />„ , где «I,

Л-

Приведенные соотношения яахястоя частным случаем более общего утверждения о том, чм , еолы

для 5 имеет моото (22). «одульнои вадшше ранга числа открывает воаможнооть болео рациояаяьногг вспольезвания отоЛ характориоткхв при поотроании алгоритмов непозиционнод ма-лшг'оД арифметики о общей .штжнхжацжж ввкоторшс обменных в вычхолитольншс процедур в ажтоматиажривжшшх аиогаиах переработки информации.

Прикладным вопрооам реалжаацви ьткх воамолноотей посвж-щены /, У1 и У11 главы диооортацжж,

В пятой главе юоледуюто* в раарайатываютоя елецкая, кие методы нелозиционного кодирования для жнформационно-иамарж-?елышх подог.отем, нграиошс вое более важную роль в ооотава автоматизированных систем управления. На оонове наДденша в I в Ш глпв&х диооертации кодовых модификаций, предложена методика, по8 водящая применять для намерения лк .^иных величии опециальнь'е модели "цельных", жли "баавоных" мер, не разбиваемых в процеоов намерений на додж, цена которых лхшггдрует точнооть измерения.

Действительно, пуоть ныаагоя ^ахтор М , модуль которого $ I где я„р»....,Я. -попарно ьаакмно проотне чхохы. ЛЪгдл любому С' £ - сумма ортов направления

N , гх.о ?) , однозначно ооотватотвует линейная коь*-бкнацяя кодлинеарных векторов вдда

модуля которых ооотббтотмнно i причем, ца-

лочяолешше омияршю хоаффкцжиггы ,^ удовлетворяю? уоховхям: .

Коквниацаи поллшгззргпт Еггтсроз вида (23) однозначно определявшие ооответстаеадо вадасры с-С с и отличается друг от дата за vesse, чей яа величину

ГАв líOíSf

Таким образом два oueassr огэтегяя по акала намерении о цэ-ноИ младаего делваая ч - , ара измерения базис-

ными мвраиа «Ьгдут отлидатзся друг от друга не аенее, чей па величины« хратнне Î. ж/V. - .

# зависимости от количества мер, учаотвувцих з конбина-цяа (¿3),иенпетоя абсолзтная согрепность намерения .причем погрешность те» неньпе, чем бслапо скалярных элеиентоа аэ ооотнозоивя (23) равш! пула). Лсазапноо оботоятельотво nos-золяет отроить специальна? оспорят ни уточнения измерений путей сверки результатов изавргзи! близких по аааченао величин, Аааиойые водоля которых гягчительио отличатся друг от друга колипоотаоа мер, упаствуетсас в коаояяацив вида (23).

Следует ответить, что csejapoaaaae крупными ыерани вводит к аинаЦуму возшжззта j,a.0flpouaxaB пря пзиерепаях.

Другим, заодушшагщк* гагггавп оботоятельотво», связаи-йыа с арииеаеиаеи методе? пггсззттаояиоЛ иаяшшой арифнетикя для оптинизацяа яетрогсгзпгггсго ебеопоченпя АСУ, является то, что т.и. "критически* sôtsa®, гдо еоаиикавт трудности о опредодеааеа штегрзггг^г —р2ггзр"згак пзпозпщюаиого пред-ставленая информация, ралюязиаа э мчало a иоацз интервала 10,Р). ^вазашшо 2рудзс5та гзрзййтся з той, что для "критических точек9 пвзозногиэ в приааленоз лреаа определят» йеотопололешю чпола и тазлагсз аатаргала, лрячаи возаякаст альтернатива! находится "хваггискал кочка" о начала ила э конце интервала Оддхгэ» пра иассоззшс азнеренаял ко-

зодои сукмзрогааля бэгйсанз к??, когда известна ааперед сэ-даааал средняя аоличиаа аззгрмаого параметра, зохучеааэ результата леаацего s протиаополсаао a области "рзаброса" ваиэ-р&эиого паранотрз С конце натерзалз «зосприаикается каг аэнерптедькн1"прсиах" и аогзт быть легко сбнзруавно спецэ-ьдьаама средствами контроля. Т.о. трудности, приеуоаз задачам аепозацяоааоЗ кааашзоЛ гри^мвтакп ие отрапв-гса па аре-

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

Показано, что повышение точности швмерениа в знача-тельной степени имитирует о я выбором системы оснований для неиозициошшх представлений чиоол. Доказан ряд теорем, ио-ходя на которых били найдены оаецвяяьиия параметрические оиотены представления информация две вв^ормацвонно-иамер»-тельных подсистем АСУ. Разработана методика применения во» дооних параметрических систем ара маосзвых авхоматнэмрован-них измерениях и определены интервалы намерений для различных допуоксв н требований к точности* Поскольку найденные специальные параметрические системы поавол-ст задавать значения рангов чисел в наперед установленных участках числового интервала, в "рабочей" интервале 10,Р) иохет быть определено неокольцо участков массовых намерений:

- при больших разоросах нзмеряеаых даранетроа н невысоких треоованинх н точности - обдаст* намерение целесообразно опридешть в конце диапазона. Там - сашА бодьлюЁ про-менуток безранговых значений кодируемых чноел, но в то же время, в самые большие абсолютные погрешности намеренна,т.е. оуммы вида = А, Аг „, где А, , -неустранимые погрешности соответственно мер J, , Га . . Однако качеотво намерений на атом учаотке интервала ДО,Р) самое высокое, т.к.» концу интервала растет анаменатель N отношения f* • -jf- . (

- в середине интервала - участка беаранговых аначиннй, г да F,t:«ijooopasuo проводить намерения ара более строгих до-иуслах на изделие, меньиии раабросё измеряемого параметра;

- самый строгие намерения - а jbkhx промежутках беаранговых значении кодируемых чисел начала интервала 10,Р),

Иокаваао, что оиатемы можно •яоддирать" оаёцаадьншш цедима стандартным« нервна, чтоб» аорсмеьать обдаоть нзме-f сив! м минимизировать стноситваьцуа погрешность.

¡JtjjroH глава в основной диевхшшш исолздоаашшв нахо«деаав иаходоз иоогроеная впвдаалышх нзбыночных ивао-

ввцлонши чиологшс продетазлениЗ о задаяшша параиотраиа. tloorpoeiiti а псолодозаны иерархические окотоин продотазленяя ан^орнагща а нвЗдацн аетоды вычисления пароходных паранетроа соответотзупгщх иерархических аопозиционккх оиотен.

Создание иерархических вичполэталышг структур приводя* к наогоуровназоЗ дохоыпознцня, причем оСрвботка инфоркадня аа каядоя урознэ связана о репейной опвцкф|гчсокнх для этого уровня задач организация гычнолитвдм« процедур. Б овяза о отни гамоэ эначаииз приобретает построение рациональных алгорз7!<оз, устаиаалйзасоих ооотаетотгнэ мояду оснозншыя nft-рзиотрч.уц капинноЯ ип^оршдйн аа различннд уровнпг рорзооткя, ОдиоЗ из такп задач ялляатоя «аховдоние удрОиия для реализация пзрпиотркчеокиз зззооиностэй манду раиганя снезшх оту-пэпей в нногоступенчатнх яепознцнопннх саотеиах првдотавдо-пяя каианпо! информации.

Цуоть азаетоя саотева попарно взаимно простнг оснований

Р, .-••.A»—-.fl.

г,й jtOTopc.l IIOOTPOSUO непоэяцдонлоо представление кзлнпио! ип-Ооркацяа по клену /С » причем некоторзо s Сзпоирогашшх оснований - соотазгшз & тэт ляд

s¡H!<--^ »<*> (г5>

Уваозяадоаноз прздагаддэныз ПО lUfSTj К Судан рассеаг-как сисадго старлуо отуясш. ао 0JBрденш? х попоэпци-ояаоау представления чисел, построенному ва сиотеие основа» аЕЗ ^,.. # -... д„ ^- ¡t»>-S)

а во клочу isk (med 7) • Счозядйо, что такие

снэязке ступени будут caet» одинаковые период ? »Докага-дается, «то tow аялзъ ueajsf t„' - рангок вр^дотавле-вня числа Л/ в сяствна п -го порядка по клячу К д tj"'' - рангом представления atoro te часлз i с йот выв С n^^-i-o порядка ао плачу /с задается соотноюаяаи

-Т, 1 л. с

Й рмрад •цваозшиоадого прадстаалеши числа из интервала С0,Р)} т., - ранг иенозици.>ышго прадитавла-1ШЯ величины Д., , иоотроишюго на оист на ооноваши! (26) о периодом р^

Фа-МиГи

- целочисленные "пораходше" коноталты, (¿лиишроиашше для аа-дшших оистон ооиованиП (21) и (25); И., , , 1г>'ч -

г итватст¿укляла базнснш аоса.

Паргшзтричаокие иинозишоиный оиатиыы низкого порядка достаточна разраОотани и сособны закрыть лийоД мдшпьш&. диапазон. Однако иотрологичоокие применения иопазкциошшх аистом триОуиг Оолее иолноИ декомпозиции и-формодин» что ыодют быть достигнуто 8а счет пошщаивя порядка подоистед иорнрхичиокоЛ структуры кода. НаОдвшшо порвходшв соотно-¡¿о<:ая и параметры даьт возможность распространения на такна ыного^рошюьие оистечы методов матричной обработки ноповицв-онних операнд; а таквд роаультатов и катанных алгоритмов, цодучишшх для оиотаи низкого иорядка.

Проводим анализ методов обработки непознцнашшх представлении информации для иифэрущцонно-нзмаритолышх под-сиотиы АСУ.

В последних, 3-м и 4-и параграфах главы р&асыатршщютоя иреддожош'че матодц послредиил специальных избыточных псовдо-дьимчкых и пиеиданииоэлциошшх числовых представлений для обёопччеаия оквозного контроля достоверности данных в раоп-родаяоиннх АСУ.

Ч4':.':0, аадшшоо пооладоватвлънаотъи двоично кодирование вычетов Л,,с*,, | рдооматржааатоя как псавдодвоичное олово вида

(26)

З.з.чсь

о. ,0.1—

~ июпная запись а, - наименьшего мотрхцат&хшого вычета чмода /I по оспаашш р, ,

¿водитоя'весовая rjusman" »/(1) , отвечавшая уоло-виян O* i

Тогда ^ и

Формула (¿7) является ооновшш ооотновением для конгро-ля операций иод псовдодзоичныып словами вида (¿6)« Ооаару-севке сцйячпоЗ озибка а псевдодвоцчнои олове (26),здесь воеот достигаться введением двух избыточных двоичных разрядов, тогда как для получения аналогичного результата конт-.рольный-код в СОК строится путом введешш в оиотему -го я^оыточного основания, отвечающего условно р ^ р , (lT Г/1) • Основанной cj, , кие&оии первообразный корень равный дв>н, как правило, ногат бить избыточное (и)-о основание, првдназначоиноз для пйнструврссзагз коррактируо-цего ариЗшетаческого попозициониого кода. Таким образом, при технической реализации появляется вооиоаность двоякого использования , имвктиигосп цодудьного ари§аеткческого уотройотва по основана- для програыняого выполнения двух раз-

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

Рассьаграгаотоя гакгэ обратная задача: отоздеотвлепио позиционной конечной двоичной последовательности о непоаицй-ошшв представлением некоторого гипотетического числа Т, Upa этом определяоюя условия "бозранговости" такого прэдо-товдвнил: у ___.

a~'t) l¿<l¡ 1~<Р. Л'

где г* - длина регулярно!! группы двоичных разрядов, отоз-деотвхяеамх о ипеиспьппми неотрицательными вычетани чсола A*o»s<p, • йрниенсняе введенных избыточных кодовых кодификаций пулевого ранга позволяет значительно упроотпть извеотиые алгоритм декодирования для иепоаицкоииых онотеа, обаарулэ-нпо в коррекцио оаибоя а псевдонепозационных числоккх пред-оталлевиях о "иодразуиемеиой •нзоыточкостьп.

11 седьмой главе дхооертацнх хоолодувтся методы фориаль-ио! дйкомпоакцях для о ките за коифогурадм распределены.« АС/ при применен*« избыточных маоакцхошшх \лалоша предотавл»-uxi, В аарвод параграфа главы »та вопрос всоладуются пркш-ихтельно к хаьаогиоиу методу быстрого умножения Шенхаге.

Оонову метода составляет а случаям опвцжальккх р« щенка ожотомы сравнена* w.-kfimjli* ',«» t дм w*[0,m) путан применения рекуррентных вычхолешсД, арх условии, что основа-икя м, представляют собой параметрхчаокуг скотому попарно изаишо простых «ком Мероенна. В.б 7.1 дасоертацих докаливается, что введя в окотему ооиованжЛ ¿ленточное основание вида т.« 2 в оперируя опотмтотвуэдюа вычетами ооммовкто-лей м , по основании гг>, , можно кшшчхть кз пооладна-го »тала алгоритма рекуррентные вычхолацуя, на долю которых приходятся адеоь ооноанне ареи&шше »атрати. Имаот коото слэ-душе в Предложение, Пуоть

U V* W« fO.M) (N- rfw. ), oouoi uuta IL.,

uouajiuo взаяшо прооты швд оооой в введено хзбиточнэо ооно-ышне ►г,»}' такое, что 2ц-2<2* . Тогда иг модах быть вычислено на соотношения

v-tyi^i *"•*

гда

Mi« /W; U • о-- М ); 0< - о-;

двоичного представления произведения и } Ь. - числа, определяемые J шкишшм разрядам* двоичных предотсалаавД оелкчвн t *г. - ЦАлочвслвнаая кокотанта.

ги. «2"-/ (£•*,»)

Црааоаенив яабнточного непоаиционного числового представления о модульный заданием аиачеаип ранга кодируемого числа, позволило, поиаио раопараллелнвания вычислительных процедур, значительно упроотить алгорити декодирования и построить модификации ивтода, прзвосходяцув по быстродействии и доотовор-поота исходный алгоритм Шекхаге. /иноженав на конотанта а случав табличной реализации, во влечет аа собой лреиенныа а аппаратурные затрат,Также получение и. , а, -вычетов ооиножитолей и. , сг по основании р\-2"и величин $1 (¡' I,*) из требует дополнительных ареиенных затрат и роа-яаауотсл на стандартном оборудовании с инициальной аппаратурной избиточностьо.

Определение бза предварительных рекуррентных вы-

числения приводит бчалидиоиу граненному выигрышу, Не ноноэ супсотаешшиа лродогшшетоя открияаоыно предлагаеной ноди-Оккацаоа дополлигояыша аозногаоаги распараллеливания а таб-аячноа реализации ».ичислоиий, ооотаогоиуилио ооарзвоиини гондоиц(1Ш4 развитии янчшштолышх отруктур.

Ьо агорой параграф! илалогичнна результат полученн пр;! построения нодлфшад;!:! иотода з&гдоы лафорлация Морки-Азл-лнзиа л рассмотрены аозыозлоотп применения напоэкциогшого аре«» дстаалоияя ¡трораотт яра реаеачч вохогодо задач целочисленного лилейного программирования.

Современный лнторео к вопросам криптографачоскоЗ ааплтн информации обусловлен азасстныни доотизенилни в области конструирования а эксплуатации вычислительных оистеи н АСУ оо многими пользователями. «то обстоятельство само по бобо привело к внедрение а криптографии новых идей, баааруийлхоя аа своеобразной прилоионин иокоторых вичиоллголышх алгоритмов а негодов оцзнхи дефективности о«стем о точка зрения оценки вычислительных мовноотвй а слокносгя алгоритмов, необходимых ч для уолеаного аньляаа.

Специфике задач я вычислительных сетях я АС/ исиболоо ооотзототауот система о т.а."открытыми клочаин" удовлетворительно рвзаааиз проблемы транопортирозхя клячей в ядбнте*»-едцш! при аалхчжя оохьаого числа польвоватехой.

Одной ив систем о открытии ключами, где подо Сын коиоддзодаш во8ыожнооги модульно* «рнфнехвки, явхяегоя ов-сявна Иеркля-Хвмшэна, вычислительная сзиАкосхь которой ойеодачиваехоя хрудноотямн решения » оО*°и виде х.а.*8ада-чи об укладке раица". Как иагоотио, в хаки сйохвыах в качестве открытого ключ? опуоликодидаеход /т-мариый векхор ' ач»,^,,...*, порождаемый вокхором а' на оравионн* а,.««; уМЧ) (Ола^Ч; .£«,', <г; Коипоиааты вокхора а' подобраны хакад обр?.аом, что ооот-иотсхиуот легко.. рсшааиоцу частному случае гадая«об укладке, раица. Кодирование л -ои'шя даоичии. блоков«аг,,^,...,*« нроиоходйх путей образования сунн вида £ а, дексАи-рои«ни( - аооредогаои ьычиоленил и цоодйаующвго решения чаогього одучая аадичи ой укладке ранда при 5" * . Царанвтри а', \ и/ ; - еоохаьдям'". коииаоко личного ключа оодмоа&хдда,

Р&осиахршютоя воаыожаоохь ноподьааванна для декоди-роаа. нн дифроаого сообщения одвцислъних процедур пере- . кода а.одиу и» цааоайционцых апогеи счиоленин, ирудлонин-ш;х в § 1.2, Дикодиро1 анив ноояе нахождении , ооохонх и о£оидаохлдииш( атого сообщения о его «впоашцшиннм пред- . отаддикиеи д двде поолудоватодьиоохи иаимвмыш наохрица-ходьних личехов * ооохавхохваано во

ноиарно ¿одишо ироигии оааоааиит», прнчаи

где £ 'А ("Л р.К & левая часть пршшиает значения О йда ¿ь И чаотоога, нездешне двоичиых разрядов кодах .■о^й»«:параллельно. иа.;п аычнодитехышх бдонах, , рбайизуь&их дыхеквецм иа (¿а) сосхкощание

('О, $ *о —

* I I. ~г.< 5 4 (Р (^р.)

Такая структура алгоритма поанолвст увадичихь проиа-аодихадьноотк декодарусщей аадьрагури, иаоехаг* на данной

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

— Долее рассматралаогоя врилогеякэ нолучваш: з главе П хооретичоских результатов 2.и, "мпикбазисного моделирования" для построения олгоркгиоз решения нокоюрих задач долочЕолоииого линейного програк«иро»а!Шй. Пря эхон зектор

.....з.„) j спхшширувпаь. .ятюднуд i"(l)• Z •

о ляяс&шм огрзиилошш-ча ''

2 Я, * ь. ; о о < h L " ) j <2у)

>'' . -огоздеомдявхоя с аешшцвошиш продехазяояао" локохорого целого часла'/1/*'fo?) по клйпу Кё , .яяодвхоа дополните ль» sao дкнойлые Ограничений

х^ Г. ; та у. (сс: i .с-к ml л о. , V

i» Г .

Поагрогам д^гшхевм эдгтаэвд* длп кохолдог!«^ соохватсглу« ъщях ааагоаахсякя чиовд Д шшнбааксйого представления чме?а //«vX » Иокасздо, что уя с?е<5одуях «глачоя уро*-йояйЗ (2S>) ;t:i2»2 nocsi» ор-тшолил "

где '/, noiiop пнгергада «*{) 9), f " которой нзяо-датоя число , "7,"" - ранг числа С * -V,'"" <? 9„ зидз

з сшс-us оснований. F.iPi,--, п0 клвчу

¡Ct'^'fK.,К, ) ,• адесь Ч"'" *ü «ра г»й*

"отрицательном псиазенла оллуата" й яра^по-

догеихольнои иекакоиикг

След/62 отметить, что з .процессе разработка на основе найденной когодлкл находягоя П0ролехх.шшй kJii'Op;,iwi репе-якя некоторых целочисленных задач линейной оптимизаций.

, В последней параграфа глава расоматривеотоя корроктнру-евде ¿oiuosaüüxa зййдошшх азбиючных олииоголиадичеоилх оиогеи очлолуная.

Согласию главе 1 для д - разрядов слабоаолиаджчеохо-го представления чиола имеет меото

(30)

где ¡ , a¡ положительные целые чнола соответственно вв интервалов С -i 1, [О, р. -1 ] ,

Пуоть А., i« - "неправильная" последовательность, где хотя бы для одного члена условие (30) не выполняется. Показывается, что тогда существует тол_ко одна правильная последовательность у для которой справедливо оравдеым

i« * ■ .« •

а члены последовательностей ? и у овяваны соотношениям!

Я.-iЕMmídft^,«íА-. (™¿P¡) (31)

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

ЗАКЛЮЧЕНИЕ

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

2. Разработана теория поотроешш базнаных предотавле-•Х1Л аепозкихонних снотаы, позвомщая формировать' базисные яГ^АОтавления о наааред «аданныш овойотвами.

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

обработки совокупности фгйлов распределе. .шх АСУ.

4. Обобщена теоретические ооновы построения нопоакцн-онных и позиционных систем счисления, введены т.н. "слабо-полиатическио" системы счиолиния, занимающие по ряду свойств промежуточное полоконко мезду непозициошшш и позиционными тасловыш! представлениями, и создана единая мэтодика формирования файлов с заданными структурншш п корректирующий СВОЙСТ^ЛИ.

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

6. Разработано алгоритмическое обеспеченно кодовых прообразовали!! нопозициошшх параметрических оке тем 3-го, 4-го порядков и вводено модульное зацшко интегральных характеристик п состалэ нопозициошшх файлов распределенных АСУ.

7. Разработали тооратичоскно основы расширения изтро-логпчеекпх возможностей нопозициошшх представлений информация, првдназначешшх для информацвонно-Езмордтолышх подсистем распределенных АСУ.

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

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

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

I. Хадаевич З.Х. Об арифметических возможностях одного класса нэзозкцкэкных кодов. Сб."Управ.внч.маджнТ."Экер-гхя 9 <<!« $ • $

2, Акушакий К.Я., Хацкевич В.Х. Инверсные представления чисел в оиотеш остаточных классов. В об, "Цифровая вычислительная техника н программирование". М.,1967,вып.2.

3. Акушокий И.Я.Дацкввич В.Х. О бевранговых неаовициощш представлениях чисел для одного класоа оснований. Б сборнике "Матоматическая и техническая кибернетика". Тбшшси, "Мецниервба",1975.

' 4. Хацкевич В.Х. Об одном классе неортогональных базиоша онотем в СОК. Министерство обороны СССР. Сб.научных трудов * 75, М.,1967.

5. Хацкевич В.Х. Вопросы работы с приближенными чиоламн в > оистома остаточных классов. Сообщ.АН ГССР. Тбилиси,1%7. , 6. Хацкевич В.Х. Модульная арифметика в оно теме оотаточшсс клаооов. Труды ТНШСА.1Х т. Тбилиси, 1969.

7. Хацкевич В.Х.,Даниленко П.Я. К вопросу о почншвнии ефь

! фектнвнооти работы электронных цифровых систем путем применения методов напозиццонного кодирования. ВРЭ В 9.и., 1969.

8. Габадшшш П.В. Дпцкавнч В.Х. К вопросу о матричной арифметике непозипношют оиотеи. Сообщ.АН ГССР, Тбилиси,1971,

9. Хацкевич В.Х. О неортогашшшх базисных системах непозиционных представлений чисел. Сообщ.АН ГССР, Тбилиси, 1971.

10. Гегелия Г.Д.,Хацкевич В.Х, Об одном метода поотроення

систем автоматического контроля. Тр. Ш научно-технической | конференции по надежности. Л.,1970, II, Габашвили Н.В,,Хацкевич В.Х. К вопрооу о мультипликативных характеристиках непозяцнонных систем. Тр, Проблем лабор. автоматики н вычислительной техишсн 1Ш1 иы.В.II.Ленина. Тбилиси,1971. ' • !

12, Габашвили Ц.В.,Хацкевич В.Х, 0 контроле по модулю машха-ных операций над ноевдодвоичными олэвамя, Тр. Проблем, лабор. автоматики и вычислительной техника ПШ хм.В.И. Ленина. Тбилиси, 1971.

13. Хацкевич В.Х. К вопрооу о достоверности передачи инфор-мацях мзаду коцнонентаыи гибридных нычиолАтедьных комплексов. Сб."Гибридные вычиол игольные машвд к кошиекои", Кх»в,"Ыаукова душса",1973.

11. Хацкович В.Х.,Шакарлн P.A. О применении элемолтоп теории вычетов для измерения линейных величин. Материалы П научной республиканской кэнфэренцпл по метрологии.т,1,Тбилиси,1974.

L 't, Хацкович В.Х. О расширения диапазона представления чнсол для одного класса Непозицполных кодов. Сб.""/лгоматкчоская к техническая кибернетика","Мецкиереба",Тбилиси, 1975.

IS. Хацкович В.Х..'/лшябазисныо модели нолозиционшх онотом, Сб.Матеглтичоакач и тохничоская ¡ш0арногш'лн,яМоцккораС!аи| Тбилиси,1*77.

17. Хацковнч В.Х. .Чачанашшш! А.Р. Базисные представления для одного класса нопозициотшх слоте». Сб.материалов "ItoTöip-тлческая и гохшпссгал к t:6 о р ч з тшса","ецилер оба", Тбплпсп, 1977.

18. Хацкович В^Х. Вопросы построения избыточных нопознцпошшх кодов. Сб."Вопросы вычислительной техники и управления", Тбилиси,1987. Изд,"Мацниороба".

19. Хацкович В.Х.,Чачанашвилц А.Р. Вопрооы построения однопара-матрнчоских двуступенчатых непозицношшх кодов.СбТМатоматл-чоская а техническая кибернетика","Мацни9рвба"Т0илзси,1979.

]j. Хшшепич В.Х..Чачанаовали А.Р. Избыточноз представление чисел гля матричных компонент вычислительны! сотой. Сб. " вопросы кибернетики, кодирования и передачи информации в вычислительных сетях".АН СССг.оыпуск 42. ;,1.,137о.

..1, Хацкович В.Х. Газвсныэ представления непозиционных систец в метрологических задачах. !.!атариал пятой республиканской научно-техническоА конференции по метрология. Тбилиси,1978,

'.. , >'ип<вш1ч З.Х. ,-Лкпрян P.A. О применении одно.1 модификация •шкллч&ского -кода для г:о'.-г].>оения ыоду.тьноА арифметика непошгщэтпшх систем. Сб.",:<опрооы вычислительной техника", ' Тбилиси, 19^9.11!

.':.), Хацкеняч З.Х. О реленкя целочисленных лянеДных оптипгаа-циоянух задач з остяточт-чгх класонх/.Сб."Математическая и техническая киберногккя". И?д."Чецлкегэба",Тбилиси, 1^1.

24» 1ацкевич 3. л., Цгебришвиди U.E. О некоторых кодовых upo* , двденнях ¿ычиодителмых сетях. С0,В1У Воеоосз-ная школ^-оймлнар по вычислительным сетям" .Нооква-Таш-кант,Ь79.

¿5» ¿ацкевич В.1., Кодификация криптографической системы для вычисли едышх сетей. СО."У Всесоюзная икола-оеминар оо вычислительным сетям". Ииоква-Владивосток,I9BU.

26; 1ацкевич B.I., Шакарян P.A. Применение нормальных инверсных представлений в задачах цифрового регулирования* Сб."Материалы У1 конференции по иетродогии,,«Тбияион,1982,

27. Оацкавич tí.1* Некоторые методы декодирования * оиотеиа счисления в оотаточных классах. Сб.йШ Международный оиыпозиуы по теории информации".Москва-Тбидиои,1979.

28. Яацкевич В.д. Корретируюг'е возможности некоторых базисных представлений непозиционных систем. Со,"1У Всесоюзная шкода-семинар по вычислительным овтям,,,иоаква-Таикант,1979.

29. Дацкович В.д. Адаптивный метод нахождения цихеградышх характеристик прк нвпоаициоиннх параллельных зычислвш»-ях. Со."Вопросы разработки и ириманения средств вычислительной техники"(Материалы республиканской конкуренции).Тбидиои, 1982.

30. .шцкевич В.А.,' Ревазишвили Г.Г. Система Иеркля-Хеллмэ-

на о распараллеливанием вычислений. Сб."УШ Всесоюзная

шкода-оеыинар но вычислительным сетям",П.,1983. i ■ .

31. Аацкевич ü.¿. Специальные базисные представления нешо-

виционных систем для метрологических задач. Труды института вычислительной математики."Математическая и техническая кийерномка". jüJ:2, 19Й.

32. оацкевнч В.д., Избыточном* для опхииизации опециадь-ных арифметических свойств кода. Труды 9-го оимнозиума по иробдемо иаОыточаооти в информационна системах.!., 1986.

33« Ааодевач В. А., Чачалалвилл А.Р. Уорройотво для определения знака чнола а скотене оотаточных клаооов. Авторское свидетельство -на изобретение & I25448U. Государственный рееотр изобретений СССР. Бюллетень изобретений от 1.5.Ъб.

34. лацкевич в. а. О использования отруктуры представавши!

инфорнацин для заяиты арифнетнчвско8 обработки в оете-зы1 оиотенах. Труды Jüi ВсесопзяоЙ вколи-оеиинара по вычислительный сетяи. Мооква-Одвоса.ХУЬ?.

35. хацковяч а.д. Модификация нетода быотрого уиногзивя для высокопроизводительных систем. Сб."Математическая я техническая кибернетика","Мецяиереба",Тбнлиов,1987.

36. хадкзвич В.Х, Избыточность для декодировааия на оовово адгоратнов о модулярной арш$иотдкоВ. л об.' иоотой иелду-híipoahüfl симпозиум по тоорин информации".ваоть П, Ноо-ава-Таакс: г,1У84.

37. лацкеанч ¡i.л. Сопряженные но рангу пиологыо представления, Сб."Девятая Всесовзпал конференция по теория, коднроганил я передача информации",часть I. Одесоа,1У88

3U# хащеввич Э.А, Переходные пар-'ыетрм ступенчатых нопевк-цвошшх снстен. Сб."1!атенаилоокоя в техническая кибернетика", 3.24, анп.2. Тбшшза,1Уй*.

$9, 1авдеаач В.¿Сорроктарувцав маиохиоота оолряхваных послодоватэльностеа параше прохзлодоигЛ. Сб."х опнпоза-уи по проблеме азбыточноотл s шфориацхбвшх овотенах".

40. Хадкович В.х. Быстрое умножения для аыовхешроиамдятоль-иых састем. Труды Иеадаародной конференции "¿ыооксдро-аалодлтвлмме хычхедятвльяно cácteas s упрааляаля л вау*-

' aux хсолвдомвхях"«!!., 19Я.