Advanced
Generation and Analysis of Pattern Classifier based on LFSRs
Generation and Analysis of Pattern Classifier based on LFSRs
Journal of the Korea Institute of Information and Communication Engineering. 2015. Jul, 19(7): 1577-1584
Copyright © 2015, The Korean Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : February 09, 2015
  • Accepted : March 19, 2015
  • Published : July 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
숙희 권
Department of Applied Mathmatics, Pukyong University, Pusan 608-737, Korea
성진 조
Department of Applied Mathmatics, Pukyong University, Pusan 608-737, Korea
sjcho@pknu.ac.kr
언숙 최
Department of Information & Communications Engineering, Tongmyong University, Pusan 608-711, Korea
길탁 공
Department of Applied Mathmatics, Pukyong University, Pusan 608-737, Korea
한두 김
Department of Applied Mathmatics, Inje University, Pusan 621-749, Korea

Abstract
본 논문에서는 LFSR 기반의 패턴분류기를 생성법을 제안한다. 생성한 LFSR 기반의 패턴분류기는 도달불가능 상태를 쉽게 파악할 수 있고 0-기본경로를 이용하여 의존벡터를 구할 수 있다. 또한 주어진 의존벡터에 대응하는 LFSR 기반의 패턴분류기를 생성하는 방법을 제안한다.
Keywords
Ⅰ. 서 론
패턴인식의 처리 과정은 패턴의 특징을 파악하여 패턴이 속한 부류로 분류하는 과정으로 구성되며, 패턴인식의 대부분인 분류 작업은 패턴분류기에 의하여 이루어진다. 패턴분류기는 데이터로부터 패턴들의 중요한 특징이나 속성을 추출하여 패턴을 특정한 클래스에 할당한다 [1 - 3] . 패턴분류기의 설계는 작은 저장 공간, 큰 데이터 처리량, 낮은 가격대로 구현하는 것을 고려하여야 한다.
메모리 량을 최소화 할 수 있는 방법으로 Maji 등은 클래스의 수가 2개인 패턴을 효과적으로 분류할 수 있는 MACA(Multiple Attractor Cellular Automata)를 합성하여 패턴분류기를 설계하였다 [3] . Maji 등은 의존벡터(Dependency Vector, 이하 DV )를 이용하여 시간복잡도를 O ( n 3 )에서 O ( n )으로 줄였다. 그러나 DV 를 구하기 위하여 MACA에 대응하는 0-트리에 속하는 모든 원소를 구하여 그것을 계수로 하는 동차연립방정식의 해를 구하야 하므로 초기 설정시간이 오래 걸린다.
본 논문에서는 초기 설정시간을 효과적으로 줄이기 위해 LFSR(Linear feedback shift register) 기반의 패턴 분류기를 생성한다. 생성한 LFSR 기반의 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬에 대한 특성을 분석하여 주어진
PPT Slide
Lager Image
의 상태전이그래프에서 0-트리의 한 도달불가능한 상태를 구하는 방법을 제안한다. 따라서
PPT Slide
Lager Image
에 대응하는 DV 를 구하는 시간을 효과적으로 줄일 수 있다. 또한 주어진 n -셀 DV 에 대응하는 LFSR 기반의 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬 TMn 에 대하여, DVi 에 대응하는 TMi 를 합성하여 생성할 수 있다.
Ⅱ. 배경 지식
의사난수열 생성, 암호화 시스템 구현 등에 이용되는 LFSR은 시프트 레지스터의 일종으로, 레지스터에 입력되는 값이 이전 상태 값들의 선형 함수로 계산되고 유한체 위에서 정의된 선형점화식 수열을 효율적으로 발생시킬 수 있다. 이러한 수열의 특성은 점화식에 의해 유도되는 특성다항식에 의하여 결정된다 [4 , 5] . n 개의 셀과 선형 피드백 함수(Linear feedback function) f ( s 0 , s 1 ,⋯, s n -1 ) 로 구성되는 n 차 LFSR은 식(1)과 같다 [6] .
PPT Slide
Lager Image
여기서 s 0 , s 1 ,⋯, s n -1 는 레지스터에 입력되는 초깃값이고 c 0 , c 1 ,⋯, c n -1 GF (2) 이다.
그림1 n 차 LFSR의 구조이다. 식(1)에 대한 다항식 cT ( x ) = xn + c n -1 x n -1 + ⋯ + c 0 를 LFSR의 특성다항식 (Characteristic polynomial)이라 한다 [7] .
PPT Slide
Lager Image
LFSR의 구조 Fig. 1 Structure of LFSR
다음은 본 논문에서 사용되는 용어에 대한 정의이다.
<정의2.1 [8 - 10] >
  • (ⅰ) 끌개(attractor): 상태전이그래프에서 순환상태 중 사이클의 길이가 1인 상태
  • (ⅱ)α-트리: 순환상태α를 루트로 하는 트리
  • (ⅲ) 깊이(depth): 상태전이그래프에서 임의의 도달불가능상태에서 가장 가까운 순환상태로 가는데 걸리는 최소단계 수
  • (ⅳ)α-기본경로: 깊이가d인α-트리의 도달불가능 상태 x는d단계 후 그 상태가α가 된다. 이때 상태전이 단계 (x →Tx → ⋯ →Tdx (=α))를α-기본경로라 한다. 여기서T는 상태전이행렬이다.
  • (ⅴ) 도달불가능상태(non-reachable state): 상태전이 그래프에서 직전자가 존재하지 않는 상태.
  • (ⅵ) 도달가능상태(reachable state): 상태전이그래프에서 직전자가 적어도 한 개 존재하는 상태
