Архитектура компьютерных систем 1 часть. Логические вентили / Хабр
Логические элементы
Доброго времени суток, я начинаю серию статей по написанию виртуальной машины на языке Golang. Я выбрал этот язык так как он прост для чтения и имеет в стандартной библиотеке уже необходимые функции, которые пригодятся в дальнейшем.
Эта статья не несёт в себе абсолютно никакой новой информации для тех, кто умеет составлять таблицы истинности для простых логических вентилей. Если вы это умеете, то не тратьте время и переходите ко второй части.
Логический вентиль это устройство с одним или несколькими входами и одним или несколькими выходами. В этой части будем рассматривать только самые простые из них. Для моделирования вентилей мы будем использовать только сигналы 0 и 1, не используя входные, выходные характеристики реальных вентилей.
Так как мы будем работать с Golang, то каждый элемент можно представить в виде функции.
В Go функция выглядит так:
func имя(имя переменной тип переменной) тип возвращаемого значения { //код return имя возвращаемой переменной }
Буфер
Это самый простой элемент имеющий один вход и один выход. На практике используется для усиления сигнала или создания задержки, иногда можно заменить проводником.
в случае с буфером наша функция будет выглядеть так:
func Buf(v bool) bool {
return v
}Инвертор
Тот же самый буфер, только на выходе инвертирует сигнал.
в случае с инвертором функция будет выглядеть так:
func Inv(v bool) bool {
return !v
}ИЛИ
Этому элементу необходим хотя бы один сигнал равный 1, чтобы на выходе получить 1.
func Or(v, s bool) bool {
return v || s
}И
Всегда возвращает 1, когда на все его входы подаётся 1, во всех остальных случаях он возвращает 0.
func And(v, s bool) bool {
return v && s
}Исключающее ИЛИ
Для того, чтобы на выходе получить 1, нужно чтобы на вход подавались разные сигналы (0 и 1) или (1 и 0). Эта операция является полезной, так как позволяет поменять местами две переменные без использования дополнительной памяти. s) мы не можем потому, что для bool такой операции в языке нет, поэтому юзаем костыль return (v || s) && !(v && s) }
ИЛИ-НЕ
Работает как элемент ИЛИ, только к его выходу подсоединён инвертор, с которого получаем сигнал.
func Nor(v, s bool) bool {
return !(v || s)
}И-НЕ
Элемент работает точно так же, как элемент И, только на выходе инвертируется сигнал.
func Nand(v, s bool) bool {
return !(v && s)
}Исключающее ИЛИ с инверсией
Элемент работает точно так же, как элемент ИЛИ, только на выходе инвертируется сигнал.
func Xnor(v, s bool) bool {
// и тут костыль
return !((v || s) && !(v && s))
}Теперь, когда функции написаны, можно их собрать в пакет Gate, на основе которого будем реализовывать более сложные вещи. Наша иерархия пакетов будет похожа иерархию абстракций реального компьютера. Исходный код можно найти здесь.
Создан логический вентиль из ДНК
Логический вентиль выдает тот или иной сигнал на выходе в зависимости от входных сигналов. В данном случае ученым удалось реализовать логические вентили, выполняющие различные логические функции, в частности функцию исключающего «ИЛИ». Ключевыми элементами созданной авторами новой работы системы выступали комплементарные нити ДНК, то есть нити определенных последовательностей, которые образуют друг с другом прочное соединение. Каждая из нитей представляла значение «1», если присутствовала, и «0», если отсутствовала. Чтобы непосредственно наблюдать, какой сигнал нити создают на входе, ученые присоединили к ним флуоресцирующие молекулы. Когда на входе присутствовала только одна нить, молекула испускала свечение, а когда нитей было две, их флуоресценция взаимно гасилась.
Помимо создания единичного работающего логического вентиля, ученые также получили систему из последовательно работающих вентилей, реализующих различные логические функции. Теоретически развитие этой работы может привести к созданию компьютера из ДНК, способного выполнять элементарные арифметические операции — сложение и вычитание. Кроме того, исследователи добились протекания нескольких последовательных операций, когда сигнал на выходе одного устройства служил входным сигналом для следующего.
Авторы новой работы протестировали в пробирке, насколько полезным созданное ими устройство может быть для медицины. Ученые связали логический вентиль с молекулой, способной инактивировать тромбин, фермент, вызывающий сворачивание крови. В норме сворачивание крови позволяет избежать кровотечений, но при сердечно-сосудистых заболеваниях образующиеся сгустки крови представляют серьезную опасность для жизни человека. В созданной учеными схеме инактиватор тромбина выделялся только в том случае, если вентиль «натыкался» на фермент.
Создание компьютеров на основе биологических систем — не самое популярное, но достаточно активно развивающееся направление науки. Различные коллективы исследователей по-разному подходят к решению этого вопроса. Один из возможных подходов — это создание компьютеров из бактерий. Недавно такой компьютер смог решить классическую вычислительную задачу по сортировке блинов.
По материалам www.nature.comrel=»nofollow»>;
www.newscientist.comrel=»nofollow»>; www.lenta.rurel=»nofollow»>
Цікава інформація для Вас:
НОУ ИНТУИТ | Лекция | Логические вентили, схемы, структуры
Аннотация: Рассматриваются основные теоретические (математические, логические) понятия и сведения, касающиеся базовых логических элементов и структур – логических вентилей, логических (переключательных) схем, логической базы аппаратуры ЭВМ и их оптимальной структуры, оптимизации их структур.
Любой, самый примитивный компьютер – сложнейшее техническое устройство. Но даже такое сложное устройство, как и все в природе и в технике, состоит из простейших элементов. Любой компьютер, точнее, любой его электронный логический блок состоит из десятков и сотен тысяч так называемых вентилей (логических устройств, базовых логических схем ), объединяемых по правилам и законам (аксиомам) алгебры вентилей в схемы, модули.Логический вентиль (далее – просто вентиль) – это своего рода атом, из которого состоят электронные узлы ЭВМ. Он работает по принципу крана (отсюда и название), открывая или закрывая путь сигналам.
Логические схемы предназначены для реализации различных функций алгебры логики и реализуются с помощью трех базовых логических элементов ( вентилей, логических схем или так называемых переключательных схем ). Они воспроизводят функции полупроводниковых схем.
Работу вентильных, логических схем мы, как и принято, будем рассматривать в двоичной системе и на математическом, логическом уровне, не затрагивая технические аспекты (аспекты микроэлектроники, системотехники, хотя они и очень важны в технической информатике).
Логические функции отрицания, дизъюнкции и конъюнкции реализуют, соответственно, логические схемы, называемые инвертором, дизъюнктором и конъюнктором.
Логическая функция «инверсия», или отрицание, реализуется логической схемой ( вентилем ), называемой инвертор.
Принцип его работы можно условно описать следующим образом: если, например, «0» или «ложь» отождествить с тем, что на вход этого устройства скачкообразно поступило напряжение в 0 вольт, то на выходе получается 1 или «истина», которую можно также отождествить с тем, что на выходе снимается напряжение в 1 вольт.
Аналогично, если предположить, что на входе инвертора будет напряжение в 1 вольт («истина»), то на выходе инвертора будет сниматься 0 вольт, то есть «ложь» ( схемы на рисунках 6.1 а, б).
Рис. 6.1. Принцип работы инвертора
Функцию отрицания можно условно отождествить с электрической схемой соединения в цепи с лампочкой (рис. 6.2), в которой замкнутая цепь соответствует 1 («истина») или х = 1, а размыкание цепи соответствует 0 («ложь») или х = 0.
Рис. 6.2. Электрический аналог схемы инвертора
Дизъюнкцию реализует логическое устройство ( вентиль ) называемое дизьюнктор (рис. 6.3 а, б, в):
Рис. 6.3a.
Рис. 6.3b.
Рис. 6.3c. Принцип работы дизъюнктора
Дизъюнктор условно изображается схематически электрической цепью вида (рис. 6.4)
Рис. 6.4. Электрический аналог схемы дизъюнктора
Конъюнкцию реализует логическая схема ( вентиль ), называемая конъюнктором (рис. 6.5 а, б, в):
Рис. 6.5a.
Рис. 6.5b.
Рис. 6.5c. Принцип работы конъюнктора
Логический вентиль — это… Что такое Логический вентиль?
Пример работы схемы RS-триггера, построенного на базе восьми 2И-НЕ логических вентилей.Логи́ческий ве́нтиль
— базовый элемент цифровой схемы, выполняющий элементарную логическую операцию[1], преобразуя таким образом множество входных логических сигналов в выходной логический сигнал. Логика работы вентиля основана на битовых операциях[2] с входными цифровыми сигналами в качестве операндов. При создании цифровой схемы вентили соединяют между собой, при этом выход используемого вентиля должен быть подключён к одному или к нескольким входам других вентилей. В настоящее время в созданных человеком цифровых устройствах доминируют электронные логические вентили на базе полевых транзисторов, однако в прошлом для создания вентилей использовались и другие устройства, например, электромагнитные реле, гидравлические устройства, а также механические устройства. В поисках более совершенных логических вентилей исследуются квантовые устройства[3][4], биологические молекулы[5], фононные тепловые системы[6].В цифровой электронике логический уровень сигнала представлен в виде уровня напряжения (попадающего в один из двух диапазонов) или в виде значения тока. Это зависит от типа используемой технологии построения электронной логики
Основные характеристики
Реализация
Хранение информации
История
Примечания
- ↑ gpntb.ru — Термины микроэлекроники
- ↑ Например: 2И-НЕ (NAND), XOR (исключающее ИЛИ) и другие.
- ↑ scientific.ru — Квантовый логический вентиль на сверхпроводниках
- ↑ pereplet.ru — Спиновые логические вентили на основе квантовых точек
- ↑ skms.impb.psn.ru — Электронный логический вентиль XOR на основе ДНК.
- ↑ lenta.ru — Создан логический вентиль для теплового компьютера.
- ↑ Наиболее известные это КМОП, ТТЛ, N-МОП, ЭСЛ, ДТЛ, РТЛ.
См. также
Архитектура компьютерных систем 1 часть. Логические вентили
Логические элементы
Доброго времени суток, я начинаю серию статей по написанию виртуальной машины на языке Golang. Я выбрал этот язык так как он прост для чтения и имеет в стандартной библиотеке уже необходимые функции, которые пригодятся в дальнейшем.
Эта статья не несёт в себе абсолютно никакой новой информации для тех, кто умеет составлять таблицы истинности для простых логических вентилей. Если вы это умеете, то не тратьте время и переходите ко второй части.
Логический вентиль это устройство с одним или несколькими входами и одним или несколькими выходами. В этой части будем рассматривать только самые простые из них. Для моделирования вентилей мы будем использовать только сигналы 0 и 1, не используя входные, выходные характеристики реальных вентилей.
Так как мы будем работать с Golang, то каждый элемент можно представить в виде функции.
В Go функция выглядит так:
func имя(имя переменной тип переменной) тип возвращаемого значения {
    //код
    return имя возвращаемой переменной
}Буфер
Это самый простой элемент имеющий один вход и один выход. На практике используется для усиления сигнала или создания задержки, иногда можно заменить проводником.
в случае с буфером наша функция будет выглядеть так:
func buf(v bool) bool {
    return v
}Инвертор
Тот же самый буфер, только на выходе инвертирует сигнал.
в случае с инвертором функция будет выглядеть так:
func inv(v bool) bool {
    return !v
}ИЛИ
Этому элементу необходим хотя бы один сигнал равный 1, чтобы на выходе получить 1.
func or(v, s bool) bool {
    return v || s
}И
Всегда возвращает 1, когда на все его входы подаётся 1, во всех остальных случаях он возвращает 0.
func and(v, s bool) bool {
    return v && s
}Исключающее ИЛИ
Для того, чтобы на выходе получить 1, нужно чтобы на вход подавались разные сигналы (0 и 1) или (1 и 0). s) мы не можем потому, что для bool такой операции в языке нет, поэтому юзаем костыль     return (v || s) && !(v && s) }
ИЛИ-НЕ
Работает как элемент ИЛИ, только к его выходу подсоединён инвертор, с которого получаем сигнал.
func nor(v, s bool) bool {
    return !(v || s)
}НЕ-И
Элемент работает точно так же, как элемент И, только на выходе инвертируется сигнал.
func nand(v, s bool) bool {
    return !(v && s)
}Исключающее ИЛИ с инверсией
Элемент работает точно так же, как элемент ИЛИ, только на выходе инвертируется сигнал.
func xnor(v, s bool) bool {
// и тут костыль
    return !(v || s) && !(v && s)
}Теперь, когда функции написаны, можно их собрать в пакет Gate, на основе которого будем реализовывать более сложные вещи. Наша иерархия пакетов будет похожа иерархию абстракций реального компьютера. Исходный код можно найти здесь.
Создан логический вентиль для теплового компьютера: Наука и техника: Lenta.ru
Ученые создали логические вентили для теплового компьютера. Вентили – основные элементы логической обработки данных – состоят из термических транзисторов, в которых носителем информации является наличие/отсутствие не электрического тока, а передачи тепла, сообщает PhysOrg.
В простейшем транзисторе обычного компьютера основным носителем информации является электрический ток: есть ток – транзистор находится в открытом состоянии, нет тока – в закрытом (на самом деле стандартный транзистор устроен чуть сложнее: состояние зависит от напряжения). В оптическом компьютере (такие уже созданы) функцию тока выполняет свет.
Профессор Баовэнь Ли (Baowen Li) и его коллеги из Национального университета Сингапура уже несколько лет работают над созданием еще одного типа компьютера, в котором носителем информации было бы тепло – тот вид энергии, который обычно считается в информационных технологиях бесполезным и даже вредным. Тепловой компьютер также называют «фононным»: в обычном компьютере информацию переносят электроны, в оптическом – фотоны, а в тепловом – фононы. Фононы – это квазичастицы, представляющие собой квант колебаний атомов твердого тела. С их помощью удобно описывать, в частности, передачу тепла.
Простейшим элементом теплового компьютера является термический транзистор, состоящий из трех точек (в обычных транзисторах точки называются электродами): две, определяющие состояние транзистора, особым образом соединены, третья – контрольная. Тепло в транзисторе передается колебаниями кристаллической решетки. Когда колебательные спектры двух точек перекрываются, между точками возникает устойчивый поток тепловой энергии (открытое состояние), когда не перекрываются – потока нет или он очень слаб (закрытое состояние).
Чтобы состояния были устойчивыми, система должна обладать особым свойством – малым тепловым откликом – большое изменение температуры должно вызывать малое изменение теплового потока. Сингапурская группа научилась делать такие системы в 2006 году.
На данный момент термические транзисторы позволяют оцифровывать тепловой сигнал, а также создавать вентили NOT (отрицание) и AND/OR (нестрогое ‘или’).
Исследователи утверждают, что потенциальный тепловой компьютер будет требовать сравнительно мало энергии и сможет питаться, например, остаточным теплом, производимым другими устройствами.
Логические вентили, схемы, структуры
Любой, самый примитивный компьютер – сложнейшее техническое устройство. Но даже такое сложное устройство, как и все в природе и в технике, состоит их простейших элементов. Любой компьютер, точнее, любой его электронный логический блок состоит из десятков и сотен тысяч так называемых вентилей (логических устройств, базовых логических схем), объединяемых по правилам и законам (аксиомам) алгебры вентилей в схемы, модули.
Логический вентиль (далее – просто вентиль) – это своего рода атом, из которого состоят электронные узлы ЭВМ. Он работает по принципу крана (отсюда и название), открывая или закрывая путь сигналам.
Логические схемы предназначены для реализации различных функций алгебры логики и реализуются с помощью трех базовых логических элементов (вентилей, логических схем или так называемых переключательных схем). Они воспроизводят функции полупроводниковых схем.
Работу вентильных, логических схем мы, как и принято, будем рассматривать в двоичной системе и на математическом, логическом уровне, не затрагивая технические аспекты (аспекты микроэлектроники, системотехники, хотя они и очень важны в технической информатике).
Логические функции отрицания, дизъюнкции и конъюнкции реализуют, соответственно, логические схемы, называемые инвертором, дизъюнктором и конъюнктором.
Логическая функция «инверсия», или отрицание, реализуется логической схемой (вентилем), называемой инвертор.
Принцип его работы можно условно описать следующим образом: если, например, «0» или «ложь» отождествить с тем, что на вход этого устройства скачкообразно поступило напряжение в 0 вольт, то на выходе получается 1 или «истина», которую можно также отождествить с тем, что на выходе снимается напряжение в 1 вольт.
Аналогично, если предположить, что на входе инвертора будет напряжение в 1 вольт («истина»), то на выходе инвертора будет сниматься 0 вольт, то есть «ложь» (схемы на рисунке 9).
Функцию отрицания можно условно отождествить с электрической схемой соединения в цепи с лампочкой (рисунок 10), в которой замкнутая цепь соответствует 1 («истина») или х=1, а размыкание цепи соответствует 0 («ложь») или х=0.
Рисунок 9 – Принцип работы инвертора
Рисунок 10 – Электрический аналог схемы инвертора
Дизъюнкцию реализует логическое устройство (вентиль) называемое дизъюнктор (рисунок 11):
Рисунок 11 – Принцип работы дизъюнктора
Дизъюнктор условно изображается схематически электрической цепью вида (рис. 12)
Рисунок 12– Электрический аналог схемы дизъюнктора
Конъюнкцию реализует логическая схема (вентиль), называемая конъюнктором (рис. 13):
Рисунок 13– Принцип работы конъюнктора
Конъюнктор можно условно изобразить схематически электрической цепью вида (рис. 14)
Рисунок 14– Электрический аналог схемы конъюнктора
Схематически инвертор, дизъюнктор и конъюнктор на логических схемах различных устройств можно изображать условно следующим образом (рис. 15). Есть и другие общепринятые формы условных обозначений.
Рисунок 15– Условные обозначения вентилей (вариант)
Из указанных простейших базовых логических элементов собирают, конструируют сложные логические схемы ЭВМ, например, сумматоры, шифраторы, дешифраторы и др. Большие (БИС) и сверхбольшие (СБИС) интегральные схемы содержат в своем составе (на кристалле кремния площадью в несколько квадратных сантиметров) десятки тысяч вентилей. Это возможно еще и потому, что базовый набор логических схем (инвертор, конъюнктор, дизъюнктор) является функционально полным (любую логическую функцию можно представить через эти базовые вентили), представление логических констант в них одинаково (одинаковы электрические сигналы, представляющие 1 и 0) и различные схемы можно «соединять» и «вкладывать» друг в друга (осуществлять композицию и суперпозицию схем).
Таким способом конструируются более сложные узлы ЭВМ – ячейки памяти, регистры, шифраторы, дешифраторы, а также сложнейшие интегральные схемы.
В двоичной системе таблицу суммирования цифры x и цифры y и получения цифры z с учетом переноса p в некотором разряде чисел x и y можно изобразить таблицей вида
Эту таблицу можно интерпретировать как совместно изображаемую таблицу логических функций (предикатов) вида
Логический элемент, соответствующий этим функциям, называется одноразрядным сумматором и имеет следующую схему (обозначим ее как или – если мы хотим акцентировать именно выбранный, текущий i-й разряд) (рис. 16):
Рисунок 16– Схема одноразрядного сумматора
«Черным ящиком» называется некоторое закрытое устройство (логическая, электрическая или иная схема), содержимое которого неизвестно и может быть определено (идентифицировано) только по отдельным проявлениям входа/выхода ящика (значениям входных и выходных сигналов). В «черном ящике» находится некоторая логическая схема, которая в ответ на некоторую последовательность входных (для ящика) логических констант выдает последовательность логических констант, получаемых после выполнения логической схемы внутри «черного ящика». Определим логическую функцию внутри «черного ящика» (рис. 17), если операции выполняются с логическими константами для входных последовательностей (поразрядно). Например, х = 00011101 соответствует последовательности поступающих значений: «ложь», «ложь», «ложь», «истина», «истина», «истина», «ложь», «истина».
Рисунок 17– Схема «черного ящика 1»
Из анализа входных значений (входных сигналов) х, у и поразрядного сравнения логических констант в этих сообщениях с константами в значении z – результате выполнения функции в «черном ящике», видно, что подходит, например, функция вида .
Действительно, в результате «поразрядного» сравнения сигналов (последовательностей значений «истина», «ложь») получаем следующие выражения (последовательности логических констант):
.
Важной задачей (технической информатики) является минимизация числа вентилей для реализации той или иной схемы (устройства), что необходимо для более рационального, эффективного воплощения этих схем, для большей производительности и меньшей стоимости ЭВМ.
Эту задачу решают с помощью методов теоретической информатики (методов булевой алгебры).
Пример. Построим схему для логической функции . Схема, построенная для этой логической функции, приведена на рис. 18.
Рисунок 18– Схема для функции 1
Пример. Определим логическую функцию , реализуемую логической схемой вида (рис. 19):
Рисунок 19– Схема для функции 2
Искомая логическая функция, если выписать ее последовательно, заполняя «верх» каждой стрелки, будет иметь следующий вид: .
Вопросы для обсуждения.
1. Что мы называем высказывательной формой?
2. Что называется логической переменной?
3. Что есть предикат?
4. Какая функция называется логической (булевой)?
5 Какую задачу мы называем инфологической?
6. Дайте определение логического вентиля.
7Структурные схемы алгоритмов
Общие сведения
Широкая известность понятия алгоритма в наше время обусловлена развитием и широким применением электронно-вычислительной техники. Использование ЭВМ способствовало уяснению того, что разработка алгоритма – необходимый этап в процессе решения задачи на ЭВМ и, что в связи с этим, алгоритмы представляют самостоятельную ценность как интеллектуальные ресурсы общества. В данных методических указаниях рассматриваются основы алгоритмизации как внемашинного процесса построения алгоритма.
Большинство филологов термин «алгоритм» связывают с именем выдающегося узбекского ученого Аль Хорезми, жившего в VIII-IX веках. По его трудам в Европе познакомились с десятичной системой счисления и правилами арифметических действий. Книга Аль Хорезми «Арифметика индусскими цифрами» произвела огромное впечатление на европейских математиков. Имя ученого в их устах превратилось в Algorithmus. Аль Хорезми первым сформулировал правила, позволяющие систематически составлять и решать квадратные уравнения.
Строгое математическое определение термина «алгоритм» принадлежит математикам А.Н.Колмогорову и А.А.Маркову. Проблемы, связанные с изучением самого понятия алгоритма, выросли в настоящее время в отдельную «теорию алгоритмов». Потребность такой теории вызвана бурным развитием вычислительной техники, а также средств автоматизированного проектирования промышленных роботов, автоматизированных линий, систем управления. Во всех случаях требуется создание алгоритмов выполнения тех или иных операций разной степени сложности.
Что же мы называем алгоритмом?
В соответствии с ГОСТ 19.004-80 «алгоритм – точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату». В литературе встречаются различные трактовки термина «алгоритм». Приведем их.
Алгоритм – система формальных правил, четко и однозначно определяющая процесс выполнения заданной работы в виде конечной последовательности действий.
Алгоритм – точный порядок действий, определяющий процесс перехода от исходных данных к искомому результату.
Алгоритм – это конечный набор правил, однозначно раскрывающих содержание и последовательность выполнения операций для систематического решения определенного класса задач за конечное число шагов.
Алгоритм – однозначно трактуемая конечная последовательность точно определенных шагов или операций, для выполнения каждой из которых требуется конечный объем оперативной памяти и конечное время, необходимое для решения задачи на ЭВМ.
Алгоритм должен обладать следующими свойствами:
- детерминированностью – однозначностью получаемого результата при одних и тех же исходных данных;
- массовостью – возможностью получения искомого результата при различных исходных данных для некоторого класса задач;
- результативностью – для любых допустимых исходных данных алгоритм должен через конечное число шагов завершить свою работу, либо подать сигнал о том, что данный алгоритм неприменим для решения поставленной задачи;
- дискретностью – возможностью разбиения определенного алгоритмического процесса на отдельные элементарные этапы, выполнение которых человеком или ЭВМ не вызывает сомнения, а результат выполнения каждого элементарного этапа определен и понятен.
Существуют различные способы описания алгоритма. Наиболее распространенными считаются следующие формы представления алгоритмов: словесная, формульно-словесная, графическая, на языках программирования.
Словесный способ описания алгоритмов отражает содержание выполняемых действий средствами естественного языка. Достоинства этого способа: общедоступность, возможность описывать алгоритм с любой степенью детализации. Недостатки: громоздкое описание, низкая наглядность.
Формульно-словесный способ описания алгоритмов основан на записи содержания выполняемых действий с использованием изобразительных возможностей языка математики, дополненного с целью указания необходимых пояснений средствами естественного языка. Данный способ более лаконичен и нагляден.
Графический способ описания алгоритмов представляет собой изображение структуры алгоритма, при котором все этапы процесса обработки данных представляются с помощью определенного набора геометрических фигур – блоков, имеющих строгую конфигурацию в соответствии с характером выполняемых действий. Такое графическое представление алгоритма называется схемой алгоритма. Составление алгоритмов осуществляется в соответствии с требованиями ГОСТ 19701-90 «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения» и ГОСТ 19.003-80 «Схемы алгоритмов и программ. Обозначения условные графические». По назначению и характеру отображаемых функций условные графические изображения делятся на основные и вспомогательные. Основные символы используются для представления операций, раскрывающих характер обработки данных в процессе решения задачи. Вспомогательные символы предназначены для пояснения отдельных элементов схемы алгоритма. Изображение схем алгоритмов осуществляется по определенным правилам. Каждая схема должна начинаться и заканчиваться символами, обозначающими начало и окончание алгоритма. Все блоки в схеме располагаются в последовательности сверху вниз и слева направо. Отдельные блоки соединяются между собой линиями потоков информации. Направление линии потока сверху вниз и справа налево принимаются за основные и стрелками не обозначаются в отличие от других направлений. Необходимым условием является один выход из символов, обозначающих обрабатывающие блоки, и двух выходов из символов, обозначающих логические операции по проверке выполнения условий.
Приведем основные условные обозначения функциональных блоков схем алгоритмов (таблица 10).
Таблица 10
Обозначения, название и функциональное назначение блоков алгоритмов
Функциональным блокам схемы алгоритма могут присваиваться порядковые номера, которые проставляются слева в верхней части символов в разрыве их контура.
Другой способ нумерации блоков заключается в следующем. Поле листа разбивают на зоны. Координаты зон по горизонтали определяются арабскими цифрами (проставляются слева направо в верхней части листа), по вертикали – прописными латинскими буквами (проставляются сверху вниз в левой части листа). Координаты зон в виде сочетаний букв и цифр присваиваются условным обозначениям блоков, размещенным в полях этих зон (рисунок 20).
Алгоритм может быть записан на одном из языков программирования. Под языком программирования понимается формальный язык, воспринимаемый ЭВМ и предназначенный для общения человека с машиной. Алгоритм, записанный на языке программирования, называется программой. В этом случае алгоритм представляется в виде последовательности операторов языка.
Выясним роль и место алгоритма при решении задач на ЭВМ.
В настоящее время принято выделять следующие этапы подготовки и решения задачи на ЭВМ:
- математическая постановка задачи – предусматривает формирование условий, ограничений и зависимостей, определяющих ее математическое описание, математическую модель. Этот этап является наиболее сложным при решении подавляющего числа задач, однако, когда уже имеются математическая постановка задачи, этот этап опускается;
- выбор численного метода определяет требования, поставленные перед разработчиком: точность решения задачи, время решения, время подготовки и т.п.;
- проектирование алгоритмов – на основании выбранного численного метода и математической постановки задачи строится детальный алгоритм решения задачи;
- составление программы.
Рисунок 20 – Координатный метод нумерации блоков
Алгоритмы бывают чрезвычайно сложными, многоступенчатыми по своей структуре и состоят из тысяч отдельных операций.
При всем многообразии алгоритмов решения задач в них можно выделить три основных (канонических) вида алгоритмических структур: линейную (следование), ветвящуюся, циклическую. С помощью этих трех видов структур можно построить алгоритм любой сложности.
Линейным называется алгоритмический процесс, при котором все этапы решения задачи выполняются в порядке следования записи этих этапов. Порядок выполнения этапов не зависит ни от исходных данных, ни от результатов выполнения предыдущих этапов.
Например, определим величину при (рисунок 21).
Рисунок 21 – Линейный вычислительный процесс и структура следование
Порядок выполнения операций в алгоритме должен отвечать принципу следования или принципу обеспеченности переменных, в основе которого лежит обеспеченность (определенность) значений переменных на каждом шаге выполнения алгоритма. Так для алгоритма на рисунке 21 перестановка блоков 3 и 4 не допустима, поскольку для вычисления z необходимо значение у.
Ветвящимся называется алгоритмический процесс, в котором выбор направления и характера обработки информации зависит от результатов проверки выполнения какого-либо логического условия. Часто такую структуру называют также структурой ЕСЛИ-ТО-ИНАЧЕ. Каждое отдельное направление обработки информации называется ветвью и ведет к общему выходу, так что работа алгоритма продолжается независимо от того, какая ветвь будет выбрана. Базовая структура ветвление приведена на рисунке 22, а. В частном случае может оказаться, что для одного из выбранных путей никаких действий выполнять не надо (рис. 22, б). Такая структура получила название обход или ЕСЛИ-ТО. Для приведения ее к общему виду можно во второй ветви поместить пустую операцию (рис. 22, в). Если в алгоритме ветвление имеет три и более направлений, то его можно представить в виде совокупности базовых структур ЕСЛИ-ТО-ИНАЧЕ (рис. 22, г).
Алгоритм, в состав которого входят только структуры следование и ветвление, называется разветвляющимся алгоритмом. Пример разветвляющегося алгоритма приведен на рисунке 20.
Циклический процесс представляет собой алгоритмическую структуру, называемую ЦИКЛ или ПОВТОРЕНИЕ, в которой многократно повторяются однотипные этапы обработки данных. Цикл – многократно повторяющийся участок алгоритма. Циклы, которые не содержат внутри себя других циклов, называются простыми. Сложные или вложенные циклы содержат внутри себя хотя бы одну циклическую структуру.
По способу организации порядка исполнения проверки условия окончания цикла различают две разновидности базовых циклических структур: с проверкой условия окончания цикла до (ЦИКЛ-ПОКА) и после (ЦИКЛ-ДО) реализации цикла (рис. 23).
Операция или группа операций, повторяющаяся в цикле, называется телом цикла. Основное отличие структуры ЦИКЛ-ПОКА от структуры ЦИКЛ-ДО заключается в том, что в первой структуре тело цикла, в зависимости от условия, могут не выполняться совсем, тогда как в структуре ЦИКЛ-ДО тело цикла обязательно выполняется хотя бы один раз.
Алгоритмы, имеющие в своем составе базовую структуру ЦИКЛ, называются циклическими алгоритмами. Пример циклического алгоритма для решения задачи построения таблицы функции
для a изменяющегося от 0° до 360° с шагом 10° с использованием структуры ЦИКЛ-ДО приведен на рис. 24, а. Величина a в этом случае называется параметром цикла.
Рисунок 22 – Базовая структура ветвление и ее модификации
Для организации цикла необходимы управляющие операции задания начального значения параметра цикла, изменения параметра цикла и проверки условия окончания цикла. На рис. 24, а к управляющим относятся операции 4, 7 и 8. Операции 5 и 6 составляют тело цикла. Следует обращать внимание, что необходимо выносить из цикла операции, результат выполнения которых не зависит от параметра цикла, поскольку это позволяет избежать ненужных повторений в цикле и тем самым экономить время работы.
Рисунок 23 — Базовая структура ЦИКЛ
а — структура ЦИКЛ-ПОКА; б — структура ЦИКЛ-ДО
Организация цикла с использованием структуры ЦИКЛ-ПОКА показана на рис. 24, б. Здесь к управляющим операциям относятся операции 4, 5 и 8, а тело цикла составляют операторы 6 и 7.
Для компактного изображения управляющих операций цикла в схемах алгоритмов используется символ модификации. Пример использования символа модификации для изображения циклических алгоритмов, показанных на рис. 24, а, б приведен на рис. 24, в.
Этот способ графического представления циклических алгоритмов применим для обеих структур ЦИКЛ-ДО и ЦИКЛ-ПОКА, однако, чаще всего, для определенности, его используют для представления структуры ЦИКЛ-ПОКА. Текст заголовка цикла, приведенного в символе модификация, может быть в достаточной степени произвольным, однако чаще всего используют следующую запись:
V = Vn, Vk [,DV],
где V — параметр цикла;
Vn — начальное значение параметра цикла;
Vk — конечное значение параметра цикла;
DV — шаг изменения параметра цикла. Если этот параметр опущен вместе с предшествующей ему запятой, шаг параметра цикла предполагается равным 1.
На практике допускаются обе формы графического представления алгоритма, выбор конкретной формы зависит от степени детализации алгоритма.
Рисунок 24 — Схемы циклических алгоритмов
а— структура ЦИКЛ-ДО; б— структура ЦИКЛ-ПОКА;
в — изображение цикла с использованием символа модификация
Основные логические ворота с таблицами истинности
В настоящее время компьютеры стали неотъемлемой частью жизни, поскольку они выполняют множество задач и операций за довольно короткий промежуток времени. Одной из наиболее важных функций ЦП в компьютере является выполнение логических операций с использованием оборудования, такого как программные технологии и электронные схемы интегральных схем. Но как это оборудование и программное обеспечение выполняют такие операции — загадочная загадка. Чтобы лучше понять такую сложную проблему, мы должны познакомиться с термином «логическая логика», разработанным Джорджем Булем.Для простой операции компьютеры используют двоичные цифры, а не цифровые. Все операции выполняются воротами базовой логики. В этой статье обсуждается обзор того, что такое базовые логические вентили в цифровой электронике и их работа.
Что такое базовые логические вентили?
Логический вентиль — это базовый строительный блок цифровой схемы, имеющей два входа и один выход. Отношения между i / p и o / p основаны на определенной логике. Эти затворы реализованы с помощью электронных ключей типа транзисторов, диодов.Но на практике базовые логические вентили строятся с использованием технологии CMOS, полевых транзисторов и полевых транзисторов MOSFET (Metal Oxide Semiconductor FET). Логические вентили используются в микропроцессорах, микроконтроллерах, встроенных системных приложениях, а также в электронных и электрических схемах проекта. Основные логические элементы делятся на семь категорий: AND, OR, XOR, NAND, NOR, XNOR и NOT. Эти логические вентили с их символами логических вентилей и таблицами истинности объясняются ниже.
Работа основных логических вентилей
Что такое 7 основных логических вентилей?
Основные логические вентили подразделяются на семь типов: вентиль И, вентиль ИЛИ, вентиль ИЛИ, вентиль И-НЕ, вентиль ИЛИ, вентиль ИЛИ-ИЛИ и вентиль НЕ.Таблица истинности используется для демонстрации функции логического элемента. Все логические элементы имеют два входа, кроме элемента НЕ, который имеет только один вход.
При построении таблицы истинности используются двоичные значения 0 и 1. Каждая возможная комбинация зависит от количества входов. Если вы не знаете о логических вентилях и их таблицах истинности и нуждаетесь в руководстве по ним, просмотрите следующую инфографику, которая дает обзор логических вентилей с их символами и таблицами истинности.
Почему мы используем базовые логические вентили?
Основные логические элементы используются для выполнения основных логических функций.Это основные строительные блоки цифровых ИС (интегральных схем). Большинство логических вентилей используют два двоичных входа и генерируют один выход, например 1 или 0. В некоторых электронных схемах используется несколько логических вентилей, тогда как в некоторых других схемах микропроцессоры включают в себя миллионы логических вентилей.
Реализация логических вентилей может осуществляться с помощью диодов, транзисторов, реле, молекул и оптики, иначе говоря, различных механических элементов. По этой причине основные логические вентили используются как электронные схемы.
Двоичные и десятичные числа
Прежде чем говорить о таблицах истинности логических вентилей, важно знать основы двоичных и десятичных чисел. Все мы знаем десятичные числа, которые мы используем в повседневных вычислениях, например, от 0 до 9. Эта система счисления включает в себя десятичную систему счисления. Таким же образом двоичные числа, такие как 0 и 1, могут использоваться для обозначения десятичных чисел, если основание двоичных чисел равно 2.
Значение использования двоичных чисел здесь состоит в том, чтобы обозначать положение переключения, в противном случае положение напряжения цифрового компонента .Здесь 1 представляет высокий сигнал или высокое напряжение, тогда как «0» указывает низкое напряжение или низкий сигнал. Таким образом, была начата булева алгебра. После этого каждый логический вентиль обсуждается отдельно, он содержит логику логического элемента, таблицу истинности и ее типичный символ.
Типы логических вентилей
Различные типы логических вентилей и символов с таблицами истинности обсуждаются ниже.
Базовые логические вентилиИ вентиль
Логический вентиль И представляет собой цифровой логический вентиль с «n» i / ps один o / p, который выполняет логическое соединение на основе комбинаций своих входов.Выход этого вентиля истинен только тогда, когда все входы истинны. Когда один или несколько входов i / ps логического элемента И являются ложными, тогда только выход логического элемента И является ложным. Таблица символов и истинности логического элемента И с двумя входами показана ниже.
Логический элемент И и его таблица истинностиЛогический элемент ИЛИ
Логический элемент ИЛИ — это цифровой логический вентиль с n i / ps и одним o / p, который выполняет логическое соединение на основе комбинаций своих входов. Выход логического элемента ИЛИ истинен только тогда, когда один или несколько входов истинны.Если все i / ps логического элемента ложны, то ложным является только выход логического элемента ИЛИ. Таблица символов и истинности логического элемента ИЛИ с двумя входами показана ниже.
Логический элемент ИЛИ и его таблица истинностиЭлемент НЕ
Элемент НЕ — это цифровой логический вентиль с одним входом и одним выходом, который управляет инверторной операцией входа. Выход логического элемента НЕ является обратным входу. Когда вход логического элемента НЕ истинен, тогда выход будет ложным, и наоборот. Таблица символов и истинности логического элемента НЕ с одним входом показана ниже.Используя этот вентиль, мы можем реализовать вентили ИЛИ и И-НЕ.
Шлюз НЕ и его таблица истинностиШлюз И-НЕ
Логический вентиль И-НЕ — это цифровой логический вентиль с ‘n’ i / ps и одним o / p, который выполняет операцию вентиль И, за которым следует вентиль НЕ. вентиль НЕ разработан путем объединения вентилей И и НЕ. Если вход логического элемента И-НЕ высокий, то выход элемента будет низким. Ниже показаны символы и таблица истинности логического элемента И-НЕ с двумя входами.
Шлюз И-НЕ и его таблица истинностиШлюз ИЛИ
Шлюз ИЛИ-НЕ — это цифровой логический вентиль с n входами и одним выходом, который выполняет операцию логического элемента ИЛИ, за которым следует вентиль НЕ.Ворота NOR спроектированы путем объединения ворот OR и NOT. Когда любой из i / ps логического элемента ИЛИ-НЕ истинен, тогда выход логического элемента ИЛИ-НЕ будет ложным. Таблица символов и истинности ворот ИЛИ-НЕ с таблицей истинности показана ниже. Логический элемент
ИЛИ и его таблица истинностиЭлемент исключающего ИЛИ
Элемент исключающего ИЛИ — это цифровой логический вентиль с двумя входами и одним выходом. Краткая форма этих ворот — Ex-OR. Он работает на основе операции логического элемента ИЛИ. . Если на каком-либо из входов этого логического элемента высокий уровень, то выход логического элемента EX-OR будет высоким.Символы и таблица истинности EX-OR показаны ниже.
Элемент EX-OR и его таблица истинностиЭлемент Exclusive-NOR
Элемент Exclusive-NOR — это цифровой логический элемент с двумя входами и одним выходом. Краткая форма этих ворот — Ex-NOR. Он работает на основе работы логического элемента ИЛИ-НЕ. Когда оба входа этого логического элемента имеют высокий уровень, тогда выход элемента ИСКЛЮЧАЮЩЕЕ НЕ будет высоким. Но если один из входов высокий (но не оба), то выход будет низким. Символы и таблица истинности EX-NOR показаны ниже.
Шлюз EX-NOR и его таблица истинностиПрименение логических вентилей в основном определяется на основе их таблицы истинности, то есть режима их работы. Базовые логические вентили используются во многих схемах, таких как кнопочный замок, охранная сигнализация со световым сигналом, предохранительный термостат, автоматическая система полива и т. Д.
Таблица истинности для экспресс-схемы логического шлюза
Схема затвора может быть выражена с помощью общий метод известен как таблица истинности. Эта таблица включает все комбинации входных логических состояний: высокий (1) или низкий (0) для каждой входной клеммы логического элемента через эквивалентный выходной логический уровень, такой как высокий или низкий.Схема логического элемента НЕ показана выше, и ее таблица истинности действительно чрезвычайно проста
Таблицы истинности логических элементов очень сложны, но больше, чем вентиль НЕ. Таблица истинности каждого гейта должна включать много строк, как будто есть возможности для эксклюзивных комбинаций для входных данных. Например, для логического элемента НЕ есть две возможности ввода: 0 или 1, тогда как для логического элемента с двумя входами есть четыре возможности, такие как 00, 01, 10 и 11. Таким образом, он включает четыре строки для эквивалентная таблица истинности.
Для логического элемента с 3 входами существует 8 возможных входов, таких как 000, 001, 010, 011, 100, 101, 110 и 111. Следовательно, требуется таблица истинности, включающая 8 строк. Математически необходимое количество строк в таблице истинности эквивалентно двум, увеличенным в степени «нет». i / p терминалов.
Анализ
Сигналы напряжения в цифровых схемах представлены двоичными значениями, такими как 0 и 1, вычисленными относительно земли. Недостаток напряжения в основном означает «0», тогда как наличие полного напряжения питания постоянного тока означает «1».
Логический вентиль — это особый тип схемы усилителя, который в основном предназначен для входных и выходных логических напряжений. Схемы логического затвора чаще всего обозначаются схематической диаграммой с помощью их собственных эксклюзивных символов вместо основных резисторов и транзисторов.
Как и в случае с операционными усилителями (операционными усилителями), соединения источника питания с логическими вентилями часто неуместны на схематических диаграммах в целях упрощения. Он включает возможные комбинации входных логических уровней через их конкретные выходные логические уровни.
Какой самый простой способ узнать логические ворота?
Ниже объясняется самый простой способ изучить функции основных логических вентилей.
- Для логического элемента И — если оба входа имеют высокий уровень, то и выход также высокий
- Для логического элемента ИЛИ — если минимум одного входа высокий, то выход высокий
- Для элемента ИСКЛЮЧАЮЩЕЕ ИЛИ — Если минимальный вход высокий, тогда высокий только выход.
- Шлюз И-НЕ — Если минимальный входной сигнал низкий, то выход высокий.
- ИЛИ вентиль — Если оба входа низкие, то выход высокий.
Теорема Де Моргана
Первая теорема ДеМоргана утверждает, что логический вентиль, такой как И-НЕ, равен вентилю ИЛИ с пузырем. Логическая функция логического элемента И-НЕ:
A’B = A ’+ B’
Вторая теорема ДеМоргана утверждает, что логический элемент ИЛИ-НЕ равен логическому элементу И с пузырьком. Логическая функция логического элемента ИЛИ-НЕ:
(A + B) ’= A’. B ’
Преобразование логического элемента И-НЕ
Логический элемент И-НЕ может быть сформирован с использованием логического элемента И и НЕ.Булево выражение и таблица истинности показаны ниже.
Формирование логических вентилей NANDY = (A⋅B) ‘