384 Rule110 cell automata

384 : Rule110 cell automata

  • Author: ReJ aka Renaldas Zioma
  • Description: Cellular automaton based on the Rule 110
  • GitHub repository
  • Clock: 0 Hz

How it works

This design executes over 200 cells of an elementary cellular automaton every cycle applying Rule 110 to all of them in parallel. Roughly 115 cells with parallel read/write bus can be placed on 1x1 TinyTapeout tile. Without read/write bus, up to 240 cells fit on a 1x1 tile!

The edge of chaos - Rule 110 exhibits complex behavior on the boundary between stability and chaos. It could be explored for pseudo random number generator and data compression.

Gliders - periodic structures with complex behaviour, universal computation and self-reproduction can be implemented with Rule 110.

Turing complete - with a particular repeating background pattern Rule 110 is known to be Turing complete. This implies that, in principle, any calculation or computer program can be simulated using such automaton!

Definition of Rule 110

The following rule is applied to each triplet of the neighboring cells. Binary representation 01101110 of 110 defines the transformation pattern.

1. Current iteration of the automaton
            111  110  101  100  011  010  001  000
             |    |    |    |    |    |    |    |
             v    v    v    v    v    v    v    v
2. The next iteration of the automaton
            .0.  .1.  .1.  .0.  .1.  .1.  .1.  .0.

Interesting links for further reading

How to test

After RESET all cells will be set to 0 except the rightmost that is going to be 1. Automaton will immediately start running. Automaton produce new state every cycle for all the cells in parallel. One hardware cycle is one iteration of the automaton. Automaton will run until /HALT pin is pulled low.

The following diagram shows 10 first iteration of the automaton after RESET.

                                                      X
                                                     XX
                                                    XXX
                                                   XX X
                                                  XXXXX
                                                 XX   X
                                                XXX  XX
                                               XX X XXX
                                              XXXXXXX X
          automaton state on the             XX     XXX
        10th iteration after RESET  ---->   XXX    XX X

To read automaton state

  1. pull /HALT pin low and 2) set the cell block address pins.