다항식 f ( x ) = xn + c n -1 x n -1 + c n -2 x n -2 + ⋯ + c 1 x + c 0 ( ci GF (2), 0 ≤ i n -1)에 대해 아래와 같은 n × n 행렬 T f ( x )의 동반행렬(Companion matrix)이라고 하고 [7] , 다음 식(2)와 같이 4가지 형태로 나타낼 수 있다.
PPT Slide
Lager Image
n 차 LFSR은 Xt = TXt -1 로 표현할 수 있다. 여기서, Xi 는 시간 i 에서의 n × 1 상태벡터이고 T 는 동반행렬로 표현할 수 있다. 동반행렬 T 에 대하여 cT ( x ) = mT ( x )이 성립한다 [7] . 단 mT ( x )는 T 의 최소 다항식(Minimal polynomial)이다.
<정리 2.2 [11] > 임의의 m × n 행렬 A 에 대하여 다음이 성립한다.
PPT Slide
Lager Image
앞으로 cT ( x ) = mT ( x ) = xn -1 ( x +1)인 2개의 끌개를 갖는 패턴분류기를
PPT Slide
Lager Image
로 나타내기로 한다.
<정의 2.3 [3] > 의존벡터(Dependency Vector, 이하 DV )는 n 비트 패턴들로 구성된 벡터공간의 부분공간
PPT Slide
Lager Image
의 모든 원소에 대하여 성립하는 변수들 간의 선형 종속 관계이다. DV 와 0-트리의 성분의 내적은 0이다.
DV = (101)인 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬 TM 3 은 다음 식(4)과 같이 두 가지 경우가 있다.
PPT Slide
Lager Image
Ⅲ LFSR 기반의 패턴분류기
이 절에서는 LFSR을 이용한 패턴분류기를 생성하고 0-기본경로를 이용하여 DV 를 구할 수 있는 방법을 제안한다. n -셀 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬 TMn 에 대하여 CTMn ( x ) = mTMn ( x ) = xn -1 ( x +1)이 성립한다. 이때 끌개의 개수는 2개이고, 0-트리의 상태의 개수는 2 n -1 개다. 그리고 rank ( TMn ) = n -1이다. cTMn ( x ) = mTMn ( x ) = xn -1 ( x +1)인 n -셀 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬 TMn 에 대하여 대각성분의 1의 개수는 홀수이다.
<정리 3.1 [12] > 상태전이행렬이 TMn n -셀 패턴분류기
PPT Slide
Lager Image
의 상태전이그래프에서, x 가 0-트리의 한 도달불가능상태일 때 DV 는 0-기본경로
PPT Slide
Lager Image
의 성분을 각 행으로 하는 행렬 ( B 0 )의 영공간 N ( B 0 )의 기저벡터이고 유일하다.
위 정리로부터 0-트리의 도달불가능상태를 알면 0-기본경로를 알 수 있으므로 DV 를 구하기가 쉽다는 것을 알 수 있다.
LFSR 기반의 n -셀 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬 TMn 은 다음 식(5)과 같이 4가지 형태로 나타낼 수 있다.
PPT Slide
Lager Image
<정리 3.2> 길이가 n 인 LFSR 기반의 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬 TMn 에 대하여, e i 를 크기가 n 이고 i 번째 성분이 1인 단위벡터
PPT Slide
Lager Image
일 때,
PPT Slide
Lager Image
의 상태전이그래프에서 0-트리의 한 도달불가능한 상태 x 는 다음과 같다.
  • (ⅰ)
  • (ⅱ)
  • (ⅲ)
  • (ⅳ)
