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

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

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

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

Устройства, у которых дискретны множества внутренних состояний, входных и выходных сигналов, а также множество моментов времени, в которые поступают входные сигналы, меняются внутренние состояния и выдаются выходные сигналы, называются дискретными.

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

· информационные – справочные автоматы, электронные табло, светофоры, устройства аварийной сигнализации и пр.;

· управляющие – кодовый замок, устройство управления лифтом, станки с программным управлением, микропроцессоры фотоаппарата, видео пр.;

· вычислительные – микрокалькулятор, микропроцессоры компьютеров.

Существуют устройства, осуществляющие деятельность всех трёх видов, например, компьютер, автопилот и др.

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

Другими словами, функция переходов показывает, в какое состояние из всех возможных перейдёт дискретное устройство, если оно находилось в состоянии , а на вход поступил символ .

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

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

Говорят, что пятеркой компонентов задаётся автомат, обеспечивающий преобразование по определённым правилам последовательностей символов входного алфавита в выходную последовательность. Действительно, если принять начальное условие , то рекуррентные соотношения и определят порядок преобразования конечной последовательности входных символов , , …, в некоторую последовательность выходных символов той же длины , , …, ; при этом будет возникать определённая последовательность внутренних состояний. В этом и заключается функционирование автомата. Выходной символ, вырабатываемый автоматом на некотором такте , зависит не только от входного символа, воспринятого на этом же такте, но и от символов, поступивших ранее – они фиксируются в автомате путём изменения его внутреннего состояния. В этом смысле множество внутренних состояний автомата является его внутренней памятью. В зависимости от объёма этой памяти выделяются следующие типы автоматов:

· без памяти;

· с конечной памятью;

· с бесконечной памятью.

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

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

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

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

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

· в-третьих, рассматривается круг вопросов, в которых определяется строение автомата по характеру и соотношению входных и выходных сигналов (автомат – «чёрный ящик») – это важная прикладная задача технической диагностики устройств, без которой невозможна их практическая эксплуатация;

· в-четвёртых, выделяются структурных элементов автоматов и определяются правил построения из них сложных устройств (задача синтеза автоматов) – с этим связана разработка новых автоматов, в частности, компьютеров.

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

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

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

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

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

Дата добавления: 2015-10-28