Синтез цифровых устройств циклического действия

Москва
Горячая линия – Телеком
2014

УДК 621.38 
ББК 32.85 
      Г93 

Гудко Н. И.

Г93    
 Синтез цифровых устройств циклического действия. – 
М.: Горячая линия – Телеком, 2014. – 96 с., ил. 

ISBN 978-5-9912-0427-9. 

Рассмотрены вопросы синтеза цифровых устройств циклического действия, являющихся одними из самых распространенных функциональных 
узлов цифровой техники, к которым относятся счетчики, распределители 
импульсов, кодирующие устройства, устройства управления процессоров и 
др., на основе широко известного инженерного метода, использующего процедуры канонического синтеза и таблицы переходов Хаффмена, базой которых является теория конечных автоматов. Предложена для использования 
специалистами в инженерной практике оригинальная методика синтеза этого частного класса устройств, позволяющая значительно улучшить их характеристики в части повышения быстродействия, экономии количества 
оборудования, обеспечения регулярности структуры, основанная на моделях 
этих устройств, разработанных автором.  
Краткое описание указанных классических методик с инженерным 
уклоном, предваряющее описание оригинального материала с целью сокращения затрат времени на ознакомление с ним, может быть использовано для первоначального знакомства с формализованными методами разработки функциональных устройств цифровой техники. Все рассмотренные схемы проверены путем моделирования на ПЭВМ с использованием 
программ Multisim 6.0 и Multisim 12.0.     

Для широкого круга специалистов в области радиоэлектроники, будет полезна студентам, изучающим цифровую схемотехнику и  микросхемотехнику. 

ББК 32.85 
Адрес издательства в Интернет WWW.TECHBOOK.RU 

Научное издание 

Гудко Николай Иванович 

Синтез цифровых устройств циклического действия 
Монография 

Редактор  Ю. Н. Чернышов 
Компьютерная верстка  Ю. Н. Чернышова 
Обложка художника  О. В. Карповой 

Подписано  в  печать  21.05.14. Формат 60×90/16. Усл. печ. л. 6.  Тираж 500 экз. (1 завод – 100 экз.) 
ISBN 978-5-9912-0427-9     
       ©  Г. И. Гудко, 2014 
©  Научно-техническое издательство 
«Горячая линия – Телеком», 2014 

Введение

Широкое внедрение в практику цифровых методов обработки
информации предъявляет высокие требования к методам схемотехнического проектирования этих устройств и профессиональной подготовке специалистов в этой области.
Настоящая монография посвящена рассмотрению вопросов синтеза цифровых устройств циклического действия, к которым отнесены такие наиболее распространённые функциональные узлы цифровой техники, как счётчики импульсов, распределители импульсов,
кодирующие устройства, устройства управления процессоров и др.
Термин «устройства циклического действия» вводится потому,
что он отображает основное свойство, объединяющее устройства этого класса, заключающееся в том, что эти устройства под действием
входных сигналов принимают одну и ту же последовательность состояний (состояний элементов памяти), которая может циклически
повторяться.
Известно, что учёт свойств цифровых устройств частных классов, особенностей их алгоритмов функционирования приводит к повышению эффективности методов формализованного синтеза и увеличивает размерность решаемых задач [4, 9, 24, 25].
В монографии предлагается методика синтеза именно этих устройств частного вида (цифровых устройств циклического действия),
позволяющая значительно улучшить такие их характеристики, как
быстродействие, количество используемого оборудования, регулярность структуры. Она основывается на структурных схемах (моделях) этих устройств, защищённых патентами на изобретения [28–30].
Эти модели являются, в отличие от обобщённой структурной схемы цифрового автомата (модели Хаффмена), отображающей цифровое устройство без учёта свойств его алгоритма функционирования, отображением цифровых устройств частного класса и потому
более эффективными, так как учитывают их особенности.
В монографии показано, в том числе на многих примерах, что
в рамках этих моделей могут реализовываться различные многочисленные варианты конкретных устройств, обладающие различными
свойствами, но при этом имеющие в большинстве случаев указанные преимущества.

Модели являются многоблочными структурами. Блоки имеют
оригинальные структуру, алгоритм функционирования и связи между их входами и выходами.
Синтез блоков может выполняться с использованием широко известного инженерного метода с применением процедуры канонического синтеза, модели и таблиц переходов Хаффмена, основанных на
теории автоматов.
Описанный подход к синтезу устройств данного класса предлагается к применению специалистами в инженерной практике как
при «ручном» проектировании (при этом размерность решаемых задач практически не ограничена), так и при автоматизированном (например, в части использования уже полученных схем, приведенных
в работе, и тех многочисленных схем, которые могут быть синтезированы «вручную» применительно к конкретным потребностям с
учётом разнообразных критериев в качестве функциональных узлов
библиотек).
Предложенные модели могут реализовываться при разработке
практически всех широко известных цифровых устройств этого класса. Более тщательная проработка целесообразности и эффективности такой реализации, рассмотрение различных алгоритмов и методик могут быть осуществлены в процессе последующих исследований и практического применения их результатов. Дальнейшие исследования в этой области представляются весьма перспективными. Те
решения, которые уже наработаны, целесообразно внедрять в инженерную практику разработки цифровых устройств и микросхем как
обеспечивающие существенный эффект (повышение быстродействие
примерно в 1,5 раза, уменьшение количества вентилей примерно на
30 %, обеспечение регулярности структуры).
Из истории развития цифровой техники известно, что большинство её оригинальных и эффективных функциональных узлов создавались эвристическими методами усилиями многочисленных изобретателей и разработчиков на основе их опыта и интуиции [6]. В данном случае речь идёт о получении рациональных решений с существенным эффектом при использовании совокупности формализованных и эвристических методов.
То есть указанные модели были получены при сочетании подхода, основанного на опыте и интуиции автора, и использования
основных понятий и представлений теории конечных автоматов, в
частности зависимости сложности устройства от количества его состояний и количества элементов памяти, а также взаимоотношения
сложности памяти и комбинационной схемы. Важным явилось так

же использование методов разбиения устройств на блоки (декомпозиции), рассматриваемых в теории автоматов, и др.
Монография может использоваться широким кругом специалистов по радиоэлектронике и студентами для первоначального ознакомления с практическими методами формализованного синтеза
цифровых устройств, так как в ней дано краткое описание классических процедур синтеза, предваряющее изложение оригинального
материала с целью сокращения затрат времени на ознакомление с
ним.
При изложении вопросов, достаточно подробно рассмотренных
в широко известной и особенно учебной литературе, даётся ссылка
на соответствующие источники. В то же время базовым понятиям,
тем более недостаточно освещенным в учебниках, уделяется больше
внимания. В принципе для освоения материалов работы при отсутствии первоначальной подготовки в данной области достаточно пользоваться литературой из основного списка, которая вполне доступна
широкому кругу специалистов различных областей радиоэлектроники и студентам [1–7]. Дополнительная литература предназначена
для более глубокого и всестороннего изучения этой тематики [8–37].
В разделе 1 рассматривается структурная схема цифрового устройства, которую часто называют канонической, обобщённой моделью Хаффмена.
Первоочередное рассмотрение этой модели, по
мнению автора, является важным, так как при этом поясняются основные понятия теории автоматов, используемые в процедуре канонического синтеза и объекты (параметры), формально определяющие цифровое устройство. В результате, ввиду появившейся мотивации, более осознанно и просто должны усваиваться в процессе
дальнейшего изложения суть и назначение аппарата алгебры логики
и процедуры, предназначенные для определения этих параметров.
Раздел 2 посвящен изложению методики инженерного синтеза
цифровых устройств на основе таблиц переходов Хаффмена с кратким описанием аппарата алгебры логики, понятий комбинационного, последовательностного, синхронного и асинхронного автоматов,
процедур этапов абстрактного и структурного синтеза, методов борьбы с явлениями состязаний при синтезе и др. При этом рассматриваются примеры синтеза устройств, наглядно иллюстрирующие
изложенный материал, учитывающие специфику тематики работы.
В разделе 3 кратко анализируются традиционные принципы построения цифровых устройств циклического действия. На качественном уровне оцениваются возможности улучшения их основных параметров путём изменения их структуры. Проводится синтез циклических цифровых устройств (распределителя импульсов в коде Грея

и распределителя импульсов в коде Джонсона) с использованием RSтриггеров в качестве элементов памяти вместо широко используемых в практике в таких случаях сложных триггеров типа JK, T, D
и других с анализом преимуществ и недостатков этих циклических
устройств. Синтез этих устройств необходим в первую очередь потому, что они используются в качестве первых блоков в многоблочной
оригинальной структуре, защищённой патентами на изобретения.
В разделе 4 излагается основной оригинальный материал, касающийся описания и теоретического обоснования моделей цифровых
устройств циклического действия, защищённых патентами на изобретения, с различными примерами синтеза конкретных устройств,
с подробным сравнительным анализом этих устройств и известных
устройств подобного типа и определением достигаемого существенного эффекта. При этом синтезируются аналоги широко используемых устройств с различными видами переноса информации (последовательным, параллельным, сквозным) и различными видами кодов для кодирования внутренних состояний и представления выходной информации. Предлагается оригинальная модификация таблиц
переходов, позволяющая более компактно по сравнению с их традиционной формой описывать алгоритмы функционирования устройств данного класса и проводить синтез схем практически неограниченной размерности.
Приводятся пояснения по поводу распечаток схем для моделировния в среде Multisim всех синтезированных в работе устройства,
а также порядка работы с ними в процессе моделирования.
Необходимо отметить, что рассмотренные в монографии вопросы чрезвычайно важны и не утратили своей актуальности в связи с прогрессом микроэлектроники и развитием автоматизированных систем разработки.
Это следует, например, из предисловия
к фундаментальной работе известного американского специалиста
Дж.Ф. Уэйкерли (Проектирование цифровых устройств», том I–II. —
M.: Постмаркет, 2002.), где о подходе автора к проектированию цифровых устройств сказано: «Его подход многогранен. Он основан на
исходных принципах цифровой электроники, не меняющихся с развитием технологии, состоящих в рассмотрении комбинационных и
последовательностных логических схем и конечных автоматов».
Основное назначение монографии — ознакомление специалистовразработчиков цифровых устройств с эффективным оригинальным
подходом к синтезу самых распространённых функциональных узлов цифровой техники.
Все схемы, синтезированные в пособии, проверены моделированием на ПЭВМ с использованием программ Multisim 6.0 и Multisim

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

Структурная схема цифрового
устройства

Цифровые устройства выполняют функции обработки информации, отображаемой в виде двоичных кодовых комбинаций, и в
общем случае любое из них может быть представлено в виде некоторого устройства с неизвестной внутренней структурой (рис. 1.1),
имеющего входы x1, x2, . . . , xn и выходы z1, z2, . . . , zk.

Рис. 1.1. Цифровое
устройство с неизвестной
(произвольной) структурой

Устройство под действием двоичных
комбинаций состояний входов (входных сигналов) переходит из одного внутреннего состояния в другое и формирует двоичные комбинации состояний выходов (выходные сигналы).
Закон (алгоритм) функционирования
устройства — это соответствие последовательностей двоичных комбинаций состояний входов последовательностностям двоичных комбинаций состояний выходов. Двоичные комбинации состояний некоторых объектов называют иногда наборами.

Рис. 1.2. Обобщенная
(структурная, каноническая)
схема цифрового устройства

Эта схема может быть детализирована в плане выделения из неё некоторых
элементов, комбинации состояний которых будут определять внутренние состояние устройства (рис. 1.2). Эти элементы являются элементами памяти (ЭП) [4,
6, 7, 8, 9, 11, 15, 21].
Эта структурная схема (часто её называют канонической, обобщенной или
моделью Хаффмена [11, 12]) содержит
также логический преобразователь (блок
ЛП), часто называемый комбинационной
схемой (КС).
Блок ЛП (КС) имеет алгоритм фун

