LFSR( Linear Feedback Shift Register)

 디지털 회로에서 현재 상태에 대한 선형 연산( linear function)으로 다음 상태를 만드는 레지스터다. 해당 연산에는 다양한 종류들이 있겠지만 일반적으로 쓰이는건 XOR이라고 한다. LFSR의 초기값은 Seed라고 부르며 다음 상태를 생성하는 연산에 관여하는 bit는 tap이라고 하며 또한 가장 오른쪽에 있는 bit를 output bit라고 한다.

 

 기본적인 내용은 다음과 같다. LFSR의 초기값을 다음과 같은 8bits로 설정한다.

 

 현재의 상태는 0x59이다. LFSR의 tap이 5, 6, 8번째 bits라고 가정하자.

 현재 상태의 output bit과 tap들을 XOR 연산시킨 값을 MSB로 보낸다.

 

 다음 상태는 0x2C가 되었다. 같은 방법으로 다음 상태를 계속하여 생성할 수 있다. 8bits의 LFSR을 예시로 들었으며 이 경우에 최대 255($2^{8-1}$, 0제외)개의 경우의 수를 가질 수 있다. 모든 경우에 대해 항상 경우의 수가 255가 되는 것은 아니지만 m-bits의 LFSR에 대해 특정 조건을 만족하면 LFSR의 cycle의 maximal length를 가진다고 하며 이 길이는 $2^{m-1}$이 된다.

 

 

Feedback Polynomial

 LFSR에서 다음 상태를 생성하기 위하여 사용되는 tap들의 배열을 유한체의 개념을 사용하여 수학적 표현이 가능하다. 이러한 다항식을 feedback polynomial 혹은 characteristic polynomial이라고 한다.

 

 위의 예시를 참고하면 tap의 배열은 $0'b00001101$이고 5, 6, 8번재 bits가 tap에 해당한다. 이 배열은 GF($2^8$)의 원소로 나타낼 수 있으며 다항식 형태로는 $x^8+x^6+x^5+1$로 표현할 수 있다. 마지막의 1은 결과가 입력되는 bit를 의미한다. 이러한 방법으로 m-bits LFSR의 tap 배열을 GF($2^m$)의 원소에 대응시킬수 있으며 이를 다항식으로 표현한 것이 feedback polynomial이다.

 

 위에서 특수한 경우에 대하여 m-bits LFSR의 cycle이 $2^{m-1}$이 된다고 하였다. 구체적으로 feedback polynomial이 GF($2^m$)의 primitive element의 minimal polynomial이면 해당 다항식을 특성다항식으로 가지는 LFSR의 cycle은 항상 $2^{m-1}$이라는 것이며 역으로도 성립한다.

 

Reference

https://en.wikipedia.org/wiki/Linear-feedback_shift_register

http://www.secmem.org/blog/2019/08/19/Linear-Feedback-Shift-Register