Структурная декомпозиция как средство оптимизации схемы автомата Мили на ПЛИС
Запропоновано дві моделі схеми мікропрограмного автомата Мілі, що базуються на перетворенні кодів об’єктів. Методи синтезу орієнтовані на ПЛІС типу FPGA, що включають вбудовані блоки пам’яті. Для зменшення числа логічних елементів у схемі автомата запропоновано зменшувати кількість нерегулярних функ...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2012 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84044 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Структурная декомпозиция как средство оптимизации схемы автомата Мили на ПЛИС / А.А. Баркалов, Л.А. Титаренко, А.А. Баркалов (мл.) // Кибернетика и системный анализ. — 2012. — Т. 48, № 2. — С. 177-187. — Бібліогр.: 15 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84044 |
|---|---|
| record_format |
dspace |
| spelling |
Баркалов, А.А. Титаренко, Л.А. Баркалов, А.А. (мл.) 2015-07-02T09:17:03Z 2015-07-02T09:17:03Z 2012 Структурная декомпозиция как средство оптимизации схемы автомата Мили на ПЛИС / А.А. Баркалов, Л.А. Титаренко, А.А. Баркалов (мл.) // Кибернетика и системный анализ. — 2012. — Т. 48, № 2. — С. 177-187. — Бібліогр.: 15 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84044 004.383.3 Запропоновано дві моделі схеми мікропрограмного автомата Мілі, що базуються на перетворенні кодів об’єктів. Методи синтезу орієнтовані на ПЛІС типу FPGA, що включають вбудовані блоки пам’яті. Для зменшення числа логічних елементів у схемі автомата запропоновано зменшувати кількість нерегулярних функцій у його описі. Наведено приклад синтезу і результати досліджень для методу, який ґрунтується на перетворенні кодів наборів мікрооперацій у коди станів автомата. Two models of logic circuit are proposed for Mealy FSM. The models target on FPGA with embedded memory blocks and are based on transformation of the object codes. To decrease the number of LUT elements, it is proposed to decrease the number of irregular functions representing FSM. Both example of design and results of experiments are given for the method based on transformation of the codes of collections of microoperations into state codes of FSM. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Новые средства кибернетики, информатики, вычислительной техники и системного анализа Структурная декомпозиция как средство оптимизации схемы автомата Мили на ПЛИС Структурна декомпозиція як засіб оптимізації схеми автомата Мілі на ПЛІС Structural decomposition as a tool for optimization of Mealy FSM logic circuit on FPGA Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Структурная декомпозиция как средство оптимизации схемы автомата Мили на ПЛИС |
| spellingShingle |
Структурная декомпозиция как средство оптимизации схемы автомата Мили на ПЛИС Баркалов, А.А. Титаренко, Л.А. Баркалов, А.А. (мл.) Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| title_short |
Структурная декомпозиция как средство оптимизации схемы автомата Мили на ПЛИС |
| title_full |
Структурная декомпозиция как средство оптимизации схемы автомата Мили на ПЛИС |
| title_fullStr |
Структурная декомпозиция как средство оптимизации схемы автомата Мили на ПЛИС |
| title_full_unstemmed |
Структурная декомпозиция как средство оптимизации схемы автомата Мили на ПЛИС |
| title_sort |
структурная декомпозиция как средство оптимизации схемы автомата мили на плис |
| author |
Баркалов, А.А. Титаренко, Л.А. Баркалов, А.А. (мл.) |
| author_facet |
Баркалов, А.А. Титаренко, Л.А. Баркалов, А.А. (мл.) |
| topic |
Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| topic_facet |
Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| publishDate |
2012 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Структурна декомпозиція як засіб оптимізації схеми автомата Мілі на ПЛІС Structural decomposition as a tool for optimization of Mealy FSM logic circuit on FPGA |
| description |
Запропоновано дві моделі схеми мікропрограмного автомата Мілі, що базуються на перетворенні кодів об’єктів. Методи синтезу орієнтовані на ПЛІС типу FPGA, що включають вбудовані блоки пам’яті. Для зменшення числа логічних елементів у схемі автомата запропоновано зменшувати кількість нерегулярних функцій у його описі. Наведено приклад синтезу і результати досліджень для методу, який ґрунтується на перетворенні кодів наборів мікрооперацій у коди станів автомата.
Two models of logic circuit are proposed for Mealy FSM. The models target on FPGA with embedded memory blocks and are based on transformation of the object codes. To decrease the number of LUT elements, it is proposed to decrease the number of irregular functions representing FSM. Both example of design and results of experiments are given for the method based on transformation of the codes of collections of microoperations into state codes of FSM.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84044 |
| citation_txt |
Структурная декомпозиция как средство оптимизации схемы автомата Мили на ПЛИС / А.А. Баркалов, Л.А. Титаренко, А.А. Баркалов (мл.) // Кибернетика и системный анализ. — 2012. — Т. 48, № 2. — С. 177-187. — Бібліогр.: 15 назв. — рос. |
| work_keys_str_mv |
AT barkalovaa strukturnaâdekompoziciâkaksredstvooptimizaciishemyavtomatamilinaplis AT titarenkola strukturnaâdekompoziciâkaksredstvooptimizaciishemyavtomatamilinaplis AT barkalovaaml strukturnaâdekompoziciâkaksredstvooptimizaciishemyavtomatamilinaplis AT barkalovaa strukturnadekompozicíââkzasíboptimízacííshemiavtomatamílínaplís AT titarenkola strukturnadekompozicíââkzasíboptimízacííshemiavtomatamílínaplís AT barkalovaaml strukturnadekompozicíââkzasíboptimízacííshemiavtomatamílínaplís AT barkalovaa structuraldecompositionasatoolforoptimizationofmealyfsmlogiccircuitonfpga AT titarenkola structuraldecompositionasatoolforoptimizationofmealyfsmlogiccircuitonfpga AT barkalovaaml structuraldecompositionasatoolforoptimizationofmealyfsmlogiccircuitonfpga |
| first_indexed |
2025-11-24T21:09:27Z |
| last_indexed |
2025-11-24T21:09:27Z |
| _version_ |
1850497631471534080 |
| fulltext |
ÓÄÊ 004.383.3
À.À. ÁÀÐÊÀËÎÂ, Ë.À. ÒÈÒÀÐÅÍÊÎ, À.À. ÁÀÐÊÀËÎÂ (ìë.)
ÑÒÐÓÊÒÓÐÍÀß ÄÅÊÎÌÏÎÇÈÖÈß ÊÀÊ ÑÐÅÄÑÒÂÎ
ÎÏÒÈÌÈÇÀÖÈÈ ÑÕÅÌÛ ÀÂÒÎÌÀÒÀ ÌÈËÈ ÍÀ ÏËÈÑ
Êëþ÷åâûå ñëîâà: ìèêðîïðîãðàììíûé àâòîìàò Ìèëè, ÏËÈÑ, ñòðóêòóðíàÿ
äåêîìïîçèöèÿ, âñòðîåííûå áëîêè ïàìÿòè.
ÂÂÅÄÅÍÈÅ
Ìîäåëü ìèêðîïðîãðàììíîãî àâòîìàòà (ÌÏÀ) Ìèëè [1] ÷àñòî èñïîëüçóåòñÿ äëÿ
ñèíòåçà óñòðîéñòâ óïðàâëåíèÿ [2]. Ðàçâèòèå ìèêðîýëåêòðîíèêè ïðèâåëî ê ïî-
ÿâëåíèþ ðàçíîîáðàçíûõ ñåìåéñòâ ïðîãðàììèðóåìûõ ëîãè÷åñêèõ èíòåãðàëüíûõ
ñõåì (ÏËÈÑ) [3, 4]. Ïðè ñèíòåçå ñõåì ÌÏÀ â áàçèñå ÏËÈÑ âîçíèêàåò ðÿä
îïòèìèçàöèîííûõ ïðîáëåì, îäíà èç íèõ — óìåíüøåíèå ÷èñëà ìàêðîÿ÷ååê
ÏËÈÑ â ëîãè÷åñêîé ñõåìå [5]. Ìåòîäû ðåøåíèÿ ýòîé çàäà÷è çàâèñÿò îò îñî-
áåííîñòåé ìîäåëè àâòîìàòà, àëãîðèòìà óïðàâëåíèÿ è ýëåìåíòíîãî áàçèñà [6].
 äàííîé ðàáîòå ðàññìàòðèâàåòñÿ çàäà÷à ðåàëèçàöèè ñõåìû ÌÏÀ Ìèëè â áà-
