(11011000111101) ₂ =11 0110 0011 1101= 0011 0110 0011 1101=(363D) ₁₆.

1.3. Представление информации в ЭВМ.

ЭВМ оперирует с данными трёх основных типов: числами, строками символов и логическими значениями.

1.3.1. Двоичные числа.

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

Представление числа с фиксированной запятой имеет следующий формат (структуру):

(1.5)

Разряд с номером «n» является знаком числа: знак «+» кодируется цифрой 0, а знак «» - цифрой 1. Разряды от 0 до n-1 являются цифровыми. Запятая фиксируется в определённом месте относительно разрядов числа. Обычно она находится или перед старшим разрядом или после младшего. Формат числа с фиксированной запятой после младшего разряда служит для изображения целых чисел N. Число разрядов n определяет диапазон значений, которые могут быть представлены в этом формате: N[-(2ⁿ-1),+(2ⁿ-1)].

Увеличение количества цифровых разрядов n на единицу расширяет диапазон значений в два раза.

Выполнение операций над целыми числами, изображаемыми словами фиксированной длины, имеет следующие особенности. Операции сложения и вычитания определены только в том случае, если результат может быть представлен в n цифровых разрядах, т. е. если результат |C|<2ⁿ. В противном случае говорят, что результат переполняет размерную сетку ЭВМ. Если |C|2ⁿ в процессоре формируется признак переполнения, используемый для прекращения вычислений.

Формат числа с запятой, фиксированной перед старшими разрядом, используется для представления действительных чисел, принадлежащих отрезку [-(1-2^-n),+(1-2^-n)] и изменяются с шагом 2^-n. В отличие от целых, они представляются приближённо с погрешностью =2^-(n+1). Отсюда следует, что количество цифровых разрядов определяет точность представления значений числами с фиксированной запятой. С увеличением n на один дополнительный разряд погрешность  уменьшается в два раза.

Выполнение операций над действительными числами в форме с фиксированной запятой имеет следующие особенности. Операции сложения и вычитания определены в том случае, если результат может быть представлен в форме с фиксированной запятой, т.е. если результат |C|<1. В противном случае фиксируется переполнение. Деление А/B возможно, если B0 и |A|<|B|.

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

Z=Md^P (1.6)

где d – основание чисел с плавающей запятой.

P – целое число, называемое порядком числа Z;

M – мантисса числа Z.

Как видно из (1.6) число представляет собой произведение мантиссы и экспоненты по основанию d, поэтому такое представление называют также экспоненциальным.

Обычно d=2^r, r=1,2,… В качестве основания d чаще всего используется значение 2 или 16. Мантисса числа с плавающей запятой всегда меньше единицы, и если выполняется условие:

, (1.7)

то такое число называется нормализованным. В противном случае число называется ненормализованным.

Число с плавающей запятой имеет следующий формат:

(1.8)

Разряд m+p+1 слова представляет знак числа, который одновременно является знаком мантиссы. Мантисса М представляется m – разрядным числом с фиксированной запятой. Знак порядка кодируется «m+p» - ым разрядом слова. Порядок Р является целым числом и занимает р разрядов с m по m+p+1. У нормализованных чисел r старших разрядов мантиссы не равны нулю.

В ЭВМ знак порядка и порядок представляются одним (р+1) – разрядным целым значением Х, называемым характеристикой числа с плавающей запятой, которая связана с порядком соотношением:

X=2^P+P, (1.9)

С учётом этого порядок определяется по значению характеристики Х следующим образом:

P=2^P-X, (1.10)

где 0X2^P+1-1

Как следует из (1.9) и (1.10), значение характеристики 0,1,2,…,2^P используются для представления порядков –2^P,-(2^P-1),-(2^P-2),…,0 соответственно, а значения характеристики 2^P+1, 2^P+2,…,2^P+(2^P-1) – значения для представления порядков 0,1,2,…,2^P–1. При этом нулевое значение старшего разряда характеристики соответствует знаку порядку минус, а единичное значение – знаку плюс. Таким образом, характеристика – это дополнительный код порядка с инверсным представлением знака. Использование характеристики несколько упрощает алгоритм операций над числами с плавающей запятой.

Учитывая, что и , и , получим, что нормализованные числа с плавающей запятой обеспечивают представление значений в диапазоне

(1.11)

с предельной относительной погрешностью

(1.12)

так как 2^-m<<1, выражение (1.11) преобразуется к виду

, (1.13)

или переходя к десятичному основанию,

(1.14)

За счёт ненормализованных чисел диапазон значений Z расширяется слева на . В этой области значения представляются с предельной относительной погрешностью, лежащий в интервале Из (1.13) и (1.14) видно, что диапазон определяется величиной основания и порядком, а точность представления чисел количеством разрядов мантисс. Увеличение основания d приводит к существенному расширению диапазона значений, а погрешность при этом увеличивается незначительно. По этой причине в ЭВМ общего назначения, к которым принадлежат ЕС ЭВМ, IBM 360/370, использовалось основание 16.

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

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

2. Исчезновение порядка происходит, когда порядок результата должен иметь значение, меньшее –2^P – максимального по модулю отрицательного порядка. В таком случае результат приходиться представлять машинным нулём.

3. Переполнение порядка возникает, когда порядок результата должен иметь значение, превосходящее максимально возможное (2^Р-1). Такое значение не может быть представлено в формате (1.8), поэтому результат операции считается неопределённым, что отличается выработкой признака переполнения.

4. Деление на нуль, которое невозможно, что отличается выработкой признака переполнения.

В современных ЭВМ используются целые числа и числа с плавающей запятой. Целые числа представляются в формате с фиксированной запятой (1.5), расположенной после младшего разряда. Используется представление целых чисел со знаком и без знака. Для примера рассмотрим представление целых чисел в персональных ЭВМ IBM PC.

Для представления действительных чисел с различной точностью используются несколько форматов чисел с плавающей запятой. В персональных ЭВМ IBM PC используются следующие форматы:

1.3.2. Кодирование десятичных чисел и алфавитно-цифровой информации.

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

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

Совокупность всех символов, используемых в вычислительной системе, представляет собой её алфавит. Символу соответствует машинная единица информации слог. Так называют группу двоичных разрядов, служащую для представления символа в машине (двоичный код символа). Если группа включает k разрядов, то с её помощью можно кодировать 2^k символов.

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

Для представления алфавитно-цифровой информации в ЭВМ используются различные стандарты двоичных кодов обмена информацией. Так в ЕС ЭВМ использовались восьмибитные коды для обмена и обработки информации КОИ-8, ДКОИ, в вычислительных системах IBM 360 и 370 восьми битный код EBCDIC (Extended Binary Coded Decimal Interchange Code) – расширенный двоично-кодированный десятичный код для обмена информацией. Каждый из переменных стандартов позволяет кодировать до 256 различных символов.

В мини ЭВМ, микро ЭВМ и персональных ЭВМ используются коды обмена информацией, ядром которых является семибитный код ASCII (American National Standard Code for Information Interchange) – Американский национальный стандартный код для обмена информацией. Этот код позволяет кодировать 128 различных символов включающие прописные и строчные буквы латинского алфавита. Добавление восьмого разряда к коду ASCII позволяет кодировать национальные алфавиты и символы псевдографики. ASCII код символа соответствует нулевому значению этого дополнительного разряда.

Например, в коде EBCDIC букве А соответствует код (С1)₁₆, B – (C2)₁₆, S – (E2)₁₆. В ASCII коде латинские буквы от A до Z последовательными двоичными кодами от (41)₁₆ до (5А)₁₆.

Для представления текстовой информации используются строки символов. Строки символов изображаются в ЭВМ полем переменной длины. Так в ЕС ЭВМ длина поля может изменяться от 1 до 256 байт. В систему команд ЭВМ вводятся специальные команды для обработки строк символов.

В ЭВМ, поддерживаются десятичную арифметику, десятичные числа представляются либо в распакованном (зонном) формате, либо в упакованном формате. При представлении чисел в распакованном формате каждая цифра записывается в виде байта, значение которого определяется применяемым кодом обмена информации. Так в коде EBCDIC цифры 0,1,2,…,9 изображаются байтами (F0)₁₆, (F1)₁₆, (F2)₁₆,…, (F9)₁₆. Старшие четыре разряда заполняются единицами: (1111)₂=(F)₁₆. Они образуют зонную часть представления, поэтому распакованный формат называют зонным. Младшие четыре разряда образуют двоичное значение цифры в BCD – формате с весами 8421:

00000, 10001, 20010, 30011, 40100, 50101, 60110, 70111, 81000, 91001/

Для эффективного использования памяти, уменьшения длин программ и времени решения задач десятичные данные необходимо представлять последовательностями из любого числа цифр – полями переменной длины, которые могут содержать 1,2,… цифр. Так в ЕС ЭВМ десятичные числа представляются полями переменной длины от 1 до 16 байтов.

Пример 1.10.

Изображения чисел в зонном формате для ЕС ЭВМ:

1. Число 457 в данном формате в поле, длинной три байта, имеет вид:

1. Число – 5678 в зонном формате в поле, длиной четыре байта, имеет вид:

Как видно из примеров в зонной части младшей цифры записывается знак числа: С ( или F) для знака «+», и D для знака «-».

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

Пример 1.11.

Число 457 в упакованной форме занимает поле длиной два байта:

Число – 5678 в упакованном формате занимает 3 байта:

При использовании ASCII кода каждая цифра в распакованном формате представляется байтами, старшая тетрада которых имеет значение (0011)²=(3)¹⁶: 0(30)¹⁶, 1(31)¹⁶, 2(32)¹⁶, 3(33)¹⁶, 4(34)¹⁶, 5(35)¹⁶, 6(36)¹⁶, 7(37)¹⁶, 8(38)¹⁶, 9(39)¹⁶.

1.3.3. Логические значения.

Переменные, принимающие одно из двух значений «ложь» (FALSE) или «истина» (TRUE), называются булевыми (логическими) переменными. Значения «ложь» и «истина» принято кодировать цифрами 0 и 1 соответственно. Операции над логическими переменными как объектами определены в языках программирования. В этом случае под их значения отводится группа битов (байт или машинное слово). Наличие хотя бы одного единичного байта в группе определяет истинное значение, а все нули – ложное.

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

