С уровнем абстракции представления алгоритмов

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

Эффективность использования САПР во многом определяется заложенными в них алгоритмами синтеза цифровых логических схем, от качества этих алгоритмов в дальнейшем зависят фактически все основные технико-эксплуатационные параметры создаваемых цифровых устройств: быстродействие, надежность, компактность, помехоустойчивость, тестопригодность, стоимость, простота технических решений и другие. В то же время актуальной является разработка таких методов синтеза и минимизации, которые бы, с одной стороны, обладали достаточной эффективностью, а с другой – были пригодны для проектирования цифровых устройств реальной степени сложности, с практически существующей размерностью и сложностью реализуемых алгоритмов функционирования.

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

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

Одним из основных классических методов формализации описания функционирования автоматов является алгебра логики. Предложенная Джорджем Булем в XIX веке для изучения законов человеческого мышления, она стала в настоящее время математическим аппаратом, адекватным цифровым логическим системам и является основным средством их анализа и синтеза.

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

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

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

Рис.6.3.Взаимосвязь степеней детализации проектов

с уровнем абстракции представления алгоритмов

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

Формализация алгоритма функционирования цифрового устройства при анализе и синтезе – наиболее трудоемкая и ответственная операция. От того, насколько правильно она осуществлена, зависит эффективность работы синтезированной системы управления и успех распознавания алгоритма при ее анализе.

Различают два этапа синтеза: абстрактный и структурный. При абстрактном синтезе составляют алгоритм функционирования, проверяют его правильность и корректность формализации. Затем строят оптимальную, в списке принятых критериев, схему устройства, реализующего требуемый алгоритм. Структурный синтез – второй этап построения автоматов. Основные его задачи – выбор элементной базы и преобразование математической модели, полученной на этапе абстрактного синтеза, к виду, удобному для реализации цифрового устройства в выбранном базисе.

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

В процессе синтеза переключательных схем можно выделить следующие основные операции: составление словесного алгоритма функционирования устройства, заполнение таблицы состояний, запись логической функции, ее минимизация и преобразование к необходимому элементному базису. В настоящее время широко известны инженерные методы построения логических схем, базирующиеся, в основном, на классической теории релейно-контактных (переключательных) схем и сводящиеся, как правило, к минимизации переключательных функций. Использование этих методов для высокоинтегральных логических схем не позволяет учесть ряд их специфических особенностей, таких как многофункциональность некоторых элементов, ограниченная нагрузочная способность и другие. Зачастую минимальная длина переключательной функции уже не гарантирует минимальную сложность устройства. В особой мере это относится к построению цифровых логических устройств на больших и сверхбольших интегральных схемах, у которых плотность размещения достигает сотен тысяч элементов на кристалл. Поэтому проблемы минимизации числа вентилей для них не существует, главная задача здесь - минимизация числа выводов из корпуса микросхемы.

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

Анализ цифровых устройств

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

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

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

- на втором этапе анализа формально описывают работу схемы. Это целесообразно выполнять в следующем порядке: вводятся обозначения переменных, соответствующих входным и выходным сигналам, а также внутренним узлам анализируемой схемы. При этом все переменные, соответствующие соединенным между собой узлам, приравнивают друг другу; для каждого логического элемента, входящего в схему, записывают реализуемую им логическую функцию, зависящую от соседних переменных, т.е. от тех узлов, с которыми отождествлены его входы. Выписывают систему переключательных функций анализируемой схемы, представляющую собой суперпозицию операторов элементов, на базе которых реализован автомат. Для однотактных логических схем (комбинационных) выходные функции выражают как функции только входных переменных. Для многотактных последовательностных схем (конечных автоматов) – как функции входных и внутренних переменных. Производят преобразование системы переключательных функций к их нормальным формам или (если необходимо) – к одной из скобочных форм, пользуясь законами алгебры логики.

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