WO1997012330A1 - Method and apparatus for information processing using cellular automata transform - Google Patents

Abstract

A method and apparatus for information processing including encoding and decoding data, encrypting and decrypting data, and modeling physical phenomena using a transform which is a function of input data and a basis. After the input data is received, the basis is generated from key values specifying characteristics of a cellular automata space of at least one cell and at least one rule of interaction for the at least one cell. Using the generated basis, the input data is transformed into encoded data.

Description

Description

Method and Apparatus for Information Processing

Using Cellular Automata Transform

Background ofthe Invention

The present invention relates to information processing, and, in particular, to applying a cellular automata transform to information processing While the invention is subject to a wide range of applications, it is especially suited to data encoding/decoding systems, data compression/decompression systems, image processing systems, and high speed telecommunication systems, and will be particularly described in that connection Background Art

(a. Data Compression

Many industries such as the telecommunications, multimedia, remote sensing, network and cable television, photogrammetry, computer animation, robotics, and medicine require systems that collect, analyze, store, and/or transmit huge amounts of data at high speeds Conventional systems, however, cannot maintain pace with these industries' growing data processing needs For example, the multimedia industry continuously seeks technology to store hundreds and, perhaps, thousands of megabytes of data in the limited space available on storage devices such as personal computer hard disks Similarly, the telecommunications industry strives for increased data transfer speeds Data compsression technology seeks to meet these needs Improved data compression techniques increase efficiency of existing data processing devices and reduce the cost of performing certain applications

Consider, for example, a grayscale video image signal array of 512 x 512 pixels, with 8 bits of data per pixel One image frame will contain 256 kilobytes of data Since about 30 frames/second are required for a flicker-free viewing, approximately 8 megabytes of this video signal will need to be stored or transmitted for every second of viewing Storing one minute of such a video signal will require a storage space of almost 0 5 gigabytes To transmit such a signal, in realtime, through the typical telephone line at 9600 bits per second requires a compression ratio exceeding 655 1 The requirements of a color video signal, at the same resolution, are even more severe. Thus, existing compression technologies cannot achieve high- quality compression and speed with a moderate computational overhead

The increasing need to capture efficiently, store and transmit data is fueling the search for high-performance compression systems. Conventional compression and modeling systems are, in general, either too slow to implement on a computer of moderate power or produce images of unacceptable quality Some of these conventional systems also require detailed prior knowledge ofthe input data stream for successful operation

In one type of data compression, knoen as "lossy" compression, the reconstructed data is not completely identical to the original The use of lossy compression is therefore limited to applications (e.g.. images or video) where some error can be tolerated. However, even video applications constitute major challenges for current compression technology. Existing interactive video compression hardware is expensive. Further, existing technology degrades the image quality and cannot achieve massive compression in real-time The disclosed invention is capable of achieving rates of real-time information processing and modeling.

One class of conventional lossy compression techniques uses transform coding Older methods in this class include the Walsh Transform, Hadamard Transform. Fourier Transform. Haar Transform, and the Discrete Cosine Transform More recent transform techniques include the Fractal Transform and Wavelet Transform The Discrete Cosine Transform (DCT) was selected as the standard compression technique by JPEG (Joint Photographic Expert Group) for still images; and MPEG (Motion Picture Experts Group) for video. Each of these techniques employs a transform in which input data is processed using a "basis " For example, the DCT employs the cosine function as its basis

A considerable amount of research effort has been committed towards enhancing the performance of DCT, and its implementation in hardware. DCT is typically a frame-based compression technique. Data representing a given image is broken into blocks of 64 pixels (8 * 8). A number of arithmetic operations are then performed to implement the transformation process. On a typical 8 x 8 block, DCT originally required 256 operations A refinement of DCT, known as the Generalized Chen Transform, has reduced the 256 operations to 64

The Fractal Transform was developed by Michael Barnsley and Alan Sloan (U.S. Patent No. 4,941, 193 and 5,065,447) and exploits the self-similarities inherent in most images Parts ofthe image, when translated, rotated, and scaled are used as the basic building blocks of other portions ofthe image The encoding and decoding processes are both iterative The encoding process is computationally intensive The decoding is reportedly quicker

The Wavelet Transform involves the decomposition ofthe data into a set of basis functions known as wavelets, as reported by S G Mallat in "A Theory of Multiresolution Signal Decomposition the Wavelet Representation," Comm. Pure and Appl. Math . 41 , 7, 674-693, 1988 The major drawback ofthe Wavelet Transform is the computational difficulty in generating the basis

In some applications, for example, text or database information processing, it is of vital importance that the compression be error-free Techniques achieving this result are called "lossless" compression Conventional lossless compression techniques include the Huffman Method, the Arithmetic Method, and the Dictionary Method The Huffman Method is a statistical encoder in which variable-length codes of integral numbers of bits are created Shorter codes are assigned to symbols with high probabilities More sophisticated versions ofthe original Huffman Method make use of higher-order statistics

In the Arithmetic Method, a given message is represented by an interval of real numbers between 0 and 1 The longer the message gets, the longer the interval needed to represent it

Encoders that employ the Dictionary Method use single tokens to represent symbols with variable lengths An index to a dictionary is formed using the tokens The LZW compression method is an example ofthe Dictionary Method, which extends the alphabet with additional strings used to represent strings of regular characters LZW is the compression used in the GIF file format (a standard developed by CompuServe for transmitting and storing image files), the UNIX COMPRESS program, and the compression/decompression software known as PKZIP Only modest compression ratios, usually on the order of 2 1, are achievable using these lossless data encoding techniques Higher compression ratios can be obtained from the lossy methods The major disadvantages ofthe lossy encoders generally include one or a combination ofthe following 1 ) high computational intensity, 2) a limited/small family of transform bases, 3) large encoding errors at high compression ratios The processing time, in particular, constitutes a significant barrier towards achieving routine or real-time compression in various applications

(b) Data Encryption

Data is encrypted, that is, scrambled, for security during transmission or storage. Several encryption techniques using dynamic systems have been developed in recent years

For example, in U S Patent No 5,048,086, M Bianco and D Reed taught a system that uses dynamic systems to generate pseudo-random numbers which are combined, in an XOR operation, with the plain text to form the encrypted message The seed ofthe pseudo-random number is the encryption key

S Wolfram taught the use of a particular cellular automaton, known as Rule 30. to generate pseudo-random numbers Proceedings of Crypto '85, pp 429-432 The encryption key is only the initial state ofthe cellular automaton Additionally, P Guan taught the use of an invertible dynamical system for encryption "Cellular Automata Public-Key Cryptosystems." Complex Systems 1. 1987 During the encryption phase the dynamical system is run in the forward direction Decryption involves running the inverse ofthe dynamical system on the encrypted message

J Kari has also described an encryption technique that uses reversible dynamical systems J-P, Delahaye, "Les Automates," Pour La Science, pp 126-134, 1991

Lastly, H Gutowitz described a system using irreversible dynamical systems, involving either or both forward and backward iteration, in some aspects of the encryption and decryption process U S Patent No 5.365,589

None of these conventional techniques employs a transform in which input data is encrpyted/decrypted using a basis Further, one primary limitation of these conventional cryptographic techniques is the complexity ofthe encryption and decryption processes In the implementations that use pseudo-random numbers, for example, the quality ofthe generated numbers, as pertaining to their true randomness, cannot by fully guaranteed. The ones that use forward and backward iteration of reversible and irreversible dynamical systems involve complicated arithmetic operations As will be explained below, the present invention uses a transform that involves a huge library of cryptographic keys derived from a family of cellular automata

(c) Modeling of Phenomena

Existing art, in a form known as lattice-gas modeling, attempts to obtain models of phenomena by using cellular automata Cellular automata can be defined as dynamic systems in which space and time are discrete The cells of a cellular automata space are arranged in a lattice structure and have a finite number of states These states are updated synchronously according to specified local rules of interaction For example, a two-state, one-dimensional cellular automata space consists of a line of cells (also called "sites"), with each cell capable of taking one of two values such as "0" or " 1 " Using a specified rule the value of each cell is updated synchronously in discrete time steps The phenomena being modeled can originate from complex systems derived from physics (e g., fluid dynamics, heat conduction, deformation of solids), chemistry (e g , diffusion-controlled reactions), biology (e g , cell reproduction), or economics (e g . financial market analysis)

Consider, for example, the application of cellular automata to model physical processes The use of cellular automata as a model of a physical system has always relied on an ad hoc application ofthe dynamic rules, combined with complex statistical inferences The process of relating particular cellular automata rules to the laws governing specific physical processes is not well established A common feature of existing cellular automata models is the huge number of cells required for a typical simulation ofthe physical process For example, in the work reported by Shimomura et al , (T Shimomura, G D Doolen, B Haaslacher, and C Fu, "Calculations Using Lattice Gas Techniques," in From Cardinals to Chaos - Reflections on the Life and Legacy of Stanislaw Ulam. ed N G Cooper, Cambridge, 1989) 20 million cells were used to simulate the movement of fluids past a cylinder None of these conventional cellular automata modeling systems employs a transform in which the phenomena is modeled using a basis In contrast, the present invention teaches a more direct and highly accurate method of using a cellular automata-based transform for modeling physical processes The cellular automata transform ofthe present invention requires a much smaller array of cells, and provides a direct way of measuring the errors inherent in the use of particular cellular automata rules for a specific phenomenon The solution process is fast and does not require dedicated computers of enormous power and speed

Disclosure ofthe Invention

To overcome the limitations ofthe existing technology the present invention applies a cellular automata (CA) transform to information processing and modeling In accordance with the disclosed method, a computer receives input data, generates a CA basis from a combination of key values, and transforms the input data into encoded data using the CA basis.

Decoding of encoded data is performed by a computer that receives encoded input data, generates a C A basis from a combination of key values, and transforms the encoded data using the basis into decoded data using the CA basis

In another aspect ofthe invention, a computer implemented transform is employed to model a physical system The method of modeling of a physical system includes the steps of receiving input data describing characteristics ofthe physical system, generating a CA basis from a combination of predetermined key values, and transforming the input data using the CA basis into a model ofthe physical system described by the input data

In still another aspect, the invention includes an apparatus for information processing and modeling This apparatus includes a receiver for receiving input data and a key value, an input device, a programmed control interface, read only memory, a processing unit, a cell state random access memory, a cell coefficient random access memory, and a transmitter The transmitter transmits any key value used to generate a CA basis used to transform input data into output data This transmitter also transmits output data It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are intended to provide further explanation ofthe invention as claimed

Brief Description of Drawings

The accompanying drawings are included to provide a further understanding of the invention and are incoφorated in and constitute part of this specification These drawings illustrate several embodiments ofthe invention and together with the description serve to explain the principles ofthe invention

Fig 1 is an illustration of three-cell neighborhoods in a CA lattice,

Fig 2 is an illustration of the application of a local rule of interaction to a three-cell CA neighborhood.

Fig 3 shows the iteration of CA cell states at four time intervals,

Fig 4 is a block diagram of an apparatus for computing the CA transform according to the present invention,

Fig 5 is a flow diagram for CA encoding of data according to a preferred implementation of the present invention.

Fig 6 is an illustration of a CA key and CA key values according to the present invention,

Fig 7 is an illustration of a data string used to explain the S-bases according to the present invention.

Fig 8 is a flow chart showing the CA transform using an S-basis according to the present invention,

Fig 9 illustrates examples of 7 basis types according to the present invention,

Fig 10 is a block diagram illustrating C A transform compression and decompression of an image according to a preferred implementation ofthe present invention,

Fig 1 1 is a table showing the CA coefficients associated with the 8-bit grey scale subimages (each 8 * 8) of different portions of a digitized image of a human face,

Fig 12 is a block diagram showing data encryption and decryption using the CA transform according to a preferred implementation ofthe present invention, and Fig. 13 is a block diagram illustrating modeling of a physical system using the CA transform according to a preferred implementation ofthe present invention Best Mode for Carrying Out the Invention

Reference will now be made in detail to the present preferred embodiments of the invention, examples of which are illustrated in the accompanying drawings

Cellular automata (CA) are dynamic systems in which space and time are discrete The ceils, which are arranged in the form of a regular lattice structure, have a finite number of states These states are updated synchronously according to a specified local rule of interaction For example, a 2-state 1 -dimensional cellular automaton will consist of a set of cells (sites), each of which can take value 0 or 1 Using a specified "rule," the values for all cells are updated simultaneously in discrete time steps An example of a rule is the expression that the value of each cell at a specific time interval is equal to the sum of the values of its immediately adjacent neighbor cells at the previous time interval With a .-state automaton, each cell can take any of the integer values between 0 and k-\ In general, the rule governing the evolution ofthe cellular automaton will encompass r sites up to a finite distance away Thus, such a cellular automaton is a Estate, r-site neighborhood CA

A CA-based technology offers a favorable computational environment for compressing and decompressing data in real time The greatest advantage is that the underlying computational procedure uses Boolean computation, the natural language of computers, and thus does not devour time and computational resources by performing complicated floating point computations The computational simplicity translates into extremely fast data processing speed

Fig 1 illustrates an eleven cell lattice 100 with cells 1 lOa-k some of which are grouped in three exemplary cell "neighborhoods" 120a-c as shown by dashed lines Each neighborhood 120a-c comprises a one-dimensional CA space The state of each cell 1 1 Oa-k is given by the Boolean variable a When the state is on, a ≡ 1 , otherwise it is off and a ≡ 0 The quantity a_;, represents the state (Boolean) ofthe /-th cell, at discrete time /, and whose two neighbors are in the following states a, „ and a,.„ One of ordinary skill in the art will readily appreciate that there are many possible lattice configurations and groupings of cell neighborhoods In general, the present invention implements a rule that will be used to synchronously calculate the state a„₊, from the state ofthe cells in the neighborhood at the t-t time level. The cellular automaton evolution is expressible in equation (1): a, . , . = <y (a . ., a _, <-, .. .) (1 )

where < is a Boolean function defining the rule

There are eight possible cell values combinations for each neighborhood in a dual-state 3-site neighborhood automaton. These configurations are:

1 1 1 - C₀

1 10 - C.

101 - c₂

100 - (

01 1 - c 010 - c_s

001 - c₆ ooo - c₇ in which C„ is the Boolean value generated by the rule given the .-th configuration. There are 2ⁿ possible configurations for an n-site dual-state automaton.

Each rule for a one dimensional, dual-state. 3-site automaton, for example, the neighborhoods 120a-c, can be described by an eight-digit binary number. When specifying the rule of interaction for a CA, this binary number is used interchangeably with its decimal equivalent. There are, for example, 2* (or 256) possible distinct CA rules in one dimension with a two-state, three-site neighborhood.

Fig. 2 illustrates application of a rule (to be described below) over one time interval for a one dimensional CA The variables at each cell may take values 0 or 1 The eight possible states of three adjacent cells are given in the left hand column and constitute the configurations C₀-C₇ set forth above The right hand column gives the result of the application ofthe rule for the time evolution of the CA by giving a_j( the value to be taken by the central cell 1 lOf of the three cells at the next time interval.

If a particular rule is applied to the dual-state three-cell neighborhood value combination listed above, a set of "configurations" C„-C₁ result. For example, application ofthe rule known as the "modulo two" rule, that is, where the value of a cell at a particular time interval is the modulo two sum ofthe values of its two neighbors at the previous time interval results in the configurations shown in Fig 2 Those skilled in the art know that this CA rule can be referred to by its Wolfram notation In Wolfram notation, a CA rule number is assigned based on the decimal equivalent ofthe binary number C₀C,C₂C,C C₅C₆C₇ For example, rule number 90 is the decimal equivalent ofthe binary number 0101 1010

In general, for a -state/r-site CA, there are k ^r rules and the evolution is

Λ

expressible in equation (2) a it, - .1 = - (a i ιιι „r a i m - ,l . , I - o f int ,') n \ )_.

where m = (/' - 1 )/2 If there are N cells in the entire one-dimensional CA space, there are a total of k^κ possible initial configurations with which to start the evolution ofthe CA space Furthermore, if the CA is run over T discrete time intervals, the number of boundary (at the left and right boundaries) configurations possible is lc⁷

For certain applications ofthe present invention, boundary configurations, the assumptions dictating which cells are neighbors of cells at the edge of a CA lattice, are derived from the evolving lattice (cell states change over successive time intervals) by imposing a periodic (cyclic) condition A cyclic boundary condition means that cells on the left 1 lOd and right edges 120c of a CA lattice are considered neighbors for purposes ofthe application ofthe rule of interaction

Since there are k^{k '} rules, the number of ways we can evolve a

A-state/r-site N-cells CA over T time steps is ofthe order

k^{k '} -" -²⁷

Fig 3 illustrates the evolution of cell states over four time intervals In this example, a different rule, Wolfram rule 203, is applied to a two-state, three-site neighborhood in a four-cell lattice using cyclic boundary conditions. The first row represents the cell states in their initial configuration The second, third, and fourth rows represent cell state values after the first, second, and third application ofthe CA Wolfram rule 203, respectively.

The preferred implementation ofthe present invention uses a CA transform to encode and decode data This CA transform is specified in equation (3)

= Σ ^CL , (3)

The function f is defined in a physical space of lattice grid i using basis A and associated transform coefficients c The variable k is an index that refers to the CA space of a lattice grid The elements A^ of basis A are generated from the states ofthe CA cells a^ Each element A^ is generated according to specified characteristics described below

Equation (3) represents a mapping ofthe function f (in the physical domain) into c (in the CA space) using the basis A to define the mapping A strength of this invention is the huge number and varied nature ofthe basis that can be generated The basis A comprises the building blocks used to construct the function f The building blocks possess a plurality of shapes, which will be explained further below The coefficients c measure the size of each basis required to reconstruct f Thus, in equation (3). f represents, for example, data, c represents an encoded version ofthe same data (e.g , compressed data), and basis A represents the function used to encode the data The manner in which the present invention implements this transform will be explained in greater detail below CA Transform Apparatus

Fig 4 is a block diagram of a preferred CA transform apparatus 400 in which the CA transform represented by equation (3) may be implemented Other apparatus types, for example, general purpose computers, may be used to implement the CA transform represented by equation (3)

Apparatus 400 is comprised of a receiver 402, an input device 405, a programmed control interface 404, control read only memory ("ROM") 408, control random access memory ("RAM") 406, process parameter memory 410, processing unit PU 416, cell state RAM 414, coefficient RAM 420, disk storage 422, and transmitter 424. Receiver 402 receives data from a transmitting data source for realtime (or batch) processing of information such as satellite imagery. Alternatively, data awaiting processing by the present invention (e.g., archived images) are stored in disk storage 422.

The present invention preferably performs information processing according to programmed control instructions stored in control ROM 408 and/or control RAM 406 Information processing steps that are not fully specified by instructions loaded into control ROM 408 may be dynamically specified by a user using an input device 405 such as a keyboard In place of, or in order to supplement direct user control of programmed control instructions, a programmed control interface 404 provides a means to load additional instructions into control RAM 406 Process parameters received from input device 405 and programmed control interface 404 that are needed for the execution ofthe programmed control instructions are stored in process parameter memory 410 In addition, key values needed to compute a CA transform and any default process parameters can be preloaded into process parameter memory 410 Transmitter 424 provides a means to transmit the results of computations performed by the CA transform apparatus and process parameters used during computation.

The preferred apparatus 400 consists of at least one module 412 comprising a processing unit (PU) 418 and a cell state RAM 416. Module 412 is a physical manifestation of the CA cell In an alternate embodiment more than one cell state RAM may share a PU

The transform apparatus 400 shown in Fig 4 can be readily implemented in parallel processing computer architectures ln a parallel processing implementation, processing units and cell state RAM pairs, or clusters of processing units and cell state RAMs, are distributed to individual processors in a distributed memory multiprocessor parallel architecture General Description of Process Steps

Fig 5 is a flow diagram showing the steps common to performing information processing using the present invention First, a process type is specified (step 502) The process type indicates the specific type of applications to which the present invention will be directed It can be preprogrammed in control ROM 408, determined dynamically from user input via the user interface 404, or read from a software control program loaded into control RAM 406

There are two general categories of process types information processing and modeling When performing the first category of process types, the present invention transforms physical signals received by receiver 402 or stored in memory (disk storage 422) Examples of information processing application ofthe present invention include data compression/decompression, encryption/decryption, and image processing

The second category of process types, information modeling, encompasses all aspects of phenomena modeling/simulation These aspects include those derived from physics (e.g , fluid dynamics, deformation of solids, heat conduction, optics, acoustics, transport processes in porous media, etc ), chemistry (e g , electrochemistry, diffusion- controller reactions, chemical turbulence, kinetics, etc ), biology (e g , cell reproduction, neurology, artificial life, etc ), and economics (e g , financial market analysis, etc )

Once a process type has been determined (step 502), the relevant process parameters are entered (step 504) The process parameters may vary for each process type The process parameters, like the selection ofthe process type, can be preloaded or established dynamically

For information processing applications, such as image compression, relevant parameters are specified including the desired image fidelity, the maximum time allowed for compression, the desired compression ratio, and the uncompressed data stream or file Information modeling parameters include a system of equations and mathematical operators that define physical phenomena and physical boundary conditions A gateway key is specified either by a user or by choosing from among preloaded gateway key values stored in control memory (step 506) These gateway key values are described in detail below

Using the specified gateway key (step 506), CA transform bases are generated (step 508) The computations required to generate the CA bases are performed by the PU 416. CA transform coefficients, in the form of encoded data, are computed by the PU 416 (step 510) as well

Any computed CA transform coefficients may optionally be stored in memory 420 or transmitted via a transmitter 424 (step 512) The gateway key that was specified (step 506) and used to generate the CA transform basis (step 508) are also either stored in memory 410 or transmitted via transmitter 424 CA Transform (Gateway Kev

The preferred implementation uses a CA transform (gateway) key 600 consisting of a set of key values 602-620 illustrated in Fig 6 This key 600 contains the building blocks, or parameters, necessary to fully specify a CA transform for a particular information processing or modeling application The key values 602-620 include

Key value 1 (602) specifies a rule of interaction of the cells within a defined neighborhood, for example rule 90 (discussed above)

Key value 2 (604) specifies the number of states allowed for each cell For example, a binary cell has two states

Key value 3 (606) indicates the number of cells within each neighborhood Fig 1 illustrates several three-cell neighborhoods

Key value 4 (608) defines the total number of cells in the entire lattice Fig. 3 illustrates a four cell lattice

Key value 5 (610) defines the initial configuration of the cells The cell state initial configuration include, for example, the values of the four cells in lattice 302 of Fig 3 at time interval zero (t=0)

Key value 6 (612) defines the boundary configuration ofthe cells For many applications, a cyclic boundary configuration yields the best results Key value 7 (614) specifies the geometric structure ofthe CA lattice For example, CA lattice 302 has cells arrayed in a line segment

Key value 8 (616) specifies the dimensionality ofthe CA lattice CA lattice 302, for example, is a one-dimensional lattice

Key value 9 (618) specifies the type ofthe CA transform Representative types of CA transforms include standard orthogonal, progressive orthogonal, non- orthogonal, and self-generating transforms Each of these transform types is discussed in detail below

Key value 10 (620) specifies the CA basis type, also discussed in detail below The selection ofthe key values 602-620 governs the properties ofthe CA transform ln most applications ofthe present invention, some ofthe key values 602- 620 will be fixed (e.g , key values 3, 4, and 7) for certain classes of information processing and modeling problems One of ordinary skill in the art will be able to vary the key values to achieve optimum performance for a particular information processing and modeling application within an application class. Types of CA Transforms

Using the present invention to transform an input data sequence using a CA transform produces an encoded data sequence of CA transform coefficients Similarly, modeling a physical system using the present invention generates CA coefficients representative of the system's behavior The techniques available for generating these transform coefficients are divided into two domains orthogonal and non-orthogonal An orthogonal transform can be characterized by the way the coefficients are generated A progressive orthogonal approach or the standard orthogonal method may be used The progressive approach begins with computing the first coefficient using the entire input function The error introduced by using this single coefficient to reconstruct the original function is then determined Subsequently, the second coefficient is determined using the residual error as an input function A new error is obtained when the two coefficients are used to reconstruct the original function Next, the third coefficient is calculated using the new residual error The process is continued until the residual error is zero for all the data points If the transformation is truly ofthe orthogonal kind, there will be the same number of transform coefficients as there are data points by the time the residual error is equal to zero.

In the standard orthogonal method, the entire input function is used in determining all ofthe transform coefficients The transformation error is zero if none ofthe coefficients is quantized, that is, none have been approximated, and every coefficient is used in the reconstruction of the input data Orthogonal transformation permits the determination of transform coefficients without the need for elaborate and complex matrix inversion procedures

Non-orthogonal transforms include the self-generating CA transform. The inherent similarity that exists in different parts of a given data sequence, self-similarity, can be exploited in a compact encoding ofthe data bv using CA ^'-bases (discussed below) ln certain instances it is possible, staπing from an arbitrary or random function, to achieve an accurate reconstruction ofthe encoded data, via an iterative transformation called self-generation.

Self-generation may not be guaranteed regardless ofthe magnitude ofthe error allowed in the self-similar transformation of the data The present invention embodies two types of self-generation ( 1 ) strong self-generation and (2) weak self-generation Strong self-generation is characterized by the ability to recover encoded data using a CA transform by application of an _S^'-basιs starting from an initial arbitrary sequence. Self-generation is weak when the recovery ofthe encoded data can only be achieved from a specified initial data set ln CA transforms, the chief attraction of weak self-generation is the ease with which convergence during decoding can be guaranteed by the CA selection process in the encoding phase ofthe data processing For applications requiring weak self- generation, only CA gateway values which ensure convergence to the given data, starting from a specific initial set are used The initial set may be formed by simply assigning the same constant value for all data points Types of C A Bases

A CA basis is characterized by one (or a combination) ofthe following features.

1 The method used in calculating the bases from the evolving CA lattice. 2. The orthogonality or non-orthogonality ofthe basis

3. The window size of the bases. Windows define regions in the basis where the values are non-zero If the window size exceeds the number of cells in the lattice then the basis is non-windowed

4 The method used in calculating the transform coefficients c

Several basis classes may be used with the CA transform ofthe present invention The first class of bases is referred to as the β-class Elements in this class are comprised of the integers -1, 1 for non-windowed and -1,0, 1 for windowed

Next is the p-bases whose elements are generated from the CA cell density of the evolving CA space The CA cell density is the number of cells attaining a specified state or the number of times a given state has been attained by a specified cell Therefore, p-bases always have integer values and are suitable for lossless data encoding

A third class of bases, μ-bases, are generated from the CA cell density ofthe evolving CA space for multiple cells divided by a number corresponding to at least a subset ofthe total number of cells The μ-bases have floating point elements

S-bases. a fourth class, can be windowed or non-windowed In a windowed S- basis a subset of the basis elements is set equal to zero The transform coefficients consist of scaling parameters that connect segments of data with other segments ofthe same data Therefore, CA transformation using an S-basis can result in significant data compression when the redundancy resulting from data self-similarity is exploited

Fig 7 is a flow diagram ofthe steps for computing an S-basis CA transform using the present invention. First, a set of CA key values are randomly selected (step 640) The input data is divided into segments (642) In general, the segments may overlap The overlapping of segments will yield a greater fidelity in encoding at the expense of an increased number of parameters and increased encoding time The next step is to calculate a set of weights such that using these weights, the value of a given reconstructed data point is a weighted sum of the entire data sequence (step 644) Starting with an initial data value, CA transform the data using an S-basis and the weights computed at step 646 Next, compare the reconstructed data sequence is compared with the original data sequence (step 648) The reason for reconstructing the data during the encoding process is to ensure the repeated application ofthe S-basis CA transform will actually converge to the original data If the reconstruction error (the difference between the data sequence being encoded and the reconstructed data sequence that resulted from transformation) using the selected key is acceptable (step 650), then the computed weights comprise the S-basis, otherwise return to step 644 and calculate a new set of reconstruction weights Repeat steps 646-650 until a gateway key producing a suitable reconstruction error has been found

Consider the data string, F, shown in the upper portion ofthe Fig 8 This data string is subdivided, for example, into 4 equal segments labelled f„ f,, f,, f, In the figure, the data segment f₄, is multiplied by a scaling parameter λ₁₄ that defines a mapping from segment f, to segment f,, and the result is used as the transform coefficients for the segment f, The scaling parameter is calculated by minimizing the error involved in the S-basis CA transform using, for example, a least square error technique The functions used to link every data point on the segment f, with each point ofthe scaled data segment λ₁₄/₄ are the S-bases Similarly, the segment f₃ is generated from the scaled version of data in segment 2 (i e , λ₃₂f,) Once this association has been made, between different segments ofthe partitioned data, only the scaling parameters, and the keys used in generating the S-bases, need be stored or transmitted The original data can be reproduced, with some error (whose magnitude depends on the degree of self-similarity and self-generation) by repeated application of the S-bases transformation to the various parts ofthe data

There is an infinite number of ways by which the basis A_lk can be expressed as a function ofthe CA cell states a ≡ ,„ (i.t = 0,1,2,»^»» N-l ) Examples of these are enumerated below for a dual-state CA One of ordinary skill in the an will recognize that there are many more types of bases than the examples provided below

In several of the example basis types, there are variable parameters in some of the formulas for these bases In such cases, there are multiple sub-bases, each with unique characteristics and capable of being used solely (or in groups) as transform bases Fig 9 illustrates examples of al! 7 basis types given the CA state, a_lk

A type 1 basis falls under the β class of CA bases The CA state at cell i, at time k. is represented by a,_k The value ofthe CA basis element A, is 1 if the CA state of cell a^ is 1 (on), otherwise the corresponding CA basis element is -1, as explained in equation 4 where a^ is the state ofthe CA cell i at time / = k

^A ι = ^la, - ^l (4)

A type 2 basis is an example of a p class of CA bases The correspondence between the value of a basis element and a cell state follows Table 1 below For example, following equation 5 when cell a^ is 1 and cell a^ is 1 , the basis element A^ is 1

A_Λ = (2a_ι - 1 ) (2a_kι - 1 ) _{(5 )}

TABLE 1 : CA basis element value for type 2 bases.

C A state of a^ C A state of a^ Value of Basis Element

1 1 1

0 0 -1

1 0 -1

0 1 - 1

A type 3 basis is an example of a μ class of CA bases In a type 3 basis the value ofthe basis element A^ corresponds to the average number of cells that have a value of 1 in a specified range of cells and may be represented by equation 6

^A, = μ,Λ, (6)

Σ a

In <J

where 1 < //" < N - 2 This equation implies that there are (N - 2) different ways of generating type 3 bases

A type 4 basis are examples ofthe p class of CA bases A type 4 basis element A^ is computed using equation 7 from the density a CA cell i, at time k, multiplied by the density of a CA cell k at time i

A,_k - P,_kP (7) where /;,,, 2a_lk - l - p_A-\ and P,_v = 2a^ - 1 A type 5 basis element, like a type 4 basis, is the product of two cell densities, however, in a type 5 basis each cell density is modulated prior to multiplication Modulation, in this sense, means periodically resetting the cell density value to zero once a threshold has been exceeded Equation 8 explains the computation of type 5 basis elements

A,κ ⁼ AA, (8) where p^ = 2a, - 1 + p^-\ mod L_v and p_Λt = 2a_lk - 1 mod L_v in which -_.„ >= 2 is an integer

There are as many ways of generating a type 5 basis as are the selection of £_H A type 6 basis is another example of the p class of CA bases. In a type 6 basis the value ofthe basis element corresponds to the product of the average CA cell densities, as explained in equation 9.

A = μ_ikμ_k, (9) where μ,_k = μ_ik_, + a, σ_k and

A type 7 basis is generated by windowing the result obtained in computing a basis element value using any ofthe foregoing six basis types. Thus, a type 7 basis may be a member of either the β, μ, or p classes of CA bases. Setting basis element values to zero outside of a compact region of support is the windowing operation used to produce a type 7 basis. This is explained further below in equation 10: = δ A*_uk (10)

1 if O ≤ u <N

0 otherwise

where A * is the basis obtained using the non-windowed types such as type 3 explained above.

Type 7 bases are orthogonal for a large class of CA rules and initial boundary configurations. Those skilled in art will recognize that there are many other types of bases including, for example, two-dimensional or multi-dimensional bases. Special Characteristics of CA Bases

Non-windowed bases, especially those of two-dimensional Type 8 in the β class, provide an automatic feature extraction capability with compression. The CA coefficients for these bases exhibit a clear and distinct structure. This feature can be exploited for efficient storage and in image segmentation. For example, the table in Fig. 1 1 shows the CA coefficients associated with the 8-bit grey scale subimages (each 8 ^χ 8) of different portions of a digitized image of a human face. The selected subimages are chosen at random. The following observations have been made

1. The large coefficients in Group C, at odd-numbered rows and column locations mainly represent the texture ofthe image.

2 The coefficients in Group C₂ at the even-numbered columns are associated with the edges of the image

3 The remaining coefficients in Groups C, and C₄ provide the necessary detail to complete an error-free representation ofthe image.

By storing the running differences between the coefficients within each group, fewer bits are required to encode these coefficients. Orthogonality of Windowed Bases

Windowed bases of any class and type are orthogonal, in the progressive sense, over a plurality of CA rules, initial configuration, and boundary configurations In particular, the special configuration wherein all the initial cell states are on (or given the value 1 ), and the boundary condition is cyclic, results in progressive orthogonal bases of all types and classes with excellent data compression characteristics. Data Compression

In using CA transforms for compression, data redundancy is identified by transforming the data into the CA space The principal strength of compression using CA transforms is the large number of transform bases available The present invention preferably employs CA bases that maximize the number of transform coefficients with zero or near zero magnitudes Certain data compression applications desire a transform that always provides a predictable coefficient pattern Using bit encoders known in the art, the predictability of coefficient patterns allows such encoders to concentrate on a targeted subset of coefficients.

Therefore, CA transforms permit the selection of bases that can be adapted to the peculiarities of the data. A strength of CA compression is the Boolean character and parallel nature of the computational process involved in the calculation ofthe evolving states ofthe CA. This can translate into an enormous computational speed improvement in a well-designed encoder using a CA transform.

An implementation of the present invention for encoding of a digital image using the CA transform to perform image data compression of an exemplary image is illustrated in Fig. 10. An image file 702 with pixel value decimal equivalent 704 is passed through a CA transform ("CAT") encoder 706 A typical image pixel is encoded using an eight bit binary code Example image file 702 would require one hundred twenty-eight bits to encode the entire image without CA transform compression. The CAT encoder 706 requires key values 708 to transform the input image data. Fig 4 illustrates an apparatus 400 that is suitable for this CAT encoder The key values used for this illustration are given in Table 2. A CA space is defined by key values 708

TABLE 2: Key values for CAT image compression shown in Fig. 10.

Key Value Name Key Value

CA Rule of Interaction 203

Number of States Per Cell 2

Number of Cells Per Neighborhood 3

Number of Cells Per Lattice 4

Initial Configuration 1000

Boundary Configuration Cyclic

Cellular Space Structure Line Segment

Dimensionality of CA Space ID

Type of CA Transform Progressive Orthogonal

Type of CA Basis Type 7 (Type 6, with a window size of 2)

In this implementation, the cell space is one dimensional, a single row of four CA cells, CA lattice 710 Rule 203 for local interaction among cells is applied to neighborhoods of three cells Each cell takes on one of two possible states "on" (cell has a value of 1 ) or "off' (cell has a value of 0) Row 710 shows the CA cells in their initial configuration

Row 712 shows the CA cells after one time interval, i e , one iteration of applying rule 203 to the each cell neighborhood Rows 714 and 716 show the CA lattice after two and three iterations respectively The boundary configuration in each iteration is cyclic

The CA cell states shown in row 716 are used by CAT encoder 706 to generate a type 7 CA transform basis In this implementation, the type 7 basis is a windowed type 6 basis and is, therefore, a member ofthe p class of CA bases Using this type 6 basis, the image is encoded into CA transform coefficients 720 using a progressive orthogonal CA transform

In order to increase the amount of image compression achieved using CA transform based image encoding, the CA coefficients 720 can be quantized by quantizer 722 to produce quantized CA transform coefficients 724 The quantizer 722 applies a rounding operation CA transform image compression is further enhanced by ordering the transform coefficients using a CA transform coefficient orderer 726 so non-zero coefficients are grouped together One of ordinary skill in the art will recognize that there are other coefficient quantization and ordering techniques known in the art that would also be suitable for use as a quantizer 722 and CA transform coefficient orderer 726

The image data, now in the form of ordered CA transform encoded data 728, is further compressed by a bit encoder 730 into a compressed bit encoded binary CA transform data 732 Row 734 ofthe encoded binary CA transform data 732 indicates that the first CA transform coefficient has a decimal value of 2 (10 in binary) and a flag (binary 1 ) indicating that this CA transform coefficient is repeated Row 736 indicates that the CA coefficient value identified in the previous row, is repeated three times (1 1 in binary) Row 738 of the encoded binary file indicates that the next CA transform coefficient has a value of 0 (00 in binary) and is not repeated (flag set to binary 0) The last row 740 ofthe encoded data file shows a CA transform coefficient with a value of 1 (01 binary) that is not repeated (flag is set to binary 0) Using the CA transform to compress the example image provided in Fig 7, this entire image is encoded using twelve bits Accordingly, the using the present invention to compress the example image, greater than 10 1 compression is achieved

An image is recovered by decoding the bit encoded CA transformed data 732 Bit decoder 742 decodes the bit encoded binary CA transform data 732 to produce the quantized CA transform coefficients 744 The order ofthe coefficients 748 is restored by the inverse CA ordering unit 746 The inverse quantizer 750 restores the CA transform coefficients to their original value Note that CA transform coefficient 754 is not recovered exactly because of round-off error in coefficient quantization during image compression The CAT decoder 756, also implemented using apparatus 400 of Fig 4, uses the key values 708 specified during image compression to inverse CA transform the CA coefficients 752 to produce recovered uncompressed image 758 (pixel value representation) represented alternatively as 760 (gray level representation)

The present invention thus discloses efficient means to exploit the CA transform for information processing As it has been described, the present invention is particularly suited for digital data processing related to a wide variety of applications including but not limited to medical imaging, high definition television, video telephony, facsimile devices, digital photography, satellite communications, digital video interaction, computer data storage, wireless/cellular telephony, video transmission via telephone systems, remote sensing, data transmission in computer networks, communications via modems, digitized photocopying, video on demand, printers, image/pattern recognition, transmission of weather data, cable television transmission, teleconferencing, x-rays, magnetic resonance imaging, speech recognition, audio recording, lasers, passive transponders, and millimeter-wave radio transmission Data Encryption

For certain kinds of data archival or data transmission purposes, the encoding error must be zero One example is data encryption applications CA transform bases which are capable of lossless encoding include both windowed and non-windowed β- and _/O-types The transform coefficients have to be non-quantized integers, otherwise errors due to floating-point calculations may result during the decoding phase. In encryption applications, the focus is on data security If a message is encoded using the present invention, a code breaker must contend with searching through different key values such as rules, initial configurations, boundary configurations, window sizes, and types of CA bases The odds against code breakage increase tremendously as the number of states, cellular space, neighborhood, and dimensionality increase.

An implementation of the present invention for CA transform based data encryption is illustrated in Fig. 12. Unencrypted data 802 shown in integer format 804 is fed into CAT encoder 806. A CA transform key 808 (including key value) is selected to generate encrypted data 810 shown in integer form 812 The key values of key 808 used by the CAT encoder 806 to generate encrypted data 810 are provided in Table 3.

TABLE 3: Key values used for CAT data encryption shown in Fig. 12.

Key Value Name Key Value

CA Rule of Interaction 186

Number of States Per Cell 2

Number of Cells Per Neighborhood - -

Number of Cells Per Lattice 8

Initial Configuration 1 1 101010

Boundary Configuration Cyclic

Cellular Space Structure Line Segment

Dimensionality of CA Space ID

Type of CA Transform Progressive Orthogonal

Type of CA Basis Type 7 (Type 3, with a window size and averaging length of 8 cells) The integer representation ofthe encrypted data 812 illustrates that without knowledge ofthe key values and CAT process used to encrypt the data, the relationship between the unencrypted data 804 and the encrypted data 812 would not be apparent to an unauthorized recipient

To decrypt encrypted data 812 this encrypted data is fed into CAT decoder 814 Key 816 with identical key values to key 808 must be used by CAT decoder 814 to recover the original unencrypted data 818

The present invention thus discloses efficient means to exploit the CA transform for data encryption/decryption System Modeling

The CAT encoder ofthe present invention can also be used for modeling of physical systems (Fig 13) For example, to model the temperature distribution in a solid plate 903. parameters representative ofthe physical system 902 are specified In this example, the plate surface temperature at the left edge and lower edge are fixed at zero degrees The top edge of plate 903 has a temperature T that varies with respect to position in the horizontal direction x according to the equation T=x/(1 4+ 35x) Similarly, the temperature along the right edge of plate 903 varies according to position in the vertical direction y according to the equation T=y/( 1 2+ 55y) The thermal conductivity K of plate 903 at a location on the plate specified by the horizontal and vertical coordinate pair (x,y) is specified as K=(l + 2x+ 4y+ 15xy)^: A final parameter ofthe physical characteristics of plate 903 is the relationship between the spatial coordinates, conductivity, and temperature It is known that in physical systems such as plate 903 the divergence ofthe product of the conductivity and the gradient of the plate temperature is equal to zero, Div(K grad T)=0

Once parameters 902 of plate 903 are specified, C A key generator 906 generates keys for CAT encoder 904 The CA key generator 906 continues to generate keys and the CAT encoder 904 executes successive CA transforms until the transform performed by CAT encoder 904 produces a model consistent with physical system parameters 902 In the present invention topological key values (2, 3, 4, 6, 7, and 8) are chosen to map to the physical characteristics ofthe system being modeled and remain fixed during key generation The other key values are selected, consistent with the search for CA transform bases, A, which best represent the physical system. Once all CA keys are selected, the transform coefficients, c, are determined to ensure the satisfaction of external conditions (e.g., the temperature profile along the boundaries) imposed on the system. In this invention, the transform coefficients, c, are themselves the solution (in this example, the temperature field) to the physical system. One of ordinary skill in the art will recognize that there are other techniques available for generating an appropriate CA key.

Once an appropriate key is found, the CA transform coefficients 908 that correspond to the generated CA key represent a model of the temperature distribution 909 in plate 903 The CA key for this physical system is given in Table 4

TABLE 4 Key values used for CAT data modeling shown in Fig 13

Key Value Name Key Value

CA Rule of Interaction 36

Number of States Per Cell 2

Number of Cells Per Neighborhood 3

Number of Cells Per Lattice 8

Initial Configuration 1 1 1 1 1 1 1 1

Boundary Configuration Cyclic

Cellular Space Structure Line Segment

Dimensionality of CA Space ID

Type of CA Transform Progressive Orthogonal

Type of CA Basis Type 7 (Type 3, with a window size and averaging length of 8)

The present invention thus discloses efficient means to exploit the CA transform for information processing and modeling As it has been described, the present invention is particularly suited for image processing and modeling of physical systems Persons of ordinary skill will recognize that modifications and variations may be made to this invention without departing from the spirit and scope ofthe general inventive concept. This invention in its broader aspects is therefore not limited to the specific details or representative methods shown as described

Claims

I claim

1 A method of encoding data using a transform which is a function of input data and a basis, the method comprising the steps performed by a computer of a receiving the input data, b. generating the basis from key values specifying characteristics of a cellular automata space of at least one cell and at least one rule of interaction for the at least one cell, and c transforming the input data into encoded data using the basis

2 The method of claim 1 wherein the transforming step includes a substep of storing the encoded data

3 The method of claim 1 wherein the generating step includes a substep of evolving the at least one cell using the key values and the at least one rule of interaction

4 The method of claim 3 wherein the generated basis is one of a plurality of classes of bases, each class having a basis type and defining an element value

5 The method of claim 4 wherein the element value for a first class ofthe plurality of classes of bases is one, zero, or negative one

6 The method of claim 4 wherein the element value is a weighted sum of values in selected ones of the cells during intervals of said evolution

7 The method of claim 4 wherein the element value is an average ofthe cells having a selected value

8 The method of claim 4 wherein the element value is computed following the steps of selecting the kev value. dividing the input data into segments, calculating reconstruction weights, wherein an element of said input data is determined using the reconstruction weights from other elements of said input data, transforming an initial data value into reconstructed data using the reconstruction weights, and comparing said reconstructed data to the input data

9 The method of claim 1 wherein the input data is a digital image

10 The method of claim 1 further comprising the step of storing the key values in memory

1 1. The method of claim 1 further comprising the step of transmitting the key values to a receiver

12 The method of claim 1 further comprising the step of transmitting the encoded data to a receiver

13 A method of decoding data using a transform which is a function of input data and a basis, the method comprising the steps performed by a computer of a receiving the input data, b generating the basis from key values specifying characteristics of at least one cell and at least one rule of interaction ofthe at least one cell, and c. transforming the input data into decoded data using the basis

14 The method of claim 13 wherein the transforming step includes a substep of storing the decoded data

15 The method of claim 13 wherein the generating step includes a substep of evolving the at least one cell using the key values and the at least one rule of interaction

16 The method of claim 15 wherein the generated basis is one of a plurality of classes of bases, each class having a basis type and defining an element value

17 The method of claim 16 wherein the element value for a first class of the plurality of classes of bases is one, zero, or negative one

18 The method of claim 16 wherein the element value is a weighted sum of values in selected ones of the cells during intervals of said evolution

19 The method of claim 16 wherein the element value is an average of the cells having a selected value

20 The method of claim 16 wherein the element value is computed following the steps of selecting the key value, dividing the input data into segments, calculating reconstruction weights, wherein an element of said input data is determined using said reconstruction weights from other elements of said input data, transforming an initial data value into reconstructed data using said reconstruction weights, and comparing said reconstructed data to said input data

21 The method of claim 13 wherein said input data is a digital image

22 The method of claim 13 further comprising the step of storing the key values in memory

23 The method of claim 13 further comprising the step of transmitting the key values to a receiver

24 The method of claim 13 further comprising the step of transmitting the encoded data to a receiver

25 A system for encoding data using a transform which is a function of input data and a basis, the system comprising a means for receiving the input data, b means for generating the basis from key values specifying characteristics of a cellular automata space of at least one cell and at least one rule of interaction for the at least one cell, and c means for transforming the input data into encoded data using the basis

26 The system of claim 25 wherein the transforming means is comprised of means storing the encoded data

27 The system of claim 25 wherein the generating means is comprised of means for evolving the at least one cell using the key values and the at least one rule of interaction

28 The system of claim 27 wherein the generated basis is one of a plurality of classes of bases, each class having a basis type and defining an element value

29 The system of claim 28 wherein the element value for a first class ofthe plurality of classes of bases is one, zero, or negative one

30 The system of claim 28 wherein the element value is a weighted sum of values in selected ones of the cells during intervals of said evolution

31 The system of claim 28 wherein the element value is an average ofthe cells having a selected value

32 The system of claim 28 comprising means for generating the element value including: means for selecting the key value, means for dividing the input data into segments, means for calculating reconstruction weights, wherein an element of said input data is determined using the reconstruction weights from other elements of said input data, means for transforming an initial data value into reconstructed data using the reconstruction weights, and means for comparing said reconstructed data to the input data

33 The system of claim 25 wherein the input data is a digital image

34 The system of claim 25 further comprising means for storing the key values in memory

35 The system of claim 25 further comprising means for transmitting the key values to a receiver

36 The system of claim 25 further comprising means for transmitting the encoded data to a receiver

37 A system for decoding data using a transform which is a function of input data and a basis, the system comprising a. means for receiving the input data, b means for generating the basis from key values specifying characteristics of at least one cell and at least one rule of interaction ofthe at least one cell, and c means for transforming the input data into decoded data using the basis

38 The system of claim 37 wherein the transforming means includes means for storing the decoded data

39. The system of claim 37 wherein the generating means includes: means for evolving the at least one cell using the key values and the at least one rule of interaction.

40. The system of claim 39 wherein the generated basis is one of a plurality of classes of bases, each class having a basis type and defining an element value.

41. The system of claim 40 wherein the element value for a first class ofthe plurality of classes of bases is one, zero, or negative one.

42. The system of claim 40 wherein the element value is a weighted sum of values in selected ones ofthe cells during intervals of said evolution.

43. The system of claim 42 wherein the element value is an average ofthe cells having a selected value.

44. The system of claim 42 wherein the element value is computed by means comprised of: means for selecting the key value; means dividing the input data into segments; means for calculating reconstruction weights, wherein an element of said input data is determined using said reconstruction weights from other elements of said input data; means for transforming an initial data value into reconstructed data using said reconstruction weights; and means for comparing said reconstructed data to said input data.

45. The system of claim 35 wherein said input data is a digital image.

46 The system of claim 35 further comprising means for storing the key values in memory

47. The system of claim 35 further comprising means for transmitting the key values to a receiver

48 The system of claim 35 further comprising means for transmitting the encoded data to a receiver

49 An apparatus for encoding or decoding data using a transform which is a function of input data and a basis, the apparatus comprising a a receiver receiving the input data, b a processing module, connected to the receiver, generating the basis from key values specifying characteristics of at least one cell and at least one rule of interaction ofthe at least one cell, and c said processing module transforming the input data into decoded data using the basis

50 A method of encrypting data using a transform which is a function of input data and a basis, the method comprising the steps performed by a computer of a receiving the input data, b generating the basis from key values specifying characteristics of a cellular automata space of at least one cell and at least one rule of interaction for the at least one cell, and c. transforming the input data into encrypted data using the basis

51 The method of claim 50 wherein the transforming step includes a substep of transmitting the encrypted data to a receiver

52. The method of claim 50 wherein the generating step includes a substep of evolving the at least one cell using the key values and the at least one rule of interaction

53 The method of claim 52 wherein the generated basis of one of a plurality of classes of bases, each class having a basis type and defining an element value

54 The method of claim 53 wherein the element value for a first class ofthe plurality of classes of bases is one, zero, or negative one

55 The method of claim 53 wherein the element value is a weighted sum of values in selected ones ofthe cells during intervals of said evolution

56 The method of claim 53 wherein the element value is an average of the cells having a selected value

57 The method of claim 53 wherein the element value is computed following the steps of selecting the key value, dividing the input data into segments, calculating reconstruction weights, wherein an element of said input data is determined using the reconstruction weights from other elements of said input data, transforming an initial data value into reconstructed data using the reconstruction weights, and comparing said reconstructed data to the input data

58 The method of claim 50 wherein the input data is a digital image

59 The method of claim 50 further comprising the step of storing the key values in memory

60. The method of claim 50 further comprising the step of transmitting the key values to a receiver

61 A method of decrypting data using a transform which is a function of input data and a basis, the method comprising the steps performed by a computer of a receiving the input data, b generating the basis from key values specifying characteristics of at least one cell and at least one rule of interaction ofthe at least one cell, and c transforming the input data into decrypted data using the basis

62 The method of claim 61 wherein the transforming step includes a substep of storing the decrypted data

63. The method of claim 61 where the generating step includes a substep of evolving the at least one cell using the key values and the at least one rule of interaction

64 The method of claim 63 wherein the generated basis is one of a plurality of classes of bases, each class having a basis type and defining an element value

65 The method of claim 64 where the element value for a first class ofthe plurality of classes of bases is one, zero, or negative one

66 The method of claim 64 wherein the element value is a weighted sum of values in selected ones ofthe cells during intervals of said evolution

67 The method of claim 64 wherein the element value is an average of the cells having a selected value 68 The method of claim 64 wherein the element value is computed following the steps of selecting the key value, dividing the input data into segments, calculating reconstruction weights, wherein an element of said input data is determined using said reconstruction weights from other elements of said input data, transforming an initial data value into reconstructed data using said reconstruction weights, and comparing said reconstruction data to said input data

69 The method of claim 66 wherein said input data is a digital image

70 The method of claim 63 further comprising the step of storing said key values in memory

71 The method of claim 63 further comprising the step of transmitting said key values to a receiver

72 An apparatus for encrypting or decrypting data using a transform which is a function of input data and a basis, the apparatus comprising a a receiver receiving the input data, b a processing module, connected to the receiver, generating the basis from key values specifying characteristics of at least one cell and at least one rule of interaction ofthe at least one cell, and c said processing module transforming the input data into encrypted or decrypted data using the basis

73 A method of modeling a physical system using a transform which is a function of input data and basis, the method comprising the steps performed by a computer of a receiving the input data including information describing the characteristics ofthe physical system. b. generating the basis from key values wherein said key values specify characteristics of at least one cell and at least one rule of interaction ofthe cell, and c transforming the input data into a model of the physical system using the basis

74 The method of claim 73 wherein said transforming step includes a substep of storing the model ofthe physical system

75 The method of claim 73 wherein the generating step includes a substep of evolving the at least one cell using the kev values and the at least one rule of interaction

76 The method of claim 75 wherein the generated basis is one of a plurality of classes of bases, each class having a basis type and defining an element value

77 The method of claim 76 where the element value for a first class ofthe plurality of classes of bases is one, zero, or negative one

78 The method of claim 76 wherein the element value is a weighted sum of values in selected ones ofthe cells during intervals of said evolution

79 The method of claim 76 wherein the element value is an average ofthe cells having a selected value

80 The method of claim 76 wherein the element value is computed following the steps of selecting the key value, dividing the input data into segments, calculating reconstruction weights, wherein an element of said input data is determined using said reconstruction weights from other elements of said input data, transforming an initial data value into reconstructed data using said reconstruction weights, and comparing said reconstructed data to said input data

81 The method of claim 73 further comprising the steps of storing said key values in memory

82 Apparatus for modeling a physical system using a transform which is a function of input data and basis, the apparatus comprising a means for receiving the input data including information describing the characteristics ofthe physical system, b means for generating the basis from key values wherein said key values specify characteristics of at least one cell and at least one rule of interaction ofthe cell, and c means for transforming the input data into a model ofthe physical system using the basis

83 The apparatus of claim 82 wherein said transforming means includes means for storing the model ofthe physical system

84 The apparatus of claim 82 wherein the generating means includes means for evolving the at least one cell using the key values and the at least one rule of interaction

85 The apparatus of claim 84 wherein the generated basis is one of a plurality of classes of bases, each class having a basis type and defining an element value

86 The apparatus of claim 85 where the element value for a first class of the plurality of classes of bases is one, zero, or negative one 87 The apparatus of claim 85 wherein the element value is a weighted sum of values in selected ones ofthe cells during intervals of said evolution

88 The apparatus of claim 85 wherein the element value is an average ofthe cells having a selected value

89 The apparatus of claim 85 further comprising means for computing the element value, the computing means comprising means for selecting the key value. means for dividing the input data into segments, means for calculating reconstruction weights, wherein an element of said input data is determined using said reconstruction weights from other elements of said input data, means for transforming an initial data value into reconstructed data using said reconstruction weights, and means for comparing said reconstructed data to said input data

90 The apparatus of claim 82 further comprising means for storing said key values in memory

91 An apparatus for modeling a physical phenomenon using a transform which is a function of input data and a basis, the apparatus comprising, a a receiver receiving the input data, b a processing module, connected to the receiver, generating the basis from key values specifying characteristics of at least one cell and at least one rule of interaction of the at least one cell, and c said processing module transforming the input data into a model ofthe physical phenomenon using the basis