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

 

Изобретение относится к области вычислительной и измерительной техники. Цель изобретения -повышение быстродействия и расширения класса решаемых задач. Для этого анализатор содержит коммутатор, дополнительньй (второй) блок преобразования ключа в адрес, которые имеют характерную для данного решения стрз ктуру, как и блок управления, соединенные с остальными узлами анализатора в соответствии с алгоритмом функционирования. Изобретение может быть использовано при статистическом анализе каналов связи, контроле качества носителей информации магнитных и оптических дисковых запоминающих устройств при проведении статистических экспериментов в ядерной физике и т.п. U ел со

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСИИХ . РЕСПУБЛИН (Я).4 G 06 F 15 36

l3, ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3750022/24-24 (22) 01.06.84 (46) 30,06.86. Бюл. № 24 (71) Пензенский политехнический институт (72) Н.П.Вашкевич, Н.Н.Коннов и В.Б.Меканов (53) 681.3 (088.8) (56) Курочкин С.С. Многомерные статистические анализаторы, N. Атом издат, 1968, с. 311.

Авторское свидетельство СССР

¹ 976449, кл. G 06 F 15/36, 1980. (54) 1"1НОГОМЕРНЬЙ СТАТИСТИЧЕСКИИ

АНАЛИЗАТОР (5?) Изобретение относится к облас-. ти вычислительной и измерительной

„,Я0„„1241259 А1 техники. Цель изобретения — повышение быстродействия и расширения класса решаемых задач. Для этого анализатор содержит коммутатор, дополнительный (второй) блок преобразования ключа в адрес, которые имеют характерную для данного решения структуру, как и блок управления, соединенные с остальными узлами ана" лизатора в соответствии с алгоритмом функционирования. Изобретение может быть использовано при статистическом анализе каналов связи, контроле качества носителей информации магнитных и оптических .дисковых запоминающих устройств при про ведении статистических экспериментов в ядерной физике и т.п.

С:

Ф

Ю

«М

ЬФ

Сл

41259

55

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

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

На фиг. 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, а выходы являются соответствующими выходами блока 4.

Коммутатор 6 (фиг.3) может содер15 жать группу 13 элементов 2И-ИЛИ и элемент HE 14, вход которого объединен с первыми входами элементов

2И-ИЛИ и является управляющим входом коммутатора 6, выход элемента НЕ 14 0 соединен с вторыми входами элементов 13 2И-ИЛИ, третьи и четвертые входы которых являются соответственно первым и вторым информационными входами коммутатора 6, а выходы элементов 2И-ИЛИ 13 являются выходами коммутатора 6.

Блок 8 управления (фиг.4) может состоять иэ генератора 15, счетчика 16, дешифратора 17, регистра 18, 30 элемента 2И-ИЛИ 19 и группы 20 мультиплексоров, выходы которых являются управляющими выходами блока 8, а информационные входы объединены с первыми входами элемента 2И-ИЛИ 19

:и соединены с выходами регистра 18, информационные входы которого объеди. иены между собой и являются вторым управляющим входом блока 8, а входы синхронизации регистра 18 объединены с вторыми входами элемента 2ИИЛИ 19 и соединены с выходами дешифратора 17, вход которого обьединен с адресными входами мультиплексоров 20 и соединен с выходом счетчика 16, информационный вход которо45 го соединен с выходом генератора 15, вход сброса соединен с выходом элемента 19 2И-ИЛИ, а вход синхронизации является первым управляющим входом блока 8.

Работа анализатора основана на следующем способе размещения ключей.

Область памяти, отводимая для хранения данных, разбивается на две непересекающиеся подтаблицы так, чтобы количество адресов в каждой из них Ml и М2 были равны между собой . Формируется адрес Аl для подтаб лицы 1. Если прн обращении по этому

З 124 адресу коллизии не возникает, то для текущего ключа достраивается гистограмма. Если коллизия возникает, происходит обращение к подтаблице 2 по адресу А2, вычисляемому независи.

Мо от Al. Если и здесь возникает коллизия, выполняется повторное обращение к подтаблице 1, но уже по адресу А2. Наконец, если и здесь происходит коллизия, осуществляется обращение к подтаблице 2 по адр".ñó Al °

В результате преобразования ключа в адрес получают равномерное распределение адресов. Тогда (N — число ключей, M — количество .адресов) не— роятность того, что число ключей, адресуемых к данной ячейке, равно К подчиняется биномиальному закону и определяется выражением:

Р(К) = С „Р". и, где р = 1/M — вероятность попадания любого ключа в а-й адрес (a=1,2, M); — — 1/М вЂ” вероятность попадания любого ключа в адрес, отличный от а.

Так как М достаточно велико, а произведение Ы-р имеет один порядок, с количеством ключей, которые могут разместиться по одному адресу, можно воспользоваться пуассоновским приближением для биномиального расп. ределения: где

Отсюда можно вычислить среднее число ключей, приходящихся на один адрес

N й(т,51 = n Р(5+л1 и процентное содержанке ключей„размещенных в памяти

g(m,S) = ††- - 100, m-n(m $ где m=N/Ì вЂ” коэффициент загрузки ключей;

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

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

g=g(m 1,2) + 8(тп 2,2) 5 я (тп 1 2) я (т 2 22

100 где тпl = N/Ml;

10 тп2 (100 — д(тп 1 2 )

100 М2

1 l

P = — (1 — — )

M M 9

N — m т m

Как показывают расчеты по формуле (1) применение описанного алго) ритма позволяет разместить все 100Х поступающих ключей в памяти (при т «1) без указания адресов связей.

Многомерный статистический .анализатор работает следующим образом.

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

30 предварительное ЗУ 1, разрядность которого зависит от размерности анализируемого процесса. Блоки 2 и 4 преобразования ключа в адрес формируют независимо друг от друга адреса ячеек блока 7 памяти в заданном диапазоне.

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

Ключ, представляющий собой цифровой двоичный код, поступает в преднарительное ЗУ I, которое может быть выполнено н виде регистра. Выходы

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

Блок 2 преобразования ключа в адрес, реализованный в виде сумматора, выполняет операцию сложения соответствующих разрядов различных групп выходов предварительного ЗУ 1 и результат запоминается н первом регистре 3 адреса, разрядность которого ранна и. Если обшее число разрядов предварительного ЗУ 1 не кратно

12 )2 и, то последняя группа с количеством разрядов меньше и условно дополняется до п нулями и учясФнует н операции сложения наравне с остальными группами разрядов.

Бторой блок 4 преобразования к:0n— ча в адрес может быть выполнен н ниде группы элементов ИСКЛОЧЛ10))1ЕЕ ИЛИ каждый из которых реализует операцию сложения по модулю 2. При этом входы каждого элемента ИСК)ЦОЧЛ)ОЦ)ЕЕ

ИЛИ 12 соединены с выходами соответствующих разрядов различных групп -выходов. предварительного ЗУ 1.

Сигнал на четвертом управляющем выходе блока 8 управления разрешает записать адреса, сформированные первым и вторым. блоками 2 и 4 преобразования кпюча н адрес, соответственно в первый и второй регистры 3 и 5 адреса.

Старшие разряды регистров 3 и 5 могут быть выполнены в виде Т-триггеров, начальное состояние которых равно соответственно "1" и "0". Это сделано для того, чтобы иметь возможность адресоваться поочередно к первой (диапазон изменения адресов от 1 до 2 л ) и второй (диапазон изменения адресов от ". + 1 до 2 ) полонинам отведенной для хранения даHHblx области памяти. Таким образом достигается разбиение памяти на две непересекающиеся подтаблицы. Ряб>ота при этом происходит следующим образом.

Появление сигнала на четнертом управляющем входе блока 8 управления (фиг.4) заставляет старшие раз— ряды первого и второго регистров 3 и 5 переключить соответственно н состояние 0 и ") . Затем с подачей разрешающих сигналов из блока 8 управления адрес из первого регистра 3 адреса через коммут-тор 6 пос— тупает на адресные входы блока памяти.

Коммутатор 6 работает следующим образом.

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

2И-ИЛИ 13 на выход коммутатора 6.

При этом низкий уровень на выходе элемента НЕ 14 запрещает прохождение адреса с второго регистра 5 адреса через нторые информационные нхо

?О

3 >

>О q Ь ды элемен гон 2И-И))И 13 . 11изкий уровень на пятом управляющем;выходе бпо ка 8 управления разрешает прохождение на выход коммутатора б адреса с второго регистря 5 адреса, н то время как выходы первого регистра 3 адреса блокирун>тся.

После установления адреса на адресных входах блока 7 памяти содержимое ячейки с данным адресом извлекается на регистр 10 и на схему 9 сравнения, где происходит сравнение содержимого этой ячейки с нулем.

Память при этом может быть организована так, чтобы каждая запоминающая ячейка хранила и ключ, и гистограмму (например, дпя хранения ключа выделяются определенные разряды ячейки). Тогда на схему 9 сравнения поступает группа разрядон, соответствующая ключу, а на регистр 10 группа разрядов ячейки, соответствующая гистограмме. Если схема 9 сравнения обнаруживает, что данная ячейка свободна, т.е. ее содержимое равно нулю, она вырабатывает сигнал, который поступает на второй управляющий вход блока 8 управления.

Блок 8 управления унеличивает со— держимое регистра 10, осуществляя тем самым достраивание гистограммы, и разрешает затем запись ключа из предварительного ЗУ 1 и гистограммы из регистра 1О н блок 7 памяти по адресу, храня.вемуся на первом ре— гистре 3 адреса. Обработка ключа завершена.