증명>
PPT Slide
Lager Image
의 상태전이그래프에서 0-트리의 도달가능상태는 T 의 모든 열들의 일차결합으로 표현된다.
먼저 (i)에 대하여 첫 번째 행이 영벡터이므로 TMn e 1 e 1 이다. 그런데
PPT Slide
Lager Image
의 모든 열들의 일차결합으로 표현되지 않으므로 0-트리의 도달불가능 상태가 된다. 따라서
PPT Slide
Lager Image
의 0-트리의 도달불가능한 상태이다.
(ii)는 (i)과 같은 방법으로 증명할 수 있다.
(iii)에서
PPT Slide
Lager Image
은 1행과 2행이 같다. y
PPT Slide
Lager Image
라 하면
PPT Slide
Lager Image
을 만족한다. 그런데
PPT Slide
Lager Image
의 모든 열들의 일차결합으로 표현되지 않는다. 그리고
PPT Slide
Lager Image
이므로
PPT Slide
Lager Image
의 모든 열들의 일차결합으로 표현되지 않으므로 0-트리의 도달 불가능상태가 된다. 따라서
PPT Slide
Lager Image
의0-트리의 도달불가능한 상태이다.
(iv)는 (iii)과 같은 방법으로 증명할 수 있다. □
<정리 3.3> 길이가 n 인 LFSR 기반의 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬
PPT Slide
Lager Image
에 대하여 DV 는 다음과 같다.
PPT Slide
Lager Image
증명> (i)
PPT Slide
Lager Image
을 상태전이행렬로 갖는
PPT Slide
Lager Image
의 상태 전이그래프에서 0-트리의 한 도달불가능상태는 정리 3.2에 의하여 x = (110 ⋯ 0) t 이고 0-기본경로
PPT Slide
Lager Image
는 (110 ⋯ 0) t → (011 ⋯ 0) t → ⋯ → (000 ⋯ 0) t 이다. 또한 0-기본경로의 성분을 각 행으로 하는 행렬 B 0 는 식(6)과 같다.
PPT Slide
Lager Image
따라서 N ( B 0 ) = {(00 ⋯ 0) t , (11 ⋯ 1) t }이므로 정리 3.2에 의하여 DV = (1 ⋯ 1)이다.
(ii) , (iii), (iv)는 (i)과 같은 방법으로 증명할 수 있다.
표 1 n -셀 LFSR 기반의 패턴분류기
PPT Slide
Lager Image
에 대하여 상태전이행렬
PPT Slide
Lager Image
에 대응하는 상태전이 그래프에서 0-트리의 한 도달불가능한 상태와
PPT Slide
Lager Image
DV 를 나타낸다.
n-셀 LFSR 기반의 패턴분류기Table. 1n-cell Pattern Classifierbased on LFSR
PPT Slide
Lager Image
n-셀 LFSR 기반의 패턴분류기 Table. 1 n-cell Pattern Classifier based on LFSR
<예제 3.1> 길이가 4인 LFSR 기반의 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬이
PPT Slide
Lager Image
이라 하자.
PPT Slide
Lager Image
은 식(7)과 같고, 0이 아닌 끌개는 1이고 도달불가능상태는 정리 3.2에 의해 x = (1100) t 이다.
PPT Slide
Lager Image
PPT Slide
Lager Image
의 상태전이그래프를 나타내면 그림 2 와 같고 0-트리의 0-기본경로는 ((1100) t → (0110) t → (0011) t → (0000) t = 12→6→3→0)이다. 0-기본경로의 성분을 각 행으로 하는 행렬 B 0 는 식(8)과 같다.
PPT Slide
Lager Image
PPT Slide
Lager Image
의 상태전이그래프 Fig. 2 State-transition diagram of
따라서 N ( B 0 ) = {(0000) t , (1111) t }이므로 DV = (1111)이다.
길이가 4인 LFSR 기반의 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬
PPT Slide
Lager Image
에 대하여 DV 표 2 와 같다.
n-셀 LFSR 기반의 패턴분류기 ℂ4MTable. 2n-cell Pattern Classifierbased on LFSR
PPT Slide
Lager Image
n-셀 LFSR 기반의 패턴분류기 ℂ4M Table. 2 n-cell Pattern Classifier based on LFSR
Ⅳ. LFSR 기반의 패턴분류기 합성
이 절에서는 주어진 DV 에 대응하는 LFSR 기반의 패턴분류기를 합성하는 방법을 제안한다.
[1 , 12] 에서 언급한
PPT Slide
Lager Image
인 경우와 DV = (0∗⋯∗0)인 경우를 제외하고 n -셀 DV 에 대응하는 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬 TMn 를 구성하는 방법이다. 다음 정리는 주어진 DV 에 대응하는 LFSR 기반의 패턴분류기를 합성하는 방법이다.
<정리4.1> 길이가 n 인 LFSR 기반의 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬 TMn 에 대하여 n -셀 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬 TMn 은 다음 표 3 과 같다.
n-셀 LFSR 기반의 패턴분류기 ℂnMTable. 3n-cell Pattern Classifierbased on LFSR
PPT Slide
Lager Image
n-셀 LFSR 기반의 패턴분류기 ℂnM Table. 3 n-cell Pattern Classifier based on LFSR
여기서 DV = (101) 인 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬 TM 3 은 다음 식(4)과 같다.
증명> 정리 3.2에 의하여 도달불가능상태 x는 (110 ⋯ 0) t 이고 0-기본경로((110 ⋯ 0) t → (0110 ⋯ 0) t → ⋯ → (0 ⋯ 0110) t → (0 ⋯ 010) t → (0 ⋯ 001) t 의 성분을 각 행으로 하는 행렬 B 0 는 식(9)과 같다.
PPT Slide
Lager Image
N ( B 0 ) = {(00 ⋯ 00) t , (1 ⋯ 10) t } 이므로 DV = (1 ⋯ 10 ⋯ 0)이다.
(ii), (iii), (iv), (v), (vi)의 경우 (i)과 같은 방법으로 증명할 수 있다.
<예제 4.1> (i) DV = (11110)인 LFSR 기반의 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬 TM 5 은 식(10)과 같다.
PPT Slide
Lager Image
(ii) DV = (11101)인 LFSR 기반의 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬 TM 5 은 식(11)과 같다.
PPT Slide
Lager Image
(iii) DV = (00101)인 LFSR 기반의 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬 TM 5 은 식(12)와 같다.
PPT Slide
Lager Image
<예제 4.2> (i) DV = (1101000)인 LFSR 기반의 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬 TM 7 은 식(13)과 같다.
PPT Slide
Lager Image
(ii) DV = (1101000)인 LFSR 기반의 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬 TM 7 은 식(14)와 같다.
PPT Slide
Lager Image
다음은 LFSR 기반의 패턴분류기 합성에 대한 알고리즘이다.
PPT Slide
Lager Image
Ⅴ. 결 론
본 논문에서는 LFSR 기반의 패턴분류기를 생성하 였다. 생성한 LFSR 기반의 패턴분류기의 분석을 통해 상태전이그래프에서 0-트리의 한 도달불가능상태를 찾 는 방법을 제안하였고 이를 통해 DV 를 구하는 시간을 효과적으로 줄였다. 또한 주어진 길이가 n DV 에 대응하는 LFSR 기반의 패턴분류기
PPT Slide
Lager Image
의 상태전이행렬 TMn 을 기본형이 되는 TMi 를 합성하여 생성하는 방법을 제안하였다.
BIO
권숙희(Sook-Hee Kwon)
2011년 부경대학교 응용수학과 졸업(이학석사)
2011년 ~ 현재 부경대학교 응용수학과 박사과정
※관심분야 : 정보보호, 부호이론
조성진(Sung-Jin Cho)
1988년 고려대학교 대학원 수학과 졸업(이학박사)
1988년 ~ 현재 부경대학교 응용수학과 교수
※관심분야 : 셀룰라 오토마타론, 정보보호
최언숙(Un-Sook Choi)
2004년 부경대학교 대학원 응용수학과 졸업(이학박사)
2009년 부경대학교 대학원 정보보호학과 졸업(공학박사)
2006년 ~ 현재 동명대학교 정보통신공학과 교수
※관심분야 : 셀룰라 오토마타론, 정보보호, 암호이론
공길탁(Gil-Tak Kong)
2011년 ~ 현재 부경대학교 응용수학과 석사과정
※관심분야 : 셀룰라 오토마타론, 암호이론
김한두(Han-Doo Kim)
1988년 고려대학교 대학원 수학과 졸업(이학박사)
1989년 ~ 현재 인재대학교 응용수학과 교수
※관심분야 : 전산수학, 셀룰라 오토마타론
References
Ganguly N. , Ph. D. dissertation 2003 “Cellular Automata Evolution: Theory and Applications in Pattern Recognition and Classification,” CST Dept. BECDU India Ph. D. dissertation
Krishna C. , Jas A. , Touba N.A. 2004 “Achieving high encoding efficiency with partial dynamic LFSR reseeding,” ACM Trans. Design Automation of Electronic Systems 9 500 - 516    DOI : 10.1145/1027084.1027089
Maji P. , Shaw C. , Ganguly N. , Sikdar B.K. , Chaudhuri P.P. 2003 “Theory and application of cellular automata for pattern classification,” Fundamenta Informaticae 58 321 - 354
Krishna C. , Jas A. , Touba N.A. 2004 “Achieving high encoding efficiency with partial dynamic LFSR reseeding,” ACM Trans. Design Automation of Electronic Systems 9 500 - 516    DOI : 10.1145/1027084.1027089
Krishna C.C. , Touba N.A. “Reducing test data volume using LFSR reseeding with seed compression,” in Proc. IEEE ITC 2002 321 - 330
Golomb S. 1967 Shift Register Sequences Aegean Park Press California
Lidl R. , Niederreiter H. 1997 Finite Fields Cambridge University
Das A.K. , Chaudhuri P.P. 1993 “Vector space theoretic analysis of additive cellular automata and its application for pseudo-exhaustive test pattern generation,” IEEE Trans. Comput-Aided Des. Integr. Circuits Syst. 42 340 - 352
Chaudhuri P.P. , Chowdhury D.R. , Nandy S. , Chattopadhyay C. 1997 Additive Cellular Automata; Theory and Applications IEEE Computer Society Press California vol. 1
Cho S.J. , Choi U.S. , Kim H.D. 2002 “Behavior of complemented cellular automata derived from a linear cellular automata,” Mathematical and Computer Modelling 36 979 - 986    DOI : 10.1016/S0895-7177(02)00251-0
Strang G. 2009 Introduction to Linear Algebra Wellesley-Cambridge Press
Cho S.J. , Kim H.D. , Choi U.S. , Kim S.T. , Kim J.G. , Kwon S.H. , Gong G.T. 2014 “Generation of TPMACA for Pattern Classification,” LNCS 8751 408 - 416