The theory of m-sequences

Presentation on theme: "The theory of m-sequences"— Presentation transcript:

1 The theory of m-sequences
Problems 13, 14 2001년 6월 기 영 민 연세대학교 전기전자공학과 기 영 민 <유한체 이론 및 응용>

2 Problem 13 13. Prove the following two facts about C(x,y)
a. C(x,y) must have the same parity as n. b. For every number c between +n and –n such that c  n (mod 2), there exist sequences x and y such that C(x,y) = c. 기 영 민 <유한체 이론 및 응용>

3 Problem 13 a. (증명) Lemma 10.3을 참조, C(x,y) = n - 2w1 - 2w2 + 4n1,1
그러므로, C(x,y)는 n과 같은 기우성(parity)을 가진다. b. (증명) 문제를 풀이하면, 만약, n이 짝수일 때 -n~n까지의 모든 짝수 값을, C(x,y)가 가질 수 있도록 하는 x와 y가 존재한다는 것 이며, n이 홀수일때 -n~n까지의 모든 홀수 값을 C(x,y)가 가질 수 있도록 하는 x와 y가 존재한다는 뜻이다. 이미 a)에서 C(x,y)와 n이 같은 기우성이라는 것을 증명했으므 로, 이제, C(x,y)가 –n~n 사이의 값이고, 모든 n-2k형태에 대해 존 재한다는 것만 보이면 된다. 기 영 민 <유한체 이론 및 응용>

4 Problem 13 C(x,y)는 반드시 –n~n 사이의 값이다. (증명 생략)
C(x,y) = n(x와 y가 서로 같을 때), C(x,y)=-n(x와y가 서로 다를 때)가 존재하고, C(x,y) = n-2k가 존재하면, (단, -n <n-2k<n이고, k는 이를 만족 하는 정수) C(x’,y’) = n-2k+2는 x와 y가 다르던 위치 하나가 수정되어 같아 지면 된다. 즉, C(x’, y’) = C(x, y) +2가 된다. C(x’,y’)=n-2k-2는 x와 y가 같던 위치 하나가 수정되어 달라지면 된다. 즉, 즉, C(x’, y’) = C(x, y) -2가 된다. <증명 끝> 기 영 민 <유한체 이론 및 응용>

5 Problem 14 14. Any m-sequences can be used to construct a continuous function of time with some interesting properties. In this problem we will investigate this construction. If (sn) is an m-sequence with period 2m-1, define the real-valued function S(t) as follows: 기 영 민 <유한체 이론 및 응용>

6 Problem 14 where t0 is a fixed positive number. For values t which are not integer multiples of t0, S(t) is defined by linear interpolation. a. What is the period of the function S(t)? b. The autocorrelation function of the function S(t) is defined to be Where T0 is the period of S(t) found in part (a). Find C() explicitly. Compare your result to Theorem 10.5. 기 영 민 <유한체 이론 및 응용>

7 Problem 14 a. 주기 T0 = (2m-1)t0이다. (풀이) t = at0 (a는 정수)에 대해,
S(t+T0) = S(at0 + (2m-1)t0) = sa+2m-1 = sa = S(t) 반면, T’ < (2m-1)t0에 대해, T’ = ct0 라 하면, S(t+T’) = S((a+c) t0) = sa+c  sa = S(t) 이제, t가 t0 의 정수배가 아닐 때, t = bt0이면, a는 정수, 기 영 민 <유한체 이론 및 응용>

8 Problem 14 S(t) = S(bt0) = kS(at0) + (1-k)S((a+1) t0)
= ksa + (1-k)sa+1에서, S(t+T0) = S(bt0+T0) = kS(at0+T0) + (1-k)S((a+1) t0+T0) = ksa+ 2m-1 + (1-k)sa+1+ 2m-1 = ksa + (1-k)sa+1 = S(t) T’ < (2m-1)t0에 대해, T’= ct0라 하면, S(t+T’) = S(bt0+T’) = kS(at0+ ct0) + (1-k)S((a+1) t0+ ct0) = ksa+ c + (1-k)sa+1+c  ksa + (1-k)sa+1 = S(t) 그러므로, 주기 T0 = (2m-1)t0이다. 기 영 민 <유한체 이론 및 응용>

