KiKi的博客

 摘要：本文主要介绍利用FPGA的自身的特性实现随机数发生器，在Virtex-II Pro开发板上用ChipScope观察随机数序列，以及在PCIe4Base（基于Virtex-4 FPGA）上实现。

基本的原理

    随机数在计算机科学中的密码学中有着重要的用途，常常被用作密钥的来源。随机数包括伪随机数以及真随机数。伪随机数是通过一定的算法计算得出，具有类似于随机数的统计特征，这样的发生器称为伪随机数发生器。而真随机数是通过物理现象产生，例如使用电子元件的噪声、核裂变等等作为噪声源[2],这样的随机数发生器叫做物理随机数发生器，也叫做真随机数发生器（TRNG：True Random Number Generator）。

    基于FPGA的随机数发生器基本原理是利用奇数个反相器组成振荡器作为随机数发生器的噪声源，因为由于FPGA自身的特性--信号传输存在抖动，所以多个反相器组成振荡器输出也不是很稳定的时钟信号，每个振荡器输出不是相同的，这样成为了理想的噪声源，见图1。振荡器输出通过D触发器进行采样输出，采样频率是fs，然后多个采样输出结果经过异或门之后再通过一个D触发器进行采样，采样频率还是fs。这样简单的随机数发生器就完成了。

图1.随机数发生器原理图[1]

实现

    根据前面所述的原理图，进行如下设计：抽样频率是fs为50MHz，用3个反相器组成一个振荡器，共用了25个振荡器。因为整个结构很简单，这里就不多讲述，主要想说的是振荡器的描述。为了避免综合器将振荡器进行一定的优化从而背离当初的设计，所以在代码中添加了属性语句，用于保证网络不被优化掉。见28至31行，36至39行。

   1: library IEEE;

   2: use IEEE.STD_LOGIC_1164.ALL;

   3: use IEEE.STD_LOGIC_ARITH.ALL;

   4: use IEEE.STD_LOGIC_UNSIGNED.ALL;

   5:  

   6: ---- Uncomment the following library declaration if instantiating

   7: ---- any Xilinx primitives in this code.

   8: library UNISIM;

   9: use UNISIM.VComponents.all;

  10:  

  11: entity Ring_osc_3 is

  12:     port (    clk        : in     STD_LOGIC;

  13:             D_out    : out     STD_LOGIC

  14:         );

  15: end Ring_osc_3;

  16:  

  17: architecture Behavioral of Ring_osc_3 is

  18: ---------------------------------------

  19: -- Interial signal in the Ring_OSC

  20: ---------------------------------------

  21: signal delay1 : std_logic;

  22: signal delay2 : std_logic;

  23: signal delay3 : std_logic;

  24:  

  25: ---------------------------------------------------------------------

  26: --Attributes to stop delay logic from being optimised.

  27: ---------------------------------------------------------------------

  28: attribute keep : string;

  29: attribute keep  of delay1 :signal is "true";

  30: attribute keep  of delay2 :signal is "true";

  31: attribute keep  of delay3 :signal is "true";

  32:  

  33: ---------------------------------------------------------------------

  34: --Attributes to stop trim logic from being optimised

  35: ---------------------------------------------------------------------

  36: attribute s     : string;

  37: attribute s     of delay1 : signal is "true";

  38: attribute s     of delay2 : signal is "true";

  39: attribute s     of delay3 : signal is "true";

  40:  

  41: ---------------------------------------

  42: --Code start

  43: ---------------------------------------

  44:  

  45: begin

  46:     --osc_out is the last invertor output, 

  47:     --and also the output feeds back to the first invertor

  48:     --invertor 1

  49:     inv_lut1: LUT1

  50:     generic map (init => X"1")

  51:     port map (

  52:             I0 => delay1,

  53:             O     =>    delay2);

  54:     

  55:     --invertor 2

  56:     inv_lut2: LUT1

  57:     generic map (init => X"1")

  58:     port map (

  59:             I0    => delay2,

  60:             O     =>    delay3);

  61:     

  62:     --invertor 3

  63:     inv_lut3: LUT1

  64:     generic map (init => X"1")

  65:     port map (

  66:             I0 => delay3,

  67:             O     =>    delay1);

  68:  

  69:     --D Flip-flop

  70:     D_ff : FD

  71:     port map (

  72:         D => delay3,

  73:         Q => D_out,

  74:         C => clk);

  75:         

  76: end Behavioral;

振荡器最后综合出来的结果是（图2）：

图2. 3个反相器组成的振荡器外加一个D触发器

ChipScope的观察

    首先对管脚以及时钟进行约束，为了通过ChipScope观察随机数的输出序列，还需要添加ICON以及ILA IP core。操作如下，在ISE窗口左侧的source栏中右键选择new source，然后见到New Source Wizard窗口。输入一个名字，然后点击OK。然后在Source窗口中看到生成的cdc source file。接下来就是配置触发信号、观察信号、时钟信号等属性。

图3.  New Source Wizard

    这里不细说如何配置，具体见参考文献3。

    在这里，观察的RNG输出信号同时作为触发信号来配置。配置完后编译实现。然后再Process栏中选择Analyze Design Using ChipScope 同时连接Virtex-II Pro板子并且上电。进入ChipScope　Pro Analyzer界面后点击工具栏中的OPEN Cable/Search JTAG Chain，然后看到JTAG Chain上的三个设备。右键选中FPGA芯片（XC2VP30），选择配置，选中刚才生成的bit文件。配置完成后会出现图5的信号列表。

   图5中Trigger Setup是触发配置，Waveform 是波形列表。

图4. JTAG Chain                                                   图5. 信号观察列表

    双击 Waveform打开波形观察窗口，因为触发信号就是需要观察的信号，所以这里不用设置触发。在工具栏中点击 ，你就可以观察到随机数的输出波形了，图6。肉眼观察信号比较随机，但是没有定性的测试。

图6. 随机数输出波形

 随机数的测试

    常用的测试随机数的工具有ENT[4]，DIEHARD[5]等。而这些工具需要大量的随机数（最好是10M以上的数据）才可以测试，而用ChipScope最多一次只能才是65536bit的数据，这样的测试肯定是不行的。所以将同样的设计放到了PCIeV4base，这个板子具有PCIe插槽，用的是Virtex-4的FPGA芯片。PC机通过PCIe桥接芯片读取数据，这样很方便得到大量的随机数数据。

   具体的原理图，图7。看起来有些麻烦，涉及到了FIFO，Wishbone上添加从设备，以及Linux下PCIe的编程，幸好相关的东西已经有实例和SDK提供，只要做一些修改就可以了。

图7.  随机数发生器作为WISHBONE BUS的从设备的原理图

    最后通过软件得到15MB的数据。然后通过ENT工具进行测试，测试的结果如下：

D:\Document\RNG\ent>ent out
Entropy = 7.999890 bits per byte.     

Optimum compression would reduce the size
of this 16777212 byte file by 0 percent.

Chi square distribution for 16777212 samples is 2563.57, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 127.5056 (127.5 = random).
Monte Carlo value for Pi is 3.141033445 (error 0.02 percent).
Serial correlation coefficient is -0.000568 (totally uncorrelated = 0.0). 

    测试的结果分析:
        熵值实际值为7.9989bits/byte, 而理想值为8.0bits/byte，实际值很接近于理想值；
        最佳压缩比实际值为：0%，理想值为0%；
        卡方分布比实际值为：0.0153%，理想值为<0.01%；
        算术平均值实际值为：127.5056，而理想值为127.5；
        蒙特卡洛价值实际值为：3.141033445，而理想值为Pi；
       序列相关系数实际值为：-0.000568，理想值为0.0。

    所以综合各个参数与理想值的比较得出，所生成的随机数序列比较理想。
  

 后续的工作

    以后的工作是想着利用Virtex-II Pro开发板得到大量的随机数，现在的主要的问题是如何将大量的数据存储起来呢。其中一个办法是利用处理器，然后通过编程采集数据，存到CF卡中，或者通过串口直接传输到计算机中，都是可以去尝试的。

   读者如果有什么更好的建议或者意见，或者发现什么错误，请联系本人。
    yq000cn@gmail.com.

参考文献

1. Knut Wold and Chik How Tan, Analysis and Enhancement of Random Number Generator in FPGA Based on Oscillator Rings
2. 随机数----wikipedia
3. ChipScope Core Generator 使用说明
4. A Pseudorandom Number Sequence Test Program
5. DIEHARD