çèñå ÏËÈÑ òèïà FPGA (field-programmable gate array) [7, 8]. Ïîäîáíûå ÏËÈÑ
ñîñòîÿò èç ýëåìåíòîâ òàáëè÷íîãî òèïà (look-up table — LUT) è âñòðîåííûõ
áëîêîâ ïàìÿòè (embedded memory block — EMB). Óñëîâèìñÿ â äàëüíåéøåì
ïîä ÏËÈÑ ïîíèìàòü FPGA, à òàêæå ââåäåì îáîçíà÷åíèÿ ËÝ (ëîãè÷åñêèé ýëå-
ìåíò) äëÿ LUT è ÂÁÏ (âñòðîåííûé áëîê ïàìÿòè) äëÿ ÅÌÂ.
Êàê ïðàâèëî, ËÝ ðåàëèçóþò òàáëèöó èñòèííîñòè ïðîèçâîëüíîé áóëåâîé
ôóíêöèè, èìåþùåé 4–6 àðãóìåíòîâ [4]. Ýòî îãðàíè÷åíèå ïðèâîäèò ê íåîáõîäè-
ìîñòè ôóíêöèîíàëüíîé äåêîìïîçèöèè [5] ðåàëèçóåìûõ ñèñòåì áóëåâûõ ôóíêöèé
(ÑÁÔ). Ïðè ýòîì ñõåìà ïðèîáðåòàåò ìíîãîóðîâíåâûé õàðàêòåð, ÷òî óâåëè÷èâàåò
âðåìÿ òàêòà â ñëó÷àå ðåàëèçàöèè ÌÏÀ íà ÏËÈÑ. Äëÿ óìåíüøåíèÿ àïïàðàòóðíûõ
çàòðàò öåëåñîîáðàçíî èñïîëüçîâàòü ìåòîä ñòðóêòóðíîé äåêîìïîçèöèè [6], îñíî-
âàííûé íà óâåëè÷åíèè ÷èñëà ñòðóêòóðíûõ óðîâíåé ñõåìû ÌÏÀ.  äàííîé ðàáî-
òå ðàññìàòðèâàåòñÿ ìåòîä, çàêëþ÷àþùèéñÿ â êîäèðîâàíèè íåêîòîðûõ îáúåêòîâ
ÌÏÀ (íàïðèìåð, íàáîðîâ ìèêðîîïåðàöèé) è èõ ïîñëåäóþùåì äåêîäèðîâàíèè ñ
èñïîëüçîâàíèåì ÂÁÏ. Ýòî ïðèâîäèò ê ñáàëàíñèðîâàííîìó èñïîëüçîâàíèþ ðàç-
ëè÷íûõ ðåñóðñîâ ÏËÈÑ (ËÝ è ÂÁÏ), à òàêæå ê óìåíüøåíèþ ÷àñòè êðèñòàëëà, çà-
íÿòîé ñõåìîé ÌÏÀ [9]. Â íàñòîÿùåé ðàáîòå ðàññìàòðèâàþòñÿ ìåòîäû
ñòðóêòóðíîé äåêîìïîçèöèè ñõåìû ÌÏÀ Ìèëè, îñíîâàííîé íà ìåòîäå
ïðåîáðàçîâàíèÿ îáúåêòîâ [10]. Ýòè ìåòîäû àäàïòèðóþòñÿ ê îñîáåííîñòÿì ÏËÈÑ
ñî âñòðîåííûìè áëîêàìè ïàìÿòè.
1. ÎÑÍÎÂÍÛÅ ÏÎËÎÆÅÍÈß
Ìèêðîïðîãðàììíûé àâòîìàò Ìèëè ïðåäñòàâëÿåòñÿ âåêòîðîì [1]
S X Y A a� � �, , , , ,� � 1 , (1)
ãäå X x x
L
� { }1, ..., — ìíîæåñòâî âõîäíûõ ñèãíàëîâ (ëîãè÷åñêèõ óñëîâèé),
Y y y
N
� � �{ 1 � } — ìíîæåñòâî âûõîäíûõ ñèãíàëîâ (ìèêðîîïåðàöèé),
A a a
M
� � �{ }1 � — ìíîæåñòâî âíóòðåííèõ ñîñòîÿíèé. Äëÿ ñèíòåçà ñõåìû ÌÏÀ
ñîñòîÿíèÿ a A
m
� êîäèðóþòñÿ äâîè÷íûìè êîäàìè K a
m
( ) ðàçðÿäíîñòè R , ïðè
ýòîì äëÿ êîäèðîâàíèÿ èñïîëüçóþòñÿ âíóòðåííèå ïåðåìåííûå T T
r
� . Ôóíêöèÿ
ïåðåõîäîâ � îïðåäåëÿåò ñîñòîÿíèå ïåðåõîäà, à ôóíêöèÿ âûõîäîâ � — âûõîä-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2 177
© À.À. Áàðêàëîâ, Ë.À. Òèòàðåíêî, À.À. Áàðêàëîâ (ìë.), 2012
íîé ñèãíàë ÌÏÀ.  íà÷àëüíûé ìîìåíò âðåìåíè àâòîìàò íàõîäèòñÿ â íà÷àëü-
íîì ñîñòîÿíèè a A1 � . Íà ïðàêòèêå ôóíêöèÿ � ïðåäñòàâëÿåòñÿ ñèñòåìîé ôóíê-
öèé âîçáóæäåíèÿ ýëåìåíòîâ ïàìÿòè ÌÏÀ
� �� ( , )X T , (2)
ãäå � � � �{ }D D
R1 � . Àíàëîãè÷íî ôóíêöèÿ � ïðåäñòàâëÿåòñÿ ñèñòåìîé âûõîä-
íûõ ôóíêöèé
Y Y X T� ( , ) . (3)
Ïóñòü ÌÏÀ Ìèëè ïðåäñòàâëåí ïðÿìîé ñòðóêòóðíîé òàáëèöåé (ÏÑÒ) [1] ñî
ñòîëáöàìè: a
m
, K a
m
( ) , a
s
, K a
s
( ) , X
h
, Y
h
, �
h
, h. Çäåñü a A
m
� — èñõîäíîå ñî-
ñòîÿíèå ÌÏÀ; a A
s
� — ñîñòîÿíèå ïåðåõîäà; X
h
— âõîäíîé íàáîð, îïðåäåëÿþ-
ùèé ïåðåõîä � �a a
m s
, è îïðåäåëÿåìûé êîíúþíêöèåé íåêîòîðûõ ýëåìåíòîâ (èëè
èõ îòðèöàíèé) ìíîæåñòâà Õ ; Y Y
h
� — íàáîð âûõîäíûõ ôóíêöèé, ôîðìèðóåìûé
íà ïåðåõîäå � �a a
m s
, ; � �
h
� — íàáîð ôóíêöèé âîçáóæäåíèÿ, ïðèíèìàþùèõ
åäèíè÷íîå çíà÷åíèå äëÿ ïåðåêëþ÷åíèÿ ïàìÿòè ÌÏÀ èç K a
m
( ) â K a
s
( ) ;
h H� � �{ }1 � — íîìåð ïåðåõîäà. Êàæäàÿ ñòðîêà ÏÑÒ ïðåäñòàâëÿåòñÿ êîíúþíê-
òèâíûì òåðìîì
F X T h H
h h
r
R
r
mr
� � � �
�1
1
�
�( ), (4)
ãäå �mr �{ }0 1, — çíà÷åíèå r-ãî ðàçðÿäà êîäà K a
m
( ) ñîñòîÿíèÿ a A
m
� , çàïè-
ñàííîãî â h-é ñòðîêå ÏÑÒ, T T
r r
0
� , T T
r r
1
� ( , , )r R� �1 . Ïðè ýòîì ôóíêöèè
(2) è (3) ïðåäñòàâëÿþòñÿ â ñëåäóþùåì âèäå:
D C F r R
r
h
H
rh h
� � � ��
�1
1( )� , (5)
y C F n N
n
h
H
nh h
� � � ��
�1
1( )� , (6)
ãäå C C
rh nh
( ) — áóëåâà ïåðåìåííàÿ, ðàâíàÿ åäèíèöå, åñëè è òîëüêî åñëè â h-é
ñòðîêå ÏÑÒ çàïèñàí ñèìâîë D y
r n
( ).
Íà ðèñ. 1 ïðèâåäåíà ñòðóêòóðíàÿ ñõåìà ÌÏÀ Ìèëè, ðåàëèçóåìîãî íà îñíîâà-
íèè ñèñòåì (5), (6). Â ýòîé ìîäåëè êîìáèíàöèîííàÿ ñõåìà (ÊÑ) ðåàëèçóåò ôóíêöèè
(2), (3), à ðåãèñòð (Ðã) èñïîëüçóåòñÿ êàê
ïàìÿòü ñîñòîÿíèé. Ñèãíàë Start ïðèìå-
íÿåòñÿ äëÿ óñòàíîâêè ÌÏÀ â íà÷àëüíîå
ñîñòîÿíèå a A1 � , à ñèãíàë Clock — äëÿ
èçìåíåíèÿ ñîäåðæèìîãî Ðã. Òåîðåòè-
÷åñêè ýòà ìîäåëü ïðèâîäèò ê ðåàëèçà-
öèè (ñõåìå àâòîìàòà) ñ ìàêñèìàëüíûì
áûñòðîäåéñòâèåì. Óñëîâèìñÿ â äàëü-
íåéøåì îáîçíà÷àòü ýòó ìîäåëü
ñèìâîëîì S1.
2. ÐÅÀËÈÇÀÖÈß ÑÕÅÌ ÌÏÀ ÍÀ ÏËÈÑ
Ïðè èñïîëüçîâàíèè ÏËÈÑ òèïà FPGA ñõåìà ÊÑ è ðåãèñòð Ðã ðåàëèçóþòñÿ íà ËÝ,
èìåþùèõ S âõîäîâ ( )S
6 . Ïóñòü f Y
i
� �� — áóëåâà ôóíêöèÿ, ðåàëèçóåìàÿ
ñõåìîé ÊÑ, L f
i
( ) — ÷èñëî ëîãè÷åñêèõ óñëîâèé â òåðìàõ (4), âõîäÿùèõ â äèçúþíê-
òèâíóþ íîðìàëüíóþ ôîðìó (ÄÍÔ) ôóíêöèè f
i
( )i R N� � � �1 � . Åñëè âûïîëíÿ-
åòñÿ óñëîâèå
L f R S
i
( ) � � , (7)
178 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2
ÊÑ
Ðã
X
Y
Ô
Start
T
Clock
Ðèñ. 1. Ñõåìà àâòîìàòà Ìèëè
òî äëÿ ðåàëèçàöèè ôóíêöèè f
i
íåîá-
õîäèìî èñïîëüçîâàòü ìåòîäû ôóíêöè-
îíàëüíîé äåêîìïîçèöèè [11]. Ïðè
ýòîì ôóíêöèÿ f
i
ðåàëèçóåòñÿ â âèäå
ìíîãîóðîâíåâîé ñõåìû (ðèñ. 2).
Çäåñü T T X X
H
i
H
i
� �, — ìíî-
æåñòâà âíóòðåííèõ ïåðåìåííûõ è ëî-
ãè÷åñêèõ óñëîâèé, èñïîëüçóåìûõ ñîîò-
âåòñòâåííî äëÿ ðåàëèçàöèè ïîäôóíê-
öèé H
i
; T T X X
U
i
U
i
� �, — ìíîæåñòâà âíóòðåííèõ ïåðåìåííûõ è ëîãè÷åñêèõ
óñëîâèé, èñïîëüçóåìûõ ñîîòâåòñòâåííî äëÿ ðåàëèçàöèè ôóíêöèè f
i
. Ïðè ýòîì
| | | | | |H T X S
i
U
i
U
i
� �
(8)
è ìîãóò âûïîëíÿòüñÿ óñëîâèÿ
X X
T T
H
i
U
i
H
i
U
i
� � �
� � �
;
.
(9)
Åñëè âûïîëíÿåòñÿ óñëîâèå
| | | |T X S
H
i
H
i
�
, (10)
òî ðåçóëüòèðóþùàÿ ñõåìà èìååò äâà óðîâíÿ.  ïðîòèâíîì ñëó÷àå íåîáõîäèìî
ðåøàòü çàäà÷ó ôóíêöèîíàëüíîé äåêîìïîçèöèè äëÿ ôóíêöèé H
i
. Òàêèì îáðà-
çîì, ðåçóëüòèðóþùàÿ ñõåìà ìîæåò èìåòü ïðîèçâîëüíîå ÷èñëî óðîâíåé.
Îòìåòèì, ÷òî ÷èñëî óðîâíåé â ñõåìå ÊÑ, êàê è ÷èñëî ËÝ â íåé, â çíà÷èòåëü-
íîé ñòåïåíè çàâèñèò îò èñïîëüçóåìîãî ìåòîäà êîäèðîâàíèÿ ñîñòîÿíèé [5, 12].
Ýòà ïðîáëåìà â íàñòîÿùåé ñòàòüå íå ðàññìàòðèâàåòñÿ, à äëÿ êîäèðîâàíèÿ èñïîëü-
çóþòñÿ äâîè÷íûå êîäû ðàçðÿäíîñòè
� �
R M� log 2 . (11)
Íàçîâåì áóëåâó ôóíêöèþ f ðåãóëÿðíîé îòíîñèòåëüíî ÂÁÏ (r-ôóíêöèÿ),
åñëè ÷èñëî åå àðãóìåíòîâ íå ïðåâûøàåò ÷èñëà àäðåñíûõ âõîäîâ ÂÁÏ.  ïðîòèâ-
íîì ñëó÷àå íàçîâåì ôóíêöèþ íåðåãóëÿðíîé îòíîñèòåëüíî ÂÁÏ ( i-ôóíêöèÿ).
Óñëîâèìñÿ â äàëüíåéøåì âûðàæåíèå «îòíîñèòåëüíî ÂÁÏ» îïóñêàòü è íàçûâàòü
ôóíêöèè ñîîòâåòñòâåííî ðåãóëÿðíûìè è íåðåãóëÿðíûìè. Äëÿ ðåàëèçàöèè
r-ôóíêöèè ìîæíî èñïîëüçîâàòü ÂÁÏ, â òî âðåìÿ êàê i-ôóíêöèÿ ðåàëèçóåòñÿ íà
ëîãè÷åñêèõ ýëåìåíòàõ (â ñëó÷àå ÏËÈÑ) [13].  àâòîìàòàõ ñðåäíåé ñëîæíîñòè [1]
R L H� � �6 30 2000, , , ïðè ýòîì èìååòñÿ îêîëî 10
12
ðàçëè÷íûõ âõîäíûõ íàáîðîâ
äëÿ ñèñòåì ôóíêöèé � è Y . Ñëåäîâàòåëüíî, ôóíêöèè (2), (3) îòíîñÿòñÿ ê êëàññó
i-ôóíêöèé. Òàêèì îáðàçîì, äëÿ ðåàëèçàöèè ñõåìû ÌÏÀ S1 èñïîëüçóþòñÿ òîëüêî
ëîãè÷åñêèå ýëåìåíòû. Ïðè ýòîì íåò âîçìîæíîñòè èñïîëüçîâàòü ÂÁÏ, ò.å. íåò ñáà-
ëàíñèðîâàííîñòè â èñïîëüçîâàíèè ðåñóðñîâ êðèñòàëëà ÏËÈÑ.
3. ÑÒÐÓÊÒÓÐÍÀß ÄÅÊÎÌÏÎÇÈÖÈß ÑÕÅÌÛ ÀÂÒÎÌÀÒÀ
Ïóñòü Y Y
q
� — íàáîð ìèêðîîïåðàöèé, çàïèñàííûé â íåêîòîðîé ñòðîêå ÏÑÒ,
ãäå q Q�{1, ,� }. Ïîñòàâèì â ñîîòâåòñòâèå êàæäîìó íàáîðó Y
q
äâîè÷íûé êîä
K Y
q
( ) ðàçìåðíîñòè
� �
R Q
Y
� log 2 . (12)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2 179
H( f
i
)
U ( f
i
)
Ðèñ. 2. Ìíîãîóðîâíåâàÿ ñõåìà ôóíêöèè f
i
T
H
i
X
H
i
X
U
i
T
U
i
H
i
f
i
Èñïîëüçóåì äëÿ êîäèðîâàíèÿ íà-
áîðîâ Y Y
q
� ïåðåìåííûå z Z
r
� ,
ãäå | |Z R
Y
� . Ïðè ýòîì àâòîìàò
S1 ïðåîáðàçîâûâàåòñÿ â PY -àâòî-
ìàò [6], îáîçíà÷àåìûé â äàëüíåé-
øåì ñèìâîëîì S 2 (ðèñ. 3).
 ÌÏÀ S 2 ñõåìà ÊÑ1 ðåàëè-
çóåò ôóíêöèè (2) è ôîðìèðóåò ïå-
ðåìåííûå z Z
r
� , ïðåäñòàâëåííûå
â âèäå
Z Z X T� ( , ). (13)
Êîìáèíàöèîííàÿ ñõåìà ÊÑ2 ðåàëèçóåò ìèêðîîïåðàöèè y Y
n
� , ïðåäñòàâëåííûå
â âèäå
Y Y Z� ( ) . (14)
Ïîñêîëüêó ïàðàìåòð R
Y
îïðåäåëÿëñÿ ñîãëàñíî (12), ôóíêöèè (14) îòíîñÿòñÿ ê
êëàññó r-ôóíêöèé è ìîãóò áûòü ðåàëèçîâàíû íà ÂÁÏ. Òàêèì îáðàçîì, ÷èñëî
i-ôóíêöèé óìåíüøàåòñÿ îò k R N1 � � (àâòîìàò S1) äî k R R
Y2 � � .
Ðàññìîòðåííûé ìåòîä êîäèðîâàíèÿ íàáîðîâ ìèêðîîïåðàöèé îòíîñèòñÿ ê ìå-
òîäàì ñòðóêòóðíîé äåêîìïîçèöèè. Ïðè ýòîì óâåëè÷èâàåòñÿ ÷èñëî ñòðóêòóðíûõ
óðîâíåé ñõåìû, íî óìåíüøàåòñÿ ÷èñëî ËÝ â íåé (ïî ñðàâíåíèþ ñ àâòîìàòîì S1).
Òåïåðü ñõåìó ÌÏÀ ìîæíî ðåàëèçîâàòü íà ÏËÈÑ ñ ìåíüøèì ÷èñëîì ËÝ (ò.å. íà
áîëåå äåøåâîé ÏËÈÑ), ëèáî ñýêîíîìëåííûå ËÝ ìîæíî èñïîëüçîâàòü äëÿ ðåàëè-
çàöèè äðóãèõ áëîêîâ öèôðîâîé ñèñòåìû, ðàáîòàþùèõ ïîä óïðàâëåíèåì ÌÏÀ
Ìèëè. Î÷åâèäíî, ÷òî ýêîíîìèÿ ÷èñëà ËÝ òåì áîëüøå, ÷åì ìåíüøå i-ôóíêöèé íå-
îáõîäèìî ðåàëèçîâàòü. Àáñîëþòíûé ìèíèìóì ÷èñëà i-ôóíêöèé äîñòèãàåòñÿ ïðè
èñïîëüçîâàíèè ìåòîäà ïðåîáðàçîâàíèÿ êîäîâ îáúåêòîâ [10].
Íàçîâåì ñîñòîÿíèÿ a A
m
� è íàáîðû ìèêðîîïåðàöèé Y Y
q
� îáúåêòàìè
ÌÏÀ Ìèëè. Îñíîâíîé èäååé ìåòîäà ïðåîáðàçîâàíèÿ êîäîâ îáúåêòîâ ÿâëÿåòñÿ
ïðåäñòàâëåíèå, íàïðèìåð êîäîâ ñîñòîÿíèé (âòîðè÷íûõ îáúåêòîâ) êàê íåêîòîðûõ
ôóíêöèè îò íàáîðîâ ìèêðîîïåðàöèé (ïåðâè÷íûõ îáúåêòîâ) è äîïîëíèòåëüíûõ
ïåðåìåííûõ, îáåñïå÷èâàþùèõ îäíîçíà÷íîñòü òàêîãî ïðåäñòàâëåíèÿ [10]. Ðàñ-
ñìîòðèì ýòîò ìåòîä è ïîðîæäàåìóþ èì ñòðóêòóðó ÌÏÀ Ìèëè ñ ìàêñèìàëüíûì
êîäèðîâàíèåì íàáîðîâ ìèêðîîïåðàöèé.
Ïóñòü A Y A
q
( ) � — ìíîæåñòâî ñîñòîÿíèé ÌÏÀ, ïðè ïåðåõîäå â êîòîðûå
ôîðìèðóåòñÿ íàáîð Y Y
q
� , ãäå m A Y
q q
� | ( ) | . Ïóñòü K m m
Q
� � �max ( 1 � ) , òîãäà
äëÿ îäíîçíà÷íîé èäåíòèôèêàöèè ëþáîãî èç ñîñòîÿíèé a A Y
m q
� ( ) äîñòàòî÷íî
K èäåíòèôèêàòîðîâ, îáðàçóþùèõ ìíîæåñòâî I I I
K
� � �{ }1 � . Ïîñòàâèì â ñîîò-
âåòñòâèå ñîñòîÿíèþ a A Y
m q
� ( ) ïàðó �
mq mq q
I Y� � �, , ãäå èäåíòèôèêàòîð I
mq
îäíîçíà÷íî îïðåäåëÿåò ñîñòîÿíèå a A
m
� â ìíîæåñòâå A Y
q
( ). Çàêîäèðóåì íàáî-
ðû Y Y
q
� äâîè÷íûìè êîäàìè ðàçìåðíîñòè (12), à èäåíòèôèêàòîðû I I
k
� — äâî-
è÷íûìè êîäàìè K I
k
( ) ðàçðÿäíîñòè
� �
R K
I
� log 2 (15)
è èñïîëüçóåì äëÿ èõ êîäèðîâàíèÿ ïåðåìåííûå �
r
V� , ãäå | |V R
I
� . Òåïåðü
ïàðà �
mq
îäíîçíà÷íî îïðåäåëÿåò êîä
C a K Y K I
m q q mq
( ) ( )* ( )� , (16)
ãäå * — çíàê êîíêàòåíàöèè. Òàêîé ïîäõîä ïðèâîäèò ê ìîäåëè àâòîìàòà Ìèëè
S 3 (ðèñ. 4).
180 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2
ÊÑ1
Ðã
X Y
Ô
Start
ÊÑ2
T
Z
Clock
Ðèñ. 3. Ñõåìà àâòîìàòà Ìèëè S
2
 àâòîìàòå S 3 ñõåìà ÊÑ1 ðå-
