1-Dimensional Cellular Automata

The FIRST project on Altera DE2 educational board.

In this exerice a binary, nearest-neighbor, one-dimensional cellular automata (CA) is developed and displayed on VGA monitor. A state machine is designed to read various user fed inputs, compute the CA and store the same in the VGA buffer. The VGA buffer is stored in the internal M4K blocks. The VGA buffer is then read simultaneously and displayed on the VGA screen.

The state of the cellular automata is displayed along the X axis of the VGA screen. Each new generations of the CA are calculated and displayed on the next row. Thus, time is represented in the Y-axis of the VGA screen.

The state machine is implemented in the hardware by Verilog hardware description language and ported to Altera DE2 board. The Altera DE2 board is a development and education board built with the Altera Cyclone II 2C35 FPGA and it offers interfaces to various peripherals such as VGA, Ethernet, Audio, memory etc. that can be used to build various applications.

RTL Description and State Machine

The RTL schematics of the whole system is shown in Figure below.

1D CA_DE2 TOP module

Top Module RTL schematics

 

This schematic is generated from the Quartus II RTL viewer. As can be seen from the RTL schematics, the major components in the hardware design of the 1Dimensional Cellular automata are as mentioned below.

  1. Reset_Delay
  2. VGA_Audio_PLL
  3. VGA Buffer
  4. VGA Controller

The detailed functionality for each of these modules are described in the Design section. Once all the hardware is interfaced, the 1D cellular automata generation and the display of the same on the VGA controller is guided by the state machine. The state machine initializes all the VGA buffer and then calculates the cellular automata and displays the same on the VGA. The complete state machine designed for this purpose is shown below. This state machine is also generated by the Quartus II software based on the hardware description language code written for this lab.

1D CA_DE2 TOP state

State Diagam

 

Design

In this section, the design of the whole 1 dimensional cellular automata system is described along with the various testing methods for each modules in the design.

Hardware Design:

The block diagram for the system is shown below.

1D CA_Block Diagram

Block diagram

 

The hardware for the system Cellular automata system was developed incrementally. The incremental steps in this system design is described below.

Reset Delay:

The first step in this design process was to develop a module that generate the required delay for the VGA controller. This module is used in most of the VGA related applications.

VGA Audio PLL:

The VGA H_Sync uses a 25.175MHz clock. Since there was no on-board clock source for this required frequency, the VGA Audio PLL module was designed to generate this required clock frequency. The VGA Audio PLL takes the 27 MHz onboard clock as input and generates the 25.2MHz clock which is used by the H_Sync on the VGA controller. The VGA Audio PLL module was generated using the megawizard tool within Quartus II software. Since the modules generated using mega wizard are well designed and tested, it did not require any further testing.

VGA Buffer:

The system requires a memory to store the VGA screen memory. Similar to the above PLL file, this memory was also designed by the Mega Wizard utility and did not require any testing. However, the easiest way to test it would be to load an image using a .mif file and displaying the same on the VGA screen.

The VGA buffer takes 19 bit address. The most significant 10 bits will be for the X_position and the least significant 9 bits for the Y_position of the VGA. 10 bits are required to address to 640 pixels within the row and 9 bits are required to address 480 rows.

VGA Controller:

The last module in the system hardware design was the VGA controller. The VGA controller performs various sub tasks mentioned below.

  • Pixel Look Up Table Address generator
  • Cursor generator
  • H_Sync generator
  • V_Sync generator

The complete RTL schematic of the VGA controller is shown below.

VGA Controller module

VGA Controller module

State Machine:

Once all the hardware is designed for the system, the system logic to calculate the CA and to display the same on the VGA screen is implemented by means of the state machine. The design of the state machine is implemented in the incremental approach implementing the design for one requirement at a time.

Reset for the state machine:

The system enters the state machine when reset. The reset is provided by means of pressing the Push button Key0. One of the requirements of the system is that the CA rule should not be changed during the any other time but for reset. Thus the CA rule is read from Switches SW[7:0] and latched during the reset. To make sure that the switches are latched only during the reset, the system was tested by changing the switches positions once the CA generation started. As expected, changing the switches position did not change the CA rule that was latched during reset and the same rule was employed for further frames of CA without reset.

Initial State for the CA:

During the reset, the initial state of the cellular automata is defined by means of the Switch SW17. If the switch is in high position, the initial state of the CA is defined to have a single white dot in the center of the row. To display a white dot in the center of the row, the state machine is initialized to state “init0”.  In this state, the address is set to the middle pixel of the first row and the data bit is set to 1 to put a white dot. In the next cycle, the systems transitions to state “init1”. In this state, the VGA buffer is enabled to write the white dot in the middle of the row as set during the “init0” state.

On the other hand, if SW17 is in low position during the reset, the initial state of the system will be random. To initialize the system with random data, the initial value of the Linear Feedback Shift Register (LFSR) is set to the output of the 32 bit counter value during the reset. Then, in the next cycle, the state machine is initialized to state “rand0”. In this state, X_position and Y_position are combined to form the address to set the address to the pixels in the first row and with the data bit set to the output of the LFSR. In the next cycle, the system transitions to state”rand1”. In this state, the VGA buffer is enabled to write the values set for the address and data registers during rand0 state and then increments the X_position of the first row. Then it loops back to “rand0” state. The process is continued until all pixels of the first row are set with the random data.

This initial state of the CA was tested for both positions of the SW17 and by visually testing for the single white dot in the center or random initial state appropriately.

Generating CA for next generation:

Once the initial state of the CA is set either for random state or to the single point, the system enters “init2” state. For here onwards, the system should calculate the next generation of the CA based on the three neighboring pixels of the previous generation. Thus, to compute the CA, the state machine first reads the three neighboring pixels. To read these pixels, the state machine traverses from “init2” state through “read0”, “read1”, “read2” and “read3” states. In each of these states, the address register is set to the next neighbor to read the bit.

Once all three neighbors are read, the state machine transitions from “read3” state to “ca” state. In the “ca” state, the cellular automata is calculated based on the neighbors thus read. In the next cycle, the system transitions to the “write0” state where it assigns the CA thus computed to data register and sets the address register accordingly. In the next cycles, the systems moves traverses through “write1” and “write2” states to write the CA to the VGA buffer.

Once, the CA for the next generation is written back to the VGA buffer, it transitions to “new_walker”. In this state, if the VGA screen is not completely filled, the X-position and Y_position are updated appropriately to point to the next pixel and loops back to the “init2” state. Otherwise, upon filling the whole VGA screen, it moves to “new_frame” state where the system waits for the user input to generate the next frame.

While calculating the CA for the next generation, since the first and the last columns have only two neighbors these columns are always set to zero and CA is calculated for the remaining intermediate columns.

These block of state machine was tested by visually looking at the VGA screen for the required CA pattern.

Next Frame generation using Key3 press:

Another requirement from the systems is that once the whole VGA screen is filled with the CA pattern the system should wait for the user input to generate the new frame of the CA. While generating the new frame, the last row of the previous frame should be copied over to the first row of the next frame and then the whole VGA screen should be filled as usual.

Once the whole VGA screen is filled with the cellular automata patterns, the system enters the state “new_frame” in which it waits for the user input to generate the next frame. The user can provide the signal to generate the next frame by pressing the Push button Key3. To make sure that only one frame is generated per key press, the key needs to be debounced. As soon as the user presses Key3, the system transitions to state “debounce” where it waits until the Key3 is released. Once the Key3 is released, the system switches to state “copy0” where it initializes the VGA address to the last row pixels and moves to “copy1” state. In copy1 state, the VGA buffer is read for the address provided and moves to the “copy2” state. In this state, the data bit read from the VGA buffer in the previous state is assigned to the data register and the address register is pointed to the corresponding pixel in the first row. In the next cycle, the state machine transitions to the “copy3” state where the VGA buffer is enabled to write the data bit set at the address pointed by the address register. It then increments the X_position of the VGA screen and loops back to “copy0” state to copy the next pixel. The process repeats until all the pixels from the last row is copied to the first row and then transitions to “init2” state to compute further generations of the cellular automata.

The new frame generation was tested by making sure that exactly one frame was generated after clicking on Key3 once the VGA screen was filled.

Results

In this section, the various results for various user selections are shown. The results are obtained for various CA rules. For each rule, the CA pattern is determined for known definite single dot in the center and the random initial state of the CA system. For each of these initial states, two frames are captured, one after reset and another after the Push Button Key 3 press. These pictures are taken for Rules 30 and 60 as shown below.

 

 

Advertisements
Categories: Embedded Systems Design | Tags: , , , | Leave a comment

Post navigation

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: