보완순서

생물학의 보완적 시퀀스는 보완성(분자생물학)을 참조한다.

응용 수학에서, 보완 시퀀스(CS)는 위상 외 주기 자기 상관 계수가 0에 합한 유용한 속성의 시퀀스 쌍이다. 이진 보완 시퀀스는 1949년 마르셀 J. E. 골레이에 의해 처음 도입되었다. 1961–1962년에 골레이는 길이 2의^N 시퀀스를 구성하기 위한 몇 가지 방법을 제시했고 길이 10과 26의 보완 시퀀스의 예를 제시했다. 1974년 R. J. Turyn은 21026^NKM 형식의 어떤 길이의 시퀀스를 구성할 수 있는 길이 m과 n의 시퀀스로부터 길이 mn의 시퀀스를 구성하는 방법을 제공했다.

후에 다른 저자들에 의해 보완 시퀀스 이론이 다단계 보완 시퀀스, 다단계 보완 시퀀스, 임의의 복잡한 보완 시퀀스로 일반화되었다. 보완적인 집합도 고려되었다; 이것들은 세 개 이상의 시퀀스를 포함할 수 있다.

정의

Let (a₀, a₁, a, ...a_{N − 1})와 (b₀, b₁, b, ..., b_{N − 1})는 양극 시퀀스의 한 쌍으로, a(k)와 b(k)는 +1 또는 -1 값을 가지고 있다는 것을 의미한다. 시퀀스 x의 주기적 자기 상관 함수를 정의하도록 두십시오.

${\displaystyle R_{x}(k)=\sum _{j=0}^{{N-k-1}x_{j}x_{j+k}\,}$

다음 경우 시퀀스 a와 b의 쌍은 보완적이다.

${\displaystyle R_{a}(k)+R_{b}(k)=2N,\,}$

k = 0의 경우

${\displaystyle R_{a}(k)+R_{b}(k)=0,\,}$

k = 1, ..., N - 1의 경우.

크론커 델타를 이용하면 다음과 같이 쓸 수 있다.

${\displaystyle R_{a}(k)+R_{b}(k)=2N\delta(k),\,}$

그러므로 우리는 보완 시퀀스의 자기 상관 기능의 합이 델타 함수라고 말할 수 있는데, 이것은 레이더 펄스 압축과 주파수 통신 확산과 같은 많은 응용에 이상적인 자기 상관이다.

예

• 가장 간단한 예로서 길이 2의 순서(+1, +1)와 (+1, -1)가 있다. 그들의 자기 상관 함수는 (2, 1)과 (2, -1)이며, 이 함수는 (4, 0)까지 더해진다.
• 다음 예시(길이 4의 순서)로서 (+1, +1, +1, -1)와 (+1, +1, -1, +1)가 있다. 그들의 자기 상관 함수는 (4, 1, 0, -1)과 (4, -1, 0, 1)이며, 최대 (8, 0, 0, 0)이다.
• 길이 8의 한 예는 (+1, +1, +1, -1, +1, +1, +1)과 (+1, +1, +1, +1, -1, -1, -1, -1, +1)이다. 그들의 자기 상관 함수는 (8, -1, 0, 3, 0, 1, 0, 1)과 (8, 1, 0, -3, 0, -1, 0, -1)이다.
• 골레이가 제시한 길이 10의 예로는 (+1, +1, -1, +1, -1, -1, -1, +1)와 (+1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, +1, -1, +1, +1, -1, +1)가 있다. 그들의 자기 상관 함수는 (10, -3, 0, -1, 0, 1, 2, 1)과 (10, 3, 0, 1, 0, 2, 2, 1)이다.

상호 보완적인 시퀀스 쌍의 속성

• 보완 시퀀스에는 보완 스펙트럼이 있다. 자기 상관 함수와 전력 스펙트럼이 푸리에 쌍을 형성하므로 보완 시퀀스에도 보완 스펙트럼이 있다. 하지만 델타 함수의 푸리에 변환이 상수인 만큼, 우리는 쓸 수 있다.

${\displaystyle S_{a}+S_{b}=C_{S}}$

여기서_S C는 상수다.

S와_a S는_b 시퀀스의 푸리에 변환의 제곱으로 정의된다. 푸리에 변환은 시퀀스의 직접 DFT가 될 수 있고, 패딩이 0인 시퀀스의 DFT가 될 수 있으며, Z = e의^jω Z 변환과 동등한 시퀀스의 연속 푸리에 변환이 될 수 있다.

• CS 스펙트럼은 상한이다. S와_a S는_b 음이 아닌 값이기 때문에 우리는 쓸 수 있다.

${\displaystyle S_{a}=C_{S}-S_{B}<C_{S}}}$