àëèçóåò ñèñòåìû (13) è
V V X T� ( , ) , (17)
ñõåìà ÊÑ2 ðåàëèçóåò ñèñòåìó
(14), à ñõåìà ÊÑ3 ôîðìèðóåò
ôóíêöèè �, ïðåäñòàâëåííûå
â âèäå
� �� ( , )V Z . (18)
Êàê ïîêàçûâàåò àíàëèç, äëÿ
àâòîìàòîâ ñðåäíåé ñëîæíîñòè [1] ôóíêöèè (18) ìîãóò áûòü ðåàëèçîâàíû íà ÂÁÏ ñî-
âðåìåííûõ ÏËÈÑ [7, 8]. Òåïåðü ÷èñëî i-ôóíêöèé îïðåäåëÿåòñÿ êàê k R R
Y I3 � � .
Î÷åâèäíî, ÷òî k k3 2� ïðè âûïîëíåíèè óñëîâèÿ
R R
I
� . (19)
×åì áîëüøå ðàçíîñòü R R
I
� , òåì áîëüøèé âûèãðûø äàåò ïåðåõîä îò ìîäåëè
S 2 ê ìîäåëè S 3 .
Àíàëîãè÷íûì îáðàçîì ìîæíî ïîëó÷èòü ìîäåëü S 4 , îñíîâàííóþ íà ïðåîáðà-
çîâàíèè êîäîâ ñîñòîÿíèé â êîäû íàáîðîâ ìèêðîîïåðàöèé. Ïóñòü Y a
m
( ) — ìíî-
æåñòâî íàáîðîâ ìèêðîîïåðàöèé, ôîðìèðóåìûõ ïðè ïåðåõîäå â ñîñòîÿíèå
a A
m
� , è ïóñòü | ( ) |Y a Q
m m
� . Åñëè U Q Q
M
� � �max ( 1 � ), òî äëÿ îäíîçíà÷íîé
èäåíòèôèêàöèè ëþáîãî íàáîðà Y Y a
q m
� ( ) äîñòàòî÷íî U èäåíòèôèêàòîðîâ, îá-
ðàçóþùèõ ìíîæåñòâî I I I
U0 { }� � �1 � . Ïîñòàâèì â ñîîòâåòñòâèå êàæäîìó íàáîðó
Y Y a
q m
� ( ) ïàðó �
qm qm m
I a� � �, , ãäå èäåíòèôèêàòîð I
qm
îäíîçíà÷íî îïðåäåëÿ-
åò íàáîð Y Y
q
� â ìíîæåñòâå Y a
m
( ) . Çàêîäèðóåì íàáîðû Y Y
q
� äâîè÷íûìè êî-
äàìè ðàçìåðíîñòè (12), à èäåíòèôèêàòîðû I I
u
� 0 — äâîè÷íûìè êîäàìè
ðàçðÿäíîñòè
� �
R U
U
� log 2 (20)
è èñïîëüçóåì äëÿ èõ êîäèðîâàíèÿ ïåðåìåííûå w W
r
� , ãäå | |W R
U
� . Òåïåðü
ïàðà �
qm
îäíîçíà÷íî îïðåäåëÿåò êîä
C Y K a K I
q m m qm
( ) ( ) )* ( )� , (21)
ãäå * — çíàê êîíêàòåíàöèè. Ýòîò ïîäõîä ïðèâîäèò ê ìîäåëè àâòîìàòà Ìèëè
S 4 (ðèñ. 5).
 àâòîìàòå S 4 ñõåìà ÊÑ1 ðåàëèçóåò ñèñòåìû (2) è
W W X T� ( , ) , (22)
ñõåìà ÊÑ3 ðåàëèçóåò ñèñòåìó (13), à ñõåìà ÊÑ2 — ñèñòåìó
Z Z T W� ( , ) . (23)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2 181
ÊÑ1
Ðã
X Y
Ô
ÊÑ2
T
Z
ÊÑ3
V
Start
Clock
Ðèñ. 4. Ñõåìà àâòîìàòà Ìèëè S
3
ÊÑ1
Ðã
X
YÔ ÊÑ2T Z
ÊÑ3
W
Start
Clock
Ðèñ. 5. Ñõåìà àâòîìàòà Ìèëè S
4
Êàê è â ñëó÷àå àâòîìàòà S 3 , ñõåìû áëîêîâ ÊÑ2 è ÊÑ3 àâòîìàòà S 4 ìîãóò
áûòü ðåàëèçîâàíû íà ÂÁÏ. Òàêèì îáðàçîì, ÷èñëî i-ôóíêöèé òåïåðü îïðåäåëÿåòñÿ
êàê k R R
U4 � � . Åñëè
R R
U Y
� , (24)
òî àâòîìàò S 4 ÿâëÿåòñÿ àëüòåðíàòèâîé àâòîìàòó S 2 . Îòìåòèì, ÷òî âûáîð êîí-
êðåòíîé ìîäåëè èç ìíîæåñòâà { }S S S2 3 4, , îïðåäåëÿåòñÿ õàðàêòåðèñòèêàìè àë-
ãîðèòìà óïðàâëåíèÿ è ýëåìåíòíîãî áàçèñà.
4. ÐÅÀËÈÇÀÖÈß ÍÀ ÏËÈÑ ÀÂÒÎÌÀÒÎÂ Ñ ÏÐÅÎÁÐÀÇÎÂÀÍÈÅÌ ÊÎÄÎÂ ÎÁÚÅÊÒÎÂ
Õàðàêòåðíîé îñîáåííîñòüþ ñîâðåìåííûõ ÏËÈÑ [7, 8] ÿâëÿåòñÿ íàëè÷èå ÂÁÏ,
äëÿ êîòîðûõ ìîæíî âûáèðàòü ÷èñëî ñëîâ N
W
è èõ ðàçðÿäíîñòü L
W
ïðè íåêî-
òîðîé ôèêñèðîâàííîé åìêîñòè V0 :
V N L
W W0 � . (25)
Íàèáîëåå ÷àñòî V0 4� Kb, ïðè ýòîì áëîê ïàìÿòè ìîæåò áûòü îðãàíèçîâàí êàê
ÎÇÓ èëè ÏÇÓ ñî ñëåäóþùèìè õàðàêòåðèñòèêàìè: 4 1K x , 2 2Kx , 1 4Kx , 512 8x ,
256 16x . Ïî ìåðå ðîñòà ñòîèìîñòè ìèêðîñõåìû óâåëè÷èâàåòñÿ è ïàðàìåòð V0 .
 íàñòîÿùåå âðåìÿ ñóùåñòâóåò ÂÁÏ, íàïðèìåð, ñ õàðàêòåðèñòèêàìè îò 512õ36