Структурная схема цифрового устройства
9

кционирования, при котором каждой комбинации состояний входов
x1, x2, . . . , xn, . . . , xn+s соответствует одна комбинация состояний выходов z1, z2, . . . , zk, . . . , zk+s. Отсюда и термин «комбинационная схема».
Входы x1, x2, . . . , xn — внешние входы устройства.
Входы xn+1, . . . , xn+s — внутренние входы комбинационной схемы, являющиеся выходами элементов памяти.
Выходы z1, z2, . . . , zk — внешние выходы устройства.
Выходы zk+1, . . . , zk+s — внутренние выходы комбинационного
устройства, являющиеся входами элементов памяти.
Элементы памяти являются устройствами, занимающими два
состояния 0 и 1. Комбинации их состояний являются внутренними
состояниями устройства.
Состояние выходов логического преобразователя зависит не
только от состояния внешних входов, но и от состояния внутренних
входов, являющихся выходами элементов памяти.
Переход устройства из одного внутреннего состояния в другое
происходит при изменении состояния внешних входов.
При изменении состояния внешних входов, приводящем к изменению внутреннего состояния, изменяется состояние внутренних выходов таким
образом, что оно соответствует состоянию элементов памяти в следующем внутреннем состоянии.
Элементы памяти под действие внутренних выходов переходят
в состояние, соответствующее следующему внутреннему состоянию.
При этом состояние внешних выходов при одном и том же состоянии внешних входов может быть различным, так как оно определяется не только внешними входами, но и состоянием элементов памяти. Состояние элементов памяти определяется предысторией работы
устройства, т. е. теми последовательностями комбинаций состояний
входов (входными сигналами), которые поступали на вход устройства в предыдущие моменты времени.

1.1. Комбинационные и последовательностные
цифровые устройства

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

Р а з д е л 1

Последовательностное цифровое устройство (устройство с памятью) — устройство, в котором комбинация состояний выходов определяется не только комбинацией состояний входов в данный момент,
но и комбинацией состояний входов в предыдущие моменты времени [1, 3, 10, 14, 17–20, 22, 32–35].
Структурная схема цифрового устройства (рис. 1.2) представляет собой последовательностное устройство. Её блок ЛП (КС) является комбинационной схемой. Иногда комбинационную схему называют цифровым устройством с одним внутренним состоянием.
Таким образом, любое последовательностное устройство состоит из комбинационного устройства (логического преобразователя) и
элементов памяти.
Часто комбинационное устройство называют логическим блоком ввиду того, что оно, как будет показано ниже, строится из логических элементов, а совокупность элементов памяти, в качестве которых чаще всего используется триггеры, называют блоком памяти.

1.2. Понятие конечного автомата

Структурная схема (см. рис. 1.2) в теории автоматов называется
также структурной моделью конечного автомата. Существует абстрактная модель конечного автомата, которая не рассматривается в
данном пособии.
Автомат называется конечным ввиду того, что конечно множество комбинаций состояний входов (их число равно 2n), множество
комбинаций состояний выходов (их число равно 2k), множество внутренних состояний (их число равно 2s) [4, 7, 8, 10, 29, 33–35].
Методы теории автоматов [4, 8] лежат в основе инженерных методов синтеза цифровых устройств. Поэтому часто при инженерном
синтезе цифровых устройств используется термин «цифровой автомат», «автомат с памятью», «автомат без памяти» и даже «конечный автомат» и т. п.
В данной монографии мы будем использовать термин «цифровое устройство» или просто «устройство» с указанием его особенностей.

1.3. Шесть объектов (параметров) цифрового
устройства

Цифровое устройство, или конечный автомат (см. рис. 1.2) определяется шестью объектами (параметрами), которые также определяют конкретное цифровое устройство, реализованное в соответствии с этой структурной схемой [4, 8]: