數(shù)字二進(jìn)制計(jì)數(shù)器的設(shè)計(jì)和實(shí)現(xiàn)

將二進(jìn)制數(shù)視為元胞自動(dòng)機(jī)可能有助于數(shù)字二進(jìn)制計(jì)數(shù)器的設(shè)計(jì)和實(shí)現(xiàn)嗎?

正如大多數(shù)讀者已經(jīng)知道的那樣，二進(jìn)制計(jì)數(shù)類(lèi)似于任何其他數(shù)字系統(tǒng)中的計(jì)數(shù)。計(jì)數(shù)從使用下一個(gè)可用符號(hào)(十進(jìn)制的 0 到 9，八進(jìn)制的 0 到 8，十六進(jìn)制的 0 到 F，二進(jìn)制的 0 和 1)增量替換最低有效位(最右邊的位置)開(kāi)始。當(dāng)這個(gè)數(shù)字的符號(hào)用盡時(shí)(因?yàn)樽詈笠粋€(gè)符號(hào)已經(jīng)被使用)，這個(gè)最低有效數(shù)字被重置為 0 并且左邊的數(shù)字增加。此過(guò)程以迭代方式繼續(xù)，因此當(dāng)任何位置的數(shù)字符號(hào)用盡時(shí)，該數(shù)字重置為 0，并且其左側(cè)的數(shù)字遞增。

我們剛剛在上面所做的是設(shè)置了一個(gè)規(guī)則，用于計(jì)算或從一個(gè)數(shù)字演變?yōu)橄乱粋€(gè)數(shù)字。一個(gè)數(shù)字可以被認(rèn)為是一個(gè)n位的一維數(shù)組(在二進(jìn)制的情況下稱為“位”)，其中用于一個(gè)數(shù)字的下一個(gè)符號(hào)不僅取決于該數(shù)字的當(dāng)前符號(hào)，還取決于在數(shù)組中其他數(shù)字的當(dāng)前符號(hào)上?；诖?，我開(kāi)始懷疑將二進(jìn)制數(shù)視為元胞自動(dòng)機(jī)是否有助于數(shù)字二進(jìn)制計(jì)數(shù)器的設(shè)計(jì)和實(shí)現(xiàn)。

編者注：從 Conway 的生命游戲到 Langton 的螞蟻再到 Reynold 的 Boids，人工生命模擬展示了由簡(jiǎn)單規(guī)則引起的復(fù)雜緊急行為(另見(jiàn)“人工生命模擬”)。

很明顯，如果不知道元胞自動(dòng)機(jī)是什么以及它如何與數(shù)字?jǐn)?shù)組相關(guān)，我將無(wú)法對(duì)此感到疑惑，但是當(dāng)我們閱讀以下元胞自動(dòng)機(jī)的簡(jiǎn)明一般定義時(shí)，這種關(guān)系變得顯而易見(jiàn)：

一個(gè)規(guī)則的細(xì)胞網(wǎng)格，其特征是有限數(shù)量的狀態(tài)，這些狀態(tài)將根據(jù)一些固定規(guī)則(進(jìn)化)從當(dāng)前變化(進(jìn)化)到下一代，該規(guī)則根據(jù)兩者的當(dāng)前狀態(tài)確定每個(gè)細(xì)胞的新?tīng)顟B(tài)單元格和其他單元格(其鄰域)。

在二進(jìn)制數(shù)的情況下，位等價(jià)于單元格，可能的狀態(tài)是 0 和 1，自動(dòng)機(jī)是一維的(上面的網(wǎng)格只有一行，因?yàn)橹挥幸粋€(gè)數(shù)組要考慮)，以及任何生成的自動(dòng)機(jī)表示與其所有位的狀態(tài)相對(duì)應(yīng)的數(shù)字。

一維元胞自動(dòng)機(jī)的一個(gè)特例是所謂的初等元胞自動(dòng)機(jī)，其中每個(gè)元胞只能有兩個(gè)狀態(tài)，并且下一代每個(gè)元胞的狀態(tài)僅取決于元胞及其兩個(gè)直接鄰居的當(dāng)前狀態(tài)(右邊和左邊)。這種基本元胞自動(dòng)機(jī)的一個(gè)例子就是規(guī)則 90，其中所有單元的狀態(tài)同時(shí)被它們的兩個(gè)相鄰單元的狀態(tài)的異或 (XOR) 替換。

圖 1：具有隨機(jī)初始條件的規(guī)則 90 的時(shí)空?qǐng)D(來(lái)源：Javier Piay)

