Задание

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

Уточнение задания

Для выполнения поставленной задачи необходимо устройство, имеющее один вход и два выхода. На вход подается параллельный 48-разрядный код А{48:1}. Т. к. максимальный номер разряда в 48- разрядном слове 48, то для формирования номеров нулей 5- разрядное слово НОМ{4:0}, для формирования количества нулей потребуется 5- разрядное слово КОЛ{4:0}. Для данного устройства выберем внешнюю синхронизацию с частотой ГТИ=5 МГц.

Длительность импульсов СТРОБ и УСЧИТ равна периоду тактовой последовательности и положительные фронты этих импульсов появляются вслед за положительным импульсом внешней синхронизации ГТИ.

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

УСЧИТ.

1 2 3	4 5 6	7 8 9	…	46 47 48
1 0 1	1 0 1	1 0 1	…	1 0 1
1	2	3	…	16

48:3 = (16)₁₀ = (10000)₂ => НОМ{4:0} и КОЛ{4:0}

Схема устройства:

НОМ{4:0}

Временные диаграммы

ГИ

СТРОБ

А

НОМ

УСЧНОМ

КОЛ

УСЧКОЛ

Комбинационная реализация вычислительного устройства.

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

Регистровая реализация устройства

В блок-схеме применены следующие обозначения:

РГД{48:1} – регистры данных;

СЧКОЛ{4:0} – счетчик количества нулей;

СЧНОМ{4:0} – счетчик номера разряда в коде А;

Описание алгоритма:

Устройство находится в начальном состоянии и в нем не производится никаких операций до тех пор пока не придет сигнал стробирования СТРОБ. По приходу сигнала СТРОБ происходит запись в регистр РГД{32:1} входного слова А. Счетчик СЧКОЛ{4:0} устанавливается в нуль, а счетчик СЧНОМ{4:0}в два. Далее происходит проверка РГД равенству 0, т. е. произошло ли заполнение регистра нулями. Если условие выполняется, то считывается при появлении сигнала УСЧИТ количество комбинаций УСЧКОЛ. Если условие не выполняется, то осуществляем проверку признака комбинации 101. Если условие выполняется, то увеличиваем на единицу СЧКОЛ, последовательно сдвигаем РГД влево на три разряда и увеличиваем СЧНОМ на три, возвращаемся к проверке РГД=0. Если условие не выполняется, т. е. нет комбинации вида 101, то сдвигаем РГД влево на один разряд и увеличиваем СЧНОМ на единицу, возвращаемся к проверке РГД=0.

Блок-схема алгоритма функционирования устройства.

нет

да

да

нет

0

1

Микропрограмма 1

Переменные:

входные: А{1:48}, строб;

внутренние: РГД{1:48}, СЧНОМ{4:0}, СЧКОЛ{4:0};

внешние: УСЧКОЛ, УСЧНОМ, НОМ{4:0}:=СЧНОМ{4:0}, КОЛ{4:0}:=СЧКОЛ{4:0};

Признаки:

Р1:=┐строб;

Р2:=РГД{1:48}:=0;

Р3:= (РГД{1}&РГД{2}&РГД{3});

Процедура:

М1 если Р1, то М1;

УЗАП1: РГД:=А,

УН1: СЧКОЛ:=0,

УН2: СЧНОМ:=2;

М2 если Р2, то М4;

если Р3, то М3;

УСЧКЛ: СЧКОЛ:= СЧКОЛ+1,

УСЧНОМ;

УСДВ: РГД:=РГД{2:48}.0;

УСЧНМ: СЧНОМ:= СЧНОМ+1;

УСДВ: РГД:=РГД{2:48}.0;

УСЧНМ: СЧНОМ:= СЧНОМ+1;

М3 УСДВ: РГД:=РГД{2:48}.0;

УСЧНМ: СЧНОМ:= СЧНОМ+1;

Идти к М2;

М4 УСЧКОЛ: ;

конец.

