ПРОГРАММИРУЕМАЯ НЕЙРОМАТРИЦА Российский патент 2006 года по МПК G06N3/04 

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

Известен нейроэлемент (Пат. SU 1831715A3, кл. G 06 G 7/60, Бюл. №28, 30.07.93), содержащий элементы И, ИЛИ, И-ИЛИ. Такой нейроэлемент при реализации пороговой логической функции многократно выполняет операции суммирования и сдвига двоичных чисел. Этот нейроэлемент не позволяет реализовать произвольную логическую функцию.

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

Известен также цифровой нейрон (Регистрационный номер заявки RU 93004711, кл. G 06 F 17/00, 20.03.97), содержащий ОЗУ на 2ⁿ однобитовых ячеек однородной среды. При реализации частично заданных логических функций от большого числа n переменных аппаратура цифрового устройства используется неэффективно, так как емкость ОЗУ будет многократно превышать емкость области определения частично заданной логической функции.

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

Наиболее близкой по технической сущности к предлагаемому изобретению является каноническая контактная цепь (А.Фридман, П.Менон. Теория и проектирование переключательных схем. М.: Мир, 1978 г., стр.102-103), содержащая коммутационные элементы, организованные в виде однородной среды. Такая цепь реализует симметрические функции и может реализовать пороговые функции посредством отождествления соответствующих переменных, управляющих срабатыванием коммутационных элементов. Однако при этом объем однородной среды (число пар коммутационных элементов) выражается числом Q=p(р+1)/2,

где р - сумма весов входных сигналов;

a_i - вес (целое положительное число) i-го входного двоичного сигнала, i=1÷n.

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

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

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

Для достижения указанного технического результата в программируемой нейроматрице, содержащей вход установки сигнала "логическая единица", элементы настройки соединения, первый и второй блоки ячеек коммутации, в каждом из которых ячейки коммутации расположены в узлах диагональной сетки так, что первый выход предшествующей ячейки коммутации соединен с вторым входом следующей по диагонали верхней ячейки, а второй выход предшествующей ячейки коммутации соединен с первым входом следующей по диагонали нижней ячейки, управляющие входы ячеек коммутации одного вертикального ряда в каждом блоке ячеек коммутации соединены с соответствующим управляющим входом соответствующего блока ячеек коммутации, вход установки сигнала "логическая единица" соединен с первым входом одной из ячеек коммутации первого вертикального ряда первого блока ячеек коммутации, отличающаяся тем, что в нее введены коммутатор, элементы И, ИЛИ, последовательности элементов ИЛИ, блок элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, при этом информационные входы программируемой нейроматрицы соединены с соответствующими входами блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, в котором элементы ИСКЛЮЧАЮЩЕЕ ИЛИ образуют прямоугольную матрицу, причем в каждом вертикальном ряду элементов ИСКЛЮЧАЮЩЕЕ ИЛИ выход предшествующего элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с первым входом следующего элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход каждого из элементов ИСКЛЮЧАЮЩЕЕ ИЛИ одного горизонтального ряда элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с выходом соответствующего элемента настройки соединения соответствующего одного горизонтального ряда элементов настройки соединения блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вход каждого из элементов настройки соединения одного горизонтального ряда элементов настройки соединения блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с соответствующим входом блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, первый вход каждого из элементов ИСКЛЮЧАЮЩЕЕ ИЛИ первого горизонтального ряда элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с выходом соответствующего элемента настройки соединения первого горизонтального ряда элементов настройки соединения блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вход каждого из элементов настройки соединения первого горизонтального ряда элементов настройки соединения блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с соответствующим входом блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ последнего горизонтального ряда соединены с соответствующими выходами блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены с соответствующими входами управления первого и второго блоков ячеек коммутации, в каждом из которых в каждой ячейке коммутации управляющий вход соединен с входами первого и второго элементов настройки соединения ячейки коммутации, выходы которых соединены соответственно с прямым и инверсным входами первого элемента ИЛИ, выход которого соединен с первым входом первого элемента И и вторым инверсным входом второго элемента И, первый и второй входы ячейки коммутации соединены в ячейке с соответствующими входами второго элемента ИЛИ, выход которого соединен с вторым входом первого элемента И, первым входом второго элемента И и входом третьего элемента настройки соединения ячейки коммутации, выход которого соединен с вторым входом третьего элемента ИЛИ и первым входом четвертого элемента ИЛИ, выход первого элемента И соединен с первым входом третьего элемента ИЛИ, выход которого соединен с входом четвертого элемента настройки соединения ячейки коммутации, выход которого соединен с первым выходом ячейки коммутации, выход второго элемента И соединен с вторым входом четвертого элемента ИЛИ, выход которого соединен с входом пятого элемента настройки соединения ячейки коммутации, выход которого соединен с вторым выходом ячейки коммутации, первые выходы ячеек коммутации верхнего горизонтального ряда соединены с вторыми входами соответствующих элементов ИЛИ верхней последовательности, в которой выход предыдущего элемента ИЛИ соединен с первым входом следующего элемента ИЛИ, вторые выходы ячеек коммутации нижнего горизонтального ряда соединены с первыми входами соответствующих элементов ИЛИ нижней последовательности, в которой выход предыдущего элемента ИЛИ соединен с вторым входом следующего элемента ИЛИ, выходы последних элементов ИЛИ верхней и нижней последовательностей и первые выходы ячеек коммутации последнего вертикального ряда первого блока ячеек коммутации, за исключением верхней ячейки этого ряда, соединены с соответствующими выходами первого блока ячеек коммутации, выходы первого блока ячеек коммутации соединены с соответствующими входами коммутатора, выходы которого соединены во втором блоке ячеек коммутации соответственно с первым входом первого элемента ИЛИ верхней последовательности, с вторым входом первого элемента ИЛИ нижней последовательности и с соответствующими первыми входами ячеек коммутации первого вертикального ряда, выходы последних элементов ИЛИ верхней и нижней последовательностей второго блока ячеек коммутации соединены соответственно с первым и вторым входами элемента ИЛИ, выход которого соединен с выходом устройства.

