Аттестационная робота. Проектирование и диагностирование легкотестируемых конечных автоматов

Постановка задачи
Цель работы – разработка процедур автоматизированного синтеза легкотестируемых конечных автоматов, на основе HDL-моделей в форме автоматного шаблона
Автоматный шаблон - это специальная структура HDL -модели, в которой функции переходов и выходов выделены в отдельные процессы, а назначение нового состояния осуществляется в специальном процессе, связанном с синхронизацией.
begin
p1: process (state, data)
begin
case state is
when a0 =>
if data='0' then nextstate<= a0;
y<='0';
else nextstate<= a1;y<='0';
end if;
. . .
p2: process (clk,reset)
begin
if reset='1' then state <= a0;
elsif clk'event and clk = '1'
then state <= nextstate;
end if;
end process;
Модель структурного автомата Хаффмена
Типы ошибок проектирования
ошибка в выборе текущего состояния в операторе when,
ошибка выбора следующего состояния в функции переходов (ai вместо aj),
ошибка в операторе if( ) при анализе входного сигнала;
ошибка в назначении выходного сигнала.

Формы представления моделей автоматов
Формы представления конечных автоматов: таблица переходов-выходов, граф переходов, HDL-модель, граф-схема алгоритма
library IEEE;
use IEEE.std_logic_1164.all;
entity Mur_two is
port (clk: in STD_LOGIC;
data: in BIT; reset: in BIT;
y: out BIT);
end Mur_two;
architecture Mur_two of Mur_two is
type statetype is (a0, a1, a2);
signal state, nextstate: statetype;
begin
p1 : process (state, data) is
begin
case state is
when a0 =>
if (data='0') then nextstate <= a0;
y <= '0';
else nextstate <= a1; y <= '0';
end if;
Граф переходов
VHDL-код
Граф-схема алгоритма
Табличная (ТПВ)

Принципы тестопригодности
Схема является тестопригодной, если процедуры генерации множества тестовых наборов, оценки их эффективности и реализации тестового диагностирования могут быть выполнены при условии соблюдения в установленных пределах финансовых затрат, затрат времени и значений показателей, характеризующих приспособленность схемы к обнаружению неисправностей, поиску места неисправностей и реализации тестового диагностирования (Беннеттс)
Принципы сканирования пути
1) Элементы памяти проверяются отдельно от всей схемы и в первую очередь;
2) КЧ проверяется во вторую очередь с возможностью установки внутренних переменных в любое состояние (независимо от их предыдущего состояния) и наблюдения выходов КЧ непосредственно.
3) Каждому элементу памяти предшествует мультиплексор "2 в 1", управляемый общим сигналом выбора режима сканирования V

Обеспечение тестопригодности HDL-моделей конечных автоматов
Если рассматривать в качестве объекта диагностирования HDL-модели конечных автоматов в форме автоматного шаблона, то для построения на их основе легкотестируемых (тестопригодных) автоматов рассматриваемые модели должны отвечать следующим условиям:
в модели должен быть специальный режим перевода автомата в режим тестирования и наоборот на любом такте работы автомата;
в режиме тестирования автомат может быть установлен в любое состояние за (n-1) тактов, где n – число состояний автомата и может быть организован гамильтонов цикл для любого из состояний автомата;
легкотестируемый автомат должен строиться в автоматизированном режиме средствами САПР.

Организация сдвигового регистра в HDL-модели конечного автомата
Наличие входа TDI (test data input) дает возможность записывать в память код нужного состояния .
entity FSM_MX is
port ( Clk: in STD_LOGIC;
Reset, A, TDI: in STD_LOGIC;
x1, x2, x3: in STD_LOGIC;
y1, y2, y3, y4: out STD_LOGIC);
end;
architecture FSM_MX of FSM_MX is
signal State, NextState: STD_LOGIC_vector (2 downto 0);
signal a1: STD_LOGIC_vector (2 downto 0):="001";
signal a2: STD_LOGIC_vector (2 downto 0):="010";
signal a3: STD_LOGIC_vector (2 downto 0):="011";
signal a4: STD_LOGIC_vector (2 downto 0):="100";
signal a5: STD_LOGIC_vector (2 downto 0):="101";
begin
-- Формирование последовательностной части автомата
Sreg0_CurrentState: process (Clk, Reset)
begin
if Reset='1' then State <= a1;
elsif Clk'event and Clk = '1' then
if A='1' then State <= NextState;
else State <=TDI & State(2 downto 1);
end if;
end if;
end process;