또한

${\displaystyle S_{b}<C_{S}}}$

• CS 쌍의 시퀀스 중 하나가 반전된 경우(-1로 곱함) 그것들은 보완적인 상태를 유지한다. 일반적으로 시퀀스 중 하나에 e를^jφ 곱한 경우 이는 보완적으로 유지된다.
• 두 시퀀스 중 하나가 반전된 경우, 이 시퀀스는 보완적으로 유지된다.
• 두 시퀀스 중 하나가 지연되는 경우, 이 시퀀스는 보완적으로 유지된다.
• 시퀀스가 상호 교환되는 경우, 이 시퀀스는 보완적으로 유지된다.
• 두 시퀀스에 동일한 상수(실제 또는 복합)를 곱한 경우, 두 시퀀스는 상호 보완적으로 유지된다.
• 두 시퀀스가 모두 K에 의해 시간 내에 소멸되는 경우, 그들은 보완적인 상태를 유지한다. 보다 정확히 말하자면, 보완적 쌍(a(k), b(k)에서 우리는 건너뛴 샘플이 버려진 새로운 쌍(a(Nk), b(Nk)을 형성한다면, 새로운 시퀀스는 보완적이다.
• 두 시퀀스의 교대 비트가 반전되면 상호 보완적으로 유지된다. 일반적으로 임의 복합 시퀀스의 경우 두 시퀀스에 e(여기서^jπkn/N k는 상수, n은 시간 지수)를 곱한 경우 이 시퀀스는 보완적으로 유지된다.
• 새로운 쌍의 보완 시퀀스는 [a b]와 [a -b]로 형성될 수 있다. 여기서 [..]는 결합을 나타내고 a와 b는 CS 쌍이다.
• {a b} 및 {a -b}(여기서 {a..)로 새 시퀀스 쌍을 구성할 수 있다.{}은(는) 시퀀스의 인터리빙을 의미한다.
• 새로운 시퀀스 쌍은 + b와 - b로 형성될 수 있다.

골레이 쌍

보완 쌍 a, b는 다항식 A(z) = a(0) + a(1)z + ... + a(N - 1)z로^N−1 인코딩할 수 있으며, B(z)와 유사하게 인코딩할 수 있다. 시퀀스의 상호보완성 특성은 조건과 동일하다.

${\displaystyle \vert A(z)\vert ^{2}+\vert B(z)\vert ^{2}=2N\,}$

단위 원의 모든 z에 대해, 즉 z = 1. 그렇다면 A와 B는 다항식의 골레이 쌍을 형성한다. 예를 들어 샤피로 다항식(Shapiro polyomials)을 들 수 있는데, 이 경우 길이가 2로 보완되는 시퀀스가 발생한다.

보완적 시퀀스의 적용

• 멀티슬릿 분광법
• 초음파 측정
• 음향 측정
• 레이다 맥박 압축
• Wi-Fi 네트워크,
• 3G CDMA 무선 네트워크
• OFDM 통신 시스템
• 트레인 휠 감지 시스템^[1][2]
• 비파괴검사(NDT)
• 커뮤니케이션
• 코드화된 조리개 마스크는 보완 시퀀스의 2차원 일반화를 사용하여 설계된다.

참고 항목

• 바이너리 골레이 코드(오류 수정 코드
• 골드 시퀀스
• 카사미 시퀀스
• 다상 시퀀스
• 유사 길이의 이진 시퀀스(최대 길이 시퀀스 또는 M 시퀀스라고도 함)
• Ternary Golay 코드(오류 수정 코드)
• 월시-하다마드 시퀀스
• 자도프-추 시퀀스

참조