Cells are read in 8 cell blocks and are addressed sequentially from right to left. Adress #0 represents the rightmost 8 cells. Adress #1 represents the cells from 16 to 9 on the rights and so forth.

          automaton state on the 
        10th iteration after RESET  ---->   XXX    XX X
        00000000  ...  00000000000000000000011100001101
        |      |              |       |       |       |
        [adr#14]  ...  [addr#3][addr#2][addr#1][addr#0]
            cells are addressed in blocks of 8 bits

The state of the 8 cells in the block will appear on the Output pins once the cell block address is set.

Timing diagram

CLK   ___     ___     ___     ___     ___     ___           ___
   __/   `___/   `___/   `___/   `___/   `___/   `___ ... _/   `___
     |       |       |       |       |       |             |
     |       |       |       |       |       |             |

WRITE  ____                                                 _______
    X__HALT__________________________________________ ... _/ 

WRITE_______________  ______________  _______________
   _/ ADDR#0        `/ ADDR#1       `/ ADDR#2 

READ OUTPUT_______         ________        ________
   ______/00001101`_______/00000111`______/00000000`_  
              ^                ^
              |                |
       these are the expected values on
          the 10th cycle after RESET

      ____
      HALT  - /HALT, inverted halt automata
      ADDR# - cell block address bits 0..4

(Over)write automaton state

To write state of the cells, 1) pull /HALT pin low, 2) set the cell block address pins, 3) set the new desired cell state on the Input pins and 4) finally pull /WE pin low.

Cells are updated in 8 cell blocks and are addressed sequentially from right to left. Adress #0 represents the rightmost 8 cells. Adress #1 represents the cells from 16 to 9 on the rights and so forth.

Timing diagram

CLK   ___     ___     ___     ___     ___     ___           ___
   __/   `___/   `___/   `___/   `___/   `___/   `___ ... _/   `___
     |       |       |       |       |       |             |
     |       |       |       |       |       |             |
WRITE  ____                                                 _______
    X__HALT__________________________________________ ... _/ 

WRITE_______________  ______________  _______________
   _/ ADDR#0        `/ ADDR#1       `/ ADDR#2

WRITE INPUT_________  ______________  _____________
   __/ 00000111     `/ 11100110     `/ 11010111    `_

WRITE______  __    ________  __    ________  __    __ ... _________
           `_WE___/        `_WE___/        `_WE___/
                 wait 1 cycle    wait 1 cycle

         __
    ____ WE   - /WE, inverted write enable 
    HALT      - /HALT, inverted halt automata
        ADDR# - cell block address bits 0..4

The following diagram shows 10 cycles of automaton after /HALT pulled back to high.


      [adr#14]  ...  [addr#3][addr#2][addr#1][addr#0]
      |      |              |       |       |       |
      00000000  ...  00000000110101111110011000000111
                             XX X XXXXXX  XX      XXX
                            XXXXXXX    X XXX     XX X
                           XX     X   XXXX X    XXXXX
                          XXX    XX  XX  XXX   XX   X
                         XX X   XXX XXX XX X  XXX  XX
                        XXXXX  XX XXX XXXXXX XX X XXX
                       XX   X XXXXX XXX    XXXXXXXX X
                      XXX  XXXX   XXX X   XX      XXX
                     XX X XX  X  XX XXX  XXX     XX X
10 cyles later ->   XXXXXXXX XX XXXXX X XX X    XXXXX


Picture

IO

#InputOutputBidirectional
0write cell 0 stateread cell 0 state/WE, inverted write enable
1write cell 1 stateread cell 1 state/HALT, inverted halt automata
2write cell 2 stateread cell 2 stateADDR#, cell block address bit 0
3write cell 3 stateread cell 3 stateADDR#, cell block address bit 1
4write cell 4 stateread cell 4 stateADDR#, cell block address bit 2
5write cell 5 stateread cell 5 stateADDR#, cell block address bit 3
6write cell 6 stateread cell 6 stateADDR#, cell block address bit 4
7write cell 7 stateread cell 7 state

Chip location

Controller Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux tt_um_chip_rom (Chip ROM) tt_um_factory_test (TinyTapeout 05 Factory Test) tt_um_loopback (TinyTapeout 05 Loopback Test Module) tt_um_Leaky_Integrate_Fire_nfjesifb (Leaky Integrate and Fire Neuron Model) tt_um_topModuleKA (Time Multiplexed Neuron Ckt) tt_um_sap_1 (SAP-1 Computer) tt_um_lif (Leaky Integrate-and-Fire Neuron (Verilog Demo)) tt_um_jleugeri_ticktocktokens (TickTockTokens) tt_um_LSNN (Spiking LSTM Network) tt_um_if (Integrate-and-Fire Neuron. (Verilog Demo)) tt_um_mihailocode_neural_network (Neural network on chip) tt_um_hls_lfi (Simple Leaky Integrate and Fire (LIF) Neuron) tt_um_diadatp_spigot_e (e Spigot) tt_um_kskyou (Continued Fraction Calculator) tt_um_wokwi_380005495431181313 (Water Pump Controller) tt_um_EventFilter (Event Denoising Circuit) tt_um_wokwi_380416099936681985 (7 segment seconds (Verilog Demo)) tt_um_freq_hcohensa (Frequency Encoder/Decoder) tt_um_wokwi_380410498092232705 (UART Greeter with RNN Module) tt_um_wokwi_380120751165092865 (WS2812B LED strip driver) tt_um_wokwi_380408486941145089 (Tiny Tapeout 5 Workshop) tt_um_wokwi_380409169798008833 (Tiny Tapeout 1) tt_um_wokwi_380409488188706817 (Supercon Workshop) tt_um_matrix_multiplier (Matrix Multiplier) tt_um_wokwi_380408594272345089 (Clock Divider) tt_um_wokwi_380408784463076353 (Binary Counter) tt_um_wokwi_380408396356749313 (ring osc test) tt_um_7segx4_clock_abhishek_top (7 segment clock with 4 digits) tt_um_wokwi_380409481852161025 (test001) tt_um_hodgkin_huxley (Hodgkin-Huxley Chip Design) tt_um_wokwi_380408823952452609 (Character Selector) tt_um_wokwi_380409904919056385 (Intructouction to PRBS) tt_um_wokwi_380409081067502593 (tto5 Supercon Project) tt_um_jmadden173_delta_modulation (Delta Modulation Spike Encoding) tt_um_wokwi_380409086743445505 (GameOfLife) tt_um_reflex_game (Reflex Game) tt_um_wokwi_380409019830656001 (Logic Gates Tapeout) tt_um_Fiona_CMU (Stream Cipher w/ LSR) tt_um_wokwi_380409532780455937 (tt5modifyd) tt_um_alu_chip (ALU Chip) tt_um_wokwi_380408936929183745 (Tapeout Test) tt_um_rjmorgan11_calculator_chip (Calculator chip) tt_um_wokwi_380409369220404225 (Shifty Snakey) tt_um_synth_GyanepsaaS (Synth) tt_um_wokwi_380408774591779841 (Sawtooth Generator) tt_um_wokwi_380197591775930369 (Blinking A) tt_um_wokwi_380409393770716161 (Supercon 2023) tt_um_mvm (Sparsity Aware Matrix Vector Multiplication) tt_um_wokwi_380408455148316673 (Ring Oscillator and Clock Source Switch) tt_um_mv_mult_alrdelcr (Matrix Vector Multiplication (Verilog Demo)) tt_um_wokwi_380416361853146113 (IDK WHAT TO DO) tt_um_wokwi_379319062779062273 (7-segment display logic system ) tt_um_wokwi_380409568391147521 (Hardware Trojan Example) tt_um_wokwi_379824923824476161 (Analog Clock) tt_um_wokwi_380145600224164865 (7 segment display) tt_um_wokwi_379889284755158017 (W_Li_10/28) tt_um_wokwi_380408409844584449 (Supecon Gate Play) tt_um_manjushettar (ECE 183 - Integrate and Fire Network Chip Design) tt_um_wokwi_380409236812508161 (tto5) tt_um_rebel2_balanced_ternary_ALU (REBEL-2 Balanced Ternary ALU) tt_um_wokwi_380229599886002177 (Stochastic Multiplier) tt_um_jeffdi_seven_segment_seconds (7 segment seconds - count down) tt_um_wokwi_380416616536542209 (TT05 Submission) tt_um_lif_n (Leaky Integrate-and-Fire Neuron) tt_um_wokwi_379764885531576321 (Count via LFSR) tt_um_dlmiles_tt05_i2c_bert (I2C BERT) tt_um_loopback_ericsmi (tt05-loopback tile with input skew measurement) tt_um_flappy_vga_cutout1 (Flappy VGA) tt_um_async_proc_paulschulz (Asynchronous Parallel Processor Demonstrator) tt_um_wokwi_380055891603379201 (Hex Countdown) tt_um_nickjhay_processor (Matrix multiply coprocessor (8x8 1bit)) tt_um_htfab_cell_tester (Standard cell generator and tester) tt_um_wta (Winner-Take-All Network (Verilog Demo)) tt_um_muncherkin_lioncage (Lion cage) tt_um_seven_segment_seconds_ksandov4 (Brain Inspired Random Dropout Circuit) tt_um_seanvenadas (Event-Based Denoising Circuit) tt_um_wokwi_378231665807713281 (RAM cell test) tt_um_rejunity_ay8913 (Classic 8-bit era Programmable Sound Generator AY-3-8913) tt_um_rnn (RNN (Demo)) tt_um_gharenthi_top (STDP Neuron) tt_um_SNN (Basic Spiking Neural Network) tt_um_btflv_8bit_fp_adder (8 bit floating point adder) tt_um_perceptron (Perceptron Hardcoded) tt_um_jkprz (Cheap and quick STDP) tt_um_topLevel_derekabarca (Brain-Inspired Oscillatory Network) tt_um_uwuifier (UART uwuifier) tt_um_perceptron_connorguzi (Perceptron and basic binary neural network) tt_um_hadirkhan10_lif_neuron (Leaky Integrate-and-Fire Neuron) tt_um_wokwi_380119282165535745 (7 segment seconds) tt_um_uabc_electronica_2023 (UABC-ELECTRONICA) tt_um_proppy_bytebeat (bytebeat) tt_um_meriac_play_tune (Super Mario Tune on A Piezo Speaker) tt_um_wrapper_inputblackboxoutput (Byte Computer) tt_um_vhdl_seven_segment_seconds (7 segment seconds (VHDL Demo)) tt_um_cejmu (4-Bit ALU) tt_um_rejunity_sn76489 (Classic 8-bit era Programmable Sound Generator SN76489) tt_um_minipit_stevej (Miniature Programmable Interrupt Timer) tt_um_gchenfc_seven_segment_gerry (7-segment Name Display) tt_um_supertails_tetris (Tetris) tt_um_mabhari_seven_segment_seconds (Simple_Timer-MBA) tt_um_njzhu_uart (UART Receiver) tt_um_wokwi_376553022662786049 (AGL CorticoNeuro-1) tt_um_adaptive_lif (Leaky-Integrated Fire Neuron) tt_um_myuart (MyUART) tt_um_wokwi_380438365946734593 (UART test) tt_um_tkmheart (Heart Rhythm Analyzer) tt_um_stdp (Spike-timing dependent plasticity (Verilog Demo)) tt_um_wokwi_380465686251921409 (Tiny Tapeout 5 TM project1) tt_um_thermocouple (Thermocouple-to-temperature converter (digital backend)) tt_um_wokwi_380412382001715201 (Naive 8-bit Binary Counter) tt_um_asinghani_tinyscanchain_tt05 (tinyscanchain Test Design) tt_um_carlosgs99_cro_udg (6 digit chronometer.) tt_um_suhrojo (Convolutional Network Circuit Chip Design) tt_um_mvm_ (Matrix Vector Multiplication Accelerator) tt_um_perceptron_neuromeme (Perceptron (Neuromeme)) tt_um_czlucius_alu (4 Bit ALU) tt_um_BNNNeuron (Binary Neural Network (Verilog Demo)) tt_um_urish_skullfet (SkullFET) tt_um_ja1tye_sound_generator (Wavetable Sound Generator) tt_um_jaylennee_wta_pwm (PWM signal generation with Winner-Take-All selection) tt_um_joerdsonsilva_top (Multimode Modem) tt_um_toivoh_synth (Analog emulation monosynth) tt_um_tiny_game_of_life (Tiny Game of Life) tt_um_mingkaic1_stack_machine (Stack Machine) tt_um_morningjava_top (ChipTune) tt_um_urish_silife (Game of Life 8x8 (siLife)) tt_um_tt05_analog_test (TT05 Analog Testmacro (Ringo, DAC)) tt_um_wokwi_380409528895479809 (RBUART) tt_um_mattngaw_fp8 (8-bit Floating-Point Adder) tt_um_chip_inventor_music__6_bit_count (6 bit Counter and Piano Music created by Chip Inventor) tt_um_4_bit_pipeline_multiplier (4 Bit Pipelined Multiplier) tt_um_wokwi_380477805171811329 (2-Bit ALU + Dice) tt_um_wokwi_380490286828784641 (TT02 Wokwi 7seg remake) tt_um_wokwi_380361576213660673 (ping pong asic) tt_um_prg (A Boolean function based pseudo random number generator (PRNG)) tt_um_digital_clock_sellicott (Digital Desk Clock) tt_um_haozhezhu_top (4-bit FIFO/LIFO) tt_um_top_mole99 (One Sprite Pony) tt_um_GrayCounter_ariz207 (4 bit Sync Gray Code Counter) tt_um_clkdiv (Clock and Random Number Gen) tt_um_matt_divider_test (TT05 Analog Test) tt_um_tomkeddie_a (VGA Experiments) tt_um_rejunity_rule110 (Rule110 cell automata) tt_um_no_time_for_squares_tommythorn (No Time for Squares) tt_um_urish_silife_max (Game of Life 8x32 (siLife)) tt_um_gfg_development_tros (TROS) tt_um_chatgpt_snn_mtomlin5 (ChatGPT designed Spiking Neural Network) tt_um_ks_pyamnihc (Karplus-Strong String Synthesis) tt_um_dinogame (VGA Dino Game) tt_um_himanshu5_prog_chipTop (Dual Compute Unit) tt_um_rtfb_collatz (Collatz conjecture brute-forcer) tt_um_retospect_neurochip (Field Programmable Neural Array) tt_um_urish_dffram (DFFRAM Example (128 bytes)) tt_um_rejunity_snn (Chonky SNN) tt_um_hh (Hodgkin-Huxley Neuron) tt_um_wokwi_377426511818305537 (PRBS Generator) tt_um_devinatkin_stopwatch (Stop Watch) tt_um_algofoogle_vga_spi_rom (vga_spi_rom) tt_um_blink (RO and counter) tt_um_ttl74hc595_v2 (8-Bit Shift Register with Output Latches 74HC595) tt_um_psychogenic_neptuneproportional (Neptune guitar tuner (proportional window, version b, debug output on bidir pins, larger set of frequencies)) tt_um_urish_simon (Simon Says game) tt_um_kianV_rv32ima_uLinux_SoC (KianV uLinux SoC) tt_um_urish_ringosc_cnt (Ring oscillator with counter) tt_um_sunaofurukawa_cpu_8bit (cpu_8bit) tt_um_vga_clock (VGA clock) tt_um_seven_segment_seconds (7 segment seconds (Verilog Demo)) tt_um_frequency_counter (Frequency counter) tt_um_rgb_mixer (RGB Mixer) tt_um_MichaelBell_spi_peri (SPI Peripheral) tt_um_multiplexed_clock (Multiplexed clock) tt_um_psychogenic_shaman (Shaman: SHA-256 hasher) tt_um_yubex_metastability_experiment (metastability experiment) Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available