Синтез цифровых автоматов

Глушков В.М.

Скачать: в формате pdf (176 Мб) или в формате djvu (5, 3 Мб)

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

Предисловие

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

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

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

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

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

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

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

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

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

Развиваясь в рамках логико-математической теории релейно-контактных схем, теория комбинационного синтеза достигла значительных успехов и после появления электронных цифровых машин стала успешно приспосабливаться к проблемам синтеза схем из электронных логических элементов. В этот период она пополнилась также существенными фрагментами теории структурного и блочного синтеза автоматов (см., например, работы Д. Xафмена, Г. Мили, В. И. Шестакова, М. Уилкса и др.).

Несколько отстала в своем развитии теория абстрактного и надежностного синтеза автоматов. Первый существенный сдвиг в этих разделах теории автоматов произошел в результате появления известного сборника статей «Автоматы» под редакцией К. Шеннона и Дж. Макка р т и. В первую очередь этот сдвиг был обязан помещенным в указанном сборнике работам С. К. Клини, Э. Мура и Д. Неймана.

В упомянутых работах Клини и Мура было положено начало возникновению абстрактной теории автоматов, хотя сами полученные в них результаты были еще достаточно далеки от возможности реального их использования на этапе абстрактного синтеза автоматов, где в это время продолжали господствовать эмпирические методы. В работе Неймана было положено начало созданию общей математической теории для одной из самых интересных областей надежностного синтеза, именно — теории синтеза надежных схем из ненадежных элементов.

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

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

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

Что касается характера изложения, то он определяется следующими соображениями, казавшимися автору существенными для достижения указанной цели.

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

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

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

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

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

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

В заключение скажем несколько слов о характере распределения материала в книге. Книга состоит из семи глав.

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

Вторая глава посвящена изложению проблем, возникающих на этапе абстрактного синтеза автоматов. Эта глава почти полностью построена на основании собственных результатов автора, изложенных в упомянутых выше его работах, а также некоторых новых результатов, излагаемых впервые. То же самое относится к первым двум, а также к последнему, параграфам третьей главы, которая посвящена структурной теории автоматов. В остальных параграфах этой главы содержится теоретический материал, подготавливающий читателя к усвоению проблематики и методов комбинационного синтеза. Наряду с некоторыми новыми вопросами здесь изложены также основы булевой алгебры, включая теорему о функциональной полноте; § 7 гл. III существенным образом использует идеи и методы, содержащиеся в работе С. В. Яблонского «Функциональные построения в &-значной логике».

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

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

В главе произведено обобщение постановки и методов решения известных проблем гонок и риска. Изложены также (в несколько измененной интерпретации) известные результаты Шеннона — Мура о синтезе надежных схем из ненадежных элементов. Приведены простейшие сведения о самокорректирующихся кодах.

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

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

Имея в целом прикладную направленность, излагаемый в книге материал основан на широком использовании идей, понятий и средств математической логики. Так, гл. IV, большая часть гл. III, а также гл. V представляют собой, по существу, разделы современной прикладной логики, точнее, прикладной теории булевых функций. Абстрактная теория алгоритмов, излагаемая в гл. II, может рассматриваться как один из разделов теории алгоритмов, также имеющий ярко выраженную прикладную направленность. Один из аспектов прикладной теории алгоритмов составляют и вопросы алгоритмической структуры универсальных цифровых машин, рассматриваемые в §§ 1 и 3 гл. VII. Всем сказанным и объясняется включение этой книги в серию «Математическая логика и основания математики».

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

В. М. Глушков
Киев
май 1961 г.

Помещена в музей с разрешения родных автора 31 мая 2019