1.4. Машинные коды.

Двоичные числа в ЭВМ представляются машинными кодами определённой разрядности. Предположим, что число разрядов слова равно m тогда двоичный код числа X в этой разрядности запишется следующим образом:

X=X_m-1X_m-2X_m-3…X₁X₀ (1.15)

Здесь X_m-1 – знаковый разряд числа

1.4.1. Прямой код.

Прямой код числа X определяется следующим образом:

(1.16)

Из (1.16) следует, что ноль имеет два представления:

Пример 1.12.

Представить в прямом коде двоичные числа (+1000010)₂ и (-1000010)₂:

а) [+1000010]_пр=0 1000010

б) [-1000010]_пр=1 1000010

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

1.4.2. Дополнительный код.

Дополнительный код числа X определяется следующим образом:

(1.18)

Пример 1.13.

Представить в дополнительных кодах двоичные числа (+1000010)₂ и (-1000010)₂:

а) [+1000010]_доп=0 1000010

б) [-1000010]_доп=2⁸-1000010=10 0000000-1000010=1 0111110

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

Ноль в дополнительном коде имеет единственное представление:

[+0]_доп=[-0]_доп=[0]_доп=

К
ак следует из (1.18) дополнительный код осуществляет отображение отрицательных чисел на область положительных чисел (рис. 1.1)

1.4.3. Обратный код числа.

Обратный код числа X определяется следующим образом:

(1.19)

Пример 1.14.

Представить в обратном коде двоичные числа (+1000010)₂ и (-1000010)₂

а) [+1000010]_обр=0 1000010

б) [-1000010]_обр=2⁸-1000010-1=10 0000000-1000010-1=1 0111101

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

Ноль в обратном коде имеет два представления:

К
ак следует из (1.19) обратный код, также как и дополнительный, осуществляет отображение отрицательных чисел на область положительных чисел (Рис. 1.2.).

На основании (1.19) можно установить связь между обратным и дополнительным кодом,

[X]_обр=[X]_доп-1, X0 (1.20)

откуда можно получить другое правило образования дополнительного кода,

[X]_доп=[X]_обр+1. (1.21)

Это правило используется в ЭВМ при переходе к дополнительному коду числа.

1.4.4. Выполнение арифметических действий с кодами.

Обратный и дополнительный код чисел обладают свойством линейности относительно операций сложения и вычитания

[X+Y]=[X]+[Y]

[X-Y]=[X]+[-Y] (1.22)

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

Пример 1.15.

Сложить двоичные числа (+1001001)₂ и (-110010)₂

а )

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

1.4.5. Признаки переполнения разрядной сетки.

Рассмотрим следующий пример.

Пример 1.16.

Сложим следующие числа:

а) (+1000010)₂ и (+1001001)₂,

б) (-1000010)₂ и (-1001001)₂,

используя дополнительные коды:

а) ; б)

При сложении положительных чисел (случай «а») получим отрицательный результат, а при сложении отрицательных чисел – положительный (случай «б»). Это явление говорит о переполнении разрядной сетки ЭВМ, поскольку результат не помещается в выбранную разрядную сетку машины. Факт переполнения легко устанавливается при использовании модифицированных дополнительного и обратного кодов. В этих кодах знак «+» кодируется двумя нулями 00, а знак «-» двумя единицами 11. Сложим двоичные числа из предыдущего примера, воспользовавшись дополнительным кодом:

а) ; б)

Сочетания 01 и 10 в знаковых разрядах говорит о переполнении разрядной сетки: 01 в области положительных чисел, 10 в области отрицательных чисел. При сложении чисел с фиксированной запятой результат не может быть скорректирован. Если переполнение возникло при сложении мантисс, результат может быть исправлен.

Пример 1.17.

Представим числа (+1000010)₂ и (+1001001)₂ в форме с плавающей запятой:

+1000010=+0,1000010*10¹¹¹

+1001001=+0,1001001*10¹¹¹ (10-двоичное основание)

Складывая мантиссы в дополнительном коде получим:

.

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

В результате получили число с плавающей запятой 0,1000101*10¹⁰⁰⁰. Поскольку при сдвиге младший разряд выходит за разрядную сетку, то в зависимости от способа округления, результат получается приближенным с недостатком или с избытком.

2. Синтез комбинационных устройств.

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

2.1 Логические переменные и функции.

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

Физическая природа.

Физическая природа этих сигналов может быть самой разнообразной: наличие или отсутствие импульса в определенной позиции, наличие или отсутствие тока, высокий и низкий потенциал, значение фазы φ: φ = 0 и φ = π состояние положительной и отрицательной намагниченности и т.д.

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

уровни	полож. лог.	отриц. лог.
Umax	1	0
Umin	0	1

Уровни напряжений потенциальной логики для микросхем различных серий представлены в таблице:

	КМОП	ТТЛ	Эм. Связн. Лог.
+Umax	8 в	>2.3 в	-0.7 в
- Umin	<0.5 в	от 0 до 0.3 в	-1.9 в

Будем обозначать переменные латинскими буквами (строчными, прописными, с индексами или без них)

A a, B b, C c …

X₁ , X₂ , X₃ …

Логическая функция - это функция логических переменных, принимающая только два значения. Совокупность значений двоичных переменных, называется набором. Максимальное число наборов функций n переменных равно 2ⁿ. Если переменную считать определённым разрядом двоичного позиционного кода, каждому набору можно поставить в соответствие двоичное число, которое в десятичном представлении определяет номер набора.

Пример 2.1.

Для функций трёх переменных (n=3) существует 2³ = 8 наборов:

c b a № набора (десятичное число)

0

1

2

3

4

5

6

7

Здесь переменная «а» образует младший разряд двоичного числа.

Общее число функций n-переменных – 2²ⁿ . Если функция определена на всех своих 2ⁿ наборах, то она называется полностью определённой, в противном случае – не полностью определённой. Наборы, на которых функция не определена, называются запрещёнными. Значения переменных, соответствующие этим наборам, не должны появляться на входе схемы.

2.2 Элементарные функции.

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

2.2.1 Функции одной переменной.

n=1 - количество переменных; 2¹ =2 - количество наборов; 2² =4 – число функций;

X	F1	F2	F3	F4
0	0	0	1	1
1	0	1	0	1

F ₁0; - константа нуль в положительной логике это «земля»; «0»

F₂=X; - функция повторения, реализуется на элементе повторения;

Элемент повторения.

1

X F₂(X)=X

_

F₃=X; - функция отрицания (инверсия), реализуется на элементе «НЕ»;

Элемент «НЕ».

1

_

X F₃(X)=X;

F₄1; константа единица;

+Е R «1»

2.2.2 Функции двух переменных.

n=2 –количество переменных; 2² =4 –количество наборов; 2⁴ =16 –число функций;

X1	X2	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13	F14	F15	F16
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
		0	X1 X2	_______ X1  X2	X1	_______ X1  X2	X2	X2	X1 X2	X1 X2	X2  X1	__ X2	X1  X2	__ X1	X1  X2	X1 | X2	1
								
								X1

Из перечисленных функций шесть (F₁, F₄, F₆, F₁₁, F₁₃, F₁₆) являются ранее рассмотренными функциями одной переменной, и только десять функций по существу являются функциями двух переменных.

F₂= X₁ X₂= X₁ X₂= X₁ X₂ -конъюнкция, функция «и», логическое умножение, реализуется на элементе «И»

Элемент «И».



X₁

F(X₁, X₂)= X₁ X₂

X₂

F₈= X₁ X₂= X₁+X₂ -дизъюнкция, функция «ИЛИ», логическое сложение, реализуется на элементе «ИЛИ»

Элемент «ИЛИ».

1

X₁

X₂ F(X₁, X₂)= X₁X₂

_____

F₁₅= X₁/ X₂= X₁ X₂ -штрих Шеффера, реализуется на элементе «И-НЕ»

Элемент «И-НЕ».

&

X₁

F(X₁, X₂)= X₁/X₂

X₂

_____

F₉= X₁ X₂= X₁ X₂ -стрелка Пирса, реализуется на элементе «ИЛИ-НЕ»

Элемент «ИЛИ-НЕ».

1

X₁

F (X₁, X₂)= X₁ X₂

X₂

__________

F7=X1

ς

X2= X1 mod2 X2

-функция сложения по модулю два, функция «исключающее ИЛИ»,

функция отрицания равнозначности, реализуется на элементе «исключающее ИЛИ»

Элемент «исключающее ИЛИ».

=1

X₁

F(X₁, X₂)= X₁ mod2 X₂

X₂

________

F10=X1

ς

X2= X1 mod2 X2

-функция равнозначности, отрицание функции сложения по модулю два.

F₁₄=X₁  X₂ -функция импликации, прямая импликация, «ЕСЛИ…ТО…»

______

F₃=X₁  X₂ -отрицание прямой импликации;

F₁₂=X₂  X₁ -обратная импликация;

______

F₅=X₂  X₁ -отрицание обратной импликации.

Для функций F₁₀, F₁₄, F₁₂, F₅, F₃ не существует отдельных логических элементов, но они могут быть реализованы на других элементах.

2.3 Функции многих переменных.

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

Примеры (2.2.) базисов:

1. ¬,  -дизъюнктивный базис;

2. ¬,  -конъюнктивный;

3. ¬, ,  -Булевский базис (смешанный);

4. / -штрих Шеффера;

5. ↓ -стрелка Пирса;

6. /, «1»;

7. ↓, «0»;

8. →, «0»;

9. →, «1»;

10. →, mod2;

11. &, mod2 –базис Жегалкина.

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

Основные законы Булевского базиса:

1) закон идемпотентности

аа=а; аа=а;

2) коммутативный (переместительный) закон

ав=ва; ав= ва;

3) ассоциативный (сочетательный) закон

а(вс)=(ав)с; а(вс)=(ав) с;

4) дистрибутивный (распределительный) закон

а(вс)= (ав) (ас); а (вс)= (ав)  (ас);

5) закон двойного отрицания

_

ā =а;

6) законы двойственности (правила де Моргана)

_ _ __ _ _ ____

