Ключевые слова: конечный автомат, торговый автомат

Конечный автомат (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.

Пример

`timescale 1ns/1ps

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-сегментным описанием.

Изменённые части приведены ниже:

Пример

//(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-сегментного автомата Мура, выглядит следующим образом:

Пример

module  vending_machine_moore    (
    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-сегментному автомату Мили.

Скачать исходный код

Скачать