Оптимизация логической схемы автомата Мура на CPLD

Оптимизация логической схемы автомата Мура на CPLD

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

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2007
Hauptverfasser: Баркалов, А.А., Матвиенко, А.В., Цололо, С.А.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2007
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/6473
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Оптимизация логической схемы автомата Мура на CPLD / А.А. Баркалов, А.В. Матвиенко, С.А. Цололо // Комп’ютерні засоби, мережі та системи. — 2007. — № 6. — С. 46-51. — Бібліогр.: 10 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-6473
record_format dspace
spelling Баркалов, А.А.
Матвиенко, А.В.
Цололо, С.А.
2010-03-04T14:23:50Z
2010-03-04T14:23:50Z
2007
Оптимизация логической схемы автомата Мура на CPLD / А.А. Баркалов, А.В. Матвиенко, С.А. Цололо // Комп’ютерні засоби, мережі та системи. — 2007. — № 6. — С. 46-51. — Бібліогр.: 10 назв. — рос.
1817-9908
https://nasplib.isofts.kiev.ua/handle/123456789/6473
681.324
Предлагается метод уменьшения числа макроячеек PAL в логической схеме микропрограммного автомата Мура. Метод основан на использовании свободных выходов встроенных блоков памяти для представления кодов классов псевдоэквивалентных состояний. Предлагаемый подход позволяет уменьшить аппаратурные затраты без уменьшения призводительности цифровой системы.
Method of decrease of number of PAL macrocells in the circuit of Moore FSM is proposed. Method is based on usage of free outputs of embedded memory blocks to represent the codes of the classes of the pseudoequivalent states. Proposed approach permits to decrease the hardware amount without decrease of digital system performance.
ru
Інститут кібернетики ім. В.М. Глушкова НАН України
Оптимизация логической схемы автомата Мура на CPLD
Optimization of logic circuit of Moore FSM on CPLD
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Оптимизация логической схемы автомата Мура на CPLD
spellingShingle Оптимизация логической схемы автомата Мура на CPLD
Баркалов, А.А.
Матвиенко, А.В.
Цололо, С.А.
title_short Оптимизация логической схемы автомата Мура на CPLD
title_full Оптимизация логической схемы автомата Мура на CPLD
title_fullStr Оптимизация логической схемы автомата Мура на CPLD
title_full_unstemmed Оптимизация логической схемы автомата Мура на CPLD
title_sort оптимизация логической схемы автомата мура на cpld
author Баркалов, А.А.
Матвиенко, А.В.
Цололо, С.А.
author_facet Баркалов, А.А.
Матвиенко, А.В.
Цололо, С.А.
publishDate 2007
language Russian
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
format Article
title_alt Optimization of logic circuit of Moore FSM on CPLD
description Предлагается метод уменьшения числа макроячеек PAL в логической схеме микропрограммного автомата Мура. Метод основан на использовании свободных выходов встроенных блоков памяти для представления кодов классов псевдоэквивалентных состояний. Предлагаемый подход позволяет уменьшить аппаратурные затраты без уменьшения призводительности цифровой системы. Method of decrease of number of PAL macrocells in the circuit of Moore FSM is proposed. Method is based on usage of free outputs of embedded memory blocks to represent the codes of the classes of the pseudoequivalent states. Proposed approach permits to decrease the hardware amount without decrease of digital system performance.
issn 1817-9908
url https://nasplib.isofts.kiev.ua/handle/123456789/6473
citation_txt Оптимизация логической схемы автомата Мура на CPLD / А.А. Баркалов, А.В. Матвиенко, С.А. Цололо // Комп’ютерні засоби, мережі та системи. — 2007. — № 6. — С. 46-51. — Бібліогр.: 10 назв. — рос.
work_keys_str_mv AT barkalovaa optimizaciâlogičeskoishemyavtomatamuranacpld
AT matvienkoav optimizaciâlogičeskoishemyavtomatamuranacpld
AT cololosa optimizaciâlogičeskoishemyavtomatamuranacpld
AT barkalovaa optimizationoflogiccircuitofmoorefsmoncpld
AT matvienkoav optimizationoflogiccircuitofmoorefsmoncpld
AT cololosa optimizationoflogiccircuitofmoorefsmoncpld
first_indexed 2025-11-25T22:31:33Z
last_indexed 2025-11-25T22:31:33Z
_version_ 1850565649535860736
fulltext Комп’ютерні засоби, мережі та системи. 2007, № 6 46 A.A. Barkalov, A.V. Matvienko, S.A. Tsololo OPTIMIZATION OF LOGIC CIRCUIT OF MOORE FSM ON CPLD Method of decrease of number of PAL macrocells in the circuit of Moore FSM is proposed. Method is based on usage of free outputs of embedded memory blocks to represent the codes of the classes of the pseudoequivalent states. Pro- posed approach permits to decrease the hardware amount without de- crease of digital system perfor- mance. Предлагается метод уменьшения числа макроячеек PAL в логиче- ской схеме микропрограммного автомата Мура. Метод основан на использовании свободных вы- ходов встроенных блоков памяти для представления кодов классов псевдоэквивалентных состояний. Предлагаемый подход позволяет уменьшить аппаратурные за- траты без уменьшения призводи- тельности цифровой системы.  А.А. Баркалов, А.В. Матвиенко, С.А. Цололо, 2007 УДК 681.324 А.А. БАРКАЛОВ, А.В. МАТВИЕНКО, С.А. ЦОЛОЛО ОПТИМИЗАЦИЯ ЛОГИЧЕСКОЙ СХЕМЫ АВТОМАТА МУРА НА CPLD Устройство управления (УУ) является важ- ной частью любой цифровой системы, ко- ординирующим взаимодействие всех бло- ков системы [1, 2]. Для представления УУ на практике часто используется модель микро- программного автомата (МПА) Мура [3, 4]. В настоящее время успехи в развитии мик- роэлектроники позволяют реализовать доста- точно сложную цифровую систему, исполь- зуя единственную микросхему типа «сис- тема-на-кристалле» (SoC, system-on-a-chip) [5, 6]. При этом системы булевых функций могут быть реализованы, используя макро- ячейки PAL (programmable array logic) мик- росхемы SoC, если последняя использует технологию CPLD (complex programmable lo- gic devices) [7]. В то же время табличные функции могут быть реализованы с исполь- зованием встроенных блоков памяти EMB (embedded memory blocks) микросхемы SoC [3]. Одной из актуальных проблем в области проектирования УУ в этом базисе является минимизация аппаратурных затрат [4]. Ре- шение данной проблемы позволяет умень- шить площадь кристалла, занимаемую схе- мой УУ, и тем самым дает возможность уве- личения числа функций системы в рамках одного кристалла. Для решения этой задачи необходимо учитывать как особенности эле- ментного базиса, так и особенности модели УУ [3]. Особенностями PAL являются боль- шой коэффициент объединения по входу (достигающий сотен) и крайне ограниченное число термов в макроячейке [8, 6]. Особен- ностями МПА Мура являются наличие псев- ОПТИМИЗАЦИЯ ЛОГИЧЕСКОЙ СХЕМЫ АВТОМАТА МУРА НА CPLD Комп’ютерні засоби, мережі та системи. 2007, № 6 47 доэквивалентных состояний и регулярный характер системы микроопераций, что позволяет реализовать схему формирования микроопераций на блоках EMB микросхемы SoC [9, 10]. В настоящей работе предлагается метод оптимизации числа макроячеек PAL в логической схеме МПА Мура, основанный на учете вышеотмеченных особенностей. Пусть алгоритм управления цифровой системы представлен в виде граф- схемы алгоритма (ГСА) [4] ( , )B E   , где   210, EEbbB E  – множе- ство вершин; E – множество дуг. Здесь 0b – начальная вершина; Eb – конеч- ная вершина; 1E – множество операторных вершин; 2E – множество условных вершин. Вершина 1Ebq  содержит набор микроопераций   YbY q  , где  NyyY ,...,1 – множество микроопераций операционного автомата цифровой системы [6]. Вершина 2Ebq  содержит логическое условие Xxe  , где  LxxX ,...,1 – множество логических условий [1]. Начальная и конечная вершины ГСА соответствуют начальному состоянию Aa 1 , где  MaaA ,...,1 – множество внутренних состояний МПА Мура. Каждая операторная вершина 1Ebq  соответствует уникальному состоянию Aam  , при этом Y(bq)  Y(am). Логическая схема МПА Мура 1U задается системой булевских функций:  ,T X  , (1)  TYY  , (2) где  RTTT ,...,1 – множество внутренних переменных, кодирующих состоя- ния Aam  ,  2 log R M ;  RDD ,...,1 – множество функций возбуж- дения триггеров регистра памяти МПА. Структурная схема МПА Мура 1U показана на рис. 1. CC RG CMO Start Clock X T Y РИС. 1. Структурная схема микропрограммного автомата Мура U1 А.А. БАРКАЛОВ, А.В. МАТВИЕНКО, С.А. ЦОЛОЛО Комп’ютерні засоби, мережі та системи. 2007, № 6 48 В этой структуре комбинационная схема CC формирует функции (1), которые представляют собой функции возбуждения D триггеров регистра RG. Схема формирования микроопераций CMO реализует систему (2). Одиночный импульс Start используется для загрузки кода исходного состояния МПА в регистр RG, синхроимпульс Clock используется для изменения содержимого RG из кода  maK текущего состояния Aam  в код  SaK состояния перехода AaS  . В случае микросхемы SoC, ориентированной на технологию CPLD, схема CC реализуется на макроячейках PAL, а схема CMO реализуется на встроенных блоках памяти EMB [6]. Основой для формирования систем (1), (2) является прямая структурная таблица (ПСТ) автомата Мура со столбцами: ma – текущее состояние МПА;  maK – код текущего состояния, имеющий R разрядов; Sa – состояние пере- хода,  SaK – код состояния перехода; hX – конъюнкция некоторых элементов множества X (или их отрицаний), вызывающая переход Sm aa , ;  h – набор функций возбуждения, принимающих единичное значение для пере- ключения регистра RG из  maK в  SaK ; h – номер перехода (h = 1,…,H1(Г)). Кроме того, столбец ma содержит набор микроопераций   YaY m  , форми- руемых в этом состоянии. Как правило, число переходов Н1(Г) превышает число переходов Н2(Г) эквивалентного МПА Мили [9]. Это приводит к росту числа макроячеек PAL (аппаратурных затрат), а иногда – и к росту числа уровней в схеме CC автомата Мура по сравнению с этими характеристиками эквивалентного автомата Мили [4]. Величина Н1(Г) может быть уменьшена за счет учета наличия псевдоэквивалентных состояний (ПЭС) автомата Мура [1]. Состояния ,m Sa a A называются ПЭС, если выходы отмеченных ими вершин ГСА связанны с входом одной и той же вершины ГСА  . Пусть  1,...,A IB B  – разбиение множества состояний A на классы ПЭС  MI  . Закодируем каждый класс AiB  двоичным кодом  iBK , имеющим  IR 21 log разрядов. Используем для такого кодирования переменные rτ τ , причем 1| τ | R . В этом случае в схему МПА 1U может быть введен специальный преоб- разователь кодов TC, который формирует коды классов  iBK на основе кодов состояний  maK , где im Ba  . В этом случае схема CC формирует функции  τ, X  , (3) а схема TC формирует функции  τ τ T . (4) ОПТИМИЗАЦИЯ ЛОГИЧЕСКОЙ СХЕМЫ АВТОМАТА МУРА НА CPLD Комп’ютерні засоби, мережі та системи. 2007, № 6 49 В силу регулярного характера системы (4) схема TC реализуется с исполь- зованием блоков EMB, входящих в SoC [3]. В работе [9] доказано, что система (3) имеет Н2(Г) термов. Однако такой подход имеет один недостаток: для реализации схемы преобразователя кодов необходимы дополнительные блоки памяти EMB. В настоящей работе предлагается метод синтеза МПА Мура, позволяющий минимизировать аппаратурные затраты в схеме CC без введения преобразова- теля кодов. Предлагаемый метод основывается на следующих особенностях базиса CPLD [6 – 8]: - коэффициент объединения по входу макроячейки PAL значительно превы- шает максимально возможное число литералов в термах системы (1), определяе- мый как RL  ; - число выходов блока EMB может быть фиксировано и выбрано из множе- ства {1, 2, 4, 8}. Пусть Ft – фиксированное число выходов блока EMB и пусть q – число слов блока при 1Ft . Величина Ft для МПА 1U определяется следующим образом: ] / [ F t q M . Общее число выходов St всех блоков EMB схемы CMO определяется следующим образом:   FFS t*t/Nt  . В этом случае NtSt  (5) выходов не используются для представления микроопераций ny Y . Представим множество A как CBA  , где BiB  , если вы- полняется условие 1iB , в противном случае CiB  . Очевидно, что блок TC должен формировать только коды классов BiB  . Закодируем каждый класс BiB  двоичным кодом  iBK , имеющим  2 2 1log 1R M     (6) разрядов, где BM 1 и единица в формуле (6) добавляется для учета ситуации, когда BiB  . Используем для такого кодирования переменные Zzr  , где 2RZ  . Рассмотрим случай выполнения условия 2t R  . (7) При этом для интерпретации ГСА  предлагается МПА Мура U2 (рис. 2). А.А. БАРКАЛОВ, А.В. МАТВИЕНКО, С.А. ЦОЛОЛО Комп’ютерні засоби, мережі та системи. 2007, № 6 50 CC RG CMOC Start Clock X T Y  Z РИС. 2. Структурная схема автомата Мура U2 В этой структуре схема CC формирует функции  XZT ,, , (8) а схема CMOC формирует функции (2) и функции  TZZ  . Переменные TTr  представляют коды состояний  maK , где im Ba  и CiB  . Такой подход позволяет уменьшить число термов в системе функций  до Н2(Г), причем число блоков EMB в схемах CMO и CMOC совпадает. Как можно видеть, схема МПА U2 не включает блок TC. Число входов в макроячейках PAL автомата U2 увеличивается до 2RRL  , но это не приводит к увеличению аппаратурных затрат в схеме CC по сравнению с МПА Мура с блоком TC. В худшем случае времена циклов для автоматов U1 и U2 совпадают. В лучшем случае схема CC автомата U2 имеет меньше уровней, чем схема CC автомата U1, при этом время цикла МПА U2 будет меньше времени цикла МПА U1. Следовательно, предлагаемый подход позволяет уменьшить аппаратурные затраты без уменьшения производительности цифровой системы. Метод проектирования логической схемы МПА U2 отличается от метода проектирования схемы МПА U1 [4] только в некоторых деталях. Эти отличия связаны с необходимостью определения параметров (5)  (7) и формирования модифицированной ПСТ для формирования системы функций (8). ОПТИМИЗАЦИЯ ЛОГИЧЕСКОЙ СХЕМЫ АВТОМАТА МУРА НА CPLD Комп’ютерні засоби, мережі та системи. 2007, № 6 51 Предложенный в настоящей работе метод позволяет уменьшить число мак- роячеек PAL в схеме формирования функций возбуждения триггеров регистра памяти МПА Мура. Исследования авторов показали, что это уменьшение про- порционально значению коэффициента   Н1(Г) / Н2(Г). Необходимо отметить, что величина параметра Н2(Г) равняется числу переходов эквивалентного автомата Мили. При этом автоматы являются экви- валентными в том смысле, что они интерпретируют одну и ту же ГСА. Примене- ние предложенного метода имеет смысл только при выполнении условия (7). Это условие справедливо, если блоки схемы CMOC имеют достаточное число свободных выходов для представления кодов классов псевдоэквивалентных состояний. Наши исследования показали, что в рассматриваемых примерах аппаратурные затраты в схеме МПА Н2(Г) были на 26–28 % меньше, чем в схеме МПА U1(Г). 1. Adamski M., Barkalov A. Architectural and Sequential Synthesis of Digital Devices. – Zielona Gora: University of Zielona Gora Press, 2006. – 199 p. 2. De Micheli G. Synthesis and Optimization of Digital Circuits. – New York: McGraw Hill, 1994. – 578 p. 3. Barkalov A., Wegrzyn W. Design of Control Units with Programmable Logic. – Zielona Gora: University of Zielona Gora Press, 2006. – 150 p. 4. Baranov S. Logic Synthesis for Control Automata. – Boston: Kluwer Academic Publishers, 1994. – 312 p. 5. Maxfield C. The Design Warrior’s Guide to FPGA. – New Jersey: Elsevier, 2004. – 542 p. 6. Соловьев В.В. Проектирование цифровых схем на основе программируемых логических интегральных схем. – М.: Горячая линия-ТЕЛЕКОМ, 2001. – 636 с. 7. Грушницкий Р.И., Мурсаев А.Х., Угрюмов Е.П. Проектирование систем на микросхемах программируемой логики. – Петербург: БХВ, 2002. – 636 с. 8. Kania D. Synteza logiczna przeznaczona dla matrycowych struktur programowalnych typu PAL. – Gliwice: Zeszyty naukowe Politechniki Śląskiej, 2004. – 240 p. 9. Баркалов А.А. Принципы оптимизации логической схемы микропрограммного автомата Мура // Кибернетика и системный анализ. – 1998. – № 1. – С. 65– 72. 10. Баркалов А.А. Синтез устройств управления на программируемых логических устройст- вах. – Донецк: ДНТУ, 2002. – 262 с. Получено 10.05.2007

Ähnliche Einträge