а + в= ав; а в = а + в;

Его можно распространить на любое число переменных n:

7) закон склеивания

_

а в + а в =а; (склейка по в)

_

(a + в) (a + в) =а;

8) закон поглощения

а + а в= а; а(а + в)=а.

Действия с константами «0» и «1»:

_

а + 0=а; а + 1=1; а + а =1;

_

а 0 =0; а 1=а; а а =0.

Правило введения и исключения лишних связок:

_ _

F₁X+ F₂X= F₁X+ F₂X+ F₁ F₂;

_ _

(F₁+X) (F₂+X)= (F₁+X) (F₂+X) (F₁+ F₂).

2.4. Задание функции комбинационных логических схем.

Функция может быть задана:

1) таблицей истинности.

Таблица истинности (рис 2.1.) перечисляет все наборы значений двоичных переменных и содержит строк, где n – число переменных. Для каждого набора указывается значение функции.

Если функция на наборе не определена, то в столбце значений функции используется “-“ (прочерк).

Если определить старшинство переменных, то каждому набору можно присвоить номер указываемый в столбце номеров N.

2
) номерами наборов, например, F=1 на наборах {2,3,6}.

3) задание в виде формулы алгебры логики.

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

Выражение вычисляется слева на право в соответствии со старшинством операций .

4) топологические способы задания функции в виде графов или диаграмм (карт) Карно, в виде n - мерных кубов.

2.4.1. Нормальные формы записи булевых функций.

Любая функция алгебры логики может быть представлена в дизъюнктивной нормальной форме (ДНФ) или конъюнктивной нормальной форме (КНФ).

ДНФ – дизъюнкция элементарных конъюнкций.

Элементарная конъюнкция – это конъюнкция переменных функций и их отрицаний. Она не может включать переменную и её отрицание одновременно.

Пример 2.3.

Следующие выражения являются элементарными конъюнкциями.

Дизъюнкция элементарных конъюнкций: - ДНФ.

КНФ – конъюнкция элементарных дизъюнкций.

Элементарная дизъюнкция – это дизъюнкция переменных функций и их отрицаний. Она не может включать переменную и её отрицание одновременно.

Пример 2.4.

Следующие выражения являются элементарными дизъюнкциями.

Конъюнкция элементарных дизъюнкций: - КНФ.

Одна и та же функция может иметь несколько ДНФ или КНФ.

2.4.2. Совершенные нормальные формы.

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

Конституентой нуля называют элементарную дизъюнкцию всех переменных функций, иначе её называют дизъюнктивной конституентой, или макситермом.

Конституента единицы принимает единственное значение тогда и только тогда, когда все буквы принимают единичное значение (буква – сама переменная или её отрицание ).

abc=1 только на том наборе, где a=1, b=1, c=1, N=7 (см. рис. 1)

только на том наборе, где , N=5.

Конституента нуля принимает нулевое значение только на одном наборе, на котором все буквы равны нулю.

Конституента нуля равна 0 на наборе , а конституента нуля равна 0 на наборе

На основе конституент 1(0) строятся совершенные нормальные формы (СНФ)

Дизъюнкция конституент 1 носит название совершенной дизъюнктивной нормальной формой (СДНФ).

Пример 2.5.

Конъюнкция конституент 0 носит название совершенной конъюнктивной нормальной формой (СКНФ).

Пример 2.6.

СДНФ и СКНФ строится по соответствующей таблице истинности. СДНФ представляет собой дизъюнкцию всех конституент единицы, соответствующих тем наборам, на которых функция принимает значение единицы. СКНФ определяется по таблице истинности следующим образом. При этом переменная, имеющая в наборе значение ноль, входит в конституенту единицы с отрицанием, а имеющая значение единицы – без отрицания. СКНФ представляет собой конъюнкцию всех конституент 0, соответствующих тем наборам, на которых функция равна 0. При этом переменной, имеющей в наборе значение 0, в конституенте соответствует сама переменная, а переменной имеющей значение 1, соответствует отрицание переменной.

Пример 2.7.

Ф
ункции, заданной таблицей истинности (рис. 2.2), соответствует СДНФ.

Функции, заданной этой же таблицей истинности, соответствует СКНФ.

Представление в виде СДНФ или СКНФ для функции является единственным.

Свойства СНФ.

I. 1. Дизъюнкция всех конституент 1 равна единице

.

2. Конъюнкция всех конституент 0 равна нулю

.

II. 1. Дизъюнкция каких-то k конституент единицы равна отрицанию дизъюнкций оставшихся конституент единицы.

2. Конъюнкция каких-то k конституент нуля равна отрицанию конъюнкций оставшихся конституент нуля

Пример 2.8.

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

2.5. Задача минимизации булевых функций.

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

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

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

Канонический метод синтеза логических схем заключается в следующем.

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

Функции считаются эквивалентными, если они имеют одну и ту же таблицу истинности. Наиболее разработаны методы минимизации функции, выраженных в ДНФ или КНФ.

О
бычно задача оптимального синтеза решается в два этапа. На первом этапе упрощается ДНФ и КНФ функции. На втором этапе производится дальнейшее упрощение функции путём построения скобочных форм. Окончательные формы функций используется для построения проектируемой схемы. Оптимизация схем в других базисах осуществляется через преобразование системы функций в булевский базис.

При использовании многовходовых логических элементов схема может быть получена на основе ДНФ или КНФ функции. В этом случае ( без учёта инверсий входных переменных) она получается двухуровневой. Например, функция реализуется схемой на рис. 2.3.

Количество входов элементов первого уровня, т.е. количество входов схемы, равно числу букв в записи функции, количество входов элемента второго уровня равно числу элементарных конъюнкций для ДНФ (элементарных дизъюнкций для КНФ) в записи функции:

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

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

С
хема имеет на элемент меньше, чем схема реализованная по нормальной форме, но обладает меньшим быстродействием, поскольку содержит большее число ступеней. Для получения максимального быстродействия следует использовать МДНФ (МКНФ) функций.

Таким образом, задача минимизации сводится к получению минимальных нормальных форм (МДНФ или МКНФ).

2.6. Минимизация нормальных форм булевых функций.

Существуют следующие методы минимизации:

1. Ручные методы минимизации.

2. Машинные методы минимизации.

Ручные методы минимизации используют, если число переменных не больше 7.

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

Ручные методы минимизации делятся на:

1. Аналитические;

2. Топологические.

Аналитические методы минимизации основаны на законах булевской алгебры.

Особую роль играют законы склеивания, поглощения, введения и исключения лишних связок.

минимальная форма

С использованием правила введения и исключения лишних связок нет необходимости в переходе к совершенным формам:

.

2.7 Минимизация с помощью диаграмм Карно.

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

- дизъюнктивную диаграмму Карно (ДДК). В ней записывают единичные значения функции;

- конъюнктивную диаграмму Карно (КДК), В ней записывают нулевые значения функции.

В
пределах одной и той же таблицы нельзя использовать 1 и 0 одновременно.

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

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

Н
а рисунке 2.9. приведена диаграмма Карно для n=5, при построении которой использовалось выше приведённое правило.

2.8 Топологическая интерпретация правил минимизации.

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

С межные или соседние единицы могут быть объединены в одну группу, причём число единиц в группе равно , например для рис. 2.11. эта группа состоит из четырёх единиц и её соответствует конъюнкция db.

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

Правила минимизации:

1. Объединяем единицы (нули) в группы, число которых в группе равно , причём k=0…n, где n – число переменных, каждой группе соответствует конъюнкция n-k переменных. Исключаются k переменных, относительно осей которых выполняется правило симметрии.

2. В объединение включается как можно большее число единиц и нулей.

3. Одни и те же единицы (нули) могут входить в разные объединения.

4. Минимизация начинается с тех единиц (нулей) которые образуют единственно возможные максимальные объединения.

5. Объединения должны покрывать все единицы (нули) функции.

Пример 2.9.

n=4

;

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

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

;

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

Минимизация систем логических функций.

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

2.9. Построение комбинационных схем на реальной элементной базе.

При проектировании комбинационных схем необходимо учитывать основные характеристики логических элементов:

1) Коэффициент объединения по выходу (коэффициент разветвления).

2) Коэффициент объединения по входу.

3) Быстродействие.

1) Коэффициент объединения по выходу.

К
оэффициент разветвления задает максимальное количество входов логических элементов, которые могут быть соединены с выходом данного элемента (см. рис. 2.16):

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

1. Используются элементы с повышенным значением коэффициента разветвления.

2
. Используют метод дублирования и размножения (см. рис.2.17.):

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

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

2) Коэффициент объединения по входу.

К
оэффициентом объединения по входу называют количество выходов элементов, соединённых с входами данного элемента. Таким образом, он совпадает с числом входов данного элемента, как показано на рис. 2.20.

Число входов элементов ограничено. Например, для микросхем ТТЛ- серий число входов:

- на элементе «И» не больше четырех;

- на элементе «ИЛИ» не больше двух;

- на элементе «И-НЕ» от двух до восьми;

- на элементе «ИЛИ-НЕ» от двух до пяти.

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

_ _ _

a b c + d b + d c = a ( b c ) + d ( b + c );

_ _ _ _

a b c + d b + e c = a ( b c ) + ( d b + e c ).

3) Быстродействие.

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

Пример 2.10.

_

F(a,b,c) = a b + a c; Временные диаграммы:

Реализация данной функции: b, c

t

a

&

τ₃₁

α1 t

b

1

f τ₃₁ t

t

_ τ₃₁

a

&

τ₃₂

t

α2 f

c t

ложное значение

где τ₃₁ и τ₃₂ время задержки на первом и втором элементе, причём τ₃₁ < τ₃₂ . При переходе от набора = к набору из-за разных задержек в элементах, на выходе возникает ложное значение f(a,b,c)=0 вместо f=1.

Неодновременные изменения выходных сигналов логических элементов при одновременном изменении сигналов на их входах называется состязаниями логических элементов. Состязания называются критическими, если они приводят к появлению ложных значений выходных сигналов, и не критическими – в противном случае. Для борьбы с состязаниями, необходимо в диаграммах Карно склеивать все соседние единицы. Например, если для выше приведённых функций добавить конъюнкцию bc , выполнив операцию склеивания всех соседних единиц (смотри диаграмму Карно функции на рис. 2.21.), то ложный сигнал f=0 на выходе исчезнет. Таким образом, реализация F= a b + c + b c; позволяет устранить критические состязания, происходящие из-за изменения переменной а.

