Ключевые слова: конечный автомат, торговый автомат
Конечный автомат (FSM), называемый также автоматом, — это математическая модель, представляющая конечное число состояний и поведение, такое как переходы и действия между этими состояниями. Конечный автомат — это не только инструмент описания схем, но и образ мышления; он широко используется на системном уровне и уровне RTL при проектировании схем.
Типы конечных автоматов
В Verilog конечные автоматы в основном используются при проектировании синхронной последовательностной логики и могут переключать состояния последовательностных схем между конечным числом состояний в соответствии с определёнными требованиями и правилами. Направление переключения состояний зависит не только от входных значений, но и от текущего состояния. Конечные автоматы можно разделить на 2 категории: автоматы Мура и автоматы Мили.
Конечный автомат типа Мура
Выход автомата Мура зависит только от текущего состояния, а не от текущего входа.
Выход остаётся стабильным в течение полного тактового цикла. Даже если входной сигнал изменяется в это время, выход не изменится. Влияние входа на выход может отразиться только в следующем тактовом цикле. Это также важная особенность автомата Мура: вход и выход изолированы.

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

Процесс проектирования конечного автомата
Нарисуйте диаграмму переходов состояний в соответствии с требованиями проектирования, определите тип используемого конечного автомата и обозначьте различные входные и выходные сигналы, что больше помогает при программировании. Обычно чаще всего используется 3-сегментный конечный автомат типа Мили. Далее на конкретном примере проектирования автоматического торгового автомата иллюстрируется процесс проектирования конечного автомата.
Автоматический торговый автомат
Функциональное описание автоматического торгового автомата приведено ниже:
Цена напитка — 2 юаня. Торговый автомат может принимать только монеты номиналом 0.5 юаня и 1 юань. Учитывайте выдачу сдачи и выдачу товара. Процессы внесения монет и выдачи товара выполняются по одному за раз; не будет ситуации, когда несколько монет вносятся одновременно или несколько бутылок напитка выдаются одновременно. Только после того, как каждый цикл работы торгового автомата завершит внесение монет, выдачу товара и выдачу сдачи, он сможет перейти в новое состояние автоматической продажи.
Диаграмма переходов рабочих состояний торгового автомата показана ниже, включая состояния входных и выходных сигналов.
Здесь coin = 1 означает, что внесена монета 0.5 юаня, а coin = 2 означает, что внесена монета 1 юань.

