본 논문에서는 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.
패턴인식의 처리 과정은 패턴의 특징을 파악하여 패턴이 속한 부류로 분류하는 과정으로 구성되며, 패턴인식의 대부분인 분류 작업은 패턴분류기에 의하여 이루어진다. 패턴분류기는 데이터로부터 패턴들의 중요한 특징이나 속성을 추출하여 패턴을 특정한 클래스에 할당한다[1-3]. 패턴분류기의 설계는 작은 저장 공간, 큰 데이터 처리량, 낮은 가격대로 구현하는 것을 고려하여야 한다.
메모리 량을 최소화 할 수 있는 방법으로 Maji 등은 클래스의 수가 2개인 패턴을 효과적으로 분류할 수 있는 MACA(Multiple Attractor Cellular Automata)를 합성하여 패턴분류기를 설계하였다[3]. Maji 등은 의존벡터(Dependency Vector, 이하
본 논문에서는 초기 설정시간을 효과적으로 줄이기 위해 LFSR(Linear feedback shift register) 기반의 패턴 분류기를 생성한다. 생성한 LFSR 기반의 패턴분류기 의 상태전이행렬에 대한 특성을 분석하여 주어진 의 상태전이그래프에서 0-트리의 한 도달불가능한 상태를 구하는 방법을 제안한다. 따라서 에 대응하는
의사난수열 생성, 암호화 시스템 구현 등에 이용되는 LFSR은 시프트 레지스터의 일종으로, 레지스터에 입력되는 값이 이전 상태 값들의 선형 함수로 계산되고 유한체 위에서 정의된 선형점화식 수열을 효율적으로 발생시킬 수 있다. 이러한 수열의 특성은 점화식에 의해 유도되는 특성다항식에 의하여 결정된다[4,5].
여기서
그림1은
다음은 본 논문에서 사용되는 용어에 대한 정의이다.
다항식
<정리 2.2[11]> 임의의
앞으로
<정의 2.3[3]> 의존벡터(Dependency Vector, 이하
이 절에서는 LFSR을 이용한 패턴분류기를 생성하고 0-기본경로를 이용하여
<정리 3.1[12]> 상태전이행렬이
위 정리로부터 0-트리의 도달불가능상태를 알면 0-기본경로를 알 수 있으므로
LFSR 기반의
<정리 3.2> 길이가
증명> 의 상태전이그래프에서 0-트리의 도달가능상태는
먼저 (i)에 대하여 첫 번째 행이 영벡터이므로
(ii)는 (i)과 같은 방법으로 증명할 수 있다.
(iii)에서 은 1행과 2행이 같다. y를 라 하면 을 만족한다. 그런데 의 모든 열들의 일차결합으로 표현되지 않는다. 그리고 이므로 의 모든 열들의 일차결합으로 표현되지 않으므로 0-트리의 도달 불가능상태가 된다. 따라서 의0-트리의 도달불가능한 상태이다.
(iv)는 (iii)과 같은 방법으로 증명할 수 있다. □
<정리 3.3> 길이가
증명> (i) 을 상태전이행렬로 갖는 의 상태 전이그래프에서 0-트리의 한 도달불가능상태는 정리 3.2에 의하여 x = (110 ⋯ 0)
따라서
(ii) , (iii), (iv)는 (i)과 같은 방법으로 증명할 수 있다.
표 1은
n-셀 LFSR 기반의 패턴분류기
<예제 3.1> 길이가 4인 LFSR 기반의 패턴분류기 의 상태전이행렬이 이라 하자. 은 식(7)과 같고, 0이 아닌 끌개는 1이고 도달불가능상태는 정리 3.2에 의해 x = (1100)
따라서
길이가 4인 LFSR 기반의 패턴분류기 의 상태전이행렬 에 대하여
n-셀 LFSR 기반의 패턴분류기 ?4M
이 절에서는 주어진
[1,12]에서 언급한 인 경우와
<정리4.1> 길이가
n-셀 LFSR 기반의 패턴분류기 ?nM
여기서
증명> 정리 3.2에 의하여 도달불가능상태 x는 (110 ⋯ 0)
(ii), (iii), (iv), (v), (vi)의 경우 (i)과 같은 방법으로 증명할 수 있다.
<예제 4.1> (i)
(ii)
(iii)
<예제 4.2> (i)
(ii)
다음은 LFSR 기반의 패턴분류기 합성에 대한 알고리즘이다.
본 논문에서는 LFSR 기반의 패턴분류기를 생성하 였다. 생성한 LFSR 기반의 패턴분류기의 분석을 통해 상태전이그래프에서 0-트리의 한 도달불가능상태를 찾 는 방법을 제안하였고 이를 통해