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

Иванов Александр Леонидович

канд. техн. наук, доцент, РГСУ, г. Москва

e-mail: Alex_Ivanov1949@mail.ru

Широко известно, что моделью поведения (МЛП) одновыходной комбинационной схемы (КС) является булева функция (БФ) вида:

y=f (x₁, x₂,…, x_L), x_i ∈ X,                                                  (1)

где y — выходной сигнал, соответствующий в каждый момент автоматного времени комбинации входных переменных x_i. При дизъюнктивной нормальной форме (ДНФ) представления БФ X — это конъюнкция БФ. Канонические методы оптимизации БФ подразумевают её минимизацию, в том числе и факторизацию — вынесение за скобки переменных x_i, входящих в разные конъюнкции.

Как было показано в [1] каноническая минимизация теряет смысл в случае микроэлектронной реализации цифрового устройства с жесткой логикой (ЦУ), когда уровень структурной избыточности ЦУ не имеет решающего значения.

Если считать, что структуру ЦУ образует совокупность конструктивных модулей (КМ) и, если решается задача унификации КМ при микроэлектронной реализации ЦУ, а при этом каждый КМ отображает базовую структуру ЦУ [3], то качество КМ при достигнутом уровне унификации целиком зависит прежде всего от интенсивности отказов их коммутационных узлов λ_Q [1].

Условимся, что конструктивный модуль реализует некоторую подфункцию φ_i (X") | X". При этом y=φ₁₊φ₂+…+φ_t. Следовательно, всегда можно положить, что для КМ i-го типа интенсивность его отказов λ_i=λ_Qi. В то же время

λ_Qi=λ_Qi1+λ_Qi2 * q,

где λ_Qi1 и λ_Qi2  — интенсивность отказов внешнего и внутреннего коммутационных узлов (КУ), соответственно.

Хорошо известно, что заведомо q=Q₂/Q₁ ≥ 1 и всегда λ_Qi2>λ_Qi1, а λ_Qi2* q » λ_Qi1.

Непосредственно отсюда следует вывод, что для минимизации критерия качества К [1]:

K=+)/ ,                                         (2)

необходимо, чтобы КМ i-го типа реализовывал бы подфункцию φ_i БФ (1), содержащую минимальное число букв — переменных x_i и их отрицаний. Совершенно очевидно, что подфункция φ_i должна быть скобочным булевым выражением (СБВ).

В формуле (2) t — число типов КМ; a=2—3 — доля затрат на амортизационные отчисления и текущий ремонт ЦУ; q_i — число морфологически однородных подфункций i-го типа в БФ (1) [2]; h_i — число морфологически однородных подфункций i-го типа, реализуемых в КМ дополнительно к основным и коммутируемых либо в процессе изготовления ЦУ металлизацией, если часть подфункций при тестировании ЦУ не воспроизводится, либо в процессе настройки или эксплуатации электрической коммутацией; N_i — число морфологически однородных подфункций i-го типа, реализуемых в КМ.

Если выполняется факторизация Λ_k букв из p_k конъюнкций БФ (1), то эффект факторизации определяется как:

∆q= Λ_k(p_k – 1) – 2],                                                 (3)

где   G — число групп конъюнкций p_k .

Поскольку число КМ i-го типа, помещаемых в ЗИП, определяется по следующей формуле [1]:

h_i=,                                                               (4)

где   — знак округления до ближайшего меньшего целого числа;

t_n   — время пополнения ЗИП;

Ti — среднее время безотказной работы КМ i-го типа;

=1/T_i — интенсивность отказов КМ i-типа, то с учетом вышесказанного, выражение (4) приобретает вид:

h_i=λ_Q1i+λ_Q2i(L_i – Λ _ip_i+2]                               (5)

где L_i=r_ij p_i, а r_ij — ранг j-той конъюнкции в i-той группе конъюнкций ДНФ БФ (1).

Исходя из выражений (2) и (5), можно сделать вывод о том, что оптимизацию качества МЛП КС можно проводить по пути увеличения надежности КМ, т. е. уменьшения числа букв в БФ (1), при ограничении на общее число КМ, по пути уменьшения числа типов морфологически однородных подфункций [1] φ_i при ограничении на величину Λ_i , либо одновременно по двум названным параметрам при указанных ограничениях, а также ограничении на число букв в подфункции (υ).

Определение 1. Морфологической оптимизацией МЛП КС называется её представление в виде декомпозиции таких подфункций φ_i , которые обеспечивают их реализацию КМ минимального числа типов, имеющих заданные конструктивные характеристики.

Поэтому, согласно определению 1, задачей морфологической оптимизации МЛП КС является получение такого скобочного булева выражения, которое представляется декомпозицией морфологически однородных подфункций (базовых структур МЛП КС), являющихся простыми (с одним вложением скобок) скобочными булевыми выражениями (СБВ) при ограничениях:

υ≤υ_крит. ; R≤R_доп.; Λ _i >0,                                                    (6)

где υ_крит. — максимально допустимое число букв (переменных или их отрицаний) в подфункции;

R — общее число подфункций, реализованных в КМ.

Это обеспечивает максимальный уровень унификации КМ при минимальных значениях КУ и числа КМ в ЗИП при прочих равных условиях.

Правила формирования СБВ связаны с вопросом связности БФ. Пусть X={x₁, x₂,…, x_L} — множество булевых переменных, тогда булево пространство М над множеством X определяется как множество комбинаций значений переменных x_i. Комбинация значений некоторого подмножества X’ определяет интервал  на пространстве М. В алгебраической форме интервал — это конъюнкция переменных ;

:  , =x_i.

Понятие связности БФ определено, когда существует такая последовательность интервалов . Это понятие характеризует связность БФ с точки зрения наличия пересечения её интервалов, на которых она принимает единичное значение.

Две конъюнкции υ_i и υ_j считаются связными на множестве X, если пересечение множеств букв, их определяющих, не пусто. Степень связности υ_i и υ_j :

μ_ij=card (υ_i  υ_j)/(r_i+r_j),                                        (7)

где r_i, r_j — ранги конъюнкций υ_i и υ_j, соответственно.

Степень связности ДНФ БФ (1) — это:

μ_f = _ij),

где   Т — число конъюнкций ДНФ.

В связи с конкретным значением μ_f различают БФ сильносвязные и слабосвязные. В дальнейшем под слабосвязной БФ будем понимать такое булево выражение, что:

Очевидно, что факторизация сильносвязной ДНФ БФ дает возможность получения сложного СБВ (имеющего несколько уровней вложения скобок), а факторизация слабосвязной ДНФ — как правило лишь простые СБВ.

При оптимизации БФ с использованием автоматизированных методов факторизации (не канонических) необходимо определить метод поиска морфологически однородных подфункций в формуле СБВ. Для этого следует получить аналитическое выражение порядка следования (_k) [2] бинарных операторов в формуле СБВ.

БФ в классе ДНФ имеет морфологическую структуру, которая характеризуется порядком _д [2]

_д=< n⁰НЕ, d[(n-)И, ИЛИ], (n-)И>, (i=)             (8)

при (n — )≤υ_крит. (j),

где   n⁰— максимальное число инвертированных переменных в БФ;

 d — число периодов следования операторов И-И-…-ИЛИ;

 n — число переменных БФ;

 — число переменных, отсутствующих в i-той конъюнкции;

υ_крит. — допустимое число букв в подфункциях.

Пусть, например, задана БФ F вида:

F=x₁x₂₄+ x₁x₂x₄+ x₁x₃₄+ x₂x₃x₄,

Тогда n=4 и _д (F)=<2 НЕ, 3[3И, ИЛИ], 3И> при υ_крит.=4.

Пусть задано начальное покрытие БФ (1) комплексом кубов С₀. Хорошо известно, что при получении СБВ каноническими методами факторизации, выделяющий куб С_mj содержит λ — часть и μ-часть. Считаем, что λ — часть куба С_mj (j=) содержит Λ_j координат. Пусть _j — множество кубов, у которых из С_mj удалены λ — части и пусть C_j=C_j–1\_j, |_j|=C, тогда порядок следования бинарных операторов в пределах простого СБВ задается формулой [4]:

_сп=<n⁰НЕ, M{dj[(n––1)И, ИЛИ], (n –  – |M_j|–1)И,

 И, ИЛИ}, (C-1)[( n-)И, ИЛИ], (n-)И>                             (9)