Сущность предлагаемого изобретения поясняется чертежами, где на фиг.1 - блок-схема программируемой нейроматрицы, на фиг.2 - блок-схема варианта блока ячеек коммутации, на фиг.3 - схема варианта блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, на фиг.4 - схема ячейки коммутации, на фиг.5 - блок-схема алгоритма программирования нейроматрицы, на фиг.6 - пример настройки и коммутации первого и второго блоков ячеек коммутации, обеспечивающих реализацию заданной логической функции.

Программируемая нейроматрица (фиг.1) содержит информационные входы 1₁÷1_n приема значений сигналов x_i, i=1÷n, представляющих разряды двоичного вектора х - аргумента логической функции ƒ(х), блок 2 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы 4(1)÷4(m) блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вход 3 установки сигнала "логическая единица", первый блок 5 ячеек коммутации, выходы 6(1)÷6(p) первого блока ячеек коммутации, коммутатор 7, выходы 8(1)÷8(q) коммутатора, второй блок 9 ячеек коммутации, первый вход 10 элемента ИЛИ, второй вход 11 элемента ИЛИ, элемент ИЛИ 12, выход 13 программируемой нейроматрицы.

Вариант первого и второго блоков ячеек коммутации (фиг.2) содержит элементы ИЛИ "1", ячейки коммутации 19, первые входы 14 ячеек коммутации, вторые входы 16 ячеек коммутации, входы управления 15 ячеек коммутации, первые выходы 17 ячеек коммутации, вторые выходы 18 ячеек коммутации.

Схема варианта блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ (фиг.3) содержит горизонтальные линии соединений входов элементов настройки с информационными входами 1₁÷1_n нейроматрицы, элементы настройки 20, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ "=1", линии соединений выходов элементов ИСКЛЮЧАЮЩЕЕ ИЛИ нижнего горизонтального ряда с выходами 4(1)÷4(m) блока. Для представляемого варианта m=5.

Ячейка коммутации (фиг.4) содержит 3 двухвходовых элемента ИЛИ "1", элемент ИЛИ "1" с прямым и инверсным входами, двухвходовой элемент И "&", элемент И "&" с прямым и инверсным входами, пять элементов настройки 20.

Вход 3 установки сигнала "логическая единица" соединен с первым входом 14 одной из ячеек коммутации 19 первого вертикального ряда первого блока 5 ячеек коммутации, в котором, как и в блоке 9, ячейки коммутации 19 расположены в узлах диагональной сетки так, что первый выход 17 предшествующей ячейки коммутации 19 соединен с вторым входом 16 следующей по диагонали верхней ячейки 19, а второй выход 18 предшествующей ячейки коммутации 19 соединен с первым входом 14 следующей по диагонали нижней ячейки 19, управляющие входы 15 ячеек коммутации 19 одного вертикального ряда в каждом из блоков 5 или 9 ячеек коммутации соединены с соответствующим управляющим входом соответствующего блока 5 или 9 ячеек коммутации, информационные входы 1₁÷1_n программируемой нейроматрицы соединены с соответствующими входами блока 2 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, в котором элементы ИСКЛЮЧАЮЩЕЕ ИЛИ образуют прямоугольную матрицу, причем в каждом вертикальном ряду элементов ИСКЛЮЧАЮЩЕЕ ИЛИ выход предшествующего элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с первым входом следующего элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход каждого из элементов ИСКЛЮЧАЮЩЕЕ ИЛИ одного горизонтального ряда элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с выходом соответствующего одного горизонтального ряда элементов настройки соединения 20 блока 2 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вход каждого из элементов настройки соединения 20 одного горизонтального ряда элементов настройки соединения 20 блока 2 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с соответствующим входом блока 2 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, первый вход каждого из элементов ИСКЛЮЧАЮЩЕЕ ИЛИ первого горизонтального ряда элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с выходом соответствующего элемента настройки соединения 20 первого горизонтального ряда элементов настройки соединения 20 блока 2, вход каждого из элементов настройки соединения 20 первого горизонтального ряда элементов настройки соединения 20 блока 2 соединен с соответствующим входом блока 2, выходы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ последнего горизонтального ряда соединены с соответствующими выходами 4(1)÷4(m) блока 2 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы 4(1)÷4(m) блока 2 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены с соответствующими входами управления первого 5 и второго 9 блоков ячеек коммутации, в каждом из которых в каждой ячейке коммутации 19 управляющий вход 15 соединен с входами первого и второго элементов настройки соединения 20 ячейки коммутации 19, выходы которых соединены соответственно с прямым и инверсным входами первого элемента ИЛИ, выход которого соединен с первым входом первого элемента И и вторым инверсным входом второго элемента И, первый 14 и второй 16 входы ячейки коммутации 19 соединены в ячейке 19 с соответствующими входами второго элемента ИЛИ, выход которого соединен с вторым входом первого элемента И, первым входом второго элемента И и входом третьего элемента настройки соединения 20 ячейки коммутации 19, выход которого соединен с вторым входом третьего элемента ИЛИ и первым входом четвертого элемента ИЛИ, выход первого элемента И соединен с первым входом третьего элемента ИЛИ, выход которого соединен с входом четвертого элемента настройки соединения 20 ячейки коммутации 19, выход которого соединен с первым выходом 17 ячейки коммутации 19, выход второго элемента И соединен с вторым входом четвертого элемента ИЛИ, выход которого соединен с входом пятого элемента настройки соединения 20 ячейки коммутации 19, выход которого соединен с вторым выходом 18 ячейки коммутации 19, первые выходы 17 ячеек коммутации 19 верхнего горизонтального ряда соединены с вторыми входами соответствующих элементов ИЛИ верхней последовательности, в которой выход предыдущего элемента ИЛИ соединен с первым входом следующего элемента ИЛИ, вторые выходы 18 ячеек коммутации 19 нижнего горизонтального ряда соединены с первыми входами соответствующих элементов ИЛИ нижней последовательности, в которой выход предыдущего элемента ИЛИ соединен с вторым входом следующего элемента ИЛИ, выходы последних элементов ИЛИ верхней и нижней последовательностей и первые выходы 17 ячеек коммутации 19 последнего вертикального ряда первого блока 5 ячеек коммутации, за исключением верхней ячейки 19 этого ряда, соединены с соответствующими выходами 6(1)÷6(р) первого блока 5 ячеек коммутации, выходы 6(1)÷6(р) первого блока 5 ячеек коммутации соединены с соответствующими входами коммутатора 7, выходы 8(1)÷8(q) которого соединены во втором блоке 9 ячеек коммутации соответственно с первым входом первого элемента ИЛИ верхней последовательности, с вторым входом первого элемента ИЛИ нижней последовательности и с соответствующими первыми входами 14 ячеек коммутации 19 первого вертикального ряда, выходы последних элементов ИЛИ верхней и нижней последовательностей второго блока 9 ячеек коммутации соединены соответственно с первым 10 и вторым 11 входами элемента ИЛИ 12, выход которого соединен с выходом 13 устройства.

