CA Based Pseudorandom Sequence Generation and Pattern Classification

Abstract

VLSI시대는 선형 기계와 특히 국소적인 이웃을 갖는 셀룰라 오토마타(Cellular Automata, 이하 CA)의 연구에 새로운 국면을 열었다. VLSI 하드웨어의 구현은 국소적으로 상호 연결된 간단하고 규칙적이며 모듈러하고 작은 단위로 확장 연결이 가능한 구조가 적합하다. 한편 CA는 동역학계를 해석하는 한 방법으로 시간과 공간을 이산적으로 다룬다. 이산적인 공간인 셀룰라 공간의 기본단위인 셀이 취할 수 있는 상태를 유한하게 처리하며, 각 셀들의 상태가 국소적인 상호작용에 의해 동시에 갱신되는 시스템인 CA는 스스로 조직화하고 재생산할 수 있는 모델로 Von Neumann에 의해 소개되었다. 이후 Wolfram은 CA의 가장 간단한 구조로 GF(2)에서의 1차원 CA를 제안하였으며, 이후 Das에 의하여 행렬 대수에 의하여 이를 체계화하였다. 특히 CA 중 다음 상태를 결정하는 함수가 선형적인 CA는 LFSR보다 난수성이 우수한 것으로 알려지며 LFSR의 대안으로 제안되었다. 이로 인해 테스트패턴 생성, 의사난수열 생성, 암호, 부울방정식, 오류정정부호, 압축치 분석, 이미지 압축 등 많은 분야에서 응용되었다. 본 논문에서는 주어진 CA-다항식을 특성다항식으로 갖는 90/150 CA를 효과적으로 합성하는 방법을 제안한다. 이 합성법은 알고리즘 복잡도가 O(n^(7))인 기존의 CA합성방법과 달리 알고리즘 복잡도가 O(n²)으로 매우 큰 차수의 90/150 CA를 합성하는데 있어 효과적이다. 이러한 합성법을 이용하여 작동방식이 간단하고 또한 구현이 용이하여 고속의 암호화가 요구되는 응용분야에 적합한 스트림암호로 잘 알려져 있는 Shrinking 생성기를 개선한 수축-삽입 수열 생성기를 제안하고 선형복잡도와 주기를 분석한다. 또한 이차함수 f(x)=x²+ax+b에 의해 생성되는 수열과 동일한 수열을 생성하는 비그룹 CA를 제안하고 보다 효과적인 수열 생성방법을 제안한다. 또한 90/150 비그룹 CA중 순환상태의 길이가 1인 90/150 TPMACA를 분석하고 이러한 CA의 합성방법을 제안한다. 먼저 90/150 TPSACA의 합성에 대한 방법을 제안하고 90/150 TPSACA로부터 유도된 90/150 TPMACA를 찾는 방법을 제안한다. 그 결과로 이미지 압축과 해싱의 연구에 유용한 TPSACA와 TPMACA의 상태전이그래프에서 주어진 상태가 도달가능상태인지 도달불가능상태인지를 영공간 개념을 이용하여 결정하는 방법을 제시한다. 또한 데이터 베이스 시스템에서 기록을 그룹화 하거나, VLSI 회로에서 결함을 찾는데 있어 주어진 패턴 집합을 두 개 이상의 분할 된 클래스로 분류하는 분류기로 D-1 MACA를 제안한다. 이 때 메모리량을 최소화 할 수 있는 최적의 D-1 MACA를 합성하는 알고리즘을 제안한다.

We proposed a new and very efficient method to find CA for a given CApolynomial by using the concept of similarity of two matrices and Lanczos tridiagonalization algorithm in GF(2). In this case CA-polynomials need neither irreducible nor primitive. By this method we showed that for a given irreducible polynomial there exist two CA. Our method is different from the method of Cattel’s[47]. By our algorithm we obtained the CA whose degree is 9689. We obtained the 1600 cell CA by about 50 CPU seconds. Moreover we obtained very large(at least 10000 cell) CA by a PC. The program was written in VC 6.0 and was run a PC(Microsoft Windows XP, Professional, Pentium(R) 4 CPU, 2.80 GHz, 504 MB RAM). And we proposed a new method which generates nonlinear pseudorandom sequences using two maximum-length 90/150 LHGCA obtained by the new synthesis algorithm. The generator which generates these sequences is possible to overcome spatial weak points of the interleaved sequence generator proposed by Gong[62]. Moreover the new sequence generator generated nonlinear sequences whose cycle lengths are always same for a given initial state. The nonlinear pseudorandom sequence obtained by our method has a larger period and a higher linear complexity than the shrunken sequence generated by LFSRs.