はじめに

なんかよくわからないけど，みんなFizzBuzzを作るのが好きらしい．
Verilogでちょっと書いてみる．

通常，ソフトウェアでFizzBuzzを書くと特に何も意識することなく，普通に剰余演算を使うことになる．HDLの場合でも除算器を構成すれば剰余を求めることは可能だ．しかし，除算器というのは，作るのがめんどくて，大変コストのかかるモジュールである．これは，除算という演算が，原理的にトライ&エラーに頼っていることに起因している．

通常のHDLモジュール設計では，なるべく除算を行わないように工夫をする．そのため，今回も，カウンタの値から剰余を求めるような計算は行わない．

仕様

外部仕様はこんな感じかな？

I/O	ポート名	概要
input	clk	クロック入力
input	srst	同期リセット(High Active)
output	valid	Highで出力が有効
output	[7:0] counter	1--255，ただし，3の倍数か5の倍数の時は0を出力
output	fizz	3で割り切れるかつ5で割り切れないときHigh,その他はLow
output	buzz	5で割り切れるかつ3で割り切れないときHigh,その他はLow
output	fizzbuzz	3で割り切れるかつ5で割り切れるときHigh,その他はLow

HDLなので，外部からクロックの供給がある．同期回路で設計する．非同期回路で設計するのはめんどい．
リセットはめんどいから同期リセット入力とした．プッシュスイッチとかでリセットするには非同期入力とするのだが，どうせ同期リセットに作り替えるんだから，別に良いだろう．
出力はvalidがHighのときの，counter，fizz，buzz，fizzbuzzの合計11ビットの状態で表現される．
counterは1から順番に数値が出力される．ただし．3で割り切れる，または，5で割り切れるときは0が出力される．
fizz，buzz，fizzbuzzはそれぞれ，3で割り切れるかつ5で割り切れないとき，5で割り切れるかつ3で割り切れないとき，3で割り切れるかつ5で割り切れるときのみHighを出力する．FizzBuzzにおいて，3で割り切れるかつ5で割り切れるときはFizzとBuzzの2個の言葉を言うのではなく，FizzBuzzという1つの言葉を言うはずだ．これを表現するには，fizz出力とbuzz出力の2本を出力するのは良くない．fizzbuzzという出力を設けるべきだ．

実装

何となく作る物のイメージができたので，実装してみる．

メインモジュール

メインモジュールでは内部状態の管理とか，出力の制御をやる．
ここで，カウンタが回る．
validとか，カウンタを回すタイミングとかは，ステートマシンで行っている．
このモジュールのポートが外部仕様と一致するようになっている．

FizzBuzzMain.v

module FizzBuzzMain (
    input wire clk,
    input wire srst,
    output wire o_valid,
    output wire [7:0] o_counter,
    output wire o_fizz,
    output wire o_buzz,
    output wire o_fizzbuzz,
);

//////////////
// localparam
//////////////
localparam signed [15:0] ONE_RE = 16384;
localparam signed [15:0] ONE_IM = 0;
localparam signed [15:0] ROOT3_RE = -8192;
localparam signed [15:0] ROOT3_IM = 14189;
localparam signed [15:0] ROOT5_RE = 5063;
localparam signed [15:0] ROOT5_IM = 15582;
localparam SHIFT = 14;

//////////////
// state
//////////////
wire cycle_fizz_valid;
wire cycle_buzz_valid; // unused
reg [1:0] state;

localparam STATE_INIT = 2'd0;
localparam STATE_VALID = 2'd1;
localparam STATE_WAIT = 2'd3;
localparam STATE_END = 2'd2;

always @(posedge clk) begin
    if(srst) begin
        state <= STATE_INIT;
    end
    else begin
        case(state)
        STATE_INIT:  state <= STATE_VALID;
        STATE_VALID: state <= STATE_WAIT;
        STATE_WAIT:  state <= (cycle_fizz_valid) ? STATE_VALID : state;
        STATE_END:   state <= state;
        default:     state <= STATE_INIT;
        endcase
    end
end

wire srst_st = (state == STATE_INIT) ? 1'b1 : srst;
wire valid = (state == STATE_VALID) ? 1'b1 : 1'b0;

//////////////
// counter
//////////////
reg [7:0] counter;

always @(posedge clk) begin
    if(srst_st) begin
        counter <= 1;
    end
    else if(cycle_fizz_valid) begin
        counter <= counter + 1;
    end
    else begin
        counter <= counter;
    end
end

//////////////
// Fizz
//////////////
wire cycle_fizz;

Cycle #(
    .ONE_RE(ONE_RE),
    .ONE_IM(ONE_IM),
    .ROOT_RE(ROOT3_RE),
    .ROOT_IM(ROOT3_IM),
    .SHIFT(SHIFT)
) CycleFizz_inst (
    .clk(clk),
    .srst(srst_st),
    .i_valid(valid),
    .o_valid(cycle_fizz_valid),
    .o_cycle(cycle_fizz)
);

//////////////
// Buzz
//////////////
wire cycle_buzz;

Cycle #(
    .ONE_RE(ONE_RE),
    .ONE_IM(ONE_IM),
    .ROOT_RE(ROOT5_RE),
    .ROOT_IM(ROOT5_IM),
    .SHIFT(SHIFT)
) CycleBuzz_inst (
    .clk(clk),
    .srst(srst_st),
    .i_valid(valid),
    .o_valid(cycle_buzz_valid),
    .o_cycle(cycle_buzz)
);

//////////////
// latch
//////////////
reg [1:0] l_valid;
reg [7:0] l_counter;
reg l_fizz;
reg l_buzz;
reg l_fizzbuzz;

always @(posedge clk) begin
    if(srst_st) begin
        l_valid <= 0;
    end
    else begin
        l_valid <= {l_valid[0], cycle_fizz_valid};
    end
end

always @(posedge clk) begin
    if(srst_st) begin
        l_counter <= 0;
        l_fizz <= 0;
        l_buzz <= 0;
        l_fizzbuzz <= 0;
    end
    else if(cycle_fizz_valid) begin
        l_counter <= (cycle_fizz | cycle_buzz) ? 0 : counter;
        l_fizz <= cycle_fizz & ~cycle_buzz;
        l_buzz <= cycle_buzz & ~cycle_fizz;
        l_fizzbuzz <= cycle_fizz & cycle_buzz;
    end
end

//////////////
// output
//////////////
assign o_valid = l_valid[1];
assign o_counter = l_counter;
assign o_fizz = l_fizz;
assign o_buzz = l_buzz;
assign o_fizzbuzz = l_cycle_buzz;

endmodule

Cycleモジュール

Cycleモジュールではパラメータで指定された波長の波を生成する．
演算モジュールの出力が1になったときのみ，o_cycleはHighを出力し，これがFizzやBuzzとなる．

Cycle.v

module Cycle #(
    parameter signed [15:0] ONE_RE = 16384,
    parameter signed [15:0] ONE_IM = 0,
    parameter signed [15:0] ROOT_RE = 16384,
    parameter signed [15:0] ROOT_IM = 0,
    parameter SHIFT = 14
) (
    input wire clk,
    input wire srst,
    input wire i_valid,
    output wire o_valid,
    output wire o_cycle
);

//////////////
// main
//////////////
wire complex_valid;
wire signed [15:0] complex_re;
wire signed [15:0] complex_im;
reg signed [15:0] my_re;
reg signed [15:0] my_im;

always @(posedge clk) begin
    if(srst) begin
        my_re <= ONE_RE;
        my_im <= ONE_IM;
    end
    else if(complex_valid) begin
        my_re <= complex_re;
        my_im <= complex_im;
    end
    else begin
        my_re <= my_re;
        my_im <= my_im;
    end
enb

ComplexMul #(
    .PARAM_RE(ROOT_RE),
    .PARAM_IM(ROOT_IM),
    .SHIFT(SHIFT)
) ComplexMul_fizz (
    .clk(clk),
    .srst(srst),
    .i_valid(i_valid),
    .i_re(my_re),
    .i_im(my_im),
    .o_valid(complex_valid),
    .o_re(complex_re),
    .o_im(complex_im)
);

//////////////
// output
//////////////
assign o_valid = complex_valid;
assign o_cycle = ((complex_re == ONE_RE) && (complex_im == ONE_IM)) ? 1'b 1 : 1'b0;

endmodule

複素数乗算モジュール

複素数乗算モジュールでは入力とパラメータ指定との値の乗算を求める．演算は固定小数点で行う．
パイプラインっぽく書いてしまったけど，パイプラインである必要は無い．

ComplexMul.v

module ComplexMul #(
    parameter signed [15:0] PARAM_RE = 16384,
    parameter signed [15:0] PARAM_IM = 0,
    parameter SHIFT = 14
) (
    input wire clk,
    input wire srst,
    input wire i_valid,
    input wire signed [15:0] i_re,
    input wire signed [15:0] i_im,
    output wire o_valid,
    output wire signed [15:0] o_re,
    output wire signed [15:0] o_im
);

//////////////
// define
//////////////
localparam DLY = 4;

//////////////
// 1st
//////////////
reg signed [15:0] l_re;
reg signed [15:0] l_im;

always @(posedge clk) begin
    if(srst) begin
        l_re <= 0;
        l_im <= 0;
    end
    else begin
        l_re <= i_re;
        l_im <= i_im;
    end
enb

//////////////
// 2nd
//////////////
reg signed [31:0] l_lre_pre;
reg signed [31:0] l_lim_pim;
reg signed [31:0] l_lre_pim;
reg signed [31:0] l_lim_pre;

always @(posedge clk) begin
    if(srst) begin
        l_lre_pre <= 0;
        l_lim_pim <= 0;
        l_lre_pim <= 0;
        l_lim_pre <= 0;
    end
    else begin
        l_lre_pre <= l_re * PARAM_RE;
        l_lim_pim <= l_im * PARAM_IM;
        l_lre_pim <= l_re * PARAM_IM;
        l_lim_pre <= l_im * PARAM_RE;
    end
enb

//////////////
// 3rd
//////////////
reg signed [32:0] l_add_re;
reg signed [32:0] l_add_im;

always @(posedge clk) begin
    if(srst) begin
        l_add_re <= 0;
        l_add_im <= 0;
    end
    else begin
        l_add_re <= l_lre_pre - l_lim_pim;
        l_add_im <= l_lre_pim + l_lim_pre;
    end
enb

//////////////
// 4th
//////////////
wire signed [SHIFT:0] round_const = $signed({2'b01, {SHIFT-1{1'b0}}});
wire signed [32:0] w_round_re = l_add_re + round_const;
wire signed [32:0] w_round_im = l_add_im + round_const;
reg signed [15:0] l_res_re;
reg signed [15:0] l_res_im;

always @(posedge clk) begin
    if(srst) begin
        l_res_re <= 0;
        l_res_im <= 0;
    end
    else begin
        l_res_re <= ROUND(w_round_re);
        l_res_im <= ROUND(w_round_im);
    end
enb

function [15:0] Round(input signed [33:0] in);
    begin
        if(in[33] & (~&in[32:15+SHIFT])) begin
            ROUND = 15'h8000;
        end
        else if(~in[33] & (|in[32:15+SHIFT])) begin
            ROUND = 15'h7FFF;
        end
        else begin
            ROUND = in[15+SHIFT:SHIFT];
        end
    end
endfunction

//////////////
// delay
//////////////
reg [DLY-1:0] l_valid;

always @(posedge clk) begin
    if(srst) begin
        l_valid <= 0;
    end
    else begin
        l_valid <= {l_valid[DLY-2:0], i_valid};
    end
enb

//////////////
// output
//////////////
assign o_valid = l_valid[DLY-1];
assign o_re = l_res_re;
assign o_im = l_res_im;

endmodule

原理

動作原理について．

Fizzとは何か？

Fizzとは何か？
3で割り切れる数というのは，3の倍数と同義だ．
Fizzは3の倍数ごとに出力されることになる．
1,2,3,...という数列において，3の倍数というのは3を始めとして，その後は+3ごとに出現する．これは数学的帰納法を使えば，容易に証明可能だ．
+3ごとにFizzは出力されることから，Fizzは波長が3の波であると言える．
波長が3の波というのは数学的にどう表現されるか？
波というのは，複素平面上の原点を中心とした回転のことだ．
つまり，円の円周を3等分して，時間1ごとに3等分した1個分だけ進ませるということだ．
このような動きをする標準的なものを我々は既に知っている．そうだ，1の3乗根を自然数乗した結果のことなのだ！
1の3乗根の自然数乗であるので，除算は不要である．
今回は何乗かして1になったときにFizzを出力するようにした．

Buzzの方も同じ手法で波長5の波を作れば良いだけだ．

固定小数演算

浮動小数点の演算というのは，HDLで実装するにはこれまたコストのかかる手法である．だけど，小数を扱いたい．
こんなときは，固定小数演算を行う．これならば，整数演算だけで済むので，とても楽だ¹．
しかし，どこに小数点があるか，ちゃんとどこかに書いておかないと忘れてあとでメンテナンスできなくなるので注意が必要だ．
今回は，16ビット符号付整数のうち，下位14ビットを小数点以下とした．なので，何カ所か出てくる16384という値は厳密に1という値を14ビット左シフトした値になっている．
波長3の方のパラメータで，ROOT3_REは-8192/16384のことであり，ROOT3_IMじゃ14189/16384のことである．これらの値はそれぞれ1の3乗根の実部と虚部に近い値になっている．初期値1として，1の3乗根の累乗を計算していることになる．

同期

しかし，ここで問題が発生する．それは位相だ．この手法では，波を作るモジュールにカウンタ値を入力しないので，カウンタと，波長3の波を作るモジュールと，波長5の波を作るモジュールが非同期で動いてもらっては困る．これを解決するために，同期リセットが必要となるのだ．

さらなる高みを目指して

これはちゃんと期待通りに動いてくれる．だけど，作るのが超絶めんどい．この回路で3の倍数と5の倍数であれば，正しく動くが²，7の倍数とか11の倍数とか他の倍数で正しく動くかは保証しない．これを防ぐためには，差分を使った方が良いかもしれないが，パラメータをたくさん設定しないといけないので大変だ．別の手法としては，1付近に戻ってきたとき，強制的に厳密に1にしてしまうというやり方がある．整数演算だけなので，何乗すればどんな値になるのか，予め厳密に分かる．浮動小数点と違って，誤差を考える必要が無いので簡単だ．

今回の設計では，CycleBuzz_instのvalid信号は参照せず，CycleFizz_instのvalid信号だけを参照している．これはCycleFizz_instと同じモジュールで，遅延が同じことが保証されているからだ．一般的には，両方のvalid信号を参照して状態遷移を行う．

ハードウェア量は減らせないだろうか？周期15の波を作ることにすれば，ComplexMulモジュールは1個で実現できるようになる³．その代わり，FizzやBuzzを出力するタイミングは演算結果が1になったときだけではないので注意が必要だ．また，先の強制的に1に戻す手法を使えば，レジスタ長を短くできる可能性もある．

ビット数は最適だろうか？今回はめんどいから16ビット符号付整数で計算しているが，計算上，符号ビットを飛ばした最上位ビットが1になることはほとんど無い．単位円なので，-1以上1以下の値しか取らないが，小数点以下14ビットだと-2以下2未満のの範囲で表現できてしまい，ほぼ1ビット分が無駄である．こういう場合は，思い切って1ビット削って，15ビット符号付整数にしてしまう手がある．この場合，最大値は厳密に1にならなくなるが，そもそもこのシステムではそこまでの厳密さを要求されてはいなので，特に問題とはならない．

固定小数は実質的に整数演算だけで実現でき，異なる計算機システムでも同じ結果が必ず得られる． ↩
正しく計算できることは，Excelを使って検証した． ↩
ローテーションシフト？そんなもん作って何が面白いと？ ↩