拡張有限状態マシン

可変長符号デコーダでは、状態遷移と状態に対応する出力信号をもとに回路を設計しました。 Verilog HDL では、出力信号だけでなく、データの転送や演算などの処理を行うこともできます。 これらの処理をレジスタ・トランスファ・オペレーション (Register Transfer Operation) と呼びます。

レジスタ・トランスファ・オペレーションとは、レジスタ・トランスファ¹を行う処理のことです。本講義では、ノンブロッキング代入（<=）や四則演算（+, -, *, /）をイメージしてください。これを利用して、「ある処理を行い、さらに次の状態へ遷移する」ということを Verilog HDL で記述できます。

このように、各状態に応じてある処理と状態遷移とを一緒に記述していくスタイルを「拡張有限状態マシン」記述あるいは、拡張シーケンサ記述と呼ばれています。拡張シーケンサ記述のイメージと記述例を図 4.11 に示します。ここからは乗算回路を例にして、拡張シーケンサ記述の方法を解説します。

加算で乗算するアルゴリズム

ここでは、部分積を求めてそれを累算していくことで積を求めるアルゴリズムについて概説します。

簡単化のために、乗数、被乗数ともに 4 ビットの正数を扱います。 乗数をLreg、被乗数をMreg、乗算結果をHregとLregに格納するものとします。 なお、Mregは 5 ビットです。

つまり、以下のような計算になります。

{Hreg, Lreg} <= Lreg * Mreg

以下に示す乗算アルゴリズムをもとに、乗算器を設計・記述します。

これをハードウェアで実現すると、以下のようになると良さそうです。

アルゴリズムの基本部分の設計

次の段階として、乗算アルゴリズムの基本部分をモックアップ（模型の作成）してみます。 今回は、アルゴリズムが簡単ですので、モックアップに Verilog HDL を利用し、本番実装に近い形のものを作成しています。 大規模はアルゴリズムになればなるほど、モックアップの作成は重要になります。 どの部分にどれくらい工数がかかるのか？やどの部分を誰に分担させるのか？などの決定にも利用されます。

まず、上に示した 2 つの動作を、以下の 2 つの状態で実行することにします。

1. 加算ステート（A ステート）：STEP1 のLregの LSB によって加算する状態
2. シフトステート（S ステート）：STEP2 の右シフトを行う状態

状態遷移は、クロックごとに加算ステートとシフトステートをループすることになります。 また、それぞれの状態において状態遷移と処理（演算）を行います。

この乗算処理（ストップなし）を Verilog HDL で記述したものを以下に示します。 モックアップですので、これだけでは動きません。

このコードでは、13 行目や 17 行目のブロックで以下の処理を行っています。

1. レジスタ・トランスファ・オペレーション（13 行目、17 行目）
2. 状態遷移（14,15 行目、18,19 行目）

可変長符号デコーダでは、信号を出力していましたが、これが処理に代わっただけと言えます。

部分積加算型乗算処理（ストップなし）の Verilog HDL による記述例 (multi4basic.vvv)

/* -----
 * multiplier basic part
 * multi4basec.vvv    designed by Shinya KIMURA
 * ----- */

