3. Покрытие функциональной схемы эс набором фту и разбиение схемы эс

Лабораторная работа № 1

3.1. Описание проектной задачи покрытия электрической функциональной схемы эс (СхЭф) набором функционально-типизированных узлов (фту)

Покрытие СхЭФ набором ФТУ рассмотрим для цифровой аппаратуры [1]. В этом случае функциональной схемой является логическая схема ЭС, ФТУ- это набор ИМС (например серия ИМС).

Логическая схема состоит из функциональных (логических) элементов. В простейшем случае это логические вентили и триггеры.

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

Фактически покрытие схемы – это разбиение логической схемы на подсхемы, которые заранее заданы.

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

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

Входные данные

1. Схема электрическая функциональная ЭС (логическая схема).

2. Набор ФТУ (ИМС обычно).

Выходные данные

Схема электрическая принципиальная ЭС (СхЭПр).

Обратите внимание, что в этой задаче ИМС играют роль конструктивных узлов, а не элементов.

На рис. 2 представлена СхЭПр, полученная в результате покрытия логической схемы интегральными микросхемами малой степени интеграции серии 137.

Критерии качества

1. Минимальная стоимость покрытия. Если все ИМС стоят одинаково, то тогда минимизируется число израсходованных ИМС.

2. Минимальное число типов узлов покрытия.

3. Минимальное число межузловых соединений. Этот критерий используется совместно с первым критерием, так как первый критерий дает не одно, а несколько одинаковых оптимальных решений.

Математические модели объектов проектирования

Математическая модель логической схемы - взвешенный по вершинам гиперграф. "Веса" вершин означают различные типы логических элементов схемы.

Математические модели ИМС – аналогичные гиперграфы меньшей размерности.

Формализованная формулировка

Покрытие схем – это задача идентификации графов (распознавание структур). Действительно, при решении ее необходимо отыскать в гиперграфе схемы подграфы, соответствующие гиперграфам ИМС. Таким образом, покрытие схем сводится к задаче покрытия взвешенного по вершинам гиперграфа гиперграфами из заданного набора.

Сведения к задаче математического программирования

В общем случае покрытие логическая схема – комбинаторная задача экстремального типа: нелинейная дискретная задача математического программирования.

В частном случае, когда ИМС содержит несвязанные между собой логические элементы, то задача становится линейной и упрощается: это задача ЦЛП – целочисленного линейного программирования [7].

Алгоритмы покрытия

Ввиду трудности формализации и сложности решения задача покрытия схем ЭС решается обычно вручную. Известные алгоритмы являются эвристическими [1]. Для частного случая, когда удается свести задачу к ЦЛП, можно применить метод отсечений [7] или эвристические алгоритмы.