본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

90/150 Uniform CA의 합성 및 특성다항식 계산
Synthesis of 90/150 Uniform CA and Computation of Characteristic Polynomial corresponding to uniform CA

최언숙    (동명대학교 미디어공학과   ); 조성진    (부경대학교 응용수학과   ); 임지미    (부경대학교 응용수학과  );
  • 초록

    전이 규칙 90과 150만을 사용하는 90/150 CA는 최소다항식과 특성다항식이 같은 CA로 랜덤성이 우수하여 LFSR의 대안으로 사용되어왔다. 90 Uniform CA와 150 uniform CA는 모든 셀에 동일한 전이규칙이 적용되는 CA로 기밀성과 인증을 제공하는 Sarkar의 암호기법에 사용되었다. 본 논문에서는 전이규칙이 90 또는 150인 uniform CA에 대하여 분석하고 특별한 전이규칙을 갖는 n-셀 90/150 CA를 이용하여 2n-셀 uniform CA와 (2n+1)-셀 uniform CA를 합성하고 대응하는 특성다항식을 계산하는 효율적 방법을 제안한다.


    90/150 CA is a CA completely specified by using rule 90 and rule 150. Since 90/150 CA whose minimal and characteristic polynomials are identical has outstanding randomness, this CA is more attractive than LFSR. Sarkar proposed a scheme based on the 90 uniform CA and the 150 uniform CA. That scheme provided authentication by digital signature and other basic security requirements like confidentiality. In this paper we analyze 90 or 150 uniform CA and give a synthesis method of 2n-cell uniform CA and (2n+1)-cell uniform CA using a special n-cell 90/150 CA. And we propose an effective method of computation of characteristic polynomial corresponding to uniform CA.


  • 주제어

    합성 .   특성다항식 .   전이규칙 .   상태전이행렬.  

  • 참고문헌 (14)

    1. S. Wolfram, O. Martin and A. M. Odlyzko, "Algebraic properties of cellular automata," Communications in Mathematical Physics, 3, pp. 219-258, 1984. 
    2. A.K. Das, "Additive Cellular Automata: Theory and Applications as a Built-In Self-Test Structure," Ph. D. Thesis, I.I.T. Kharagpur, India, 1990. 
    3. A.K. Das and P.P. Chaudhuri, "Efficient characterization of cellular automata," Proc. IEE(Part E), Vol. 137, pp. 81-87, 1990. 
    4. A.K. Das and P.P. Chaudhuri, "Vector space theoretic analysis of additive cellular automata and its application for pseudo-exhaustive test pattern generation," IEEE Trans. Comput., Vol. 42, pp. 340-352, 1993. 
    5. S. Nandi, B.K. Kar and P.P. Chaudhuri, "Theory and applications of cellular automata in cryptography," IEEE Trans. Computers, Vol. 43, pp. 1346-1357, 1994. 
    6. S. Chakraborty, D.R. Chowdhury, P.P. Chaudhuri, "Theory and application of nongroup cellular automata for synthesis of easily testable finite state machines," IEEE Trans. Computers, Vol. 45, pp. 769-781, 1996. 
    7. S. Nandi and P.P. Chaudhuri, "Analysis of periodic and intermediate boundary 90/150 cellular automata," IEEE Trans. Computers, Vol. 45, pp. 1-12, 1996. 
    8. S.J. Cho, U.S. Choi, Y.H. Hwang, Y.S. Pyo, H.D. Kim and S.H. Heo, "Computing Phase Shifts of Maximum-Length 90/150 Cellular Automata Sequences," LNCS, Vol. 3305, pp. 31-39, 2004. 
    9. K. Cattell and J. Muzio, "Analysis of one-dimensional linear hybrid cellular automata over GF(q)," IEEE Transactions of Computers, Vol. 45, pp. 782-792, 1996. 
    10. K. Cattell and J. Muzio, "Synthesis of one-dimensional linear hybrid cellular automata," IEEE Transactions on Computer-Aided Design of Integrated Circuit and Systems, Vol. 15, pp. 325-335, 1996. 
    11. S.J. Cho, U.S. Choi, H.D. Kim and Y. H. Hwang, "New synthesis of one-dimensional 90/150 linear hybrid group cellular automata," IEEE Trans. Comput-Aided Des. Integr. Circuits Syst., Vol. 26(9), pp. 1720-1724, 2007. 
    12. S. Chattopadhyay, "Some studies on theory and application of additive cellular automata," PhD thesis, I.I.T., Kharagpur, India, 1995. 
    13. S.J. Cho, U.S. Choi, H.D. Kim and Y. H. Hwang, J.G. Kim, "Analysis of 90/150 Two Predecessor Nongroup Cellular Automata," ACRI 2008 LNCS Vol. 5191, pp. 128-135, 2008. 
    14. S.K. Sarkar, T. Karmakar, A. Kumar, K. Sharma, P.C. Pradhan and C. Puttamadappa, "A One Dimensional Cellular Automata based Security Sheme providing both Authentication and Confidentiality," IE(I) Journal-CP, Vol. 87, pp. 1-8, 2006. 
  • 이 논문을 인용한 문헌 (1)

    1. Kwon, Sook-Hee ; Cho, Sung-Jin ; Choi, Un-Sook ; Kim, Han-Doo 2015. "Reachable table of nonlinear cellular automata" 한국전자통신학회 논문지 = The Journal of the Korea Institute of Electronic Communication Sciences, 10(5): 593~598     

 저자의 다른 논문

  • 최언숙 (42)

    1. 2006 "3-이웃 셀룰라 오토마타의 도달 가능/불가능 상태 분석" 한국해양정보통신학회논문지 = The journal of the Korea Institute of Maritime Information & Communication Sciences 10 (6): 1132~1136    
    2. 2006 "최대 동일 길이를 갖는 여원 HGCA구성" 한국해양정보통신학회논문지 = The journal of the Korea Institute of Maritime Information & Communication Sciences 10 (9): 1565~1572    
    3. 2008 "D1-MACA 기반의 두 클래스 패턴 분류기" 한국전자통신학회 논문지 = The Journal of the Korea Institute of Electronic Communication Sciences 3 (4): 254~259    
    4. 2009 "D1-MACA 기반의 최소 메모리량을 갖는 두 패턴 분류기의 구성" 한국해양정보통신학회논문지 = The journal of the Korea Institute of Maritime Information & Communication Sciences 13 (5): 931~936    
    5. 2010 "셀룰라 오토마타 기반의 수축-삽입 수열의 분석" 한국해양정보통신학회논문지 = The journal of the Korea Institute of Maritime Information & Communication Sciences 14 (10): 2283~2291    
    6. 2010 "위상이동차를 이용한 수축 생성기의 분석" 한국해양정보통신학회논문지 = The journal of the Korea Institute of Maritime Information & Communication Sciences 14 (11): 2507~2513    
    7. 2010 "페이지 쉬프터 기반의 의사 난수 패턴 생성기" 한국해양정보통신학회논문지 = The journal of the Korea Institute of Maritime Information & Communication Sciences 14 (3): 707~714    
    8. 2010 "다중 끌개를 갖는 셀룰라 오토마타를 이용한 패턴 분류기 생성" 한국전자통신학회 논문지 = The Journal of the Korea Institute of Electronic Communication Sciences 5 (3): 315~320    
    9. 2010 "수축생성기에 기반한 비선형 수열의 분석" 한국전자통신학회 논문지 = The Journal of the Korea Institute of Electronic Communication Sciences 5 (4): 412~417    
    10. 2010 "GF(2p) 위에서의 LFSR과 CA를 이용한 shrunken 수열의 분석" 한국전자통신학회 논문지 = The Journal of the Korea Institute of Electronic Communication Sciences 5 (4): 418~424    
  • 조성진 (90)

  • 임지미 (5)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기