äî 16Kx1 (áèò) [7, 8]. Ýòà îñîáåííîñòü ìîæåò èñïîëüçîâàòüñÿ ïðè ðåàëèçàöèè
ñõåì ÌÏÀ, îñíîâàííûõ íà ïðåîáðàçîâàíèè êîäîâ îáúåêòîâ.
Ïóñòü O �{ , , , , }1 2 4 8 16 — ìíîæåñòâî ôèêñèðîâàííûõ âûõîäîâ ÂÁÏ, âêëþ÷à-
þùåå ýëåìåíòû L
W
èç (25). Äëÿ ðåàëèçàöèè ñõåìû ÊÑ3 àâòîìàòà S 3 íåîáõîäèìî
N S
W
R R
Y I( )3 3 2�
� (26)
ñëîâ ÂÁÏ. Ïðè ýòîì ÂÁÏ áóäåò èìåòü
L S V N S
W W
( ) / ( )3 3 0 3 3� (27)
âûõîäîâ, îïðåäåëÿåìûõ ìíîæåñòâîì Î. Ïðè âûïîëíåíèè óñëîâèÿ
L S R
W
( )3 3 � (28)
÷àñòü ìèêðîîïåðàöèé y Y
n
�
ðåàëèçóþòñÿ ñõåìîé ÊÑ3.
Ïóñòü ýòè ìèêðîîïåðàöèè îá-
ðàçóþò ìíîæåñòâî Y
1
. Òåïåðü
áëîê ÊÑ2 ðåàëèçóåò îñòàâøè-
åñÿ ìèêðîîïåðàöèè, îáðàçóþ-
ùèå ìíîæåñòâî Y
2
. Åñòåñò-
âåííî, ÷òî Y Y
1 2
� � � è
Y Y Y
1 2
� � . Ðàñïðåäåëåíèå
ìèêðîîïåðàöèé ïî ìíîæåñò-
âàì Y
1
è Y
2
íå èìååò çíà-
÷åíèÿ. Íà ðèñ. 6 ïðèâåäåíà ñòðóêòóðíàÿ ñõåìà ÌÏÀ S 5 , îñíîâàííàÿ íà ðàçáè-
åíèè ìíîæåñòâà ìèêðîîïåðàöèé â ÌÏÀ S 3 .
Àíàëîãè÷íûì îáðàçîì ìîæåò áûòü ïðåîáðàçîâàíà è ìîäåëü S 4 , â êîòîðîé
íåîáõîäèìî
N S
W
R R
U( )4 2 2�
�
(29)
ñëîâ ÂÁÏ äëÿ ðåàëèçàöèè ñõåìû ÊÑ2. Ïðè ýòîì ÷èñëî âûõîäîâ ÂÁÏ îïðåäå-
ëÿåòñÿ êàê
L S V N S
W W
( ) / ( )4 2 0 4 2� . (30)
182 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2
ÊÑ1
Ðã
X Y
2
Ô
ÊÑ2
T
Z
ÊÑ3
V
Y
1
Start
Clock
Ðèñ. 6. Ñõåìà àâòîìàòà Ìèëè S
5
Ïðè âûïîëíåíèè óñëîâèÿ
L S R
W Y
( )4 2 � (31)
ìèêðîîïåðàöèè y Y
n
�
1
ðåàëèçóþòñÿ ñõåìîé ÊÑ2. Îñòàâøèåñÿ N L S R
W Y
� �( ( ) )4 2
ìèêðîîïåðàöèé îáðàçóþò ìíîæåñòâî Y
2
è ðåàëèçóþòñÿ ñõåìîé ÊÑ3. Ýòîò
ïîäõîä ïðåîáðàçîâûâàåò àâòîìàò S 4 â àâòîìàò S 6 (ðèñ. 7).
 íàñòîÿùåé ðàáîòå ïðåäëàãàåòñÿ ìåòîä ñèíòåçà àâòîìàòà S 5 , çàäàííîãî ïðÿ-
ìîé ñòðóêòóðíîé òàáëèöåé. Ìåòîä âêëþ÷àåò ñëåäóþùèå ýòàïû:
1) êîäèðîâàíèå íàáîðîâ ìèêðîîïåðàöèé Y Y
q
� ;
2) îäíîçíà÷íàÿ èäåíòèôèêàöèÿ ñîñòîÿíèé a A
m
� êîäàìè (16);
3) ïðåîáðàçîâàíèå èñõîäíîé ÏÑÒ;
4) ðàçáèåíèå ìíîæåñòâà ìèêðîîïåðàöèé;
5) ñïåöèôèêàöèÿ áëîêà ÊÑ2;
6) ñïåöèôèêàöèÿ áëîêà ÊÑ3;
7) ðåàëèçàöèÿ ñõåìû àâòîìàòà â çàäàííîì ýëåìåíòíîì áàçèñå.
 ýòîé ðàáîòå ìåòîä ñèíòåçà àâòîìàòà S 6 íå ðàññìàòðèâàåòñÿ; îí ÿâëÿåòñÿ
