Студопедия
Обратная связь


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram 500-летие Реформации


Дискретные устройства без памяти

Введенное в предыдущем параграфе понятие автомата является достаточно общим. Накладывая ограничения на компоненты X, Y, Q, Ψ, Θ можно получить частные случаи автоматов. Одним из них являются автоматы без памяти, т.е. устройства, в которых не происходит фиксации внутреннего состояния. Очевидно, в этом случае из общего описания должны быть исключены компоненты Q и Ψ; автомат без памяти задается тройкой компонентов < X, Y, Θ>. Соотношение (9.2) принимает вид

т.е. выходной символ на данном такте определяется только входным символом и не зависит от ранее поступивших символов. Следовательно, каждый автомат без памяти реализует единственный преобразователь (оператор), который осуществляет «побуквенный перевод» входных последовательностей символов в выходные.

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

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

Подобные устройства могут быть построены путем соединения некоторого набора элементарных компонентов (элементов). Эти элементы образуют конечный набор, называемый базисом, а входящие в него элементы - базисными. Базис имеет смысл совокупности элементарных (простейших) действий, о которых шла речь в теории алгоритмов, а базисный элемент можно рассматривать в качестве устройства, выполняющее элементарное действие. Если речь идет о двоичных дискретных устройствах, то базисы строятся из элементов, которые реализуют простейшие логические функции. Напомним, что к таким функциям относятся конъюнкция (логическое И - ^), дизъюнкция (логическое ИЛИ - v), импликация (→), сумма по модулю 2 (Å), эквивалентности (~) и отрицания (логическое НЕ - Ø,). Однако между простейшими функциями имеются соотношения эквивалентности (см. приложение), позволяющие выразить одни функции через другие. В результате оказывается, что нет необходимости включать в базис все элементы, реализующие простейшие логические функции - достаточно выбрать некоторое минимальное их подмножество. Этому условию удовлетворяет базис, построенных на элементах И, ИЛИ и НЕ - он называется простейшим, а входящие в него элементы - логическими элементами или (логическими вентилями). Схемы элементов приведены на рис. 9.1. Рассмотрим каждый их них по отдельности.

Элемент И (^) имеет два входа, на которые независимо могут подаваться сигналы x1 и х2; каждый из сигналов является двоичным, т.е. может принимать одно из двух значений - 1 или 0; элемент формирует единственный выходной сигнал у, значения которого определяются только входными сигналами. Функция выходов Q (x1,x2) согласно табл. Б.1 (см. приложение Б) принимает следующие значения:

Функция выходов элемента ИЛИ (V) принимает следующие значения:

Логический элемент НЕ (Ø) обеспечивает одноместное преобразование (с одним входным сигналом) в соответствии с правилами:

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

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





 

Читайте также:

Связь компьютеров по телефонным линиям

Вероятность какого-либо одного из двух исходов независимых и несовместных событий равна сумме их вероятностей

Определение системы

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

Об объектном подходе в прикладной информатике

Вернуться в оглавление: Теоретические основы информатики

Просмотров: 1635

 
 

54.198.205.145 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам.