LFSR 기반의 패턴분류기의 생성 및 분석

Generation and Analysis of Pattern Classifier based on LFSRs

  • cc icon
  • ABSTRACT

    본 논문에서는 LFSR 기반의 패턴분류기를 생성법을 제안한다. 생성한 LFSR 기반의 패턴분류기는 도달불가능 상태를 쉽게 파악할 수 있고 0-기본경로를 이용하여 의존벡터를 구할 수 있다. 또한 주어진 의존벡터에 대응하는 LFSR 기반의 패턴분류기를 생성하는 방법을 제안한다.


    In this paper, we propose a method for generating pattern classifier based on LFSR. The proposed pattern classifier bosed on LFSR is easy to see non-reachable state, and we can obtain dependency vector by using the 0-basic path. Also, we propose a method for generating pattern classifiers based on LFSR which correspond to given dependency vector.

  • KEYWORD

    LFSR , 패턴분류기 , 의존벡터 , 끌개 , 0-기본경로

  • Ⅰ. 서 론

    패턴인식의 처리 과정은 패턴의 특징을 파악하여 패턴이 속한 부류로 분류하는 과정으로 구성되며, 패턴인식의 대부분인 분류 작업은 패턴분류기에 의하여 이루어진다. 패턴분류기는 데이터로부터 패턴들의 중요한 특징이나 속성을 추출하여 패턴을 특정한 클래스에 할당한다[1-3]. 패턴분류기의 설계는 작은 저장 공간, 큰 데이터 처리량, 낮은 가격대로 구현하는 것을 고려하여야 한다.

    메모리 량을 최소화 할 수 있는 방법으로 Maji 등은 클래스의 수가 2개인 패턴을 효과적으로 분류할 수 있는 MACA(Multiple Attractor Cellular Automata)를 합성하여 패턴분류기를 설계하였다[3]. Maji 등은 의존벡터(Dependency Vector, 이하 DV)를 이용하여 시간복잡도를 O(n3)에서 O(n)으로 줄였다. 그러나 DV를 구하기 위하여 MACA에 대응하는 0-트리에 속하는 모든 원소를 구하여 그것을 계수로 하는 동차연립방정식의 해를 구하야 하므로 초기 설정시간이 오래 걸린다.

    본 논문에서는 초기 설정시간을 효과적으로 줄이기 위해 LFSR(Linear feedback shift register) 기반의 패턴 분류기를 생성한다. 생성한 LFSR 기반의 패턴분류기 의 상태전이행렬에 대한 특성을 분석하여 주어진 의 상태전이그래프에서 0-트리의 한 도달불가능한 상태를 구하는 방법을 제안한다. 따라서 에 대응하는 DV를 구하는 시간을 효과적으로 줄일 수 있다. 또한 주어진 n-셀 DV에 대응하는 LFSR 기반의 패턴분류기 의 상태전이행렬 TMn에 대하여, DVi 에 대응하는 TMi를 합성하여 생성할 수 있다.

    Ⅱ. 배경 지식

    의사난수열 생성, 암호화 시스템 구현 등에 이용되는 LFSR은 시프트 레지스터의 일종으로, 레지스터에 입력되는 값이 이전 상태 값들의 선형 함수로 계산되고 유한체 위에서 정의된 선형점화식 수열을 효율적으로 발생시킬 수 있다. 이러한 수열의 특성은 점화식에 의해 유도되는 특성다항식에 의하여 결정된다[4,5]. n개의 셀과 선형 피드백 함수(Linear feedback function) f(s0,s1,⋯,sn-1) 로 구성되는 n차 LFSR은 식(1)과 같다[6].

    image

    여기서 s0,s1,⋯,sn-1는 레지스터에 입력되는 초깃값이고 c0,c1,⋯,cn-1GF(2) 이다.

    그림1n차 LFSR의 구조이다. 식(1)에 대한 다항식 cT(x) = xn + cn-1 xn-1 + ⋯ + c0를 LFSR의 특성다항식 (Characteristic polynomial)이라 한다[7].

    다음은 본 논문에서 사용되는 용어에 대한 정의이다.

    <정의2.1[8-10]>

    다항식 f(x) = xn + cn-1 xn-1 + cn-2 xn-2 + ⋯ + c1x + c0 (ciGF(2), 0 ≤ in-1)에 대해 아래와 같은 n × n 행렬 Tf (x)의 동반행렬(Companion matrix)이라고 하고[7], 다음 식(2)와 같이 4가지 형태로 나타낼 수 있다.

    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 에 대하여 다음이 성립한다.

    image

    앞으로 cT(x) = mT(x) = xn-1(x+1)인 2개의 끌개를 갖는 패턴분류기를 로 나타내기로 한다.

    <정의 2.3[3]> 의존벡터(Dependency Vector, 이하 DV)는 n비트 패턴들로 구성된 벡터공간의 부분공간 의 모든 원소에 대하여 성립하는 변수들 간의 선형 종속 관계이다. DV와 0-트리의 성분의 내적은 0이다.

    DV = (101)인 패턴분류기 의 상태전이행렬 TM3은 다음 식(4)과 같이 두 가지 경우가 있다.

    image

    Ⅲ LFSR 기반의 패턴분류기

    이 절에서는 LFSR을 이용한 패턴분류기를 생성하고 0-기본경로를 이용하여 DV를 구할 수 있는 방법을 제안한다. n-셀 패턴분류기 의 상태전이행렬 TMn에 대하여 CTMn(x) = mTMn(x) = xn-1(x+1)이 성립한다. 이때 끌개의 개수는 2개이고, 0-트리의 상태의 개수는 2n-1개다. 그리고 rank(TMn) = n-1이다. cTMn(x) = mTMn(x) = xn-1(x+1)인 n-셀 패턴분류기 의 상태전이행렬 TMn에 대하여 대각성분의 1의 개수는 홀수이다.

    <정리 3.1[12]> 상태전이행렬이 TMnn-셀 패턴분류기 의 상태전이그래프에서, x가 0-트리의 한 도달불가능상태일 때 DV는 0-기본경로 의 성분을 각 행으로 하는 행렬 (B0)의 영공간 N(B0)의 기저벡터이고 유일하다.

    위 정리로부터 0-트리의 도달불가능상태를 알면 0-기본경로를 알 수 있으므로 DV를 구하기가 쉽다는 것을 알 수 있다.

    LFSR 기반의 n-셀 패턴분류기 의 상태전이행렬 TMn은 다음 식(5)과 같이 4가지 형태로 나타낼 수 있다.

    image

    <정리 3.2> 길이가 n인 LFSR 기반의 패턴분류기 의 상태전이행렬 TMn에 대하여, ei 를 크기가 n이고 i번째 성분이 1인 단위벡터 일 때, 의 상태전이그래프에서 0-트리의 한 도달불가능한 상태 x는 다음과 같다.

    증명> 의 상태전이그래프에서 0-트리의 도달가능상태는 T의 모든 열들의 일차결합으로 표현된다.

    먼저 (i)에 대하여 첫 번째 행이 영벡터이므로 TMne1e1이다. 그런데 의 모든 열들의 일차결합으로 표현되지 않으므로 0-트리의 도달불가능 상태가 된다. 따라서 의 0-트리의 도달불가능한 상태이다.

    (ii)는 (i)과 같은 방법으로 증명할 수 있다.

    (iii)에서 은 1행과 2행이 같다. y를 라 하면 을 만족한다. 그런데 의 모든 열들의 일차결합으로 표현되지 않는다. 그리고 이므로 의 모든 열들의 일차결합으로 표현되지 않으므로 0-트리의 도달 불가능상태가 된다. 따라서 의0-트리의 도달불가능한 상태이다.

    (iv)는 (iii)과 같은 방법으로 증명할 수 있다. □

    <정리 3.3> 길이가 n인 LFSR 기반의 패턴분류기 의 상태전이행렬 에 대하여 DV는 다음과 같다.

    image

    증명> (i) 을 상태전이행렬로 갖는 의 상태 전이그래프에서 0-트리의 한 도달불가능상태는 정리 3.2에 의하여 x = (110 ⋯ 0)t 이고 0-기본경로 는 (110 ⋯ 0)t → (011 ⋯ 0)t → ⋯ → (000 ⋯ 0)t이다. 또한 0-기본경로의 성분을 각 행으로 하는 행렬 B0는 식(6)과 같다.

    image

    따라서 N(B0) = {(00 ⋯ 0)t, (11 ⋯ 1)t}이므로 정리 3.2에 의하여 DV = (1 ⋯ 1)이다.

    (ii) , (iii), (iv)는 (i)과 같은 방법으로 증명할 수 있다.

    표 1n-셀 LFSR 기반의 패턴분류기 에 대하여 상태전이행렬 에 대응하는 상태전이 그래프에서 0-트리의 한 도달불가능한 상태와 의 DV를 나타낸다.

    <예제 3.1> 길이가 4인 LFSR 기반의 패턴분류기 의 상태전이행렬이 이라 하자. 은 식(7)과 같고, 0이 아닌 끌개는 1이고 도달불가능상태는 정리 3.2에 의해 x = (1100)t이다.

    image
    image
    image

    따라서 N(B0) = {(0000)t, (1111)t}이므로 DV = (1111)이다.

    길이가 4인 LFSR 기반의 패턴분류기 의 상태전이행렬 에 대하여 DV표 2와 같다.

    Ⅳ. LFSR 기반의 패턴분류기 합성

    이 절에서는 주어진 DV에 대응하는 LFSR 기반의 패턴분류기를 합성하는 방법을 제안한다.

    [1,12]에서 언급한 인 경우와 DV = (0∗⋯∗0)인 경우를 제외하고 n-셀 DV에 대응하는 패턴분류기 의 상태전이행렬 TMn를 구성하는 방법이다. 다음 정리는 주어진 DV에 대응하는 LFSR 기반의 패턴분류기를 합성하는 방법이다.

    <정리4.1> 길이가 n인 LFSR 기반의 패턴분류기 의 상태전이행렬 TMn에 대하여 n-셀 패턴분류기 의 상태전이행렬 TMn은 다음 표 3과 같다.

    여기서 DV = (101) 인 패턴분류기 의 상태전이행렬 TM3은 다음 식(4)과 같다.

    증명> 정리 3.2에 의하여 도달불가능상태 x는 (110 ⋯ 0)t이고 0-기본경로((110 ⋯ 0)t → (0110 ⋯ 0)t → ⋯ → (0 ⋯ 0110)t → (0 ⋯ 010)t → (0 ⋯ 001)t의 성분을 각 행으로 하는 행렬 B0는 식(9)과 같다.

    image

    N(B0) = {(00 ⋯ 00)t, (1 ⋯ 10)t} 이므로 DV = (1 ⋯ 10 ⋯ 0)이다.

    (ii), (iii), (iv), (v), (vi)의 경우 (i)과 같은 방법으로 증명할 수 있다.

    <예제 4.1> (i) DV = (11110)인 LFSR 기반의 패턴분류기 의 상태전이행렬 TM5은 식(10)과 같다.

    image

    (ii) DV = (11101)인 LFSR 기반의 패턴분류기 의 상태전이행렬 TM5은 식(11)과 같다.

    image

    (iii) DV = (00101)인 LFSR 기반의 패턴분류기 의 상태전이행렬 TM5은 식(12)와 같다.

    image

    <예제 4.2> (i) DV = (1101000)인 LFSR 기반의 패턴분류기 의 상태전이행렬 TM7은 식(13)과 같다.

    image

    (ii) DV = (1101000)인 LFSR 기반의 패턴분류기 의 상태전이행렬 TM7은 식(14)와 같다.

    image

    다음은 LFSR 기반의 패턴분류기 합성에 대한 알고리즘이다.

    Ⅴ. 결 론

    본 논문에서는 LFSR 기반의 패턴분류기를 생성하 였다. 생성한 LFSR 기반의 패턴분류기의 분석을 통해 상태전이그래프에서 0-트리의 한 도달불가능상태를 찾 는 방법을 제안하였고 이를 통해 DV를 구하는 시간을 효과적으로 줄였다. 또한 주어진 길이가 nDV에 대응하는 LFSR 기반의 패턴분류기 의 상태전이행렬 TMn을 기본형이 되는 TMi를 합성하여 생성하는 방법을 제안하였다.

  • 1. Ganguly N. 2003 “Cellular Automata Evolution: Theory and Applications in Pattern Recognition and Classification,” google
  • 2. Krishna C., Jas A., Touba N.A. 2004 “Achieving high encoding efficiency with partial dynamic LFSR reseeding,” [ACM Trans. Design Automation of Electronic Systems] Vol.9 P.500-516 google doi
  • 3. Maji P., Shaw C., Ganguly N., Sikdar B.K., Chaudhuri P.P. 2003 “Theory and application of cellular automata for pattern classification,” [Fundamenta Informaticae] Vol.58 P.321-354 google
  • 4. Krishna C., Jas A., Touba N.A. 2004 “Achieving high encoding efficiency with partial dynamic LFSR reseeding,” [ACM Trans. Design Automation of Electronic Systems] Vol.9 P.500-516 google doi
  • 5. Krishna C.C., Touba N.A. 2002 “Reducing test data volume using LFSR reseeding with seed compression,” [in Proc. IEEE ITC] P.321-330 google
  • 6. Golomb S. 1967 Shift Register Sequences google
  • 7. Lidl R., Niederreiter H. 1997 Finite Fields google
  • 8. 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.] Vol.42 P.340-352 google
  • 9. Chaudhuri P.P., Chowdhury D.R., Nandy S., Chattopadhyay C. 1997 Additive Cellular Automata; Theory and Applications google
  • 10. 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] Vol.36 P.979-986 google doi
  • 11. Strang G. 2009 Introduction to Linear Algebra google
  • 12. 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] Vol.8751 P.408-416 google
  • [] 
  • [그림 1.] LFSR의 구조
    LFSR의 구조
  • [] 
  • [] 
  • [] 
  • [] 
  • [] 
  • [] 
  • [표 1.] n-셀 LFSR 기반의 패턴분류기
    n-셀 LFSR 기반의 패턴분류기
  • [] 
  • [] 
  • [] 
  • [그림 2.] 의 상태전이그래프
    의 상태전이그래프
  • [표 2.] n-셀 LFSR 기반의 패턴분류기 ?4M
    n-셀 LFSR 기반의 패턴분류기 ?4M
  • [표 3.] n-셀 LFSR 기반의 패턴분류기 ?nM
    n-셀 LFSR 기반의 패턴분류기 ?nM
  • [] 
  • [] 
  • [] 
  • [] 
  • [] 
  • [] 
  • []