9 Problem 14 b. (1)  =kT0 일때, (단, k는 정수) 이 때, t0구간에서, S(t)2는 그림과
같은 두 가지 꼴 중의 하나로 나타난다. 이 중 (a)가 2m-1-1번 (b)가 2m-1번 나타난다. (a)의 적분 값은 t0, (b)의 적분값은 t0/3이므로, (왜냐하면, Theorem 10.5에서 C(1) = -1이므로) 기 영 민 <유한체 이론 및 응용>

10 Problem 14 (2)  =kt0 일때, (단, k는 정수이며, 2m-1의 배수가 아님)
이 때, S(t)S(t+)는 그림과 같은 꼴 중의 하나로 나타난다. 이 중, (a), (b)의 적분값은 +t0, -t0, (c), (d) 는 +t0/3, -t0/3, (e), (f)는 0이다. 이들은 m-sequence의 랜덤함에 의해, 즉, (a)와 (b)의 개수가 비슷하게, (c) 와 (d)의 개수가 비슷하게 분포한다. 그러나, m-sequence의 주기가 홀수이기때문에, 다음과 같은 4가지 경우의 수가 발생한다 기 영 민 <유한체 이론 및 응용>

11 Problem 14 ① (a) 또는 (b)가 1개 더 많다(이 때는 (c)와 (d)의 개수는 같다).
② (c) 또는 (d)가 1개 더 많다(이 때는 (a)와 (b)의 개수는 같다). ③ (a)가 (b)보다 1개 많고, (d)가 (c)보다 2개 많다. ④ (b)가 (a)보다 1개 많고, (c)가 (d)보다 2개 많다. ①은 t0, ②는 t0/3, ③은 t0/3, ④는 -t0/3의 자기상관 함수를 얻는다. 즉, 이다. 위 ①,②,③,④의 경우에 대한 경우의 수는 m-sequence에 따라 다르다. 기 영 민 <유한체 이론 및 응용>

12 Problem 14 예) m = 3인 3-sequence에 대해, st = 0010111일 때, C(0) = 13t0/3 t
(a) (b) (c) (d) (e) (f) 경우 C(t) 1 ③ t0/3 2 ① -t0 3 4 5 6 기 영 민 <유한체 이론 및 응용>

13 Problem 14 (3)  kt0 일때, (단, k는 정수)
(1)과 (2)의 구한 값을 Interpolation한 값이다. 그러나, Linear Interpolation이 아닌, Square-Pulse를 이용한 Interpolation이어야 할 것이다. (왜냐하면, Linear Interpolation의 제곱이 되므로) 그러므로, 이와 같은 가정 하에 C(t)를 도시하면 다음 페이지의 그림과 같다. 그리고, 물론 C(t)는 T0의 주기를 갖는다. 점선은 m = 3에 대해 얻은 자기상관 함수의 곡선이고, 실선은 m을 크게 하면서 얻은 근사적인 자기상관 함수의 곡선이다. 대략, Theorem 10.5의 자기상관함수와 비슷한 모양이다. 기 영 민 <유한체 이론 및 응용>

14 Problem 14 Linear Interpolation된 m-sequence의 자기상관함수 기 영 민
<유한체 이론 및 응용>

15 Problem 14 Theorem 10.5의 결과와 비교할 때, C(kT0)에서는 크기가 큰 양의 값을 가지고, 나머지 C(t)에서는 상대적으로 크기가 작은 음의 값을 갖는다는 면에서 비슷하다. 그러나, Theorem 10.5의 자기상관함수는 이상적인 m-sequence의 자기상관 함수이고, 이 문제에서 구한 자기상관 함수는 삼각펄스를 이용하여 구현된 m-sequence의 자기상관 함수이다. 왜냐하면, Linear Interpolation은 각 신호마다 삼각펄스를 곱한 것과 같다. 그러므로, 이 문제에서 구한 자기상관함수는 실제 통신 시스템에서 쓰이는 m-sequence 신호와 많이 유사하다고 볼 수 있다. 기 영 민 <유한체 이론 및 응용>