FC2カウンター FPGAの部屋 擬似乱数、M系列を使う1
FC2ブログ

FPGAやCPLDの話題やFPGA用のツールの話題などです。 マニアックです。 日記も書きます。

FPGAの部屋

FPGAの部屋の有用と思われるコンテンツのまとめサイトを作りました。Xilinx ISEの初心者の方には、FPGAリテラシーおよびチュートリアルのページをお勧めいたします。

擬似乱数、M系列を使う1

今度、作製するAXI4マスタIP用に擬似乱数としてM系列を使おうと思う。M系列は今から約30年前に大学の符号理論で習った。その時に教えて頂いた先生はもうすでに亡くなられた。今回は亡くなられた先生を偲びながら、M系列の性質について勉強しながら、Verilogファイルを作成して、シミュレーションで、その性質を検証してみようと思う。(元々、これについては、Veritakの作者の菅原様から教えて頂いた)

ウィキペディアのM系列の項目によると、”M系列(-けいれつ、m-sequence;maximal length sequence)とは、ガロア体における線形漸化式が生成する数列(sequence)のうち最長の周期(maximal length)を持つもの。”とある。M系列の生成多項式のページによると、”n ビットのシフトレジスタと フィードバックで生成される周期が 2^n - 1 の符号列”ということだ。 2^n - 1毎に自己相関のピークが来て、それ以外の自己相関値は低い。つまり乱数に近いという事になる。

擬似乱数としては、線形帰還シフトレジスタのフィボナッチ LFSRで生成する方式が有力らしい。
M系列の生成多項式のページにも書いてあるが、更にたくさんの例が、線型M系列符号発生器の結線表のページに書かれている。その内の mms8.txt を参考にした。mms8.txt の値の内の”8E, 95”を実装する。実装の仕方は、95を例にとると、95の2進表示は、"1001 0101"なので、bit7, bit4, bit2, bit0 のXORを取って、LSBにシフトする。

さて、この8ビットM系列の例を下に示す。なお、書き方は、Veritakの作者の菅原様から教えて頂いたVerilogコードを参考にさせて頂いた。下に、m_seq_test.v を示す。mseqf8_0 は 8EのM系列、mseqf8_1 は 95 のM系列だ。

// M sequence test(m_seq_test.v)

`default_nettype none

module m_seq_test(
    input    wire         clk,
    input    wire        reset,
    output    reg [7:0]    mseq8
);
    
    function [7:0] mseqf8_0 (input [7:0] din);
        reg xor_result;
        begin
            xor_result = din[7] ^ din[3] ^ din[2] ^ din[1];
            mseqf8_0 = {din[6:0], xor_result};
        end
    endfunction
    
    function [7:0] mseqf8_1 (input [7:0] din);
        reg xor_result;
        begin
            xor_result = din[7] ^ din[4] ^ din[2] ^ din[0];
            mseqf8_1 = {din[6:0], xor_result};
        end
    endfunction
    
    always @(posedge clk) begin
        if (reset) 
            mseq8 <= 8'd1;
        else
            mseq8 <= mseqf8_0(mseq8);
    end
    
endmodule

`default_nettype wire


”mseq8 <= 8'd1;”を初期値として代入しているが、ここが0だとずーと0になってしまう。初期値は0以外の数を代入する。

m_seq_test.v をテストするm_seq_test_tb.v を下に示す。今回は、リセットが解除された後から、mseq8の値をクロックが立ち上がるごとにmseq8.txtに書き込む。これで、mseq8.txtを見ればビットパターンがわかるわけだ。
なお、これらのVerilog 記述は、ファイル入出力システムタスクのページファイル入出力タスクのページを参考にさせて頂いた。

`default_nettype none

`timescale 1ns / 1ps

module m_seq_test_tb;

    // Inputs
    reg clk = 1'b0;
    reg reset;
    wire [7:0] mseq8;

    // Instantiate the Unit Under Test (UUT)
    m_seq_test uut (
        .clk(clk), 
        .reset(reset), 
        .mseq8(mseq8)
    );

    parameter        CLK_PERIOD = 10;
    parameter real    CLK_DUTY_CYCLE = 0.5;
    parameter        CLK_OFFSET = 0;
    parameter        START_STATE    = 1'b0;
    
    initial begin
        #CLK_OFFSET;
        forever begin
            clk = START_STATE;
            #(CLK_PERIOD-(CLK_PERIOD*CLK_DUTY_CYCLE)) clk = ~START_STATE;
            #(CLK_PERIOD*CLK_DUTY_CYCLE);
        end
    end

    // リセットが解除された後から、mseq8の値をクロックが立ち上がるごとにmseq8.txtに書き込む
    integer F_HANDLE;
    initial F_HANDLE = $fopen("mseq8.txt");

    always @(posedge clk) begin
        if (~reset) begin
            $fdisplay(F_HANDLE, "%b", mseq8);
            $fflush(F_HANDLE);
        end
    end

    initial begin
        // Initialize Inputs
        reset = 1'b1;

        // Wait 100 ns for global reset to finish
        #100;
        
        // Add stimulus here
        reset = 1'b0;
        
        #9900;
        $fclose(F_HANDLE);
        $finish;
    end
      
endmodule

`default_nettype wire


これでISimでシミュレーションを行った。
M_seq_1_120327.png

mseq8.txt をmseq8_0.txtとリネームしたファイルの一部を下に示す。

00000001
00000010
00000101
00001011
00010110
00101100
01011000
10110001
01100011
11000111


上のデータは1番目から10番目だが、256番目から265番目まで、511番目から520番目も同じデータだった。

次に、mseqf8_1ファンクションの1番目から10番目、256番目から265番目、511番目から520番目のデータを下に示す。

00000001
00000011
00000111
00001110
00011101
00111011
01110110
11101100
11011000
10110000


次回は、実際に使用するM系列を決定する。
  1. 2012年03月27日 22:15 |
  2. IP
  3. | トラックバック:0
  4. | コメント:2

コメント

こんにちは、細かいことなんですが、n^2-1でなく2^n-1ですね。
  1. 2012/04/04(水) 00:17:52 |
  2. URL |
  3. Sim #mQop/nM.
  4. [ 編集 ]

Simさん、ありがとうございました。修正しました。また、なにかミスってたら、ご指摘ください。
  1. 2012/04/04(水) 03:36:16 |
  2. URL |
  3. marsee #f1oWVgn2
  4. [ 編集 ]

コメントの投稿


管理者にだけ表示を許可する

トラックバック URL
https://marsee101.blog.fc2.com/tb.php/2095-4a3ae460
この記事にトラックバックする(FC2ブログユーザー)