Построение компактных тестов для функциональной верификации VHDL-описаний конечных автоматов
Разработана программа, позволяющая по полученной в результате моделирования последовательности состояний автомата строить ориентированный граф переходов автомата и находить покрытие всех дуг. Входные тестовые наборы, соответствующие дугам, вошедшим в покрытие, будут образовывать тест для функциональ...
Gespeichert in:
| Veröffentlicht in: | Управляющие системы и машины |
|---|---|
| Datum: | 2017 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2017
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/124949 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Построение компактных тестов для функциональной верификации VHDL-описаний конечных автоматов / П.Н. Бибило, В.И. Романов // Управляющие системы и машины. — 2017. — № 1. — С. 35-45. — Бібліогр.: 13 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859669030287179776 |
|---|---|
| author | Бибило, П.Н. Романов, В.И. |
| author_facet | Бибило, П.Н. Романов, В.И. |
| citation_txt | Построение компактных тестов для функциональной верификации VHDL-описаний конечных автоматов / П.Н. Бибило, В.И. Романов // Управляющие системы и машины. — 2017. — № 1. — С. 35-45. — Бібліогр.: 13 назв. — рос. |
| collection | DSpace DC |
| container_title | Управляющие системы и машины |
| description | Разработана программа, позволяющая по полученной в результате моделирования последовательности состояний автомата строить ориентированный граф переходов автомата и находить покрытие всех дуг. Входные тестовые наборы, соответствующие дугам, вошедшим в покрытие, будут образовывать тест для функциональной верификации.
Розроблено програму, яка дозволяє за отриманою в результаті моделювання послідовністю станів автомата будувати орієнтовний граф переходів автомата і знаходити покриття всіх дуг. Вхідні тестові набори, відповідні дугам, які увійшли в покриття, створюватимуть тест для функціональної верифікації.
A correct VHDL-description of a finite state machine (FSM) is given. It is necessary to construct a test Tsrc for functional verification by simulation that will check the performance of all the available transitions between internal states of the FSM. The selection of FSM internal states from VHDL-description and the construction of the transition graph is a nontrivial task. In fact, it is necessary to automate the process of constructing a mathematical model of FSM in form of graph of transitions by analysis VHDL-program of FSM. To solve the problem we suggest an approach for obtaining an approximate solution based on simulation of VHDL-description of the FSM on the pseudo-random test Tsrc; selection from the test Tsrc some test kits, which will be included in the target test Tres. A program that allows constructing a directed graph of FSM transitions and finding coverage of all arcs on the base of the simulation results is developed. The input test kits corresponding to the arcs, which are in the coverage, make a test for the functional verification. An experimental research of the method of constructing compact tests for the verification of VHDLmodels of FSM on standard examples is performed.
|
| first_indexed | 2025-11-30T12:49:20Z |
| format | Article |
| fulltext |
УСиМ, 2017, № 1 35
Технические средства информатики
УДК 004.3
П.Н. Бибило, В.И. Романов
Построение компактных тестов для функциональной верификации VHDL-описаний
конечных автоматов
Разработана программа, позволяющая по полученной в результате моделирования последовательности состояний автомата
строить ориентированный граф переходов автомата и находить покрытие всех дуг. Входные тестовые наборы, соответствую-
щие дугам, вошедшим в покрытие, будут образовывать тест для функциональной верификации.
Розроблено програму, яка дозволяє за отриманою в результаті моделювання послідовністю станів автомата будувати орієнто-
вний граф переходів автомата і знаходити покриття всіх дуг. Вхідні тестові набори, відповідні дугам, які увійшли в покриття,
створюватимуть тест для функціональної верифікації.
Введение. При проектировании цифровой ап-
паратуры широкое распространение получила
модель цифрового устройства с памятью в ви-
де конечного автомата, в зарубежной литера-
туре называемая FSM (Finite State Machine).
Конечные автоматы, как и другие модели циф-
ровых устройств, представляются на языках
VHDL [1], Verilog [2], предназначенных для
проектирования цифровых схем на современ-
ной базе заказных СБИС (сверхбольших инте-
гральных схем) либо программируемых поль-
зователями логических интегральных схем типа
FPGA. По VHDL-описаниям конечных автома-
тов синтезируются синхронные логические
схемы в том или ином базисе логических эле-
ментов, называемом технологическим (целе-
вым) базисом либо целевой библиотекой логи-
ческих элементов. Сегодня процесс синтеза ав-
томатизирован и важнейшей проблемой при
создании проектов СБИС и систем-на-кристал-
ле [3] – проблема верификации исходных спе-
цификаций, представленных на VHDL либо дру-
гих языках, используемых для алгоритмичес-
кого описания проектируемых цифровых уст-
ройств и систем. Под верификацией понимает-
ся проверка правильности исходного VHDL-
описания, т.е. проверка соответствия состав-
ленного синтезируемого VHDL-описания про-
ектируемой цифровой системы спецификаци-
ям на проектирование [4].
Большое достоинство модели конечного ав-
томата – данная модель может быть верифи-
цирована [4]. Система моделирования Questa
[5] имеет в своем составе средства для функ-
циональной верификации FSM, если модель
FSM написана соответствующим образом. Дан-
ные средства (опции) позволяют при модели-
ровании распознавать конечный автомат, вхо-
дящий в состав проекта, определить все прой-
денные (в конкретном сеансе моделирования)
состояния конечного автомата и подсчитать
число прохождений дуг в графе переходов ав-
томата. Такие средства весьма полезны, однако
конечные автоматы, как правило, входят в ка-
честве управляющих блоков в состав более
сложных проектов. Для проведения верифика-
ции всего проекта в целом требуется построе-
ние компактных функциональных тестов для
управляющего блока – конечного автомата.
Автоматизированное построение таких тестов
по результатам моделирования VHDL-описа-
ний конечных автоматов – цель данной статьи.
Постановка задачи и предлагаемый подход
Модель конечного автомата и его VHDL-
описание назовем корректными, если из лю-
бого внутреннего состояния автомата имеется
путь в начальное состояние автомата. Отме-
тим, что для микропрограммных автоматов [6]
данное условие – обязательно и всегда выпол-
няется. Микропрограммные автоматы давно
36 УСиМ, 2017, № 1
используются в практике проектирования и
описываются в настоящее время на современ-
ных языках [7, 8].
Под тестом понимается упорядоченная по-
следовательность наборов значений входных
сигналов, которые при моделировании пода-
ются на входные порты VHDL-модели авто-
мата. Для проведения моделирования готовит-
ся специальная тестирующая программа (test-
bench) либо множество таких программ, ориен-
тированных на различные цели тестирования и
способы организации тестов. Тесты, позволяю-
щие проверить правильность функционирова-
ния исследуемой модели автомата, называются
функциональными.
Задача 1. Задано корректное VHDL-описа-
ние конечного автомата. Требуется построить
тест Трез, позволяющий при моделировании
(данного автомата на наборах теста Трез) вы-
полнить функциональную верификацию – про-
верить выполнение всех имеющихся в модели
автомата переходов между внутренними
состояниями.
Например, в листинге 1 задано VHDL-опи-
сание конечного автомата Mealy. Отметим, что,
кроме переходов si sj (смены внутреннего
состояния) по переднему фронту синхросигна-
ла clk, имеются также переходы в начальное
состояние s0 по единичному значению сигнала
rst. Для краткости назовем первые из них син-
хронными и, соответственно, вторые – асин-
хронными. Под состояниями автомата всегда
будут пониматься его внутренние состояния.
Точнее, в качестве автоматов будут рассмат-
риваться конечные автоматы с закодирован-
ными входными и выходными состояниями,
такие конечные автоматы в научной литерату-
ре называются автоматами с абстрактными
состояниями [9].
На рис. 1 показан граф ( , )E E EG S A автомата
Mealy, соответствующий VHDL-модели, пред-
ставленной в листинге 1. Назовем этот граф
эталонным. Эталонный граф ( , )E E EG S A опи-
сывает только функцию переходов между со-
стояниями автомата. На рис. 1 не показаны
асинхронные переходы (рис. 2) из любого со-
стояния is в начальное состояние 0s при еди-
ничном значении сигнала rst. Дизъюнктивные
нормальные формы (ДНФ) ijD , описывающие
условия переходов is js между состояниями
is , js , и значения выходных сигналов автомата
при выполнении таких переходов, заданы в
табл. 1.
Рис. 1. Эталонный граф GE(SE, AE) переходов автомата Mealy
Рис. 2. Асинхронные переходы в начальное состояние s0 в
эталонном графе GE(SE, AE)
Т а б л и ц а 1. Таблица переходов автомата Mealy
si sj Условия перехода Выходные сигналы
s0 s1 0,1D =1; y2
s2 1,2D = 2 31 1 2x x x x x y3
s3 1,3D = 21 3x x x y4 s1
s4 1,4D = 1x y5
s2 s3 2,3D =1 y4
s3 s0 3,0D = 2x y1
s5 3,5D = 2x y6
s4 s0 4,0D = 1 4x x y1
s3 4,3D = 4x 1 4x x y4
s5 s0 5,0D =1 y1
Далее будут рассматриваться примеры ко-
нечных автоматов на языке VHDL, однако,
предлагаемый подход к построению тестов
может быть применим для описаний автоматов
на языке Verilog.
УСиМ, 2017, № 1 37
Выделение из VHDL-описания автомата
внутренних состояний автомата и построение
графа ( , )E E EG S A переходов – нетривиальная
задача, так как сводится к анализу VHDL-кода,
синтаксис которого сложный, а автомат может
быть задан в другой форме, отличающейся от
формы описания, представленной в листин-
ге 1, и тогда система моделирования Questa не
сможет его распознать. По сути, надо автома-
тизировать процесс построения математиче-
ской модели графа переходов по VHDL-
программе, задающей автомат, например, по-
строить матрицу смежности ориентированного
графа переходов. Чтобы избежать
такого анализа, для решения зада-
чи 1 предлагается подход, позво-
ляющий получить приближенное
решение и базирующийся на:
моделировании VHDL-описа-
ния автомата на псевдослучайном
тесте Тисх ;
выделении из теста Тисх неко-
торых двоичных тестовых набо-
ров, которые включаются в иско-
мый тест Трез.
Для того чтобы реализовать дан-
ный подход, надо правильно орга-
низовать моделирование, а имен-
но: для каждого тестового набора
(каждого такта моделирования)
выдать внутреннее состояние ав-
томата, в которое переходит авто-
мат при подаче тестового набора
на вход VHDL-модели автомата и
в котором он будет находиться в
следующем такте моделирования.
Тестирующая программа для на-
чального моделирования при фик-
сированном значении rst = 0 пред-
ставлена в листинге 2.
Обратим внимание на то, что
для доступа к внутренним сигна-
лам проекта
state_top <= <<signal .tstb.p0.state :
T_state>>;
требуется моделирование в системе
Questa [5] с включенной опцией
«Стандарт VHDL’2008» [10].
Проведем моделирование VHDL-описания
автомата на 30 псевдослучайных наборах, за-
даваемых в файле IN.TST (табл. 2). Результа-
том моделирования будут потактовые выход-
ные реакции автомата (текстовый файл
OUT.TST) и текстовый файл STATE.TST, в ко-
тором задается последовательность пройден-
ных состояний автомата. В табл. 2 приводится
файл IN.TST тестовых наборов и файл
STATE.TST. При моделировании осуществля-
ются циклические попадания в начальное со-
стояние автомата s0 , семь таких циклов приве-
Листинг 1. VHDL-описание конечного автомата Mealy
library ieee;
use ieee.std_logic_1164.all;
entity Mealy is
port( x1, x2, x3, x4 : in std_logic;
clk, rst : in std_logic;
y1, y2, y3, y4, y5, y6 : out std_logic);
end Mealy;
architecture rtl of Mealy is
type T_state is (s0, s1, s2, s3, s4, s5);
signal NEXT_state, state: T_state;
signal w: std_logic_vector (1 to 6);
begin
y1 <= w(1); y2 <= w(2);y3 <= w(3);y4 <= w(4);y5 <= w(5);
y6 <= w(6);
NS : process (state, x1, x2, x3, x4)
begin
case state is
when s0 =>
NEXT_state <= s1; w <="010000";
when s1 => if ( (x1 and not x2 and not x3) or (x1 and x2) ) = '1'
then NEXT_state <= s2; w <="001000";
elsif ((x1 and not x2 and x3) = '1')
then NEXT_state <= s3; w <="000100";
elsif (not x1 = '1')
then NEXT_state <= s4; w <="000010";
end if;
when s2 => NEXT_state <= s3; w <="000100";
when s3 => if (not x2 = '1')
then NEXT_state <= s0 ; w <="100000";
elsif ( x2 = '1')
then NEXT_state <= s5 ; w <="000001";
end if;
when s4 => if ((not x1 and x4 ) = '1')
then NEXT_state <= s0; w <="100000";
elsif ( (not x4) or (x1 and x4) ) = '1'
then NEXT_state <= s3; w <="000100";
end if;
when s5 => NEXT_state <= s0; w <="100000";
end case;
end process NS;
state_process: process (clk, rst)
begin -- process state_process
if rst = '1' then -- asynchronous reset (active low)
state <= s0;
elsif clk'event and clk = '1' then -- rising clock edge
state <= NEXT_state;
end if;
end process state_process;
end rtl;
38 УСиМ, 2017, № 1
дены в табл. 2, восьмой цикл не закончен. Бу-
дем считать, что в нулевом (начальном) такте
моделирования автомат всегда находится в на-
чальном состоянии, куда он попадает по
VHDL-команде rst <='1' ; (выделенная жирным
шрифтом строка в листинге 2).
Т а б л и ц а 2. Результат моделирования VHDL-модели авто-
мата Mealy
Циклы на графике G переходов
Такт
Тест Tисх
(IN.TST)
x1x2 x3 x4
Состояния Sисх
(STATE.TST) 1 2 3 4 5 6 7 8
0 s0 s0
1 0101 s1 s1
2 1001 s2 s2
3 0001 s3 s3
4 1011 s0 s0 s0
5 0100 s1 s1
6 1000 s2 s2
7 1000 s3 s3
8 1110 s5 s5
9 1000 s0 s0 s0
10 1110 s1 s1
11 0011 s4 s4
12 1101 s3 s3
13 0110 s5 s5
14 1100 s0 s0 s0
15 0111 s1 s1
16 0011 s4 s4
17 0011 s0 s0 s0
18 0110 s1 s1
19 0101 s4 s4
20 1011 s3 s3
21 0010 s0 s0 s0
22 1100 s1 s1
23 0111 s4 s4
24 0001 s0 s0 s0
25 0000 s1 s1
26 0101 s4 s4
27 0000 s3 s3
28 1001 s0 s0 s0
29 0111 s1 s1
30 1110 s2 s2
По результатам моделирования автомата
(файлам IN.TST, STATE.TST) строим граф
G(S, A), вершинами которого есть состояния
автомата, а ребрами – переходы между состоя-
ниями. В файле IN.TST задаются тестирующие
наборы – это последовательность Тисх , файл
STATE.TST представляет собой последователь-
ность Sисх состояний автомата, в которые авто-
мат переходит при подаче тестовых наборов из
файла IN.TST. Обозначим через x = ( 1x , 2x ,…
, nx ) входные информационные сигналы ав-
томата (в этот список не включаются синхро-
сигнал сигнал clk (тактирования) и сигнал rst
(асинхронного сброса в начальное состояние).
Листинг 2. Тестирующая программа для моделирования
VHDL-описания конечного автомата Mealy (rst = 0)
library IEEE;
use IEEE.std_logic_1164.all;
use STD.TEXTIO.all;
use STD.ENV.all;
use IEEE.std_logic_TEXTIO.all;
use ieee.numeric_std.all;
entity tstb is end;
architecture BEHAVIOR of tstb is
component Mealy is
port( x1, x2, x3, x4 : in std_logic;
clk, rst : in std_logic;
y1, y2, y3, y4, y5, y6 : out std_logic);
end component ;
signal x1, x2, x3, x4 : std_logic;
signal clk, rst : std_logic;
signal y1, y2, y3, y4, y5, y6 : std_logic;
signal W: std_logic_vector (4 downto 1);
signal DATA : std_logic_vector (4 downto 1);
signal YY : STD_LOGIC_VECTOR (6 downto 1);
type T_state is (s0, s1, s2, s3, s4, s5);
signal state_top : T_state;
begin
p0: Mealy
port map ( x1, x2, x3, x4, clk, rst, y1, y2,
y3, y4, y5, y6);
state_top <= <<signal .tstb.p0.state : T_state>>;
W <= DATA;
x1 <= W(4); x2 <= W(3); x3 <= W(2); x4 <= W(1);
YY <= (y1, y2, y3, y4, y5, y6);
Process
file INFILE,OUTFILE, OUTSTATE : text;
variable PTR,POKE, PRSTATE :line;
variable DATA_IN: std_logic_vector (4 downto 1);
variable DATA_OUT: std_logic_vector (6 downto 1);
variable STATE_OUT: line;
variable var_ST: T_state;
begin
file_open(INFILE,"IN.TST",read_mode);
file_open(OUTFILE,"OUT.TST",write_mode);
file_open(OUTSTATE,"STATE.TST",write_mode);
rst <='1';
clk <= '0';
wait for 50.0 ns;
clk <= '1';
wait for 50.0 ns;
clk <= '0';
wait for 25.0 ns;
rst <='0';
while not (endfile(INFILE)) loop
clk <= '0';
wait for 25.0 ns;
readline(INFILE,PTR);
read(PTR,DATA_IN);
DATA <= DATA_IN;
wait for 25.0 ns;
clk <= '1';
wait for 50.0 ns;
DATA_OUT := YY;
write(POKE,DATA_OUT);
writeline(OUTFILE,POKE);
var_ST := state_top;
write(PRSTATE, to_string(var_ST));
writeline(OUTSTATE,PRSTATE);
end loop;
file_close(INFILE);
file_close(OUTFILE);
file_close(OUTSTATE);
report "Done!" severity WARNING;
wait;
end process;
end;
УСиМ, 2017, № 1 39
Через xV обозначим булево пространство над
переменными вектора x = ( 1x , 2x , …, nx ). Бу-
лево пространство xV содержит n2 двоичных
наборов *
ix . В рассматриваемом примере n = 4,
x = ( 1x , 3x , 4x ), а число всех возможных значе-
ний вектора x равно 16. Если при моделиро-
вании автомат из состояния si перешел в со-
стояние sj при подаче на его вход входного на-
бора *
qx , то в ориентированный граф G(S, A)
вносится дуга i js s и помечается набором
*
qx . В данном графе S – множество вершин
графа (каждой вершине графа соответствует
состояние автомата), А – множество дуг
i js s . Последовательность *
1qx , *
2qx , …, *
qkx
входных наборов – это наборы теста Тисх . По-
следовательность состояний 1s , 1is , 2is , …, iks
обозначим через Sисх . Множество S состоит из
символов различных состояний, имеющихся в
последовательности Sисх . В рассматриваемом
примере (табл. 2) переход автомата из состоя-
ния s0 в состояние s1 осуществляется при пода-
че на вход автомата двоичного набора *
qx 1 =
= (0101), переход автомата из состояния s1 в со-
стояние s2 осуществляется при подаче на вход
автомата двоичного набора *
2qx = (1001) и т.д.
Задача 2. По заданным последовательностям
Тисх , Sисх построить ориентированный граф
G = (S, A), вершинам которого соответствуют
состояния si , а каждая дуга i js s которого
помечена одним двоичным набором, вызы-
вающим переход из состояния si в состояние sj .
Решение задачи 2 не вызывает затруднения,
при этом метка дуги устанавливается равной
первому встреченному входному набору, вы-
звавшему соответствующий переход. В рас-
сматриваемом примере результатом решения
задачи 2 есть граф G = (S, A), изображенный на
рис. 3.
Отметим, что если в последовательности
Sисх нет соседних элементов si, sj , то в графе
G = (S, A) будет отсутствовать дуга i js s . В
примере последовательность S не содержит
соседних состояний s1 , s3 , поэтому в графе
G = (S, A) отсутствует дуга 1 3s s . На рис. 3
отсутствующая дуга показана штриховой ли-
нией. Таким образом, требуется, чтобы началь-
ный тест Тисх был достаточно длинным и обес-
печил наличие в графе G = (S, A) всех перехо-
дов автомата, которые есть в VHDL-модели
этого автомата. В примере тест Тисх из 30 набо-
ров короткий и не обеспечивает наличия в гра-
фе всех требуемых дуг. Требуется более длин-
ный тест, как будет показано далее, для по-
строения графа G = (S, A), содержащего все
требуемые дуги, достаточно псевдослучайного
теста из 80 наборов. Цель начального модели-
рования будет достигнута, если граф G(S, A)
будет равен графу ( , )E E EG S A (без учета поме-
ток на ориентированных дугах данных графов).
Рис. 3. Граф G = (S, A), построенный по результатам начально-
го моделирования на 30 наборах
С использованием графа G = (S, A) задача 1
сводится к задаче 3.
Задача 3. Для заданного ориентированного
графа G = (S, A) найти минимальный по длине
цикл, содержащий все дуги графа.
Данная задача – известный случай задачи о
китайском почтальоне для ориентированных
графов [11, 12].
Среди вершин S графа в качестве целевой
выделим вершину 0s , соответствующую на-
чальному (конечному) состоянию автомата.
Искомый цикл может быть представлен набо-
ром контуров, содержащих указанную верши-
ну 0s . Имея в распоряжении найденный цикл,
нетрудно построить тест Трез , обеспечиваю-
щий проверку VHDL-модели автомата, а после
40 УСиМ, 2017, № 1
синтеза и логической схемы, реализующей
VHDL-модель.
Приближенный алгоритм решения задачи 3
Исходные данные – матрица смежности
графа G = (S, A), при этом каждая дуга имеет
метку, представленную тестовым набором, по-
родившим соответствующий переход между
вершинами.
Ш а г 1. Реализуется вычислительная про-
цедура, основанная на рекурсии и обеспечи-
вающая нахождение кратчайших путей из ка-
ждой вершины графа G в целевую вершину.
Ш а г 2. Реализуется рекурсивная процеду-
ра нахождения в графе G циклов, начинаю-
щихся с исходной вершины и в совокупности
содержащих все дуги графа. В качестве аргу-
ментов этой процедуры выступает номер рас-
сматриваемой вершины, текущее состояние мат-
рицы смежности и формируемый цикл, пред-
ставленный последовательностью пройденных
вершин графа. Кроме того, в процедуре ис-
пользуется глобально доступная матрица пока
непокрытых дуг (в начальный момент – копия
матрицы смежности). Непокрытой считается
та дуга, которая не входит ни в один из уже
построенных циклов.
Ш а г 2.1. Последовательно рассматривают-
ся все дуги, инцидентные исследуемой верши-
не. Если такая дуга находится, то она удаляет-
ся из графа и матрицы непокрытых дуг. После
этого реализуется очередной шаг рекурсии с
определением концевой вершины дуги в каче-
стве исследуемой.
Ш а г 2.2. По завершению перебора дуг,
инцидентных исследуемой вершине, строится
результирующий путь. Для этого его началь-
ное состояние, переданное в качестве аргумен-
та, пополняется кратчайшим путем из иссле-
дуемой вершины графа в целевую вершину.
Ш а г 2.3. Результирующий путь проверя-
ется на покрываемость ранее сохраненными
путями: если среди ранее найденных путей не
находится такой, что содержит все дуги нового
результирующего пути, то этот путь дополняет
набор найденных. После пополнения проверя-
ется наличие еще непокрытых дуг по глобаль-
ной матрице непокрытых дуг. Если еще оста-
ются претенденты, то завершается текущий
шаг рекурсии. При их отсутствии – завершает-
ся вся процедура поиска.
Ш а г 3. Найденное множество путей обыч-
но не является минимальным по количеству со-
держащих в себе дуг и может быть подвергну-
то следующей цепочке оптимизирующих пре-
образований, улучшающих найденное решение.
Ш а г 4. Множество путей упорядочивается
в порядке убывания их длин.
Ш а г 5. Реализуется процедура разложения
найденных путей на простые циклы – каждый
такой путь содержит только одно вхождение
целевой вершины – путь задается последова-
тельностью вершин, которая при описании на-
чинается и завершается номером целевой вер-
шины. При реализации процедуры контроли-
руется уникальность вносимых в множество
простых путей – повторное внесение в резуль-
тирующее множество ранее определенного пу-
ти не проводится. Например, цикл
0102340506
162654610
разложится на простые циклы:
010,
02340,
050,
06162654610.
В данном примере 0, 1, 2, 3, 4, 5, 6 – номера
вершин, целевая (начальная) вершина имеет
номер 0.
Оценка решения улучшается путем ликви-
дации повторов на множестве циклов.
Ш а г 6. Из путей временно исключаются
присутствующие в ней петли.
Ш а г 7. Множество циклов упорядочивает-
ся в порядке убывания их длин.
Ш а г 8. Реализуется процедура исключения
покрываемых циклов, при которой из множе-
ства циклов удаляются те, все дуги которых
присутствуют в каком-то другом цикле из ос-
тавшегося множества. Например, при наличии
во множестве пары путей 06154
50 и 06150 после реализации
процедуры останется только первый из них.
УСиМ, 2017, № 1 41
Ш а г 9. Реализуется процедура исключения
повторения вложенных циклов. В рамках этой
процедуры последовательно перебираются все
циклы результирующего множества. В каждом
цикле ищутся вложенные циклы и после обна-
ружения повторы таких же циклов ликвиди-
руются для всего множества путей. Например,
при наличии пары путей 06234
54650 и 02345
4650 после реализации процедуры
второй путь станет короче – 0234
650. В связи с возможностью наличия
иерархической вложенности циклов процедура
может оказаться полезной при многократном
применении.
Ш а г 10. Множество циклов сортируется
по значениям и из него исключаются прямые
повторы, которые могут там появиться в ре-
зультате ранее выполненных преобразований.
Ш а г 11. Множество циклов упорядочива-
ется в порядке убывания их длин.
Ш а г 12. Реализуется процедура исключе-
ния контуров, покрываемых совокупностью
других оставшихся путей исследуемого мно-
жества.
Ш а г 13. Реализуется восстановление ранее
удаленных путей–петель.
Ш а г 14. Конец.
В рассмотренном примере в результате вы-
полнения шага 2 находятся четыре цикла.
Цикл 1: s0 s1 s2 s3 s5 s0.
Цикл 2: s0 s1 s4 s3 s0.
Цикл 3: s0 s1 s2 s3 s0.
Цикл 4: s0 s1 s4 s0.
Ликвидация повторов дуг в данном простом
примере приводит к удалению третьего цикла,
так как все его дуги покрываются дугами цик-
лов 1, 2: дуги s0 s1, s1 s2, s2 s3 цикла 3
входят в цикл 1, дуга s3 s0 входит в цикл 2.
По оставшимся циклам 1, 2, 4 легко строится
функциональный тест (табл. 3) по всем син-
хронным переходам.
В данном случае при начальном моделиро-
вании на 30 наборах ни разу не был выполнен
переход s1 s3, в результирующем тесте его
тоже нет. Если провести начальное моделиро-
вание на 80 наборах, то можно получить пол-
ный функциональный тест (табл. 4) для син-
хронных переходов. Всего в графе десять син-
хронных и шесть асинхронных переходов (из
каждого состояния в состояние s0). Тест из 16
наборов позволяет проверить все десять син-
хронных переходов. Таким образом, по длин-
ным входным тестам начального моделирова-
ния моделируются все переходы автомата, ал-
горитм построения функционального теста мо-
жет построить полный функциональный тест.
Если же задать короткий для начального моде-
лирования, то не все переходы между состоя-
ниями автомата будут промоделированы и пол-
ный функциональный тест (по всем перехо-
дам) не будет построен.
Т а б л и ц а 3. Неполный функциональный тест, полученный
по результатам моделирования на 30 наборах
Такт Тест Tрез x1 x2 x3 x4 Состояния Sрез
0
1
2
3
4
5
6
7
8
9
10
11
12
0101
1001
0001
1110
1000
0101
0011
1101
1011
0101
0011
0011
s0
s1
s2
s3
s5
s0
s1
s4
s3
s0
s1
s4
s0
Т а б л и ц а 4. Полный функциональный тест, полученный по
результатам моделирования на 80 наборах
Такт Тест Tрез x1 x2 x3 x4 Состояния Sрез
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0101
1001
0001
1110
1000
0101
0011
1101
1011
0101
1010
1110
1000
0101
0011
0011
s0
s1
s2
s3
s5
s0
s1
s4
s3
s0
s1
s3
s5
s0
s1
s4
s0
42 УСиМ, 2017, № 1
Пример 2. На рис. 4 задан граф G = (S, A)
автомата dk14 – одного из тестовых примеров
(benchmarks) конечных автоматов [13]. На дан-
ном примере можно проиллюстрировать те
шаги алгоритма, которые пропущены при рас-
смотрении предыдущего примера.
Рис. 4. Граф для синхронных переходов автомата dk14, на-
чальная вершина 0
Проведем моделирование VHDL-описания
автомата dk14 на 512 наборах значений вход-
ных сигналов. В процессе выполнения про-
граммы, решающей задачи 2 и 3, получим граф
G = (S, A), в котором будет 26 дуг. Граф G =
= (S, A) содержит 71 цикл, в которые входит
1241 дуга. Простых циклов 37, в которые вхо-
дят 249 дуг. В результате решения задачи 3
получим следующие девять циклов:
06614454622
650;
061654610;
06154610;
0546250;
0236140;
023450;
02350;
0230;
010.
Результирующий тест Трез для функцио-
нальной верификации автомата dk14 содержит
54 тестовых набора, покрывает 26 дуг графа
переходов для проверки синхронных перехо-
дов. Если провести моделирование на 40 набо-
рах, то получим тест из 34 наборов и будет по-
крыто только 19 дуг.
Построение теста для выполнения асин-
хронных переходов
Проведенные эксперименты над конечными
автоматами показали, что нахождение теста
для проверки асинхронных переходов началь-
ное моделирование со случайными значениями
rst малоэффективно, так как требуется случай-
ным образом сгенерировать входные наборы с
единичными значениями сигнала rst для каж-
дого состояния автомата. Более целесообразно
построить тест для асинхронных переходов по
тесту для синхронных переходов.
Задача 4. Задан функциональный тест Трез
для проверки выполнения синхронных перехо-
дов. Требуется построить тест асT для провер-
ки асинхронных переходов.
Для решения задачи 4 требуется провести
моделирование автомата на тесте Трез и полу-
чить соответствующую последовательность Sрез
состояний автомата, затем в тест Трез добавить
последний нулевой столбец, которому в фор-
мируемом тесте будет соответствовать сигнал
rst. Для того чтобы построить тест для выпол-
нения асинхронного перехода si s0, надо
найти в последовательности Sрез кратчайшую
подпоследовательность, начинающуюся с si и
заканчивающуюся s0 , затем выделить соответ-
ствующие входные наборы из теста Трез . После
этого надо добавить еще один тестовый набор
(повторить последний набор) и изменить в нем
нулевое значение сигнала rst на единичное
значение, что и позволит выполнить асинхрон-
ный переход из состояния si в состояние s0.
Применим данный подход для теста, задан-
ного в табл. 4. Построим тест для выполнения
асинхронного перехода из состояния s2 в со-
стояние s0 .
В последовательности s0, s1, s2, s3, s5, s0, s1,
s4, s3, s0, s1, s3, s5, s0, s1, s4, s0 (табл. 4) найдем
подпоследовательность s0, s1, s2, которой соот-
ветствуют тестовые наборы
01010
10010.
УСиМ, 2017, № 1 43
Повторим последний вектор 10010 и по-
следний нулевой разряд этого вектора заменим
единичным значением. Получим тест
01010
10010
10011
для выполнения асинхронного перехода из со-
стояния s2 в состояние s0 . Действуя аналогич-
но, построим тесты для всех асинхронных пере-
ходов (табл. 5) автомата Mealy.
Т а б л и ц а 5. Тест для проверки выполнения асинхронных
переходов автомата Mealy
Такт
Тест асT
1x 2x 3x 4x rst
Состояния
acS Асинхронные переходы
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
00001
01010
01011
01010
10010
10011
01010
10100
10101
01010
00110
00111
01010
10100
11100
11101
s0
s0
s1
s0
s1
s2
s0
s1
s3
s0
s1
s4
s0
s1
s3
s5
s0
s0 s0
s1 s0
s2 s0
s3 s0
s4 s0
s5 s0
Вычислительные эксперименты
Для автоматизированного построения функ-
циональных тестов по результатам моделиро-
вания конечных автоматов была разработана
программа CoverGraph, решающая задачи 2 и
3. С использованием программы CoverGraph
были проведены вычислительные эксперимен-
ты на примерах VHDL-описаний конечных ав-
томатов, имеющихся в библиотеке [11].
Эксперименты показали, что VHDL-гене-
рация длинных тестов, содержащих десятки
тысяч тестирующих векторов, осуществляется
за секунды работы персонального компьютера.
VHDL-моделирование автоматов с десятками и
сотнями состояний на таких тестах (для полу-
чения последовательностей состояний Sисх )
занимает несколько минут работы персональ-
ного компьютера. Поэтому рекомендуется вы-
полнить моделирование на возможно более
длинных начальных тестах, чтобы обеспечить
полноту построенного функционального теста.
Отметим, что нетрудно написать тестирующую
программу, в которой будут генерироваться
входные наборы и записываться в текстовый
файл IN.TST, а не считываться из файла.
Выбор длины тестовой последовательно-
сти зависит от размерности автомата – числа
входов и числа состояний автомата. Автоматы с
большим числом состояний требуют более длин-
ных тестовых последовательностей. Однако на
получение графа G(S, A), максимально прибли-
женного к модельному графу ( , )E E EG S A пере-
ходов конечного автомата, влияют также функ-
ции переходов. Если характеристическое мно-
жество булевой функции, представленной ДНФ
Dij, имеет небольшую мощность, то переход
si sj может быть не выполнен при начальном
моделировании, и граф G(S, A) не будет содер-
жать дугу si sj, что приведет к неполному
функциональному тесту, даже если программа
CoverGraph найдет точное решение для графа
G(S, A). Точное решение задачи 3 гарантирует
минимальный по длине тест Трез , однако, на
практике гораздо более важна не длина функ-
ционального теста, а его полнота – покрытие
всех дуг.
Программа CoverGraph позволяет быстро
находить решение и гарантирует полный функ-
циональный тест, соответствующий графу
G(S, A), например, для обработки текстовых
файлов IN.TST, STATE.TST, содержащих 64 ты-
сячи строк (тактов моделирования), требуется
не более минуты. Во всех проведенных экспе-
риментах программа построила полные функ-
циональные тесты. Результаты эксперимента
по нахождению тестов для функциональной
верификации синхронных переходов конечных
автоматов приведены в табл. 6.
Заключение. Представленный подход к по-
лучению функциональных тестов практичен и
позволяет быстро получать компактные тесты
для VHDL-моделей конечных автоматов, опи-
сывающих управляющую логику цифровых
устройств. Получение функциональных тестов
для управляющих блоков цифровых устройств
44 УСиМ, 2017, № 1
позволяет, в свою очередь, конструировать
функциональные тесты для устройства в целом,
так как появляется возможность дополнять тест
и выполнять для заданных состояний управ-
ляющего блока операции над требуемыми опе-
рандами в операционном блоке, когда цифро-
вое устройство представляется в виде компо-
зиции управляющего и операционного блока.
Т а б л и ц а 6. Результаты экспериментов
Имя
автомата
Длина
теста
исхT
Число
состояний
автомата
Число дуг
графа
G(S,A)
Длина теста Трез
для функциональ-
ной верификации
Dk14 40 7 19 34
Dk14 512 7 26 54
Dk14 64000 7 27 64
Dk15 512 4 12 25
Dk17 8000 8 23 63
Dk17 64000 8 23 63
Mealy 80 6 10 16
Mealy 8000 6 10 16
Kirkman 16000 16 32 32
Функциональные тесты для компонентных ав-
томатов позволяют также конструировать тес-
ты для верификации VHDL-описаний иерархи-
ческих автоматов, для которых в определен-
ных состояниях головного автомата начинает
функционировать подчиненный конечный ав-
томат.
1. Ashenden P.J., Lewis J. VHDL-2008. Just the New
Stuff. – Burlington, MA, USA. – Morgan Kaufman
Publishers, 2008. – 244 с.
2. Поляков А.К. Языки VHDL и VERILOG в проекти-
ровании цифровой аппаратуры. – М.: СОЛОН-
Пресс, 2003. – 320 с.
3. Немудров В., Мартин Г. Системы-на-кристалле. Про-
ектирование и развитие. – М.: Техносфера, 2004. –
216 c.
4. Валидация на системном уровне. Высокоуровневое
моделирование и управление тестированием /
М. Чэнь, К. Цинь, Х.-М. Ку и др. – М.: Техносфера,
2014. – 296 с.
5. Лохов А., Рабоволюк А. Комплексная функциональ-
ная верификация СБИС. Система Questa компании
Mentor Graphics // Электроника: наука, технология,
бизнес. – 2007. – № 3. – С. 102–109.
6. Баранов С.И., Скляров В.А. Цифровые устройства
на программируемых БИС с матричной структу-
рой. – М.: Радио и связь, 1986. – 272 с.
7. Skliarova I., Sklyarov V., Sudnison A. Design of
FPGA-based Circuits using Hierarchical Finite State
Machines. – Tallinn: TUT Press, 2012. – 242 p.
8. Иванюк А.А. Проектирование встраиваемых циф-
ровых устройств и систем. – Минск: Бестпринт,
2012. – 337 с.
9. Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д.
Логические основы проектирования дискретных
устройств. – М. : Физматлит, 2007. – 589 c.
10. Авдеев Н.А., Бибило П.Н. Расширение возможно-
стей автоматизированного проектирования цифро-
вых систем при использовании стандарта VHDL’2008
// Информационные технологии. – 2015. – № 7. –
С. 510–520.
11. Thimbleby H. The directed Chinese Postman Problem
// Software Practice and Experience. – 2003. – 33 (11). –
P. 1081–1096.
12. Бурдонов И.Б., Косачев А.С., Кулямин В.В. Неизбы-
точные алгоритмы обхода ориентированных гра-
фов. Детерминированный случай // Программми-
рование. – 2003. – № 5. – С. 11–30.
13. Yang S. Logic Synthesis and Optimization Bench-
marks User Guide. V. 3.0. Technical Report. North. –
Carolina. Microelectronics Center of North Carolina. –
1991. – 44 p.
Поступила 09.04.2015
Тел. для справок: +375 017 284-2084, 284-2076 (Минск)
E-mail: bibilo@newman.bas-net.by, rom@newman.bas-net.by
© П.Н. Бибило, В.И. Романов, 2017
UDC 004.3
Bibilo P.N., Romanov V.I.
Constructing Compact Tests for Functional Verification of VHDL Descriptions of the Finite State Machines
In designing digital devices, the finite state machine (FSM) model is widely used. FSM as well as other models of digital
devices is represented in VHDL and Verilog languages intended to design the digital circuits in the basis of modern VLSI or
user-programmable FPGA logic integrated circuits. Using VHDL-description of the finite state machines, synchronous logic
circuits are synthesized based on the logic elements, called technological (target) basis or target library gates. Now, the syn-
thesis process is automated, and the most important issue in creating the VLSI projects is the problem of verifying the origi-
nal and target specifications of algorithmic descriptions of the designed digital devices and systems. Verification of the cor-
rectness of VHDL-description means checking correspondence between the composed synthesizable VHDL-description and
the digital system specifications. The great advantage of FSM model is that it can be verified. Questa simulation system in-
УСиМ, 2017, № 1 45
corporates the tools for the functional verification of the FSM if the model is written in a certain pattern, namely, in the form
of two VHDL-processes. In the first process, the functions (transition and output) are recorded, and the other process realizes
changes of the states, attaching to changes of the clock signals and the signal setting the FSM to the initial state. The first
process is implemented in a combinational circuit after the circuit implementation, the second one in a memory element regis-
ter. In the process of simulation, Questa simulation system allows recognizing a FSM, which is part of the project. This sys-
tem identifies all passed (in particular modeling session) states of the FSM and calculates the number of passes of arcs in the
transition graph of the FSM. Such tools are very useful; however, FSMs are included usually as parts of control blocks of
more complicated projects. The verification of the whole project requires constructing compact functional tests for the control
unit, FSM. The article considers the problem of automated construction of such tests according to the results of simulation of
VHDL-description of FSM.
The FSM model and its VHDL-description are called correct if, in the FSM transition graph, there is a path from any in-
ternal state to the initial state of the FSM. Note that this condition is obligatory and always holds for the microprogram auto-
mata. The microprogram automata have been applied for a long time in the practice of engineering and are described in the
present time in modern design languages. A test is an ordered sequence of sets of values of input signals fed to input ports of
the FSM VHDL-model in simulation. A special test program (testbench) or a set of programs aimed at testing with different
goals and different ways of organizing the tests is prepared for the simulation. The tests that allow you to check the correct
functioning of the FSM model are called functional.
Problem. A correct VHDL-description of a FSM is given. It is necessary to construct a test Tsrc for functional verification
by simulation that will check the performance of all the available transitions between internal states of the FSM.
The selection of FSM internal states from VHDL-description and the construction of the transition graph is a nontrivial
task. In fact, it is necessary to automate the process of constructing a mathematical model of FSM in form of graph of transi-
tions by analysis VHDL-program of FSM. To solve the problem we suggest an approach for obtaining an approximate solu-
tion based on
simulation of VHDL-description of the FSM on the pseudo-random test Tsrc;
selection from the test Tsrc some test kits, which will be included in the target test Tres.
A program that allows constructing a directed graph of FSM transitions and finding coverage of all arcs on the base of the
simulation results is developed. The input test kits corresponding to the arcs, which are in the coverage, make a test for the
functional verification. An experimental research of the method of constructing compact tests for the verification of VHDL-
models of FSM on standard examples is performed.
1. Ashenden P. J., Lewis J. VHDL-2008. Just the New Stuff. Burlington, MA, USA, Morgan Kaufman Publishers, 2008,
244 p.
2. Polyakov A. K. Yazyiki VHDL i VERILOG v proektirovanii tsifrovoy apparaturyi, M.: SOLON-Press, 2003, 320 p (In
Russian).
3. Nemudrov V., Martin G. Sistemyi-na-kristalle. Proektirovanie i razvitie, M.: Tehnosfera, 2004, 216 p. (In Russian).
4. Chen M., Tsin K., Ku H.-M., Mishra P. Validatsiya na sistemnom urovne. Vyisokourovnevoe modelirovanie i upravle-
nie testirovaniem, M.: Tehnosfera, 2014, 296 p (In Russian).
5. Lohov A., Rabovolyuk A. Kompleksnaya funktsionalnaya verifikatsiya SBIS. Sistema Questa kompanii Mentor Graph-
ics, Elektronika: nauka, tehnologiya, biznes. 2007, N 3, P. 102–109 (In Russian).
6. Baranov S.I., Sklyarov V.A. Tsifrovyie ustroystva na programmiruemyih BIS s matrichnoy strukturoy, M.: Radio i
svyaz, 1986, 272 p (In Russian).
7. Skliarova I., Sklyarov V., Sudnison A. Design of FPGA-based Circuits using Hierarchical Finite State Machines, Tal-
linn: TUT Press, 2012, 272 p.
8. Ivanyuk A. A. Proektirovanie vstraivaemyih tsifrovyih ustroystv i system, Minsk: Bestprint, 2012, 337 p (In Russian).
9. Zakrevskiy A.D., Pottosin Yu.V., Cheremisinova L.D. Logicheskie osnovyi proektirovaniya diskretnyih ustroystv, M.:
Fizmatlit, 2007, 589 p (In Russian).
10. Avdeev N.A., Bibilo P.N. Rasshirenie vozmozhnostey avtomatizirovannogo proektirovaniya tsifrovyih sistem pri is-
polzovanii standarta VHDL’2008. Informatsionnyie tehnologii. 2015, N 7, P. 510–520 (In Russian).
11. Thimbleby H. The directed Chinese Postman Problem. Software Practice and Experience, 2003, V. 33 (11), P. 1081–1096.
12. Burdonov I.B, Kosachev A.S., Kulyamin V.V. Neizbyitochnyie algoritmyi obhoda orientirovannyih grafov. Deter-
minirovannyiy sluchay. Programmirovanie, 2003, N 5, P. 11–30 (In Russian).
13. Yang S. Logic Synthesis and Optimization Benchmarks User Guide, v 3.0, Technical Report, North Carolina, Microelec-
tronics Center of North Carolina, 1991, 44 p.
<<
/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
|
| id | nasplib_isofts_kiev_ua-123456789-124949 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0130-5395 |
| language | Russian |
| last_indexed | 2025-11-30T12:49:20Z |
| publishDate | 2017 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Бибило, П.Н. Романов, В.И. 2017-10-12T12:34:28Z 2017-10-12T12:34:28Z 2017 Построение компактных тестов для функциональной верификации VHDL-описаний конечных автоматов / П.Н. Бибило, В.И. Романов // Управляющие системы и машины. — 2017. — № 1. — С. 35-45. — Бібліогр.: 13 назв. — рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/124949 004.3 Разработана программа, позволяющая по полученной в результате моделирования последовательности состояний автомата строить ориентированный граф переходов автомата и находить покрытие всех дуг. Входные тестовые наборы, соответствующие дугам, вошедшим в покрытие, будут образовывать тест для функциональной верификации. Розроблено програму, яка дозволяє за отриманою в результаті моделювання послідовністю станів автомата будувати орієнтовний граф переходів автомата і знаходити покриття всіх дуг. Вхідні тестові набори, відповідні дугам, які увійшли в покриття, створюватимуть тест для функціональної верифікації. A correct VHDL-description of a finite state machine (FSM) is given. It is necessary to construct a test Tsrc for functional verification by simulation that will check the performance of all the available transitions between internal states of the FSM. The selection of FSM internal states from VHDL-description and the construction of the transition graph is a nontrivial task. In fact, it is necessary to automate the process of constructing a mathematical model of FSM in form of graph of transitions by analysis VHDL-program of FSM. To solve the problem we suggest an approach for obtaining an approximate solution based on simulation of VHDL-description of the FSM on the pseudo-random test Tsrc; selection from the test Tsrc some test kits, which will be included in the target test Tres. A program that allows constructing a directed graph of FSM transitions and finding coverage of all arcs on the base of the simulation results is developed. The input test kits corresponding to the arcs, which are in the coverage, make a test for the functional verification. An experimental research of the method of constructing compact tests for the verification of VHDLmodels of FSM on standard examples is performed. ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Технические средства информатики Построение компактных тестов для функциональной верификации VHDL-описаний конечных автоматов Constructing Compact Tests for Functional Verification of VHDL Descriptions of the Finite State Machines Article published earlier |
| spellingShingle | Построение компактных тестов для функциональной верификации VHDL-описаний конечных автоматов Бибило, П.Н. Романов, В.И. Технические средства информатики |
| title | Построение компактных тестов для функциональной верификации VHDL-описаний конечных автоматов |
| title_alt | Constructing Compact Tests for Functional Verification of VHDL Descriptions of the Finite State Machines |
| title_full | Построение компактных тестов для функциональной верификации VHDL-описаний конечных автоматов |
| title_fullStr | Построение компактных тестов для функциональной верификации VHDL-описаний конечных автоматов |
| title_full_unstemmed | Построение компактных тестов для функциональной верификации VHDL-описаний конечных автоматов |
| title_short | Построение компактных тестов для функциональной верификации VHDL-описаний конечных автоматов |
| title_sort | построение компактных тестов для функциональной верификации vhdl-описаний конечных автоматов |
| topic | Технические средства информатики |
| topic_facet | Технические средства информатики |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/124949 |
| work_keys_str_mv | AT bibilopn postroeniekompaktnyhtestovdlâfunkcionalʹnoiverifikaciivhdlopisaniikonečnyhavtomatov AT romanovvi postroeniekompaktnyhtestovdlâfunkcionalʹnoiverifikaciivhdlopisaniikonečnyhavtomatov AT bibilopn constructingcompacttestsforfunctionalverificationofvhdldescriptionsofthefinitestatemachines AT romanovvi constructingcompacttestsforfunctionalverificationofvhdldescriptionsofthefinitestatemachines |