Ячейка однородной среды

Ячейка однородной среды относится к автоматике и вычислительной технике и может быть использована в системах обработки информации, в контурах управления адаптивных промышленных роботов, в системах контроля знаний обучаемых, при проектировании БИС и СБИС. Техническим результатом является расширение функциональных возможностей за счет реализации класса повторных упорядоченных произвольных нормальных булевых формул из h букв, а также систем булевых формул как с пропусками аргументов, так и без них. Указанный результат достигается за счет того, что ячейка содержит восемь входов, сорок пять элементов И, три элемента ИЛИ, три выхода. 12 ил.

 

Изобретение относится к автоматике и вычислительной технике и предназначено для построения линейных и плоскостных однородных структур, реализующих бесповторные упорядоченные произвольные (в том числе любые скобочные) нормальные формулы из h букв, формулы из классов повторных и бесповторных упорядоченных и неупорядоченных булевых формул как с пропусками аргументов, так и без них, а также систем булевых формул, заданных в базисе И, ИЛИ, НЕ при равной доступности прямых и инверсных выходов источников информации.

Известна ячейка однородной среды, содержащая элементы И, ИЛИ предназначенная для построения линейных однородных структур, реализующих произвольные дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ) из h букв, произвольные скобочные формы при h≤11, большой класс скобочных форм для h>11, а также класс бесповторных упорядоченных булевых формул с пропусками аргументов, при равной доступности прямых и инверсных выходов источников информации (Авторское свидетельство СССР №1448344, от 01.00.1988, кл. G 06 F 7/00, бюл. №48 от 30.12.88).

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

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

Под упорядоченными булевыми формулами понимается следующее. Пусть ячейки соединены так, что образуют однородную линейную структуру. Пронумеруем входы ячеек однородной структуры (исключая настроечные входы) и каждому из них поставим в соответствие логический аргумент вида х_i, где i - номер ввода однородной структуры. Если в записи бесповторной булевой формулы индекс i при логических аргументах возрастает слева направо, то будем считать, что эта формула упорядочена. Упорядоченной будем считать формулу и в том случае, если существуют тождественные преобразования в результате которых получается запись формулы с возрастающими слева направо индексами аргументов. Во всех остальных случаях булевы формулы являются неупорядоченными. Если в записи упорядоченной бесповторной булевой формулы аргументы с теми или иными индексами отсутствуют, то будем считать, что эта формула содержит пропуски соответствующих аргументов.

Наиболее близкой по технической сущности к предлагаемой является ячейка, содержащая элементы И, ИЛИ, причем семь входов ячейки подключены к соответствующим входам логических элементов, а на двух выходах данной ячейки обеспечивается формирование заданных функциональных зависимостей. Данная ячейка предназначена для построения линейных и плоскостных однородных структур, реализующих бесповторные упорядоченные произвольные (и в том числе любые скобочные) нормальные формулы из h букв, а также формулы из классов повторных и бесповторных неупорядоченных булевых формул как с пропусками аргументов, так и без них (АС №1476456 от 03.01.1989 г., кл. G 06 F 7/00, бюл. №16 от 30.04.1989).

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

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

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

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

