Системный анализ гетерогенных слабоструктурированных автоматов. Переход от преобразований "химического типа" к логическим схемам и обратно

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Самарский государственный технический университет

Системный анализ гетерогенных слабоструктурированных автоматов. Переход от преобразований «химического типа» к логическим схемам и обратно

Е.Н. Гребенщиков

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

Ключевые слова: логические схемы, функциональная полнота, «химические логические элементы», двухстабильные элементы, автоматы Мили и Мура.

В первой части статьи «Системный анализ гетерогенных слабоструктурированных автоматов. I. Основные определения и свойства»были рассмотрены некоторые свойства автоматов нового типа, для которых предложено название «слабоструктурированные гетерогенные самосинхронные автоматы с индивидуальными именами объектов операций»(СГСА с ИИОО)[1]. Для удобства во второй части статьи сохранена сквозная нумерация утверждений (т. е. как продолжение [1]).

В [2] для аналого-цифровых систем обработки информации гетерогенного характера предложен следующий набор функциональных блоков - ФБ (рис. 1).

Рис. 1. Реализация булевых функций в специальном базисе ФБ

В [2, 3] доказано, что справедливо следующее.

Лемма 1. С помощью ФБ типа «2И», «НЕ», «разветвителя», «константы 0» или «константы 1» (рис. 1) могут быть реализованы любые булевы функции.

Фактически лемма 1 повторяет, с учетом специфики СГСА с ИИОО, известную в логике теорему о функциональной полноте системы логических функций с конъюнктором и инвертором [4].

Химические реакции (т. е. функциональности «химического типа») с очевидностью относятся к самосинхронным процессам, которые происходят только тогда, когда в среде присутствуют все компоненты реакции. Чтобы исследовать возможные пути перехода к «химическим» самосинхронным функциональностям, сначала снабдим все ФБ (рис. 1) входами синхронизации ci, при подаче сигнала на которые выполняется заданная функция элемента и на выходе запомнится полученный результат - до прихода следующего импульса синхронизации (рис. 2).

Введем также понятие уровня обработки - т. е. положения соответствующего элемента и других элементов, которые переключаются синхронно с ним, на самой длинной цепочке распространения сигнала в схеме реализации функции. На рис. 2 одной из таких цепочек является следующая: вход x - верхний разветвитель - верхняя схема «НЕ» - следующий разветвитель - верхняя схема «2И» - выход 0. Момент подачи очередного синхронизирующего импульса на любом уровне должен отстоять от импульса предшествующего уровня на время, достаточное для надежной обработки сигналов на предшествующем уровне.

Рис. 2. Пример двоичного дешифратора на синхронных ФБ. Уровни обработки сигналов отмечены вертикальными пунктирными линиями с цифрами 1...4. Рядом показаны входы синхронизации соответствующего уровня

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

Доказательство. Поскольку в условии леммы 2 сразу оговаривается нормальный (естественный) режим синхронизации, а состав ФБ - тот же, что и в лемме 1, то с очевидностью все логические операции будут выполнены так же и в том же порядке, что и для схем, построенных на основании леммы 1.

В соответствии с определениями 1, 2 сформулируем следующее.

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

Схемы таких преобразований элементов рис. 1, рис. 2 представлены на рис. 3.

Заметим, что согласно рис. 3 одна и та же функция может быть выполнена несколькими типами гетерогенных самосинхронных автоматов с индивидуальными именами объектов именно благодаря индивидуализации «имен» сигналов.

Так, функция «2И» может быть реализована как по схеме с промежуточным объектом c и сигналом синхронизации ((a=x)+(b=y)?c)+(d=ci)?(e=z), где объект «d»выполняет функцию внешнего сигнала синхронизации ci, так и по схемам без специального сигнала синхронизации (a=x) + (b=y) ? (c=z) и даже (a=x) + (b=y) ?<(c=z), («f»игнорируется)>. Необходимость в двух последних случаях (изображенных на рис. 3 в верхней строке справа) в сигнале синхронизации отпадает по той причине, что его функцию выполняют оба входных сигнала x иy. Только при одновременном наличии объектов (a=x) и (b=y) будет получен объект «c», соответствующий выходному сигналу «z». Если все же сигнал синхронизации необходим, можно воспользоваться схемой, в которую он введен в явном виде.

