1i7 (1i7) wrote,
1i7
1i7

Categories:

Лабораторная работа 4, часть 1: простые конечные автоматы (2)

Продолжение, начало Лабораторная работа 4, часть 1: простые конечные автоматы (1) <<

предыдущие лабы

Упражнение 2: знакомство с конечными автоматами - светофор



Теперь, когда мы окончательно освоили работу с генератором тактового сигнала и регистрами на Verilog+ПЛИС, пришло время сделать что-то более понятное широкому кругу лиц и приближенное к реальной жизни, чем просто мигающая лампочка. Сделаем сфетофор, который поочереди мигает 3мя лампочками. Но основная полезность светофора в качестве задания в данной лабораторной работе заключается в том, что его реализация представляет из себя простой и наглядный конечный автомат и в дальнейшем именно она ляжет в основу реализаций таких еще более понятных и полезных вещей, как микроэлектронные биороботы и подмножество настоящего процессора MIPS.

Конечный автомат (или машина состояний или стейт-машина - finit state machine) представляет из себя всего-навсего способ описания поведения системы в виде конечного набора состояний и событий, которые переводят систему из одного состояния в другое. Но чтобы долго не мусолить формальные определения, сразу попробуем описать светофор в виде конечного автомата.

Для этого в первую очередь все посмотрим на сам светофор:


и увидим, что он судя по всему может находиться всего в 3х состояниях: красный (red), желтый (yellow) и зеленый (green). Событием для перехода от одного состояния к другому будет истечение времени нахождения в текущем состоянии (для простоты будем считать, что в каждом из состояний сфетофор находится секунду).

Цепочка перехода: красный>желтый>зеленый>желтый>красный>желтый>зеленый>желтый>...

Нарисуем все состояния на диаграмме в виде именованых кружочков, а события перехода попробуем обозначить подписанными стрелочками:



Как видим, переход из желтого состояния по событию "истекла 1 секунда" в данном случае не однозначен, т.к. исходя из одной только нарисованной машины состояний не очень ясно, куда в этот момент переходить - в красное или зеленое. Чтобы сделать правильный выбор, нужно знать в каком состоянии машина находилась перед этим - если она была красная, значит переходить нужно в зеленый, а если была зеленая, то нужно переходить в красный.

Для решения этого вопроса разобьем состояние желтый на две части - желтый1 (yellow1) и желтый2 (yello2) и перерисуем машину новым образом:





итого получили всего четыре состояния с циклическим переходом: красный>желтый1>зеленый>желтый2>красный>...

Проблема решена, неоднозначности исправлены, конечный автомат получен, приступаем к реализации.

Для начала немного поправим модуль clock_divider из предыдущего упражнения так, чтобы он не генерировал подряд секундные импульсы бесконечно, а по команде отсчитывал секунду и останавливался до новой команды.

timer.v
module timer
#(parameter delay_bit = 25)
(
    input  clock,
    input  reset,
    output finish
    );

    reg [delay_bit:0] counter;

    always @(posedge clock, posedge reset)
    begin
        if (reset)
            counter <= 0;
        else if (!counter [delay_bit])
            counter <= counter + 1;
    end

    assign finish = counter [delay_bit];
endmodule


Из новых вещей здесь видим конструкцию if/else if/else, которую можно использовать внутри блока always и макрос #(parameter delay_bit = 25) - на тот случай, если мы захотим изменить время сигнала таймера извне (например для 2хсекундного таймера заменить индекс бита и размер счетчика с 25 на 26) и при этом не переписывать модуль (акцентировать внимание на подробностях этой возможности языка Verilog здесь не буду, просто обозначу ее существование).

Входной сигнал clock традиционно - тактовый сигнал 25МГц, выходной сигнал finish опять традиционно показывает статус таймера (0 - считает, 1 - счет окончен), вход reset позволяет управлять таймером - если подать на него 1, таймер будет "взведен" для нового старта (обнуляем счетчик), после этого подать 0 - таймер запустится и отсчитает секунду.

Переходим к реализации конечного автомата в точном соответствии с нарисованной диаграммой - модуль traffic_light.