Реализация сдвигового регистра на основе HDL-модели конечного автомата
В результате синтеза предложенной HDL-модели получается схема с мультиплексорами, дающая возможность организовать сканированный путь.

Расширение ТПВ автомата Мура
Расширение TПB автомата путем добавления столбца Sh, в общем случае реализующего произвольную функцию переходов-выходов повышает управляемость состояний автомата и приводит к преобразованию структуры ОД, к стандартному виду Scan Path,

Расширение HDL-модели автомата Мура
Добавление столбца Sh в HDL-модель автомата Мура реализует сдвиговый регистр
Формирование КЧ автомата – описание переходов состояний
Sreg0_NextState: process (State, x1, x2, x3)
begin
case State is
when a1 => NextState <=a2;
when a2 => if Sh = '1' then NextState <= a3;
elsif x1='1' then NextState <= a4;
else NextState <= a3;
end if;
when a3 => if Sh = '1' then NextState <= a4;
else NextState <= a5;
end if;
when a4 => if Sh = '1' then NextState <= a5;
elsif x2='1' then NextState <= a3;
elsif x3='1' then NextState <= a4;
else NextState <= a5;
end if;
when a5 => NextState <= a1;
when others => NextState <= a1;
end case;
end process;
-- Формирование выходных сигналов
y1<='1' when State=a2 else '0';
y2<='1' when State=a3 else '0';
y3<='1' when State=a4 else '0';
y4<='1' when State=a5 else '0';
end;

Диагностический эксперименнт над легкотестируемым автоматом Мура
Временные диаграммы моделирования гамильтонова цикла автомата Мура с сигналом Sh (FSM_ Sh)

Расширение ТПВ автомата Мили
Расширение TПB автомата путем добавления столбца Sh, в общем случае реализующего произвольную функцию переходов-выходов повышает управляемость состояний автомата и приводит к преобразованию структуры ОД, к стандартному виду Scan Path,

Расширение HDL-модели автомата Мили
Добавление столбца Sh в HDL-модель автомата Мили
-- Формирование КЧ автомата – описание переходов состояний
Sreg0_NextState: process (State, x1, x2, x3)
begin
y1 <= '0'; y2 <= '0'; y3 <= '0'; y4 <= '0'; y5 <= '0';
case State is
when a1 => if Sh = '1' then NextState <= a2;
else NextState <= a2; y1 <= '1';y2 <= '1';
end if;
when a2 => if Sh = '1' then NextState <= a3;
elsif x1='1' then NextState <= a4; y4<='1';
else NextState <= a3; y3 <= '1';
end if;
when a3 => if Sh = '1' then NextState <= a4;
else NextState <= a5;
end if;
when a4 => if Sh = '1' then NextState <= a5;
elsif x2='1' then NextState<=a3; y4<='1'; y5<= '1';
elsif x3='1' then NextState <= a4;
else NextState <= a5; y3 <= '1';
end if;
when a5 => if Sh = '1' then NextState <= a1;
else NextState <= a1; y5 <= '1';
end if;
when others => NextState <= a1;
end case;
end process;

Схемная реализация легкотестируемого автомата
Используемое устройство: плата Spartan 3E, микросхема FPGA XC3S500E, Package FG 320. Пакет САПР: XILINX ISE 10.1.

Диагностические эксперименты над автоматами
Входная последовательность X называется отличительной для автомата A (X,Y,Z,δ,λ), если выходная последовательность автомата, как реакция на X, различна для любого начального состояния.
Входная последовательность X называется установочной для автомата A (X,Y,Z,δ,λ), , если его конечное состояние δ(Z,x), может быть однозначно определено по выходной последовательности λ(Z,x), для всех Z.
Входная последовательность X автомата A (X,Y,Z,δ,λ), которая устанавливает его в определенное конечное состояние независимо от состояния выхода и начального состояния, называется синхронизирующей последовательностью.
Пусть Z(z1,z2, … zn) подмножество состояний минимального автомата А. Множество X(x1,x2,…xm) будем называть множеством характеристических последовательностей (ХП), если для каждого начального состояния zi, реакция на xk различна.

Аппаратурные затраты на обеспечение тестопигодности
Как видно из приведенных результатов оптимальным по аппаратурным затратам является введение дополнительного режима повышения управляемости состояний автомата (дополнительный столбец в ТПВ) как для автомата Мура так и для автомата Мили. Аппаратурные затраты при том возрастают на 20-25% в зависимости от типа автомата.