From 71b83fc040b848c98c5065d95ecbc72b0b4f8943 Mon Sep 17 00:00:00 2001 From: Hans-Christoph Steiner Date: Thu, 17 Jan 2013 22:54:00 +0000 Subject: merging maxlib v1.5.5 from branches/pd-extended/0.43 svn path=/trunk/externals/maxlib/; revision=16897 --- automata.txt | 178 ----------------------------------------------------------- 1 file changed, 178 deletions(-) delete mode 100644 automata.txt (limited to 'automata.txt') diff --git a/automata.txt b/automata.txt deleted file mode 100644 index 3f5ff21..0000000 --- a/automata.txt +++ /dev/null @@ -1,178 +0,0 @@ -[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) - -- cgit v1.2.1