Для начала определим внешний интерфейс модуля - на входе нам нужен тактовый сигнал clock, который будет гонять светофор из одного состояния в другое, а на выход будем оптавлять значение текущего состояния out_state - т.к. у нас возможных состояний всего 4, для их кодирования как раз хватит ровно 2 бита:

module traffic_light(
    input clk,
    output [1:0] out_state
    );

Перечисляем константы с именами состояний (2 бита каждая - одно из этих значений всегда будет принимать выход out_state):
  // enumerate state constants
    parameter state_green = 2'b00;
    parameter state_yellow1 = 2'b01;
    parameter state_red = 2'b10;
    parameter state_yellow2 = 2'b11;

И заводим для хранения значения текущего состояния автомата и следующего состояния автомата (так реализована логика перехода - см ниже) два внутренних регистра (тоже по два бита - они будут принимать значения описанных выше констант):
reg [1:0] state, next_state;

Подключаем таймер:
  // one second timer controls
    wire timer_one_second;
    reg timer_one_second_reset;
     timer one_second(.clock(clk), .reset(timer_one_second_reset), .finish(timer_one_second));

И описываем логику перехода между состояниям машины - главная цель - получить значение для следующего состояния светофора и записать его в регистр next_state:

   // detect next state depending on current state
    // and current clock - change state one time per second:
    // green>yellow1>red>yello2>green>...
    always @(*)
    begin
        // start timer if it was reset
        timer_one_second_reset = 0;
        // next state would not change by default
        next_state = state;

        case (state)
            state_green:
               begin
                   if(timer_one_second)
                   begin
                         // arm timer to count one second
                         // before moving to the next state
                         timer_one_second_reset = 1;
                         // move to the next state
                         next_state = state_yellow1;
                   end
               end
               state_yellow1:
               begin
                   if(timer_one_second)
                   begin
                       // arm timer to count one second
                       // before moving to the next state
                       timer_one_second_reset = 1;
                       // move to the next state
                       next_state = state_red;
                   end
              end
               state_red:
               begin
                   if(timer_one_second)
                   begin
                       // arm timer to count one second
                       // before moving to the next state
                       timer_one_second_reset = 1;
                       // move to the next state
                       next_state = state_yellow2;
                   end
               end
               state_yellow2:
               begin
                   if(timer_one_second)
                   begin
                       // arm timer to count one second
                       // before moving to the next state
                       timer_one_second_reset = 1;
                       // move to the next state
                       next_state = state_green;
                    end
                end
        endcase
    end


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

always @(*)
Звездочка в списке чувствительности предлагает компилятору вставить в него все сигналы, которые могут каким-то образом повлиять на значения, вычисляемые внутри текущего блока always - это могут быть конечно сигналы, которые стоят в правой части операторов присвоения <= или =, но также сигналы, которые участвуют в качестве условия в частности в конструкциях case или if.

В данном случае запись со звездочкой будет эквивалентна указанию сигналов state и timer_one_second явным образом:
always @(state, timer_one_second)

Запускаем взведенный таймер, если он не был запущен (если на этот такт он был уже запущен или не взведен, то эта команда ничего не изменит):
timer_one_second_reset = 0;

По умолчанию next_state не меняется (по сути эта инструкция нужна здесь потому, что без нее компилятор без нее чувствует во всей конструкции always неопределенность и при компиляции показывает предупреждения - он хочет, чтобы все участвующие в ней переменные получали значения; на платах альтера с этой инструкцией автомат не переходит из состояния в состояние, следует разобраться):
next_state = state;

Далее конструкция case - фактически полный аналог такой же конструкции в С/С++ - внутри скобок проверяемое значение сигнала state, ниже варианты действий в зависимости от текущего значения сигнала state - возможнные значения приведены в формате 'значение:' (двоеточие) - в нашем случае для значений перечислены все константы состояний. После двоеточия и до следующего значения - блок действия.
case (state)
    state_green:
    begin
        if(timer_one_second)
        begin
            // arm timer to count one second
            // before moving to the next state
            timer_one_second_reset = 1;

            // move to the next state
            next_state = state_yellow1;
        end
    end
// ...
endcase

В блоке действия у нас опять стоит еще одна проверка значения сигнала timer_one_second - если он равен 0 (т.е. условие не выполнено), значит таймер не закончил отсчет или не запущен, ничего не делаем. Если timer_one_second равен 1 (условие выполнено), отдаем две команды:

Взводим таймер для нового отсчета секунды (сам отсчет в этот момент еще не пошел - для этого потребуется еще выполнить timer_one_second_reset = 0;)
timer_one_second_reset = 1;

Вычисляем следующее состояние, в которое должна перейти система - т.к. текущее состоянии системы в данном случае - зеленое (state_green - см значение case), следующим состоянием у нас будет желтый1 (state_yellow1 - небольшое несоответствие с картинкой - yellow1 и yellow2 в коде поменяли местами, но ничего страшного):
next_state = state_yellow1;

Остальные блоки внутри case полностью аналогичны, отличия только в значениях текущего и следующего состояний.

И финальный штрих - установить новое текущее состояние светофора (попытка будет происходить на каждый clock, те. 25 млн раз в секунду, но реально значение регистра state изменится только тогда, когда изменится значение next_state):
always @ (posedge clk)
    state <= next_state;

Точнее совсем финальный штрих - это отправить значение текущего состояния светофора наружу, но это и так понятно:
assign out_state = state;


Теперь попробуем понять, что здесь вообще происходит. Система стартует в зеленом состоянии (state и next_state по нулям = state_green = 2'b00) с запущенным таймером (внутренний счетчик обнулен, внешний reset тоже 0). Таймер отсчитывает одну секунду, сигнал timer_one_second получает значение 1 и вызывает этим срабатывание 1го блока always @(*), т.к. '*' автоматически поместила timer_one_second в его список чувствительности. Далее внутри 1го блока always 'timer_one_second_reset = 0' не приводит ни к чему, т.к. reset пока что и так 0, 'next_state = state' аналогично - оба регистра до сих пор равны 0, т.е. указывают на зеленое состояние. Внутри case отрабатывает блок для условия 'state_green:', внутри него также отрабатывает 'if(timer_one_second)' (ради него сюда и пришли) - соответственно далее выполняются две команды - взводим (но пока не запускаем) новый таймер 'timer_one_second_reset = 1' и устанавливаем новое значение желтый1 в регистр next_state 'next_state = state_yellow1'. На этом текущая итерация 1го блока always завершается - в итоге next_state получил значение state_yellow1. Почти сразу после этого момента (на очередной такт clock - примерно через одну 25тимиллионную долю секунды) в очередной раз срабатывает второй блок always @(posedge clk), но на этот раз инструкция 'state <= next_state' не отрабатывает вхолостую, а записывает в регистр state новое значение state_yellow1 (оно же отправляется на выход модуля out_state) из регистра next_state, которое не равно его предыдущему значению state_green. Т.о. регистр state в этот момент меняет значение, а это значит, что первый блок always опять начинает отрабатывать уже по новому поводу, т.к. сигнал state тоже находится в его списке чувствительности. Первая инструкция 'timer_one_second_reset = 0' на этот раз спускает взведенный в прошлый раз таймер, и он начинает отсчитывать одну секунду, вторая инструкция 'next_state = state' опять ничего не меняет, внутри case сначала отрабатывает блок 'state_yellow1:', однако внутрь 'if(timer_one_second)' он уже не попадает, т.к. в этот момент секунда еще не прошла и timer_one_second=0 - работа 1го блока always опять завершается. Далее через секунду, когда запущенный таймер отработал и установил значение сигнала timer_on_second=1 вместо нуля, опять отрабатывает 1й always - получили ситуацию, почти полностью аналогичную началу этого абзаца, только теперь текущие значения state и next_state равны state_yellow1 - далее все по аналогии и по циклу.

Замечание: последний важный нюанс, который еще не был рассмотрен - нужно обратить внимание, что в 1м блоке always @(*) для записи в регистры значений используется оператор =, а во 2м блоке always @(posedge clk) используется оператор <=. Первый оператор = называется блокируещее присвоение (blocking assignment), второй оператор <= называется неблокирующее присвоение (nonblocking assignment). Неблокирующее присвоение <= похоже на работу оператора assign вне блока always - если внутри блока always расположить подряд несколько инструкций с неблокирующим присвоением, то в нужный момент они все сработают одновременно вне зависимости от порядка расположения. Блокирующее присвоение = работает подругому - вычисление значения и присвоение для каждого следующего регистра не начнется до тех пор, пока не будет вычислено и присвоено значение для предыдущего - порядок расположения инструкций присвоения уже имеет ключевое значение, т.к. вычисляемое значение следующего регистра может зависеть от только что вычисленного значение предыдущего - получается уже некий аналог последотельного выполнения программы. Рассматриваемое упражнение не очень наглядно демонстрирует разницу между блокирующими и неблокирующими присвоениями, поэтому подробнее на них здесь останавливаться пока не буду. Пока достаточно запомнить, что при реализации конечного автомата в таком виде используется два блока always - внутри блокирующего проводятся основные вычисления для следующего состояния - можно сказать статика на текущем временном срезе автомата; а внутри неблокирующего происходит динамика - смена состояний по сигналу импульс-генератора в зависимости от вычисленных в предыдущем блоке значений. Важно, что второй блок завязан на импульс-генератор clock, а первый - нет. Кроме того, нельзя мешать блокирующие и неблокирующие присвоения внутри одного блока always.

Подключение к внешним устройствам ввода-вывода отдельных объяснений уже не требует - в данном случае для простоты и для скорости для всех трех цветов светофора были задействованы встроенные в плату Digilent Basys2 зеленые лампочки, поэтому, чтобы увидеть в них светофор, придется подключить немного воображения, хотя мигают они как нужно - при желании можно легко заменить их на внешние разноцветные светодиоды, подключенные через универсальные порты ввода-вывода PIO.

traffic_light_top.v
/**
* Top module to test traffic light.
*/

module traffic_light_top(
    input clk,
    output [0:2] ld
    );

  // enumerate state constants
   parameter state_green = 2'b00;
   parameter state_yellow1 = 2'b01;
   parameter state_red = 2'b10;
   parameter state_yellow2 = 2'b11;

    // current state value
   wire [1:0] state;

   // connect "clk" and "state" wires to traffic light logic implementation
   traffic_light lights(.clk(clk), .out_state(state));

   // display current state on output devices (lamps)
   // for state_green switch on green lamp and switch off red and yellow,
   // for state_yellow1 and state_yellow2 switch on yellow lamp and switch off green and red,
   // for state_red switch on red lamp and swithc off green and yellow.
   //
   // All actions are performed at on and the same moment - order does not make
   // any sense.

   // "green" lamp
   assign ld[0] = state == state_green ? 1 : 0;
   // "yellow" lamp
   assign ld[1] = (state == state_yellow1) | (state == state_yellow2) ? 1 : 0;
   // "red" lamp
   assign ld[2] = state == state_red ? 1 : 0;

endmodule

basys2_traffic_light.ucf
# Pin assignment for LEDs
NET "ld<2>" LOC = "p7" ;
NET "ld<1>" LOC = "m11" ;
NET "ld<0>" LOC = "m5" ;

# Pin assignment for clock
NET "clk" LOC = "b8";





Упражнение 3: самостоятельная работа - сделать робота, управляемого простым конечным автоматом

Группа разбивается на 3 команды, каждая из которых самостоятельно делает Робота Таракана, Робота Скорпиона и Робота Черепаху. Для каждого робота определяется логика его поведения и под нее рисуется новая схема конечного автомата с состояниями и переходами. Далее схема переносится в Verilog по полной аналогии со светофором, в качестве основы проекта берется код светофора. Параллельно идет распиновка сигналов модуля верхнего уровня по внешним интерфейсам (датчики/моторчики), а также сборка корпуса робота и подключение его проводами к выбранным портам ввода-вывода на плате.

Позже будут дополнительные подробности по устройству каждого из роботов отдельно, однако ничего нового в плане языковых конструкций или технологичных концептов по сравнению с сегодняшней лабой там уже не будет - только закрепление полученного опыта на практике с интересной задачей. Код Verilog роботов можно посмотреть уже сейчас - предварительный вариант Робота Скорпиона от меня, Робот Скорпион, Робот Черепаха и Робот Таракан от студентов, про запчасти для корпусов и результаты работы уже были подробности здесь. А пока на очереди процессор MIPS.

код лабы на github, подсветка синтаксиса
Tags: verilog, плис, цифровая электроника для программистов
Subscribe

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 6 comments