Пристрій для обробки нечіткої інформації

Изобретение относится к вычислительной технике имеет быть использовано при создании устройств обработки нечеткой информации системах искусственного интеллекта. Известны устройства, выполняющие разные виды обработки нечеткой информации. Так, в [1, с.160] представлены устройства для сложения функций распределения вероятностей двух многозначных случайных последовательностей и для их умножения, включающие нечеткие схемы И и ИЛИ. С помощью схемы И реализуется выбор минимальной из двух случайных последовательностей, а схема ИЛИ выбирает большую из многозначных случайных последовательностей - производит операцию умножения. Эти устройства выполняют всего по одной функции и последовательно по времени, что .замедляет процесс выполнения операций. В [2,с.313] имеется структура устройства с одиночным потоком команд и множественным потоком данных. Устройство содержит ведущий процессор, 288 независимых идентичных процессорных элементов (включающих оперативную память, арифметическое устройство и другие устройства), а также устройство управления. В оперативной памяти процессорного элемента хранятся данные, которые обрабатываются арифметическим устройством этого процессорного элемента. Все процессорные элементы независимы и не имеют непосредственных связей между собой, причем каждый из них может одновременно выполнять операции, задаваемые устройством управления. Устройство не может выполнять операции над нечеткими множествами. В [3] защищено устройство для обработки нечеткой информации. Устройство содержит N регистров слова (где N - мощность нечетких множеств-операндов), N блоков памяти, N блоков адреса, регистр команд, дешифратор, блок управления, N блоков поиска минимума, N блоков поиска максимума, N блоков сдвига, арифметико-логический блок, счетчик команд, буферный регистр. Устройство имеет вход сброса, вход пуска, вход управления начальной загрузкой, выход управления начальной загрузкой, вход адреса пуска. Устройство обеспечивает выполнение операций (+,-) над четкими операндами. Устройство выполняет операции над нечеткими словами и в том случае, когда нечеткое слово соответствует четкому (абсолютный нуль или максимальное число - все единицы) и результат операции равен одному из слов. Арифметические операции сложения и вычитания нечетких множеств выполняются наполовину последовательно, с использованием блоков сдвига. Два перечисленных свойства рассмотренного устройства замедляют выполнение операций над нечеткими словами. По большинству совпадающих признаков принимаем это устройство за прототип. Прототип содержит N регистров слова, N блоков памяти, N блоков адреса, регистр команд, дешифратор, блок управления, N блоков поиска минимума, N блоков поиска максимума, N блоков сдвига, арифметикологический блок, счетчик команд, буферный регистр. Устройство имеет вход сброса, вход пуска, вход управления начальной загрузкой, выход управления начальной загрузкой, вход адреса пуска. В прототипе для выполнения операций сложения и вычитания нечетких множеств параллельно производится поиск min по первой строке, затем поиск max по столбцам и сдвиг на одно значение функции принадлежности. Далее параллельно производится поиск nnn по второй строке, max над найденной строкой и содержимым регистра, формирующего max по столбцам, а затем сдвиг полученного результата на одно значение функции принадлежности и т.д. до последней строки матрицы. За 2(N/2* m)+1 микрокоманд формируется множество функций принадлежности, описывающих нечеткое множество результата от суммирования/вычитания нечетких множеств. Устройство реализует также логические операции объединения (ν), пересечения (Λ) нечетких множеств и операции с четкими числами (+;-), в которых последовательно читаются функции принадлежности сначала первого множества, затем второго, проводится сама операция над ними и записывается результат. Целью изобретения является повышение быстродействия при выполнении операций над нечеткими .данными за счет параллельного чтения и анализа участвующих в логической операции слов на соответствие четким нулю и максимуму и формирования результата без выполнения операции. Повышение быстродействия при выполнении арифметических операций обеспечивается параллельным выполнением операций min и max сразу над всеми тетрадами функций принадлежности. На фиг.1 представлена структурная схема устройства для обработки нечетких данных; на фиг.2 структурная схема блока выбора одного значения функции принадлежности; на фиг.3 - структурная схема блока анализа операнда: на фиг.За - структурная схема сравнения нечеткого слова с четкими "О" и всеми "1"; на фиг.4-структурная схема блока нечеткой арифметики. Устройство (фиг.1) содержит 2N регистров 1 слова, 2N блоков 2 памяти, 2N блоков 3 адреса, регистр 4 команд, дешифратор 5, блок 6 управления, N блоков 7 выбора одного значения функции принадлежности, 2N блоков 8 анализа операнда, блок 9 нечеткой арифметики, арифметико-логический блок 10, счетчик 11 команд, буферный регистр 12 кода операции, группа входов А1 кода операции, входы А2 признака, входы A3 сброса и А4 пуска, вход А5 адреса, А6 управления начальной загрузкой, выход А7 управления, вход А8 адреса пуска, управляющие выходы Y1.....Y(10+N+2). На фиг.2 представлены, блок 7 выбора одного значения функции принадлежности, построенный на схеме сравнения кодов 13, ключах 14, схеме ИЛ!/! 15 на два входа, многовходовых схемах И 16 и 17, многовходовой схеме ИЛИ 18 с тремя состояниями по выходу и инверторе 19. Предполагается, что функция принадлежности описывается тет-. радой. Первый информационный вход обозначен R1, второй - R2, вход управления - R3. Фиг.3 изображает блок 8 анализа операнда, который имеет схемы сравнения 20, схемы И-НЕ 21 и 22, двухвходовую схему И 23. На третьи входы 1,2 ...m подается тетрада, а на первый и второй входы - "0" и "1”. Схема сравнения 20 (фиг.3а) реализована на мажоритарных элементах 24, схемах И 25 и 26, инверторах 27. На фиг.4 изображен блок 9 нечеткой арифметики, включающий схемы min 28 и схемы max 29 с тремя состояниями по выходу у схем 29, подключаемых ко входу блока 2. Блок 9 состоит из независимых схем, число которых не более чем в два раза минус единица больше, чем наибольшее исходное нечеткое множество. Блок 1 регистра слова имеет информационный вход R1, вход R2 выбора блока, управляющий вход R3, первый выход К1 с тремя состояниями, которые управляются ПО ВХОДУ R3 И ВТОРОЙ Неуправляемый ВЫХОД; Блок 2 памяти имеет выход данных К1, адресный вход R1, вход данных R2, вход R3 управления записи/чтения, вход R4 управления и вход R5 выбора блока. Выход данных и вход данных могут быть соединены. Блок 3 адреса имеет вход К1 адреса, вход К2 разрешения, вход КЗ управления чтением, выход R1 адреса, выход R2 выбора блока памяти. Регистр 4 команд имеет выход операции R2, выход адреса, вход для приема кодов операции и адреса, Дешифратор 5 команд имеет вход К1 и выход К2 кода операции, Блок 6 управления имеет группу входов А1 кода операции, вход А2 признака, входы A3, А4 сброса и пуска, вход А5 адреса, вход А6 управления начальной загрузкой, выход А7 управления, вход А8 адреса пуска и управляющие выходы Y1...Y(10+N+2). Арифметико-логический блок 10 имеет первый и второй информационные входы К1 и К2 для подачи операндов, третий вход кода операции, выход для чтения результата операции. Счетчик команд 11 имеет входы и выходы для подсчета команд. Буферный регистр 12 имеет вход для приема информации, вход записи и информационный выход. Устройство предназначено для выполнения арифметических и логических операций над нечеткими и четкими числами. Под нечетким числом понимается множество А = {иА(Х),Х}, где Хμ:Х->[0,1] - отображение множества X в единичный отрезок [0,1] -называется функцией принадлежности нечеткого множества А. Значение функции принадлежности μΑ(Χ) Для элементов хЄХ называется степенью принадлежности. Интерпретация степени принадлежности μΑ(Χ) является субъективной мерой того, насколько элемент хЄХ соответствует понятию, смысл которого формализуется нечетким множеством А. Арифметические операции над нечеткими числами определяются по формуле где А = {μi А, аі} -первое нечеткое число. В = {μв, bj} - второе нечеткое число; В соответствии с формулой (1) максимумы, взятые по столбцам матрицы (4), дадут значение функции принадлежности искомого нечеткого множества С соответственно в точках. ~ C = {max(minμiA, μjB)}, ai* bj - нечеткое число - результат операции (1); * - знак арифметической операции. ~ ~ Пусть задано нечеткое множество A =(a1 μ1A.....an, μηA) и нечеткое множество B =(b 1μ1.....bm, μmB), тогда в соответствии с формулой (1) для каждой пары значений из области определения нечетких множеств для операции сложения запишем Предположим, что все нечеткие множества, участвующие в операции, заданы на области определения с одинаковым шагом D т.е. Это требование выполнимо, так как если Da—Dβ, то множество, заданное с большим шагом, можно доопределить или убрать промежуточные значения в множестве, заданном с меньшим шагом. Тогда, опираясь на выражение (3) и анализируя матрицу (2), имеем Описанный алгоритм позволяет выполнять арифметические операции сложения и вычитания нечетких множеств. Устройство реализует также логические операции объединения (ν), пересечения (Ù ) нечетких множеств и операции с четкими числами Модифицируем матрицу (2) так. чтобы в одном столбце находились значения искомого нечеткого множества, относящиеся к одной и той же точке области определения, т.е. Заметим, что количество точек, на которых задано найденное нечеткое множество, не более чем в два раза минус единица больше, чем наибольшее исходное множество. Алгоритм выполнения арифметических операций сложения и вычитания, который реализует данное устройство, разработай на основе выражения (4). Вначале параллельно производится поиск min по первой строке, затем отыскивается max по столбцам. Очевидно, что первая операция max будет производиться над первой строкой выражения (4) и строками с нулевыми значениями, а последняя операция max -над последней строкой выражения (4) и строками с нулевыми значениями. Параллельно производится поиск min по второй строке и отыскивается max над min второй строки и min первой строки по столбцам и т.д. до последней строки матрицы (4). Рассмотрим работу устройства при выполнении арифметических и логических операций с четкими и нечеткими числами. Для заданий одного значения (одной точки) функции принадлежности нечеткого множества используются, например, четыре двоичных разряда или тетрада, т.е. выделяется шестнадцать уровней степени принадлежности. При использовании шестнадцатиразрядных блоков памяти в одном слове одного блока памяти может храниться четыре значения функции принадлежности. Работа устройства начинается с подачи сигнала "Сброс" на вход A3 блока 6 управления. По приходу сигнала "Пуск" на вход А4 блока 6 управления, начинается загрузка, выполняются линейные участки микропрограмм и переходы по адресу, подаваемому на вход А1 блока 6 управления, при этом читаются "1" с его входа А2, обеспечивая пропуск информации об адресе первой микрокоманды микропрограммы. При необходимости осуществляется ветвление в микропрограмме по логическим условиям, поступающим на входы А2 и A3 блока 6 управления. Пусть в регистре 4 команд находится команда сложения двух четких операндов, находящихся по адресам А1 и А2 в блоках 2 памяти. Код операции команды с выхода кода операции R2 регистра 4 команд через дешифратор 5 поступит на вход А1 блока б управления и по этому коду будет осуществлен переход на микропрограмму выполнения команды. В первой микрокоманде адрес первого операнда с выхода адреса регистра 4 команд поступает на первые входы всех блоков 3 адреса. Управляющие сигналы Y3 и Y4, поступающие на входы разрешения К2 блоков адреса, настраивают коммутаторы в блоке 3 адреса на пропуск адреса первого операнда Младшие разряды сразу идут на выход R1 адреса блоков адреса, а старшие анализируются. Если код в старших разрядах адреса соответствует номеру блока 2 памяти, то с выхода R1 адреса блоков адреса он позиционным кодом подается на адресный вход R1 блоков 2. Таким образом, выбирается один из блоков 2 памяти, младшие разряды адреса задают конкретную ячейку в этом блоке. Адрес первого операнда после дешифрации в блоках 3 адреса поступит на вход R1 адреса блока 2 памяти, один из которых будет инициирован по входу адреса. На его вход записи/чтения подан управляющий сигнал Y6, задающий режим чтения. Информация, считанная с 1-го из блоков 2 памяти поступит на информационный вход R1 і-го регистра 1 слова. На вход R2 выбора і-го регистра 1 поступает сигнал дешифрации адреса с выхода R2 блока 3 адреса. На i-тый блок регистра слова 1 также поступают сигналы "Запись" и "Разрешение выхода". Таким образом, информация с выхода і-го блока 2 памяти будет записана в i-тый регистр 1 слова и с его выхода через магистраль будет подана на первый вход буферного регистра 12, где и будет записана по заднему фронту управляющего сигнала Y8. Во второй микрокоманде информация, выбранная из блока 2 памяти по адресу второго операнда, будет записана в i-тый регистр 1 слова и с его· выхода поступит на информационный вход К1 блока 10, на втором информационном входе К2 которого присутствует информация, выбранная по адресу первого операнда с выхода буферного регистра 12. На третий вход блока 10 с второго выхода блока 6 управления поступает код, задающий операцию сложения в блоке 10. Результат операции с выхода блока 10 поступает на входы данных всех блоков 2. При выполнении -третьей микрокоманды результат по управляющему сигналу Y6 будет записан в ячейку памяти в і-ом блоке 2 памяти β соответствии с алгоритмом по адресу первого или второго операнда. Таким образом, за три микрокоманды будет выполнена операция сложения двух четких операндов. На данной структуре могут быть реализованы и иные алгоритмы арифметических операций над четкими операндами. Рассмотрим теперь выполнение команды логического умножения (пересечения) нечетких операндов. В первой микрокоманде адреса первого и второго операндов подаются с выхода адреса регистра 4 команд на входы К1 адреса блоков 3 адреса. Причем управляющий сигнал Υ3, поступающий на входы К2 разрешения iых блоков 3 адреса 0=1 ,Ν), обеспечивает подачу адреса первого операнда на входы адреса для первой половины блоков 2 памяти. Управляющий сигнал Υ4 обеспечивает подачу адреса второго операнда на входы адреса для второй половины блоков 2 памяти. По управляющему сигналу Y6, поступающему на входы R3 управления записью/чтением блока 2 памяти, параллельно происходит считывание первого и второго операндов из бяоков памяти, а по управляющему сигналу Y(9+i), поступающему на входы R3 регистров 1 слова, происходит запись первого операнда в первую половину регистров 1 слова, а второго операнда - во вторую половину регистров 1 слова. На вторых выходах регистров 1 можно читать информацию. С помощью блоков 8 анализируются параллельно первый и второй операнды. Нечеткие операнды могут иметь разные значения. Один из них или оба могут иметь абсолютно минимальное значение (четкий нуль), один из них, или оба могут иметь абсолютно максимальное значение (четкий максимум) функции принадлежности и т.д. Если первый операнд абсолютно минимален, то он является результатом логического умножения. Сигнал об этом с первого блока 8 идет на блок управления 6 и микропрограмма логического умножения завершается. В блоке 2 по адресу первого операнда в соответствии с микропрограммой хранится результат - первый операнд. Если первый операнд абсолютно максимален, то результатом умножения будет вто-' рой операнд. Сигнал об этом с первого блока 8 идет на блок 6 и завершается микропрограмма логического умножения результат умножения хранится по адресу второго операнда. Если первый операнд действительно нечеткий, то учитываются результаты анализа во втором блоке 8 второго операнда. Если второй операнд абсолютно минимален, то он является результатом, сигнал об это идет со второго блока 8 на блок управления 6 и микропрограмма логического умножения завершается - результат умножения хранится по адресу второго операнда. Если второй операнд абсолютно максимален, то результатом будет первый операнд, который сохраняется по адресу первого операнда. Если оба операнда абсолютно минимальны, то результат - один из них - хранится по адресу одного из операндов. С помощью блоков 8 операнд анализируется следующим образом. Тетрада операнда поступает на мажоритарные элементы 24 схемы сравнения 20. Если в тетраде все "нули", то они после инверсии в 27 попадают на схему И 26, логическая единица на выходе которой соответствует тетраде со всеми нулями. Ε с/1 и в тетраде все "единицы", то появляется логическая единица на выходе схемы И 25. Если тетрада нечеткая, то на выходах схем И25, 26 имеются логические нули. Все выходы схем 25 соединены со входами схемы 22, а схем 26 - со входами схем 21.0 наличии абсолютно максимального операнда сигнализирует логический нуль на выходе схемы И-НЕ 22 -первом выходе К1 блока, о наличии абсолютно минимального - на выходе схемы И-НЕ 21 - втором выходе К2. о наличии нечеткого операнда - логическая единица на выходе схемы И 23 - третьем выходе К3. Если оба операнда действительно нечеткие, то учитывается выходной сигнал блока 7, который обрабатывал операнды одновременно с первым и вторым блоками 8. На первый информационные вход R1 блока 7 выбора одного значения функции принадлежности с выхода первых регистров 1 слова подан первый нечеткий операнд, второй операнд со вторых регистров 1 слова поступает на вторые информационные входы R2 блока 7. Управляющий сигнал Υ10, поданный на вход R3 разрешения блоков 7. настраивает ключи 14 на пропуск минимального значения из двух функций принадлежности, поступающих на информационные входы блока 7. Первый нечеткий операнд поступает на входы А схем 13 сравнения, на входах В которых присутствует второй нечеткий операнд, поступающий на вход R2 блоков 7. Схемы 13 сравнения производят потетрадное сравнение двух нечетких операндов параллельно по всем блокам 7 и настраивают схемы И 16,17 на пропуск наименьшего. Таким образом, на выходах схем ИЛИ 18 и на выходах блоков 7 формируется результат логической операции умножения (пересечения) нечетких операндов в виде потетрадных минимумов. В следующей микрокоманде открываются выходы блоков 7 и результат операции с выходов блоков 7 записывается параллельно в блоки 2 памяти по адресу первого операнда в соответствии со схемой фиг.1. Рассмотрим выполнение команды логического Сложения (объединения) нечетких операндов. В первой микрокоманде адреса первого и второго операндов подаются с выхода адреса регистра 4 команд на входы К1 адреса блоков 3 адреса. Причем управляющий сигнал Υ3, поступающий на входы К2 разрешения i-ых блоков 3 адреса (i=1,N), обеспечивает подачу адреса первого операнда на входы адреса для первой половины блоков 2 памяти. Управляющий сигнал Υ4 обеспечивает подачу адреса второго операнда на входы адреса для втопой половины блоков 2 памяти. По управляющему сигналу Υ7, поступающему на входы R3 управления записью/чтением блока 2 памяти, происходит считывание первого и второго операндов из блоков памяти, а по управляющему сигналу Y13, поступающему на входы R3 регистров 1 слова, происходит запись первого операнда в первую половину регистров 1 слова, а второго операнда - во вторую половину регистров 1 слова. С помощью блоков 8 анализируются параллельно первый и второй операнды. Нечеткие операнды могут иметь разные значения. Один из них или оба могут иметь абсолютно минимальное значение (четкий ° нуль), один из них или оба могут иметь абсолютно максимальное значение (четкий максимум) функции принадлежности и т.д. Если первый операнд абсолютно максимален, то он является результатом логического сложения. Сигнал об этом с первого блока 8 идет на блок управления 6 и микропрограмма логического сложения завершается. В блоке 2 по адресу первого операнда в соответствии с микропрограммой хранится результат - первый операнд. Если первый операнд абсолютно минимален, то результатом сложения будет второй операнд. Сигнал об этом с первого блока 8 идет на блок 6 и завершается микропрограмма логического сложения результат сложения хранится по адресу второго операнда. Если первый операнд действительно нечеткий, то учитываются результаты анализа во втором блоке 8 второго операнда. Если второй опера н абсолютно максимален, то он является результатом, сигнал «б этом идет со второго блока 8 на блок управления 6 и микропрограмма логического сложения завершается -результат сложения хранится по адресу второго операнда. Если второй операнд абсолютно минимален, то результатом будет первый операнд, который сохраняется по адресу первого операнда. Если оба операнда абсолютно максимальны, то результат -один из операндов - хранится по адресу одного из операндов. Если оба операнда действительно нечеткие, то учитывается выходной сигнал блока 7, который обрабатывал операнды одновременно с первым и вторым блоками 8. На первый информационный вход R1 блока 7 выбора одного значения функции принадлежности с первых регистров 1 слова подан первый нечеткий операнд, второй операнд со вторых регистров 1 поступает на второй информационный вход R2 блоков 7. Управляющий сигнал Υ10, поданный на вход R3 разрешения блоков 7, настраивает ключи 14 на пропуск максимального значения из двух функций принадлежности, поступающих на информационные входы блока 7. Первый нечеткий операнд поступает на входы А схем 13 сравнения, на входах В которых присутствует второй нечеткий, операнд, поступающий на вход R2 блоков 7. Схемы 13 сравнения производят потетрадное сравнение двух нечетких операндов параллельно по всем блокам 7 и настраивают схемы И 16,17 на пропуск наибольшего. Таким образом, на выходах схем ИЛИ 18 и на выходах блоков 7 формируется результат логической операции сложения (объединения) нечетких операндов в виде потетрадных максимумов. В следующей микрокоманде открываются выходы блоков 7 и результат операции с выхода блоков 7 записывается параллельно в блоки 2 памяти по адресу первого операнда в соответствии со схемой фиг Д. Рассмотрим выполнение команды арифметического сложения (вычитания) нечетких операндов. В первой микрокоманде адреса первого и второго операндов подаются с выхода адреса регистра 4 команд на входы К1 адреса блоков 3 адреса. Причем управляющий сигнал Υ3, поступающий на входы К2 разрешения i-ых блоков 3 адреса (i=1 ,N), обеспечивает подачу адреса первого -операнда на входы адреса для первой половины блоков 2 памяти. Управляющий сигнал Υ4 обеспечивает подачу адреса второго операнда на входы адреса для второй половины блоков 2 памяти. По управляющему сигналу Υ7, поступающему на входы R3 управления записью/чтением блока 2 памяти происходит считывание первого и второго операндов из блоков памяти, а по управляющему сигналу Υ13, поступающему на вхо-. ды R3 регистров 1 слова, происходит запись первого операнда в первую половину регистров 1 слова, а второго операнда - во вторую половину регистров 1 слова. Закрываются выходы блоков 7. В следующей микрокоманде открываются выходы блоков 9 нечеткой арифметики в соответствии с микропрограммой арифметического сложения/вычитания. Параллельно со вторых выходов регистров 1 слова операнды поступают на входы блока 9 нечеткой арифметики, построенного и подключенного к регистрам 1 в соответствии с уравнением (4). В блоке 9 сначала вычисляются все возможные min, затем все max. Центр тяжести, ядро, вокруг которого располагается найденное нечеткое множество, находится аналогично арифметической операции над четкими операндами. Арифметическая операция выполняется над ядрами нечетких множеств.