Файл: Васильев, В. В. Гибридные модели задач оптимизации.pdf

Г л а в а 4

ГИБРИДНЫЕ ВЫЧИСЛИТЕЛИ НА ОСНОВЕ

СЧЕТЧИКОВЫХ СИСТЕМ

Известно, что счетчиковые структуры получили распро­ странение в информационно-измерительных системах [138, 164]. Выше рассмотрены специализированные цифровые модели задач об экстремальных путях и потоках в сетях. В последних обработка информации сводилась к операциям алгебраического суммирования и выборки экстремума над величинами, заданными пропорциональ­ ными им временными интервалами. Здесь мы рассмотрим подроб­ нее свойства счетчиковых структур и предпримем попытку расши­ рить их функциональные возможности.

4.1. ПРЕДСТАВЛЕНИЕ ИНФОРМАЦИИ В СЧЕТЧИКОВЫХ СТРУКТУРАХ

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

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

78

Здесь т — величина временного интервала; / — частота тактового генератора.

После окончания формирования временного интервала счетчик останется в нулевом состоянии и записанная в нем информация будет утеряна. Для восстановления (регенерации) этой информации можно воспользоваться схемой рис. 37. Здесь используются два идентич­ ных счетчика Счх и Сч2 с одинаковой емкостью N импульсов. Счет­ чик Счх по-прежнему несет информацию о машинной переменной х, а счетчик Сч2 обеспечивает ее восстановление после каждого цикла

опроса. С подачей пускового сигнала на полюс «Вход» оба счетчика начинают одновременно отсчет импульсов. На выходе И2будет сфор­ мирован временной интервал т, пропорциональный х, но счетчики

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

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

4.2. СПОСОБ ВЫПОЛНЕНИЯ ОПЕРАЦИЙ В СЧЕТЧИКО-РЕГИСТРОВЫХ'СТРУКТУРАХ

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

79

Пусть необходимо выполнить некоторую математическую опе­ рацию над вектором входных переменных (аргументов)

где хг, ..., хп — значения аргументов операции (4.2); у — значение функции (результата) операции; ф — символ однозначной алгебраи­ ческой функции, не зависящей явно от времени.

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

1. Каждому аргументу лу, функции у и диапазону представимых чисел N сопоставляют соответствующие счетчики. В счетчики аргу­

ментов записывают количества им­

Гпульсов, дополняющие величины аргументов до полной емкости счетчиков N — х{.

F = F(xl t t), 0

4. Путем опроса счетчика результата генератором импульсов ча­ стоты / формируют, в случае необходимости, временной интервал Ту. Количество импульсов, записанных в счетчике результата за

время Т, будет, очевидно,

т

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

на полюс П подается пусковой сигнал, который устанавливает триг­

Счх, ..., Сч„+1 . Одновременно импульсы этого генератора синхро­ низируют работу управляемого преобразователя частоты /> , им-

80

зависимости от времени, в качестве датчика которого могут исполь­ зоваться импульсы генератора Г[ или внешние сигналы, подавае­ мые на полюс t, так и в зависимости от величин т,, пропорциональ­ ных х{, которые формируются триггерами 7\, ..., Тп по сигналам переполнения счетчиков аргументов. Схемы совпадения И1 и # 2 закроются по сигналу нулевого выхода триггера Тп+1, когда сиг­ нал переполнения счетчика Сч„+і установит его в единичное со­ стояние. При этом в счетчиках аргументов будет восстановлена исходная информация.

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

4.3. РЕАЛИЗАЦИЯ ЛИНЕЙНЫХ ОПЕРАЦИЙ

ВСЧЕТЧИКОВЫХ СТРУКТУРАХ

1.Инвертирование у = — х.

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

Рис. 40

ленного в позиционной системе счисления с основанием л и числом разрядов k, понимают разность пк — х. Так, десятичным трехраз­ рядным дополнением числа 039 будет 103 — 39 = 961. Схема, поз­ воляющая находить дополнения числа, изображена на рис. 40.

Счетчик Счх обеспечивает формирование временного интервала хх = x/f при подаче пускового сигнала на вход П1. Если первона­ чально установить счетчик Сч2 в нулевое состояние, то в нем в

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

которая является «-дополнением интервала хх.

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

впадения И3, управляемую нулевым выходом триггера Тг и единич­

ным выходом Т2 (рис. 41).

к

2. Сложение у = —2,vf. /=і

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

/

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

82

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

Рис. 42

интервалов производится одновременно, а счетчик результата за­ полняется тактовыми импульсами F переменной частоты.

Примем следующий закон модуляции F:

F = r(t)f,

где г (t) — количество неоконченных в момент t временных интер­

Ha рис. 43 приведена одна из возможных схем управляемого по закону (4.6) преобразователя частоты. Его основой является много­ ступенчатая линия задержки ЛЗ, возбуждаемая генератором им­ пульсов Г/ в течение времени Т. В схеме сумматора используется количество выходов ЛЗ, равное числу слагаемых. Входы схем сов­ падения Иг — Ик, выполняющих здесь функции управляемых кла­ панов, обозначенные на рис. 43 ту, подключаются к нулевым