Уменьшение числа LUT-элементов в схеме совмещенного автомата
Предложен метод синтеза совмещенного микропрограммного автомата в базисе FPGA, позволяющий получить схему с минимальным числом элементов LUT и встроенных блоков памяти EMB. Минимизация достигается путем замены части множества логических условий и соответствующего кодирования состояний автомата. Прив...
Збережено в:
| Дата: | 2016 |
|---|---|
| Автори: | , , , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2016
|
| Назва видання: | Управляющие системы и машины |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/113332 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Уменьшение числа LUT-элементов в схеме совмещенного автомата / А.А. Баркалов, Л.А. Титаренко, Я.Е. Визор, А.В. Матвиенко, В.В. Горина // Управляющие системы и машины. — 2016. — № 3. — С. 16-22. — Бібліогр.: 15 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-113332 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1133322025-02-09T21:02:08Z Уменьшение числа LUT-элементов в схеме совмещенного автомата Зменшення числа LUT-елементів в схемі суміщеного автомата Synthesis of Combined Finite State Machine with FPGAs Баркалов, А.А. Титаренко, Л.А. Визор, Я.Е. Матвиенко, А.В. Горина, В.В. Технические средства информатики Предложен метод синтеза совмещенного микропрограммного автомата в базисе FPGA, позволяющий получить схему с минимальным числом элементов LUT и встроенных блоков памяти EMB. Минимизация достигается путем замены части множества логических условий и соответствующего кодирования состояний автомата. Приведен пример применения метода. Запропоновано метод синтезу суміщеного мікропрограмного автомата в базисі FPGA, що дозволяє отримати схему з мініма льним числом елементів LUT і вбудованих блоків пам'яті EMB. Мінімізація досягається шляхом заміни частини множини логічних умов та відповідного кодування станів автомата. Наведено приклад застосування методу. A method for synthesis of combined finite state machine (CFSM) with FPGA is proposed. An analysis of CFSM’s peculiarities is given. The main feature of CFSM is an existence of two types of the output signals. Mealy outputs depend on the both inputs and states. Moore outputs depend only on the states. The known methods of CFSM design and conditions for their application and the method of the logical conditions replacement is thoroughly analyzed. It allows using embedded memory locks (EMB) for implementing some part of CFSM circuit. It is shown that the situations are possible when not all address inputs of an EMB are used. The suggested method is based on using these free address inputs. It is proposed to connect a part of logical conditions with unused address inputs of EMB blocks. It allows diminishing for the number of look-up table (LUT) elements in the circuit of logical conditions replacement in comparison with known methods of CFSM design. It is proposed to replace some part of the logical conditions set by additional variables. A design method based on such partial replacement is proposed. The method allows obtaining a CFSM circuit with the minimum number of table elements LUTs and memory blocks EMBs. Some additional optimization are possible for the replacement block of the logical conditions due to a special state assignment. The main idea of the special state assignment is reduced the assignment neighbor codes for states with transitions depending on the same logical conditions. It allows diminishing the number of the literals in functions implemented of the block of the logical conditions replacement. An example of the studied method application is shown. The proposed method allows obtaining a circuit required minimum chip space and consuming minimum power in comparison with the known design methods. The conducted researches are based on some library of standard GSAs. The investigations show that for the majority of standard GSAs the proposed method produces the circuits with a single EMB. 2016 Article Уменьшение числа LUT-элементов в схеме совмещенного автомата / А.А. Баркалов, Л.А. Титаренко, Я.Е. Визор, А.В. Матвиенко, В.В. Горина // Управляющие системы и машины. — 2016. — № 3. — С. 16-22. — Бібліогр.: 15 назв. — рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/113332 004.274 ru Управляющие системы и машины application/pdf Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Технические средства информатики Технические средства информатики |
| spellingShingle |
Технические средства информатики Технические средства информатики Баркалов, А.А. Титаренко, Л.А. Визор, Я.Е. Матвиенко, А.В. Горина, В.В. Уменьшение числа LUT-элементов в схеме совмещенного автомата Управляющие системы и машины |
| description |
Предложен метод синтеза совмещенного микропрограммного автомата в базисе FPGA, позволяющий получить схему с минимальным числом элементов LUT и встроенных блоков памяти EMB. Минимизация достигается путем замены части множества логических условий и соответствующего кодирования состояний автомата. Приведен пример применения метода. |
| format |
Article |
| author |
Баркалов, А.А. Титаренко, Л.А. Визор, Я.Е. Матвиенко, А.В. Горина, В.В. |
| author_facet |
Баркалов, А.А. Титаренко, Л.А. Визор, Я.Е. Матвиенко, А.В. Горина, В.В. |
| author_sort |
Баркалов, А.А. |
| title |
Уменьшение числа LUT-элементов в схеме совмещенного автомата |
| title_short |
Уменьшение числа LUT-элементов в схеме совмещенного автомата |
| title_full |
Уменьшение числа LUT-элементов в схеме совмещенного автомата |
| title_fullStr |
Уменьшение числа LUT-элементов в схеме совмещенного автомата |
| title_full_unstemmed |
Уменьшение числа LUT-элементов в схеме совмещенного автомата |
| title_sort |
уменьшение числа lut-элементов в схеме совмещенного автомата |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| publishDate |
2016 |
| topic_facet |
Технические средства информатики |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/113332 |
| citation_txt |
Уменьшение числа LUT-элементов в схеме совмещенного автомата / А.А. Баркалов, Л.А. Титаренко, Я.Е. Визор, А.В. Матвиенко, В.В. Горина // Управляющие системы и машины. — 2016. — № 3. — С. 16-22. — Бібліогр.: 15 назв. — рос. |
| series |
Управляющие системы и машины |
| work_keys_str_mv |
AT barkalovaa umenʹšeniečislalutélementovvshemesovmeŝennogoavtomata AT titarenkola umenʹšeniečislalutélementovvshemesovmeŝennogoavtomata AT vizorâe umenʹšeniečislalutélementovvshemesovmeŝennogoavtomata AT matvienkoav umenʹšeniečislalutélementovvshemesovmeŝennogoavtomata AT gorinavv umenʹšeniečislalutélementovvshemesovmeŝennogoavtomata AT barkalovaa zmenšennâčislalutelementívvshemísumíŝenogoavtomata AT titarenkola zmenšennâčislalutelementívvshemísumíŝenogoavtomata AT vizorâe zmenšennâčislalutelementívvshemísumíŝenogoavtomata AT matvienkoav zmenšennâčislalutelementívvshemísumíŝenogoavtomata AT gorinavv zmenšennâčislalutelementívvshemísumíŝenogoavtomata AT barkalovaa synthesisofcombinedfinitestatemachinewithfpgas AT titarenkola synthesisofcombinedfinitestatemachinewithfpgas AT vizorâe synthesisofcombinedfinitestatemachinewithfpgas AT matvienkoav synthesisofcombinedfinitestatemachinewithfpgas AT gorinavv synthesisofcombinedfinitestatemachinewithfpgas |
| first_indexed |
2025-11-30T17:34:57Z |
| last_indexed |
2025-11-30T17:34:57Z |
| _version_ |
1850237621930819584 |
| fulltext |
16 УСиМ, 2016, № 3
Технические средства информатики
УДК 004.274
А.А. Баркалов, Л.А. Титаренко, Я.Е. Визор, А.В. Матвиенко, В.В. Горина
Уменьшение числа LUT-элементов в схеме совмещенного автомата
Предложен метод синтеза совмещенного микропрограммного автомата в базисе FPGA, позволяющий получить схему с мини-
мальным числом элементов LUT и встроенных блоков памяти EMB. Минимизация достигается путем замены части множества
логических условий и соответствующего кодирования состояний автомата. Приведен пример применения метода.
Ключевые слова: совмещенный автомат, FPGA, LUT, EMB, синтез, граф-схема алгоритма.
Запропоновано метод синтезу суміщеного мікропрограмного автомата в базисі FPGA, що дозволяє отримати схему з мініма-
льним числом елементів LUT і вбудованих блоків пам'яті EMB. Мінімізація досягається шляхом заміни частини множини ло-
гічних умов та відповідного кодування станів автомата. Наведено приклад застосування методу.
Ключові слова: суміщений автомат, FPGA, LUT, EMB, синтез, граф-схема алгоритму.
Введение. Любая цифровая система включает
устройство управления, для синтеза которого
часто используется модель микропрограммно-
го автомата (МПА) [1, 2]. Одна из моделей
МПА – совмещенный автомат, в котором су-
ществуют выходные сигналы двух типов [3].
Выходные сигналы типа Мили формируются
при переходе между состояниями. Выходные
сигналы типа Мура существуют в течение так-
та работы МПА [2, 3].
Для реализации схем цифровых систем в на-
стоящее время широко используются СБИС ти-
па FPGA (Field-Programmable Logic Arrays) [4,
5]. Два типа логических элементов, входящих в
FPGA, могут использоваться для реализации
схемы МПА. Первый из них – логические эле-
менты типа LUT (Look-Up Table), выходы кото-
рых могут быть связаны с входами триггеров.
Элементы LUT имеют ограниченное число вхо-
дов (S ≤ 6) и только один выход. Второй тип ло-
гических элементов – встроенные блоки памяти
типа EMB (Embedded Memory Blocks). Их важная
характеристика – реконфигурация, при которой
меняется число выходов (tF) и ячеек памяти (V).
При этом общая емкость (V0) есть константой:
0 2 A F
S tV ,
где SA – число адресных входов при данном
количестве выходов tF. Как правило, существу-
ют следующие конфигурации EMB: 32K×1,
16K×2, 8K×4, 4K×8, 2K×16, 1K×32, 512×64
(битов) [4, 5]. Это определяет следующие пары
вида SA, tF: 15, 1; 14, 2; 13, 4; 12, 8; 11, 16; 10,
32 и 9, 64.
При реализации МПА в базисе FPGA важно
уменьшать площадь кристалла, занимаемого
схемой. При этом улучшаются такие характе-
ристики МПА, как время распространения
сигналов и потребляемая мощность [6]. Один
из подходов для решения этой задачи – замена
элементов LUT блоками EMB [7–12]. Однако
до сих пор никто не рассматривал эту задачу
применительно к совмещенному МПА. В ста-
тье авторы предлагают одно из возможных ре-
шений и анализ условия его применения.
Особенности совмещенного МПА
Микропрограммный автомат задается шес-
тикомпонентным вектором:
1, , , , ,S A X Y a ,
где A = {a1,…,aM} – множество внутренних со-
стояний, X = {x1,…, xL} – множество входных
переменных, Y = {y1,…,yN} – множество выход-
ных переменных, δ – функция переходов, λ –
функция выходов, a1 A – начальное состоя-
ние. Функция δ служит для нахождения со-
стояния перехода as A на основе текущего
состояния am A и входных переменных:
,s ma a X . (1)
Для автомата Мили функция λ определяет
выходную переменную ynY:
,n my a X . (2)
УСиМ, 2016, № 3 17
Для автомата Мура выходные переменные
определяются только внутренними состояниями:
n my a . (3)
В совмещенном МПА множество Y = Y1UY2,
где Y1 – множество выходных переменных ти-
па Мили и Y2 – множество выходных перемен-
ных типа Мура.
Граф переходов совмещенного автомата S1
показан на рис. 1. Вершины графа соответ-
ствуют состояниям, а дуги – переходам между
ними. Выходы типа Мура показаны рядом с
вершинами, а выходы типа Мили – под дуга-
ми. Над дугами показаны входные сигналы,
вызывающие переход. Как следует из рис. 1,
A = {a1,…, a4}, X = {x1, x2}, Y1 = {y1, y2, y4, y6},
Y2 = {y3, y4, y5}. Это дает M = 4, L = 2, N1 = 4 и
N2 = 3, где N1 = |Y1| и N2 = |Y2|. Анализ множеств
Y1 и Y2 позволяет получить соотношение Y1∩
∩Y2=Ø.
Рис. 1. Граф переходов совмещенного автомата S1
Закодируем состояния ma A двоичными
кодами mK a , имеющими R разрядов:
MR 2log . (4)
Для кодирования состояний используем пе-
ременные Tr T, где T = {T1,...,TR}.
Коды состояний хранятся в памяти МПА,
которая обычно представляется регистром RG
с D-входами [2]. Для переключения памяти
используются функции возбуждения Dr Φ,
где Φ = {D1,…, DR}.
Для синтеза схемы совмещенного МПА не-
обходимо получить функции δ и λ. Функция (1)
определяется системой булевых функций (СБФ)
,T X . (5)
Системы (6) – (7) соответствуют функциям
(2) – (3):
1 1 ,Y Y T X ; (6)
2 2Y Y T . (7)
Системы (5) – (7) определяют структурную
схему, приведенную на рис. 2.
Блок КС1 генерирует функции (5) – (6), блок
КС1 – функции (7). Сигнал Start устанавливает
в RG нулевой код начального состояния 1a A .
Импульс Clock вызывает переключение RG,
что соответствует переходам МПА.
Рис. 2. Структурная схема совмещенного МПА
Реализация совмещенного МПА в базисе
FPGA
Наилучшим с учетом аппаратурных затрат
есть решение, при котором системы (5) – (7)
реализуются на одном блоке EMB. Обозначим
такую модель символом U1 (рис. 3, а).
а б
Рис. 3. Структурная схема автомата U1 (а) и U2 (б)
В МПА U1 (как и в других моделях) регистр
RG реализуется на элементах LUT, связанных с
D-триггерами [4, 6]. Если блоки EMB синхрон-
ны, то регистр отсутствует. При этом импуль-
сы Start и Clock поступают на соответствую-
щие входы EMB.
Модель U1 используется, если выполняется
следующее условие:
02R L N R V (8)
18 УСиМ, 2016, № 3
При этом содержимое EMB определяется
таблицей со столбцами mK a , X (определяет
адрес ячейки), Φ, Y1, Y2 (содержимое ячейки), q
(номер ячейки) – табл. 1.
Т а б л и ц а 1. Таблица блока EMB автомата S1
K(am) X Φ Y 1
Y 2
T1T2 x1x2 D1D2 y1y2y6 y3y4y5
q
00 00 10 010 000 1
00 01 10 010 000 2
00 10 01 100 000 3
00 11 01 100 000 4
01 00 00 001 110 5
01 01 00 001 110 6
01 10 00 001 110 7
01 11 00 001 110 8
10 00 11 001 001 9
10 01 11 000 001 10
10 10 11 001 001 11
10 11 11 000 001 12
11 00 00 000 101 13
11 01 00 000 101 14
11 10 00 000 101 15
11 11 00 000 101 16
Для автомата S1 необходимо R = 2, что
определяет множество T = {T1, T2,} и Φ = {D1,
D2,}. Поскольку L + R = 4, таблица EMB для
автомата S1 имеет 16 строк. При этом состоя-
ния am A закодированы тривиальным обра-
зом: K(a1) = 00, ... , K(a4) = 11.
Фактически табл. 1 есть таблицей истиннос-
ти функций (5) – (7). Переходы из любого сос-
тояния am A задаются четырьмя строками. В
общем случае, это число H(am) определяется
формулой:
L
maH 2 .
Связь между графом (рис. 1) и табл. 1 оче-
видна.
Анализ стандартных бенимарков [13] пока-
зал, что условие (8) выполняется для 76 про-
центов всех примеров. Если это условие нару-
шено, то в работах [7–12] предлагается исполь-
зовать метод замены входных переменных [1].
В этом случае множество X заменяется
множеством дополнительных переменных P =
= {P1,...,PG}, где G << L. Параметр G опреде-
ляется, как максимум из мощностей множеств
X(am) X, определяющих переход из состоя-
ний am A. Например, для автомата S1 имеют-
ся следующие множества: X(a1) = {x1}, X(a2) =
= X(a4) = Ø и X(a3) = {x2}. Это определяет па-
раметр G = 1 и множество P = {P1}.
Для замены PX необходимо найти си-
стему функций:
,P P T X . (9)
Система (9) реализуется на блоке LUTer,
что определяет модель U2 (рис. 3,б). Под тер-
мином LUTer принимаем схему, реализован-
ную на элементах LUT.
В автомате U2 блок EMB реализует систему
(7) и
,T P ;
1 1 ,Y Y T P .
Эта модель применима, если выполняется
условие:
02 VRNRG . (10)
Как показал анализ библиотеки [13], эта мо-
дель применима для 82 процентов примеров.
Для уменьшения аппаратурных затрат в схе-
ме U2 необходимо уменьшить число элементов
LUT в схеме блока LUTer. В статье предлагается
подход, позволяющий решить эту задачу.
Основная идея предлагаемого метода
Конфигурация блока EMB определяется па-
рой <SA, tF>. При увеличении SA на единицу
число входов tF уменьшается в два раза. Най-
дем конфигурацию <SA0, tF0> такую, что имеет
место следующее соотношение:
200 FF tRNt .
Пусть при этом выполняется соотношение:
RGS A 0 .
Итак, конфигурация <SA0, tF0> позволяет реа-
лизовать схему МПА на одном EMB. При этом
имеется ΔS свободных адресных входов, где
RGS AS . (11)
В статье предлагается разбить множество
X на два подмножества: 1 2 ,X X X где
1 2X X X . Множество X2 имеет мощ-
ность ΔS, а множество X1 − (L − ΔS). В этом
случае условия 1
1x X подлежат преобразова-
нию PX 1 . Переменные 2
lx X поступа-
УСиМ, 2016, № 3 19
ют непосредственно на входы блока EMB. Это
определяет модель U3, показанную на рис. 4.
В автомате U3 блок LUTer реализует систе-
му функций
P = P (T ′, X
1). (12)
При этом T′ T, что возможно при специа-
льном кодировании состояний. Блок EMB реа-
лизует систему (7) и системы функций
Y1 = Y
1(T, X
2, P);
Φ = Φ (T, X
2, P).
Рис. 4. Структурная схема автомата U3
Такой подход позволяет уменьшить число
литералов в системе (12) в сравнении с этим
параметром для системы (9). Это приводит к
уменьшению числа LUT-элементов в схеме
LUTer автомата U3 в сравнении с эквивалент-
ным автоматом U2. Автоматы считаются экви-
валентными, если они синтезированы по одной
и той же исходной граф-схеме алгоритма (ГСА).
Предлагается метод синтеза автомата U3 по
ГСА Γ, включающей следующие этапы:
формирование множества состояний А и
множеств Y1, Y2;
замена логических условий xl X пере-
менными pg P;
разбиение множества логических условий;
специальное кодирование состояний;
формирование прямой структурной таб-
лицы МПА;
формирование таблиц элементов блока
LUTer;
формирование таблицы блока EMB;
реализация схемы МПА в заданном эле-
ментном базисе.
Пример применения предложенного метода
Рассмотрим пример реализации этого метода
для ГСА Γ1 (рис. 5). Используем в качестве эле-
ментного базиса микросхему FPGA со следую-
щими конфигурациями блоков EMB: 4K × 1,
2K × 2, 1K × 4, 512 × 8 и 256 × 16 (битов). Пусть
LUT-элементы имеют число входов S = 3.
Рис. 5. Исходная ГСА Γ1
На дугах ГСА Γ1 показаны выходные пере-
менные yn Y1, в операторных вершинах – пе-
ременные yn Y2. Анализ ГСА Γ1 дает множе-
ства Y1 = {y1,…, y5,}, и Y2 = {y6,…, y9}. Таким
образом N1 = 5, N2 = 4 и N = 9.
Состояния am A – состояния автомата Му-
ра, т.е. каждая операторная вершина отмечает-
ся уникальной отметкой [1]. Авторы предла-
гают отмечать одинаковыми состояниями
вершины, если: их выходы связаны с входом
одной и той же вершины ГСА Γ и в этих вер-
шинах нет переменных ynY2.
Такой подход позволяет отметить состояни-
ем a6 три вершины (рис. 5). Это приводит к
20 УСиМ, 2016, № 3
уменьшению числа состояний и числа перехо-
дов из них. Для ГСА Γ1 имеем A = {a1,…, a6},
что дает M = 6, R = 3, T = {T1, T2, T3} и Φ = {D1,
D2, D3}.
Обозначим символом Ui (Γj) тот факт, что
автомат Ui синтезируется по ГСА Γj. Рассмот-
рим возможность реализации автомата U1 (Γ1)
для данной микросхемы FPGA. Очевидно,
V0 = 4096 (это следует, например, из конфигу-
рации 4K × 1). Для ГСА Γ1 имеем L = 7, R = 3 и
N = 9. Проверим условие (8):
KVK 412392 0
10 .
Видимо, для реализации систем (5) – (7) не-
обходимо три блока EMB.
Таким образом, целесообразно проверить
автомат U2(Γ1). Обозначим символом X(am)
множество логических условий, определяющих
переходы из состояния am A. Для ГСА Γ1
имеем: X(a1) = {x1, x2}, X(a2) = X(a3) = X(a4) =
={x3, x4}, X(a5) = {x5, x6}, X(a6) = {x7}. Следова-
тельно, число переменных G определяется
следующим образом:
G = max(L1,…, LM),
где Lm = |X(am)|, m {1, …, M}.
В рассматриваемом примере имеем G = 2,
что определяет множество P = {p1, p2}. Пост-
роим таблицу замены логических условий
(табл. 2). В ней переменная xl X, заменяемая
в состоянии am A переменной ag P, записы-
вается на пересечении строки pg и столбца am.
Т а б л и ц а 2. Таблица замены логических условий
am
pg
a1 a2 a3 a4 a5 a6
p1 x 1 x 3 x 3 x 3 x 5 x 7
p2 x 2 x 4 x 4 x 4 x 6 ─
Условие (10) справедливо для автомата
U2(Γ1). Проверим возможность использования
модели U3(Γ1). Поскольку R + N = 12, необхо-
димо выбрать конфигурацию 256 × 16. Это да-
ет SA = 8. Так как G + R = 5, из (11) можно по-
лучить ΔS = 3. Таким образом, три переменные
xl X подавать непосредственно на адресные
входы EMB, т.е. модель U3(Γ1) может быть ис-
пользована.
Представим множество X в виде объедине-
ния множеств X1 = {x1, x2, x6, x7}, и X2 = {x3, x4,
x5}. Теперь таблица замены логических усло-
вий имеет следующий вид (табл. 3)
Т а б л и ц а 3. Таблица замены логических условий автомата
U3(Γ1)
am
pg
a1 a2 a3 a4 a5 a6
p1 x 1 x 3 x 3 x 3 x 5 x 7
p2 x 2 x 4 x 4 x 4 x 6 ─
Из табл. 3 следует, что p2 = x2. Таким обра-
зом, имеем множества P = {p1}, X1 = {x1, x6, x7},
X2 = {x2, x3, x4, x5}.
Специальное кодирование состояний за-
ключается в выборе таких кодов K(am), чтобы
функции (12) имели минимальное число лите-
ралов. Закодируем состояния так, как это пока-
зано в карте Карно (рис. 6). В этой карте знак
«» означает, что данный код может быть ис-
пользован для минимизации функций (12).
Рис. 6. Коды состояний автомата U3(Γ1)
Из рис. 6 можно получить уравнение:
62711211 xTxTxTTP . (13)
При использовании кодов из рис. 6 и табл. 2
можно получить следующие уравнения:
52132133213211 xTTxTTxTTxTTTP , (14)
621414322322 xTTxTxTTxTTP . (15)
В нашем примере LUT-элементы имеют
S = 3. Для реализации (13) требуется четыре
элемента и схемы имеют два уровня. Для реа-
лизации (14) – (15) требуется 13 элементов и
схема имеет четыре уровня. Таким образом,
применение предложенного подхода позволяет
в три раза уменьшить аппаратурные затраты и
в два раза увеличить быстродействие блока
LUTer.
Фрагмент прямой структурной таблицы
(ПСТ) автомата U3(Γ1) приведен в табл. 4.
УСиМ, 2016, № 3 21
Т а б л и ц а 4. Фрагмент ПСТ автомата U3(Γ1)
am K(am) aS K(aS) Xh Ph Φh Yh h
a2 001 1 P1 D3 y4 1
a3 101 x2 1P D1 D3 y2 2 a1(–) 000
a4 110 2x 1P D1 D2 y1 y3 3
a2 001 x3 1 D3 – 4
a5 010 3 4x x 1 D2 y2 y4 5 a2(y6 y7) 001
a4 110 3 4x x 1 D1 D2 y1 y3 6
ПСТ автомата U3(Γ1) имеет следующие сто-
лбцы: am – текущее состояние; K(am) – код сос-
тояния am A; aS – состояние перехода; K(aS) –
код состояния aS A; Xh, Ph – входной сигнал,
определяющий переход из am, в aS; Φh – функ-
ции возбуждения памяти, равные единице для
ее переключения из K(am) в K(aS); Yh – выход-
ные переменные, формируемые при переходе
из am, в aS; h – номер перехода. Кроме того, в
столбце am указывается формируемый в нем
выходной сигнал.
В табл. 4 показаны переходы для состояний
a1 и a2. Отметим, что ПСТ автомата U3(Γ1)
имеет H = 21 строку. Если переход не зависит
от переменных xl X (pg P), то в соответ-
ствующем столбце записывается единица. По-
добная таблица – основа для формирования
содержимого блока EMB.
Блок LUTer задается таблицами, каждая из
которых соответствует одному элементу LUT.
Например, конъюнкция 121 xTT уравнения (13)
соответствует элементу LUT1. Этот элемент
задается табл. 5.
Т а б л и ц а 5. Таблица элемента LUT1
T1 T2 x1 p1 q T1 T2 x1 p1 q
0 0 0 0 1 1 0 0 0 5
0 0 1 1 2 1 0 1 0 6
0 1 0 0 3 1 1 0 0 7
0 1 1 0 4 1 1 1 0 8
Терм 121 xTT соответствует ячейке с номе-
ром q = 2. Во второй строке переменная p1 = 1,
в остальных строках p1 = 0. Аналогичным об-
разом строятся таблицы для программирова-
ния каждого LUT-элемента.
Таблица блока EMB строится на основе
ПСТ. Она имеет столбцы K(am), X2, P (адрес
ячейки), Φ, Y1, Y2 (содержимое ячейки), q. Таб-
лица блока EMB имеет H строк, где:
SGRH 2 .
В рассматриваемом примере H = 256. Пере-
ходы из каждого состояния задаются при по-
мощи H(am) строк, где:
SG
maH 2 .
В рассматриваемом примере H(am) = 32.
Таблица блока EMB есть таблицей истинно-
сти, соответствующей ПСТ. При этом пере-
менные yn Y2 записываются во всех строках,
соответствующих состоянию am A, в котором
они формируются.
Для рассматриваемого примера адреса яче-
ек соответствуют вектору <T1 T2 T3 x2 x3 x4 x5
p1>, а их содержимое – вектору <D1 D2 D3 y1 y2
y3 y4 y5 y6 y7 y8 y9>. Например, четвертая строка
табл. 4 определяется векторами <0011> и
<001010101100>, где символ «» показывает,
что значение переменной несущественно. Та-
ким образом, четвертая строка ПСТ соответ-
ствует 16 ячейкам EMB. Мы не показываем
таблицу EMB в силу ее громоздкости.
Заключение. Предложенный метод позво-
ляет реализовать схему совмещенного МПА с
использованием минимального числа блоков
EMB и элементов LUT. Первое достигается пу-
тем замены логических условий, второе – пу-
тем замены только части множества логичес-
ких условий. При этом, основываясь на ре-
зультатах [7–12], можно утверждать, что схема
МПА занимает минимально возможную пло-
щадь кристалла и потребляет минимальную эне-
ргию.
Анализ библиотеки [13] показывает, что для
82 процентов примеров схема реализуется с
использованием только одного EMB. Для оста-
льных 18 процентов примеров требуется от
двух до трех блоков EMB. Для оптимизации
этих примеров мы предлагаем использовать
методы из статьи [14].
Для уменьшения числа LUT-элементов не-
обходимо соответствующим образом разбить
множество входных переменных. Это будет
направлением наших дальнейших исследова-
22 УСиМ, 2016, № 3
ний. В частности предлагается адаптировать
методы [15] к особенностям совмещенного ав-
томата.
1. Baranov S. Logic Synthesis for Control Automata. –
Dordrecht: Kluwer Acad. Publ., 1994. – 312 p.
2. DeMicheli G. Synthesis and Optimization of Digital
Circuits. – N.Y.: McGraw-Hill, 1994. – 636 p.
3. Соловьев В.В. Проектирование цифровых схем на
основе программируемых логических интегральных
схем. – М.: Горячая линия – ТЕЛЕКОМ, 2001. –
636 с.
4. Skliarova I., Sklyarov V., Sudnitson A. Design of FPGA-
based circuits using Hierarchical Finite State Ma-
chines. – Tallinn: TUT Press, 2012. – 240 p.
5. Грушницкий Р.И., Мурсаев А.Х., Угрюмов Е.П. Про-
ектирование систем с использованием микросхем
программируемой логики. – СПб: БХВ. – Петер-
бург, 2002. – 608 с.
6. Synthesis and Optimization of FPGA-based Systems /
V. Sklyarov, I. Skliarova, A. Barkalov et al. – Berlin:
Springer, 2014. – 432p.
7. Cong J., Yan K. Synthesis for FPGAs with Embedded
Memory Blocks // Proc. of the 2000 ACM/SIGDA 8th
Int. Symp. on FPGAs. – 2000. – P. 75–82.
8. ROM-Based Finite State Machine Implementation in
Low Cost FPGAs / L. Garcia–Vargas, R. Senhadji–
Navarro, M. Civit–Balcells et al. // IEEE Int. Simp. on
Industrial Electronics, Vigo. – 2007. – P. 2342–2347.
9. Nowicka M., Łuba T., Rawski V. FPGA-based decom-
position of boolean functions: algorithms and implemen-
tations // Advanced Comp. Syst. – 1999. – P. 502–509.
10. Rawski M., Selvaraj H., Łuba T. An application of
functional decomposition in ROM-based FSM imple-
mentation in FPGA devices // J. of System Architec-
ture. – 2005. – 51(6–7) – P. 424–434.
11. Logic Synthesis Method of Digital Circuits Designed
for Implementation with Embedded Memory Blocks
on FPGAs / M. Rawski, P. Tomaszewicz, G. Borowski
et al. // Design of Digital Systems and Devises. LNEE
70. – Berlin: Springer, 2005. – P. 121–144.
12. Tiwari A., Tomko K. Saving power by mapping finite
state machines into embedded memory blocks in FPGAs
// Proc. of Design Automation and Test in Europe. –
2004. – 2. – P. 916–921.
13. Yang S. Logic Synthesis and optimization benchmarks
user guide // Microelectronics Center of North Caro-
lina. – 1991. – 43 p.
14. Баркалов А.А. Принципы оптимизации логической
схемы микропрограммного автомата Мура // Кибер-
нетика и системный анализ. – 1998. – № 1. – C. 65–72.
15. Barkalov A., Titarenko L., Kolopenczyk M. EMB-based
design of Mealy FSM // 12th IFAC Conf. on programmable
devices and embedded systems. – 2013. – P. 215–220.
Поступила 13.05.2016
Тел. для справок: +38 044 526-2504, 406-7829 (Киев)
E-mail: A.Barkalov@iie.uz.zgora.pl,
L.Titarenko@iie.uz.zgora.pl, yaviz@ukr.net, matv@online.ua
© А.А. Баркалов, Я.Е. Визор, А.В. Матвиенко,
Л.А. Титаренко, В.В. Горина, 2016
UDC 004.274
A.A. Barkalov, L.A. Titarenko, Y.E. Vizor, A.V. Matvienko, V.V. Gorina
Synthesis of Combined Finite State Machine with FPGAs
Keywords: combined FSM, FPGA, LUT, EMB, synthesis, graph-scheme of algorithm.
A method for synthesis of combined finite state machine (CFSM) with FPGA is proposed. An analysis of CFSM’s peculi-
arities is given. The main feature of CFSM is an existence of two types of the output signals. Mealy outputs depend on the
both inputs and states. Moore outputs depend only on the states. The known methods of CFSM design and conditions for
their application and the method of the logical conditions replacement is thoroughly analyzed.
It allows using embedded memory locks (EMB) for implementing some part of CFSM circuit. It is shown that the situations are
possible when not all address inputs of an EMB are used. The suggested method is based on using these free address inputs. It is
proposed to connect a part of logical conditions with unused address inputs of EMB blocks. It allows diminishing for the number of
look-up table (LUT) elements in the circuit of logical conditions replacement in comparison with known methods of CFSM design.
It is proposed to replace some part of the logical conditions set by additional variables. A design method based on such
partial replacement is proposed. The method allows obtaining a CFSM circuit with the minimum number of table elements
LUTs and memory blocks EMBs. Some additional optimization are possible for the replacement block of the logical condi-
tions due to a special state assignment.
The main idea of the special state assignment is reduced the assignment neighbor codes for states with transitions depend-
ing on the same logical conditions. It allows diminishing the number of the literals in functions implemented of the block of
the logical conditions replacement. An example of the studied method application is shown.
The proposed method allows obtaining a circuit required minimum chip space and consuming minimum power in comparison
with the known design methods. The conducted researches are based on some library of standard GSAs. The investigations
show that for the majority of standard GSAs the proposed method produces the circuits with a single EMB.
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.4
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /CMYK
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments true
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 300
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/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 300
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/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 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile ()
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/CreateJDFFile false
/Description <<
/ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E>
/BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e>
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e>
/HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E>
/HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.)
/HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e>
/LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e>
/RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e>
/SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e>
/SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e>
/UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e>
/ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. 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 /ConvertToCMYK
/DestinationProfileName ()
/DestinationProfileSelector /DocumentCMYK
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles false
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /UseDocumentProfile
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [612.000 792.000]
>> setpagedevice
|