Поставленная цель достигается тем, что ячейка однородной среды, содержащая тринадцать элементов И и два элемента ИЛИ, причем первый выход ячейки соединен с первым элементом ИЛИ, а второй выход ячейки соединен со вторым элементом ИЛИ, первый настроечный вход ячейки соединен с первыми прямыми входами седьмого, одиннадцатого, восемнадцатого, двадцать первого, двадцать четвертого, двадцать пятого, двадцать шестого, двадцать седьмого, сорок второго, сорок пятого элементов И, вторыми прямыми входами тридцатого и тридцать седьмого элементов И, первыми инверсными входами восьмого, четырнадцатого, шестнадцатого, тридцать третьего, тридцать пятого, тридцать восьмого, сорок первого элементов И, выход которого соединен с двенадцатым входом третьего элемента ИЛИ, четырнадцатый вход которого соединен с выходом сорок третьего элемента И, первый прямой вход которого соединен со вторым настроечным входом ячейки и с первыми прямыми входами тридцать девятого, двадцать восьмого, двадцатого, пятнадцатого, четырнадцатого, восьмого, пятого элементов И, первыми инверсными входами двенадцатого, двадцать второго, тридцать первого элементов И, с вторыми прямыми входами восемнадцатого, двадцать шестого, двадцать седьмого элементами И, с третьими прямыми входами двадцать пятого, тридцать четвертого, тридцать седьмого элементов И, со вторыми инверсными входами сорок первого и тридцать третьего элементов И, выход которого соединен с четвертым входом третьего элемента ИЛИ, первый, второй, пятый, шестой, седьмой, восьмой, девятый, десятый, тринадцатый, входы которого соединены с выходами тридцатого, тридцать первого, тридцать четвертого, тридцать пятого, тридцать шестого, тридцать седьмого, тридцать восьмого, тридцать девятого, сорок второго элементов И соответственно, а шестнадцатый вход третьего элемента ИЛИ соединен с выходом сорок пятого элемента И, второй вход которого соединен с первыми прямыми входами двенадцатого и тринадцатого элементов И, с вторым прямым входом четырнадцатого элемента И, с третьими прямыми входами одиннадцатого, двадцать шестого, двадцать восьмого, двадцать девятого, сорок второго, сорок третьего, сорок четвертого элементов И, с четвертым прямым входом двадцать седьмого элемента И и выходом четвертого элемента И, первый вход которого соединен с инверсным входом третьего элемента И, первым инверсным входом первого элемента И, третьим настроечным входом ячейки и прямым входом второго элемента И, выход которого соединен с четвертым входом тридцать седьмого элемента И, с третьим входом тридцать шестого элемента И, со вторыми прямыми входами двадцатого, тридцать четвертого, тридцать пятого элементов И, с первым входом девятого элемента И, выход которого соединен с пятым входом первого элемента ИЛИ, первый, второй, третий, четвертый, шестой, седьмой, восьмой, девятый, десятый входы которого соединены с выходами пятого, шестого, седьмого, восьмого, десятого, одиннадцатого, двенадцатого, тринадцатого, четырнадцатого элементов И соответственно, а выход первого элемента ИЛИ является первым выходом ячейки, четвертый настроечный вход которой соединен со вторым прямым входом четвертого элемента И, с прямым входом третьего элемента И, с инверсным входом второго элемента И и со вторым инверсным входом первого элемента И, выход которого соединен с первым прямым входом шестнадцатого элемента И, со вторыми прямыми входами восьмого, семнадцатого, тридцать первого, тридцать третьего и с третьими входами пятого, шестого, седьмого, пятнадцатого, девятнадцатого, тридцатого, тридцать второго элементов И, выход которого соединен с третьим входом третьего элемента ИЛИ, одиннадцатый вход которого соединен с выходом сорокового элемента И, третий вход которого соединен с выходом третьего элемента И, со вторыми прямыми входами десятого, двадцать четвертого, тридцать восьмого, сорок первого элементов И, с третьими прямыми входами двадцать первого, двадцать второго, тридцать девятого элементов И, с четвертыми входами двадцать третьего и двадцать пятого элементов И, выход которого соединен с одиннадцатым входом второго элемента ИЛИ, пятый вход которого соединен с выходом девятнадцатого элемента И, первый вход которого соединен с первыми прямыми входами шестого, десятого, двадцать третьего, двадцать девятого, тридцать второго, тридцать третьего, тридцать шестого, тридцать седьмого, сорокового, сорок первого элементов И, со вторыми прямыми входами пятого, седьмого, одиннадцатого, двенадцатого, тринадцатого, двадцать пятого элементов И, с третьим входом двадцать седьмого элемента И и является пятым входом ячейки, шестой вход которой соединен с первыми прямыми входами семнадцатого и двадцать второго элементов И, со вторыми входами шестого, девятого, двадцать третьего, двадцать восьмого, двадцать девятого элементов И, с третьими прямыми входами восьмого, тринадцатого, четырнадцатого, двадцать четвертого элементов И, с четвертым входом восемнадцатого элемента И, выход которого соединен с четвертым входом второго элемента ИЛИ, пятнадцатый, четырнадцатый, тринадцатый, двенадцатый, десятый, девятый, восьмой, седьмой, шестой, третий, второй, первый входы которого являются выходами двадцать девятого, двадцать восьмого, двадцать седьмого, двадцать шестого, двадцать четвертого, двадцать третьего, двадцать второго, двадцать первого, двадцатого, семнадцатого, шестнадцатого, пятнадцатого элементов И соответственно, второй вход пятнадцатого элемента И соединен с первым входом сорок четвертого элемента И, со вторыми прямыми входами шестнадцатого, девятнадцатого, двадцать первого, двадцать второго элементов И, с третьими входами семнадцатого, восемнадцатого, двадцатого, двадцать третьего, сорок пятого элементов И, с четвертым входом двадцать шестого элемента И и является седьмым входом ячейки, восьмой вход которой соединен с первыми прямыми входами тридцатого, тридцать первого, тридцать четвертого, тридцать пятого, тридцать восьмого элементов И, с вторыми входами тридцать второго, тридцать шестого, тридцать девятого, сорокового, сорок второго, сорок третьего, сорок четвертого элементов И, выход которого соединен с пятнадцатым входом третьего элемента ИЛИ, выход которого является третьим выходом ячейки.

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

На фиг.1 представлена классификация бесповторных булевых формул, на фиг.2 показана схема ячейки, на фиг.3 - коммутационные и функциональные схемы, реализуемые ячейкой путем настройки, на фиг.4 - 12 - возможные соединения ячеек в среде.

Ячейка (фиг.2) содержит входы 1-8, элементы И 1-45 (позиции 9-53), элементы ИЛИ 1-3 (позиции 54-56), выходы 1-3 (позиции 57-59).

