情報画像学実験II

実験II-1. 論理回路

回路作成例・解説

第4週目-課題1

図1 に記述例を示す。

module COUNTER5(OUT, CLK, RST);
    input CLK;
    input RST;
    
    output [2:0] OUT;
    reg [2:0] OUT;
    
    always@(posedge CLK) begin
        if(RST) begin    // リセット
            OUT <= 0;
        end else begin
            if(OUT==4) begin    // 4の次は 0
                OUT <= 0;
            end else begin    // それ以外の場合は1増加
                OUT <= OUT+1;
            end
        end
    end
endmodule
図1. 5進カウンタの Verilog 記述例

第4週目-課題2-1

回路図自体は既に示されているので、それをそのまま Verilog 記述していけばよい。図2に記述例を示す。FFT16 が本体、RADIX4 が基数4のバタフライ演算回路、COMPLEX_ADDER, COMPLEX_SUBTRACTOR がそれぞれ複素数用加算器と減算器、J_MULTIPLIER が j倍器、TWIDDLER が回転因子との乗算のための回路である。なお、課題の回路図では -1倍器を用いているが、この記述例では直後の加算器と併せ、減算器を用いて記述している。

module FFT16(
        A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15,
        Y0, Y1, Y2, Y3, Y4, Y5, Y6, Y7, Y8, Y9, Y10, Y11, Y12, Y13, Y14, Y15);
    input [31:0] A0;
    input [31:0] A1;
    input [31:0] A2;
    input [31:0] A3;
    input [31:0] A4;
    input [31:0] A5;
    input [31:0] A6;
    input [31:0] A7;
    input [31:0] A8;
    input [31:0] A9;
    input [31:0] A10;
    input [31:0] A11;
    input [31:0] A12;
    input [31:0] A13;
    input [31:0] A14;
    input [31:0] A15;
    output [31:0] Y0;
    output [31:0] Y1;
    output [31:0] Y2;
    output [31:0] Y3;
    output [31:0] Y4;
    output [31:0] Y5;
    output [31:0] Y6;
    output [31:0] Y7;
    output [31:0] Y8;
    output [31:0] Y9;
    output [31:0] Y10;
    output [31:0] Y11;
    output [31:0] Y12;
    output [31:0] Y13;
    output [31:0] Y14;
    output [31:0] Y15;
    
    wire [31:0] B0;
    wire [31:0] B1;
    wire [31:0] B2;
    wire [31:0] B3;
    wire [31:0] B4;
    wire [31:0] B5;
    wire [31:0] B6;
    wire [31:0] B7;
    wire [31:0] B8;
    wire [31:0] B9;
    wire [31:0] B10;
    wire [31:0] B11;
    wire [31:0] B12;
    wire [31:0] B13;
    wire [31:0] B14;
    wire [31:0] B15;
    
    RADIX4 U1 (.A0(A0), .A1(A4), .A2(A8), .A3(A12),
        .W1K(32'h40000000), .W2K(32'h40000000), .W3K(32'h40000000),
        .Y0(B0), .Y1(B4), .Y2(B8), .Y3(B12));
    RADIX4 U2 (.A0(A1), .A1(A5), .A2(A9), .A3(A13),
        .W1K(32'h3b21e782), .W2K(32'h2d41d2bf), .W3K(32'h187ec4df),
        .Y0(B1), .Y1(B5), .Y2(B9), .Y3(B13));
    RADIX4 U3 (.A0(A2), .A1(A6), .A2(A10), .A3(A14),
        .W1K(32'h2d41d2bf), .W2K(32'h0000c000), .W3K(32'hd2bfd2bf),
        .Y0(B2), .Y1(B6), .Y2(B10), .Y3(B14));
    RADIX4 U4 (.A0(A3), .A1(A7), .A2(A11), .A3(A15),
        .W1K(32'h187ec4df), .W2K(32'hd2bfd2bf), .W3K(32'hc4df187e),
        .Y0(B3), .Y1(B7), .Y2(B11), .Y3(B15));
    
    RADIX4 U5 (.A0(B0), .A1(B1), .A2(B2), .A3(B3),
        .W1K(32'h40000000), .W2K(32'h40000000), .W3K(32'h40000000),
        .Y0(Y0), .Y1(Y8), .Y2(Y4), .Y3(Y12));
    RADIX4 U6 (.A0(B4), .A1(B5), .A2(B6), .A3(B7),
        .W1K(32'h40000000), .W2K(32'h40000000), .W3K(32'h40000000),
        .Y0(Y2), .Y1(Y10), .Y2(Y6), .Y3(Y14));
    RADIX4 U7 (.A0(B8), .A1(B9), .A2(B10), .A3(B11),
        .W1K(32'h40000000), .W2K(32'h40000000), .W3K(32'h40000000),
        .Y0(Y1), .Y1(Y9), .Y2(Y5), .Y3(Y13));
    RADIX4 U8 (.A0(B12), .A1(B13), .A2(B14), .A3(B15),
        .W1K(32'h40000000), .W2K(32'h40000000), .W3K(32'h40000000),
        .Y0(Y3), .Y1(Y11), .Y2(Y7), .Y3(Y15));
endmodule


module RADIX4(A0, A1, A2, A3, W1K, W2K, W3K, Y0, Y1, Y2, Y3);
    input [31:0] A0;
    input [31:0] A1;
    input [31:0] A2;
    input [31:0] A3;
    input [31:0] W1K;
    input [31:0] W2K;
    input [31:0] W3K;
    output [31:0] Y0;
    output [31:0] Y1;
    output [31:0] Y2;
    output [31:0] Y3;
    
    wire [31:0] B0;
    wire [31:0] B1;
    wire [31:0] B2;
    wire [31:0] B3;
    wire [31:0] B3J;
    wire [31:0] C0;
    wire [31:0] C1;
    wire [31:0] C2;
    wire [31:0] C3;
    
    COMPLEX_ADDER U1 (.A(A0), .B(A2), .Y(B0));
    COMPLEX_ADDER U2 (.A(A1), .B(A3), .Y(B1));
    COMPLEX_SUBTRACTOR U3 (.A(A0), .B(A2), .Y(B2));
    COMPLEX_SUBTRACTOR U4 (.A(A1), .B(A3), .Y(B3));
    
    J_MULTIPLIER U5 (.A(B3), .Y(B3J));
    
    COMPLEX_ADDER U6 (.A(B0), .B(B1), .Y(C0));
    COMPLEX_SUBTRACTOR U7 (.A(B0), .B(B1), .Y(C1));
    COMPLEX_SUBTRACTOR U8 (.A(B2), .B(B3J), .Y(C2));
    COMPLEX_ADDER U9 (.A(B2), .B(B3J), .Y(C3));
    
    assign Y0 = C0;
    TWIDDLER U10(.A(C1), .W(W2K), .Y(Y1));
    TWIDDLER U11(.A(C2), .W(W1K), .Y(Y2));
    TWIDDLER U12(.A(C3), .W(W3K), .Y(Y3));
endmodule


module COMPLEX_ADDER(A, B, Y);
    input [31:0] A;
    input [31:0] B;
    output [31:0] Y;
    
    wire signed [15:0] AR, AI, BR, BI, YR, YI;
    
    assign {AR, AI} = A;
    assign {BR, BI} = B;
    
    assign YR = AR + BR;
    assign YI = AI + BI;
    
    assign Y = {YR, YI};
endmodule


module COMPLEX_SUBTRACTOR(A, B, Y);
    input [31:0] A;
    input [31:0] B;
    output [31:0] Y;
    
    wire signed [15:0] AR, AI, BR, BI, YR, YI;
    
    assign {AR, AI} = A;
    assign {BR, BI} = B;
    
    assign YR = AR - BR;
    assign YI = AI - BI;
    
    assign Y = {YR, YI};
endmodule


module J_MULTIPLIER(A, Y);
    input [31:0] A;
    output [31:0] Y;
    
    wire signed [15:0] AR;
    wire signed [15:0] AI;
    wire signed [15:0] YR;
    wire signed [15:0] YI;
    
    assign {AR, AI} = A;        // j×(AR+j×AI) = -AI+j×AR
    assign Y = {-AI, AR};
endmodule


module TWIDDLER(A, W, Y);
    input [31:0] A;
    input [31:0] W;
    output [31:0] Y;
    
    wire signed [15:0] AR;
    wire signed [15:0] AI;
    wire signed [15:0] WR;
    wire signed [15:0] WI;
    wire signed [31:0] YR;
    wire signed [31:0] YI;
    
    assign {AR, AI} = A;
    assign {WR, WI} = W;
    
    assign YR = AR * WR - AI * WI;
    assign YI = AR * WI + AI * WR;
    
    assign Y = {YR[29:14], YI[29:14]}; 
      /* 下位14ビットを切り捨て、上位2ビット(オーバフロー分)も捨てる */
endmodule
図2. 16点離散フーリエ変換演算組合せ回路の Verilog 記述

なお、シミュレーション結果と Excel での計算結果とでは若干の誤差がある。これは Excel が小数点以下までちゃんと計算している一方で、この回路では小数点以下を無視していることに起因する。小数点以下までちゃんと計算する回路を作れば、この誤差はなくなる。

バスを要素に持つ配列を用いればもう少し綺麗に記述できそうである。しかし残念ながら、Verilog ではそのような配列を記述することができない。(正確にはできるが、それは ROM や RAM をシミュレートするための記述法であり、使い方にもかなり制約がある。)

第4週目-課題2-2

図3 に解答例の回路図を示す。この例では、左右4個ずつのバタフライ演算器の間に16×32個のフリップフロップが挿入されている。信号値が入力されたとき、まずは左4個分のバタフライ演算がなされ、その結果が一旦フリップフロップに記憶される。続いて、次のクロックで残る右4個分のバタフライ演算が行われ、計算結果が出力される。左4個のバタフライ演算器は互いの出力値を用いることはない。右4個についても同様である。つまり、入力、フリップフロップ、出力間の バタフライ演算器の数は高々1個である。なお、図中においてはクロック信号線は省略している。


図3. フリップフロップを挿入した16点離散フーリエ変換演算回路

図3 の回路を Verilog 記述したものを図4に示す。ただし、バタフライ演算器 (RADIX4) およびそれを構成するモジュールについては図2と同じなので省略する。

module FFT16(
        A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15,
        Y0, Y1, Y2, Y3, Y4, Y5, Y6, Y7, Y8, Y9, Y10, Y11, Y12, Y13, Y14, Y15, CLK);
    input [31:0] A0;
    input [31:0] A1;
    input [31:0] A2;
    input [31:0] A3;
    input [31:0] A4;
    input [31:0] A5;
    input [31:0] A6;
    input [31:0] A7;
    input [31:0] A8;
    input [31:0] A9;
    input [31:0] A10;
    input [31:0] A11;
    input [31:0] A12;
    input [31:0] A13;
    input [31:0] A14;
    input [31:0] A15;
    output [31:0] Y0;
    output [31:0] Y1;
    output [31:0] Y2;
    output [31:0] Y3;
    output [31:0] Y4;
    output [31:0] Y5;
    output [31:0] Y6;
    output [31:0] Y7;
    output [31:0] Y8;
    output [31:0] Y9;
    output [31:0] Y10;
    output [31:0] Y11;
    output [31:0] Y12;
    output [31:0] Y13;
    output [31:0] Y14;
    output [31:0] Y15;
    input CLK;
    
    wire [31:0] B0;    // C0〜C15 はフリップフロップの入力
    wire [31:0] B1;
    wire [31:0] B2;
    wire [31:0] B3;
    wire [31:0] B4;
    wire [31:0] B5;
    wire [31:0] B6;
    wire [31:0] B7;
    wire [31:0] B8;
    wire [31:0] B9;
    wire [31:0] B10;
    wire [31:0] B11;
    wire [31:0] B12;
    wire [31:0] B13;
    wire [31:0] B14;
    wire [31:0] B15;
    
    wire [31:0] C0;    // C0〜C15 はフリップフロップの出力
    wire [31:0] C1;
    wire [31:0] C2;
    wire [31:0] C3;
    wire [31:0] C4;
    wire [31:0] C5;
    wire [31:0] C6;
    wire [31:0] C7;
    wire [31:0] C8;
    wire [31:0] C9;
    wire [31:0] C10;
    wire [31:0] C11;
    wire [31:0] C12;
    wire [31:0] C13;
    wire [31:0] C14;
    wire [31:0] C15;
    
    RADIX4 U1 (.A0(A0), .A1(A4), .A2(A8), .A3(A12),
        .W1K(32'h40000000), .W2K(32'h40000000), .W3K(32'h40000000),
        .Y0(B0), .Y1(B4), .Y2(B8), .Y3(B12));
    RADIX4 U2 (.A0(A1), .A1(A5), .A2(A9), .A3(A13),
        .W1K(32'h3b21e782), .W2K(32'h2d41d2bf), .W3K(32'h187ec4df),
        .Y0(B1), .Y1(B5), .Y2(B9), .Y3(B13));
    RADIX4 U3 (.A0(A2), .A1(A6), .A2(A10), .A3(A14),
        .W1K(32'h2d41d2bf), .W2K(32'h0000c000), .W3K(32'hd2bfd2bf),
        .Y0(B2), .Y1(B6), .Y2(B10), .Y3(B14));
    RADIX4 U4 (.A0(A3), .A1(A7), .A2(A11), .A3(A15),
        .W1K(32'h187ec4df), .W2K(32'hd2bfd2bf), .W3K(32'hc4df187e),
        .Y0(B3), .Y1(B7), .Y2(B11), .Y3(B15));
    
    RADIX4 U5 (.A0(C0), .A1(C1), .A2(C2), .A3(C3),
        .W1K(32'h40000000), .W2K(32'h40000000), .W3K(32'h40000000),
        .Y0(Y0), .Y1(Y8), .Y2(Y4), .Y3(Y12));
    RADIX4 U6 (.A0(C4), .A1(C5), .A2(C6), .A3(C7),
        .W1K(32'h40000000), .W2K(32'h40000000), .W3K(32'h40000000),
        .Y0(Y2), .Y1(Y10), .Y2(Y6), .Y3(Y14));
    RADIX4 U7 (.A0(C8), .A1(C9), .A2(C10), .A3(C11),
        .W1K(32'h40000000), .W2K(32'h40000000), .W3K(32'h40000000),
        .Y0(Y1), .Y1(Y9), .Y2(Y5), .Y3(Y13));
    RADIX4 U8 (.A0(C12), .A1(C13), .A2(C14), .A3(C15),
        .W1K(32'h40000000), .W2K(32'h40000000), .W3K(32'h40000000),
        .Y0(Y3), .Y1(Y11), .Y2(Y7), .Y3(Y15));
    
    FF32 U9  (.D(B0),  .Q(C0),  .CLK(CLK));
    FF32 U10 (.D(B1),  .Q(C1),  .CLK(CLK));
    FF32 U11 (.D(B2),  .Q(C2),  .CLK(CLK));
    FF32 U12 (.D(B3),  .Q(C3),  .CLK(CLK));
    FF32 U13 (.D(B4),  .Q(C4),  .CLK(CLK));
    FF32 U14 (.D(B5),  .Q(C5),  .CLK(CLK));
    FF32 U15 (.D(B6),  .Q(C6),  .CLK(CLK));
    FF32 U16 (.D(B7),  .Q(C7),  .CLK(CLK));
    FF32 U17 (.D(B8),  .Q(C8),  .CLK(CLK));
    FF32 U18 (.D(B9),  .Q(C9),  .CLK(CLK));
    FF32 U19 (.D(B10), .Q(C10), .CLK(CLK));
    FF32 U20 (.D(B11), .Q(C11), .CLK(CLK));
    FF32 U21 (.D(B12), .Q(C12), .CLK(CLK));
    FF32 U22 (.D(B13), .Q(C13), .CLK(CLK));
    FF32 U23 (.D(B14), .Q(C14), .CLK(CLK));
    FF32 U24 (.D(B15), .Q(C15), .CLK(CLK));
endmodule


module FF32(D, Q, CLK);
    input [31:0] D;
    input CLK;
    output [31:0] Q;
    reg [31:0] Q;
    
    always@(posedge CLK) begin
        Q <= D;
    end
endmodule
図4. フリップフロップを挿入した16点離散フーリエ変換演算回路の Verilog 記述

第4週目-課題2-3

シフトレジスタを用いてシリアルパラレル変換、パラレルシリアル変換を行えばよい。図5 はシフトレジスタを用いた、シリアルパラレル、パラレルシリアル変換回路の例である。


(1) シリアルパラレル変換回路


(2) パラレルシリアル変換回路
図5. シフトレジスタを用いたシリアルパラレル・パラレルシリアル変換回路

図5(1) はシリアルパラレル変換回路である。その動作を図6に示す。入力 D から逐次入力された数列 x0, x1, x2, x3 が最終的に出力 Q0〜Q3 から並列に出力されるのが分かる。


図6. シリアルパラレル変換回路の動作

図5(2) はパラレルシリアル変換回路である。各フリップフロップの入力にはセレクタが設けられており、入力 D0〜D3 と隣接するフリップフロップの出力とを選べるようになっている。この回路の動作を図7に示す。入力 D0〜D3 から並列に入力された数列 x0, x1, x2, x3 がまず各フリップフロップに記憶され、続いて出力 Q から逐次出力されている。なおセレクタは、D0〜D3の入力を並列に読み込むときは入力 D0〜D3 を、逐次出力するときには隣接するフリップフロップの出力を選択している。


図7. パラレルシリアル変換回路の動作

解答例を図8に示す。FFT16は図3に示したフーリエ変換回路である。その入出力にシフトレジスタを配置し、入力 A から逐次入力されたデータをFFT16に並列入力できるようにしている。また、FFT16から並列に出力されたデータを出力 Y より逐次出力できるようにしている。

この回路は制御回路を持つ。制御回路はパラレルシリアル変換器のセレクタを適切に制御し、DONE 信号を適切に出力する。制御回路の中身は最初からプログラムで考え、回路図では考えない。なお、シリアルパラレル変換器やフーリエ変換回路へは制御回路は何も指示せず、計算中であるないに関わらず、動作させ放しにしておく。


図8. 入出力ピン数を削減したフーリエ変換回路

図8 に基づいたフーリエ変換回路の記述例を図9 に示す。 FFT16 は図4 に示したフーリエ変換回路である。モジュール CONTROLLER は制御回路である。 

module FFT16_SEQUENTIAL(A, Y, CLK, START, DONE, RESET);
    input [31:0] A;
    output [31:0] Y;
    input CLK;
    input START;
    output DONE;
    input RESET;
    
    reg [31:0] A0;
    reg [31:0] A1;
    reg [31:0] A2;
    reg [31:0] A3;
    reg [31:0] A4;
    reg [31:0] A5;
    reg [31:0] A6;
    reg [31:0] A7;
    reg [31:0] A8;
    reg [31:0] A9;
    reg [31:0] A10;
    reg [31:0] A11;
    reg [31:0] A12;
    reg [31:0] A13;
    reg [31:0] A14;
    reg [31:0] A15;
    wire [31:0] Y0;
    wire [31:0] Y1;
    wire [31:0] Y2;
    wire [31:0] Y3;
    wire [31:0] Y4;
    wire [31:0] Y5;
    wire [31:0] Y6;
    wire [31:0] Y7;
    wire [31:0] Y8;
    wire [31:0] Y9;
    wire [31:0] Y10;
    wire [31:0] Y11;
    wire [31:0] Y12;
    wire [31:0] Y13;
    wire [31:0] Y14;
    wire [31:0] Y15;
    reg [31:0] YR0;
    reg [31:0] YR1;
    reg [31:0] YR2;
    reg [31:0] YR3;
    reg [31:0] YR4;
    reg [31:0] YR5;
    reg [31:0] YR6;
    reg [31:0] YR7;
    reg [31:0] YR8;
    reg [31:0] YR9;
    reg [31:0] YR10;
    reg [31:0] YR11;
    reg [31:0] YR12;
    reg [31:0] YR13;
    reg [31:0] YR14;
    reg [31:0] YR15;
    
    wire SEL;
    
    always@(posedge CLK) begin
        A0 <= A1;    // シリアルパラレル変換用シフトレジスタ
        A1 <= A2;
        A2 <= A3;
        A3 <= A4;
        A4 <= A5;
        A5 <= A6;
        A6 <= A7;
        A7 <= A8;
        A8 <= A9;
        A9 <= A10;
        A10 <= A11;
        A11 <= A12;
        A12 <= A13;
        A13 <= A14;
        A14 <= A15;
        A15 <= A;
        
        YR0 <= SEL ? Y0 : YR1;    // パラレルシリアル変換用シフトレジスタ
        YR1 <= SEL ? Y1 : YR2;    // SEL が 1 のとき、
        YR2 <= SEL ? Y2 : YR3;    //    FFT16の出力値がシフトレジスタにロードされる。
        YR3 <= SEL ? Y3 : YR4;
        YR4 <= SEL ? Y4 : YR5;
        YR5 <= SEL ? Y5 : YR6;
        YR6 <= SEL ? Y6 : YR7;
        YR7 <= SEL ? Y7 : YR8;
        YR8 <= SEL ? Y8 : YR9;
        YR9 <= SEL ? Y9 : YR10;
        YR10 <= SEL ? Y10 : YR11;
        YR11 <= SEL ? Y11 : YR12;
        YR12 <= SEL ? Y12 : YR13;
        YR13 <= SEL ? Y13 : YR14;
        YR14 <= SEL ? Y14 : YR15;
        YR15 <= Y15;
    end
    
    assign Y = YR0;
    
    FFT16 U1 (
        .A0(A0), .A1(A1), .A2(A2), .A3(A3),
        .A4(A4), .A5(A5), .A6(A6), .A7(A7),
        .A8(A8), .A9(A9), .A10(A10), .A11(A11),
        .A12(A12), .A13(A13), .A14(A14), .A15(A15),
        .Y0(Y0), .Y1(Y1), .Y2(Y2), .Y3(Y3),
        .Y4(Y4), .Y5(Y5), .Y6(Y6), .Y7(Y7),
        .Y8(Y8), .Y9(Y9), .Y10(Y10), .Y11(Y11),
        .Y12(Y12), .Y13(Y13), .Y14(Y14), .Y15(Y15), .CLK(CLK));
    
    CONTROLLER U2 (.START(START), .DONE(DONE), .SEL(SEL), .CLK(CLK), .RESET(RESET));
endmodule


module CONTROLLER(START, DONE, SEL, CLK, RESET);
    input START;
    output DONE;
    output SEL;
    input CLK;
    input RESET;
    
    reg [5:0] STATE;    // STATE にはコントローラの状態を記憶
                        // 全34状態を記憶するため 6ビットを用意する
    reg LAST_START;
    
    always@(posedge CLK) begin
        if(RESET) begin
            LAST_START <= 0;
        end else begin
            LAST_START <= START;
                /* 直前のクロックにおける START の値を LAST_START に記憶しておく */
        end
    end
    
    always@(posedge CLK) begin
        if(RESET) begin
            STATE <= 0;
        end else begin
            case(STATE)
                0:    STATE <= (~LAST_START & START) ? 1 : 0;
                       /* START 信号が立ち上がったとき、STATEを 1 にし、演算開始 */
                33:    STATE <= 0;    // 演算終了時には初期状態 0 に戻す
                default:
                    STATE <= STATE+1;    // 演算中は原則、STATE を1増加
            endcase
        end
    end
    
    assign SEL = (STATE == 17);
        /* 16個の入力値をすべて入力し終え、フーリエ変換の演算を終えたときに
            パラレルシリアル変換器に演算結果を並列入力させる    */
    assign DONE = (STATE == 18);
        /* 続いて、演算結果逐次出力開始と同時に DONE 信号をオンにする    */
    
endmodule
図4. フリップフロップを挿入した16点離散フーリエ変換演算回路の Verilog 記述
第3週目の回路作成例・解説に戻る
実験II-1トップページに戻る
難波担当実験・演習のページに戻る

難波 一輝 (助教・伊藤・北神・難波研究室)
工学部1号棟4階409号室、内線3255、043-290-3255、namba@ieee.org