Если н результате проверки в схеме 9 сравнения оказалось, что дан— ная ячейка уже занята, т.е. ее со— держимое не равно нулю (фиг.5), блок 8 управления вырабатывает сигналы на первом, втором, третьем и пятом управляющих выходах. Содер жимое адресуемой ячейки (разряды, соответствующие ключу) поступает ня первь>й инфсрмационный вход схемы

9 сравнения, на второй информационньп-. вход которой поступает ключ из предварительного ЗУ ) и происходит их сравнение. Если проверяемые клю— чи совпадают, схема 9 сравнения вырабатывает сигнал, который поступает ня. второй управляющий вход блока 8 управления ° Блок 8 управления сигналом на шестом управляющем выходе увеличивает на единицу содержимое регистра )0 (достраивается гистограмма), которое в следующем

1241259

10 l5

ЗО

50

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 адреса. После этого повторяется анализ содержимого адресуемой .ячейки аналогично описанному выше.

Если и данная ячейка оказалась занятой ключом, отличным от вновь поступившего, происходит обращение к первой половине памяти (адреса от до 2 " ) по адресу, хранящемуся на втором регистре 5 адреса. Для этого -блок 8 управления устанавливает на четвертом управляющем выходе низкий уровень, разрешая прохождение на адресные входы блока 7 памяти адреса из второго регистра 5 адреса.

Затем повторяется анализ содержимого адресуемой ячейки аналогично описанному

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

По окончании эксперимента блок 8 управления может последовательно.формировать в предварительном ЗУ 1 коды возможных ключей, из которых блоки 2 и 4 преобразования ключа в адрес формируют адреса ячеек блока

7 памяти, в которых хранятся соответ ствующие элементы гистограммы. Эта информация извлекается на регистр 10, откуда поступает на блок ll вывода результата.

Блок 8 управления координирует работу всех узлов анализатора. Работа самого блока 8 может быть представлена следующим образом.

Генератор 15 формирует тактовые импульсы, которые поступают на счет- ный вход счетчика 16. Выходы счетчика

16 соединены с входами дешифратора

17 и адресными входами мультиплексо. ров 20.

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

В определенные моменты времени состояние второго управляющего входа блока 8 управления фиксируется на.регистре 18 под управлением дешифратора 17. В зависимости от информации, занесенной на регистр 18, группа 20 мультиплексоров формирует на выходе блока 8 управления последова

9 12ч12 тельность управляющих сигналов в соответствии с временными диаграммами на фиг. 5 †8. Сброс счетчика

16 осуществляется по первому управляющему входу блока 8 управления

5 при заполнении памяти, и элементом

2И-ИЛИ !9 при завершении обработки конкретного ключа.

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

15 формула изобретения

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

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

10 нен с входом синхронизации регистра, выход которого подключен к входу регистратора и второму входу з,=:.и ;си блока памяти, информационный выход которого соединен с информационным входом регистра .и вторым информационным входом схемы сравнения, синхронизирующий вход которой соединен с пятым выходом блока управления, второй управляющий вход которого соединен с выходом схемы сравнения, отличающийся тем, что, с целью повышения быстродействия и расширения класса решаемых задач, в него введены коммутатор и второй блок преобразования ключа в адрес, вход которого объединен с входом первого блока преобразования ключа в адрес, а выход подключен к входу второго регистра адреса, выходы первого и второго регистров адреса подключены соответственно к первому и второму информационным входам коммутатора, выход которого соединен с адресным входом блока памяти, а блок управления дополнительно со,цержит регистр, элемент 2И-ИЛИ и группу мультиплексоров, выходы пяти из которых являются соответственно с первого по пятый выходами блока управления, выход шестого мультиплексора группы соединен с управляющим входом коммутатора, информационные входы мультиплексоров группы объединены с первой группой входов элемента 2И-ИЛИ и подключены соответственно к выходам регистра памяти блока управления,.информационные входы которого поразрядно объединены и являются вторым управляющим входом блока управления, а входы регистра блока управления объединены с второй группой входов элемента 2И-HJIH и под. ключены к соответствующим выходам дешифратора, выход элемента 2И-ИЛИ соединен с входом счетчика, выход которого соединен с входом сброса счетчика,, выход которого соединен с управляющими входами мультиплексоров группы.!

2н1259!

l24I25) (t

1241259,Ю

ЯФЛ . м

"7-й (т1 1 гц у Ю 1

P1 Ð8 „ Я

Составитель З.Сечина

Техред 0.1ортвай

Корректор- Л.Патай

Редактор Л.Пчелинская

Тираж 67I Подписное

ВНИИПИ Государственного комитета. СССР по делам изобретений и открытий

)13035, Москва, )К вЂ” 35, . ауглская наб,, д.4/5

Заказ 3784 а

Производственно-полиграфическое предприятие, г.ужгород, ул. Проектная,4