Входами первого элемента ИЛИ являются выходы 5-14 элементов И, входами второго элемента ИЛИ являются выходы 15-29 элементов И, входами третьего элемента ИЛИ являются выходы 30-45 элементов И. Первые прямые входы 7, 11, 18, 21, 24, 25, 26, 27, 42, 45, вторые прямые входы 30, 37 и первые инверсные входы 8, 14, 16, 33, 35, 38, 41 элементов И объединены и являются первым входом ячейки. Первые прямые входы 5, 8, 14, 15, 20, 28, 39, 43, вторые прямые входы 18, 26, 27, третьи прямые входы 25, 34, 37, первые инверсные входы 12, 22, 31 и вторые инверсные входы 33, 41 элементов И объединены и являются вторым входом ячейки. Первые прямые входы 2, 4, первые инверсные входы 1, 3 элементов И объединены и являются третьим входом ячейки. Первый прямой вход 3, второй прямой вход 4, первый инверсный вход 2, второй инверсный вход 1 элементов И объединены и являются четвертым входом ячейки. Первые прямые входы 6, 10, 19, 23, 29, 32, 33, 36, 37, 40, 41, вторые прямые входы 5, 7, 11, 12, 13, 25, третий прямой вход 27 элементов И объединены и являются пятым входом ячейки. Первые прямые входы 17, 22, вторые прямые входы 6, 9, 23, 28, 29, третьи прямые входы 8, 13, 14, 24 и четвертый вход 18 элементов И объединены и являются шестым входом ячейки. Первый прямой вход 44, вторые прямые входы 15, 16, 19, 21, 22, третьи прямые входы 17, 18, 20, 23, 45, и четвертый вход 26 элементов И объединены и являются седьмым входом ячейки. Первые прямые входы 30, 31, 34, 35, 38, вторые прямые входы 32, 36, 39, 40, 42, 43, 44 элементов И объединены и являются восьмым входом ячейки.

Структура предлагаемой ячейки описывается следующей системой формул:

Ячейка путем настройки реализует следующие системы формул:

Проиллюстрируем работу однородных сред, построенных из предлагаемых ячеек, на следующих примерах.

Пример 1. Реализация повторной упорядоченной формулы без пропусков аргументов, представленной в КНФ

ƒ₁=(х₁ ∨ x₂)(х₂ ∨ x₃)(x₃ ∨ х₄),

представлена на фиг.4.

Пример 2. Повторная упорядоченная формула без пропусков аргументов, представленная в ДНФ

ƒ₂=x₁x₂ ∨ x₂x₃ ∨ x₃x₄,

реализуется линейной однородной структурой представленной на фиг.5.

Пример 3. На фиг.6 показаны настроечные коды каждой ячейки однородной структуры, реализующей повторную упорядоченную формулу без пропусков аргументов, представленную в форме высших (4-го) порядков

ƒ₃=(x₁ ∨ x₂)x₃ ∨ x₃(x₄ ∨ x₅ ∨ x₆).

Пример 4. Реализация повторной упорядоченной функции с пропусками аргументов x₂ и x₆, представленной в ДНФ

ƒ₄=x₁x₃ ∨ x₁x₄ ∨ x₃x₄ ∨ x₅ ∨ x₇,

показано на фиг.7.

Пример 5. Неупорядоченная повторная функция, представленная в ДНФ

ƒ₅=x₁x₃x₆ ∨ x₂x₄x₆ ∨ x₅x₇.

Реализуется структурой, представленной на фиг.8.

Пример 6. На фиг.9 представлена реализация системы функций высокого порядка с пропусками аргументов вида

Пример 7. Для реализации бесповторной упорядоченной функции вида

ƒ₈=[(x₁ ∨ x₂)(x₃ ∨ x₄)∨(x₅ ∨ x₆)(x₇ ∨ x₈)][(x₉ ∨ x₁₀)(х₁₁ ∨ x₁₂)∨

∨(x₁₃ ∨ x₁₄)(x₁₅ ∨ x₁₆)],

можно построить древовидную с выделенными каскадами, фиг.10. Схема каскада и настроечные коды для его ячеек показаны на фиг.11.

Пример 8. Повторная неупорядоченная функция без пропусков аргументов, представленная в ДНФ

ƒ₉=x₁x₃ ∨ x₂x₃ ∨ x₂x₄,

реализуется однородной структурой представленной на фиг.12.

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

Ячейка может быть выполнена на микросхемах серии К555, элементы И реализуются на микросхемах ЛИ3, ЛИ5, ЛИ6, элементы ИЛИ реализуются на микросхемах ЛЛ1, инверторы на входах элементов реализуются микросхемами ЛН1. (Цифровые интегральные микросхемы: Справ./ М.И.Богданович, И.Н.Грель, В.А.Прохоренко, В.В.Шалимо. - Мн.: Беларусь, 1991. - 493 с.)

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