11.6. ПРОЕКТИРОВАНИЕ КОМБИНАЦИОННЫХ СХЕМ НА ПЛМ

Под ПЛМ понимается программируемая логическая матрица — кон» структивный элемент, изготавливаемый в виде большой интегральной схемы (рис. 11.45). Настройка (программирование) ПЛМ осуществляется пользователем с помощью специального оборудования и заклю чается в устранении некоторых связей (среди обозначенных крестиком на рис. 11.45) посредством фотошаблонов либо выжиганием. Описанная ПЛМ называется -ПЛМ, где — число входов — число выходов число конъюнкций, реализуемых ПЛМ. Входы и выходы ПЛМ называются столбцами, а конъюнкции — строками. Рассматриваемая ПЛМ содержит столбцов и строк.. Число называется площадью может быть представлена в виде двух подматриц (рис. 11.46). Подматрица реализует всевозможных конъюнкхухй, каждая из которых зависит не более чем от переменных; подматрица реализует всевозможных дизъюнкций, каждая из которых зависит не более чем от переменных. На рис. 11.47 показана реализация системы функций на (. Оставленные после программирования связи изображены на рис. 11.47 точками. Электрическая принципиальная схема ( представлена на рис. 11.48. После программирования ПЛМ, заключающегося в устранении (прожигании) ненужных диодных перемычек, для реализации рассматриваемой системы функций, получаем ПЛМ (рис. 11.49),

Рис. 11.45

Рис. 11.46

функционирование которой описывается уравнениями;

Различают две задачи синтеза комби наци иных схем на ПЛМ.

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

Вторая задача заключается в разработке комбинационной схемы, реализующей заданную систему булевых функций, на минимальном числе ПЛМ с известными параметрами (число входов, выходов и строк ПЛМ определено). Эта задача часто решается при разработке средств вычислительной техники на серийно выпускаемых ПЛМ

Рассмотрим некоторые методы решения первой задачи, ограничиваясь реализацией дизъюнктивных нормальных форм булевых функций. Для того чтобы реализовать систему ДНФ на ПЛМ с минимальной

Рис. 11.47

Рис. 11.48

Рис. 11.49

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

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

Таблица 11.5

Таблица 11.6

Таблица 11.7

Если вычеркнуть столбцы переменных в табл 11 12, то переменные перестают быть фиктивными, а таблица истинности сокращается до табл 11.6

Минимально возможное число входных переменных системы булевых функций можно найти следующим образом. По исходной табл. 11.5 образуем все пары входных наборов, на которых хотя бы одна из функций системы принимает противоположное значение. Такими парами наборов являются Для каждой полученной пары наборов укажем множество тех переменных, значениями которых различаются наборы рассматриваемой пары Так, наборы, входящие и пару (1,2). отличаются значениями переменных Сведем полученные результаты матрицу, столбцы которой отмечаются парами наборов вышеописанного вида, а строки — входными переменными, от которых зависит система булевых функций. На пересечении столбца и строки матрицы поставим единицу, если переменная, отмечающая строку, имеет различные значения в паре наборов, отмечающих столбец матрицы. Полученная матрица называется матрицей различий, а каждая ее строка — вектором различий. Для рассматриваемого примера матрица различий приведена в табл. 11.7.

Найдем минимальное покрытие столбцов матрицы строками. Для этой цели можно, например, использовать метод Петрика. Конъюнктивное представление таблицы имеет вид:

После проведения преобразований получим

Следовательно, минимальным по числу строк покрытием является множество Минимальное покрытие и представляет

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

Таким образом, рассматриваемая система булевых функций существенно зависит от переменных Таблица истинности функций с учетом сказанного представлена в табл. 11.6, Вторым параметром ПЛМ, влияющим на ее площадь, является число строк (число реализуемых элементов конъюнкции). При реализации системы ДНФ булевых функций число строк полученной ПЛМ равно числу различных конъюнкций системы функций. Естественно ставится задача нахождения минимального их числа. Последнее может быть сделано с использованием метода минимизации систем булевых функций (гл. 9). В результате применения метода получаем

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

Таким образом, общая процедура реализации системы булевых функций на ПЛМ с минимизацией площади ПЛМ может быть разбита на следующие этапы:

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

2. Находится минимальная ДНФ системы булевых функций.

3. Конъюнкции полученной ДНФ реализуются в первой подматрице ПЛМ, а сами функции — во второй подматрице — дизъюнкцией соответствующих конъюнкций.

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

Рис. 11.50

Таблица 11.8

Рис. 11.51

Рис. 11.52

, представлена на рис. 11.50 и содержит 5 столбцов и 6 строк (непрожженные диодные связи показаны на рис. 11.50 точками, а инверторы в каждой строке ПЛМ опущены). Суммарная площадь ПЛМ равна 30. Если в табл. 11.5 вычеркнуть столбцы получится система функций, представленная табл. 11.8

Число входных переменных в полученной системе булевых функций не минимально. Однако минимальная ДНФ системы имеет вид

т. е. содержит четыре различных простых импликанты. Реализация полученной системы на ПЛМ представлена на рис. 11.51. Суммарная площадь ПЛМ равна

Дополнительную возможность сокращения площади ПЛМ дает использование скобочных форм. Рассмотрим, например, функции, СДНФ которых имеет вид

Непосредственная реализация их на ПЛМ приводит к необходимости использования ПЛМ площадью Используя операцию вынесения за скобки, представим функцию в виде

где Тогда

Полученные ДНФ реализуются ПЛМ, представленной на рис. 11.52 с суммарной площадью

Рассмотрим некоторые подходы к решению второй задачи — задачи синтеза комбинационных схем на серийно выпускаемых ПЛМ.

Обозначим — число входов; число выходов; — число строк ПЛМ (рис. 11,53). Пусть заданная для реализации на

Рис. 11.53

-ПЛМ система булевых функций характеризуется следующими параметрами: где — число аргументов булевых функций; где — число булевых функций в системе; где — число различных простых импликант системы булевых функций. Проще взять для реализации на первой из них реализовать первые функций системы, на второй — следующие функций и т. д., до тех пор, пока не будут реализованы все булевые функции. Очевидно, если функции исходной системы попарно различны, то число ПЛМ будет минимально.

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

иа В нашем случае Реализация функций может быть осуществлена в соответствии с блок-схемой (рис. 11.54). Принципиальная электрическая схема показана на рис. 11.55.

Пусть заданная для реализации для - ПЛМ система булевых функций характеризуется следующими параметрами: Простейший способ построения комбинационной схемы заключается в следующем. Множество всех простых импликант системы ДНФ булевых функций разбивается на непересекающиеся подмножества по импликант в каждом. Число таких подмножеств может быть не более Импликанты, входящие в одно подмножество, реализуются на одной ПЛМ. Булевы функции образуются за счет дизъюнктивного объединения соответствующих выходов ПЛМ.

Рис. 11.54

Рис. 11.55

Рис. 11.56

Пример. Реализовать на -ПЛМ систему булевых функций:

Очевидно, Одна из возможных реализаций функций представлена на рис. 11.56, где

Рассмотрим случай, когда Реализация таких систем булевых функций схемами с минимальным числом ПЛМ основана на методах декомпозиции булевых функций. Минимальной по числу ПЛМ схеме соответствует декомпозиция исходной системы функций на минимальное число подсистем, каждая из которых содержит не более чем ррфункций и не более чем конъюнкций. Если не заботиться о минимизации числа ПЛМ, то можно строить схему из ПЛМ следующим образом. Выберем из исходной системы подсистему из функций. Если число различных импликант, входящих в выбранные функции то подсистема реализуется на одной ПЛМ Если то подсистема реализуется схемой из -ПЛМ. Из оставшихся функций выберем следующие функций и поступим аналогичным образом. Общее число ПЛМ в полученной схеме по описанному способу может достигать величины

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