Элемент настройки соединения 20 в результате настройки переводится в одно из двух состояний, условно называемых "соединение" и "отключение". В состоянии "соединение" элемент настройки соединения 20 осуществляет прямое электрическое соединение входа элемента с его выходом. В состоянии "отключение" элемент настройки соединения 20 осуществляет разрыв электрического соединения входа элемента с его выходом.

Посредством настроек ячейка 19 (фиг.4) переводится в одно из четырех рабочих состояний, обозначаемых далее символами "+", "-", "=", "0":

"+" - состояние прямого управления, при котором двоичный сигнал, поступающий на вход 14 или 16 ячейки, передается на выход 17 ячейки, если на управляющем входе 15 значение сигнала "логическая единица". Если же на входе 15 значение "логический ноль", то входной сигнал поступает на выход 18 ячейки;

"-" - состояние инверсного управления, при котором двоичный сигнал, поступающий на вход 14 или 16 ячейки, передается на выход 17 ячейки, если на управляющем входе 15 значение сигнала "логический ноль". Если же на входе 15 значение "логическая единица", то входной сигнал поступает на выход 18 ячейки;

"≡" - состояние прямой проводимости, при котором двоичный сигнал, поступающий на вход 14 или 16 ячейки, передается на выходы 17 и 18 ячейки независимо от состояния входа управления 15 ячейки;

"0" - состояние, при котором на выходах 17 и 18 ячейки устанавливается значение "логический ноль" независимо от состояния входа управления 15 ячейки и состояния входов 14 и 16 ячейки.

Состояние "+" обеспечивается настройкой элементов 20, при которой осуществляются соединение прямого входа первого элемента ИЛИ ячейки 19 с управляющим входом 15, соединение выходов третьего и четвертого элементов ИЛИ ячейки 19 соответственно с выходами 17 и 18, отключение инверсного входа первого элемента ИЛИ ячейки 19 от управляющего входа 15, отключение выхода второго элемента ИЛИ ячейки 19 от входов третьего и четвертого элементов ИЛИ ячейки 19. Для этого первый, четвертый и пятый элементы 20 ячейки 19 переводятся в состояние "соединение", а второй и третий элементы 20 ячейки 19 переводятся в состояние "отключение".

Состояние "-" обеспечивается настройкой элементов 20, при которой осуществляются соединение инверсного входа первого элемента ИЛИ ячейки 19 с управляющим входом 15, соединение выходов третьего и четвертого элементов ИЛИ ячейки 19 соответственно с выходами 17 и 18, отключение прямого входа первого элемента ИЛИ ячейки 19 от управляющего входа 15, отключение выхода второго элемента ИЛИ ячейки 19 от входов третьего и четвертого элементов ИЛИ ячейки 19. Для этого второй, четвертый и пятый элементы 20 ячейки 19 переводятся в состояние "соединение", а первый и третий элементы 20 ячейки 19 переводятся в состояние "отключение".

Состояние "≡" обеспечивается настройкой элементов 20, при которой осуществляются соединение выхода второго элемента ИЛИ ячейки 19 с входами третьего и четвертого элементов ИЛИ ячейки 19, соединение выходов третьего и четвертого элементов ИЛИ ячейки 19 соответственно с выходами 17 и 18. Для этого третий, четвертый и пятый элементы 20 ячейки 19 переводятся в состояние "соединение", а первый и второй элементы 20 ячейки 19 переводятся в состояние "отключение".

Состояние "0" обеспечивается настройкой элементов 20, при которой осуществляется отключение выходов третьего и четвертого элементов ИЛИ ячейки 19 соответственно от выходов 17 и 18. Для этого все пять элементов 20 ячейки 19 переводятся в состояние "отключение".