ïðåäìåòîì äàëüíåéøèõ èññëåäîâàíèé. Ðàññìîòðèì ïðèìåð ñèíòåçà ñõåìû àâòî-
ìàòà S 5 , çàäàííîãî ÏÑÒ (òàáë. 1).
5. ÏÐÈÌÅÐ ÑÈÍÒÅÇÀ ÀÂÒÎÌÀÒÀ S5
Êàê ñëåäóåò èç òàáë. 1, àâòîìàò S 5 èìååò ñëåäóþùèå õàðàêòåðèñòèêè: M � 5,
L � 4, N � 9, R � 3, H �12. Ïàìÿòü ÌÏÀ ðåàëèçîâàíà íà D-òðèããåðàõ, ÷òî íàèáî-
ëåå ÷àñòî èñïîëüçóåòñÿ íà ïðàêòèêå [14]. Êðîìå òîãî, èç òàáë. 1 ñëåäóåò, ÷òî àâòî-
ìàò S 5 èìååò Q � 7 ðàçëè÷íûõ íàáîðîâ ìèêðîîïåðàöèé Y1 � �, Y y y2 1 2� { , },
Y y y3 3 8� { , }, Y y4 4� { }, Y y y5 2 5� { , }, Y y y6 6 9� { }, , Y y y7 3 7� { }, .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2 183
ÊÑ1
Ðã
X
Ô ÊÑ2T
Z
ÊÑ3
W
Y
2
Y
1
Start
Clock
Ðèñ. 7. Ñõåìà àâòîìàòà Ìèëè S
6
Ò à á ë è ö à 1
am K am( ) as K as( ) Xh Yh �h h
a
1
000 a
2
001 x
1
y y
1 2
D
3
1
a
3
010 x
1
y y
3 8
D
2
2
a
2
001 a
2
001 x
2
y y
1 2
D
3
3
a
3
010 x x
2 3
y
4
D
2
4
a
4
011 x x
2 3
y y
1 2
D D
2 3
5
a
3
010 a
4
011 x
1
y y
2 5
D D
2 3
6
a
5
100 x
1
y y
6 9
D
1
7
a
4
011 a
5
100 1 y y
3 7
D
1
8
a
5
100 a
2
001 x x
2 3
y y
1 2
D
3
9
a
3
010 x x
2 3
y y
3 8
D
2
10
a
5
100 x x
2 4
y y
3 7
D
1
11
a
1
000 x x
2 4
— — 12
Êàê ñëåäóåò èç (12), R
Y
� 3 è äëÿ êîäèðîâàíèÿ íàáîðîâ èñïîëüçóþòñÿ ïåðå-
ìåííûå z Z z z z
r
� � { }1 2 3, , . Çàêîäèðóåì íàáîðû Y Y
q
� ñëåäóþùèì îáðàçîì:
K Y( 1 000) � ,…, K Y( )7 110� .
Èç òàáë. 1 ìîæíî íàéòè ñëåäóþùèå ìíîæåñòâà A Y
q
( ): A Y a( ) }1 1� { ,
A Y a a( ) , }2 2 4� { , A Y a( ) }3 3� { , A Y a( ) }4 3� { , A Y a( ) }5 4� { , A Y a( ) }6 5� { ,
A Y a( ) }7 5� { . Ñëåäîâàòåëüíî, m m m1 3 7 1� � � �� , m2 2� , K � 2, R
I
�1,
V � { }�1 , I I I� { }1 2, . Ïóñòü K I( )1 0� è K I( )2 1� . Ñôîðìèðóåì ïàðû �
mq
äëÿ
íàøåãî ïðèìåðà. Åñëè m
q
�1, òî èäåíòèôèêàòîð íå íóæåí è òàêàÿ ïàðà áóäåò
âêëþ÷àòü ñèìâîë � . Äëÿ àâòîìàòà S 5 èìååì: �11 1� �� �, Y , � 22 1 2� � �I Y, ,
� 42 2 2� � �I Y, , � 33 3� �� �,Y , � 34 4� �� �, Y , � 45 5� �� �, Y , � 56 6� �� �, Y è
� 57 7� �� �, Y .  òàáë. 2 ïðåäñòàâëåíû êîäû C a
m q
( ) äëÿ àâòîìàòà S 5 .
 òàáë. 2 ñèìâîë * ñîîòâåòñòâóåò íåîïðåäåëåííîìó çíà÷åíèþ èäåíòèôèêàòî-
ðà â ïàðå �
mq
. Ïîñòðîèì ïðåîáðàçîâàííóþ ÏÑÒ àâòîìàòà S 5 (òàáë. 3).
Äëÿ ïîñòðîåíèÿ ïðåîáðàçîâàííîé ÏÑÒ íåîáõîäèìî ñòîëáöû a
s
, K a
s
( ) è �
h
èñõîäíîé ÏÑÒ çàìåíèòü ñòîëáöàìè Z
h
è V
h
. Â ñòîëáöå �
mq
, èñïîëüçóåìîì êàê
êîììåíòàðèé, óêàçûâàåòñÿ ïàðà �
mq
, ñîîòâåòñòâóþùàÿ h-é ñòðîêå ÏÑÒ; â ñòîëá-
öå Z
h
çàïèñûâàþòñÿ ïåðåìåííûå z Z
r
� , ðàâíûå åäèíèöå â êîäå K Y
q
( ) äëÿ ïàðû
� �I Y
k q
, èç h-é ñòðîêè ÏÑÒ; â ñòîëáöå V
h
ñîäåðæèòñÿ êîä K I
k
( ) äëÿ ïàðû �
mq
,
ïðè ýòîì çíàê – îçíà÷àåò, ÷òî �
r
� 0, çíàê * — ÷òî çíà÷åíèå �
r
íå îïðåäåëåíî äëÿ
h-é ñòðîêè ÏÑÒ (h H�{ }1, ..., ).
Ïðåîáðàçîâàííàÿ ÏÑÒ èñïîëüçóåòñÿ äëÿ ôîðìèðîâàíèÿ ôóíêöèé (13) è (17).
Òàê, èç òàáë. 3 ìîãóò áûòü íàéäåíû ôóíêöèè z T T T T T x x1 1 2 1 2 3 2 4� � è
�1 1 2 3 2 3� T T T x x .
184 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2
Ò à á ë è ö à 2
am C am q( ) �mq m am C am q( ) �mq m
a
1
000* �
11
1 a
4
100* �
45
5
a
2
0010 �
22
2 a
4
0011 �
42
6
a
3
010* �
33
3 a
5
101* �
56
7
a
3
011* �
34
a
5
4 110* �
57
8
Ò à á ë è ö à 3
am K am( ) Xh Zh Vh h �mq
a
1
000 x
1
z
3
— 1 �
22
x
1
z
2
* 2 �
33
a
2
001 x
2
z
3
— 3 �
22
x x
2 3
z
2
z
3
* 4 �34
x x
2 3
z
3
�
1
5 �
42
a
3
010 x
1
z
1
* 6 �
45
x
1
z
1
z
3
* 7 �
56
a
4
011 1 z
1
z
2
* 8 �
57
a
5
100 x x
2 3
z
3
— 9 �
22
x x
2 3
z
2
* 10 �
33
x x
2 4
z
1
z
2
* 11 �
57
x x
2 4
— * 12 �
11
Ïóñòü äëÿ ðåàëèçàöèè ñõåìû ÌÏÀ èñïîëüçóþòñÿ ÏËÈÑ, ñîäåðæàùèå ÂÁÏ ñ
V0 64� è Q � { , , , }1 2 4 8 . Äëÿ ðåàëèçàöèè áëîêà ÊÑ3 íåîáõîäèìî âûáðàòü êîíôè-
ãóðàöèþ 16õ4, òàê êàê R R
Y I
� � 4 . Ïîñêîëüêó óñëîâèå (28) âûïîëíÿåòñÿ, òî
L S R
W
( )3 3 1� � , ò.å. îäèí âûõîä ñõåìû ÊÑ3 ìîæåò èñïîëüçîâàòüñÿ äëÿ ðåàëèçà-
öèè ìèêðîîïåðàöèé. Ïóñòü Y y
1
2� { }, òîãäà | |Y
2
8� è äëÿ ðåàëèçàöèè áëîêà
ÊÑ2 íåîáõîäèìî âûáðàòü ÂÁÏ ñ êîíôèãóðàöèåé 8õ8.
Äëÿ ñïåöèôèêàöèè áëîêà ÊÑ2 íåîáõîäèìî ïîñòðîèòü òàáëèöó ñî ñòîëáöàìè
Z
h
, Y
h
, h, ãäå Z
h
ñîäåðæèò êîä íàáîðà Y Y
q
� èç ñòîëáöà Y
h
; h H�{ }1 2, ..., — íî-
ìåð ñòðîêè.  íàøåì ñëó÷àå ýòà òàáëèöà èìååò Í 2 8� ñòðîê (òàáë. 4).
Äëÿ ñïåöèôèêàöèè áëîêà ÊÑ3 íåîáõîäèìî ïîñòðîèòü òàáëèöó ñî ñòîëáöàìè
Z
h
,V
h
, �
h
, Y
h
, h , ãäå h H�{ }1 3,..., — íîìåð ñòðîêè. Ñòîëáåö Y
h
ñîäåðæèò ìèêðî-
îïåðàöèè y Y
n
�
1
. Äëÿ àâòîìàòà S 5 ýòà òàáëèöà ñîäåðæèò Í 3 16� ñòðîê (òàáë. 5).
Ïîÿñíèì ïðèíöèï çàïîëíåíèÿ ýòîé òàáëèöû. Íàïðèìåð, y Y1
1
� è y Y1 2� . Ïîýòî-
ìó áèò y1 1� äëÿ ñòðîê 3 è 4 òàáëèöû, ñî-
îòâåòñòâóþùèõ K Y( 2 ). Ñîñòîÿíèå a2 ñî-
îòâåòñòâóåò êîäó 0010 (ñì. òàáë. 2), ïîý-
òîìó â ñòðîêå 3 òàáë. 5 çàïèñàíû
D D D1 2 3 1� � � , ÷òî ñîîòâåòñòâóåò
êîäó K a( ) )2 001� . Ñîñòîÿíèå a3 ñîîòâå-
òñòâóåò êîäàì 010* è 011* (cì. òàáë. 2),
ïîýòîìó åãî êîä 010 çàïèñàí â ñòðîêàõ
5, 6, 7 è 8 òàáë. 5.
Ðåàëèçàöèÿ ñõåìû ÌÏÀ S 5 ñâîäèòñÿ
ê ðåàëèçàöèè ñèñòåì (13) è (17) íà ËÝ è ê
ðåàëèçàöèè òàáëèö, çàäàþùèõ áëîêè ÊÑ2
è ÊÑ3, íà ÂÁÏ. Â íàñòîÿùåå âðåìÿ ñóùåñ-
òâóþò ýôôåêòèâíûå ìåòîäû ðåøåíèÿ ýòèõ
çàäà÷ [3, 4], ïîýòîìó ýòîò ýòàï íå ðàññìàò-
ðèâàåòñÿ. Îòìåòèì, ÷òî ïåðåõîä îò ìîäåëè
S 3 ê ìîäåëè S 5 ïîçâîëèë èñïîëüçîâàòü
òîëüêî äâà ÂÁÏ ñ V0 64� . Â ñõåìå, îïðå-
äåëÿåìîé ìîäåëüþ S 3 , òðåáîâàëîñü áû òðè
òàêèõ áëîêà. Ïðè ýòîì ÷èñëî ËÝ â ñõåìàõ
áëîêîâ ÊÑ1 äëÿ îáåèõ ìîäåëåé, îïðåäåëÿ-
åìûõ ÏÑÒ (ñì. òàáë. 1), îäèíàêîâî.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2 185
Ò à á ë è ö à 4
Zh
Yh
h
y
2
y
3
y
4
y
5
y
6
y
7
y
8
y
9
000 0 0 0 0 0 0 0 0 1
001 1 0 0 0 0 0 0 0 2
010 0 1 0 0 0 0 1 0 3
011 0 0 1 0 0 0 0 0 4
100 1 0 0 1 0 0 0 0 5
101 0 0 0 0 1 0 0 1 6
110 0 1 0 0 0 1 0 0 7
111 0 0 0 0 0 0 0 0 8
Ò à á ë è ö à 5
h Zh Vh
�h Yh
D
1
D
2
D
3
y
1
1 000 0 0 0 0 0
2 000 1 0 0 0 0
3 001 0 0 0 1 1
4 001 1 0 1 1 1
5 010 0 0 1 0 0
6 010 1 0 1 0 0
7 011 0 0 1 0 0
8 011 1 0 1 0 0
9 100 0 0 1 1 0
10 100 1 0 1 1 0
11 101 0 1 0 0 0
12 101 1 1 0 0 0
13 110 0 1 0 0 0
14 110 1 1 0 0 0
15 111 0 0 0 0 0
16 111 1 0 0 0 0
6. ÈÑÑËÅÄÎÂÀÍÈÅ ÏÐÅÄËÎÆÅÍÍÛÕ ÌÅÒÎÄÎÂ ÑÈÍÒÅÇÀ
Äëÿ îïðåäåëåíèÿ ýôôåêòèâíîñòè ïðåäëîæåííûõ ìåòîäîâ ñèíòåçà èñïîëüçîâà-
ëàñü áèáëèîòåêà LGSynth91 [15], ñîäåðæàùàÿ îïèñàíèÿ àâòîìàòîâ â ôîðìàòå
KISSII. Ýòè îïèñàíèÿ ÿâëÿþòñÿ ñòàíäàðòíûìè òåñòîâûìè ïðèìåðàìè, èñïîëü-
çóåìûìè äëÿ ñðàâíåíèÿ ðàçëè÷íûõ ìåòîäîâ ñèíòåçà ÌÏÀ [5]. Äëÿ ñèíòåçà
ñõåì ÌÏÀ èñïîëüçîâàëàñü ñèñòåìà AS [9], ðàñøèðåííàÿ ïðîãðàììàìè äëÿ
ñèíòåçà ñõåìû ÌÏÀ S 5 . Ñðàâíåíèå ïðîâîäèëîñü äëÿ ñõåì, îñíîâàííûõ íà îä-
íîóðîâíåâîé ìîäåëè (àâòîìàò S1), ìîäåëè ñ êîäèðîâàíèåì íàáîðîâ ìèêðîîïå-
ðàöèé (àâòîìàò S 2) è ìîäåëè ñ ïðåîáðàçîâàíèåì êîäîâ íàáîðîâ ìèêðîîïåðà-
öèé â êîäû ñîñòîÿíèé è ðàçáèåíèåì ìíîæåñòâà ìèêðîîïåðàöèé (àâòîìàò S 5).
Íåêîòîðûå ðåçóëüòàòû èññëåäîâàíèé ïðåäëîæåííûõ ìåòîäîâ ïîêàçàíû
â òàáë. 6. Ïðè ýòîì ñõåìû ÌÏÀ ñèíòåçèðîâàëèñü íà ìèêðîñõåìàõ Virtex V50 [8]
ôèðìû Xilinx.
 ýòîé òàáëèöå â ñòîëáöå ËÝ ïðèâåäåíî ÷èñëî LUT ýëåìåíòîâ, òðåáóåìûõ
