Синтез конечного и структурного автомата

Question

[imwode]

Может быть есть те, кто знает или в настоящее время изучает дискретную математику и поможет?

Я пытаюсь сделать достаточно простую вещь — синтезировать автомат обработчика нажатия кнопки. Надо понять:
1. Была ли нажата ли кнопка
2. Если да, то было ли это короткое нажатие
3. Или длинное

Второй день читаю пособия и статьи (например эту), и все никак не могу ухватить основной смысл.

Вводные: у нас есть кнопка. Она может быть нажата и не нажата. При нажатии кнопки запускается дебаунс-таймер и отмеряет интервал короткого нажатия кнопки. Если во время работы этого таймера кнопку отпустили, возвращаемя в исходное положение. Если таймер отработал и кнопка все еще нажата, запускается таймер измерения интервала длинного нажатия. Если во время работы этого таймера кнопка отпущена, фиксируем короткое нажатие и уходим в исходное состояние. И т.д.

Я сделал такую карту переходов и выходов.

Последующее курение пособий показало, что я, похоже, неправильно понял суть входов. Т.е. вход должен быть один — x1(кнопка). Вход может быть в состоянии 0 или 1.

Дальше непонятно чем же все-таки являются таймеры — это входы или состояния? Или это вообще счетчики, инкрементирующиеся по второму входному сигналу — такту? Еще периодически встречается термин «функции возмущения», но с ними вообще ничего непонятно.

А на следующем этапе мне еще нужно будет преобразовать это в структурный автомат и синтезировать логическую схему. Мааамаааа. Помогите, пожалуйста. Хотя бы с правильным синтеза автомата Мили

Answer 1

[nerudo]

Что входы, а что состояния в данном случае- вопрос исключительно терминологический. Проблема в том, что в рамки классического описания/синтеза КА счетчики не вписываются. Поэтому в академическом стиле их описывают отдельно, т.е. КА имеет выход для управления этим счетчиком и вход, являющийся значением счетчика. Поэтому если вам необходимо синтезировать КА «на бумажке», то лучше поступить именно так.
Другое дело, если вы описываете ваш автомат «на практике» на каком-нибудь языке программирования или описания аппаратуры. Здесь плодить лишние сущности смысла никакого нет и счетчик с его сигналом управления интегрируется непосредственно в описание КА.
Я бы рекомендовал вам перерисовать ваш автомат в виде графа, а не таблицы — станет намсного нагляднее. Ну а для начала потренироваться на более простой версии — просто детектирования нажатия с дебаунсом.

Comments

[imwode]

Да, так вчера и сделал (начал с графа). После этого нарисовалась довольно понятная таблица, которая однозначно описывает автомат. В софте реализовал после этого глядя только на таблицу минуты за три.
А вот как от этого перейти к структурному автомату и потом реализовать на логике, не изучив учебник по дискретной математике, я думаю понять нереально.

[nerudo]

Это не сложно, просто много механической работы:
1) Кодируете состояния конечного автомата, обычно в двоичном виде, если нет каких-то специальных требований. Т.е. автомат из трех состояний будет описываться двумя битами памяти, имеющими значения (к примеру) 00, 01, 10
2) На базе графа переходов создаете логические функции (таблицы истинности) для первой комбинационной схемы (если смотреть на классическую структуру КА, где входы в эту КС — общие входы и текущее состояние КА, а выходы — новое состояние КА) для каждого бита состояния КА.
3) Минимизируете эти логические функции с использованием, к примеру карт Карно
Теперь у вас готово 2/3 КА. Рисуете КС1 (разбивая на дискретные логические элементы) и триггеры памяти (хранящие состояния КА)
4) Создаете КС2, входами которой являются текущие состояния КА и (для автомата Мили) общие входы. Выходы КС2 — выходы вашего устройства. Так же расписываете таблицы истинности для каждого выхода и минимизируете логические функции.
5) Дорисовываете КС2 к предыдущей структуре.
6) Идете за зачетом.

Классическая стуктура: o0o.pisem.net/TA/teoravt.files/image147.gif

[imwode]

гыгыгыы, я за зачетом 10 лет назад последний раз ходил :-)
попробую еще, попытка не пытка :-)

[nerudo]

Тогда не парьте себе мозг и опишите КА на VHDL/verilog :)

Answer 2

[EvilMan]

Пусть состояние кнопки считывается через определённые промежутки времени, достаточно короткие, но не очень. Состояние кнопки: 0 — кнопка не нажата, 1 — кнопка нажата.

состояние автомата/состояние кнопки	0	1
0	0	1
1	0	2
2	0	3
3	0	3

Состояние автомата 1 — короткое нажатие кнопки, а состояние автомата 2 — длинное нажатие кнопки.

Comments

[EvilMan]

Поправка. Коротким нажатием будет переход из состояния 1 в состояние 0, а длинным — из состояния 1 в состояние 2.

[imwode]

не, это все как-то неправильно. У кнопки может быть только два состояния — нажата или не нажата в каждый момент времени. Длинное нажатие — это состояние выхода автомата.

[EvilMan]

Так у кнопки всего два состояния (0 и 1 — две крайних правых колонки). Возможно, я просто неудачно разместил названия в таблице («состояние автомата» — название колонки, «состояние кнопки» — название строки).

Answer 3

[parilov]

Решение на verilog. FSM Миля. Нажатие кнопки до 6 тактов — короткое. Больше — длинное.
Сделал проверку, что нажатие более 10 тактов сразу считаем длительным.
Не сделал — возврат КА и выходов в исходное состояние, защиты от дребезга в сигнале кнопки,
менее громоздкое вычисление assign short и assign long без сравнений всего count.

FSM Mealy

`timescale 1ns / 1ps
module fsm_mili(
    input clk, input button, input reset,
    output short,//=1 if in fsm recd short (1..5 tick) button press
    output long//=1 if in fsm recd long (6..10 tick) button press
    );

parameter st_start = 2'b00;
parameter st_press_on = 2'b01;
parameter st_finish = 2'b11;

reg [1:0] state = st_start;
reg [3:0] count = 4'h0;

// inc count if posedge clk and button press
// reset count if end cycle
always@(posedge clk)
	if (state == st_press_on) count = count + 1;
	else if (state == st_start) count = 4'h0;

always@(posedge clk)
	if (reset) begin state <= st_start;
	end
	else
		case (state)
			st_start : begin
// wait button press
				if (button == 1'b1) state <= st_press_on;
				else state <= st_start;
			end
// wait button press_off OR (count clk when button press) = 10
			st_press_on : begin
				if (button == 1'b0 || count == 4'hA) state <= st_finish;
				else state <= st_press_on;
			end
// comment condition for go fsm to start state
// now fsm in one cycle, else fsm must be infinite  
			st_finish : begin
				//state <= st_start;
			end
			default : begin
				state <= st_start;
			end   
		endcase

assign short = (state == st_finish) & (count < 4'h6);
assign long = (state == st_finish) & (count >= 4'h6);
endmodule

Comments

[imwode]

Да, у меня есть код автомата на Си, есть конверторы в верилог. Только мне казалось, что верилог — это язык для ФПГА и, значит, можно эквивалентную логическую схему как-то получить. А вот как — не нашел.

[nerudo]

Скомпилировать его в какой-нибудь среде разработки (лучше квартус — удобнее) и запустить средство логического анализа проекта. В квартусе Tools => Netlist viewers.

[imwode]

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