Subversion Repositories ca_prng

#=======================================================================

#

# ca_prng_description.txt

# -----------------------

# README file for the ca_prng IP-core. The file

# contains a brief introduction to cellular automata based pattern

# generation, a description of the core and how to use the core.

#

#

# Author: Joachim Strömbergson

# Copyright (c) 2008, InformAsic AB

# All rights reserved.

#

# Redistribution and use in source and binary forms, with or without

# modification, are permitted provided that the following conditions

# are met:

#     * Redistributions of source code must retain the above copyright

#       notice, this list of conditions and the following disclaimer.

#

#     * Redistributions in binary form must reproduce the above

#       copyright notice, this list of conditions and the following

#       disclaimer in the documentation and/or other materials

#       provided with the distribution.

#

# THIS SOFTWARE IS PROVIDED BY InformAsic AB ''AS IS'' AND ANY EXPRESS

# OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED

# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

# ARE DISCLAIMED. IN NO EVENT SHALL InformAsic AB BE LIABLE FOR ANY

# DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL

# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE

# GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,

# WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING

# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS

# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#

#=======================================================================

1: Introduction

---------------

A cellular automata CA) is a discrete model that consists of a grid (1D,

2D, 3D ) with objects called cells. Each cell can be in one of a given

set of states (on and off, different colours etc). Each cell has a set

of cells in close proximity. Given the current internal state of a cell,

the states of the cells in the close proximity and a given set of update

rules the next state of a cell can be determined. For more information

about cellular automata, se [1].

The ca_prng IP-core implements a 1D binary cellular automata with wrap

around at the edges (i.e. a ring). The update rules for a given

cell is based on the current state of the cell and the state of its

two nearest neighbours (left and right). The cell state for a given cell

(i), stored in the ca_state_reg register array can thus be given by

the state in cells (i-1), (i) and (i+1) as inputs to the update rule, se

figure 1.

                    ---------------------

    ca_state_reg:   |...|i-1| i |i+1|...|

                    ---------------------

                          \   |   /

                        (update_rule)

                              |

                    ---------------------

    ca_state_new:   |...|i-1| i |i+1|...|

                    ---------------------

  Figure 1: State update for a cell (i) based on neighbour cells

            and the update rule.

With a three input, binary state the update rule set consists of eight

possible bit updates. In total the ca_prng supports 256 update

rules. For different rules and possible patterns, see [2].

The default update rule used in the ca_prng is rule30. Rule30 is an

uodate rule that when applied to the CA will produce a class III,

aperiodic, chaotic behaviour. The rule was discovered by Stephen Wolfram

[3].

2: IP-core description

----------------------

The ca_prng is a CA with 32 cells, implemented as a 32 bit wide

register. Each register has separate update logic that looks at the

current state of the register and its two nearest neighbours (with wrap

around). Register update latency is one cycle.

The actual update of the registers is controlled by external control

signals that allows a user to set the register initial pattern

(state) and request generation of new pattern.

Loading of initial pattern is is accomplished by setting the

input_patter_data port to the desired inital pattern and then

asserting the load_input_pattern port for one clock cycle.

Requesting a new pattern is accomplished by asserting the next_pattern

port.

After reset the ca_prng will use rule30 as the update rule. Changing the

rule is done by assigning the new rule to the update_rule port and then

asserting the load_update_rule for one clock cycle.

The generated pattern is available as a 32 bit value on the prng_data

port.

Figure 2 shows input and output ports of the ca_prng core.

                          ––––––––––-

    input_pattern_data   |           |

                -------->|           |

                         |           |

     load_init_pattern   |           |

                 ------->|           |  prng_data

                         |           |-------->

          next_pattern   |           |

                -------->|           |

                         |           |

           update_rule   |  ca_prng  |

                -------->|           |

                         |           |

       load_upate_rule   |           |

                 ------->|           |

                         |           |

                         |           |

                         |           |

                   clk   |           |

                -------->|           |

                         |           |

               reset_n   |           |

                -------->|           |

                         |––––––––––-|

  Figure 2: Input and output ports of the ca_prng core.

The ca_prng core is a positive edge triggered synchronous design. All

internal registers are equipped with a synhronous, active low reset.

3: IP-core delivery contents

----------------------------

The ca_prng is provided as RTL source code written in Verilog 2001

compliant code. The ca_prng delivery also contains a testbench that

verifies the functionality. Finally the core contains a functional model

written in Python as well as documentation (this file).

The provided testbench has been used to verify the core using the

ModelSim as well as the Icarus Verilog simulators.

The ca_prng core has been implemented in FPGA tools from Altera and

Xilinx. The following table lists the area and speed achieved.

Altera Devices (implemented using Quartus 9.0)

Stratix II

---------

Device: EP2S15

ALUT:   106

Reg:    40

Mem:    0

DSP:    0

fmax:   300 MHz

Cyclone III

-----------

Device: EP3C5

LE:     234

Reg:    40

Mem:    0

Mult:   0

fmax:   250 MHz

Xilinx Devices (implemented using ISE 11.0)

Spartan 3A

----------

Device: xc3s50a-5

Slices: 93

Reg:    48 (replicated update_rule_reg)

Mem:    0

Mult:   0

fmax:   250 MHz

Virtex-5

--------

Device: xc5vlx30-3

Slices: 42

Reg:    40

Mem:    0

Mult:   0

fmax:   400 MHz

4: References

-------------

[1]     Wikipedia. Cellular Automaton. Web page. 2009.

        http://en.wikipedia.org/wiki/Cellular_automaton

[2]     Wolfram MathWorld. Elementary Cellular Automaton. Web

        page. 2009.

        http://mathworld.wolfram.com/ElementaryCellularAutomaton.html

[3]     Wikipedia. Rule 30 description. Web page. 2009.

        http://en.wikipedia.org/wiki/Rule_30

#=======================================================================

# EOF ca_prng_description.txt

#=======================================================================