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

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

 

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

Известна ячейка однородной среды, содержащая элементы И, ИЛИ, ЗАПРЕТ (Авторское свидетельство СССР №798804, кл. G06F 7/00, 1978).

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

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

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

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

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

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

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

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

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

На фиг.1 показана общая схема ячейки, содержащей входы 1, 2, 3, 4, 5, 6, элементы ИЛИ 7, 8, 9, 10, 11, 12, 13, 14, 15, элементы И 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, выходы 27, 28: на фиг.2 представлена детализированная схема этой же ячейки с указанием номеров входов на каждый элемент ячейки, показаны номера информационных и настроечных входов, а также номера выходов ячейки, элементам ИЛИ присвоены номера от 1 до 9, элемента И - от 1 до 11 для более удобного описания и синтеза ячейки; на фиг.3 - коммутационные и функциональные схемы, реализуемые ячейкой путем настройки; на фиг.4 - то же, что и на фиг.3, но только в координатной системе для построения плоскостных однородных структур.

Входами первого элемента ИЛИ (фиг.2) являются выходы девятого и одиннадцатого элементов И, входами второго элемента ИЛИ являются выходы первого, четвертого, восьмого элементов И. Выходы первого и второго элементов ИЛИ являются первым и вторым выходами ячейки соответственно. Инверсный вход четвертого, вторые прямые пятого, шестого, седьмого элементов И, второй инверсный вход пятого элемента ИЛИ объединены и являются первым входом ячейки (третьим настроечным). Первые прямые входа третьего, шестого, седьмого, третий вход второго элементов И, первый вход третьего, первый инверсный пятого, прямой четвертого элементов ИЛИ объединены и являются вторым входом ячейки (второй настроечный). Инверсные входа третьего, шестого, седьмого, второй прямой второго элементов И, третий вход третьего, прямой пятого, инверсный четвертого элементов ИЛИ объединены и являются третьим входом ячейки (первый настроечный). Первый вход четвертого и третий вход шестого элементов И объединены и являются четвертым входом ячейки (второй информационный). Первые входа второго, пятого, второй прямой третьего элементов И, первый вход восьмого, второй вход третьего элементов ИЛИ объединены и являются пятым входом ячейки (третий информационный). Второй вход первого элемента И, первый вход девятого элемента ИЛИ объединены и являются шестым входом ячейки (первый информационный).

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

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

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

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

f₁=x₁x₂∨x₃x₄∨x₅x₆

строится однородная структура с настроечными кодами, представленная на фиг.5.

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

f₂=x₁x₂x₃∨x₅∨x₆.

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

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

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

Пример 4. Для реализации системы булевых формул вида

строится плоскостная однородная структура с настроечными кодами, представленная на фиг.9.

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

f₆=(x₁∨x₂)x₅∨x₃

строится однородная структура с настроечными кодами, представленная на фиг.10.

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

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

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