A cellular automaton (CA) is a discrete time dynamical system and consists of uniform array of memory called a cell. The states of cells in the array are updated according to a rule: the state of a cell at a given time depends only on its own state and the states of its nearby neighbors at the previous step. Since a CA has a simple, regular, modular, and cascadable structure, it is useful for hardware implementation for VLSI. Applications of CA's in various fields have been proposed.
In this dissertation, maximum length CA is considered as an alternative to linear feedback shift registers. In some applications, linear feedback shift registers of long period are required. Hence we are interested in finding configurations of maximum length CA sequences with large sizes of cells for possible applications.
First, the maximum length linear binary CA sequence is considered. It is shown that all possible maximum length linear binary CA sequences can be constructed using linear simple CA's and that the maximum length linear binary CA sequences are equivalent to the maximum length binary LFSR sequences. A procedure for finding the configurations of the maximum length linear simple CA is described. Configurations are found for cell length from 4 through 299 for immediate application using the procedure.
Secondly, we consider two dimensional maximum length cellular automaton sequences, which is an extension of the one dimensional ones. The difference between the one and two dimensional CA sequences is the physical configuration of cells. We rearranged the two dimensional cells to one dimensional CA, and then the procedure of the one dimensional case is applied. Some configurations of the two dimensional maximum length CA are found.
Lastly, we consider the two dimensional CA as a pseudorandom number generators. The two dimensional CA is similar to the generalized feedback shift registers. The k-distributivity of the two dimensional maximum length CA sequence is considered and the values of k are checked for some CA's. In addition, some statistical results are obtained for the two dimensional CA generators.
세포 자동기계는 이산시간 동적 시스템으로 세포라 불리는 메모리의 배열로 이루어 진다. 이 배열에서 세포의 다음 상태는 어떤 규칙에 따라 정해진다. 즉, 세포 자신과 이웃 세포들의 함수값으로 다음 상태가 정해진다. 세포 자동기계는 간단하고, 규칙적이며, 작은단위로 확장 연결할 수 있는 구조이기 때문에 VLSI 하드웨어 구현에 알맞다. 세포 자동기계의 응용은 여러 분야에 걸쳐 제시되고 있다.
이 논문에서는 최대 길이 세포 자동기계 수열을 선형 귀환 이동 저장기를 대신 쓰는 것으로 생각하였다. 어떤 응용에서는 긴 주기를 만드는 선형 귀환 이동 저장기들이 필요하다. 이러한 응용에 바탕을 두고 긴 주기를 만드는 세포 자동기계의 구성을 찾는 데에 관심을 두었다.
먼저, 최대 길이 선형 이진 세포 자동기계 수열을 생각하였다. 모든 가능한 최대 길이 선형 이진 세포 자동기계 수열이 3개의 이웃을 가진 선형 이진 세포 자동기계로 만들 수 있음을 보였다. 또한 이 최대 길이 세포 자동기계 수열은 최대 길이 선형 귀한 이동 저장기 수열과 같음을 보였다. 최대 길이를 갖는 세포 자동기계 의 구성을 찾는 과정을 설명하고 이 과정을 써서 즉시 응용할 수 있는 세포길이 4에서 299까지의 구성을 찾았다.
다음으로, 1차원의 확장으로 2차원 세포 자동기계 수열을 생각하였다. 1차원과 2차원의 차이는 세포들의 물리적이 배열이다. 2차원 배열을 1차원으로 재배열하여 1차원의 과정을 썼다. 최대 길이를 갖는 2차원 세포 자동기계의 구성을 찾았다.
마지막으로, 2차원 세포 자동기계를 유사 난수 발생기로써 생각하였다. 2차원 세포 자동기계는 일반화된 선형 귀한 이동 저장기와 비슷하다. 2차원 최대 길이 세포 자동기계 수열의 k-분포를 검토하였으며, 몇몇 세포 자동기계에 대하여 k 값을 검사하였다. 그리고 2차원 세포 자동기계 난수 발생기 수열에 대하여 통계적 시험을 수행하고 특성이 좋은 세포 자동기계의 구성을 찾았다.