Проектирование конечного автомата: 3-сегментный стиль (рекомендуется)
Проектирование конечного автомата выглядит следующим образом:
- (0) Сначала определите кодирование конечного автомата в соответствии с количеством состояний. Использование кодирования для присваивания значений регистрам состояний улучшает читаемость кода.
- (1) Первый сегмент конечного автомата: последовательностная логика, неблокирующее присваивание, для передачи состояния регистра.
- (2) Второй сегмент конечного автомата: комбинационная логика, блокирующее присваивание, для определения следующего состояния конечного автомата на основе текущего состояния и текущего входа.
- (3) Третий сегмент конечного автомата: последовательностная логика, неблокирующее присваивание. Поскольку это конечный автомат Мили, определите выходной сигнал на основе текущего состояния и текущего входа.
Пример
// 2 юаня за бутылку напитка
// поддерживаются только 2 монеты: 5 цзяо и 1 юань
// завершите функцию продажи и выдачи сдачи
module vending_machine_p3 (
input clk ,
input rstn ,
input [1:0] coin , //01 для 0.5 цзяо, 10 для 1 юаня
output [1:0] change ,
output sell //выдать напиток
);
// декодирование состояния автомата
parameter IDLE = 3'd0 ;
parameter GET05 = 3'd1 ;
parameter GET10 = 3'd2 ;
parameter GET15 = 3'd3 ;
//переменная автомата
reg [2:0] st_next ;
reg [2:0] st_cur ;
//(1) передача состояния
always @(posedge clk or negedge rstn) begin
if (!rstn) begin
st_cur <= 'b0 ;
end
else begin
st_cur <= st_next ;
end
end
//(2) переключение состояния, с использованием блокирующего присваивания для комбинационной логики
//все элементы case должны быть перечислены полностью
always @(*) begin
//st_next = st_cur ;//Если варианты условий рассмотрены не полностью, можно присвоить начальное значение, чтобы устранить защёлку
case(st_cur)
IDLE:
case (coin)
2'b01: st_next = GET05 ;
2'b10: st_next = GET10 ;
default: st_next = IDLE ;
endcase
GET05:
case (coin)
2'b01: st_next = GET10 ;
2'b10: st_next = GET15 ;
default: st_next = GET05 ;
endcase
GET10:
case (coin)
2'b01: st_next = GET15 ;
2'b10: st_next = IDLE ;
default: st_next = GET10 ;
endcase
GET15:
case (coin)
2'b01,2'b10:
st_next = IDLE ;
default: st_next = GET15 ;
endcase
default: st_next = IDLE ;
endcase
end
//(3) выходная логика, с использованием неблокирующего присваивания
reg [1:0] change_r ;
reg sell_r ;
always @(posedge clk or negedge rstn) begin
if (!rstn) begin
change_r <= 2'b0 ;
sell_r <= 1'b0 ;
end
else if ((st_cur == GET15 && coin ==2'h1)
|| (st_cur == GET10 && coin ==2'd2)) begin
change_r <= 2'b0 ;
sell_r <= 1'b1 ;
end
else if (st_cur == GET15 && coin == 2'h2) begin
change_r <= 2'b1 ;
sell_r <= 1'b1 ;
end
else begin
change_r <= 2'b0 ;
sell_r <= 1'b0 ;
end
end
assign sell = sell_r ;
assign change = change_r ;
endmodule
Структура тестбенча выглядит следующим образом. В ходе моделирования воспроизводятся четыре сценария, а именно:
case1 соответствует последовательному внесению четырех монет по 0.5 yuan; case2 соответствует порядку внесения монет 1 yuan - 0.5 yuan - 1 yuan; case3 соответствует порядку 0.5 yuan - 1 yuan - 0.5 yuan; case4 соответствует порядку трех идущих подряд монет по 0.5 yuan, за которыми следует одна монета 1 yuan.
Пример
module test ;
reg clk;
reg rstn ;
reg [1:0] coin ;
wire [1:0] change ;
wire sell ;
//генерация тактового сигнала
parameter CYCLE_200MHz = 10 ; //
always begin
clk = 0 ; #(CYCLE_200MHz/2) ;
clk = 1 ; #(CYCLE_200MHz/2) ;
end
//генерация мотивации
reg [9:0] buy_oper ; //хранить состояние операции покупки
initial begin
buy_oper = 'h0 ;
coin = 2'h0 ;
rstn = 1'b0 ;
#8 rstn = 1'b1 ;
@(negedge clk) ;
//case(1) 0.5 -> 0.5 -> 0.5 -> 0.5
#16 ;
buy_oper = 10'b00_0101_0101 ;
repeat(5) begin
@(negedge clk) ;
coin = buy_oper[1:0] ;
buy_oper = buy_oper >> 2 ;
end
//case(2) 1 -> 0.5 -> 1, выдача сдачи
#16 ;
buy_oper = 10'b00_0010_0110 ;
repeat(5) begin
@(negedge clk) ;
coin = buy_oper[1:0] ;
buy_oper = buy_oper >> 2 ;
end
//case(3) 0.5 -> 1 -> 0.5
#16 ;
buy_oper = 10'b00_0001_1001 ;
repeat(5) begin
@(negedge clk) ;
coin = buy_oper[1:0] ;
buy_oper = buy_oper >> 2 ;
end
//case(4) 0.5 -> 0.5 -> 0.5 -> 1, выдача сдачи
#16 ;
buy_oper = 10'b00_1001_0101 ;
repeat(5) begin
@(negedge clk) ;
coin = buy_oper[1:0] ;
buy_oper = buy_oper >> 2 ;
end
end
//(1) автомат Мили с 3-сегментным описанием
vending_machine_p3 u_mealy_p3 (
.clk (clk),
.rstn (rstn),
.coin (coin),
.change (change),
.sell (sell)
);
//завершение моделирования
always begin
#100;
if ($time >= 10000) $finish ;
end
endmodule // test
Результаты моделирования следующие:
Из рисунка видно, что сигнал sell, который представляет действие выдачи товара, может быть нормально установлен в высокий уровень после завершения внесения монеты, а сигнал change, который представляет действие выдачи сдачи, также может выдавать правильный сигнал сдачи или отсутствия сдачи в соответствии со сценарием ввода монет.
Модификация конечного автомата: 2-сегментный стиль
Объедините описания сегментов 2 и 3 3-сегментного конечного автомата, оставьте остальные части без изменений, и конечный автомат станет 2-сегментным описанием.
Изменённые части приведены ниже:
Пример
//везде используется блокирующее присваивание для комбинационной логики
reg [1:0] change_r ;
reg sell_r ;
always @(*) begin //все элементы case должны быть полностью отображены
case(st_cur)
IDLE: begin
change_r = 2'b0 ;
sell_r = 1'b0 ;
case (coin)
2'b01: st_next = GET05 ;
2'b10: st_next = GET10 ;
default: st_next = IDLE ;
endcase // case (coin)
end
GET05: begin
change_r = 2'b0 ;
sell_r = 1'b0 ;
case (coin)
2'b01: st_next = GET10 ;
2'b10: st_next = GET15 ;
default: st_next = GET05 ;
endcase // case (coin)
end
GET10:
case (coin)
2'b01: begin
st_next = GET15 ;
change_r = 2'b0 ;
sell_r = 1'b0 ;
end
2'b10: begin
st_next = IDLE ;
change_r = 2'b0 ;
sell_r = 1'b1 ;
end
default: begin
st_next = GET10 ;
change_r = 2'b0 ;
sell_r = 1'b0 ;
end
endcase // case (coin)
GET15:
case (coin)
2'b01: begin
st_next = IDLE ;
change_r = 2'b0 ;
sell_r = 1'b1 ;
end
2'b10: begin
st_next = IDLE ;
change_r = 2'b1 ;
sell_r = 1'b1 ;
end
default: begin
st_next = GET15 ;
change_r = 2'b0 ;
sell_r = 1'b0 ;
end
endcase
default: begin
st_next = IDLE ;
change_r = 2'b0 ;
sell_r = 1'b0 ;
end
endcase
end
Создайте экземпляр недавно изменённого модуля выше в 3-сегментном тестбенче для выполнения моделирования. Результаты следующие:
Из рисунка видно, что сигнал выдачи товара sell и сигнал сдачи change на один такт раньше, чем выход 3-сегментного конечного автомата. Это связано с тем, что выходные сигналы являются блокирующими присваиваниями.
Как показано на обведённых красным кружком участках рисунка, на выходных сигналах появляются глитч-импульсы. Это связано с тем, что входные сигналы асинхронны, а выходные сигналы являются выходами комбинационной логики без тактового управления.
На практике, если входные сигналы синхронизированы с тактовым сигналом, такие глитч-импульсы не появятся. Если входные сигналы асинхронны, сигналы следует сначала синхронизировать.
Модификация конечного автомата: 1-сегментный стиль (использовать с осторожностью)
Объедините описания сегментов 1, 2 и 3 3-сегментного конечного автомата, и конечный автомат станет 1-сегментным описанием.
Изменённые части приведены ниже:
Пример
//(1) описание с использованием одной переменной состояния
reg [1:0] change_r ;
reg sell_r ;
always @(posedge clk or negedge rstn) begin
if (!rstn) begin
st_cur <= 'b0 ;
change_r <= 2'b0 ;
sell_r <= 1'b0 ;
end
else begin
case(st_cur)
IDLE: begin
change_r <= 2'b0 ;
sell_r <= 1'b0 ;
case (coin)
2'b01: st_cur <= GET05 ;
2'b10: st_cur <= GET10 ;
endcase
end
GET05: begin
case (coin)
2'b01: st_cur <= GET10 ;
2'b10: st_cur <= GET15 ;
endcase
end
GET10:
case (coin)
2'b01: st_cur <= GET15 ;
2'b10: begin
st_cur <= IDLE ;
sell_r <= 1'b1 ;
end
endcase
GET15:
case (coin)
2'b01: begin
st_cur <= IDLE ;
sell_r <= 1'b1 ;
end
2'b10: begin
st_cur <= IDLE ;
change_r <= 2'b1 ;
sell_r <= 1'b1 ;
end
endcase
default: begin
st_cur <= IDLE ;
end
endcase // case (st_cur)
end // else: !if(!rstn)
end
Создайте экземпляр недавно изменённого модуля выше в 3-сегментном тестбенче для выполнения моделирования. Результаты следующие:
Из рисунка видно, что выходные сигналы точно такие же, как у 3-сегментного конечного автомата.
Недостаток 1-сегментного конечного автомата состоит в том, что множество видов логики смешаны вместе, что затрудняет последующее сопровождение. Когда конечный автомат и выходные сигналы немногочисленны, можно попробовать этот стиль описания.
Модификация конечного автомата: тип Мура
Если для описания рабочего процесса торгового автомата используется автомат Мура, то необходимо добавить ещё 2 кодировки состояний, чтобы описать входной сигнал и состояние конечного автомата, когда автомат Мили выдаёт выходные сигналы.
Код на Verilog для автоматического торгового автомата, описанного с помощью 3-сегментного автомата Мура, выглядит следующим образом:
Пример
input clk ,
input rstn ,
input [1:0] coin , //01 для 0.5 цзяо, 10 для 1 юаня
output [1:0] change ,
output sell //выдать напиток
);
// декодирование состояния автомата
parameter IDLE = 3'd0 ;
parameter GET05 = 3'd1 ;
parameter GET10 = 3'd2 ;
parameter GET15 = 3'd3 ;
// новое состояние для автомата Мура
parameter GET20 = 3'd4 ;
parameter GET25 = 3'd5 ;
//переменная автомата
reg [2:0] st_next ;
reg [2:0] st_cur ;
//(1) передача состояния
always @(posedge clk or negedge rstn) begin
if (!rstn) begin
st_cur <= 'b0 ;
end
else begin
st_cur <= st_next ;
end
end
//(2) переключение состояния, с использованием блокирующего присваивания для комбинационной логики
always @(*) begin //все элементы case должны быть полностью отображены
case(st_cur)
IDLE:
case (coin)
2'b01: st_next = GET05 ;
2'b10: st_next = GET10 ;
default: st_next = IDLE ;
endcase
GET05:
case (coin)
2'b01: st_next = GET10 ;
2'b10: st_next = GET15 ;
default: st_next = GET05 ;
endcase
GET10:
case (coin)
2'b01: st_next = GET15 ;
2'b10: st_next = GET20 ;
default: st_next = GET10 ;
endcase
GET15:
case (coin)
2'b01: st_next = GET20 ;
2'b10: st_next = GET25 ;
default: st_next = GET15 ;
endcase
GET20: st_next = IDLE ;
GET25: st_next = IDLE ;
default: st_next = IDLE ;
endcase // case (st_cur)
end // always @ (*)
// (3) выходная логика,
// задержка на один такт при использовании неблокирующего присваивания
reg [1:0] change_r ;
reg sell_r ;
always @(posedge clk or negedge rstn) begin
if (!rstn) begin
change_r <= 2'b0 ;
sell_r <= 1'b0 ;
end
else if (st_cur == GET20 ) begin
sell_r <= 1'b1 ;
end
else if (st_cur == GET25) begin
change_r <= 2'b1 ;
sell_r <= 1'b1 ;
end
else begin
change_r <= 2'b0 ;
sell_r <= 1'b0 ;
end
end
assign sell = sell_r ;
assign change = change_r ;
endmodule
Создайте экземпляр изменённого автомата Мура, приведённого выше, в 3-сегментном тестбенче для выполнения моделирования. Результаты приведены ниже:
Из рисунка видно, что выходной сигнал задержан на один такт по сравнению с 3-сегментным автоматом Мили. Это связано с тем, что вход в недавно добавленный автомат кодирования требует задержки в один такт. В этом случае использование неблокирующего присваивания для выхода приведёт к задержке итогового выходного сигнала на один такт. Это также особенность автомата Мура.
При присваивании выходного сигнала использование блокирующего присваивания может сдвинуть его на один такт раньше.
Выходная логика изменяется следующим образом.
Пример
// (3.2) выходная логика, с использованием блокирующего присваивания
reg [1:0] change_r ;
reg sell_r ;
always @(*) begin
change_r = 'b0 ;
sell_r = 'b0 ; //не перечисляя все условия, инициализируем их
if (st_cur == GET20 ) begin
sell_r = 1'b1 ;
end
else if (st_cur == GET25) begin
change_r = 2'b1 ;
sell_r = 1'b1 ;
end
end
Результаты моделирования блокирующего присваивания для выходного сигнала приведены ниже:
Из рисунка видно, что выходной сигнал теперь соответствует 3-сегментному автомату Мили.
Скачать исходный код
Скачать