F b

	1	1
a(		1	1

с

Рис. 2.21.

2.9.1 Порядок синтеза комбинационных схем.

1. Формулировка задания на проектирование комбинационной схемы.

2. Построение таблиц истинности.

3. Получение совершенных нормальных форм (СНФ): совершенной дизъюнктивной нормальной формы (СДНФ) и совершенной конъюнктивной нормальной формы (СКНФ).

4. Получение минимальных нормальных форм: минимальной нормальной дизъюнктивной формы (МДНФ) и минимальной конъюнктивной нормальной формы (МКНФ).

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

В случае необходимости следует:

а) учесть нагрузочную способность;

б) получить скобочную форму, учитывающую ограничения на число входов;

в) получить выражения, свободные от логических состязаний;

г) получить выражения в базисе выбранных логических элементов, например, преобразовать МДНФ или МКНФ в штрих Шеффера или стрелку Пирса, при использовании элементов «И-НЕ», «ИЛИ-НЕ»;

д) система функций должна реализовываться совместно.

2.9.2 Элементы «И», «ИЛИ», «НЕ».

Элемент «И» Элемент «ИЛИ» Элемент «НЕ»

1

1



Функции «И», «ИЛИ», «НЕ» образуют расширенный булевский базис, поэтому выражения для МДНФ или МКНФ могут использоваться сразу для построения схем. В случае отсутствия элементов с нужным числом входов, может потребоваться преобразование МДНФ или МКНФ к скобочному виду.

2.9.3 Элементы «И-НЕ», «ИЛИ-НЕ».

Элемент «И-НЕ» Элемент «ИЛИ-НЕ»

a

&

1

a F= a↓ b

F=a/b

b b

Запишем основные соотношения для штриха Шеффера и стрелки Пирса:

__ _ _

a / b = a b = a + b;

___ _ _

a↓ b = a v b = a b

Штрих Шеффера и стрелка Пирса функционально полны, поскольку:

___ _ _

a b = a / b = a ↓ b;

_ _ ___

a + b = a / b = a ↓ b.

_ __

a = a a = a / a.

&

_

a

a

_ __

a = a 1 = a / 1

&

a _

+ E a

_ ___

a = a + a = a ↓ a

1

_

a

a

_ ____

a = a + 0 = a ↓ 0

a _

a

Штрих Шеффера и стрелка Пирса не являются ассоциативными операциями, то есть:

a / (b / c) a / b / c (a / b) /c;

a ↓ (b ↓ c) a ↓ b ↓ c (a ↓ b) ↓ c.

При реализации функций на элементах «И-НЕ», «ИЛИ-НЕ» после получения минимальных форм МДНФ и МКНФ, их необходимо представить в базисе «штрих Шеффера» и «стрелка Пирса».

Пример 2.11.

Преобразование функции в «штрих Шеффера»:

;

в «стрелку Пирса»:

Общее отрицание на элементе «ИЛИ-НЕ» может быть реализовано одним из вышеприведённых методов,

или

.

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

Пример 2.12.

Преобразование функции в «штрих Шеффера»:

в «стрелку Пирса»:

При ограничении на число входов необходимо предварительно получить скобочную форму.

Пример 2.13.

Реализовать на двухвходовых элементах «И-НЕ»

Схема, реализующая эту функцию, изображена на рис. 2.22.

рис. 2.22.

2.9.4. Элементы И-ИЛИ-НЕ.

В
число элементов микросхем различных серий входят элементы И-ИЛИ-НЕ (рис. 2.23):

а) элемент 2-3-2-3И-4ИЛИ-НЕ без дополнительных выходов для подключения расширителей по И; б) элемент 4-4И-2ИЛИ-НЕ с дополнительными выходами; в) расширитель по И ТТЛ серии. Они могут иметь входы для получения дополнительных схем И (расширитель по И).

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

Пример 2.14.

На элементах 2-2И-2ИЛИ-НЕ реализовать функцию F, заданную диаграммой Карно:

Решение:

1. Получим МДНФ отрицания функции F.

1. Реализуем всё, что можно реализовать на данном элементе.

1. Реализуем на выбранном элементе функцию , повторив шаги 1 и 2.

Окончательно получим схему для реализации функции F.

Сформируем общий порядок синтеза схем на элементах И-ИЛИ-НЕ с учётом ограничений на число входов элементов.

1. Получить ДНФ отрицания исходной функции F.

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

3. Повторять шаги 1 и 2 до тех пор, пока не реализуем всю функцию на заданных интегральных микросхемах.

2.10. Цифровые устройства на программируемых БИС с матричной структурой.

2.10.1. Матричная реализация булевых функций.

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

Р
ассмотрим матрицу М₁ (Рис. 2.24.), в которой ЭОП является диод:

Такая матрица по каждому из своих выходов р₁,р₂,р₃,р₄,р₅ реализует конъюнкцию входных переменных х₁,х₂,х₃,х₄:

Рассмотрим матрицу М₂ (Рис. 2.25.), в которой ЭОП является биполярным транзистором.

Такая матрица по каждому из своих выходов у₁, у₂, у₃ реализует функции «ИЛИ» входных переменных p₁, р₂, р₃, р₄, p₅.

С
оединяя матрицы М1 и М2 так, как показано на рис. 2.26. можно реализовать на выходах у₁, у₂, у₃ полученной структуры следующие ДНФ входных переменных х₁, х₂, х₃, х₄:

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

По способу настройки (программированию) различают матрицы настраиваемые (программируемые) 1) на заводе изготовителе, 2) пользователем и 3) репрограммируемые (многократно настраиваемые).

Матрица первого типа называется масочными (М-типа), второго типа – программируемыми (П-типа) и третьего типа – репрограммируемыми (Р-типа).

В М-матрицах соединение ЭОП с шинами осуществляется на заводе изготовителе один раз с помощью специальных масок, используемых для металлизации определённых участков БИС. После изготовления БИС полученные соединения не могут быть изменены. БИС М–типа дороги, так как стоимость масок - шаблонов очень высока.

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

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

Сложность реализации булевых функций принято оценивать суммарной информационной ёмкостью (площадью) матриц S(M):

S(M)=S(M₁)+S(M₂)=2*s*q+q*t, где s – число входов матрицы М₁, q – число выходов матрицы М₁ (число вертикалей, промежуточных шин), t – число выходов матрицы М₂ и структуры в целом.

Для лучшего использования ёмкости при реализации булевых функций необходимо представлять их в минимальной ДНФ. Для нашего случая информационная ёмкость равна: S(M)=2*4*5+5*3=55.

2.10.2. Программируемые логические матрицы (ПЛМ).

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

Среди ПЛМ первого типа наибольшее распространение получили двухуровневые (Рис. 2.27.), которые состоят из двух матриц М₁ и М₂. Они образуют соответственно первый и второй уровни схемы. Условное обозначение структура представлена на рис. 2.27. б.

М
атрица М₁, реализует q элементарных конъюнкций р₁, р₂, р₃ … ,р_q переменных х₁, х₂ …, х_s. Матрица М₂ позволяет реализовать t элементарных дизъюнкций у₁, у₂, у₃, … у_t переменных р₁, р₂, … р_q, поступающих на её входы с выходов матрицы М₂. Выводы матрицы М₁, соединённые со входами матрицы М₂, образуют промежуточные шины ПЛМ. ПЛМ с s входами, t выходами и q промежуточными шинами называются ПЛМ(s,t,q). К выходам матрицы М₂ может подключаться слой программируемых инверторов, которой условимся не выделять в отдельный третий уровень. Аналогичные инверторы иногда включаются между матрицами М₁ и М₂.

Разновидности ПЛМ(s, t, q) направлены на эффективное использование их информационной ёмкости: расширение числа реализуемых функций при заданной площади или сокращение площади при ограничениях на количество реализуемых функций. К ним относятся матрицы ПЛМ (z, q). В ПЛМ (z, q) фиксируется лишь два параметра: число промежуточных шин q и суммарное число входов и выходов z=s+t. Конкретные значения s и t могут выбираться произвольно при настройке ПЛМ(z, q). Например, ПЛМ(6,10) путём соответствующей настройки может быть использована как ПЛМ(3, 3, 10), ПЛМ (5, 1, 10) и т. д.

Трёхуровневые ПЛМ комбинационного типа (рис. 2.28.) в отличие от двухуровневых содержит дополнительный s-входовой блок D.

Число выходов блока D равно числу h горизонтальных шин в матрице М₁. Блок D может иметь самую различную внутреннюю структуру, но наиболее часто он состоит из s/2 двухвходовых полных дешифраторов. Они реализуют все конституенты единицы от двух переменных.

Такие ПЛМ называются ПЛМD(s, t, q). Для ПЛМD(s, t, q) блок D имеет s входов и 2*s выходов: h=2*s. Дополнительные усложнения за счёт введения блока D на практике настолько незначительно, что его можно не учитывать, но при той же площади, что ПЛМ(s, t, q), позволяет реализовать более сложные системы булевых функций. Последующие работы, направленные на повышение эффективности использования площади матриц ПЛМ привели к созданию структуры разрезных ПЛМ – ПЛМР (рис. 2.29.). Она имеет следующие особенности:

1. Матрица М₁ разделена на две части : . Матрица расположена над матрицей М₂, а - под ней. Это позволяет при необходимости разрезать промежуточные шины в М₂ и реализовать на верхней и нижней частях одной и той же промежуточной шины различные элементарные конъюнкции входных переменных.

2. Входы матриц расположены с двух сторон (справа и слева). Любая горизонтальная шина разрезается в одном месте, и на одну её часть подаётся переменная (или отрицание переменной) с левого входа матрицы, а на другую – с правого.

3. Выходы матрицы М₂ расположены с двух сторон (слева и справа). Любая горизонтальная шина М₂ разрезается в одном месте, и на одной её части формируется значения функции для левого выхода матрицы, а на другой – для правого.

4. На кристалле БИС ПЛМ предусмотрена специальная система шин, позволяющая соединять выходы одной матрицы со входами другой. Выполнение разрезов шин и организация необходимых связей между входами и выходами различных матриц осуществляется на этапе настройки ПЛМ на заводе – изготовителе.

В озможности сокращения площади матриц М₁ и М₂ при тех же функциональных возможностях при использовании ПЛМР показана на примере, рассмотренном ранее, состоящем в реализации системы.

Информационная площадь приведённой ПЛМР:

S(ПЛМР)=S( )+S( )+S(M₂)=2*4+2*4+2*4=24 меньше, чем у ПЛМ(4,3,5):

S(ПЛМ)=2*4*5+5*3=55

2.10.3. Другие структуры матричных БИС.

Помимо ПЛМ существуют следующие матричные структуры: постоянные запоминающие устройства (ПЗУ), программируемые матрицы логики (ПМЛ) и программируемые матрицы вентилей (ПМВ).

Постоянные запоминающие устройства (ПЗУ).

П
ЗУ может рассматриваться как двухуровневая ПЛМ, матрица М₁ в которой настроена на реализацию функции полного дешифратора (рис. 2.30.)

Схема полного дешифратора программированию не подлежит, поэтому параметр q фиксирован: q=2^s. ПЗУ, имеющие s входов и t выходов, назовём ПЗУ(s, t). Поскольку дешифратор по своим выходам реализует конституенты 1, то ПЗУ предназначено для реализации СДНФ.

Пример 2.15.

Реализовать на ПЗУ систему функций.

Получим СДНФ каждой функции.

Реализация ПЗУ показана на рис. 2.31.

С
равним площади ПЛМ(16, 8,48) и ПЗУ (16,8): S(ПЛМ)=1920, S(ПЗУ)=2¹⁶*8=524288. Отсюда можно сделать вывод, что стандартные интегральные ПЛМ характеризуются значительно большим числом входов s и выходов t по сравнению с ПЗУ на кристалле того же размера.

Программируемая матрица вентилей (ПМВ).

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

Каждый выход М₁ путём программирования выходных вентилей можно передаваться с инверсией или без инверсии.

Программируемые матрицы логики (ПМЛ).

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

Для комбинационных ПМЛ к выходам подключаются логические элементы. В простейших ПМЛ матрица М₁ разбита на t секций по числу выходов t. Выходы каждой секции подключены ко входам элементов ИЛИ (рис. 2.33.), число которых t. К выходам секций могут подключаться более сложные логические элементы.

3. Построение цифровых устройств автоматного типа.

3.1. Понятие автомата.

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

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

В реальных автоматах в качестве элементов памяти выступают триггеры; теперь можно дать и другое определение автомата. Автомат – цифровое устройство, выходные сигналы которого является функцией входных сигналов и состояния автомата в данный момент времени. Работа автомата рассматривается в дискретные моменты времени t₀,t₁,t₂ … t_n …. Эти моменты времени образуют автоматное время. Каждый момент времени можно пронумеровать. Состояние автомата в момент времени t₀ будем называть начальным состоянием.

Состояние автомата в произвольное время t будем обозначать через а(t). Для начального состояния а(t₀) будем использовать также обозначение а(t₀)=a(0).

По способу формирования автоматного времени автоматы делятся на синхронные и асинхронные.

В синхронных автоматах автоматное время задаётся тактовой последовательностью . Поведение автомата вне автоматного времени не определено (рис.3.1.).

В асинхронных автоматах автоматное время задаётся моментами изменения входных сигналов (рис.3.2.).

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

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

Синтез автомата осуществляется в два этапа:

• этап синтеза абстрактного автомата (абстрактный синтез);

• этап синтеза структурного автомата (структурный синтез).

3.2. Синтез абстрактных автоматов.

3.2.1. Определение абстрактного автомата.

Абстрактный автомат задаётся множеством из шести элементов: S={ X, Y, A, f, g, a⁽⁰⁾} где:

X={x₁,x₂,…, } – множество входных сигналов (входной алфавит);

Y={y₁,y₂,…, } – множество выходных сигналов (выходной алфавит);

А={a₁,a₂,…, } – множество состояний (алфавит состояний);

f – функция переходов автомата;

g – функция выходов автомата;

a⁽⁰⁾ – начальное состояние автомата.

А бстрактный автомат (рис.3.3.) имеет один входной и один выходной канал. В каждый момент дискретного автоматного времени t=0,1,2,… автомат находится в определённом состоянии а(t) из множества А состояний автомата, причём в начальный момент t=0 он находится всегда в начальном состоянии a(t₀)=a⁽⁰⁾. Будем считать, что a⁽⁰⁾=a₁. В момент t, будучи в состоянии a(t)A, автомат способен воспринять на входном канале сигнал x(t)X и выдать на выходном канале сигнал y(t)Y

y(t)=g(a(t),x(t)),

переходя в состояние а(t+1)

а(t+1)=f(a(t), x(t)).

Другими словами, если на вход автомата, установленного в начальное состояние а₁, подавать буква за буквой некоторую последовательность букв входного алфавита – входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита – выходное слово. Таким образом, абстрактный автомат осуществляет словарное преобразование входных слов в выходные.

Автомат называется конечным, если конечные алфавиты A, X, Y. В дальнейшем будем рассматривать только конечные автоматы и термин «конечные» будем опускать. Автомат называется полностью определённым (полный автомат), если функции выходов g и переходов f определены на множестве всех пар вида m,x_j>, где a_mA, x_jX. У частичного автомата функции g и f определены не для всех пар m,x_j>.

На практике наибольшее распространение получили автомат Мили и Мура, которые отличаются способом формирования выходного сигнала g(t).

Закон функционирования автомата Мили задаётся уравнениями

а(t+1)=f(a(t), x(t)); t=0,1,2,…

y(t)=g(a(t), x(t)),

а закон функционирования автомата Мура задаётся уравнениями

а(t+1)=f(a(t), x(t)); t=0,1,2,…

y(t)=g(a(t)).

В автомате Мура выходной сигнал формируется в состоянии a(t), а в автомате Мили на переходе из a(t) в a(t+1).

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

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

3.2.2. Методы задания автоматов.

Чтобы задать конечный автомат S, необходимо описать все элементы множества S={X, Y, A, f, g, a⁽⁰⁾}, т.е. входной и выходной алфавиты и алфавит состояний, а такие функции переходов и выходов. Среди множества состояний необходимо выделить начальное состояние а⁽⁰⁾=а₁. Осуществляет несколько способов задания работы автомата, но наиболее часто используются следующие:

1. В виде графа переходов и выходов.

2. В виде таблиц переходов и выходов.

3. В виде матриц переходов и выходов.

Задание автомата в виде графа переходов и выходов.

Г раф автомата – ориентированный связный граф. Вершины соответствуют состояниям автомата, а дуги - переходу из состояния a(t) в состояние a(t+1): a_S=f(a_m, x_j)

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

Пример 3.1.

На рис. 3.6. и 3.7. приведены графы эквивалентных автоматов Мура S₁ и Мили S₂, определённых на алфавитах x={x₁,x₂,x₃,x₄} и y={y₁,y₂,y₃}. Эти автоматы на любую входную последовательность, оканчивающуюся на x₁x₂(… x₁x₂), формируют выходной сигнал y₂ (… y₂), а на x₁x₂x₃ (… x₁x₂x₃) сигнал y₃ (… y₃). Говорят, что автоматы распознают последовательности x₁x₂ или x₁x₂x₃. Назовём их правильными. Если входные символы не образуют правильной последовательности или пришли не все символы правильной последовательности формируется выходной сигнал y₁.

Задание автомата в виде таблиц переходов и выходов.

Описание автоматов в виде таблиц демонстрируется рис. 3.8. и 3.9, где изображены таблицы переходов и выходов эквивалентных автоматов Мура S₂ и Мили S₂, графы которых приведены на рис. 3.6 и 3.7.

Строки этих таблиц соответствуют входным сигналам, а столбцы – состояниями, причём крайний левый столбец состояний обозначен начальным состоянием a₁. В таблице переходов внутренняя клетка, находящаяся на пересечении строки и столбца, соответствует состоянию перехода a(t+1).

Для автомата Мили таблица выходов совмещены с таблицей переходов: над чертой в клетке записывается состояние а(t+1), a под ней – выходной сигнал y(t).

Задание автомата в виде матриц переходов и выходов.

Задание автоматов в виде матриц демонстрируется на рис. 3.10 и 3.11, где изображены матрицы рассмотренных выше автоматов S₁ и S₂.

Матрица переходов является квадратной матрицей.

Матрицы переходов и выходов имеют теоретическое значение, и используется при изучении поведения абстрактных автоматов.

Табличная форма представления матриц переходов и выходов.

На практике часто используется табличная форма представления матриц (рис. 3.12 и 3.13)

3.2.3. Минимизация числа внутренних состояний абстрактных автоматов.

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

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

Процедура минимизации числа внутренних состояний абстрактного автомата состоит из следующих шагов:

1. Находятся последовательные разбиения П₁ , П₂ ,…, П_k алфавита внутренних состояний на классы одно-, двух-, …, k-эквивалентных состояний, до тех пор, пока на каком-то k+1-м шагом не окажется, что П_k+1= П_k . Очевидно, что при достижении этого тождества можно утверждать, что П_k= П , т.е. что k-эквивалентные состояния являются полностью эквивалентными. Нетрудно увидеть, что число шагов этой процедуры не может превысить значения l -1, где l -размеры алфавита внутренних состояний автомата.

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

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

4. В качестве начального состояния автомата выбирается или начальное состояние исходного автомата, или любое ему эквивалентное.

Рассмотрим пример минимизации автомата Мили, заданного совмещенной таблицей переходов и выходов (табл. 3.1.).

Таблица 3.1.

Xi

a k

a 1

a 2

a 3

a 4

a 5

a 6

a 7

a 8

a 9

a 10

a 11

a 12

X1

a 10 Y1

a 12 Y1

a 3 Y2

a 7 Y2

a 3 Y1

a 7 Y2

a 3 Y1

a 10 Y1

