Алгоритмы покрытий.

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

Исходная схема представляет множество М={m₁, m₂… m_k} связанных между собой функциональных элементов, таких как логические элементы И, ИЛИ, НЕ, триггер, усилитель, видеоусилитель, генератор, формирователь, умножитель и т.д. каждый из которых m_i ϵ M реализует некоторую функцию ψ _i, а их множество определяет совокупность всех функций ψ =U ψ _i ={ ψ ₁, ψ ₂, … ψ _k }, выполняемых в схеме. Имеется ограниченный набор типов модулей N = {n₁, n₂… n_l}, на базе которого необходимо выполнить заданную схему. Каждый модуль n_j ϵ N реализует одну или несколько логических операций φ _j={ ψ ₁^(j), ψ ₂^(j), … ψ _s^(j)}, а полный набор модулей N определяет совокупность тех логических операций Ф=Uφ _j={ ψ ₁^*, ψ ₂^*, … ψ _k^*}, которые могут быть получены с их помощью. При этом могут иметь место два случая:

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

2) аааа, т.е. компоненты набора модулей реализуют не все функции схемы.

В первом случае функциональную схему устройства можно полностью покрыть модулями заданного набора, во втором – требуется «ручная доработка» покрытие, связанная с подбором дополнительных модулей, позволяющих покрыть элементы из подмножества M_r ϵ M, выполняющие операции ψ \Ф. При этом процесс покрытия схемы разбивается на два этапа: предварительный и окончательный.

Алгоритм предварительного покрытия работает следующим образом:

1). Из списка элементов схемы, подлежащих покрытию, выбираем очередной элемент m_iϵ M. Если список пуст переходим к 8).

2) Определяем все логические элементы m_q ϵ M из числа непокрытых, связанных с m_i. Формирует множество M_i=m_iUm_q.

3) Производим сравнение функций φ _n реализуемых каждым из конструктивных модулей n_h ϵ N и логических функций ψ _i ={ ψ ₁⁽ⁱ⁾, ψ ₂⁽ⁱ⁾, … ψ _t⁽ⁱ⁾}, t=|M_i|. Выбираем модуль nqϵ N, для которого ψ _i∩ φ _q=max[ψ _i∩ φ _n]. Если таких модулей несколько, то выбираем модуль наименьшей стойкости. При ψ _i∩ φ _q=0 переходим к 7)

4) Если ψ _i=φ _q, то переходим к 6)

5) Из M_i удаляем элементы m_i ϵ M_i, наименее связанные с оставшимися и выполняющие операции ψ _i\φ _q. Получаем множество элементов M_q ϵ M_i, которые целесообразно скомпоновать в едином корпусе п_q.

6) Закрепляем все выбранные логические элементы за модулем п_q. Переходим к 1).

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

8) Конец работы алгоритма.

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

Данный алгоритм обладает приемлемой для практически эффективного решения задачи и просто реализуется на ЭВМ.

Е₁ U Е₂ - или то или другое;

Е₁ ∩ Е₂ - и то и другое;

Е₁ \ Е₂ - исключение всех возможных событий.