零邊界條件下二維元胞自動(dòng)機(jī)矩陣可逆性分析

劉碧川，吳秋軒

(杭州電子科技大學(xué)自動(dòng)化研究所，浙江杭州310018)

0 引言

元胞自動(dòng)機(jī)是定義在一個(gè)由具有離散、有限狀態(tài)的元胞組成的元胞空間上，并按照一定局部規(guī)則，在離散的時(shí)間維上演化的動(dòng)力學(xué)系統(tǒng)。元胞自動(dòng)機(jī)理論自提出以來(lái)得到了長(zhǎng)足的發(fā)展，開(kāi)始只是對(duì)元胞自動(dòng)機(jī)進(jìn)行了探索性的研究［1］，逐步將建立在矩陣代數(shù)中的一維元胞自動(dòng)機(jī)擴(kuò)展到二維元胞自動(dòng)機(jī)［2］，而后對(duì)9鄰域結(jié)構(gòu)的二維元胞自動(dòng)機(jī)進(jìn)行了研究［3］，并且對(duì)二維元胞自動(dòng)機(jī)的等效轉(zhuǎn)移矩陣特性進(jìn)行了初步的分析［4］。本文在其研究基礎(chǔ)上對(duì)矩陣的可逆性研究進(jìn)行一些探索，在一定程度上增進(jìn)了二維元胞自動(dòng)機(jī)的矩陣特性的理論發(fā)展。

1 二維元胞自動(dòng)機(jī)

二維元胞自動(dòng)機(jī)的元胞分布在二維網(wǎng)格中，元胞下一時(shí)步的狀態(tài)取決于當(dāng)前元胞和其相鄰元胞的狀態(tài)。對(duì)于 9 相鄰元胞結(jié)構(gòu)，第(i，j)個(gè)元胞在 t+1 時(shí)步的狀態(tài) q 可表述為 qi，j(t+1)=f［qi－1，j－1(t)，qi－1，j(t)，qi－1，j+1(t)，qi，j－1(t)，qi，j(t)，qi，j+1(t)，qi+1，j－1(t)，qi+1，j(t)，qi+1，j+1(t)］，其中 f表示局部規(guī)則。

元胞自動(dòng)機(jī)中演化規(guī)則是定義在空間局部范圍內(nèi)的，因而，在指定規(guī)則之前，必須定義一定的鄰域規(guī)則。以最常用的規(guī)則四方網(wǎng)格劃分為例，二維元胞自動(dòng)機(jī)的常用的鄰域結(jié)構(gòu)主要有Moore型和Von Neumann型，分別如圖1(a)、(b)所示。

中心元胞表示當(dāng)前元胞，周?chē)硎酒湎噜徳?。Moore型鄰域結(jié)構(gòu)由當(dāng)前元胞和8個(gè)相鄰元胞組成，Von Neumann型鄰域結(jié)構(gòu)由當(dāng)前元胞和其上下左右共計(jì)5個(gè)元胞構(gòu)成。網(wǎng)格中的數(shù)字則表示其規(guī)則號(hào)，如Rule 1表示當(dāng)前元胞只受其本身的影響，Rule 32則表示當(dāng)前元胞只受到其左邊元胞的影響。圖1(a)中這9個(gè)規(guī)則稱(chēng)為基礎(chǔ)規(guī)則。若當(dāng)前元胞受到兩個(gè)或多個(gè)元胞的影響，則規(guī)則號(hào)表示為幾個(gè)基礎(chǔ)規(guī)則號(hào)的代數(shù)和(只考慮線(xiàn)性規(guī)則)，如常用的Rule 170(128+32+8+2)表示當(dāng)前元胞受到上下左右4個(gè)相鄰元胞的影響。

圖1 二維元胞自動(dòng)機(jī)鄰域結(jié)構(gòu)

2 二維元胞自動(dòng)機(jī)的描述矩陣

二維元胞自動(dòng)機(jī)在任一時(shí)步的狀態(tài)均可用m×n階位信息矩陣來(lái)表示。為便于分析，將轉(zhuǎn)移規(guī)則按文獻(xiàn)3，5中所述等效為mn×mn階矩陣M，初始狀態(tài)中每一行進(jìn)行轉(zhuǎn)置成Xmn×1，則下一時(shí)步狀態(tài)Ymn×1=MXmn×1。若元胞僅有{0，1}兩個(gè)狀態(tài)，但MX會(huì)產(chǎn)生不屬于這個(gè)狀態(tài)集中的2，3…狀態(tài)，這是由于實(shí)際中當(dāng)前元胞的狀態(tài)是由其相鄰元胞狀態(tài)異或得到的，而在數(shù)學(xué)表達(dá)式中卻是簡(jiǎn)單的相加，故準(zhǔn)確來(lái)講，下一狀態(tài)Y=MX mod 2。由此可推得，對(duì)于k個(gè)有限狀態(tài){0，1，2，…，k－1}的元胞自動(dòng)機(jī)，其下一狀態(tài)Y=MX mod k，其中X為當(dāng)前狀態(tài)，M為元胞規(guī)則的等效矩陣。

在零邊界條件下，二維元胞自動(dòng)機(jī)的等效轉(zhuǎn)移矩陣 M為三對(duì)角矩陣，即 M=。其中，D，U，L=0 或 In×n或(T1)n×n或(T2)n×n或 Sn×n或(I+T1)n×n或 (I+T1)n×n或 (I+S)n×n［6］，S=T1+T2，T1和 T2是 兩 個(gè) 基 礎(chǔ) 矩 陣，分 別 為 T1=

轉(zhuǎn)移矩陣M的特性取決于其子矩陣D，U，L的取值。D表示當(dāng)前元胞受到其同一行元胞的影響的情況，若不受影響，則D=0，反之亦然;U和L分別表示當(dāng)前元胞受到其下一行元胞和上一行元胞的影響情況［7］。

3 規(guī)則矩陣的可逆性

若用 Mi表示第 i號(hào)規(guī)則，其中 i=1，2，3，…，511，即 M1表示 Rule 1，M2表示 Rule 2，以此類(lèi)推。由于規(guī)則矩陣的線(xiàn)性可加性，且M32=(M2)T，M64=(M4)T，M128=(M8)T，M256=(M16)T則根據(jù)文獻(xiàn)4中所述，將{M1，M2，M4，M8，M16}做為基礎(chǔ)矩陣，其他規(guī)則矩陣都可由此5個(gè)基礎(chǔ)矩陣變換得到，例如 M15=M1+M2+M4+M8，M33=M1+M32=M4+(M2)T。

對(duì)5個(gè)基礎(chǔ)矩陣的塊矩陣進(jìn)行分析，可得M1中D=I，U=L=0;M2中D=T1，U=L=0;M4中U=T1，D=L=0;M8中 U=I，D=L=0;M16中 U=T2，D=L=0。

根據(jù)以上分析結(jié)果，假設(shè)當(dāng)前元胞的下一時(shí)步狀態(tài)僅與其Moore型鄰域的4個(gè)對(duì)角元胞(即其中非Von Neumann 型鄰域)相關(guān)，則轉(zhuǎn)移矩陣 M中，U，L=(T1)n×n或(T2)n×n或 Sn×n。可得 M中(或經(jīng)過(guò)初等變換)必有全0行，故M不可逆。由此可得:

定理 若元胞自動(dòng)機(jī)的規(guī)則矩陣可逆，則當(dāng)前元胞的下一時(shí)步狀態(tài)與其Von Neumann型鄰域的當(dāng)前狀態(tài)相關(guān)。

例:2×3維元胞自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移矩陣M276=0，其中，S=T1+T2，故|M276|=0，M276不可逆。

4 結(jié)束語(yǔ)

本文介紹了二維元胞自動(dòng)機(jī)常見(jiàn)的兩種鄰域結(jié)構(gòu)，并對(duì)Moore型鄰域結(jié)構(gòu)更新規(guī)則的狀態(tài)轉(zhuǎn)移矩陣進(jìn)行了拓展，并對(duì)矩陣的可逆性進(jìn)行了探索性的研究，指出了規(guī)則矩陣的可逆性和其Von Neumann型鄰域的聯(lián)系，但二維元胞自動(dòng)機(jī)狀態(tài)轉(zhuǎn)移矩陣可逆性的研究還沒(méi)有一個(gè)系統(tǒng)的方法，還需要進(jìn)一步的探究。

［1］ Norman H Packard，Stephen Wolfram.Two-Dimensional Cellular Automata［J］.Journal of Statistical Physics，1985，38(5－6):901－946.

［2］ Chowdhury D R，Gupta IS，Chaudhuri P P.A low cost high capacity associative memory design using cellular automata［J］.IEEE Trans on Computers，1995，44(10):1 260 －1 264.

［3］ Khan A R，Choudhury PP，Dihidar K.VLSIarchitecture of a cellular auto mat a machine［J］.Computers and Mathematics with applications，1997，33(5):79 －94.

［4］ Choudhury P P，Birendra K N，Sudhakar Sahoo，et al.Theory and Applications of Two－ dimensional，Null-boundary，Nine-Neighborhood，Cellular Automata Linear rules［EB/OL］.http://arxiv.org/abs/0804.2346，2008 －04 －15.

［5］ Chattopadhyay P，Choudhury P P，Dihidar K.Characterisation of a Particular Hybrid Transformation of Two-Dimensional Cellular Automata［J］.Computers＆ Mathematics with Applications，1999，38(5－6):207－216.

［6］ Abdul Raouf Khan.Classification of2D Cellular Automata Uniform Group Rules［J］.European Journal of Scientific Research，2011，64(1):51－57.

［7］ Santoso J，Santoso O Slamet，Trilaksono B Riyanto.Matrix characteristics for two dimensional nongroup Cellular Automata［A］.International Conference on Electrical Engineering and Informatics［C］.Bandung，Indonesia，2011:1－4.