a 7 Y2

a 1 Y2

a 5 Y2

a 2 Y2

X2

a 5 Y2

a 7 Y2

a 6 Y1

a 11 Y1

a 9 Y2

a 11 Y1

a 6 Y2

a 4 Y2

a 6 Y1

a 8 Y1

a 9 Y1

a 8 Y1

Класс П₁ выделяется из табл. 3.1. путем объединения тех внутренних состояний, которые характеризуются одинаковой реакцией на слова длиной в один символ. Заметим, что в понятие реакции входит только выходной сигнал, поскольку основным назначением автомата является осуществление словарного преобразования. Для класса П₁ выполняются:

П₁ ={ A ₁ ¹, A ₂ ¹}; A ₁ ¹={ a ₁, a ₂, a ₅, a₇, a₈}; A ₂ ¹={ a₃, a₄, a₆, a₉, a₁₀, a₁₁, a₁₂}.

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

Очевидно, что любая пара 1-эквивалентных состояний будет и 2-эквивалентна, если они любым входным сигналом будут переводиться в 1-эквивалентные. Практически это означает, что 2-эквивалентными будут те состояния, которые уже входя в тот или иной класс эквивалентности, в данной таблице имеют одинаковые столбцы. Тогда по табл. 3.2. для класса П₂ получаем: П₂ ={ A ₁ ², A ₂ ², A ₃ ², A ₄ ²}; A ₁ ²={ a₁, a₂};

A ₂ ²={ a₅, a₇, a₈}; A ₃ ²={ a₃, a₄, a_6, a₉, a₁₁}; A ₄ ²={ a₁₀, a₁₂}

Таблица 3.2.

Xi

ak, A sp

A 11

A 12

a1

a2

a5

a7

a8

a3

a4

a6

a9

a10

a11

a2

X1

A 12

A 12

A 12

A 12

A 12

A 11

A 11

A 11

A 11

A 11

A 11

A 11

X2

A 11

A 11

A 12

A 12

A 12

A 12

A 12

A 12

A 12

A 11

A 12

A 11

Таблица 3.3.

Xi

ak, A sp

A 21

A 22

A 23

A 24

a1

a2

a5

a7

a8

a3

a4

a6

a9

a11

a10

a12

X1

A 24

A 24

A 23

A 23

A 24

A 22

A 22

A 22

A 22

A 22

A 21

A 21

X2

A 22

A 22

A 23

A 23

A 23

A 23

A 23

A 23

A 23

A 23

A 22

A 22

Таблица 3.4.

Xi

ak, A sp

A 31

A 32

A 33

A 34

A 35

a1

a2

a5

a7

a8

a3

a4

a6

a 9

a 11

a 10

a 12

X1

A 35

A 35

A 32

A 32

A 34

A 33

A 33

A 33

A 33

A 33

A 31

A 31

X2

A 32

A 32

A 34

A 34

A 34

A 34

A 34

A 34

A 34

A 34

A 33

A 33

Продолжая аналогичную процедуру и далее, соответственно получим класс эквивалентности П₃. Таблицы для всех этих классов: для П₂ - табл. 3.3., для П₃ - табл. 3.4.

Из табл. 3.5. видно, что П₃ = П, откуда можно составить совмещенную таблицу уже минимизированного автомата (табл. 3.5.).

Используя рассмотренную процедуру по отношению к автомату, представленному графом на рис. 3.14., легко показать, что тот автомат после минимизации полностью переходит в автомат Мили, граф которого помещен на рис. 3.15.

Аналогичную процедуру минимизации можно провести и для автомата Мура.

Таблица 3.5.

Xi	a k
	a 1	a 5	a 8	a 3	a 10
X1	a 10 Y1	a 3 Y1	a 10 Y1	a 5 Y2	a 1 Y2
X2	a 5 Y2	a 3 Y2	a 3 Y2	a 3 Y1	a 8 Y1

Рис. 3.14. Рис. 3.15.

3.3. Структурный синтез конечных автоматов.

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

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

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

3.3.1 Этапы структурного синтеза автоматов.

1. Кодирование символов алфавитов абстрактного автомата.

2. Получение кодированных таблиц переходов и выходов.

3. Определение функций внешних переходов.

4. Выбор типа элементарных автоматов.

5. Получение функции возбуждения элементарных автоматов и функции выходов.

6. Построение принципиальной схемы автомата.

3.3.2. Кодирование символов алфавитов абстрактных автоматов.

Поскольку входные и выходные сигналы структурного автомата принимают двоичные значения, то каждый входной x_j и выходной y_i сигналы абстрактного автомата кодируются двоичными векторами длины n_C и n_Z.

Так же кодируется выходной сигнал.

Очевидно, что число разрядов векторов находится из:

;

Аналогичным образом осуществляется кодировка символов выходного алфавита.

где - количество элементарных автоматов.

Результатом кодирования является определение таких характеристик структурного автомата, как число входов n_C, число выходов n_Z и число элементарных автоматов. Кроме того, устанавливается соответствие между значениями входных и выходных сигналов и состояниями абстрактного и структурного автомата.

С
труктурная схема автомата.

Переход i-ого элементарного автомата в следующее состояние определяется функцией внешних переходов . Состояние i-ого элементарного автомата является функцией состояний всех автоматов.

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

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

Сигналы возбуждения входов элементарных автоматов формируются в соответствии со значением функций возбуждения элементарных автоматов:

Они формируются в комбинационной схеме. Выходные сигналы формируются комбинационной схемой функций выходов:

или в векторной форме

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

- для автомата Мура.

- для автомата Мили.

В автомате Мура входные сигналы С₁,С₂… не используются при формировании выходных сигналов.

Проблемы возникающие при кодировании.

Кодирование любого объекта из общего числа объектов, равному n, может быть выполнено:

способами, где . Если n=2^k, то число вариантов кодирования в точности равно n! Выбирается такой вариант кодирования, который обеспечивал бы минимальные аппаратные затраты. Эффективных алгоритмов выбора оптимальных вариантов кодирования не существует, и задача решается методом перебора.

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

Н апример, пусть для ЭА Q₁,Q₂,Q₃ имеем переход из a_k= в a_m=.

При переходе может возникнуть состояние , если Q₂ быстрее изменяет своё состояние, чем Q₃ (гонки выигрывает Q₂) или , если Q₃ быстрее изменяет своё состояние, чем Q₂ (гонки выигрывает Q₃). Возможны два случая:

В
случае «а» при воздействии входного сигнала x_i достигается верное состояние a_m, в случае «б» вместо состояния a_m переходим в другое состояние a_l. В первом, случае автомат функционирует правильно, и гонки являются некритическими, во втором неправильно - гонки являются критическими.

Для борьбы с состязаниями используют различные методы:

1) Противогоночное кодирование состояний автомата. Оно приводит к увеличению числа состояний автомата. Частным случаем такого кодирования является соседнее кодирование, при котором на каждом переходе изменяется состояние только одного ЭА: 101111110100…

2) Тактирование входных сигналов С_i C_i. В этом случае предъявляются жёсткие условия к длительности тактирующего сигнала , которая должна быть не больше времени задержки в цепи обратной связи.

3) Использование двойной памяти на MS – триггерах и им подобных.

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

Пример 3.2.

Осуществим кодирование символов алфавитов абстрактных автоматов S₁ и S₂ из раздела 3.2.2. Они заданы на входном x={x₁,x₂,x₃,x₄} и выходном y={y₁,y₂,y₃} алфавитах. Кроме того автомат Мура S₁ определён на алфавите состояний A₁={a₁,a₂,a₃,a₄}, а автомат Мили S₂ на алфавите A₂={a₁,a₂,a₃}.

Определим разрядность кодов символов:

1. алфавита состояний для S₁: n_Q=]log₂n_a[=log₂4=2 (автомат Мура).

Возможно n_a!=4!=24 способов кодирования для S₂: n_Q=]log₂n_a[=]log₂3[=2 (автомат Мили).

Возможно =4*3*2=24 способов кодирования.

1. входного алфавита

n_C=]log₂n_X[=log₂4=2

Возможно n_X!=4!=24 вариантов кодирования.

1. Выходного алфавита

n_Z=]log2n_Y[=]log₂3[=2

Возможно =4*3*2=24 вариантов кодирования.

Д
ля автомата S₂ таблицу кодирования символов алфавита состояний A₂ включает только первые три строки таблицы на рис. 3.22. Структурные автоматы имеют n_C=2 входов, n_Z=2 выходов и реализуются на n_Q=2 элементарных автоматах.

3.3.3. Получение кодированной таблицы переходов и выходов.

Исходными данными для построения кодированной таблицы переходов и выходов являются:

1) Таблицы переходов и выходов абстрактного автомата.

2) Таблицы кодирования символов алфавита абстрактного автомата.

Таблица кодирования получается путём подстановки двоичных кодов символов в таблицу переходов и выходов абстрактного автомата.

Пример 3.3.:

д
ля описанных выше автоматов S₁ и S₂ кодированные таблицы переходов и выходов. Они получаются путём кодирования таблиц на рис. 3.8 и 3.9. с использованием таблиц на рис. 3.20.,3.21. и 3.22.

Таблицы задают переходы элементарных автоматов. По кодированной таблице переходов находят функции внешних переходов элементарных автоматов, а по кодированной таблице выходов - функции выходов.

3.3.4. Определение функций внешних переходов.

Функции внешних переходов определяется в следующей последовательности.

1) Переставить строки столбцы таблицы переходов-выходов таким образом, чтобы значение входного сигнала и состояний элементарных автоматов в момент t образовывали циклический код.

2 ) Размножаем (распараллеливаем) таблицу переходов по числу элементарных автоматов и таблицу переходов для каждого автомата представляется в виде диаграммы Карно.

1. По диаграмме Карно определяем функции внешних переходов.

Ниже определяются функции внешних переходов для автоматов S₁ и S₂. Преобразуем кодированные таблицы переходов и выходов на рис. 3.23. и 3.24. автоматов S₁ и S₂ переставив местами два последних столбца.

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

3.3.5 Элементарные автоматы и их свойства.

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

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

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