Программируемая нейроматрица работает следующим образом. Предварительно, в соответствии с алгоритмом программирования определяются и осуществляются необходимые настройки линейного блока 2 и ячеек коммутации 19 в блоках 5 и 9 ячеек коммутации. При поступлении двоичного сигнала х на информационные входы 1₁÷1_n устройства формируются управляющие сигналы на выходах 4(1)÷4(m) блока 2, которые представляют собой линейные по модулю два комбинации сигналов на входах 1₁÷1_n. Под воздействием сигналов управления 4(1)÷4(m) и настроек ячеек 19 блока 5 сигнал "логическая единица" с входа 3 поступает на один из выходов 6(1)÷6(р) блока 5, далее на соответствующий вход коммутатора 7 и с одного из выходов 8(1)÷8(q) коммутатора поступает на один из входов блока 9. Если этот вход соединен с входом элемента ИЛИ верхней или нижней последовательности, то затем сигнал "логическая единица" поступает соответственно на вход 10 или вход 11 элемента ИЛИ 12 и с выхода элемента ИЛИ поступает на выход 13 устройства. Если сигнал "логическая единица" поступает с одного из выходов 8(1)÷8(q) на вход блока 9 и с него на вход 17 одной из ячеек 19 блока 9, то под воздействием сигналов управления 4(1)÷4(m) блока 2 и настроек ячеек 19 блока 9 этот сигнал поступит либо на вход одного из элементов ИЛИ верхней или нижней последовательности и далее указанным выше путем на выход 13 устройства, либо сигнал "логическая единица" поступит на вход 14 или 16 одной из ячеек 19, установленной в состояние "0", и в результате его дальнейшее продвижение невозможно и на выходе 13 устройства установится сигнал "логический ноль". При поступлении на входы 1₁÷1_n следующего сигнала х блок 2 вырабатывает другую двоичную комбинацию выходных сигналов, под воздействием которой в блоках 5 и 9 формируется другой путь передачи сигнала "логическая единица" и будет сформирована новая реакция устройства на вновь поступивший сигнал. Таким образом осуществляется реализация заданной логической функции ƒ(x).

Блок-схема алгоритма программирования нейроматрицы (фиг.5) содержит четыре блока операторов обработки исходных данных и два условных оператора. Содержание операторов обработки исходных данных следующее.

Определение h(x). На первом шаге алгоритма по исходной функции ƒ(x) определяются величины k₀=|X₀| и k₁=|X₁|, где

|X| - мощность множества Х аргументов х функции ƒ(x);

X=X₀∪X₁; X₀∩X₁=⊘.

Представляющая функция h(х) задается по формуле

r=min{k₀,k₁}.

На последующих шагах алгоритма программирования известна линеаризованная сумма t=1÷m, где

d_i(x) - линейная по модулю два функция от аргумента X.

Линеаризованная сумма w(x) задает разбиение на множестве X.

. Для каждого подмножества Xⁱ задается представляющая функция

r=min{k₀(i),k₁(i)}.

При определении настроек блоков 2 и 5 вычисляется суммарная представляющая функция , для которой вычисляется спектр по Уолшу S_h. При определении последующих настроек блока 2 и соответствующих настроек блока 9 для каждой hⁱ(x) вычисляется отдельно спектр и формируется сумма , где

- модуль, абсолютные значения коэффициентов спектра .

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