當(dāng)從單個(gè)活細(xì)胞(只有一個(gè)細(xì)胞的狀態(tài)為 1)開(kāi)始時(shí)，規(guī)則 90 具有謝爾賓斯基三角形形式的時(shí)空?qǐng)D(隨時(shí)間演變的一維數(shù)組)。

圖 2：規(guī)則 90 的時(shí)空?qǐng)D從單個(gè)活細(xì)胞開(kāi)始，形成謝爾賓斯基三角形。(來(lái)源：哈維爾皮耶)

在本視頻中，您將找到一些我為三個(gè)計(jì)算機(jī)平臺(tái)創(chuàng)建的規(guī)則 90 自動(dòng)機(jī)動(dòng)畫(huà)：micro:bit、Arduino 和我的SANX-I 微型計(jì)算機(jī)。

就受歡迎程度和學(xué)術(shù)/科學(xué)興趣而言，約翰康威創(chuàng)造的生命游戲元胞自動(dòng)機(jī)排名第一?？低纳螒蚴且粋€(gè)二維元胞自動(dòng)機(jī)，其中每個(gè)細(xì)胞根據(jù)一些簡(jiǎn)單的方法與其八個(gè)鄰居相互作用進(jìn)化規(guī)律如下：

任何少于兩個(gè)活鄰居的活細(xì)胞都會(huì)死亡，就像人口不足一樣。

任何有兩三個(gè)活鄰居的活細(xì)胞都可以活到下一代。

任何有超過(guò)三個(gè)活鄰居的活細(xì)胞都會(huì)死亡，就像人口過(guò)剩一樣。

任何只有三個(gè)活鄰居的死細(xì)胞都會(huì)變成活細(xì)胞，就像通過(guò)繁殖一樣。

生命游戲自動(dòng)機(jī)產(chǎn)生許多不同類(lèi)型的動(dòng)畫(huà)、意想不到和不可預(yù)測(cè)的模式(如靜物、振蕩器和宇宙飛船)，即使是那些偶然發(fā)現(xiàn)它的人中最不好奇的人也會(huì)對(duì)這種細(xì)胞自動(dòng)機(jī)著迷。我還編寫(xiě)了程序來(lái)模擬不同平臺(tái)上的生命游戲，并從隨機(jī)初始配置(生成)和特定配置開(kāi)始探索這些動(dòng)畫(huà)模式。在此視頻中，您將找到我的 Arduino 生命游戲。

在這個(gè)視頻中，你會(huì)發(fā)現(xiàn)我的 micro:bit 生命游戲：

到目前為止，一切都很好(我希望)。

現(xiàn)在，如果您回想本專(zhuān)欄的開(kāi)頭，您會(huì)記得本文的真正目的是確定將二進(jìn)制數(shù)視為元胞自動(dòng)機(jī)是否有助于數(shù)字二進(jìn)制計(jì)數(shù)器的設(shè)計(jì)和實(shí)現(xiàn)。我們已經(jīng)知道，我們正在尋找的元胞自動(dòng)機(jī)將是一維的，但不是基本類(lèi)型，因?yàn)橄乱淮?xì)胞/數(shù)字/位的狀態(tài)不僅僅取決于細(xì)胞的當(dāng)前狀態(tài)及其兩個(gè)直接鄰居。實(shí)際上，該狀態(tài)似乎僅取決于其右側(cè)鄰居的當(dāng)前狀態(tài)。你怎么看?

如果你仔細(xì)看計(jì)數(shù)規(guī)則，你會(huì)發(fā)現(xiàn)這是一個(gè)迭代過(guò)程，其中一個(gè)數(shù)字的下一個(gè)值不僅取決于它自己的值和它右邊數(shù)字的值，還取決于數(shù)字的值在其右側(cè)的數(shù)字的右側(cè)。這個(gè)迭代過(guò)程或依賴關(guān)系一直持續(xù)到數(shù)組的最右邊(最低有效位)。換句話說(shuō)，一個(gè)數(shù)字的下一個(gè)值取決于它自己的值和它右邊所有數(shù)字的值。

當(dāng)我得出這個(gè)結(jié)論時(shí)，我首先認(rèn)為這樣的自動(dòng)機(jī)會(huì)比基本自動(dòng)機(jī)復(fù)雜得多(其中一個(gè)單元僅受其兩個(gè)相鄰鄰居的影響);此外，很難設(shè)定和實(shí)施進(jìn)化(計(jì)數(shù))規(guī)則。幸運(yùn)的是，我意識(shí)到這種對(duì)幾個(gè)單元格(實(shí)際上是右邊的所有單元格)的依賴可以轉(zhuǎn)換為對(duì)右邊相鄰單元格的依賴，從而產(chǎn)生一種“簡(jiǎn)化和修改的基本自動(dòng)機(jī)”。

只需向每個(gè)單元格(除了其二進(jìn)制狀態(tài))添加一個(gè)新屬性或 FLAG 即可輕松完成此轉(zhuǎn)換，其值僅由其右側(cè)的單元格修改。當(dāng)其右邊所有單元的狀態(tài)為 1 時(shí)，該 FLAG 將為 1，這意味著自動(dòng)機(jī)滿足進(jìn)化規(guī)則，因此，單元的下一個(gè)狀態(tài)將從 0 變?yōu)?反轉(zhuǎn))為 1，或從 1 到 0，根據(jù)本文第一段中描述的增量替換過(guò)程(二進(jìn)制增量)。如前所述，這個(gè)FLAG的值只會(huì)被右邊的單元格修改;因此，當(dāng)且僅當(dāng)此單元狀態(tài)的當(dāng)前狀態(tài)值和與右側(cè)單元關(guān)聯(lián)的 FLAG 的值都為 1 時(shí)，它將被設(shè)置為 1。

如前所述，我稱這個(gè)元胞自動(dòng)機(jī)為“簡(jiǎn)化的”和“修改的”基本自動(dòng)機(jī)——“簡(jiǎn)化”是因?yàn)槿魏螁卧?受影響的單元格)的鄰域都被簡(jiǎn)化為右側(cè)的單元格并被“修改”，因?yàn)槊總€(gè)單元格都具有特征不僅取決于它的狀態(tài)，還取決于它的 FLAG。

只要一個(gè)或多個(gè)細(xì)胞滿足進(jìn)化規(guī)則(將它們的 FLAG 設(shè)置為 1)，這個(gè)自動(dòng)機(jī)就會(huì)進(jìn)化。但是要讓這個(gè)自動(dòng)機(jī)能夠持續(xù)進(jìn)化，最右邊的細(xì)胞必須始終滿足進(jìn)化規(guī)則所施加的要求;否則，一旦該單元的狀態(tài)變?yōu)?0，進(jìn)化將停止。因此，最右邊的單元將連接到其右側(cè)稱為 ENABLE 的外部輸入。如果 ENABLE 為 TRUE(或 1)，自動(dòng)機(jī)將進(jìn)化(執(zhí)行二進(jìn)制計(jì)數(shù));否則，所有后續(xù)世代都將保持不變。

從當(dāng)前一代到下一代的進(jìn)化將由從最右邊的單元到最左邊的單元級(jí)聯(lián)的外部時(shí)鐘信號(hào)控制。

對(duì)于初始或第一代，任何單元格中都允許任何狀態(tài)(0/1)。但是，出于演示目的，我們將首先將所有單元格清除為初始狀態(tài) 0。

正如你們中最有洞察力的人現(xiàn)在可能意識(shí)到的那樣(正如托比魔鬼——羅文·阿特金森爵士扮演的角色——可能會(huì)說(shuō)的那樣)，這個(gè)自動(dòng)機(jī)可以通過(guò)級(jí)聯(lián)連接來(lái)實(shí)現(xiàn)，我稱之為“基本單元”。

這個(gè)基本單元有兩個(gè)輸入和兩個(gè)輸出。任何單元的輸入都將連接到其右側(cè)鄰居的輸出，而任何單元的輸出將連接到其左側(cè)鄰居的輸入。

每個(gè)單元的輸入之一將是 CLOCK 信號(hào)，另一個(gè)將由其右鄰居使用來(lái)修改其 FLAG。同樣，每個(gè)單元的輸出之一將是 CLOCK 信號(hào)，而另一個(gè)將用于修改其左側(cè)單元的 FLAG。

圖 3 顯示了基本單元的數(shù)字電子實(shí)現(xiàn)，使用一個(gè) D 型觸發(fā)器來(lái)存儲(chǔ)其當(dāng)前狀態(tài)，一個(gè) XOR 門(mén)在其 FLAG 設(shè)置為 1 時(shí)更改(反轉(zhuǎn))其狀態(tài)，以及一個(gè) AND 門(mén)來(lái)設(shè)置當(dāng)它的狀態(tài)和它的 FLAG 都為 1 時(shí)，它左邊的單元格的 FLAG 為 1。