а) внутреннее состояние триггера обозначается буквой Q; при Q = 1 мы будем говорить о «единичном состоянии триггера», при Q = 0 – о «нулевом состоянии триггера»;

б) выходной сигнал триггера повторяет его внутреннее состояние и поэтому обозначается той же

буквой Q;

в) триггер имеет парафазный выход, формирующий сигналы Q и ;

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

д) сигнальные входы триггера принято делить на установочные и рабочие. Установочные сигналы подаются помимо комбинационной схемы формирования функций возбуждения К С Q, и служат для установки триггера в исходное состоя­ние (нулевое или единичное). Принято установочные сигналы обозначать через R_d (установка в «О») и S_d (установка в «1»).

Рабочие сигналы формируются на KCQ и изменяют состоя­ние триггера в процессе формирования выходного сигнала ав­томата; они обозначаются буквами D, T, R, S, J, K; Рабочие сигналы, как правило, тактируются. Входы могут быть статическими и динамическими. В случае статических входов состояний триггера изменение состояния триггера осуществляется по уровню сигнала. Установочные входы являются статическими. В случае динамических входов состояние изменяется по изменению сигнала (по фронту или срезу).

Приняты следующие обозначения для динамических входов.

е) классификацию триггеров осуществляют во числу рабо­чих сигналов.

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

Рассмотрение триггеров мы начнем с их простейших мо­дификаций - триггеров с одним входом. Таких триггеров два: D - триггер и Т-триггер.

D - триггер (от английского delay — задержка) форми­рует выходной сигнал, логически совпадающий с входным сиг­налом, но задержанный относительно последнего на один период синхроимпульсов. На рис. 1 представлено графическое изображение триггера (а) и отображена его работа в виде таблицы переходов (б), графа (в) и матрицы переходов (г). При построении учитывалось свойство D-триггера: последующее состояние триггера Q(t+1) всегда совпадает со значе­нием его входного сигнала D (t). Для определения аналити­ческого выражения функции перехода можно воспользоваться таблицей перехода, представив в виде диаграммы Карно.

Q (t+1) = D(t)

При рациональном кодировании матричной таблицы переходов ее можно интерпретировать как диаграмму Карно и использовать для минимизации функции перехода. Нетрудно видеть, что для нашего случая можно получить минимальную форму искомой функции в виде Q(t+1) = D(t).

Микросхемы D – триггеров входят в состав всех существующих серий интегральных цифровых схем. На рис. 3.29. изображён один из двух триггеров микросхемы К155ТМ2:

Рис. 3.29.

Другим одновходовым триггером является Т-триггер (от английского trigger - пусковое устройство, триггер), в Т-триггере входной сигнал, равный единице, изменяет его предыдущее состояние на противоположное, а нулевое значение входного сигнала сохраняет его предыдущее состояние. Описание

Т-триггера представлено на рис. 3.31, функция перехода определилась по таблице переходов как

Отдельно микросхем счётных триггеров не существует, но их можно реализовать на других триггерах. На рис. 3.32. приведены схемы асинхронного и синхронного счётного устройства на D- триггерах: а- асинхронный T-триггер , б- синхронный Т- триггер.

а) б)

Рис. 3.32.

Перейдем теперь к рассмотрению триггеров с двумя входами. Принято обозначать один из входов через S (от английского set - установка) и называть его S -входом или входом установки в «1», а другой - через R (от английского reset - возврат) и называть его R -входом или входом установки в «0» .

Общим свойством всех двухвходовых триггеров является их реакция на раздельное единичное воздействие их входных сигналов R и S . Так, при R=1 и S=0 триггер вне зависимости от его предыдущего состояния всегда переводится в нулевое состояние, а при S = 1, R = 0 - в единичное состояние. Условие R = 0, S = 0 соответствует отсутствию каких-либо переключающих сигналов, поэтому триггер сохраняет свое предыдущее состояние. Таким образом, двухвходовые триггеры могут различаться своей реакцией на одновременное единич­ное воздействие их входных сигналов, когда R = 1 и S = 1. Это их свойство и положено в основу классификации двухвходовых триггеров. Мы рассмотрим пять модификаций таких триггеров — триггеры R-S, r, s, e и J -K типа.

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

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

Q(t+1) = (S+Q )_t , RS=0;

Q(t+1) = (t) (S(t)+Q(t)), RS=0.

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

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

Переход Q(t) Q(t+1)	Вход. сигн.
	R(t)	S(t)
00	br00	bs00
01	br01	bs01
10	br10	bs10
11	br11	bs11

Рис. 3.34. Табличное представление матрицы переходов

Табличная форма матрицы перехода R - S - триггера показана на рис. 3,д. Для переходов 0→0 и 1→1 значения входных сигналов однозначно определены, в то время как для переходов 0→0 и 1→1 появляются неопределенные коэффици­енты. Действительно, сохранение нулевого состояния триггера происходит при любом значении сигнала установки в «0» ( R -сигнале), а сохранение единичного состояния - при любом значении сигнала установки в «1» ( S - сигнале).

Для упрощения процедуры определения входных сигналов на переходе d→β можно рекомендовать построение некоторой логической функции X_αβ, единичное значение которой вызывает этот переход. Для триггеров с одним входом эта функ­ция вырождается в переменное, если переход происходит при его единичном значении, и в отрицание переменного - при ну­левом.

Для триггеров с двумя входами функция X_αβ дизъюнктив­но связывает все наборы входных переменных, вызывающих переход α→β

К примеру, для перехода 0→0 имеем X₀₀ = + R = , откуда видно, что переход осуществляется при S = 0 и от переменной R не зависит (R = l₁).

В S - триггере комбинация R = 1; S = 1 переводит триггep в единичное состояние. Отсюда и его название - сигнал установки в единицу ( S - сигнал) всегда подавляет сигнал установки в ноль ( R - сигнал).

Описание S -триггера приведено на рис. 3.35. Поскольку ГОСТ не предусматривает специального обозначения для триг­геров S-, R- и E - типа, мы будем пользоваться графическим изображением R-S - триггера с соответствующей буквой над ним. Из таблицы переходов получаем

Q(t+1) = (S + Q )_t = ((S + )(S+Q))_t

В отличие от предыдущего случая дизъюнктивная и конъ­юнктивная формы Q( t+1) эквивалентны, поскольку они отображают функцию перехода полностью определенного эле­ментарного автомата.

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

переход 0→0; X₀₀ = + R = , откуда S=0; R= b₁; переход 0→1; X₀₁ = + R = , откуда S=1;

R. = b₂; переход 1→1; X₁₁ = + +R S= +S.

Полученное выражение для X₁₁ говорит о том, что и R и S могут быть выра­жены неопределенными, но обязательно зависимыми друг от друга коэффициен­тами. Так, сигнал S может принимать произвольное значение при R=0, а сигнал R – при S=1. Поскольку на переходе 1→1 значение X₁₁ должно оставаться равным единице, имеем

В R -триггере сигнал R подавляет сигнал S, поэтому комбинация R=1, S=1 переводит триггер в нулевое состоя­ние. Анализ этого типа триггера во многом напоминает ана­лиз S -триггера, поэтому мы его опускаем и приводим функцию перехода сразу в ее аналитической форме:

Q(t+1) = (t) (S(t)+Q(t))

В Е -триггере (от английского equal- равный) комбинация R=1, S = 1 сохраняет предыдущее состояние триггера, сигналы R и S эквивалент­ны по силе друг другу и их действие компенсируется, функция перехода

Е- триггера принимает вид

Q(t+1) =( S+Q +QS)_t .

Матрицы переходов R- и Е- триггеров приведены на рис. 3.36., значения неопределенных коэффициентов определены из выражения для X₁₁ .

Q(t)→Q(t+1)	Rтр		Eтр
	R(t)	S(t)	R(t)	S(t)
0→0		b1		b1
0→1	0	1	0	1
1→0	1	b2	1	0
1→1	0	b3	b2

Рис. 3.36. Матрицы переходов R- и E- триггеров.

В J- К -триггере комбинация R=1, S=1 изменяет его состояние на противоположное. Свое название триггер J-K – типа получил от имени изобретателя счетного триггера Jordan (1919 г.) (нелишне заметить, что идея построения триггера на год раньше была предложена М.А. Бонч-Бруевичем).

Триггер J-K - типа называют еще универсальным тригге­ром, поскольку он совмещает в себе свойства R-S- и Т-триггеров. Учитывая особое положение J-К -триггера среди дру­гих триггеров, принято его R вход обозначать буквой К , а S — буквой J . Соответственно изменяется маркировка входных сигналов. J-K - триггер обладает замечательным свой­ством: все неопределенные коэффициенты его матрицы переходов независимы. Это, как правило, обеспечивает дополнительные резервы минимизации функций возбуждения и приво­дит к наипростейшим схемным реализациям.

а) в)

R(t)	S(t)	Q(t)
		0	1
0	0	0	1
0	1	1	1
1	1	1	0
1	0	0	0

Q(t)→Q(t+1)	R(t)	S(t)
0→0	b1	0
0→1	b2	1
1→0	1	b3
1→1	0	b4

б) г)

Рис. 3.37. J-K — триггер:

а- условное обозначение; б- таблица пере­ходов, в—граф переходов; г- матрица пере­ходов

Графическое изображение триггера и его задание пред­ставлено на рис. 3.37. По таблице переходов получаем:

Q(t+1)=(Q + J)_t

В теории автоматов часто рассматривают трёхвходовый триггер R-S-Т - типа. Однако в связи с разработкой и внедрением J-K - триггеров применение R-S-Т - триггера в реальных схемах практически сведено к нулю.

3.3.6 Определение функций возбуждения элементарных автоматов.

Функции возбуждения входов P_i элементарных автоматов Q_i , , определяются в результате решения уравнений:

(3.1.)

относительно P_i

Здесь f_i - функция переходов триггера, на котором реализуется элементарный автомат;

φ_i – функция внешних переходов элементарного автомата.

Для одновходовых триггеров

P_i= D_i или T_i для одновходовых триггеров D и T соответственно.

P_i=< R_i, S_i > или < K_i, J_i > для двувходовых триггеров.

Существуют следующие методы решения уравнения (3.1):

1. Аналитические;

2. Табличные;

