Многомерный статистический анализатор

ОП ИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик ои 976449.СССР но делам изобретений н открытий(72.) Авторы изобретения Пензенский политехнический институт( 54 ) МНОГОМЕРНЫЙ СТАТИСТИЧЕСКИЙ АНАЛИЗАТОР 20 Изобретение относится к вычислительной и измерительной технике и может быть использовано при проведенииэкспериментальных исследований, связанных с многомерным статистическиманализом коррелированных многомерныхслучайных процессов,Известна схема многомерного ассо- .циативного анализатора, работа которого основанана том, что вначалепроводится предварительный эксперимент, в котором выявляются и записы-,ваются в каталог наиболее вероятныесобытия, а затем основной эксперимент, когда с помощью ассоциативногозапоминающего устройства происходитнакопление статистической информацииоб отобранных в предварительном экс"перименте событиях11,Данный анализатор характеризуетсяотносительно низким быстрЬдействием,так как время анализа возрастает за счет проведения предварительного экс"перимента. Наиболее близким к предлагаемому по технической сущности является многомерный статистический анализатор, содержащий регистр адреса, запоминающее устройство, устройство управления, регистр 1 арифметического устройства, выходное устройство и предварительное запоминающее устройство, информационные входы которого соединены с выходами источников реализации случайного процесса, а выход - с входом регистра адреса, выход которого соединен с адресным входом запоминающего устройства, управляющие вход и выход которого соединены соответственно с выходом и входом устройства управления, а информационные вход и выход " с первым информационным выходом и информационным входом регистра 1 арифметического устройства, второй информационный выход ко976449 М фс с Ъс сф фс щ О Составитель Э, Сечинактор Т. Кугрышева Техред М. Гергель Коррек Решетн Заказ 90 4 лиал ППП "Патент", г. Ужгор Проект 05/76 8 НИИПИ Государс по делам изоб 113035, Москва, Тирак 731 Подписнвенного комитета СССРретений и открытийЖ, Раушская наб., д. 4/5торого соединен со входом выходногоустройства 2 .Недостатками данного анализатора являются неэффективное использование памяти и, вследствие этого, 5сложность и низкое быстродействиепри анализе многомерных коррелированных процессов,Неэффективное использование памяти анализатора обусловлено тем; что 1 Оздесь поступающий информационныйкод служит адресом ячейки запоминающего устройства, в которой хранится соответствующий данному коду элемент гистограммы. Бсли же 15параметры анализируемого случайногопроцесса связаны между собой корреляционными зависимостями, то количество различных кодов, поступившихв ходе эксперимента на вход анализатора, будет намного меньше теоретически возможного. 8 следствие этогозначительная часть ячеек запоминающего устройства останется неиспользуемой. 25Кроме того, повышение размерности анализа ведет к резкому увеличению объема исходной информации,что делает невозможным применениебыстродействующих оперативных запоми- щнающих устройств для хранения статистической информации, Использование запоминающих устройств большойемкости, но с низким временем доступа к данным резко усложняет анализатор и снижает его быстродействие,Цель изобретения - упрощение анализатора и повышение быстродействия Поставленная цель достигается тем,40 что в многомерный статистический анализатор, содержащий предварительное запоминающее устройство, информационные входы которого являются соответствующими входами анализатора, регист адреса, выход которого соединен с адресным входом блока памяти, управляющие вход и выход которого подключены соответственно к первым управляющим выходу и входу блока управления , первые информационные вход и выход блока памяти соединены соответственно с первыми ин-.формационными выходом и входом регистра, управляющий вход которого подключен к второму управляющему выходу блока управления, второй информационный выход регистра соединен с блоком вывода результата, а третий информационный выход - с первым разрядным входом регистра адреса, введеныблок разрешения коллизий и блокпреобразования "ключа" в адрес, выход которого соединен с вторым разрядным входом регистра адреса, авход блока преобразования "ключа" вадрес объединен с вторым информационным входом блока памяти, первым информационным входом блока разрешения коллизий и соединен с выходомпредварительного запоминающего устройства, управляющий вход которого подключен к третьему управляющему выходублока управления, четвертый управляющий выход которого соединен с управляющим входом регистра адреса,а пятыйуправляющий выход -с первым управляю -щим входом блока разрешения коллизий,управляющий выход которого подключенк второму управляющему входу блокауправления, второй информационныйвход и первый и второй информационные выходы блока разрешения коллизий соединены соответственно с первым информационным выходом блока памяти, с третьим разрядным входомрегистра адреса и с вторым информационным входом регистра,Блок разрешения коллизий может состоять из схемы сравнения и регистраадреса переполнения, первый и второйвыходы которого являются первым ивторым информационными выходами блока, третий выход регистра адреса переполнения соединен с первым информационным входом схемы сравнения,второй и третий входы которой являются соответственно первым и вторыминформационными входами блока, выход схемы сравнения является управляющим выходом блока, а управляющийвход схемы сравнения объединен с управляющим входом регистра адреса переполнения и является управляющим вхо-дам блока.Блок преобразования "ключа" в адрес может быть выполнен в виде многовходового сумматора и состоять из цепочки последовательно соединенногозапоминающего устройства, сумматора ирегистра адреса, при этом вход запоминающего устройства является входомблока, а выход регистра адреса является выходом блока,Блок управления может состоять изцепочки последовательно соединенныхгенератора, счетчика и дешифратора,управляющие входы которого являются49 6 Блок 3 разрешения коллизий предлагаемого анализатора может содержатьрегистр 9 адреса переполнения, первыйи второй выходы которого являются первым и вторым информационными выходамиблока 3, и схему 1 О сравнения, первый информационный вход которой соединен с третьим выходом регистра 9адреса переполнения, а второй и третийвходя являются соответственно первым ивторым информационными входами блока3. выход схемы 10 сравнения являетсяуправляющим входом блока 3, а управляющий вход схемы 10 сравнения объединен с управляющим входом регистра9 адреса переполнения и является управляющим входом блока 3,Блок 2 преобразования "ключа" в адрес может быть выполнен в виде многовходового сумматора и состоять из цепочки последовательно соединенных запоминающего устройства 1, сумматора 2и регистра 4 адреса, при этом входзапоминающего устройства 1 являетсявходом блока, а выход регистра 4 адреса является выходом блока.Кроме того, блок 6 управления может быть выполнен в виде цепочки последовательно соединенных генератора11, счетчики 12 и дешифратора 13,управляющие входы которого являютсясоответственно первым и вторым управляющими входами блока, а выходы дешиФратора 13 являются соответственно управляющими выходами блока 6,Принцип работы предлагаемого многомерного статистического анализатора основан на использовании некоторой нелинейной функции,формующей адреса ячеек блока памяти в заданном диапазонев зависимости от исходного "ключа".Под "ключом" понимается числовой код.представляющий собой одну реализацию слуцайного процесса.Из "ключа", поступающего на входанализатора, с помощью нелинейнойфункции формируется адрес А ячейкиблока памяти, соответствующий данному "ключу". Если эта ячейка свободна, то в нее записывается "ключ".Ячейка с адресом А+отводится дляпостроения гистограммы "ключа", т.е.ее содержание увеличивается на единицу. На этом обработка данного "ключа" заканчивается, Если ячейка с адресом Аоказывается занятой, выполняется анализ на равенсво текущего"ключа" и "ключа", ранее записанногов эту ячейку, При их совпадении дост 5 9764 соответственно первым и вторым управляющими входами блока, а выходы дешифратора являются соответственно управляющими выходами блока.На фиг, 1 изображен предлагаемый многомерный статистический анализатор; на фиг.2 - блок-схема, поясняющая принцип работы анализатора; на фиг. 3 - пример реализации блока управления; на фиг. 4 - пример возмож О ной реализации блока преобразования "ключа" в адрес, когда "ключ" разбивается на три группы разрядов; на фиг. 5-9 - временные диаграммы, поясняющие работу блока управления. 15Анализатор содержит предварительное запоминающее устройство 1, информационные входы которого являются соответствующими входами анализатора, а выход соединен с входом бло ка 2 преобразования нключа" в адрес и первым информационным входом блока 3 разрешения коллизий, выход блока 2 преобразования "ключа в адрес соединен с вторым разрядным входом 25 регистра 4 адреса, выход которого соединен с адресным входом блока 5 памяти, управляющие вход и выход которого подключены соответственно к первым управляющим выходу и входу блока 6 .управления, второй управляющий выход которого подключен к управляющему вхо ду регистра 7, первые информационные выход и вход которого соединены соответственно с первыми информационными входом и выходом блока 5 памяти, а второй и третий информационные выходы - соответственно с блоком 8 вывода результата и первым разрядным входом регистра 4 адреса, управляющий вход которого соединен с четвертым управляющим выходом блока 6 управления, третий управляющий выход которого подключен к управляющему входу предварительного запоминающего устройства 1, выход которого соединен с вторым информационным входом блока 5 памяти, первый информационный выход которого соединен а вторым информационным входом блока 3 разрешения колли 50 зий, первый и второй информационные выходы которого соединены соответственно с третьим разрядным входом регистра 4 адреса и вторым информационнымвходом регистра 7, а управляющие55 вход и выход - соответственно с пятым управляющим выходом и вторым управляющим входом блока 6 управления.управляющем выходе блока 6 управления разрешает запись адреса, сфор мированного блоком 2 преобразования "ключа" в адрес, в регистр 4 адреса по второму разрядному входу. Разрядность регистра 4 адреса меньше разрядности предварительного запоминающего устройства 1 и соответствует размерам основной области памяти, в которой хранится статистическая информация. Затем блок 6 управления Формирует сигналы на первом и пятом управляющих выходах. При этом происходит обращение к блоку 5 памяти по адресу, хранящемуся на регистре 4 адреса, и в схеме сравнения О блока 3 разрешения коллизий осуществляется анализ содержимогО данной ячейки, поступающего на второй информационный вход схемы 10 сравнения. Бсли ячейка свободна, то схема 10 сравнения формирует на выходе сигнал, поступающий на второй управляющий вход блока 6 управления , который в свою очередь формирует сигналы на первом и третьем управляющем выходах, разрешая тем самым перепись текущего "ключа" в данную ячейку блока 5 памяти по второму информационному входу. В следующем такте работы сигнал на четвертом управляющем выходе блока 6 управления увеличивает на единицу содержимое регистра 4 адреса. Затем содержимое ячейки, имеющей вновь сформированный адрес, с подачей разрешающих. сигналов по первому и второму управляющим выходам блока 6 управления переписывается в ;регистр 7, в следующем такте увели,чивается на единицу и затем вновь запоминается в блоке 5 памяти по тому же адресу. Таким образом, осуществляется . построение гистограммы для данного "ключа". Обработка на этом закончена и анализатор готов к приему следующего "ключа".1Гсли в результате анализа в блоке 3 разрешения коллизий оказывается, что ячейка занята, т.е. на четвертом такте сигнал на втором управляющем входе блока 6 управления отсутствует (фиг.6), то в следующем такте блок 6 управления формирует сигналы на первом, третьем и пятом управляющих выходах. При этом "ключ", хранящийся в данной ячейке, поступает на второй информационный вход схемы 10 сравнения, на первый информационный вход которой с вы хада пред 7 976449 8раивается гистограмма по адресу А+ иобработка текущего значения "ключа"завершается, При несовпадении - коллизии , когда различные "ключи" адресу.ются к одной и той же ячейке, специальная схема формирует новое значение адреса А для текущего "ключа", послечего повторяется анализ содержимогоячейки с адресом А , Зта процедураповторяется до тех пор, пока не будет 10найдена ячейка, хранящая данный "ключ".либо свободная.В среднем, для размеще.ния любого "ключа" требуется 1-2 сравнения. По окончании эксперимента, либопо заполнении памяти осуществляется Звывод результатов на внешний носитель,Многомерный статистический анализа". тор работает следующим образом,Сигнал, формируемый на третьемуправляющем выходе блока 6 управления,20разрешает записать числовой код, поступивший на вход, анализатора отвнешних источников реализа.ций, в предварительное запоминающее устройство 1,разрядность которого зависит от размерности анализируемого процесса(фиг. 5). Блок 2 преобразования "ключа" в адрес путем нелинейного преобразования "ключа" формирует адресячейки блОка 5 памяти е которой должен храниться данный "ключ",Работа блока 2 преобразования"ключа" в адрес может проходить следующим образом,"Ключ", представляющий собой циф" Зфровой двоичный код, поступает в пред варительное запоминающее устройство 1,которое может быть выполнено в видерегистра, Выходы предварительного40запоминающего устройства, 1 разбиваются на группы по и разрядов, где и .определяется размером основной области памяти, равным 2в которуюипроисходит первоначальная адреса 45ция "ключей", Сумматор 2 выполняет операцию сложения соответствующих разрядов различных групп выходовпредварительного запоминающего устройства 1 и результат запоминается врегистре 4 адреса, разрядность которого равна и. Гсли общее число разрядов предварительного запоминающего устройства 1 не кратно и, то последняя группа с колицеством разрядов меньше и, условно дополняется55до и нулями и участвует в операциисложения наравне с остальными группами разрядов, Сигнал на четвертомварительного запоминающего устройства1 поступает текущий "ключ". При совпадении этих "ключей" схема 10 сравнения на выходе формирует сигнал, поступающий на второй управляющий вход бло"5ка 6 управления, Начиная с седьмоготакта, обработка аналогична описанному выше случаю: содержимое регистра 4 адреса увеличивается на единицуи т.д. Если последняя проверка вы Оявляет неравенство "ключей", т.е.сигнал на втором управляющем входеблока 6 управления в шестом такте отсутствует (фиг. 7) , то адрес ячейки блока 5 памяти, отводимой для хранения текущего "ключа", формируется блоком 3 разрешения коллизий. Этоможет быть реализовано следующимобразом,Каждый элемент гистограммы содержит три ячейки: первая хранит "ключ",вторая- соответственно гистограммуданного "ключа", третья - адрес ячейки, к которой следует обратиться дляразмещения текущего "ключа" при воз в 25никновении коллизии. В этом случаеработа происходит следующим образом.1.а .Блок 6 управления формирует подряддва сигнала на четвертом управляющемвыходе, которые увеличивают на двасодержимое регистра 4 адреса. Затем,при наличии сигналов на первом и втором управляющих вь 1 ходах блока 6 управления, на регистр 7 по первому информационному входу переписывается со 35держимое ячейки с вновь сформированным адресом, которое в свою очередьявляется адресом, .к которому следует обратиться для размещения текуще 40го "ключа" при коллизии, В следующемтакте этот адрес анализируется в схеме 10 сравнения. Если он отлицен отнуля, это значит, что ранее в данной. ячейке возникала коллизия. В этом случае схема 10 сравнения в одиннадца 45том такте формирует сигнал на второмуправляющем входе блока б управления, по которому он затем выставляет сигналы на втором и цетвертом управляющих выходах, что вызывает пере50пись содержимого регистра 7 в регистр4 адреса.Затем блок 6 управления разрешает схеме 10 сравнения сравнить междусобой текущий "ключ", поступающий на55первый информационный вход, и "ключ",хранимый в ячейке с вновь сформирован.ным адресом, поступающим из блока 5памяти на второй информационный вход. Дальнейшая работа аналогично описанной выше, начиная с шестого такта.Если адрес, извлеченный на десятом шаге, оказывается равным нулю, т.е, сигнал на втором управляющем входе блока 6 управления отсутствует в одиннадцатом такте (фиг, 8), это значит, что ранее коллизий в данной ячейке не возникло и размещение текущего "ключа" в памяти анализатора возлагается на блок 3 разрешения коллизий, Это может происходить следующим образом."Ключ" адресуется к дополнительной области памяти, начинающейся с некоторого заранее определенного адреса. Размеры этой дополнительной области составляют 3-Д от основчой области памяти. Блок 6 управления формирует сигналы на втором и пятом управляющем выхо" дах, что вызывает перепись адреса первой свободной яцейки дополнительной области памяти, хранящегося в регистре 9 адреса переполнения, в регистр 7, Затем этот адрес по сигналам на первом и втором управляющих выходах блока 6 управления запоминается в ячейке блока 5 памяти, адрес которой в данный момент хранится в регистре 4 адреса. Таким образом, организуется связь между "ключами", которые были адресованы в одну и ту же ячейку, В следующем такте содержимое регистра 9 адреса переполнения по третьему разрядному входу поступает в регистр 4 адреса и по этому новому адресу в блок 5 памяти записывается "ключ" из предвари тельного запоминающего устройст-, ва 1. Затем адрес в регистре 4 адреса сигналом на четвертом выходе блока 6 управления увеличивается на единицу. После этого достраивается гистограммы, для чего содержимое ячейки с вновь сфоомированным адресом извлекается на регистр 7, сигналом на втсом управляющем выходе блока 6 управления увелицивается на единицу и затем вновь запоминается в блоке 5 памяти по тому же адресу. На следующем шаге для обеспечения эффективного размещения вновь поступающих "ключейнеобходимо сформировать адрес первой свободной ячей" ки в дополнительной области памяти, где мог быть размещен вновь поступивший "ключ при возникновении кол11 97 лизии.С этой целью содержимое регистра 9 адреса переполнения сигналами на втором управляющем выходе блока б управления увеличивается на три.При выходе эа пределы разрядной сетки регистра 9 адреса переполнения на втором управляющем входе блока 6 управления формируется .сигнал который говорит о том, что дополнительная область памяти полностью занята и никакие "новые", т.е. ранее не встречавшиеся, "ключи" размещаться больше не могут . При этом можно либо прекратить эксперимент, либо продолжить накопление статистической информации об уже поступивших "ключах",По окончании эксперимента для вывода результатов оператору блок 6 уп- Зф равления последовательно формирует в предварительном запоминающем устройстве 1 коды всех возможных "ключей" (фиг. 9) . Из них блок 2 преобразования "ключа" в,адрес формиру- И ет адреса ячеек блока 5 памяти., в которых хранятся соответствующие элементы гистограммы. Эта информация извлекается на регистр 7, откуда поступает на блок 8 вывода резуль,- ЗО тата. 6 чч 9 12 Таким образом, эффективное исполь эование памяти позволяет упростить и повысить быстродействие анализатора. Формула изобретения 1.Иногомерный статистический анализатор, содержащий предварительыое запоминающее устройство, информационные входы кдторого являются соответствующими входами анализатора, ре" гистр адреса, выход которого соединен с адресным входом блока памяти, управляющие вход и выход которого подключены соответственно к первым управляющим выходу и входу блока уп равления, первые информационные вход и выход блока памяти соединены соответственно с первыми информационными выходом и входом регистра, управляющий вход которого подключен к второму управляющему выходу блока управления, второй информационный выход регистра соединен с блоком вывода результата, а третий инфор 33 40 4 Я И мационный выход " с первым разрядным входом регистра адреса, о т л ич а ю щ и й с я тем, что, с целью упрощения анализатора и повышения быстродействия, в него введены блок разрешения коллизий и блок преобра.эования "ключа" в адрес, выход которого соединен с вторым разряднымвходом регистра адреса, а вход блока преобразования "ключа" в адрес объединен с вторым информационным входом блока памяти, первым информационным входом блока разрешения коллизий и соединен с выходом предварительного запоминающего устройства, управляющий вход которого подключен к третьему управляющему выходу блока управления, четвертый управляющий выход которого соединен с управляющим входом регистра адреса,а пятый управляющий выход - с первымуправляющим входом блока разрешения коллизий; управляющий выход которого подключен к второму управляющему входу блока управления, второй информационный вход и первый ивторой информационные выходы блокаразрешения коллизий соединены соответственно с.первым информационным выходом блока памяти, с третьим разрядным входом регистра адреса и свторым информационным входом регист"ра. 2, Анализатор по и, 1, о т л ич а ю щ и й с я тем, что, блок разрешения коллизий состоит из схемы сравнения и регистра. адреса переполнения, первый и второй выходы которого являются первым и вторым информвционными выходами блока, третий выход регистра адреса переполнения соединен с первым информационным входом схемы сравнения, второй и третий входы которой являются соответственно первым и вторым информационными.входами блока, выход схемы сравнения является управляющим выходом блока, а управляющий вход схемы сравнения объединен с управляющим входом регистра адреса переполнения и является управляющим входом блока.3. Анализатор по и, 1, о т л ич а.ю щ .и й с я тем, что блок преобразования "ключа" в адрес выполнен в виде многовходового сумматора и состоит из цепочки последовательно соединенных эапоминающе13 976449 14го устройства, сумматора и регист- первым и вторым управляющими входамира адреса, при этом вход запоминаю- . блока, а выходы дешифратора являютщего устройства является входом ся соответственно управляющими выблока, а выход регистра адРеса явля- ходами блока.ется выходом блока.54. Анализатор по и, 1, о т л иИсточники информации,ч а ю щ и й с я тем, что блок управ- принятые во внимание при экспертизе, ления состоит из цепочки последова. Курочкин С. С. Многомерные стательно соединенных генератора, счет" тистические анализаторы, М., Атомчика и дешифратора, управляющие вхо р издат, 1968, с. 311,ды которого являются соответственно. 2. Там же. с. 11 (прототип).