LFSR 원리와 C코드 만들어보기(2)

 

https://jun-study.tistory.com/39

LFSR 원리와 C 코드 만들어보기 (1)

자 추가적으로 이와 관련되어 글을 써보려 한다. 

위에서 언급한 LFSR 알고리즘은 Fibonacci LFSR 이다. 추가적인 설명을 하자면 

출처 : 위키피디아 , wikipedia

1) The bit positions that affect the next state are called the taps. : 위에 diagram에서 index로 11,13,14,16번이 tap인 것을 알 수 있다. 

2) The Taps are calculated by XOR seqeuntially and the result of last calculation fed back into the leftmost bit.

: 가장 오른쪽에 있는 tap 부터 순차적으로 XOR 연산이 이뤄지고 그 결과는 가장 leftmost bit로 들어가고 나머지 bit들은 right shift된다. 

3) 이를 feedback polynomial로 표현하면 X^16 + X^14 + X^13+ X^11 + 1. 로 표현 할 수 있다. 

 

 

C 코드는 직관적이다. 

unsigned int start_state = 0xACE1FFBCu; // Initial 32 bit Seed
unsigned int lfsr = start_state;
unsigned int bit;
unsigned int period = 0;

// feedback polynomial : x^32+x^30+x^29+x^27+x^24+1
do
{
	bit = ((lfsr>>0)^(lfsr>>2)^(lfsr>>3)^(lfsr>>5)^(lfsr>>8)) & 1u;
    lfsr = (lfsr>>1) | (bit<<15);
    period = period + 1;
}
while(lfsr != start_state);

start_state는 초기 seed값이라고 생각하면 된다. 

do 안에 있는 bit는 xor을 순차적으로 계산하는 것이고 

lfsr = (lfsr>>1) | (bit<<15) 는 seed를 1bit right shift하고 위에서 계산한 순차적인 결과를 가장 leftmost bit에 넣는 것을 나타낸 것이다.  

 

 

또 다른 LFSR이 있다. 이는 Galois LFSR이다.  이는 다음글에 작성할 예정이다.