module multi( ... );
    reg [4:0] Hreg;
    reg [3:0] Lreg, Mreg;
    reg Istate, Astate, Sstate;

    always @(posedge clock) begin
        if(Astate) begin // Aステートでの処理
            Hreg <= Hreg + (Lreg[0] ? Mreg : 4'b0000); // 部分積加算
            Astate <= 1'b0; // Sステートへの遷移
            Sstate <= 1'b1;
        end else if(state) begin // Sステートでの処理
            {Hreg, Lreg} <= {1'b0, Hreg, Lreg[3:1]}; // ビットのシフト
            Sstate <= 1'b0; // Aステートへの遷移 
            Astate <= 1'b1;
        end
    end
endmodule

ここまで、乗算器（ストップなし）の基本部分の設計が完了しました。

外部インタフェース

実際に乗算をさせるためには、演算データをレジスタに設定する機能が必要です。 図 4.13 を見ながら、どのタイミングどのようにデータを設定するかを考えてみます。

まず、データの設定は乗算処理を行っている状態とは別に、アイドル状態（I ステート）を用意して行うことにします。 初期値の設定は、LregとMregの両方に対して行う必要があります。
信号線を減らすために、設定するデータは共通の信号sw_data[3:0]とし、レジスタの選択信号としてMLsel信号（"1"でMreg、"0"でLregを指定）、レジスタへの書き込み信号wrstb_N（アクティブロー）を用意することになります。
なお、Hregの初期化（"0"設定）は、リセット信号reset_Nまたは I ステートでstart_N（アクティブロー）がアクティブになった時点の両方で行うこととします。また、出力信号は、乗算結果が入るHregとLregとします。

また、アイドル状態とスタート信号を考慮した状態遷移図を以下に示します。 ここで、レジスタへのデータ設定は I ステートでのみ行えることとし、A ステートや S ステートでは、書き込み信号wrstb_N信号を無視することにします。

乗算回路（ストップなし）の Verilog HDL による記述例（multi4nc.v）

/* -----
 * multiplier (non stop control version)
 * (multi4nc.v)   designed by Shinya KIMURA 
 * ----- */

`define ON 1
`define OFF 0

module multiplier (clock, reset_N, wrstb_N, MLsel, sw_data, start_N, Hreg, Lreg);

// {Hreg, Lreg} <= Lreg * Mreg

    input clock, reset_N, wrstb_N, MLsel, start_N;
    input [3:0] sw_data;
    output [4:0] Hreg;
    output [3:0] Lreg;

    reg[4:0] Hreg;
    reg[3:0] Lreg, Mreg;
    reg Istate, Astate, Sstate;

    always @(posedge clock or negedge reset_N) begin
        if(!reset_N) begin                               //reset
            Hreg <= 0;
            Lreg <= 0;
            Mreg <= 0;
            Istate <= `ON;
            Astate <= `OFF;
            Sstate <= `OFF;
        end else if(Istate) begin
            if(!wrstb_N) begin
                case(MLsel)                          //initial data setting
                    0: Lreg <= sw_data;
                    1: Mreg <= sw_data;
                endcase
            end else if(!start_N) begin
                Istate <= `OFF;
                Astate <= `ON;
            end else begin
                /* no change*/
            end
        end else if(Astate) begin                        // add state
            Hreg <= Hreg + (Lreg[0] ? Mreg : 4'b0000);
            Astate <= `OFF;
            Sstate <= `ON;
        end else if(Sstate) begin                        //shitf state
            {Hreg, Lreg} <= {1'b0, Hreg, Lreg[3:1]};
            Sstate <= `OFF;
            Astate <= `ON;
        end else begin                                  //illegal state
            Istate <= `OFF; 
            Astate <= `OFF;
            Sstate <= `OFF;
        end
    end
endmodule

シミュレーション

これまでと同様に、以下のコマンドで、ビルド、シミュレーション、波形の確認をしてみます。 テストベンチは、P.174 リスト 6.23 を流用してください。 そのままでは動きませんので、ready_N信号を削除するなどして改修してください。

波形ファイルの生成部分

$dumpfile("multi4nc_test.vcd"); // 波形の出力
$dumpvars(0, multi); // 対象モジュール

P.174 リスト 6.23のテストベンチ multi4scsim.v

/* -----
 * mutiplier (stop control version)
 * (muiti4scsim.v)   designed by Shinya KIMURA
 * ----- */

`define PIRIOD 100

module multi_test;
    reg clock, reset_N, wrstb_N, MLsel, start_N;
    reg [3:0] sw_data;
    wire ready_N;
    wire [4:0] Hreg;
    wire [3:0] Lreg;

    // 設計対象のインスタンス化
    multiplier multi(clock, reset_N, wrstb_N, MLsel, sw_data,
                    start_N, ready_N, Hreg, Lreg);

    // 観測信号の指定
    initial begin
        $display("\t\t         r s        w   r                          ");
        $display("\t\t       c e t        r   e           M    H     L    ");
        $display("\t\t       l s a        s   a           r    r     r    ");
        $display("\t\t       o e r   s    t   d   I A S   e    e     e    ");
        $display("\t\t       c t t   w    b   y   s s s   g    g     g    ");
        $display("\t\ttime | k - -   3210 -   -   t t t   3210 43210 3210 ");
        $display("---------------------+---------+------+---+-------+-----------------");
        $monitor("%t : %b %b %b : %b %b : %b : %b %b %b : %b %b %b",
                $time, clock, reset_N, start_N, sw_data, wrstb_N,
                ready_N, multi.Istate, multi.Astate, multi.Sstate,
                multi.Mreg, Hreg, Lreg);
    end

    // テスト信号の発生
    initial begin
        $dumpfile("multi4sc_test.vcd"); // 波形の出力
        $dumpvars(0, multi); // 対象モジュール
        clock <= 1'b0;
        reset_N <= 1'b1;
        wrstb_N <= 1'b1;
        MLsel <= 1'b0;
        sw_data <= 4'b0000;
        start_N <= 1'b1;

        #`PIRIOD
            reset_N <= 1'b0;
        #(`PIRIOD*2)
            reset_N <= 1'b1; // reset off
        #(`PIRIOD/2)
            sw_data <= 4'b0101; // setting data to Mreg
            MLsel <= 1'b1;
        #(`PIRIOD/2)
            wrstb_N <= 1'b0; // write strobe on
        #`PIRIOD
        #`PIRIOD
            wrstb_N <= 1'b1;
        #(`PIRIOD/2)
            sw_data <= 4'b0111; // setting data to Lreg
            MLsel <= 1'b0;
        #(`PIRIOD/2)
            wrstb_N <= 1'b0;
        #`PIRIOD
            wrstb_N <= 1'b1;
        #`PIRIOD
            start_N <= 1'b0; // start on
        #`PIRIOD
            start_N <= 1'b1;
        #(`PIRIOD*15)
        $finish;
    end

    // クロック発生
    always #(`PIRIOD/2) begin
        clock <= ~clock;
    end

endmodule

ビルドとシミュレーション、波形の確認のコマンドは以下のとおりです。

iverilog -o ./multi4nc.o ./multi4nc.v ./multi4ncsim.v
vvp ./multi4nc.o
gtkwave multitest.vcd

multi4nc.v（ストップなし乗算回路）のシミュレーション結果の波形。 シミュレーション結果は、$5 \times 7 = 35$を計算したものです。 sw_data[3:0]に 5 と 7 が順に入力され、Hreg[4:0]とLreg[3:0]が全体として00010 | 0011を示し、35 となっていることがわかります。（横長なので拡大して見てね。）

演習：上記の$5 \times 7 = 35$のシミュレーションを実際にやってみましょう。

ステートと処理のタイミング

ここでは、ステートと処理のタイミングを詳しくみていきます。Verilog HDL ではステートごとに動作を記述しますが、ステートの開始と同時に所要の処理が行われているわけではありません。処理は実際にはステートの最後の時点で行われています。そのため、実際に計算結果が得られるのは次のクロックになります。always @()文で設定された信号から、assign文などによる組み合わせ回路を経由して信号を生成する場合には、特に注意が必要です。どのタイミングで信号が変化するかを正確に把握しておく必要があります。

波形を見ながら理解してみましょう。

乗算回路の A ステートから S ステートへの遷移は、ソースコード中ではalways @(posedge clock..)の内部に記述されています。そのため、ステートの遷移はクロック信号の立ち上がりに同期しています。そのほか、レジスタの値もクロックの立ち上がりに同期しています。しかし、実際にHregなどに値が書き込まれるのは、その次のクロックになっています。

演習

1. 0,5,7以外の自分の好きな4bitの数字を2つ選び、シミュレーションをしてください
2. シミュレーション結果の波形のスクリーンショットを撮ります
3. スクショに、入力する 2 つの値と乗算結果を、それぞれ図の上で示してください。丸を付けてください
4. クラス Web で波形画像を提出してください

---

ここまで、乗算回路の設計とシミュレーションでの動作確認が完了しました。 講義では実際には行いませんが、この後には実機（FPGA）での動作検証を行います。

この回路には、以下に示すような、実機での動作検証で問題になると予想される点があります。 これらを改良した実装が P.172 に紹介されています。

• 高い周期のクロック信号を加えると演算結果が壊れてしまう可能性がある。外部に信号が伝わる前に、シフトで結果を上書きしてしまうかもしれない
• いつ乗算処理が終了したかが外部インタフェースだけでは分かりにくいこと

回路の改良

ストップなしの乗算回路では前述のような問題がありますので、これを改良していきましょう。

加算の回数は入力する数字のビット数と同じですので、その回数だけ加算とシフトが終わったら、計算が終わったことを通知するようにしてみます。また、これをストップ制御付き乗算回路と呼ぶことにします。 具体的な処理としては、以下のような形にします。

1. シフトが終わったらcounterをインクリメント
2. カウンタが 4（counter == 3）になったら、ready_N信号を出力する
3. 2.と同時に、I ステートに遷移する

上記の方式を Verilog HDL で記述したものが以下になります。 ready_Nやcounterが追加され、それらが S ステートで処理されています。

ストップ制御付き乗算回路（multi4sc.v）

/* -----
 * multiplier (stop control version)
 * (muiti4sc.v)   designed by Shinya KIMURA 
 * ----- */

`define ON 1
`define OFF 0

module multiplier(clock, reset_N, wrstb_N, MLsel, sw_data,
                start_N, ready_N, Hreg, Lreg);

    // {Hreg, Lreg} <= Lreg * Mreg

    input        clock, reset_N, wrstb_N, MLsel, start_N;
    input  [3:0] sw_data;
    output       ready_N;
    output [4:0] Hreg;
    output [3:0] Lreg;

    reg    [4:0] Hreg;
    reg    [3:0] Lreg, Mreg;
    reg          Istate, Astate, Sstate;
    reg          ready_N;
    reg    [1:0] counter; // loop counter

    always @(posedge clock or negedge reset_N) begin
        if(!reset_N) begin // rest
            Hreg <= 0;
            Lreg <= 0;
            Mreg <= 0;
            ready_N <= 0;  // status = ready
            counter <= 0;
            Istate <= `ON;
            Astate <= `OFF;
            Sstate <= `OFF;
        end else if (Istate) begin
            if(!wrstb_N) begin
                case(MLsel) // initial data setting
                    0: Lreg <= sw_data;
                    1: Mreg <= sw_data;
                endcase
            end else if(!start_N) begin
                ready_N <= 1;
                Hreg <= 0;
                Istate <= `OFF;
                Astate <= `ON;
            end else begin
                /* no change */
            end
        end else if(Astate) begin // add state
            Hreg <= Hreg + (Lreg[0] ? Mreg : 4'b0000);
            Astate <= `OFF;
            Sstate <= `ON;
        end else if(Sstate) begin                       //shitf state
            {Hreg, Lreg} <= {1'b0, Hreg, Lreg[3:1]};
            Sstate <= `OFF;
            counter <= counter + 1;
            if(counter == 3) begin // operation end
                ready_N <= 0; // stats = ready
                Istate <= `ON;
            end else begin // operation continue
                Astate <= `ON;
            end
        end else begin                                  //illegal state
            Istate <= `OFF;
            Astate <= `OFF;
            Sstate <= `OFF;
        end
    end
endmodule

シミュレーション

これまでと同様に、以下のコマンドで、ビルド、シミュレーション、波形の確認をしてみます。 テストベンチは、P.174 リスト 6.23 がそのまま利用できます。 実行コマンドは以下のとおりです。

iverilog -o ./multi4sc.o ./multi4sc.v ./multi4scsim.v
vvp ./multi4sc.o
gtkwave multitest.vcd

multi4sc.v（ストップあり乗算回路） のシミュレーション結果の波形は以下のとおりです。 今回は、新しく追加されたready_N信号が ON から OFF になった際に、計算が完了したことがわかります。（横長なので拡大して見てね。）

演習

1. ストップあり乗算回路を改良し、32bit の 2 つの値を乗算できるようにしてください
2. 上記の回路の検証として、任意の 32bit の 2 つの値の乗算を 2 回行うようなテストベンチを作成してください
3. 上記の検証の波形を出力し、結果があっていることを示してください
4. クラス Web で波形画像を提出してください。その際、入力する 2 つの値と乗算結果を、それぞれ図の上で示してください。丸を付けてください

模範解答（4bit ですのが）は以下のとおりです。値の表示フォーマットは以下の形にするとわかりやすいです。表示フォーマットは、 $$Signals$$ サブウィンドウの信号を右クリックすると選択できます。

• 入力する 2 つの値の："Binary"
• 乗算結果の表示フォーマット："Decimal"

---

1. レジスタに対する信号値の設定を意味するもので、レジスタからレジスタへの演算を含む、データ転送を指します。 ↩