Патент на изобретение №2236698

(54) СПОСОБ ВОСПРОИЗВЕДЕНИЯ СИММЕТРИЧНЫХ БУЛЕВЫХ ФУНКЦИЙ

(57) Реферат:

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении соответствующих конечных автоматов. Техническим результатом изобретения является упрощение воспроизведения фундаментальных симметричных булевых функций за счет исключения инвертора. Указанный технический результат достигается за счет того, что для воспроизведения фундаментальной симметричной булевой функции индекса m (m{0,…,n}), зависящей от n аргументов – двоичных сигналов, подают указанные сигналы на блок вычисления простых симметричных булевых функций, а значения m-й и (m+1)-й простых симметричных булевых функций суммируют сумматором по модулю 2.

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении соответствующих конечных автоматов.

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

n аргументов – двоичных сигналов указанные сигналы предварительно подают на блок вычисления простых симметричных булевых функций ₀,… , _n+1. Здесь m {0,… ,n} есть заданное – число (индекс) функции . Как известно, только тогда, когда точно m ее аргументов равны 1, а остальные ее аргументы равны 0.

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

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

Указанный технический результат при осуществлении изобретения достигается тем, что в способе воспроизведения симметричных булевых функций, в котором для воспроизведения фундаментальной симметричной булевой функции индекса m (m {0,… ,n}), зависящей от n аргументов – двоичных сигналов, предварительно подают указанные сигналы на блок вычисления нулевой (n+1)-й простых симметричных булевых функций, особенность заключается в том, что значения m-й и (m+1)-й простых симметричных булевых функций суммируют сумматором по модулю 2.

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

В предлагаемом способе для воспроизведения фундаментальной симметричной булевой функции индекса m (m {0,… ,n}), зависящей от n аргументов – двоичных сигналов ₁,… ,x_n, указанные сигналы предварительно подают на блок вычисления простых симметричных булевых функций ₀,… _n+1, где

а значения функций _m и _m+1 суммируют сумматором по модулю 2, т.е.

В выражении (1) x_il … x_ik {x₁,… ,x_n}; k,… ,n есть -числа (индексы) угарной функции ;, есть количество неповторяющихся минтермов x_i1 … x_ik, определяемое как число сочетаний из n по k. Функция равна 1 только тогда, когда k или больше переменных из х₁,… ,х_n равны 1, а остальные переменные равны 0.

Сначала докажем справедливость (2) при 0&; m&; n, воспользовавшись известными соотношениями (см. стр. 143, 144 в книге Миллер Р. Теория переключательных схем. М.: Наука, 1970. T.1.)

где

где

где . С учетом (1) и (3.1)-(3.3) можно записать

Теперь покажем справедливость (2) при m=0 (m=n). Если m=0 либо m=n, то согласно (1) и (3.3) получим соответственно либо . Справедливость (2) доказана.

Пример. Пусть n=4, m=2, тогда согласно (1) получим

₂=(x₁ x₂) (x₁ x₃) (x₁ x₄) (x₂ x₃) (x₂ x₄) (x₃ x₄);

₃=(x₁ x₂ x₃) (x₁ x₂ x₄) (x₁ x₃ x₄) (x₂ x₃ x₄).

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

Таким образом,

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

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

Способ воспроизведения симметричных булевых функций, в котором для воспроизведения фундаментальной симметричной булевой функции индекса m (m{0,…,n}), зависящей от n аргументов – двоичных сигналов, предварительно подают указанные сигналы на блок вычисления простых симметричных булевых функций ₀–_n+1, отличающийся тем, что значения m-й и (m+1)-й простых симметричных булевых функций суммируют сумматором по модулю 2.

MM4A Досрочное прекращение действия патента Российской Федерации на изобретение из-за неуплаты в установленный срок пошлины за поддержание патента в силе

Дата прекращения действия патента: 07.12.2004

Извещение опубликовано: 20.05.2006 БИ: 14/2006