Синтез автомата Мура с преобразованием расширенных кодов состояний

УДК 681.3

А.А. БАРКАЛОВ, Л.А. ТИТАРЕНКО, Е.П. ХЕБДА, К.А.СОЛДАТОВ

СИНТЕЗ АВТОМАТА МУРА С ПРЕОБРАЗОВАНИЕМ РАСШИРЕННЫХ КОДОВ СОСТОЯНИЙ

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

1. Введение

Практически каждая цифровая система включает устройство управления, координирующее работу всех ее блоков [1]. Одной из широко используемых моделей устройства управления является микропрограммный автомат (МПА) Мура [2,3]. В настоящее время для реализации схем быстродействующих МПА применяются программируемые логические интегральные схемы (ПЛИС), макроячейки которых включают блоки программируемой матричной логики (ПМЛ) [4,5]. Одной из особенностей ПМЛ является ограниченное число промежуточных шин (термов), что вызывает необходимость минимизации реализуемых функций [6,7]. Схема МПА Мура состоит из блока формирования функций возбуждения памяти (БВП) и блока формирования микроопераций (БМО), которые реализуются на ПМЛ. Известные методы синтеза МПА Мура [2] позволяют оптимизировать аппаратурные затраты только в одном из блоков МПА. В настоящей работе предлагается метод, позволяющий оптимизировать число ПМЛ в обоих блоках МПА Мура. Метод основан на

введении дополнительного преобразователя кодов и нестандартном представлении кодов состояний автомата.

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

Задача исследования состоит в разработке метода синтеза МПА Мура, позволяющего уменьшить число ПМЛ в схеме автомата.

2. Общее положение и основная идея предлагаемого метода

Пусть алгоритм управления задан в виде граф-схемы алгоритма (ГСА) Г, отмеченной состояниями автомата Мура [2]. Состояния МПА образуют множество A = {ai,... ,ам}, а для их кодирования используются внутренние переменные Tr е T = {Tj,..., Tr }. При этом число внутренних переменных определяется формулой

R = flog 2 M1.

В условных вершинах ГСА записаны логические условия (ЛУ) xi е X = {xj,..., xl } . В операторных вершинах ГСА записаны наборы микроопераций Yq с Y, где q = 1, Q, а Y = {yi- множество микроопераций.

Представление алгоритма управления в виде ГСА используется для построения прямой структурной таблицы (ПСТ) [2], имеющей столбцы: am - исходное состояние МПА; K(am) - код состояния am е A разрядности R;as - состояние перехода; K(as) - код состояния as; Xh - выходной сигнал, определяющий переход из am в as; Ф h - набор функций возбуждения регистра памяти (RG), определяющий переход из K(am) в K(as); h - номер строки ПСТ, где h = 1,Hi . В столбце am записывается номер микроопераций (НМО) Y(a m) = Yq , формируемых в состоянии am е A . Как правило, для реализации RG используется D-триггер. Поэтому множество функций возбуждения ф содержит элементы Dr (r = 1,R). Эта таблица является основой для формирования системы функций

Ф = Ф

Y = Y

Система (2) - (3) определяет логическую схему МПА Мура, представленную на рис. 1. В этой схеме блок БВП реализует систему (2), а блок БМО - систему (3). Условимся в дальнейшем обозначать схему на рис. 1 символом U1. При этом U1(Fj) означает, что автомат Мура U1 реализует ГСА Tj. Сигнал Start используется для установки МПА в начальное состояние, а сигнал Clock - для задания момента изменения содержимого RG.

Рис. 1. Структурная схема МПА и В МПА Мура число переходов Н значительно превосходит число Но переходов эквивалентного МПА Мили [2]. Однако соответствующее кодирование состояний позволяет уменьшить этот параметр, что уменьшает число ПМЛ в блоке БВП [8]. Для уменьшения числа ПМЛ в блоке БМО также используются различные методы кодирования состояний [3,8]. Однако не существует эффективного метода кодирования состояний, который одновременно оптимизирует оба блока.

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

Пусть множество А разбивается на I классов псевдоэквивалентных состояний, образующих разбиение Пд = {В1,...,В1}. Напомним, что состояния а^^ называются псевдоэквивалентными, если выходы отмеченных ими вершин ГСА связаны со входом одной и той же вершины [3]. Закодируем классы В^ е Пд кодами К(В^), имеющими Я1 разрядов:

Я1 =[1082 11.

Используем для кодирования классов переменные тг е т, где |т| = Я1. Пусть класс В^ е П д содержит М^ состояний и пусть

Мо = шах

Закодируем состояния ат е В^ кодом С(ат) разрядности

Я 2 =Г1о82Мо 1

и используем для кодирования переменные Тг е Т , где |т| = Я 2 .

В этом случае состояние ат е д однозначно определяется расширенным кодом

K(am) = K(Bi)*C(am),

где * - знак конкатенации, т = 1, М, { = 1, I.

Подставим в соответствие каждому набору Yq с У двоичный код K(Yq) разрядности

Яз =Г1о82 01.

Используем для кодирования НМО переменные 2Г е Ъ, где |Ъ| = Я3 . В этом случае для интерпретации ГСА Г предлагается МПА Мура И2 (рис. 2).

Т

— БВП Ф RG

—*

Clock

Y

Рис. 2. Структурная схема МПА и2

3. Метод синтеза автомата Мура И2

В автомате и2 блок БВП реализует систему функций

Ф = Ф

включающую Я1 + Я 2 элементов. Блок преобразователя кодов (ПК) формирует переменные е Ъ. Для этого реализуется система функций

Ъ = Ъ

Блок БМО реализует микрооперации уп е У, как функции системы

У = У

Такой подход даёт следующие преимущества по сравнению с МПА И: - число термов в системе (9) гарантировано равняется Но при любом кодировании классов В^ е П д;

т

- кодирование наборов Уq с У может быть выполнено таким образом, чтобы минимизировать число ПМЛ в блоке БМО.

Недостатками являются увеличение числа функций в системе ф при выполнении условия

Я! + Я2 > Я ,

а также наличие блока ПК. Отметим, что кодирование классов Б^ еПд и состояний ат е Б^ можно выполнить так, чтобы уменьшить число ПМЛ в блоке ПК. При выполнении условия

Я3 < Я

уменьшаются аппаратурные затраты в блоке БМО, если он реализуется на заказных матрицах [9] либо макроячейках памяти [3].

В настоящей работе предлагается метод синтеза МПА и2, включающий следующие этапы:

1. Формирование разбиения П д .

2. Формирование наборов микроопераций Yq с У .

3. Оптимальное кодирование НМО.

4. Кодирование классов Б^ е П д и состояний ат е Б^.

5. Формирование прямой структурной таблицы МПА и2 .

6. Формирование систем функций (9) - (10).

7. Реализация схемы МПА в заданном элементном базисе.

Рассмотрим пример синтеза МПА и2(П), где ГСА Г представлена на рис. 3.

Рис. 3. Граф-схема алгоритма Г1} отмеченная состояниями автомата Мура

Как видно из рис. 3, автомат и2(Г1) имеет М = 10 состояний, что дает Я = 4 . Исходя из определения псевдоэквивалентных состояний [3], можно найти множество

ПА = {ВЬ...,В4>. Здесь В1 = (ах), = {а2,аз,а4}, В3 = {а5,к,а8}, В4 = {а9,аш}. Итак, I = 4, Ях = 2.

В операторных вершинах ГСА Г находятся Q = 7 различных НМО: Ух = У(ах) = 0 ,

У2 = {У1,У2,У7} , у3 = {У3,У5,У6} , У4 = ^ЪУЗ^Ь У5 = {У1,У2,У6,У8} , У6 = {У2, У4, У5} , У7 = {У2, У4, Уб}. Таким образом, для кодирования НМО достаточно Я3=3 переменные и Ъ = {21,22,23} . Отметим, что условие (13) в данном случае выполняется.

Будем понимать под «оптимальным» такое кодирование НМО, когда система (11) имеет минимально возможное число термов. На рис. 4 представлен один из вариантов такого кодирования.

00 01 11 10

У1 У3 У4 *

У7 У6 У2 У;

Рис. 4. Оптимальные коды наборов микроопераций С учётом этих кодов имеем систему (14) для автомата и2(Г\):

У1 = У2 VУ4 VУ5 = 22; У2 = У2 VУб VУ5 VУ7 = 21; У3 = У3 У4 = 2123;У4 = У6 VУ7 = 2122; У5 = У3 VУ6 = 2223;У6 = У3 У5 VУ7 = 212223 V 2123; У7 = У2 VУ4 = 2223; 28 = У5 = 2223.

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

автомата и2(Г\) (табл. 1).

Таблица 1

К(Уц) 001 011 100 101 110 111

ат а3 а4, а9 а8' а10 а7 а5 а2' а6

У3 У4 У7 У6 У5 У2

В каждом столбце табл.1 первый разряд кода К(Уд) соответствует переменной второй - 22 и третий - 23 . Это позволяет построить следующую систему функций:

21 = а2 V а5 V а6 V а7 V а8 V адо;

22 = а2 Vа4 Vа6 Vа9;

23 = а2 V а3 V а4 V а6 V а7 V а9.

Состояния ат е А должны быть закодированы так, чтобы у всех ат е В^ код К(В^) совпадал.

Оптимизация системы (15) - это типичная задача символьного кодирования. Методы решения подобных задач можно найти в [1]. Один из вариантов оптимального кодирования классов Вх е Па и состояний ат е В^ представлен на рис. 5.

Используя коды из рис. 5, можно получить следующую систему (16) из системы (15):

21 =т2Т1 VT1T2 V Т1Т1Т2;

22 = Т1Т2 V Т2Т2;

23 = Т2 2.

5

Т1Т2

00 01 11 10

00 01 11 10

а1 * * *

* а2 а4 а3

а5 аб а7 а8

* * а9 аю

Рис. 5. Кодирование классов и состояний автомата И2(Г]) Если для реализации блока ПК используются ПМЛ, имеющие q = 3 терма, то каждая функция е Ъ реализуется на одной макроячейке ПМЛ.

Для построения ПСТ необходимо получить систему обобщённых формул перехода [3]. В случае МПА И2(Г^) эта система имеет следующий вид:

В^ ^ х^а2 V х^х2а3 VХ^х2а4;

В2 ^ Х2Х3а5 V Х2Х3аб V Х2Х4а7 V Х2Х4а8;

В3 ^ х3а9 V Х2Х3а10 VХ2Х3а8;

В4 ^а^.

Эта система очевидным образом преобразовывается в таблицу переходов (табл. 2).

Таблица 2

В! К(В!) а8 К(а8) Хь ф Ь Ь

В1 00 а2 0101 Х1 Б2Б4 1

а3 0110 Х1Х2 Б2Б3 2

а4 0111 Х1Х2 020304 3

В2 01 а5 1100 Х2Х3 0102 4

а6 1101 Х2Х3 О1О2О4 5

а7 1111 Х2Х4 01020304 6

а8 1110 Х2Х4 010203 7

В3 11 а9 1011 Х3 010304 8

а10 1010 Х3Х2 0103 9

а8 1110 Х3Х2 010203 10

Из табл. 2 строится система (9), которая затем минимизируется для реализации на макроячейках ПМЛ. Пусть Бь - терм, соответствующий строке Ь ПСТ. Например,

=Т1Т2Х1, Бдо =Т1Т2Х3Х2 . Из табл. 2 имеем, например, 0^ = Б4 V ... V Бдо. После минимизации получаем окончательную функцию 0^ = т 2 . Аналогичным образом можно получить остальные функции системы (9).

Последний этап синтеза связан с реализацией схем блоков МПА по полученным системам функций. Этот этап достаточно полно рассмотрен в литературе [6,7]. Имеются промышленные пакеты [4,5], ориентированные на решение подобных задач. В этой связи данный этап в этой статье не рассматривается.

Отметим, что ПСТ автомата И^(Г^) имеет Н = 23 строки. При этом каждая функция 0Г е Б будет иметь до 23 термов. Применение предложенного метода уменьшает этот параметр в 2,3 раза. При этом число функций 0Г е ф будет одинаковым для И^(Г^) и И2 (Г2) из-за нарушения условия (12).

4. Заключение

Предлагаемый в работе метод синтеза МПА Мура ориентирован на уменьшение аппаратурных затрат в схеме автомата. Этот метод позволяет гарантированно уменьшить число макроячеек ПМЛ в схемах формирования функций возбуждения памяти и микроопераций. Однако это связано с введением дополнительного блока ПК, который потребляет некоторые ресурсы кристалла ПЛИС и вносит задержку в схему МПА. Эти недостатки можно уменьшить путем оптимального кодирования расширенных кодов состояний.

Исследование эффективности предложенного метода на стандартных примерах [10] показали, что предложенный метод позволяет уменьшить аппаратурные затраты на 37 % (в среднем) для 98,2 % примеров. При этом быстродействие МПА U2 практически совпадает с этим параметром МПА Ui. Это объясняется уменьшением числа уровней в схемах блоков МПА U2 .

Научная новизна предложенного метода заключается в использовании классов псевдоэквивалентных состояний и кодов состояний в этих классах для уменьшения числа макроячеек ПМЛ в схеме МПА Мура.

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

Дальнейшее направление развития этой работы связано с возможностью применения предложенного метода для базиса FPGA [11] и заказных матриц [12].

Список литературы: 1. DeMicheli G. Synthesis and Optimization of Digital Circuits. №4.: McGran-Hill, 1994.636 p. 2. Baranov S. Logic and System Design of Digital Systems. Tallinn: TUT Press, 2008. 267 p. 3. Barkalov A., Titarenko L. Logic Synthesis for FSM-Based Control Units. Springer. Lectures Notes in Electrical Engineering. №53 Berlin: Verlag Heidelberg, 2009. 233 p. 4. Altera Corporation webpage. http// www.altera.com 5. Xilins Corporation webpage. http//www.xilinx.com 6. Соловьев В.В. Проектирование цифровых систем на основе программируемых логических интегральных схем. М.: Горячая линия -Телеком, 2007. 636 с. 7. Kania D. Synteza logiczna przeznaczona dla matrycowych struktur programowalnych typu PAL. Gliwice: Politechnika. 2004. 212 str. 8. Barkalov A., Titarenko L., Chmielewski S. Hardware reduction for Moor FSM implemented with CPLD // KEiT PAN, 2009. 212 p. 9. Barkalov A., Titarenko L., Hebda O. Matrix implementation of Moore FSM with expansion of coding space // Pomiary Automatyka Kontrola.vol.56. 2010. № 7. 694 - 696 p. 10. YangS. Logic Synthesis and Optimization Benchmarks user guide. Technical report №1991 IWLS-UG Saeyang. - Microelectronics center of North Carolina. 11. Maxfield C. The Design Warrior's Guide to FPGAs. Amsterdam: Elseveir, 2004. 541 p. 12. Smith M. Application Specific Integrated Circuits. Boston: Addison-Wesley, 1997.

Поступила в редколлегию 22.11.2010

Баркалов Александр Александрович, д-р техн. наук, профессор Института информатики и электроники Университета Зеленогурского. Адрес: ul. prof. Z. Szafrana 2, 65-516 Zielona Gjra, е-mail: A.Barkalov@iie.uz.zgora.pl.

Титаренко Лариса Александровна, д-р. техн. наук, профессор Института информатики и электроники Университета Зеленогурского. Адрес: ul. prof. Z. Szafrana 2, 65-516 Zielona Gjra, е-mail: L.Titarenko@iie.uz.zgora.pl.

Хебда Елена Петровна, магистр, аспирант Института информатики и электроники Университета Зеленогурского. Адрес: ul. prof. Z. Szafrana 2, 65-516 Zielona Gуra, е-mail: O. Shapoval@weit.uz.zgora.pl.

Солдатов Константин Альбертович, магистр, аспирант кафедры компьютерной инженерии Донецкого национального технического университета. Адрес: Украина, 83000, Донецк, ул. Артема, 56, е-mail: K.Soldatov@cs.dgtu.donetsk.ua