ω=((ω₁,ω₂,K,ω_n) - аргумент спектра, двоичное число.

При определении настроек блоков 2 и 5 на выбор накладывается ограничение. Аргументы ω выбираемых коэффициентов должны быть линейно независимы в поле вычетов GF_n(2).

Настройки блоков 2, 5, 9. Определяется, какие из элементов настроек 20 в блоке 2 и в ячейках 19 блоков 5 и 9 обеспечивают соединение и отключение входов элементов ИСКЛЮЧАЮЩЕЕ ИЛИ в блоке 2, входов элементов ИЛИ и выходов 17 и 18 в ячейках 19 блоков 5 и 9.

Вычисление w(x) и распределения R_w.

t=1÷m, где

ω_j - j-й разряд аргумента ω, выбранного при определении настройки выхода 4(i).

В таблице распределения R_w указаны значения , , где

- мощность множества ;

w - значение линеаризованной суммы w(x);

i∈{0,1}, w∈(0,...,t};

Например,

w01......t-1tk₀k₀(0)k₀(1)......k₀(t-1)k₀(t)k₁k₁(0)k₁(1)......k₁(t-1)k₁(t)

Определение соединений в коммутаторе 7. Это обычная операция, связанная с конкретной реализацией коммутатора.

Коррекция исходной логической функции ƒ(x). Это определение аргументов x∈Х, значение ƒ(х) для которых реализовано на данном этапе программирования, исключение их из дальнейшего анализа.

Условный оператор . Проверяется истинность одного из равенств

k₀(w_η)=0, или k₀(w_κ)=0, где

где w_η - нижняя граница анализируемого диапазона значений w(x);

w_κ - верхняя граница анализируемого диапазона значений w(x).

Условный оператор R_w=0. Проверяется в таблице R_w выполнение условия

Пример. Пусть случайным образом задана частично определенная логическая функция ƒ(x) восьми переменных, для которой f(x₁,x₂,...,x₈)=1 при следующих значениях аргумента: {x}_ƒ(x)=1={01, 08, 0D, 13, 1A, 1D, 20, 26, 2A, 32, 3E, 44, 50, 58, 5D, 62, 81, 84, 8A, 8F, 92, 98, 9B, 9C, 9F, А0, А7, А8, AF, В5, В9, С3, С6, CB, D1, D4, DD, Е3, Е7, Е8, ED, F1, F9},

a f(x₁,x₂,...,x₈)=0 для следующего множества аргументов:

{x}_ƒ(x)=0={02, 14,16, 19, 1F, 23, 2C, 30, 38, 3D, 43, 47, 4E, 51, 57, 59, 63, 64, 6B, 76, 7E, 80, 85, 97, 9A, A1, AC, AE, B6, BA, C1, CD, D0, D5, D6, D9, DE, ЕЕ, F3, F5, FB, FF}.

Здесь в перечислениях аргументов первый шестнадцатеричный кодовый символ представляет полубайт (x₁,x₂,x₃,x₄), а второй - полубайт (х₅,х₆,х₇,x₈).

В соответствии с алгоритмом программирования первоначально вычисляются величины k₀|X₀|, k₁=|X₁|, где

|X| - мощность множества Х;

X=X₀∪X₁; X₀∩X₁=⊘.

Для исходной функции k₀=42, k₁=43. Следовательно, представляющая функция h(x) определяется следующим образом:

Вычисление по Уолшу спектра S_h этой функции и выбор максимального по абсолютному значению коэффициента спектра

где ω - двоичный аргумент спектра S_h;

ω=(ω₁,ω₂,ω₃,ω₄,ω₅,ω₆,ω₇,ω₈)=(00110101);

ω_i∈{0,1}, i=1÷8.

позволяют найти первые настройки блоков 2 и 5. На выходе 4(1) блока 2 необходимо реализовать линейную функцию

следовательно, элементы настройки соединения 20 в блоке 2 должны обеспечить соединение информационных входов 1₃, 1₄, 1₆, 1₈ устройства с вторыми входами соответствующих элементов ИСКЛЮЧАЮЩЕЕ ИЛИ первого вертикального ряда в блоке 2. Информационные входы 1₁, 1₂, 1₅, 1₇ соответствующими элементами настройки соединения 20 блока 2 отключаются от входов элементов ИСКЛЮЧАЮЩЕЕ ИЛИ первого вертикального ряда блока 2.

В соответствии с этим элемент настройки соединения 20 блока 2, вход которого соединен с информационным входом 1_i, i=1÷8, а выход соединен с входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ первого вертикального ряда в блоке 2, должен быть переведен в состояние "соединение", если соответствующий разряд ω_i=1, и в состояние "отключение", если ω_i=0.

Выход 4(1) соединяется с первым управляющим входом блока 5 и управляющие сигналы поступают на первые входы 14 ячеек 19 первого вертикального ряда в блоке 5. Так как sign(S_h(ω))=-1, то ячейка 19, вход 14 которой соединен с входом 3 устройства, устанавливается соответствующими настройками в состояние прямого управления "+". При этом в данной ячейке отключается инверсный вход первого элемента ИЛИ, устанавливается соединение прямого входа первого элемента ИЛИ с соответствующим управляющим входом блока 5, разрывается соединение выхода второго элемента ИЛИ с соответствующими входами третьего и четвертого элементов ИЛИ, устанавливается соединение выходов третьего и четвертого элементов ИЛИ с соответствующими выходами 17 и 18 ячейки. Остальные ячейки 19 первого вертикального ряда в блоке 5 устанавливаются в состояние "0", так как их входы 14 и 16 не задействованы. С этой целью настройками элементов 20 этих ячеек размыкаются соединения выходов третьего и четвертого элементов ИЛИ с соответствующими выходами 17 и 18 ячеек.

В результате при поступлении на информационные входы 1₁÷1₈ двоичного кода х на выход 17 функционирующей ячейки 19 первого вертикального ряда блока 2 поступит сигнал "логическая единица", если линеаризованная сумма

Если же w(x)=d₁(x)=0, то сигнал "логическая единица" поступит на выход 18 этой ячейки. Для дальнейшего анализа необходимо составить распределение R_w аргументов х∈X по значениям линеаризованных сумм w(x):

w01k₀2814k₁1330

В таблице распределения R_w указаны значения , , где

- мощность множества ;

w - значение линеаризованной суммы w(х);

i∈{0,1}, w∈{0,1};

Граничные значения k₀ представляются значениями k₀ в правом и левом значащих столбцах таблицы R_w. После первого шага алгоритма k₀(0)=28≠0, k₀(1)=14≠0. Поэтому необходимо определить следующую настройку блоков 2 и 5. Для каждого значения линеаризованной суммы w(x) задаются представляющие функции h(x):

если w(x)=0, то

если w(x)=1, то

Вычисляется спектр S_h и выбирается максимальный по амплитуде и линейно независимый по аргументу ω коэффициент S_h(ω)=S_h(E2)=S_h(11100010), sign(S_h(E2))=-1. Следовательно, соответствующими настройками во втором столбце блока 2 формируется линейная функция , а в блоке 5 устанавливаются в состояние прямого управления "+" те ячейки 19 второго столбца, которые соединены с выходами функционирующей ячейки первого столбца. Остальные ячейки второго столбца устанавливаются в состояние "0".

Состояния выходов функционирующих ячеек 19 второго столбца блока 5 теперь будут определяться значением линеаризованной суммы . Если w(x)=2, то сигнал "логическая единица" поступит на выход 17 верхней функционирующей ячейки; при w(x)=1 "логическая единица" поступит либо на выход 18 верхней, либо на выход 17 нижней функционирующей ячейки, и далее поступит на выход второго элемента ИЛИ ячейки третьего столбца, соединенной входами 14 и 16 с указанными выходами; при w(x)=0 "логическая единица" поступит на выход 18 нижней функционирующей ячейки второго столбца блока 5. Теперь распределение R_w аргументов х по значениям w(x) отразится в таблице следующим образом

w012k₀11274k₁111319

Граничные значения k₀(0)=11≠0, k₀(2)=4≠0. Поэтому необходимо произвести последующую настройку блоков 2 и 5. Далее цикл повторяется дважды и в результате определяются линейно независимые настройки блока 2:

и . Так как в обоих случаях знаки выбранных спектральных коэффициентов sign(S_h(ω))=-1, то настройками в третьем и четвертом столбцах блока 5 устанавливаются в состояние прямого управления "+" те ячейки, входы которых подключены к выходам функционирующих ячеек предшествующего столбца, остальные ячейки устанавливаются в состояние "0". Распределение R_w, инициируемое линеаризованной суммой , отражено в следующей таблице:

w01234k₀0142530k₁6912106

Здесь граничные значения k₀ удовлетворяют условию выхода из цикла k₀(0)=0 и k₀(4)=0. Поэтому после определения функции h(х) и вычисления спектра S_h выбирается соответствующий по знаку и максимальный по амплитуде коэффициент с аргументом ω, полученным на предыдущих этапах пройденного цикла вычислений. В результате последняя, пятая настройка блока 2 описывается выражением . Все ячейки 19 пятого вертикального столбца блока 5, соединенные входами с выходами функционирующих ячеек четвертого столбца, переводятся в состояние "+". Линеаризованная сумма индуцирует распределение R_w:

w012345k₀08191230k₁6941176

В результате произошло увеличение диапазона значений w(x) и увеличение отношения k₀(w)/k₁(w) в центре диапазона. Это обеспечит сокращение количества необходимых управляющих входов для блока 9 и сокращение количества потребных ячеек коммутации 19 в этом блоке. Построение и настройки блока 5 завершены. Выход 17 верхней функционирующей ячейки 19 пятого столбца блока 5 соединяется с вторым входом элемента ИЛИ верхней последовательности, а выход 18 нижней функционирующей ячейки 19 пятого столбца соединяется с первым входом элемента ИЛИ нижней последовательности. Это и определяет объем блока 5.

Следующий шаг по оптимизации блока 9 производится посредством коммутации. Заданием соединений в коммутаторе 7 перераспределяются связи между выходами ячеек 19 блока 5 и входами ячеек 19 блока 9. Соединения необходимо установить для входов крайних ячеек 19 первого столбца блока 9 с выходами соответствующих ячеек 19 последнего столбца блока 5 так, чтобы одна или несколько центральных ячеек 19 первого столбца блока 9 оказались свободными от соединений. Для данного примера размерность n=8 реализуемой функции невелика, поэтому достаточно освободить одну центральную ячейку 19 первого столбца блока 9. Формально это описывается новым распределением R_w:

w0123456k₀081901230k₁69401176

Свободная ячейка 19 первого столбца блока 9, соответствующая уровню диапазона w(x)=3, устанавливается в состояние "0". Для определения последующих настроек блоков 2 и 9 необходимо осуществить коррекцию области определения Х функции ƒ(x).

Из анализа необходимо исключить те аргументы х∈Х₁, для которых w(x)=0 либо w(x)=6. При поступлении соответствующих этим аргументам двоичных кодов на входы 1₁÷1_n сигнал "логическая единица" поступит на входы элементов ИЛИ верхней либо нижней последовательности блока 5, далее на коммутатор 7, на входы элементов ИЛИ соответственно верхней либо нижней последовательности блока 9, входы 10 либо 11 элемента ИЛИ 12 и окончательно - на выход 13 устройства. Таким образом, осуществится реализация значений ƒ(x) на этих аргументах. Соответственно следует сократить анализируемый диапазон значений линеаризованной взвешенной суммы w(x). Поэтому рассматриваемое распределение R_w имеет вид:

w12345k₀8190123k₁940117

При определении настроек блоков 2 и 9 для каждого значения w=i, i={1, 2, 4, 5} вычисляются функции

где r=min{k₀(i),k₁(i)}, w(x)=i.

Затем вычисляются спектры по Уолшу S_h этих функций и анализируется сумма их абсолютных величин . Настройка блока 2 определяется значением аргумента ω максимального коэффициента S(ω). Настройки блока 9 определяются двумя факторами: 1) каждая ячейка 19 одного столбца блока 9 имеет соответствующее представление w(x)=i в диапазоне значений w(x), которое формируется суммой линейных членов d_i, полученных на этапах настройки предшествующих столбцов, и настройка соответствующей ячейки зависит от соотношения

