Fluctuation-Driven Asynchronous Cellular Automaton and Its Computational Universality

HUANG Xin; LI Jia; GE Liang; SONG Wei

doi:10.12263/DZXB.20220225

您当前的位置：

首页 >

文章列表页 >

Fluctuation-Driven Asynchronous Cellular Automaton and Its Computational Universality

PAPERS | 更新时间：2025-12-11

- Fluctuation-Driven Asynchronous Cellular Automaton and Its Computational Universality
- ACTA ELECTRONICA SINICA Vol. 52, Issue 5, Pages: 1648-1656(2024)
- 作者机构：
  
  重庆大学计算机学院，重庆 400044
- 作者简介：
- 基金信息：
  
  Chongqing Technology Innovation and Application Development Project(cstc2019jscx-zdztzxX0024)
- DOI：10.12263/DZXB.20220225
  CLC： TP301;TN40
- Received：07 March 2022，
  
  Revised：2023-04-23，
  
  Published：25 May 2024
- 稿件说明：
移动端阅览
黄鑫, 李佳, 葛亮, 等. 随机波动驱动的异步元胞自动机及其计算通用性[J]. 电子学报, 2024, 52(05): 1648-1656.

HUANG Xin, LI Jia, GE Liang, et al. Fluctuation-Driven Asynchronous Cellular Automaton and Its Computational Universality[J]. Acta Electronica Sinica, 2024, 52(05): 1648-1656.
黄鑫, 李佳, 葛亮, 等. 随机波动驱动的异步元胞自动机及其计算通用性[J]. 电子学报, 2024, 52(05): 1648-1656. DOI：10.12263/DZXB.20220225

HUANG Xin, LI Jia, GE Liang, et al. Fluctuation-Driven Asynchronous Cellular Automaton and Its Computational Universality[J]. Acta Electronica Sinica, 2024, 52(05): 1648-1656. DOI：10.12263/DZXB.20220225

摘要

元胞自动机被广泛认为是基于分子自组装技术制造量子计算机、纳米计算机的基本架构，而元胞自动机的复杂度直接影响其并行分布式计算效率以及物理实现的可行性.现有复杂度最低的异步元胞自动机使用3个元胞状态和3条变迁规则能够构造所有逻辑电路，具备与图灵机等价的计算通用性（图灵通用性）.为进一步降低通用异步元胞自动机的复杂度，本文提出新型电路元件以及基于该元件的逻辑电路设计方法.不同于同步电路的逻辑门元件，新型电路元件能够有效处理信号的随机波动，对单电子隧道晶体管等纳米材料技术有积极的应用价值.据此，本文提出新的异步元胞自动机模型，该模型仅需3个元胞状态和2条规则，比现有的通用模型复杂度低.除图灵通用性外，本文通过设计大规模分布式逻辑电路，进一步证明所提的异步元胞自动机具备与所有同步元胞自动机同等的计算能力.

Abstract

Cellular automata are widely considered as a fundamental architecture for nano-computers and quantum computers based on molecular self-assembly technology. In such a situation

the complexity of cellular automata will directly affect their efficiency of parallel distributed computing

together with the feasibility of physical implementation. The simplest model of all asynchronous cellular automata in the literatures employs three cellular states and three transition rules

which can construct all logic circuits and thus hold the computational universality equivalent to Turing machine (Turing universality). In order to further reduce the complexity of universal asynchronous cellular automata

this paper proposes a new model

which requires only three cellular states and two transition rules. The smaller number of transition rules is mainly attributed to the new circuit elements and the design of large-scale distributed circuits. Different from the logic gates of synchronous circuits

the novel circuit elements can effectively utilize the random fluctuations of signals

whereby they may promise potential applications via nano-technologies such as single-electron tunnel transistors. In addition to Turing universality

this paper explicitly provides a scalable and distributed scheme to construct parallel logic circuits

which enables our proposed asynchronous cellular automaton to realize the same parallel computing capability as synchronous cellular automata.

关键词

Keywords

references

VON N J , BURKS A . Theory of Self-Reproducing Automata [M ] . New York : Springer , 1966 .

BHATTACHARJEE K , NASKAR N , ROY S , et al . A survey of cellular automata: Types, dynamics, non-uniformity and applications [J ] . Natural Computing , 2020 , 19 : 433 - 461 .

FATES N . A guided tour of asynchronous cellular automata [J ] . Journal of Cellular Automata , 2014 , 9 ( 5-6 ): 387 - 416 .

李俊文 , 夏银水 . 基于QCA的五输入Majority门设计及应用 [J ] . 电子学报 , 2019 , 47 : 404 - 409 .

LI J W , XIA Y S . Quantum-dot cellular automata based design of five-input majority gate and its applications [J ] . Acta Electronica Sinica , 2019 , 47 ( 2 ): 404 - 409 . (in Chinese)

邓飞飞 , 解光军 , 王晓旸 , 等 . 量子元胞自动机共面五输入择多门结构的分析与设计 [J ] . 电子学报 , 2020 , 48 : 861 - 869 . (in Chinese)

DENG F F , XIE G J , WANG X Y , et al . Analysis and design of coplanar five-input majority gate in quantum-dot cellular automata [J ] . Acta Electronica Sinica , 2020 , 48 ( 5 ): 861 - 869 . (in Chinese)

DEBNATH B , DAS J C , DE D . Nanoscale cryptographic architecture design using quantum dot cellular automata [J ] . Frontiers of Information Technology & Electronic Engineering , 2019 , 20 ( 11 ): 1578 - 1586 .

BANDYOPADHYAY A , PATI R , SAHU S , et al . Massively parallel computing on an organic molecular layer [J ] . Nature Physics , 2010 , 6 ( 5 ): 369 - 375 .

CICUTTIN A , DE MICCO L , CRESPO M L , et al . Physical implementation of asynchronous cellular automata networks: Mathematical models and preliminary experimental results [J ] . Nonlinear Dynamics , 2021 , 105 : 2431 - 2452 .

MORAN A , FRASSER C F , ROCA M , et al . Energy-efficient pattern recognition hardware with elementary cellular automata [J ] . IEEE Transactions on Computers , 2019 , 69 ( 3 ): 392 - 401 .

BANKS E R . Universality in cellular automata [C ] // 11th Annual Symposium on Switching and Automata Theory (swat 1970) . Piscataway : IEEE , 1970 : 194 - 215 .

FEI L J , LEE J , HUANG X , et al . Effect of random fluctuations on minimizing the complexity of universal asynchronous cellular automata [J ] . Physica D: Nonlinear Phenomena , 2021 , 428 : 133052 1 - 9 .

MARTIN A J , NYSTROM M . Asynchronous techniques for system-on-chip design [J ] . Proceedings of the IEEE , 2006 , 94 ( 6 ): 1089 - 1120 .

LEE J P F , ADAMATZKY A , ALONSO-SANZ R . On brownian cellular automata [C ] // Automata-2008: Theory and Applications of Cellular Automata . New York : Luniver Press , 2008 : 278 - 291 .

YAMASHITA T , ISOKAWA T , PEPER F , et al . Turing-completeness of asynchronous noncamouflaged cellular automata [J ] . Information and Computation , 2020 , 274 : 104539.1 - 104539.17

HELBING D , HUBERMAN B A . Moving like a solid block [J ] . Nature , 1998 , 396 ( 6713 ): 738 - 740 .

LEHMANN F , ROOP P S , RANJITKAR P . Extending particle hopping models for road traffic with timed automata [J ] . Physica A: Statistical Mechanics and Its Applications , 2020 , 553 : 124107.1 - 124107.20 .

PEPER F , LEE J , CARMONA J , et al . Brownian circuits: Fundamentals [J ] . ACM Journal on Emerging Technologies in Computing Systems (JETC) , 2013 , 9 ( 1 ): 3.1 - 3.24 .

LEE J , PEPER F , COTOFANA S D , et al . Brownian circuits: Designs [J ] . International Journal of Unconventional Computing , 2016 , 12 ( 5-6 ): 341 - 362 .

KISH L B , GRANQVIST C G . On the security of the Kirchhoff-law-johnson-noise (KLJN) communicator [J ] . Quantum Information Processing , 2014 , 13 : 2213 - 2219 .

RAO C V , WOLF D M , ARKIN A P . Control, exploitation and tolerance of intracellular noise [J ] . Nature , 2002 , 420 ( 6912 ): 231 - 237 .

ERCAN İ , SÜTGÖL Z D , ÖZHAN F O . Physical limitations on fundamental efficiency of set-based brownian circuits [J ] . Entropy , 2021 , 23 ( 4 ): 406.1 - 406.16 .

AGBO I , SAFIRUDDIN S , COTOFANA S . Implementable building blocks for fluctuation based calculation in single electron tunneling technology [C ] // 2009 9th IEEE Conference on Nanotechnology (IEEE-NANO) . Piscataway : IEEE , 2009 : 366 - 369 .

JIBIKI Y , GOTO M , TAMURA E , et al . Skyrmion Brownian circuit implemented in continuous ferromagnetic thin film [J ] . Applied Physics Letters , 2020 , 117 ( 8 ): 1 - 5 .

OLLINGER N , BÄCK T , KOK J N . Universalities in Cellular Automata [M ] // Handbook of Natural Computing . Heidelberg : Springer , 2012 : 189 - 229 .

BRICENO R , RAPAPORT I . Communication complexity meets cellular automata: Necessary conditions for intrinsic universality [J ] . Natural Computing , 2021 , 20 ( 2 ): 307 - 320 .

PATRA P , FUSSELL D S . Building-Blocks for Designing DI Circuits [R ] . University of Texas at Austin, Department of Computer Sciences , 1993 .

茅剑锋 , 赵千川 . 异步电路验证算法 [J ] . 计算机学报 , 2004 , 27 ( 1 ): 66 - 78 .

MAO J F , ZHAO Q C . Verification algorithms for asynchronous circuits [J ] . Chinese Journal of Computers , 2004 , 27 ( 1 ): 66 - 78 . (in Chinese)

孙智权 . 基于Balsa的异步集成电路设计方法 [J ] . 科学技术与工程 , 2008 , 8 ( 16 ): 4527 - 4530 .

SUN Z Q . Design methodology asynchronous circuits based on Balsa [J ] . Science Technology and Engineering , 2008 , 8 ( 16 ): 4527 - 4530 . (in Chinese)

KELLER R M . Towards a theory of universal speed-independent modules [J ] . IEEE Transactions on Computers , 1974 , 100 ( 1 ): 21 - 33 .

LEE J , PEPER F , ADACHI S , et al . Universal delay-insensitive systems with buffering lines [J ] . IEEE Transactions on Circuits and Systems I: Regular Papers , 2005 , 52 ( 4 ): 742 - 754 .

WOODS D . Intrinsic universality in self-assembly [M ] // Encyclopedia of Algorithms . New York : Springer , 2016 : 993 - 998 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

HUANG Xin

LI Jia

GE Liang

SONG Wei

Related Institution

College of Computer Science， Chongqing University

⁰