Анализ микропрограммы показывает, что сигналы УЗАП1, УН1, УН2 эквивалентны и их можно заменить одним сигналом УЗП: УЗП = УЗАП1 = УН1 = УН2. Сигналы УСДВ и УСЧНМ также эквивалентны и их можно аналогично заменить одним сигналом УСД:В УСДВ = УСДВ = УСЧНМ.

После упрощения микропрограмма примет вид

Микропрограмма 2

Переменные:

входные: А{1:48}, строб;

внутренние: РГД{1:48}, СЧНОМ{4:0}, СЧКОЛ{4:0};

внешние: УСЧКОЛ, УСЧНОМ, НОМ{4:0}:=СЧНОМ{4:0}, КОЛ{4:0}:=СЧКОЛ{4:0};

Признаки:

Р1:=┐строб;

Р2:=↓/РГД{1:48}:=0;

Р3:= (РГД{1}&РГД{2}&РГД{3});

Процедура:

М1 если Р1, то М1;

УЗП: РГД:=А, СЧКОЛ:=0, СЧНОМ:=2;

М2 если Р2, то М4;

если Р3, то М3;

УСЧКЛ: СЧКОЛ:= СЧКОЛ+1,

УСЧНОМ;

УСДВ: РГД:=РГД{2:48}.0; СЧНОМ:= СЧНОМ+1;

УСДВ: РГД:=РГД{2:48}.0; СЧНОМ:= СЧНОМ+1;

М3 УСДВ: РГД:=РГД{2:48}.0; СЧНОМ:= СЧНОМ+1;

Идти к М2;

М4 УСЧКОЛ: ;

конец.

Функциональная схема операционного автомата

А

РГД

1

СЧКОЛ

+1

{48:1} РГД{48:1} УЗП СЧКОЛ{4:0} КОЛ{4:0}

УЗП

УСЧКЛ

УСДВ

СЧКОЛ

+1

УЗП

с троб СЧНОМ{4:0} НОМ{4:0}

УСЧНОМ УСЧНОМ

УСЧКОЛ

Р1 Р3 Р2

Управляющий автомат с жесткой логикой.

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

Управляющий автомат с жесткой логикой

Автомат Мура

Граф-схема алгоритма

1

0

а1

0

а6

1

а0

1

0

а2

а3

а4

а5

Граф-схема алгоритма автомата Мили

1

0

0

1

0

1

Будем строить управляющий автомат как автомат Мили, т.к. он имеет только 2 состояния и реализуется на одном триггере. В качестве последнего выберем Д-триггер

вход	Состояния
	а0	а1
Р1	а0
┐Р1	а1/УЗП
┐Р2		а0/УСЧКОЛ
Р2*Р3		а1/УСДВ
Р2*┐Р3		а1/УСЧКЛ, УСЧНОМ, УСДВ, УСДВ

Таблица переходов и выходов

Кодированная таблица переходов и выходов

вход	а0		а1
Р1	0
┐Р1	1	УЗП
┐Р2			0	УСЧКОЛ
Р2*Р3			1	УСДВ
Р2*┐Р3			1	УСЧКЛ, УСЧНОМ, УСДВ, УСДВ

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

Q(t+1)=( ┐P1*┐Q+P2*P3*Q+P2*┐P3*Q)t=(┐P1*┐Q+P2*Q)t

УЗП=┐P1*┐Q

УСЧКОЛ= ┐P2*Q

УСДВ= P2*P3*Q+ P2*┐P3*Q= P2*Q

УСЧНОМ= P2*┐P3*Q= ┐P3* УСДВ

УСЧКЛ=┐P3* УСДВ

Функциональная схема УА

Управляющий автомат с программной логикой

номер	метка	Управляющие сигналы	переход
0	М1		если Р1, тоМ1
1		УЗП
2	М2		если Р2, тоМ4
3			если Р3, тоМ3
4		УСЧКЛ, УСЧНОМ, УСДВ, УСДВ
5	М3	УСДВ	идти к М2
6	М4	УСЧКОЛ	конец