äëÿ ðåàëèçàöèè êîìáèíàöèîííîé ñõåìû, à â ñòîëáöå ÂÁÏ — ÷èñëî âñòðîåííûõ
áëîêîâ ïàìÿòè, èñïîëüçóå-
ìûõ ñõåìàìè ÊÑ2 è ÊÑ3.
Íåîáõîäèìî îòìåòèòü, ÷òî
ïðîöåññ ñèíòåçà îñóùå-
ñòâëÿëñÿ ñèñòåìîé XST 8.1i
ôèðìû Xilinx, âõîäÿùåé â
ïàêåò ISE 8.1i [8]. Ïðè èñ-
ïîëüçîâàíèè äðóãèõ ïàêå-
òîâ ðåçóëüòàòû ìîãóò áûòü
äðóãèìè. Èññëåäîâàíèÿ ïî-
êàçàëè, ÷òî ïðåäëîæåííûé
ìåòîä ïðàêòè÷åñêè âñåãäà
äàåò ëó÷øèå ðåçóëüòàòû,
÷åì åãî ïðîòîòèïû. Èññëå-
äîâàíèÿ ïðîâîäèëèñü äëÿ
47 òåñòîâûõ ïðèìåðîâ.
 ñðåäíåì èñïîëüçîâàíèå
ìîäåëè S 5 äëÿ ýòèõ àâòîìàòîâ ïîçâîëÿåò íà 38 % óìåíüøèòü ÷èñëî ËÝ ïî ñðàâíå-
íèþ ñ ìîäåëüþ S 2 è íà 42 % — ïî ñðàâíåíèþ ñ ìîäåëüþ S1. Âûèãðûø äîñòèãà-
åòñÿ çà ñ÷åò èñïîëüçîâàíèÿ ÂÁÏ è ðàçáèåíèÿ ìíîæåñòâà ìèêðîîïåðàöèé. Ýòè ðå-
çóëüòàòû îêàçàëèñü ëó÷øå, ÷åì ïðåäâèäåëîñü ïðè èñïîëüçîâàíèè âåðîÿòíîñòíîãî
ïîäõîäà, èñïîëüçóåìîãî äëÿ èññëåäîâàíèé â [10]. Ìîäåëèðîâàíèå, ïðîâåäåííîå
ñ ïîìîùüþ ýòîé ñèñòåìû, ïîäòâåðäèëî, ÷òî ïðåäëîæåííûå ìåòîäû ïîçâîëÿþò
ñîõðàíèòü ôóíêöèîíàëüíîñòü èñõîäíîãî àâòîìàòà.
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ðàáîòå ðàññìîòðåíà àäàïòàöèÿ ìåòîäà ïðåîáðàçîâàíèÿ êîäîâ îáú-
åêòîâ ïðè ðåàëèçàöèè ñõåìû àâòîìàòà Ìèëè â áàçèñå ÏËÈÑ ñ âñòðîåííûìè
áëîêàìè ïàìÿòè. Ýòîò ìåòîä îòíîñèòñÿ ê ìåòîäàì ñòðóêòóðíîé äåêîìïîçèöèè,
êîòîðàÿ âûïîëíÿåòñÿ ïåðåä ïðèìåíåíèåì ôóíêöèîíàëüíîé äåêîìïîçèöèè ðåà-
ëèçóåìûõ íåðåãóëÿðíûõ ôóíêöèé. Îñíîâíàÿ èäåÿ ìåòîäà çàêëþ÷àåòñÿ â óâåëè-
÷åíèè îòíîñèòåëüíîãî ÷èñëà ðåãóëÿðíûõ ôóíêöèé, äëÿ ðåàëèçàöèè êîòîðûõ
èñïîëüçóþòñÿ ÂÁÏ.
 ðàáîòå ðàññìîòðåíû äâå ìîäåëè àâòîìàòà Ìèëè, îñíîâàííûå íà ýòîì ïîä-
õîäå. Â ìîäåëè S 5 êîäû íàáîðîâ ìèêðîîïåðàöèé è íåêîòîðûå äîïîëíèòåëüíûå
ïåðåìåííûå ôîðìèðóþòñÿ ñõåìîé, ðåàëèçóåìîé íà ËÝ. Ýòè ïåðåìåííûå èñïîëü-
186 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2
Ò à á ë è ö à 6
Íàçâàí
èå
òåñòà
Àâòîìàò S1 Àâòîìàò S2 Àâòîìàò S5
ËÝ ÂÁÏ ËÝ ÂÁÏ ËÝ ÂÁÏ
cse 78 — 85 1 41 1
dk16 68 — 70 1 24 1
ex1 105 — 109 2 87 3
ex2 49 — 46 1 29 1
keyb 90 — 99 1 60 2
kirkman 58 — 138 1 56 1
planet 248 — 155 2 65 4
s1494 205 — 159 2 87 4
s298 951 — 843 1 252 4
sty5 199 — 182 1 78 1
çóþòñÿ äëÿ ôîðìèðîâàíèÿ ìèêðîîïåðàöèé è ôóíêöèé âîçáóæäåíèÿ ïàìÿòè ÌÏÀ.
Ýòà ÷àñòü ñõåìû ðåàëèçóåòñÿ íà ÂÁÏ.  ìîäåëè S 6 êîäû ñîñòîÿíèé è íåêîòîðûå
äîïîëíèòåëüíûå ïåðåìåííûå èñïîëüçóþòñÿ äëÿ ôîðìèðîâàíèÿ ìèêðîîïåðàöèé,
 îáîèõ ñëó÷àÿõ ìíîæåñòâî ìèêðîîïåðàöèé ðàçáèâàåòñÿ íà äâà êëàññà, ÷òî
ìîæåò óìåíüøèòü ÷èñëî áëîêîâ ïàìÿòè, èñïîëüçóåìûõ äëÿ ðåàëèçàöèè ðåãóëÿð-
íûõ ôóíêöèé.
 ðàáîòå èññëåäîâàíà ýôôåêòèâíîñòü ðåàëèçàöèè ñõåìû àâòîìàòà, îñíî-