при (n - — 1) ≤ υ_крит., ( n-) ≤ υ_крит., ,  ≤ υ_крит.,i=; j=; k=,

где M=|_j|; dj — число периодов следования бинарных операторов И-И-…-ИЛИ в кубах из множества ;

из множества ;

 —  из множества _j.

В формуле (9) выражение

φ_i=<НЕ, d_φ[(n-Λ_φ–1)И, ИЛИ], (n –  – _φ-1)И,Λ_φ И>      (10)

задает порядок следования бинарных операторов в подфункциях φ_i, являющихся простыми СБВ. Здесь  — число инвертированных переменных в выражении φ_i.

Очевидно, что в случае определения , где f — это БФ (1), в формулах (9) и (10) значения

Например, для СБВ F=x₁x₃(x₅+x₇x₈+x₄)

<2 НЕ, 2 [И, ИЛИ], 3И>. Отметим, что литерал можно представить как =*1, поэтому в формуле _к литерал отмечается оператором «И».

Пусть задана ДНФ БФ F=_t множества переменных X={x₁, x₂,…, x_L}, X_t=, t=;

Возможным факторизационным методом получения сложного СБВ может быть алгоритм, на каждом шаге которого всевозможными попарными пересечениями во множестве С₀={₁, ₂,…, _T} (здесь Xt — интервал булева пространства) находят общие части интервалов _t={} и выносят за скобки ту конъюнкцию Z из элементов множества ; J; Z={z₁, …, z_s}, z_i , которая обеспечивает наибольший выигрыш согласно выражениям [4]:

 max,                     (11)

где   m — максимальное число общих переменных в первых n кубах из множества С₀;

n — число исходных конъюнкций, в которых после вынесения за скобки остается по одной букве.

Тогда БФ F на первом шаге факторизации приобретает вид:

F= ,

на втором шаге:

F= 

на S-ом шаге факторизации

F=…(  ( …)

…,                                               (12)

где интервал =\,

а  — число кубов начального покрытия, из которых извлекаются конъюнкции .  ; .

Конъюнкция  в БВ (12) определяется как конъюнкция, вынесенная за скобки, уровень вложения которых равен S (скобка снизу для наглядности отмечена символом S), на S-ом шаге факторизации из первых (f₁) L — кубов БФ F. Тот факт, что вынесение за скобки производится из первых L — кубов, отмечен единицей, заключенной в скобки, вверху символа .

В БВ (12) конъюнкция  может иметь нижний индекс 1. Но это не противоречит сказанному выше, т.к. после всех возможных вынесений за скобки из первых (f₁) L — кубов покрытия подобная процедура повторяется для второй группы (f₂) L — кубов, т.е. алгоритм начинает «работать» снова, и на первом шаге (S=1) извлекается конъюнкция  . Таким образом может быть сформирована МЛП КС, отображаемая конструктивными модулями с минимальным числом внешних коммутационных узлов.

Выводы и основные результаты:

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

2.Решающим фактором оптимизации ЦУ становится получение модели поведения (МЛП) КС в виде декомпозиции морфологически однородных подфункций (базовых структур КС), каждая из которых представляет собой простое скобочное булево выражение (СБВ).

3.Определено понятие морфологической оптимизации МЛП КС и сформулирована её задача.

4.Сформулированы признаки слабосвязных и сильносвязных МЛП КС.

5.Сформулировано правило получения аналитического выражения порядка следования бинарных операторов в формуле СБВ.

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

Список литературы:

1.Иванов А.Л., Угрюмов Е.П. Принципы морфологической оптимизации моделей поведения комбинационных схем стационарных восстанавливаемых цифровых устройств. — Электронное моделирование, 1985, т. 7, № 6, с. 31—34.

2.Иванов А.Л., Угрюмов Е.П. Особенности оптимизации структур комбинационных схем. — Известия ВУЗов. Приборостроение, 1980, т. 23, № 8, с. 34—37.

3.Иванов А.Л. Оценка качества операционных автоматов цифровых устройств с жесткой логикой. — Отраслевые аспекты технических наук, 2012, № 6, с. 16—18.

4.Иванов А.Л. Проектирование структурно-избыточных микроэлектронных цифровых устройств. — В кн.: Методы построения алгоритмических моделей сложных систем, Таганрог: ТРТИ. 1979, вып. 4, с. 150—153.