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

(5) Изобрете НЬИ СТАТИСТИЧЕСК носится к облас измерительной ти вычислительнои ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТ Н АВТОРСКОМУ СВИДЕТЕПЬСТВ(56) Курочкин С.тистические анализдат, 1968, с,Авторское свидетелУ 976449, кл. С 06 Р техники. Цель изобретения - повышение быстродействия и расширениякласса решаемых задач. Для этогоанализатор содержит коммутатор,дополнительный (второй) блок преобра.зования ключа в адрес, которые имеют характерную для данного решенияструктуру, как и блок управления,соединенные с остальными узлами ана"лизатора в соответствии с алгоритмом функционирования. Изобретениеможет быть использовано при статистическом анализе каналов связи,контроле качества носителей информации магнитных и оптических .дисковых запоминающих устройств при проведении статистических экспериментовв ядерной физике и т.п.Составитель З.СенинаТехред О,Гортвай дактор Л,Пчелинска ПодписноССР акал 378 Гираж ВНИИПИ Государств по делам изобр 3035 р москва, 1-3рытнинаб д,4/ дприятие Г,У еское ср олиграФ иэводственн нного коми тений и от, Изобретение относится .к вычислительной и измерительной технике и может быть использовано при проведении экспериментальных исследований, связанных с многомерным сгатистическим анализом случайных процессов.Цель изобретения - повышение быстродействия анализатора и расширение класса решаемых задач.На фиг. 1 представлена схема многомерного статистического анализатора; на фиг, 2 - схема второго блокапреобразования ключа в адрес; на фиг. 3 - схема коммутатора; иа фиг, 4 - схема блока управления; на фиг, 5 - 8 - временные диаграммы, поясняющие работу блока управления,Анализатор содержит предварительное запоминающее устройство (ЗУ) 1, входы которого являются соответствующими входами анализатора, первый блок 2 преобразования ключа в адрес, выход которого соединен с информационным входом первого регистра 3 адреса, второй блок 4 преобразования ключа в адрес, выход которого соединен с информационным входом второго регистра 5 адреса, вьйод которого соединен с вторым входом коммутатора 6, выход которого соединен с адресным входом блока 7 памяти, первые управляющие вход и выход которого соединены соответственно с первыми управляющими выходами и входом блока 8, управления, вторые управляющие вход и выход которого соединены соответственно с выходом и управляющим входом схемы 9 сравнения, первый информационный вход которой объединен с информационным входом регистра 10 и соединен с информационным выходом блока 7 памяти, первый информационный вход которого соединен с первым информационным выходом регистра 10, второй информационный выход которого соединен с входом блока 11 вывода результата, а управляющий вход - с шестым управляющим выходом блока 8 управления, пятый управляющий выход которого соединен с управляющим входом коммутатора 6, первый информационный вход которого соединен с выходом первого регистра 3 адреса, управляющий вход которого объединен с управляющим входом второго регистра5 адреса и соединен с четвертым управляющим выходом блока 8 управления третий управляющий выход которого со. единен с управляющим входом предварительного ЗУ 1, выход которого соединен с входами блоков 2 и 4 преобразования ключа в адрес и вторыми входами схемы 9 сравнения и блока 7 памяти.Второй блок 4 преобразования ключа в адрес. (фиг.2) может состоятьиз группы 12 элементов ИСКЛЮЧАЮЩЕЕ10 ИЛИ, входы которых соединены с соответствующими разрядами предварительного ЗУ 1, а выходы являются соответствующими выходами блокаКоммутатор 6 (фиг.3) может содер 1 жать группу 13 элементов 2 И-ИЛИ иэлемент НЕ 14, вход которого объединен с первыми входами элементов2 И-ИЛИ и является управляющим входомкоммутатора 6, выход элемента НЕ 14о соединен с вторыми входами элементов 13 2 И-ИЛИ, третьи и четвертыевходы которых являются соответственно первым и вторым информационнымивходами коммутатора 6, а выходы элед ментов 2 И-ИЛИ 13 являются выходамикоммутатора 6.Блок 8 управления (фиг.4) можетсостоять иэ генератора 15, счетчика 16, дешифратора 17, регистра 18,ЗОэлемента 2 И-ИЛИ 19 и группы 20 мультиплексоров, выходы которых являютсяуправляющими выходами блока 8, аинформационные входы объединены спервыми входами элемента 2 И-ИЛИ 19:и соединены с выходами регистра 18,информационные входы которого объедииены между собой и являются вторымуправляющим входом блока 8, а входысинхронизации регистра 18 объединены с вторыми входами элемента 2 ИИЛИ 19 и соединены с выходами дешифратора 17, вход которого обьединен с адресными входами мультиплексоров 20 и соединен с выходом счетчика 16, информационный вход которо 4 го соединен с выходом генератора 15,вход сброса соединен с выходом элемента 19 2 И-ИЛИ а вход синхронизации являетсяпервым управляющимвходом блока 8,Работа анализатора основана на следующем способе размещения ключей. Область памяти, отводимая для хранения данных, разбивается на две непересекающиеся подтаблицы так, чтобы количество адресов в каждойиз них М 1 и М 2 были равны между собой . Формируется адрес А 1 для подтаблицы 1. Если при обращении по этомуЗ 124 адресу коллизии не возникает, то для текущего ключа достраивается гистограмма. Если коллизия возникает, происходит обращение к подтаблице 2 по адресу А 2, вычислчемому независи мо от А 1. Если и здесь возникает коллизия, выполняется повторное обращение к подтаблице 1, но уже по адресу А 2. Наконец, если и здесь происходит коллизия, осуществляется обращение к подтаблице 2 по адресу АВ результате преобразования ключа в адрес получают равномерное распределение адресов. Тогда (Х - число ключей, М - количество;адресов) вероятность того, что число ключей, адресуемых к данной ячейке, равно К подчиняется биномиальному закону и определяется выражением: где р = 1/М - вероятность попадания любого ключа в а-й адрес (а=1,2,у М)-- 1/М - вероятность попадания любого ключа в адрес, отличный от а.Так как М достаточно велико, а произведение Ы-р имеет один порядок, с количеством ключей, которые могут разместиться по одному адресу, можно воспользоваться пуассоновским приближением для биномиального расп ределения: где 3 =Р.Отсюда можно вычислить среднеечисло ключей, приходящихся на одинадрес и процентное содержание ключей размещенных в памяти где ш=Н/М - коэффициент загрузкиключей;Б - количество ключей, которые могут разместитьсяпо одному адресу.Исходя из сказанного выше, процентное содержание ключей , которые могут быть размещены н памяти с помощью описанного алгоритма, опоределяется следующим выражением: р=8(тп 1,2) + 8(тп 2,2) 5(100 - д(тп 1 2)100 М 2 Как показывают расчеты по формуле (1) применение описанного алго)ритма позволяет разместить все 10 ОЖпоступающих ключей в памяти (приш 1) без указания адресов связей.Многомерный статистический анализатор работает следующим образом.Сигнал, формируемый на третьемуправляющем выходе блока 8 управления разрешает записать. числовой код,поступивший на вход анализатора отвнешних источников реализаций, вЗОпредварительное ЗУ 1, разрядностькоторого зависит от размерности анализируемого процесса. Блоки 2 и 4преобразования ключа в адрес формируют независимо друг от друга адресаячеек блока 7 памяти в задайном диапазоне,Первый блок 2 преобразования ключа в адрес может быть выполнен в виде многовходового сумматора и рабо 40тает следующим образом.Ключ, представляющий собой цифровой двоичный код, поступает в преднарительное ЗУ 1, которое может бытьвыполнено н виде регистра. Выходыпредварительного запоминающего устройства 1 разбиваются на группы поп разрядов, причем и определяетсяразмером отводимой для хранения данных области памяти, равной 2" ячеек.Блок 2 преобразования ключа в адрес,реализованный в виде сумматора, выполняет операцию сложения соответст.вующих разрядов различных групп выходов предварительного ЗУ 1 и результат запоминается н первом регистре 3 адреса, разрядность которого ранна и. Если обшее число разрядов предварительного ЗУ 1 не кратно,"ггбгО и, то послепняя группа с количеством разрядов меньше п условно дополняется до п нулями и учасьвует в операции сложения наравне с остальными группами разрядов,Бторой блок 4 преобразования клю - ча в адрес может быть выполнен в ви. де группы элементов 11 СКЛОЧЛ)ОЩЕГ И 1 Р каждый из которых реализует операцию сложения по модулю 2, При этом входы каждого элемента ИСКЗЦОЧЛ 1 ОЩЕЕ ИЛИ 12 соединены с выходами соответствующих разрядов различных группвыходов предварительного ЗУ 1.Сигнал на четвертом управляющем выходе блока 8 управления разрешает записать адреса, сформированные первым и вторым блоками 2 и 4 преобразования кпюча в адрес, соответственно в первый и второй регистры 3 и 5 адреса.Старшие разряды регистров 3 и 5могут быть выполнены в виде Т-триггеров, начальное состояние которыхравно соответственно "1" и "0". Этосделано для того, чтобы иметь возможность адресоваться поочередно кпервой (диапазон изменения адресовот 1 до 2 г ) и второй (диапазон изменения адресов от 2 + 1 до 2 )половинам отведенной для храненияданных области памяти, Таким образомдостигается разбиение памяти на двенепересекающиеся подтаблицы, Работапри этом происходит следующим образом.Появление сигнала на четвертомуправляющем входе блока 8 управления (фиг.4) заставляет старшие раз - ряды первого и второго регистров 3 и 5 переключить соответственно в состояние 0 и "1 . Затем с подачей разрешающих сигналов из блока 8 управления адрес из первого регистра 3 адреса через коммутатор б поступает на адресные входы блока памяти.Коммутатор б работает следующимобразом.Единичный сигнал на пятом управляющем выходе блока 8 управления разрешает прохождение адреса с первого регистра 3 адреса через первые информационные входы элементов 2 И-И 31 И 13 на выход коммутатора 6.При этом низкий уровень на выходе элемента НЕ 14 запрещает прохождение адреса с второго регистра 5 адреса через вторые информационные вхо г ( Ьды элемен гон 2 Р 1-ИИ 13. 1 изкий уровень на пятом управляющем;выходе блока 8 управления разрешает прохождение на выход коммутатора б адресас второго регистра 5 адреса, в товремя как выходы первого регистра 3адреса блокируются,После установления адреса на адресных входах блока 7 памяти содержимое ячейки с данным адресом извлекается на регистр 10 и на схему 9сравнения, где происходит сравнениесодержимого этой ячейки с нулем,Память при этом может быть организована так, чтобы каждая запоминающая ячейка хранила и ключ, и гистограмму (например, для хранения ключа выделяются определенные разрядыячейки), Тогда на схему 9 сравненияпоступает группа разрядов, соответствующая ключу, а на регистр 10группа разрядов ячейки, соответствующая гистограмме. Если схема 9сравнения обнаруживает, что даннаяячейка свободна, т.е. ее содержимое1 ивно нулю, она вырабатывает сигнал,который поступает на второй управляющий вход блока 8 управления.Блок 8 управления увеличивает со -держимое регистра 10, осуществляятем самым достраивание гистограммы,и разрешает затем запись ключа изпредварительного ЗУ 1 и гистограммыиз регистра 1 О в блок 7 памяти поадресу, хранящемуся на первом регистре 3 адреса, Обработка ключазавершена.Если в результате проверки в схе.ме 9 сравнения оказалось, что данная ячейка уже занята, т.е, ее содержимое не равно нулю (фиг.5),блок 8 управления вырабатывает сигналы на первом, втором, третьеми пятом управляющих выходах. Содержимое адресуемой ячейки (разряды,соответствующие ключу) поступаетна первый информационный вход схемы9 сравнения, на второй информационный вход которой поступает ключ изпредварительного ЗУ 1 и происходитих сравнение. Если проверяемые ключи совпадают, схема 9 сравнения вырабатывает сигнал, который поступаетна. второй управляющий вход блока 8управления. Блок 8 управления сигналом на шестом управляющем выходе увеличивает на единицу содержимое регистра 1 О (достраиваетсягистограмма), которое в следующемIтакте работы запоминается в соответствующей ячейке блока 7 памяти.Обработка данного ключа завершена.Если в результате анализа адресуемой ячейки оказалось, что оназанята ключом, отличным от вновьпоступившего, т.е, в шестом тактесигнал на втором управляющем входеблока 8 управления отсутствует(фиг.6), происходит обращение квторой половине адресуемой областипамяти (диапазон адресов от 2 + 1до 2 п ). С этой целью блок 8 управления устанавливает на пятомуправляющем выходе низкий уровень,разрешая тем самым прохождение на. адресные входы блока 7 памяти. черезкоммутатор адреса 6, хранящегося навтором регистре 5 адреса (старшийразряд второго регистра 5 адресахранит единичный уровень), Происходит обращение к блоку 7 памяти, содержимое адресуемой ячейки извлекается на регистр 10 и разряды, соответствующие ключу, поступают насхему 9 сравнения, где сравниваются с нулем. Если проверяемая ячейкасвободна, схема 9 сравнения вырабатывает на выходе единичный сигнал,блок 8 управления увеличивает содержимое регистра 10,на единицу(достраивается гистограмма), ключ из предварительного ЗУ 1 и гистограмма изрегистра 10 переписывается в ячейку памяти. Обработка ключа завершена.Если анализируемая ячейка занята,.сравниваются ключи из предварительного ЗУ 1 и .данной ячейки, Если ключи совпадают, достраивается гистограмма и обработка заканчивается.Если ключи не совпадают (Фиг,7),выполняется обращение к второй половине памяти (адреса от 2 и + 1до 2 ) по адресу, хранящемуся йапервом регистре 3 адреса. С этойцелью блок 8 управления вырабатывает на первом, втором, четвертом,пятом и шестом управляющих выходахединичные сигналы. При этом триггеры в старших разрядах первого и второго регистров 3 и 5 адреса переходят соответственно в состояние "1"и "0" и разрешается обращение к блоку 7 памяти по Йдресу, хранящемусяна первом регистре 3 адреса. Послеэтого повторяется анализ содержимого адресуемой .ячейки аналогично описанному выше,8Если и данная ячейка оказалась занятой ключом, отличным от вновь поступившего, происходит обрашение к первой половине памяти (адреса отдо 2 " ) по адресу, хранящемуся на втором регистре 5 адреса. Для это. го блок 8 управления устанавливает на четвертом управляющем выходе низкий уровень, разрешая прохождение на адресные входы блока 7 памяти адреса из второго регистра 5 адреса. Затем повторяется анализ содержимого адресуемой ячейки аналогично описанномуЕсли в результате работы описан" ного алгоритма оказывается, что вновь поступивший ключ нельзя разместить в основной памяти, необходимо или отбросить данный ключ (как маловероятный), и либо выделить небольшо-го размера дополнительную память, где такого типа ключи размещены последовательно.По окончании эксперимента блок 8 управления может последовательно.Формировать в предварительном ЗУ 1 коды возможных ключей, из которыхблоки 2 и 4 преобразования ключа вадрес формируют адреса ячеек блока7 памяти, в которых хранятся соответствующие элементы гистограммы. Этаинформация извлекается на регистр 10,откуда поступает на блок 11 выводаоезу ьтатаБлок 8 управления координируетработу всех узлов анализатора. Рабо. та самого блока 8 может быть представлена следующим образом.Генератор 15 формирует тактовые импульсы, которые поступают на счет- ный вход счетчика 16. Выходы счетчика 16 соединены с входами дешифратора 17 и адресными входами мультиплексоФ ров 20.Мультиплексор - функциональный узел, обеспечивающий передачу информации, поступающей по нескольким входным линиям связи, на одну выходную линию. Выбор той или инойлинии осуществляется в соответствии с поступающим адресным кодом.В определенные моменты времени состояние второго управляющего входа блока 8 управления фиксируется на.регистре 18 под управлением дешифратора 17. В зависимости от информации, занесенной на регистр 18, группа 20 мультиплексоров Формирует навыходе блока 8 управления последова9 12 ц 12тельность управляющих сигналов всоответствии с временными диаграммами на фиг. 5 в8. Сброс счетчика16 осуществляется по первому управляющему входу блока 8 управления5при заполнении памяти, и элементом2 И-ИЛИ 19 при завершении обработкиконкретного ключа,В качестве блока 11 вывода результата может быть использовано , 1 Олюбое стандартное периферийное оборудование, например, алфавитноцифровое печатающее устройство,дисплей, пишущая машинка, внешнеезапоминающее устройство и т.д.15формула изобретенияМногомерный статистический анализатор, содержащий предварительное запоминающее устройство, первый блок преобразования,. ключа в адрес, первый и второй регистры адреса, схему сравнения, блок памяти, регистратор и блок управления, состоящий из дешифратора, счетчика и генератора тактовых импульсов, выход которого соединен со счетным входом счетчика, выход которого соединен с входом дешифратора, вход синхронизации котоЗО рого соединен с выходом переполнения блока памяти, первый вход управления записью которого соединен с первым выходом блока управления, первый вход записи блока памяти объединен . с первым информационным входом схемы сравнения, информационным входом первого блока преобразования ключа в адрес и соединен с вводом предварительного запоминающего устройства, входы которого являются соответственно информационными входами анализатора, а вход синхронизации предварительного запоминающего устройства соединен с вторым выходом блока управления,45 третий выход которого подключен к входам управления. сдвигом первого и второго регистров адреса, а четвертый выход блока управления соеди 10нен с входом синхронизации регистра, выход которого подключен к входу регистратора и второму входу з,.п;си блока памяти, информационный выход которого соединен с информационным входом регистра .и вторым информационным входом схемы сравнения, синхро. низирующий вход которой соединен с пятым выходом блока управления, второй управляющий вход которого соединен с выходом схемы сравнения, о т л и ч а ю щ и й с я тем, что, с целью повышения быстродействия и расширения класса решаемых задач, в него введены коммутатор и второй блок преобразования ключа в адрес, вход которого объединен с входом первого блока преобразования ключа в адрес, а выход подключен к входу второго регистра адреса, выходы первого и второго регистров адреса подключены соответственно к первому и второму информационным входам коммутатора, выход которого соединен с адресным входом блока памяти, а блок управления дополнительно со,цержит регистр элемент 2 И-ИЛИ и группу мультиплексоров, выходы пяти из которых являются соответственно с первого по пятый выходами блока управления, выход шестого мультиплексора группы соединен с управляющим входом коммутатора, информационные входы мультиплексоров группы объединены с первой группой входов элемен. та 2 И-ИЛИ и подключены соответственно к выходам регистра памяти блока управления,.информационные входы которого поразрядно объединены и являются вторым управляющим входом блока управления, а входы регистра блока управления объединены с второй группой входов элемента 2 И-ИЛИ и под. ключены к соответствующим выходам дешифратора, выход элемента 2 И-ИЛИ соединен с входом счетчика, выход которого соединен с входом сброса счетчика выход которого соединен с управляющими входами мультиплексоров группы.