УП часть 2 ТА

Устройство кодирования должно преобразовать элементы информации множества А заданной природы в двоичные векторы (представленные тем или иным удобным нам способом), причем преобразование это должно быть взаимно однозначно. Аналогично, устройство декодирования должно преобразовать двоичные векторы (представленные тем или иным способом) в элементы информации множества В. Проблема построения конечного функционального преобразователя теперь сводится к реализации произвольного

преобразователя F :{0,1}m → {0,1}n , который может быть задан,

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

F :{0,1}m → {0,1}n имеет более четкую математическую

формулировку, однако решить ее непросто. Для упрощения решения этой проблемы удобен следующий простой прием: вместо одной

функции F :{0,1}m → {0,1}n построим n функций

fi :{0,1}m → {0,1} так, что реализация совокупности этих более

простых функций даст искомый преобразователь F. Этот прием представлен на рис. 4.1, в. На рис. 4.1, г функции fi выделены явно.

Функции вида f :{0,1}m → {0,1} , сопоставляющие

двоичным векторам двоичные значения, называются двоичными (или булевыми) функциями.

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

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

5 СИНТЕЗ И АНАЛИЗ ТИПОВЫХ КОМБИНАЦИОННЫХ АВТОМАТОВ.

Комбинационным автоматом (автоматом без памяти) называется автомат, у которого множество состояний состоит из

одного элемента, т.е. A =1. Для такого автомата характерно то, что

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

Комбинационный автомат называют также nk-полюсником. Это обусловлено тем, что на уровне черного ящика автомат рассматривают как устройство имеющее n-входов и k-выходов. Если k=1, то автомат называется одновыходным, если k>1, то автомат называется многовыходным или k-выходным. Для различных комбинационных автоматов существуют и различные соотношения между n и k. Процедуру синтеза комбинационных автоматов можно охарактеризовать схемой алгоритма, представленной на рис.5.1.

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

1-ый – начало синтеза комбинационного автомата; 2-ой – на этом этапе комбинационный автомат представляют

на уровне черного ящика; 3-ий – словесное описание работы автомата;

4-ый – задание работы автомата в виде таблицы истинности; в случае необходимости происходит доопределение таблицы истинности;

5-ый – аналитическое описание работы автомата в виде СДНФ или СКНФ;

6-ой – минимизация аналитического описания работы автомата;

7-ой – синтез логической схемы автомата в заданном элементном базисе;

8-ой – конец синтеза комбинационного автомата.

Начало

…

2

3

4

5

6

7

Конец

Рис. 5.1 Схема алгоритма, характеризующая процедуру синтеза комбинационного автомата.

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

Рассмотрим типовые комбинационные автоматы и их синтез.

5.1 Шифратор (coder) и его синтез.

Шифратор – это устройство, осуществляющее преобразование входного кода “1 из n” в k-разрядный позиционный выходной код.

Код “1 из n” часто называют унитарным кодом.

Если число входов шифратора равно 2n , то число выходов, очевидно, должно быть равным n, то есть числу разрядов двоичного

кода, которым можно закодировать 2n различных комбинаций.

Если в качестве позиционного кода использовать двоичный код, то между n и k должно иметь место следующее соотношение:

где ]x[- означает ближайшее целое, не меньше x. Рассчитаем по соотношению (5.1) значения k при n=2,3,4,5,6,7:

По схеме (5.1) синтезируем шифратор, преобразующий 10-ти разрядный унитарный код в двоичный код.

“1 из 10”→ 2k

1.Начало.

2.Представим шифратор на уровне черного ящика с детализацией его до входов и выходов.

Рис. 5.2 Представление шифратора на уровне черного ящика с детализацией его до входов и выходов.

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

4.Работа шифратора описывается четырьмя функциями y0, y1, y2, y3 , каждая из которых равна 1 на некоторых наборах, номер которых соответствует номеру входа шифратора. Составим таблицу истинности, отражающую закон функционирования шифратора

(табл. 5.1).

Таблица 5.1

Все остальные значения xi=0, при i=0…9.

5-6. Воспользовавшись табл.5.1, составим СДНФ функций выхода шифратора.

7. Синтезируем шифратор в элементном базисе И, ИЛИ, НЕ (рис.5.3). Функции (5.2) реализуются четырьмя дизъюнкторами, на выходах которых формируется четырехразрядный двоичный код.

Рис. 5.3 Условно-графическое обозначение шифратора, n>k.

5.2 Дешифратор и его синтез.

Дешифратор (decoder) – это комбинационное устройство, позволяющее распознавать числа, представленные позиционным n- разрядным кодом. Если на входе дешифратора n-разрядный двоичный код, то на его выходе код “1 из N”. В кодовой комбинации этого кода только одна позиция занята единицей, а все остальные – нулевые [6].

Дешифратор предназначен для преобразования n-разрядного позиционного кода в k-разрядный унитарный код.

Число входов дешифратора n должно удовлетворять соотношению n<k, где k- число выходов дешифратора.

Если k удовлетворяет соотношению k = 2n , то такой

дешифратор называется полным, если k < 2n - то неполным. По построению схемы различают дешифраторы [2]:

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

2.Линейные дешифраторы. Наиболее быстродейст-вующие, они представляют собой всего лишь одну логическую ступень элементов, которая непосредственно и осуществляет дешифрирование входных данных.

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

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

Синтезируем полный линейный дешифратор на два входа и четыре выхода, то есть n=2 и k=4. Синтезировать дешифратор будем по схеме, представленной на рис. 5.1.

1.Начало.

2.Представим дешифратор на уровне черного ящика с детализацией его до входов и выходов (рис.5.4).

Рис. 5.4 Представление дешифратора на уровне черного ящика с детализацией его до входов и выходов.

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

4.Работа дешифратора описывается четырьмя функциями y0, y1, y2, y3 , каждая из которых равна 1 только на одном наборе аргументов. Составим таблицу истинности, отражающую закон функционирования дешифратора (табл. 5.2).

Таблица 5.2

7. Синтезируем шифратор в элементном базисе И, ИЛИ, НЕ (рис.5.4). Функции (5.3) реализуются четырьмя конъюнкторами.

Рис. 5.5 Схема дешифратора на 2 входа.

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

& y1 = C × x1 × x0 y1

& y2 = C × x1 × x0 y2 & y3 = C × x1 × x0 y3

Рис. 5.6 Схема дешифратора на 2 входа со стробированием. 8. Конец.

На рис. 5.7 представлено условно-графическое обозначение (УГО) дешифратора:

Рис. 5.7 Условно-графическое обозначение дешифратора.

5.3 Мультиплексор и его синтез.

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