3. Сравнения.

Аналитический метод определения функций возбуждения.

Обозначим через

D триггер.

Для D триггера решение уравнения (3.1.) находится сразу:

T триггер.

Для Т триггера уравнение (3.1.) выглядит следующим образом:

Решая его, получим

R-S триггер.

Для R-S триггера уравнение (3.1.) выглядит следующим образом:

,

которое приводится к виду

Решая его, получим:

J-K триггер.

Для J-K триггера уравнение (3.1.) выглядит следующим образом:

Решая его, получим:

S триггер.

Для S триггера уравнение (3.1.) выглядит следующим образом:

Решая его, получим:

R триггер.

Для R триггера уравнение (3.1.) выглядит следующим образом:

Решая его, получим:

E триггер.

Для E триггера уравнение (3.1.) выглядит следующим образом:

Решая его, получим:

Здесь - неопределённые функции аргументов . В частности, если положить

, получим для всех двухвходовых триггеров:

Более простые выражения получаются путём доопределения неопределённых функций .

Пример 3.4.

Для автомата S₂ функция внешних переходов элементарного автомата Q₁ (рис. 3.28) имеет вид:

.

Тогда функции возбуждения J-K триггера, в соответствие с полученными ранее уравнениями, определяются следующим образом:

Доопределив

получим:

Табличный метод получения функций возбуждения.

Предположим, что функция переходов элементарного автомата Q_i задана диаграммой Карно

Рис. 3.38.

Нули и единицы диаграммы однозначно описывают характер перехода автомата. Так ноль левой части диаграммы Карно соответствует переходу 0→0, поскольку он лежит в полосе Q_i(t)=0 и Q_i(t+1)=0, а единица переходу 0→1, поскольку теперь Q_i(t+1)=1. Аналогично для правой части диаграммы имеем для нуля переход 1→0, а для единицы – переход 1→1.

Очевидно, что функция возбуждения должна быть построена таким образом, чтобы её значения на всех переходах вызывали требуемые таблицей изменения внутреннего состояния элементарного автомата. Отсюда следует, что диаграмма Карно функции возбуждения конкретного типа триггера может быть получена путём замены нулей и единиц диаграммы Карно функции внешних переходов значениями входных сигналов соответствующего входа, полученными из матрицы переходов этого триггера. Тогда диаграмма Карно функции внешних переходов преобразуется в одну или две (по числу входов применяемого триггера) диаграммы Карно функции возбуждения. Общий вид диаграммы Карно для функции возбуждения P^k_i- k-го входа i-го триггера представлен на рис. 3.39.

Рис. 3.39.

Индексация коэффициентов производилась аналогично матрице переходов рис. 3.34. Для удобства использования табличного метода все матрицы сведены в единую таблицу (рис. 3.40.). Неопределённые коэффициенты b_i, b^*_j внутри одной таблицы доопределяются независимо. Зависимые коэффициенты b_i, b^*_i в соседних таблицах для разных входов доопределяются в соответствие с уравнением связи:

QiQt+1	Dтр	Tтр	R-Sтр		Sтр		Rтр		Eтр		J-Kтр
	D	T	R	S	R	S	R	S	R	S	K	J
00	0	0	b1	0	b1	0	b*1	b1	b*1	b1	b1	0
01	1	1	0	1	b2	1	0	1	0	1	b2	1
10	0	1	1	0	1	0	1	b2	1	0	1	b3
11	1	0	0	b2	b3	b*3	0	b3	b2	b*2	0	b4

Рис. 3.40.

Пример 3.5.

Применения табличного метода:

Определим функции возбуждения K₁ и J₁ элементарного автомата Q₁ на J-K триггере автомата Мили S₂, функции внешних переходов которого изображены на рис. 3.27.

Метод сравнения.

Этот метод основан на приравнивании коэффициентов в левой и правой частях уравнения (3.1.) при

и .

Пример 3.6.

Определить функции возбуждения K₁ и J₁ элементарного автомата Q₁ из предыдущего примера:

Имеем:

Отсюда:

3.3.7. Определение функций выходов.

Функции выходов определяются из таблиц выходов структурного автомата.

Для рассмотренного выше автомата Мура S₁ из таблицы выходов (рис. 3.25.) получим диаграммы Карно для получения выходных сигналов Z₁ и Z₂.

Для автомата Мили S₂ из таблицы выходов (рис. 3.26.) аналогичным образом определяем выходные сигналы Z₁ и Z₂.

Содержание:

0. Введение. 1

0.1. Понятие организации ЭВМ. 1

Функция, структура и организация систем. 1

Основные факторы, влияющие на принципы построения ЭВМ. 1

0.2. Содержание курса. 2

1. Представление информации в ЭВМ. 3

1.1. Системы счисления. 3

1.1.1. Позиционные системы счисления. 3

Пример 1.1. 4

1.1.2. Двоично-кодированные системы счисления. 4

Пример 1.2. 4

1.2. Преобразование из одной системы счисления в другую. 5

1.2.1. Преобразование целых чисел. 5

Метод деления. 5

Пример 1.3. 5

Пример 1.4. 5

Метод умножения. 6

Пример 1.5. 6

Пример 1.6. 6

1.2.2. Преобразование дробей. 6

Метод Умножения. 6

Пример 1.7. 6

Метод деления. 6

Пример 1.8. 7

1.2.3. Перевод чисел с основанием q=p^k. 7

Пример 1.9. 7

1.3. Представление информации в ЭВМ. 7

1.3.1. Двоичные числа. 7

1.3.2. Кодирование десятичных чисел и алфавитно-цифровой информации. 10

Пример 1.10. 11

Пример 1.11. 11

1.3.3. Логические значения. 11

1.4. Машинные коды. 11

1.4.1. Прямой код. 12

Пример 1.12. 12

1.4.2. Дополнительный код. 12

Пример 1.13. 12

1.4.3. Обратный код числа. 12

Пример 1.14. 13

1.4.4. Выполнение арифметических действий с кодами. 13

Пример 1.15. 13

1.4.5. Признаки переполнения разрядной сетки. 14

Пример 1.16. 14

Пример 1.17. 14

2. Синтез комбинационных устройств. 15

2.1 Логические переменные и функции. 15

Физическая природа. 15

Пример 2.1. 15

2.2 Элементарные функции. 16

2.2.1 Функции одной переменной. 16

Элемент повторения. 16

Элемент «НЕ». 16

2.2.2 Функции двух переменных. 16

Элемент «И». 17

Элемент «ИЛИ». 17

Элемент «И-НЕ». 17

Элемент «ИЛИ-НЕ». 17

Элемент «исключающее ИЛИ». 17

2.3 Функции многих переменных. 18

Примеры (2.2.) базисов: 18

Основные законы Булевского базиса: 18

Действия с константами «0» и «1»: 19

Правило введения и исключения лишних связок: 19

2.4. Задание функции комбинационных логических схем. 19

2.4.1. Нормальные формы записи булевых функций. 19

Пример 2.3. 19

Пример 2.4. 20

2.4.2. Совершенные нормальные формы. 20

Пример 2.5. 20

Пример 2.6. 20

Пример 2.7. 20

Свойства СНФ. 21

Пример 2.8. 21

2.5. Задача минимизации булевых функций. 21

2.6. Минимизация нормальных форм булевых функций. 22

2.7 Минимизация с помощью диаграмм Карно. 23

2.8 Топологическая интерпретация правил минимизации. 25

Правила минимизации: 25

Пример 2.9. 25

Минимизация не полностью определённых функций. 26

Минимизация систем логических функций. 26

2.9. Построение комбинационных схем на реальной элементной базе. 27

1) Коэффициент объединения по выходу. 27

2) Коэффициент объединения по входу. 28

3) Быстродействие. 28

Пример 2.10. 29

2.9.1 Порядок синтеза комбинационных схем. 29

2.9.2 Элементы «И», «ИЛИ», «НЕ». 30

2.9.3 Элементы «И-НЕ», «ИЛИ-НЕ». 30

Пример 2.11. 31

Пример 2.12. 31

Пример 2.13. 31

2.9.4. Элементы И-ИЛИ-НЕ. 32

Пример 2.14. 32

2.10. Цифровые устройства на программируемых БИС с матричной структурой. 34

2.10.1. Матричная реализация булевых функций. 34

2.10.2. Программируемые логические матрицы (ПЛМ). 36

2.10.3. Другие структуры матричных БИС. 38

Постоянные запоминающие устройства (ПЗУ). 38

Пример 2.15. 38

Программируемая матрица вентилей (ПМВ). 38

Программируемые матрицы логики (ПМЛ). 39

3. Построение цифровых устройств автоматного типа. 39

3.1. Понятие автомата. 39

3.2. Синтез абстрактных автоматов. 40

3.2.1. Определение абстрактного автомата. 40

3.2.2. Методы задания автоматов. 40

Задание автомата в виде графа переходов и выходов. 40

Пример 3.1. 41

Задание автомата в виде таблиц переходов и выходов. 41

Задание автомата в виде матриц переходов и выходов. 42

Табличная форма представления матриц переходов и выходов. 43

3.2.3. Минимизация числа внутренних состояний абстрактных автоматов. 43

3.3. Структурный синтез конечных автоматов. 45

3.3.1 Этапы структурного синтеза автоматов. 45

3.3.2. Кодирование символов алфавитов абстрактных автоматов. 46

Структурная схема автомата. 46

Проблемы возникающие при кодировании. 47

Пример 3.2. 47

3.3.3. Получение кодированной таблицы переходов и выходов. 48

Пример 3.3.: 48

3.3.4. Определение функций внешних переходов. 49

3.3.5 Элементарные автоматы и их свойства. 50

3.3.6 Определение функций возбуждения элементарных автоматов. 55

Аналитический метод определения функций возбуждения. 55

D триггер. 55

T триггер. 55

R-S триггер. 56

J-K триггер. 56

S триггер. 56

R триггер. 56

E триггер. 56

Пример 3.4. 57

Табличный метод получения функций возбуждения. 57

Пример 3.5. 58

Метод сравнения. 58

Пример 3.6. 58

3.3.7. Определение функций выходов. 58

Содержание: 60

Литература: 63

Литература:

67