計算Fibonacci數(shù)列的自控網(wǎng)系統(tǒng)模型仿真分析

自控網(wǎng)系統(tǒng)（cyber net system）又稱自修正系統(tǒng)（self-modifying system），簡稱自控系統(tǒng)。它是Petri網(wǎng)中的一類，與P/T系統(tǒng)區(qū)別僅僅在于有向弧的權(quán)受庫所控制，它的關(guān)聯(lián)矩陣含變量元素，而P/T系統(tǒng)的關(guān)聯(lián)矩陣是常量，因此，P/T系統(tǒng)是線性的，而自控系統(tǒng)是非線性的，P/T系統(tǒng)只是自控網(wǎng)系統(tǒng)的一種特殊情況。雖然自控系統(tǒng)在上世紀(jì)70年代初就已被提出，但由于自控系統(tǒng)的非線性關(guān)系，無法直接套用其它網(wǎng)系統(tǒng)的分析技術(shù)，對自控系統(tǒng)的研究成果并不多。而正由于自控系統(tǒng)的非線性關(guān)系，它有更強(qiáng)的描述能力和更復(fù)雜的性質(zhì)。因此，對自控系統(tǒng)的研究具有重要意義。北京大學(xué)袁崇義教授對自控系統(tǒng)進(jìn)行了深入的研究，提出了自控系統(tǒng)的S-不變量和T-不變量的定義及其計算。本文采用EDA工具，用在系統(tǒng)可編程邏輯器件來實(shí)現(xiàn)自控系統(tǒng)，并通過仿真對自控系統(tǒng)進(jìn)行分析。其目的是擴(kuò)大自控系統(tǒng)的應(yīng)用范圍，激起人們對自控系統(tǒng)研究的興趣。

1．自控系統(tǒng)簡介

定義1 ?=（S，T；F，W，M0）為自控系統(tǒng)的條件是：

（1） （S，T；F）為有向網(wǎng)，稱為?的基網(wǎng)。

（2） W：S?T?T?S→{0，1，2，…}?S，且W（x，y）≠0當(dāng)且僅當(dāng)W（x，y）?F，稱為?的權(quán)函數(shù)。

（3） M0：S→{0，1，2，…}為?的標(biāo)識。

自控系統(tǒng)與P/T系統(tǒng)區(qū)別在于權(quán)函數(shù)W的值域中增加了S。定義中假定了每個S_元的容量是無限的，但在硬件實(shí)現(xiàn)時，由于存儲器的位數(shù)有限，S_元的容量都是有限的，但這不影響對問題的研究。

定義2

（1） 映射M：S→{0，1，2，…}稱為?的標(biāo)識。

（2） 標(biāo)識M下的權(quán)函數(shù)WM定義為：?（x，y）?S?T?T?S，

（3） 變遷t?T在標(biāo)識M有發(fā)生權(quán)（即M［t》）的條件是：?s?S：M（s）≥WM（s，t）且有s??t使WM（s，t）》0，即t至少有一個非0的輸入權(quán)。

（4） 若M［t》，則t可以發(fā)生，后繼標(biāo)識M’由下式給出：

M’=M（s）+WM（t，s）-WM（s，t）后繼關(guān)系記做M［t》M’。

定義2給出了自控系統(tǒng)的變遷規(guī)則。顯然，變遷發(fā)生方式對最終標(biāo)識的影響很大。P/T系統(tǒng)中“并發(fā)能到達(dá)的標(biāo)識，順序也能到達(dá)”，而這在自控系統(tǒng)中不成立。自控系統(tǒng)的動態(tài)演變是以T上的多重集的并發(fā)一步一步演變。

文給出了Fibonacci數(shù)列的增廣Petri網(wǎng)模型，用了19個庫所，18個變遷和大量的抑制弧。圖1是計算Fibonacci數(shù)列的自控網(wǎng)系統(tǒng)［2］，十分簡潔，充分反映了自控網(wǎng)系統(tǒng)的建模能力。圖1中，s5、s6中的托肯數(shù)M（s5）、M（s6）代表Fibonacci數(shù)列中數(shù)的位置，相應(yīng)的Fibonacci數(shù)由s3、s4中的托肯數(shù)表示。圖示情況下可以看出，數(shù)列的第1個數(shù)的值為0，第2個數(shù)的值為1。s2和s4確保t1和t2順序發(fā)生。

圖1 自控網(wǎng)系統(tǒng)

由圖可知，變遷t2有發(fā)生權(quán)，t2發(fā)生后，t1有發(fā)生權(quán)。設(shè)t2、t1發(fā)生后的標(biāo)識分別為M1和M2，根據(jù)自控系統(tǒng)的變遷規(guī)則計算如下：

式中運(yùn)算符號 為替換加，即將向量中的變量先進(jìn)行替換后再相加。

2．自控網(wǎng)系統(tǒng)的仿真分析與硬件實(shí)現(xiàn)

在系統(tǒng)可編程邏輯器件由于結(jié)構(gòu)不同可分為CPLD和FPGA兩種，芯片內(nèi)部有幾千至幾千萬個標(biāo)準(zhǔn)門，人們通過EDA軟件工具，采用硬件描述語言對系統(tǒng)的行為或邏輯功能進(jìn)行描述，經(jīng)編譯、仿真、優(yōu)化、適配并通過電纜下載到芯片中，從而獲得滿足功能要求的芯片。在系統(tǒng)可編程器件的特點(diǎn)是不要專門的編程器；器件可先焊接在電路板上，然后再對它進(jìn)行編程，不滿足要求還可重新編程；設(shè)計可以在各種層次上進(jìn)行，可采用自下而上或自上而下的設(shè)計方法，受到電子工程師的歡迎，并可在一塊芯片上構(gòu)造一個復(fù)雜的數(shù)字系統(tǒng)［4］。

下面以圖1中s2和s3為例說明自控系統(tǒng)的設(shè)計方法。

對于s2，t1發(fā)生時，它獲得一個托肯，t2發(fā)生時，它失去一個托肯，可用一個觸發(fā)器來代表它的狀態(tài)，觸發(fā)器為1時表示它有托肯，觸發(fā)器為0時，表明它沒有托肯。S3用8位寄存器表示，當(dāng)t1發(fā)生時，s4中有多少托肯它增加多少托肯。

再來分析一下t1、t2有發(fā)生權(quán)的條件，t1有發(fā)生權(quán)的條件是：tt1=（s1= =1）&（s2= =0）&（s5《=13）&（s3《=^h7f）&（s4《=^h7f），其中^h代表16進(jìn)制，s5、s6分別用4位寄存器表示。t2有發(fā)生權(quán)的條件是：tt2=（s1= =0）&（s2= =1）&（6《=13）&（s3《=^h7f）&（s4《=^h7f）。由于ABEL-HDL中是無符號數(shù)運(yùn)算，故采用了條件（s3《=^h7f）&（s4《=^h7f），以防s2和s3的存儲器數(shù)據(jù)溢出。

用set信號置初始標(biāo)識，采用同步置位，同步信號為clk，上升沿作用。t1和t2加外部同步信號。

程序編制完成后，進(jìn)行編譯并進(jìn)行邏輯化簡?？梢酝ㄟ^編制測試程序?qū)ο到y(tǒng)的功能進(jìn)行仿真。本文是在Lattice公司的EDA軟件工具ispDesign EXPERT環(huán)境中對圖1所示自控網(wǎng)系統(tǒng)進(jìn)行設(shè)計和仿真的，仿真波形如圖2所示。從波形圖中可看出，T1的第1個脈沖到來時，由于變遷T1沒有發(fā)生權(quán)，所以不會發(fā)生，數(shù)據(jù)沒有變化。當(dāng)計算到第13個Fibonacc數(shù)時，s4為144時，為防止數(shù)據(jù)溢出導(dǎo)致不正確的結(jié)果，停止了計算。經(jīng)適配并最終下載在ispPLSI1032E芯片中，獲得計算Fibonacci級數(shù)的專用芯片。

圖2 仿真波形

3．結(jié)束語

自控網(wǎng)系統(tǒng)由于它的非線性特點(diǎn)，用它來描述復(fù)雜系統(tǒng)特別是一些算法比其它的Petri網(wǎng)子類更有效。用硬件描述語言對自控網(wǎng)系統(tǒng)進(jìn)行描述，通過EDA軟件工具進(jìn)行仿真和硬件實(shí)現(xiàn)，為自控網(wǎng)系統(tǒng)的性能分析提供了新的途徑，也為它的實(shí)際應(yīng)用提供了物理保證。隨著人們對自控網(wǎng)系統(tǒng)研究的深入，本文所提出的自控網(wǎng)系統(tǒng)的仿真與硬件方法將得到進(jìn)一步的應(yīng)用。