где w_η - нижняя граница диапазона (в данном случае w_η=1);

w_κ - верхняя граница диапазона (в данном случае w_κ=5);

2) настройка каждой ячейки 19 одного столбца блока 9 зависит от sign(S_h(ω)) функции h(x), определяемой для .

Ячейка 19 устанавливается в состояние "+", если (i≥(w_η+w_κ)/2) & (sign(S_h(ω))=-1) или (i<(w_η+w_k)/2) & (sign(S_h(ω))=1). В противном случае ячейка 19 устанавливается в состояние инверсного управления "-".

В результате для выхода 4(6) блока 2 определяется линейная настройка , а настройки ячеек 19 первого столбца блока 9 по соответствующим значениям w(x) распределятся согласно таблице

w12345η--0++

Для завершения примера ниже приводятся перечень остальных настроек блока 2 и перечень формирующихся распределений R_w с присоединенной строкой настроек η. При появлении в R_w значений (k₀(w)=0) & (k₁(w)≠0) или (k₁(w)=0) & (k₀(w)≠0) производится необходимая коррекция подобластей определения X₁ или X₀ соответственно.

Распределения R_w и настройки η для ячеек 19 столбцов 2÷7 блока 9:

- распределение R_w для второго столбца блока 9

w123456k₀214111032k₁652297η+-+--+

- распределение R_w для третьего столбца блока 9

Здесь из распределения R_w для третьего столбца ячеек блока 9 очевидно, что ситуация или возможна только для аргументов х∈X₁, так как (k₀(1)=0) & (k₁(1)=5) и (k₀(7)=0) & (k₁(7)=5). Поэтому выход 17 верхней ячейки второго столбца и выход 18 нижней ячейки второго столбца следует соединить с входами элементов ИЛИ соответственно верхней и нижней последовательностей. При этом на выходе 13 устройства появится "логическая единица", что обеспечит реализацию значения ƒ(x)=1 для соответствующих аргументов х. В таблице для η(1) и η(7) соответственно указаны символы ИЛИ вместо значений настроек. Коррекция подобласти определения X₁ формально описывается выражением X₁:=Х₁-X¹ ₁-Х⁷ ₁. Соответственно сокращается анализируемый диапазон и w принимает значение w∈{2,...,6};

- распределение R_w, для четвертого столбца блока 9

w234567k₀212141031k₁421275η-+++--

Здесь в результате добавления в линеаризованную сумму w(x) нового линейного члена анализируемый диапазон w вновь увеличился: w∈{2,...,7};

- распределение R_w для пятого столбца блока 9

w2345678k₀051514620k₁2410464ηИЛИ+-0++ИЛИ

Здесь для пятого столбца блока 9 необходимо пояснить следующее. Для w(x)=5 (k₁(5)=0) & (k₀(5)=14), поэтому следует произвести коррекцию области Х₀ и удалить из нее и из дальнейшего анализа аргументы . Формально это описывается выражением Х₀:=Х₀-Х⁵ ₀. В блоке 9 в пятом столбце необходимо произвести установку ячейки, соответствующей w(x)=5 в состояние "0" с тем, чтобы при поступлении на входы 1₁÷1_n указанного кода х сигнал "логическая единица" не проходил далее по коммутационной схеме блока 9. В этом случае на выходе 13 устройства сигнал "логическая единица" не появится и устройство реализует значение ƒ(x)=0 для соответствующих значений аргумента х. Поэтому η(5)=0.

Из распределения для пятого столбца ячеек блока 9 также очевидно, что ситуация w(x)=2 или w(x)=8 возможна только для аргументов x∈X₁, так как (k₀(2)=0) & (k₁(2)=2) или (k₀(8)=0) & (k₁(8)=4). Поэтому выход 17 верхней ячейки четвертого столбца блока 9 и выход 18 нижней ячейки четвертого столбца блока 9 следует соединить с входами элементов ИЛИ соответственно верхней и нижней последовательностей элементов ИЛИ. При этом на выходе 13 устройства поступит "логическая единица", что обеспечит реализацию значения ƒ(x)=1 для соответствующих аргументов х. В таблице для η(2) и η(8) соответственно указаны символы "ИЛИ" вместо значений настроек ячеек коммутации;

- распределение R_w для шестого столбца блока 9

w345678k₀1118620k₁320154η++0+-≡

При реализации указанных ранее настроек на выходе 17 верхней ячейки 19 пятого столбца блока 9 будет поступать сигнал "логическая единица" при поступлении на информационные входы устройства двоичных сигналов, соответствующих аргументам х, для которых w(x)=8. Для этих же аргументов исходная функция ƒ(x)=1, так как (k₀(8)=0) & (k₁(8)=4). Вместе с тем выход 17 верхней ячейки 19 пятого столбца блока 9 в силу регулярности структуры не может быть соединен непосредственно с входом элемента ИЛИ верхней последовательности элементов ИЛИ, а соединен с входом 16 верхней ячейки шестого столбца. В связи с этим для адекватного представления функции ƒ(x) необходимо установить верхнюю ячейку 19 шестого столбца в состояние прямой проводимости: η(8)="≡".

Ячейку 19 шестого столбца блока 9, соответствующую значению линеаризованной суммы w(x)=5, необходимо перевести в состояние "0", так как на ее входы 14 или 16 поступит сигнал "логическая единица" только для аргументов х∈Х₀, ибо из распределения следует (k₀(5)=8) & (k₁(5)=0);

- распределение R_w для седьмого столбца блока 9

w3456789k₀0665300k₁3200154ηИЛИ+00+≡ИЛИ

После указанной в последней таблице настройки η под воздействием управляющего сигнала образуется распределение R_w

w456789k₀060300k₁200015

Вследствие этого настройки последующих столбцов блока 9 должны устанавливать ячейки 19 либо в состояние "0", либо в состояние "≡". Соответствующие обозначения настроек коммутатора 7, блоков 5 и 9, приведены на фиг.6. Процедура программирования нейроматрицы для реализации исходной функции ƒ(x) завершена.

Изобретение относится к вычислительной технике. Техническим результатом является увеличение функциональных возможностей, снижение аппаратных затрат и повышение быстродействия устройств, реализующих логические функции. Нейроматрица содержит блок элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, блоки ячеек коммутации, выполненных в виде однородной среды, и коммутатор. Определенная настройка блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ задает линейные преобразования входного двоичного сигнала. Линеаризованный выходной сигнал далее поступает на входы управления блоков ячеек коммутации. Соответствующей настройкой однородной среды на выходе нейроматрицы реализуется произвольная заданная логическая функция. 6 ил.

Программируемая нейроматрица, предназначенная для реализации логических функций, содержащая вход установки сигнала "логическая единица", элементы настройки соединения, входящие в состав каждой ячейки коммутации и задающие вид линейного преобразования входного двоичного сигнала, первый и второй блоки ячеек коммутации, в каждом из которых ячейки коммутации расположены в узлах диагональной сетки так, что первый выход предшествующей ячейки коммутации соединен с вторым входом следующей по диагонали верхней ячейки, а второй выход предшествующей ячейки коммутации соединен с первым входом следующей по диагонали нижней ячейки, управляющие входы ячеек коммутации одного вертикального ряда в каждом блоке ячеек коммутации соединены с соответствующим управляющим входом соответствующего блока ячеек коммутации, вход установки сигнала "логическая единица" соединен с первым входом одной из ячеек коммутации первого вертикального ряда первого блока ячеек коммутации, отличающаяся тем, что в нее введены коммутатор, элементы И, ИЛИ, последовательности элементов ИЛИ, блок элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, при этом информационные входы программируемой нейроматрицы соединены с соответствующими входами блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, в котором элементы ИСКЛЮЧАЮЩЕЕ ИЛИ образуют прямоугольную матрицу, причем в каждом вертикальном ряду элементов ИСКЛЮЧАЮЩЕЕ ИЛИ выход предшествующего элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с первым входом следующего элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход каждого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ одного горизонтального ряда элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с выходом соответствующего одного горизонтального ряда элементов настройки соединения блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вход каждого из элементов настройки соединения одного горизонтального ряда элементов настройки соединения блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с соответствующим входом блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, первый вход каждого из элементов ИСКЛЮЧАЮЩЕЕ ИЛИ первого горизонтального ряда элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с выходом соответствующего элемента настройки соединения первого горизонтального ряда элементов настройки соединения блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вход каждого из элементов настройки соединения горизонтального ряда элементов настройки соединения блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с соответствующим входом блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ последнего горизонтального ряда соединены с соответствующими выходами блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, при этом элементы настроек соединений, входящие в состав блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, предназначены для формирования управляющих сигналов на выходах блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, которые представляют собой линейные по модулю два комбинации сигналов на входах блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены с соответствующими входами управления первого и второго блоков ячеек коммутации, в каждом из которых в каждой ячейке коммутации управляющий вход соединен с входами первого и второго элементов настройки соединения ячейки коммутации, выходы которых соединены соответственно с прямым и инверсным входами первого элемента ИЛИ, выход которого соединен с первым входом первого элемента И и вторым инверсным входом второго элемента И, первый и второй входы ячейки коммутации соединены в ячейке с соответствующими входами второго элемента ИЛИ, выход которого соединен с вторым входом первого элемента И, первым входом второго элемента И и входом элемента настройки соединения ячейки коммутации, выход которого соединен со вторым входом третьего элемента ИЛИ и первым входом четвертого элемента ИЛИ, выход первого элемента И соединен с первым входом третьего элемента ИЛИ, выход которого соединен с входом четвертого элемента настройки соединения ячейки коммутации, выход которого соединен с первым выходом ячейки коммутации, при этом упомянутые элементы настройки соединения, входящие в состав каждой ячейки коммутации, предназначены для перевода этой ячейки коммутации в одно из четырех состояний: 1) состояние прямого управления, при котором двоичный сигнал, поступающий на один из входов этой ячейки коммутации, передается на первый выход этой ячейки коммутации, если на управляющем входе этой ячейки коммутации получено значение сигнала "логическая единица", а если на управляющем входе получено значение "логический ноль", то двоичный сигнал, поступающий на один из входов этой ячейки коммутации, поступает на второй выход этой ячейки коммутации; 2) состояние инверсного управления, при котором двоичный сигнал, поступающий на один из входов этой ячейки коммутации, передается на первый выход этой ячейки коммутации, если на управляющем входе этой ячейки коммутации получено значение сигнала "логический ноль", а если на управляющем входе этой ячейки коммутации получено значение "логическая единица", то двоичный сигнал, поступающий на один из входов этой ячейки коммутации, поступает на второй выход ячейки; 3) состояние прямой проводимости, при котором двоичный сигнал, поступающий на один из входов этой ячейки коммутации, передается на первый и второй выходы этой ячейки коммутации независимо от состояния входа управления этой ячейки коммутации; 4) состояние, при котором на первом и втором выходах этой ячейки коммутации устанавливается значение "логический ноль" независимо от состояния входа управления этой ячейки коммутации и состояния первого и второго входов этой ячейки коммутации, выход второго элемента И соединен со вторым входом четвертого элемента ИЛИ, выход которого соединен с входом пятого элемента настройки соединения ячейки коммутации, выход которого соединен со вторым выходом ячейки коммутации, первые выходы ячеек коммутации верхнего горизонтального ряда соединены со вторыми входами соответствующих элементов ИЛИ верхней последовательности, в которой выход предыдущего элемента ИЛИ соединен с первым входом следующего элемента ИЛИ, вторые выходы ячеек коммутации нижнего горизонтального ряда соединены с первыми входами соответствующих элементов ИЛИ нижней последовательности, в которой выход предыдущего элемента ИЛИ соединен с вторым входом следующего элемента ИЛИ, выходы последних элементов ИЛИ верхней и нижней последовательностей и первые выходы ячеек коммутации последнего вертикального ряда первого блока ячеек коммутации, за исключением верхней ячейки этого ряда, соединены с соответствующими выходами первого блока ячеек коммутации, выходы первого блока ячеек коммутации соединены с соответствующими входами коммутатора, выходы которого соединены во втором блоке ячеек коммутации соответственно с первым входом первого элемента ИЛИ верхней последовательности, с вторым входом первого элемента ИЛИ нижней последовательности и с соответствующими первыми входами ячеек коммутации первого вертикального ряда, выходы последних элементов ИЛИ верхней и нижней последовательностей второго блока ячеек коммутации соединены соответственно с первым и вторым входами элемента ИЛИ, выход которого соединен с выходом устройства.