âàííîé íà ìîäåëè S 5 , ïî ñðàâíåíèþ ñ îäíîóðîâíåâîé ñõåìîé ÌÏÀ è ñõåìîé,
îñíîâàííîé íà êîäèðîâàíèè íàáîðîâ ìèêðîîïåðàöèé. Ïðè ýòîì èñïîëüçîâàëèñü
ñòàíäàðòíûå òåñòîâûå ïðèìåðû èç áèáëèîòåêè LGSynth91 [15]. Èññëåäîâàíèÿ ïî-
êàçàëè, ÷òî ìîäåëü S 5 ïðàêòè÷åñêè âñåãäà ïðèâîäèò ê ñõåìàì ñ ìåíüøèì ÷èñëîì
ËÝ. Êðîìå òîãî, ïðåîáðàçîâàíèå êîäîâ îáúåêòîâ ñïîñîáñòâóåò áîëåå ñáàëàíñèðî-
âàííîìó èñïîëüçîâàíèþ ðåñóðñîâ êðèñòàëëà.
Äàëüíåéøèå íàïðàâëåíèÿ èññëåäîâàíèé ñâÿçàíû ñ ðàçðàáîòêîé ïðîãðàì-
ìíûõ ñðåäñòâ äëÿ ñèíòåçà ñõåìû àâòîìàòà S 6 . Ýòî ïîçâîëèò äåëàòü âûáîð ìåæäó
ìîäåëÿìè S 5 è S 6 , êîòîðûé ïðàêòè÷åñêè íåâîçìîæíî ïðîèçâåñòè àïðèîðè. Êðî-
ìå òîãî, íåîáõîäèìî èññëåäîâàòü âðåìåííûå õàðàêòåðèñòèêè ñõåì, îñíîâàííûõ
íà ìîäåëÿõ S1–S 6 , ÷òî ïîçâîëèò âûáèðàòü ìîäåëè, ïðèâîäÿùèå ê ñõåìàì
ñ òðåáóåìûìè õàðàêòåðèñòèêàìè ïî àïïàðàòóðíûì çàòðàòàì è áûñòðîäåéñòâèþ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. B a r a n o v S . Logic and system design of digital systems. — Tallinn: TUT Press, 2008. — 266 p.
2. M i n k s P . , E l i o t I . FSM — based digital design using verilog. — London: John Wiley & Sons,
2008. — 351 p.
3. Ã ð ó ø â è ö ê è é Ð . È . , Ì ó ð ñ à å â À . Õ . , Ó ã ð þ ì î â Å . Ï . Ïðîåêòèðîâàíèå ñèñòåì íà
ìèêðîñõåìàõ ïðîãðàììèðóåìîé ëîãèêè. — Ïåòåðáóðã: ÁÕÂ-Ïåòåðáóðã, 2002. — 636 ñ.
4. M a x f i e l d S . The design warrior’s guide to FPGAs. — Amsterdam: Elsevier, 2004. — 541 p.
5. D e M i c h e l i G . Synthesis and optimization of digital circuits. — N.Y.: McGraw Hill, 1994. —
626 p.
6. Á à ð ê à ë î â À . À . , Ò è ò à ð å í ê î Ë . À . Ñèíòåç ìèêðîïðîãðàììíûõ àâòîìàòîâ íà çàêàçíûõ
è ïðîãðàììèðóåìûõ ÑÁÈÑ. — Äîíåöê: ÓÍÈÒÅÕ, 2009. — 336 ñ.
7. www.altera.com
8. www.xilinx.com
9. B u k o w i e c A . Synthesis of finite state machines for programmable devices based on multi-level
implementation. — Zielona Gora: UZ Press, 2009. — 105 p.
10. B a r k a l o v A . , B a r k a l o v A . Design of Mealy finite state machines with transformation of ob-
ject codes // Appl. Mathematics and Comput. Sci. — 2005. — 15, N 1. — P. 151–158.
11. S c h o l l C . Functional decomposition with application to FPGA synthesis. — Boston: Kluwer
Academ. Publ., 2001. — 288 p.
12. Cz e r w i n s k i R . , K a n i a D . , K u l i s z I . FSM state encoding targeting at logic level mini-
mization // Bulletin of the Polish Academ. Sci. — 2006. — 54, N 4. — P. 479–487.
13. B a r k a l o v A . , T i t a r e n k o L. Logic Synthesis for FSM-based control units. — Berlin:
Springer, 2009. — 233 p.
14. Ñ î ë î â ü å â  .  . , Ê ë è ì î â è ÷ À . Ñ . Ëîãè÷åñêîå ïðîåêòèðîâàíèå öèôðîâûõ ñèñòåì íà
îñíîâå ïðîãðàììèðóåìûõ ëîãè÷åñêèõ èíòåãðàëüíûõ ñõåì. — Ì.: Ãîðÿ÷àÿ ëèíèÿ – Òåëåêîì,
2008. — 376 ñ.
15. Y a n g S . Logic Synthesis and optimization benchmarks user guide. Techn. Rep. N 1991 — IWLS
— UG — Saeyang. — Microelectronics Center of North Carolina, 1991. — 43 p.
Ïîñòóïèëà 28.09.2009
Ïîñëå äîðàáîòêè 02.02.2010
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 2 187
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Gray Gamma 2.2)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.3
/CompressObjects /Off
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages false
/CreateJDFFile false
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /LeaveColorUnchanged
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams true
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments false
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts false
/TransferFunctionInfo /Apply
/UCRandBGInfo /Remove
/UsePrologue false
/ColorSettingsFile (Color Management Off)
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 290
/ColorImageMinResolutionPolicy /Warning
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 600
/ColorImageDepth 8
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.01667
/EncodeColorImages true
/ColorImageFilter /FlateEncode
/AutoFilterColorImages false
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 290
/GrayImageMinResolutionPolicy /Warning
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 600
/GrayImageDepth 8
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 2.03333
/EncodeGrayImages true
/GrayImageFilter /FlateEncode
/AutoFilterGrayImages false
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 800
/MonoImageMinResolutionPolicy /Warning
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 2400
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/PDFX3:2003
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError false
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox false
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile (None)
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/Description <<
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000500044004600206587686353ef901a8fc7684c976262535370673a548c002000700072006f006f00660065007200208fdb884c9ad88d2891cf62535370300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef653ef5728684c9762537088686a5f548c002000700072006f006f00660065007200204e0a73725f979ad854c18cea7684521753706548679c300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002000740069006c0020006b00760061006c00690074006500740073007500640073006b007200690076006e0069006e006700200065006c006c006500720020006b006f007200720065006b007400750072006c00e60073006e0069006e0067002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f0073002000640065002000410064006f0062006500200050004400460020007000610072006100200063006f006e00730065006700750069007200200069006d0070007200650073006900f3006e002000640065002000630061006c006900640061006400200065006e00200069006d0070007200650073006f0072006100730020006400650020006500730063007200690074006f00720069006f00200079002000680065007200720061006d00690065006e00740061007300200064006500200063006f00720072006500630063006900f3006e002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f007500720020006400650073002000e90070007200650075007600650073002000650074002000640065007300200069006d007000720065007300730069006f006e00730020006400650020006800610075007400650020007100750061006c0069007400e90020007300750072002000640065007300200069006d007000720069006d0061006e0074006500730020006400650020006200750072006500610075002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f006200650020005000440046002000700065007200200075006e00610020007300740061006d007000610020006400690020007100750061006c0069007400e00020007300750020007300740061006d00700061006e0074006900200065002000700072006f006f0066006500720020006400650073006b0074006f0070002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea51fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e30593002537052376642306e753b8cea3092670059279650306b4fdd306430533068304c3067304d307e3059300230c730b930af30c830c330d730d730ea30f330bf3067306e53705237307e305f306f30d730eb30fc30d57528306b9069305730663044307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e30593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020b370c2a4d06cd0d10020d504b9b0d1300020bc0f0020ad50c815ae30c5d0c11c0020ace0d488c9c8b85c0020c778c1c4d560002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken voor kwaliteitsafdrukken op desktopprinters en proofers. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200066006f00720020007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c00690074006500740020007000e500200062006f007200640073006b0072006900760065007200200065006c006c00650072002000700072006f006f006600650072002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020007000610072006100200069006d0070007200650073007300f5006500730020006400650020007100750061006c0069006400610064006500200065006d00200069006d00700072006500730073006f0072006100730020006400650073006b0074006f00700020006500200064006900730070006f00730069007400690076006f0073002000640065002000700072006f00760061002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f0074002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a00610020006c0061006100640075006b006100730074006100200074007900f6007000f60079007400e400740075006c006f0073007400750073007400610020006a00610020007600650064006f007300740075007300740061002000760061007200740065006e002e00200020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740020006600f600720020006b00760061006c00690074006500740073007500740073006b0072006900660074006500720020007000e5002000760061006e006c00690067006100200073006b0072006900760061007200650020006f006300680020006600f600720020006b006f007200720065006b007400750072002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/DEU <FEFF004a006f0062006f007000740069006f006e007300200066006f00720020004100630072006f006200610074002000440069007300740069006c006c0065007200200037002e000d00500072006f006400750063006500730020005000440046002000660069006c0065007300200077006800690063006800200061007200650020007500730065006400200066006f0072002000680069006700680020007100750061006c0069007400790020007000720069006e00740069006e0067002e000d0028006300290020003200300031003000200053007000720069006e006700650072002d005600650072006c0061006700200047006d006200480020>
/ENU (Use these settings to create Adobe PDF documents for quality printing on desktop printers and proofers. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /NoConversion
/DestinationProfileName ()
/DestinationProfileSelector /NA
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure true
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles true
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /NA
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /LeaveUntagged
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [2834.646 2834.646]
>> setpagedevice
|