Последняя сверху справа схема на рис. 3 с двумя основными выходными «сигналами-объектами»«c» и «f» иллюстрируетвозможностьиспользованиятолькочастивыходныхобъектоввкачестве важных ,несущих «информацию» о входных объектах-сигналах. Действительно, индивидуализация имен входных и выходных объектов дает возможность на всех последующих уровнях обработки игнорировать сигнал «f» как не относящийся к сигналам, несущим значимую информацию. В дальнейшем такую ситуацию «игнорирования» некоего объекта-сигнала «w» будем записывать так: w=indif(тоесть «w» - бесполезный, ненужный сигнал-объект).

Рис. 3. Перевод универсального базиса двоичной синхронной логики в гетерогенные автоматы с функциональностями типа (1) и (2) из [1]

Для инвертора с внешним сигналом синхронизации схема очевидна: (g=x)+(h=ci)?(k=y=-x=0, если объекту x приписывается смысл логической 1).То есть объекту «k» мы приписываем значение выхода y=-x= 0 при наличии на входе x=1 и сигнале синхронизации ci. Соответственно,при отсутствии на входе x=1, тое сть при x=0 и наличии сигнала синхронизации ci=1, «значение» выходного объекта гетерогенного автомата «равно» объекту, представляющему сам «сигнал» синхронизации, тоесть «h». Т. о., «инверсное» значение входного сигнала x=0, соответствующее выходномусигналу-x=1=y,представляется объектом «h» - то есть «сигналом» синхронизации, обойтись без которого в данном случае нельзя. Исходя из этого обстоятельства и должна строиться вся последующая обработка объектов.

Отметим, что как и для схемы «2И», для реализации инвертора «НЕ» возможна гетерогенная схема с несколькими выходными сигналами-объектами, только один из которых является значимым, тогда как остальные - indif-объекты. Более того, согласно нашим определениям схема (2) из [1]может выполнять функции схемы (1) из [1]: т. е. функция a+b?c может быть реализована с помощью схемы a+b?d+f, так как можно записат ьd+f= <(d=c), (f=indif)>.

Для разветвителя с синхронизацией можно использовать схему в верхнем ряду справа рис. 3. Для реализации разветвителя без синхронизации используется схема, соответствующая (2)из [1], изображенная на рис. 3 справа внизу.?

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

Лемма 4. Любая конечная комбинационная схема (КС) от конечного числа булевых переменных может быть преобразована в эквивалентную конечную систему (сеть) слабоструктурированных гетерогенных автоматов с индивидуальными именами объектов и некоторым конечным числом дополнительных внешних объектов («сигналов»), выполняющих функцию синхронизации.

Наиболее очевидный путь доказательства леммы 4 - это сначала перевод схемы реализации данной булевой функции в универсальном базисе леммы 1 в схему с синхронизацией, и затем - перевод последней в систему гетерогенных самосинхронных автоматов с возможно меньшим числом сигналов синхронизации. Покажем, что для любого конечного числа входных булевых переменных исходной функции такое преобразование в рамках МНФ («метода назначенных функциональностей» - см. [1]) по предложенным выше схемам всегда осуществимо. Действительно, после ее перевода (лемма 2) в схему с синхронизацией мы получим схему с конечным числом элементов. Выберем в ней сигнал i (из всех входных, выходных и промежуточных), в котором используется наибольшее число разветвителей с наибольшим числом уровней обработки, на которых происходит разветвление. Пусть их число равно p. Выполняем следующее.

1. Для самого последнего из этих p уровней - уровня j - выберем согласно МНФ любой объект типа bk*bs. Для всех остальных схем разветвления сигнала i на том же уровне j выберем другие объекты, компоненты (и имена) bk, bs которых не совпадают с компонентами (именами) уже использованных. Так продолжаем до тех пор, пока не припишем всем разветвителям сигнала i на уровне j индивидуальные объекты (и имена). Теперь на входе каждого разветвителя сигнала i уровня j запишем выбранный для него объект bk*bs; на входе его синхронизации - подходящий объект типа xks; на выходах разветвителя - соответствующие данному входному объекту bk*bs и xks его компоненты - то есть выходные объекты bk и bs*xks.

2. Переходим на предыдущий уровень j-1 разветвления сигнала i. Для соответствующих пар выходных объектов типа bk*bs каждого разветвителя сигнала i на этом уровне подбираем подходящий объект типа xks и соответствующий входной объект, не использовавшиеся ранее. Записываем их на соответствующих входах каждого разветвителя сигнала i на уровне j-1, пока не припишем индивидуальные объекты (и имена) всем входам сигналов и всем входам синхронизации всех таких разветвителей.

3. Повторяем пункт 2 для каждого предыдущего уровня разветвления сигнала i, пока процесс разветвления не закончится - т. е. пока не выйдем на уровень j-p.

4. Для всех схем типа «2И» и инверсии «НЕ», связанных своими входами и/или выходами с входами-выходами схем разветвления, подбираем подходящие индивидуальные объекты (с индивидуальными именами) из оставшегося списка функциональностей в соответствии с рис. 3. Заканчиваем, когда все схемы, связанные с разветвителями, получат индивидуальные имена объектов для всех своих входных и выходных объектов-сигналов.

5. Переходим к логическим элементам и разветвителям, входы и/или выходы которых связаны с входами и/или выходами элементов, имеющих индивидуальные имена объектов. Поскольку булевы функции в КС не содержат обратных связей, то мы не столкнемся с ситуацией, когда какой-либо выходной сигнал-объект j-ого уровня попадает на предыдущий и тем самым приводит к противоречию, когда входные и выходной сигналы для какого-то элемента уже определены и требуется подобрать функциональность, соответствующую этой комбинации, уже задействованную в другом месте. Здесь, однако, могут возникнуть иные критические ситуации - когда перед разветвителями стоит достаточно много схем «2И» и мы, пытаясь использовать для реализации этих схем функциональности типа (1), вынуждены в качестве исходных объектов для схемы «2И» использовать те же объекты, что и на выходе разветвителя. То есть, имея на входе разветвителя объекты типа bk*bs и, соответственно, на его выходе два объекта bk и bs, мы хотим в схеме «2И» предшествующего уровня, выход которой связан со входом данного разветвителя, использовать те же элементы bk и bs, а именно реализовать схему «2И» в соответствии с (1) из [1]: bk+bs®c= bk*bs. Согласно правилу индивидуализации сигналов это недопустимо. Для разрешения конфликта необходимо использовать либо другие объекты, либо другой тип функциональности - например, типа (2) из [1]: a+b®c+f= =<(c=bk*bs), (f=indif)> (запись функциональности дана по рис. 3). Ясно, что используемые здесь объекты a и b должны отличаться от bk и bs. Более того, вариантов таких схем с исходными объектами, отличными от bk и bs, по крайней мере теоретически, может быть сколь угодно много.

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

Заметим, что в случае ООП рассмотренный выше подход вполне реализуем практически, поскольку при написании текстов программ мы вольны сами выбирать имена объектов и назначать их функциональности (которые в ООП называются «методами»). Однако для химических реакций мы фактически пока доказали лишь теоретическую (абстрактную) возможность преобразования конечных КС булевых функций в некие гипотетические и конечные системы химических реакций типа (1) и (2) из [1]. Вопрос о том, как такие системы химических реакций реализовать практически в каждом конкретном случае, остается открытым. Однако этого и не требует принятая нами формулировка утверждения 2.ю

Лемма 4 обеспечивает также истинность следующего утверждения.

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

Чтобы доказать утверждение 5, нам нужно лишь показать реализуемость в системе рассмотренных выше функциональностей элементов памяти. Но это уже было сделано раньше - см. интерпретацию схемы функциональности (2) в работе [1], а также на рис. 1 в [1]. Таким образом, утв. 5 доказано в полном объеме.ю

Утверждение 6. С помощью функциональностей утв. 5 может быть реализован любой конечный автомат Мили (Мура) в виде системы (сети) гетерогенных автоматов с индивидуальными именами объектов и внешней синхронизацией.

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

Рассмотрим автомат Мили (рис. 4). Выполним его комбинационную схему (КС) в функционально-полном базисе элементов «2И», «НЕ», констант и разветвителей согласно лемме 1. Переведем КС автомата в соответствующие схемы с синхронизацией, а затем - в систему гетерогенных автоматов по алгоритму, использованному в доказательстве леммы 4.

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

Рис. 4. Стандартная реализация автомата Мили

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

Наличие внешних синхронизирующих сигналов в гетерогенных автоматах, способных работать в режиме самосинхронизации, конечно, ухудшает качество системы в целом. Сигналы синхронизации появляются тогда, когда мы сталкиваемся с задачей разветвления или инверсии основных «информационных» сигналов. Таким образом, одна из важных задач оптимизации гетерогенных автоматов - максимальный их перевод на элементный базис «2И», т. е. на функциональности типа (1) из [1] с минимумом инверторов и разветвителей.

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

Утверждение 7. Любая конечная система функциональностей химического типа, состоящая из схем, соответствующих записям (1) и/или (2) в [1], может быть преобразована в эквивалентную схему классического конечного автомата, реализованного на двоичных (булевских) логических элементах.

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

Заключение. В статье показано, что, по крайней мере в теоретическом плане, сети (схемы) слабоструктурированных гетерогенных самосинхронных автоматов с индивидуальными именами объектов операций (СГСА с ИИОО), включая схемы химических реакций, заданные формами (1) и (2) в [1], могут быть заменены подходящими схемами обычных автоматов Мили или Мура, и наоборот - для конечных схем автоматов Мили или Мура можно подобрать соответствующие сети СГСА с ИИОО, выдающих определенные типы сигналов-объектов в ответ на определенные внешние сигналы-объекты и текущее состояние автомата. Однако в практическом плане гарантий реализации произвольных конечных схем классических автоматов Мили или Мура в соответствующих системах химических реакций данная статья не дает. Тем не менее полученный теоретический результат может рассматриваться как призыв к поиску таких подходов, поскольку из подобных сетей могут быть построены различные химические аналоги существующих вычислительных систем, включая самовоспроизводящиеся и саморазвивающиеся автоматы.

Библиографический список

Крылов С.М. Системный анализ гетерогенных слабоструктурированных автоматов I. Основные определения и свойства // Вестник СамГТУ. Сер. Технические науки. - Самара: СамГТУ, 2012. - № 1. - С. 17-23.

Крылов С.М. Синтез электронных блоков из гетерогенных компонентов // Труды 6-й межвузовск. научно-практ. конференции. - Самара: СамГТУ, 2007. - С. 116-119.

Крылов С.М., Сараев М.В. Синтез конфигурируемых блоков для аналого-цифровых систем-на-кристалле с использованием гетерогенных функциональных компонентов // ВестникСамарск. гос. техн. ун-та. Сер. Техн. науки. - Самара: СамГТУ, 2007. - № 2. - С. 58-63.

Крылов С.М., Сараев М.В. Функциональная полнота вычислительных систем // Труды 7-й межвузовск. научно-практ. конференции. - Самара: СамГТУ, 2008. - С. 194-197.

Алгебраическая теория автоматов, языков и полугрупп / Под ред. М.А. Арбиба. Пер. с англ. - М.: Статистика, 1975. - 335 с.

Размещено на Allbest.ru