[The following note originally appeared on the emusic-l mailing list. It is reprinted here with the author's permission] From xrjdm@FARSIDE.GSFC.NASA.GOV Wed Nov 23 11:26:39 1994 Date: Tue, 4 Oct 1994 15:09:23 -0500 From: Joe McMahon Reply to: Electronic Music Discussion List To: Multiple recipients of list EMUSIC-L Subject: Automata: the long-awaited summary Back in August, I think, I promised to post a quick intro to cellular automata and how they can be used as a sound-generation tool. Since I'm going to take a couple of different sources and sum them up with little or no direct attribution, combined with my own opinions, I'll give everybody my references *first* so they can delete the article and draw their own conclusions if they so prefer. The primary reference that got me started on all this is one in the CMJ: Vol 14, No. 4, Winter 1990: "Digital Synthesis of Self-modifying Waveforms by Means of Cellular Automata" (Jacques Chareyon). Those who are already familiar with automata may just skip to that article and forget about the rest of this one. Note: the article gives a mail address for M. Chareyon, but he did not answer an inquiry about any available recordings using this technique in 1990. So. Anyone still here? Good. Cellular automata are a mathematical concept first introduced in the late 1940's. Generally speaking, a cellular automaton consists of a grid of cells. Each cell may take on any of a number of values - binary automata (cell on or cell off) are the most commonly studied. Each cell has a neighborhood, defined more simply as other cells which influence its state. The exact nature of this influence is defined by what are called transition rules. The cellular automaton starts off with some cells in any of the allowable states. for each "step" in the automaton's history, the neighborhood of every cell is checked, and the state of the cell is updated. All updates occur simultaneously. The transition rule must describe the resulting state of a cell for every possible configuration of other cells in the neighborhood. For large numbers of states, the amount of memory required to hold the transition rule becomes increasingly large, Therefore, some automata use what is known as a "totalistic" rule. These rules simply sum the values of the cells in the neighborhood and then assign a result on this basis. The resulting tables are far smaller. Many readers may already be familiar with John Horton Conway's game of "Life". This is a two-dimensional binary automaton with a totalistic rule. This makes for a very small rule set: i) If fewer than two filled cells (cells with value 1) surround a cell, it becomes empty next generation. ii) If more than three filled cells surround a cell, it becomes empty next generation. iii) If exactly three cells filled cells surround a cell, it becomes filled on the next generation. This corresponds to a totalistic rule set with a total of 8(2-1)+1 or 9 rules (one each for the sum values of 0 (no cells with a value) through 9 (all cells with a value) ).If the transition rule were represented as a non-totalistic one, the rule set would need 2**8 or 256 entries. There are many interesting totalistic automata, so giving up detailed description of every nuance of the transitions to save memory space isn't a big sacrifice. Interesting as two dimensional automata are, they really aren't terribly useful for music making. There have been some experiments which have attempted to use a two-dimensional automaton to generate MIDI events - synthesis at the note level, using : Battista, T. and M. Giri, 1988. "Composizione Tramite Automi Cellulari." Atti del VII Cooloquio di Informatica Musicale. Rome, Italy: Edizione Arti Grafiche Ambrosini, pp. 181-182. Edgar, R. and J. Ryan, 1986. "LINA" Exhibition of the 1986 International Computer Music Conference, San Francisco: Computer Music Association. I have not heard any of the music from these efforts, so I certainly can't pass any judgement on them. For the purposes of this summary, we'll just look at one-dimensional automata. These use a linear array of cells, with the neighborhood generally being one or two cells on either side of each cell. (This is the type of automaton dealt with in M. Chareyon's article, which I will be paraphrasing broadly hereafter). M. Chareyon's automata are wavetables. A digitized signal is stored as a linear array of numbers in memory. A totalistic rule is used to determine a lookup value which indexes into an array containing the resulting value; this is saved into a second array. After the first array is completely processed, the roles of the two are swapped and the process is repeated. The limiting factor in this process is the number of bits of resolution being used to generate the sound. For a totalistic rule using a two-cell neighborhood and 12-bit individual samples, we have 3*(2*12) = 12288 entries in the rule table. At 2 bytes each, this is 24K of storage. If we go to 16-bit sample resolution, we have 196608 entries at 2 bytes each for a total of 393216 bytes, or 384K. The key point of M. Charyeon's method is the use of small neighborhoods with large numbers of cellular states. Since the computation of the new wavetable is all table lookup, very complex transition rules can be precomputed and loaded into the tables, allowing the synthesis to essentially be a fast sum-and-lookup loop to calculate each new wavesample. >From the article, it appears that M. Chareyon was able to produce 2 or 3 voices in realtime on a Mac II with a Digidesign Sound Accelerator board. It seems that it would probably be possible to use an AV Mac to do it without the board. This LASy (Linear Automaton Synthesis) method is closely related to the Karplus-Strong plucked-string algorithm, in that a wavesample is run through an algorithm which recirculates the samples to "self-modify" the wave. In fact, a judicious choice of table entries allows one to very simply simulate the K-S algoritm directly. So what are the sounds like? Some automata produce waveforms which quickly "ramp-up" to complex spectra and then drop off quickly. Others move to a steady state and then remain there. Yet others produce never-ending and unpredictable waveforms, whose harmonic content is constantly changing. Obviously enough, the original wavesample can be obtained mathematically, or by actual sampling and using LASy as a waveshaper. As M. Chareyon notes, a quick estimate of the number of possible automata for a 2-neighbor totalistic rule using a 256-entry wavetable with 12-bit entries is (2**12)**256 * (2**12)**(3*2**12) or about 10**4500 possible automata. Of course, many, many of these would not be suitable for music (e.g., the 4096 automata in which all values go to one vlaue in one step, etc.); however, the number of musically useful automata is still likely to be an immense number. M. Chareyon provides a number of examples of ways to fill out the rule tables and a number of hints on creating wave tables - generally speaking, one can create a function which is used to compute the values to be placed into the table and then fill it so it can simply be loaded and used by the basic algorithm. His experience in using LASy is that he manages approximately 50% of the time to produce sounds with the desired characteristics, and that about 10% of the remaining time he gets unexpected but useful results which can be used as starting points for further exploration. Again, the important point is that the basic automaton uses wavesamples at full resolution, calculating a new wavesample for each step of the automaton; the next wavesample can be played while the new one is being calculated. Because of the large number of states, mathematical tools for the analysis of automata and the construction of automata with specifically desired qualities require too much storage and compute time to make them useful for LASy purposes. Again, much of this article is paraphrased from M. Chareyon's article; I take no credit for any of the work in this note. I'm just summarizing. The following other articles were referenced by M. Chareyon's article: Burks, A., ed. 1970. Essays on Cellular Automata. Champaign/Urbana, IL: University of Illinois Press. Chareyon, J. 1988a. "Sound Synthesis and Processing by Means of Linear Cellular Automata." Proceedings of the 1988 Internation Computer Music Conference. San Francisco: Computer Music Association. Chareyon, J. 1988b. "Wavetable come Automa Cellulare: una Nuova Tecnica di Sintesi." Atti del VII Colloquio di Informatica Musicale, Rome, Italy: Edizioni Arti Grafiche Ambrosini, pp. 174-177. Farmer, D., T. Toffoli, and S. Wolfram, eds. 1984. Cellular Automata. North-Holland Physics Publishing. [One of the definitive works on cellular automata - fairly heavy math, not a popular presentation - JM] Gardner, M. 1970. "The Fantastic Combinations of John Conway's New Solitare Game 'Life'". Scientific American 223(4) 120-123. [A good introduction to cellular automata, focusing on 'life' in specific. Useful intro if my 1-paragraph summary of automata was confusing :) - JM] --- Joe M. -- "At the end of the hour, we'll have information on the sedatives used by the artists,,," (MST3K)