Ассоциативная запоминающая среда

 

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

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

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

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

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

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

На фиг. 1 показаны возможные правильные конфигурации разбиения 2D-пространства ассоциативной среды относительно ассоциативных ячеек, образующих точечную 2D-решетку; на фиг. 2 пять возможных правильных точечных систем (точечных решеток) ассоциативных ячеек среды в декартовой системе координат на плоскости; на фиг. 3 рассмотрен пример организации взаимодействия ассоциативной ячейки (из которых сформирована квадратная точечная 2D-решетка ассоциативной среды) с элементами памяти, образующими базовые конфигурации - многогранники Вороного в виде квадратов; на фиг 4 пример организации взаимодействия ассоциативной ячейки в 3D-пространстве с элементами памяти, образующими базовые конфигурации в виде кубов.

Многогранники Вороного [3] относительно точек решетки полностью заполняют без наложений и промежутков пространство данной размерности. Пересечение двух примыкающих друг к другу многогранников Вороного является полной гранью каждого из них. Вершины многогранников Вороного называются "глубоким дырами", если расстояние от них до соответствующей точки решетки максимально. "Дыры", не являющиеся глубокими, называются "мелкими".

На плоскости существует паять возможных точечных решеток и восемь разновидностей многогранников Вороного (параллелогонов); в 3D-пространстве - четырнадцать точечных решеток (решеток Бравэ) и пять многогранников Вороного (параллелоэдров) [4] Элементы памяти 1 (фиг. 1), образующие базовую конфигурацию, взаимодействуют со смежными с ними ассоциативными ячейками 2. Выходы 3 элементов памяти 1 соединены с входами 4 этих ассоциативных ячеек 2. Шины ассоциативного опроса 5 и шины результатов ассоциативного опроса 6 подключены соответственно к входам ассоциативного опроса 7 и выходам результатов ассоциативного опроса 8.

Из рассмотренных на фиг. 1 конфигураций наибольший интерес для практической реализации представляют те, которые характеризуются максимальной степенью симметрии (фиг. 1а; фиг. 1д). Вариант на фиг. 1а обеспечивает ортодиагональность представления и обработки информации; а на фиг. 1д - максимально возможную для параллелогонов степень симметрии, одинаковые расстояния ассоциативных ячеек и элементов памяти от своих ближайших соседей, плотнейшую упаковку информации, наиболее экономное покрытие 2D-пространства ассоциативной среды [5] В то же время и сами распределенные в пространстве ассоциативной среды данные апосредованно отражают топологические свойства этой среды. Сформированная в ассоциативной ячейке некая обобщенная характеристика на основе информации, распределенной в элементах памяти соответствующей конфигурации, позволяет учесть не только информационные, но и структурные свойства среды: характер разбиения пространства среды для выбора оптимальной метрики пространства, направления ассоциативного опроса и результатов ассоциативного опроса для реализации в пространстве среды выбранного операционного базиса. Эта интегральная характеристика может быть использована как дополнительный фактор, характеризующий структурно-информационные свойства сформированного информационного объекта.

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

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

Элементы памяти 1 состоят из узла анализа входной информации 9 и узла хранения 10, входов 11 [2] Ассоциативная ячейка 2 содержит узел формирования обобщенной характеристики 12, который в зависимости от конкретной реализации может быть настроен на выполнение различных операций обработки данных, например, операций порогового суммирующего нейрона [6] мажоритарного срабатывания, операций булевой алгебры. Ассоциативная ячейка 2 содержит также узлы ассоциативного сравнения 13_i-13_K по числу направлений ассоциативного доступа. В качестве примера реализации узла 13_i может служить схема ассоциативного сравнения по критерию "равно" и коммутационный элемент ассоциативного запоминающего элемента из [7] Критериями ассоциативного сравнения могут быть, например, полное или частичное совпадение сравниваемых объектов, их полная или частичная противоположность, одновременность или заданный интервал времени между их появлением и др. [8] Запись информации в элементы памяти 1 производится с входов 11, чтение - с входов 3.

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

Настройка узлов ассоциативного сравнения 13₁-13_K заключается в предварительной записи в регистры коммутационных элементов "кодов подключения" выходов 8₁-8_K к нужным шинам результатов ассоциативного опроса 6.

При выполнении ассоциативного опроса среды по любому из направлений признак ассоциативного опроса с шин 5 поступает на входы 7 ассоциативных ячеек 2. Этот признак сравнивается с информацией, полученной на выходе узла 12 в соответствующем узле ассоциативного сравнения 13_i. В соответствии с установленным критерием сравнения и заданными условиями коммутации результат ассоциативного сравнения с выходов узла 13_i поступает на выбранные шины результатов ассоциативного опроса 6. В случае выполнения условий ассоциативного сравнения, маскирования сравнения или блокировки прохождения результатов ассоциативного сравнения соответствующая шина 6 не изменит своего состояния или пределы этого изменения будут допустимыми. При невыполнении условий ассоциативного сравнения признак этого события поступит на выбранные шины 6, изменяя их состояние существенным образом.

Ассоциативный опрос может проводиться одновременно по нескольким, от одного до K, возможным направлениям ассоциативного доступа в ассоциативной запоминающей среде.

Источники информации.

1. А.с. N 1793475, G 11 C 15/00, 1990.

2. А.с. N 1718274, кл. G 11 C 15/00, 1990 (прототип).

3. Конвей Дж. Слоэн Н. Упаковки шаров, решетки и группы. В 2-х томах. Т. 1 М. Мир, 1990, стр. 53, 54.

4. Шубников А.В. Копцик В.А. Симметрия в науке и искусстве М. Мир, 1972, стр. 117, 147, 148, 175, 191.

5. Конвей Дж. Слоэн Н. Упаковки шаров, решетки и группы. В 2-х томах. Т. 1 М. Мир, 1990, стр. 31.

6. Розенблатт Ф. Принципы нейродинамики. Перцептрон и теория механизмов мозга. М. Мир, 1965.

7. Патент РФ N 2025797, кл. G 11 C 15/00, 1994.

8. Кохонен Т. Ассоциативные запоминающие устройства. М. Мир, 1982, стр. 29.1

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

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4