基于三值光計算機的細胞自動機計算系統

李 梅

(西安工業大學 計算機科學與工程學院，陜西 西安 710021)

0 引 言

三值光計算機[1-3]，經過幾次大的理論突破，現已發展成為能夠并行處理百位量級三值邏輯運算的實驗系統[4-8]。文中在此實驗系統上實現大規模二維三值細胞自動機的演化計算，把細胞自動機的天然并行性和三值光計算機的數據位巨并行性結合起來，極大地簡化了運算過程的時間復雜性；同時，發揮三值光計算機的運算器可重構性[9]，極大地擴充了細胞自動機演化規律的靈活性和多樣性，為細胞自動機的應用創造了更好的條件。

1 三值光計算機的相關特點

三值光計算機是一種光電混合并行數字計算機，通過控制液晶改變光的偏振性完成運算，一次運算可以處理整屏數據，因此三值光計算機擁有巨大的數據位數。同時，依據降值設計理論和方法[9]設計的三值光學邏輯處理器可以規范地為各種二元三值邏輯運算構建專門的運算器單元，具有邏輯運算器的重構性。

2 細胞自動機

細胞自動機是一種具有時間、空間和狀態離散性的動力學系統[10-11]，可表示為CA=(Ld,S,N,f)。其中，L為細胞空間，d為細胞空間維數；S為細胞的有限狀態集；N表示鄰域細胞的組合，可以采用(S1,S2,…,S|N|)表示，|N|是此組合鄰域細胞的個數；f表示將(S1,S2,…,S|N|)映射到S的一個狀態轉換函數。

目前實現細胞自動機有兩種方法，用VLSI實現[12]和軟件模擬[13]。用VLSI實現，雖然運算速度快、結構簡單，但細胞單元之間的局部狀態轉換規則一旦確定就很難改變。用軟件模擬需要逐個計算每個細胞的演化函數，屬于串行過程，當規模巨大時效率急劇降低。

3 三值光計算機上實現細胞自動機

3.1 三值邏輯運算

表1 二元三值邏輯函數真值表

有了上面的運算編號，就可以給三值光計算機完成的特殊運算Θ給予定義：

定義1：設A，B是大小為m×n的矩陣，其中矩陣元素ai,j,bi,j∈{0,1,2}，i∈{0,1,…,m-1},j∈{0,1,…,n-1}。運算Ψ1,Ψ2,…,Ψm×n∈M，AΘB是矩陣對應元素做三值邏輯運算，并且矩陣每位的運算方式都可不同，如下所示：

三值光計算機可以在一個時鐘周期內完成兩個大規模矩陣的AΘB運算。

3.2 實現三值邏輯運算的器件

基于降值設計理論(decreased-radix design principle，DRDP)設計實現的三值邏輯光學處理器是三值光計算機的核心器件，能夠完成任意二元三值邏輯運算。

3.2.1 理論的主要內容

降值設計規律可以表述為：在選擇用來表示N值信息的N個物理狀態中，如果包含一個特殊的物理狀態—D狀態，則迭合n×n×(n-1)個運算基元中不超過n×(n-1)個運算基元就可以構造出任一個N值邏輯運算器(共有n(n×n)個)。

從降值設計規律中抽取出降值設計理論，該理論的核心內容為：“D”是一個特殊物理狀態，它與任何其他狀態A相遇后結果仍是狀態A；如果用來表示信息的物理狀態中包含一個狀態“D”，則n(n×n)個n值邏輯運算器中的任一個都可以按照規范的降值構造步驟，組合n×n×(n-1)個運算基元中的幾個而成。

3.2.2 通用降值設計規范

(1)寫出待設計的邏輯運算器的真值表；

(2)確定元素d的值，通常就是邏輯運算真值表的C列中出現次數最多的那個邏輯值，并確定集合W與集合F的元素為一一對應關系(其中d與D對應)；

(3)寫出與真值表對應的物理狀態遷移表；

(4)對物理狀態遷移表應用分解定理，得到若干個基元表；進而得到對應的運算基元的編號，即標準設計組件的編號；

(5)用迭合器實現各運算基元的迭合操作，實現邏輯運算器。

3.2.3 運算器件構造

圖1是實現的三值邏輯運算的一種基元的光學硬件結構。其中，a和b為光輸入端，c為光輸出端；h1和h2為水平偏振片，它能吸收垂直線偏振光V透過水平線偏振光H；v1為垂直偏振片，它能吸收水平線偏振光H透過垂直線偏振光V；矩形框Lc為光控液晶單元，虛線是它的光控端，當其光控端有光時，Lc能控制穿過它的光束的偏振方向旋轉90度，而當其光控端無光時，穿過它的光束的偏振方向保持不變。

圖1 某處理基元的光學硬件結構

此光路的工作原理為：h2、v1和Lc構成了一路光閥，當a是無光態(W)或垂直線偏振光(V)時，由于水平偏振片h1的作用，Lc的光控端無光，于是光閥關閉，此時無論b是什么狀態，輸出端c均為無光態(W)；當a是水平線偏振光(H)時，水平線偏振光能透過h1到達Lc的光控端，即光閥打開，此時，如果b是水平線偏振光(H)，則它透過h2，再經Lc的旋光后成為了垂直線偏振光(V)，之后透過v1后到達輸出端c，即c為垂直線偏振光(V)，而當b是無光態(W)或垂直線偏振光(V)時，由于水平偏振片h2的作用，輸出端c均為無光態(W)。其他的光學運算基元均可以用類似的硬件結構實現。

總結運算器的18種運算基元的光路結構，它們具有相似的結構—兩個偏振片加一個液晶像素。其差別在于偏振片的偏振方向和液晶的靜態旋光性?；谔幚砘饴方Y構的運算器結構如圖2所示。根據液晶陣列左右所貼偏振片的偏振方向的不同，劃分為四個相等的區域：即V-V區、V-H區、H-H區和H-V區。

圖2 運算器結構

3.3 二維三值細胞自動機的數學建模

運算器是三值邏輯光學處理器的關鍵部件，它由眾多光學運算基元構成，這些基元共有18(3×3×(3-1))種。下面以18種光學運算基元中的某一種為例，說明其硬件結構。

在三值光計算機平臺上實現的細胞自動機是二維三值細胞自動機，其參數d=2，S={0,1,2}。根據三值光計算機計算平臺的特點，需要重新定義N和f的表示方法。

首先確定N，如圖3所示，把被關注的細胞標為0，然后從0號細胞開始順時針旋轉，從而可以對細胞自動機的任意一個細胞的鄰域細胞進行編號。例如向量N(0，3，7)表示圖3中間的細胞周圍與其有關系的細胞有三個，分別是自己、右鄰域細胞、左鄰域細胞。

…91011122381213227031421654152019181716

圖3 鄰域細胞的編號規則

至此，(N：F)就可以唯一地表示一種細胞自動機變換規則。例如(N：F)=((0，3，7)：(243，19062))，表示細胞自動機的一個細胞的狀態轉換函數為：此細胞與右鄰域細胞做243號運算，結果再與左鄰域細胞做19062號運算。需要強調的是，構建的細胞自動機的每個細胞的鄰域細胞組合N必須相同，F可以不同，通過F的不同可以體現細胞自動機的高可控性。

圖4是一個改進后的細胞自動機的例子，每個細胞的轉化規則都不同。圖中就是一個由16個細胞組成的二維三值細胞陣列，每個細胞的狀態轉化函數由填寫在細胞處的兩個向量表示。如第一行第一列的細胞((0,1,3):(15471,17421))表示此細胞下一時刻狀態由此細胞分別和上、右鄰域細胞做15471號、17421號邏輯運算所得的結果決定。此細胞的右鄰域細胞是第一行第二列，上鄰域細胞有兩種選擇，零邊界時直接是0，循環邊界是第四行第一列。

(0,1,3):(15471,17421)(0,1,3):(9876,15271)(0,1,3):(15700,10629)(0,1,3):(15793,17493)(0,1,3):(15957,15793)(0,1,3):(10119,16030)(0,1,3):(15943,15715)(0,1,3):(15943,15751)(0,1,3):(10629,15700)(0,1,3):(17421,15943)(0,1,3):(15271,15646)(0,1,3):(17493,9841)(0,1,3):(15646,9876)(0,1,3):(15715,15957)(0,1,3):(9841,15471)(0,1,3):(15751,10119)

圖4 改進后的三值二維細胞自動機

3.4 錯位疊加運算

三值邏輯光學處理器的解碼器能夠讀出每一條信號光線攜帶的信息，根據在V-V區、V-H區、H-H區和H-V區(如圖2所示)的相應位置通過判斷有無光而非光強大小，即可精確解碼，將光信號數據轉換成電子信號數據輸出顯示。

例如，要計算一個大小為m×n的細胞自動機CA=(L2,{0,1,2},N,f)，每個細胞的變化規則是(N:Fi)，0

下面是錯位疊加計算的具體方法。用矩陣A表示二維三值細胞陣列，每一個細胞的狀態由ai,j表示。如圖5所示，把矩陣A的所有數據循環左移一個單位構成矩陣B。AΘB的運算結果矩陣C就是細胞陣列A的所有細胞與其右鄰域細胞做邏輯運算的結果；再把矩陣A的所有數據循環下移一個單位構成矩陣D，DΘC的運算結果形成矩陣E，也就是細胞陣列A的所有細胞與其上鄰域細胞做邏輯運算的結果。這樣細胞陣列A與右鄰域細胞以及上鄰域細胞所做的邏輯運算的結果分別獲取成功。

圖5 用三值光計算機完成細胞自動機的狀態轉移

由于建立的細胞自動機計算模型的N相同，也就是每個細胞的狀態轉化規則的鄰域細胞組合相同，而運算規則不同。利用三值光計算機做AΘB運算，每位運算規則都有不同的特點，可以并行完成所有細胞與周圍細胞做邏輯運算(N:Fi)，至此一次細胞自動機的迭代計算完成，實現了二維三值細胞自動機的并行演化計算。

4 實驗驗證

在三值光計算機平臺上實現細胞自動機計算系統，完成細胞自動機的演化計算的時間復雜度與細胞自動機的細胞數目無關，只與細胞自動機所選狀態轉換函數的|N|有關，而且每個細胞的運算規則都是可控的。

目前，已經實現的百位量級三值邏輯運算的實驗系統可以完成由42個細胞組成的細胞自動機的演化計算。以圖4中規定的轉化規則對4×4的二維細胞自動機進行零邊界演化計算，結果如圖6所示。

該實驗系統采用的是市面上常見的串行控制顯示器液晶屏，雖然目前還無法充分體現系統的并行優勢，但是目前全像素并行控制的液晶模塊已經設計定做完成，而且增加數據寬度在理論上已經趨于完善，可實用的三值光計算機指日可待。

圖6 實現細胞自動機一次演化計算

5 結束語

實現的高速大規?？煽丶毎詣訖C計算系統提高了細胞自動機的演化計算速度和復雜度，為細胞自動機在密碼學[14-17]、偽隨機序列生成[18-19]、復雜系統模擬[20-21]等領域的應用開辟了一條新的途徑。

[1] 金 翊，何華燦，呂養天.Ternary optical computer principle[J].Science In China:Information Sciences,2003,46(2):145-150.

[2] JIN Yi,HE Huacan,Lü Yangtian.Ternary optical computer architecture[J].Physic Scripta,2005,118:98-101.

[3] JIN Yi,HE Huacan,AI Lirong.Lane of parallel through carry in ternary optical adder[J].Science in China:Series F,2005,48(1):107-116.

[4] 包九龍,金 翊,蔡 超.三值光計算機百位量級編碼器的實現[J].計算機技術與發展,2007,17(2):19-22.

[5] 黃偉剛,金 翊,艾麗蓉,等.三值光計算機百位編碼器的設計與構造[J].計算機工程與科學,2006,28(4):139-142.

[6] 金 翊.三值光計算機高數據寬度的管理策略[J].上海大學學報:自然科學版,2007,13(5):519-523.

[7] 詹小奇，彭俊杰，金 翊，等.三值光計算機數據位資源的靜態分配策略[J].上海大學學報:自然科學版,2009,15(5):528-533.

[8] 張趙云,金 翊,嚴軍勇,等.三值光計算機遠程交互系統

設計與實現[J].計算機工程與設計,2009,30(10):2411-2413.

[9] YAN Junyong,JIN Yi,ZUO Kaizhong.Decrease-radix design priciple for carrying/borrowing free multi-valued and application in ternary optical computer[J].Science in China:Series F,2008,51(10):1415-1426.

[10] WOLFRAM S. Statistical mechanics of cellular automata[J].Reviews of Modern Physics,1983,55(3):601-644.

[11] WOLFRAM S.Theory and applications of cellular automata[J].World Scientific,1986,43(12):1346-1357.

[12] 王 穎,陳 禾.細胞自動機在VLSI測試中的應用[J].北京理工大學學報,2007,27(5):432-435.

[13] 呂曉陽,孔令江,劉慕仁.細胞自動機的演化與計算理論[J].華南師范大學學報:自然科學版,1996(2):43-49.

[14] 韓建飛.基于細胞自動機的流密碼的設計與應用研究[D].西安:西安電子科技大學,2014.

[15] 張文濤,卿斯漢,吳文玲.對一個基于細胞自動機的分組密碼變形的分析[J].軟件學報,2004,15(5):767-771.

[16] 王曉東,王麗丹,段書凱.基于憶阻細胞自動機的圖像像素值置換加密技術[J].計算機科學,2013,40(9):133-135.

[17] 夏學文,李元香,曾 輝.基于耦合觸發細胞自動機的圖像加密算法[J].計算機科學,2009,36(2):214-219.

[18] 張傳武.細胞自動機組合偽隨機序列發生器[J].電子科技大學學報,2008,37(5):716-719.

[19] 趙建林,方 勇,楊 玲,等.基于2-by-n細胞自動機的偽隨機序列發生方法研究[J].成都信息工程學院學報,2008,23(1):73-77.

[20] 時寧國,解亞萍.基于細胞自動機的城市用地仿真研究[J].系統仿真技術,2010,6(3):192-196.

[21] 于乃功,阮曉鋼.細胞自動機及其在復雜系統研究中的應用[J].計算機工程與應用,2004,40(12):25-28.