코스타스 배열

수학에서 코스타스 배열은 기하학적으로 n개의 점 집합으로 간주될 수 있으며, 각 행 또는 열이 한 점만을 포함하고 각 점 쌍 사이의 모든 n(n - 1)/2 변위 벡터가 구별되도록 n×n 사각 타일링의 사각형 중심에 각각 있다.이것은 이상적인 "썸택" 자동 근접 기능을 만들어, 그 배열을 소나 레이더와 같은 어플리케이션에서 유용하게 만든다.코스타스 배열은 1차원 골롬 지배자 구조의 2차원 사촌격으로 볼 수 있으며, 수학적 관심사는 물론 실험 설계와 단계별 배열 레이더 공학에서도 유사한 응용을 가지고 있다.

코스타스 배열은 존 P의 이름을 따서 명명되었다. 코스타스는 1965년 기술보고서에서 이들에 대해 처음 썼다.독립적으로, 에드거 길버트도 같은 해에 코스타스 어레이를 구축하는 로그리틱 웰치 방식으로 알려진 것을 출판하면서, 이들에 대해 썼다.^[1]

수치표현상

코스타스 배열은 n×n 숫자의 배열로 숫자로 나타낼 수 있으며, 각 항목은 점의 경우 1, 또는 점이 없는 경우 0이다.이항 행렬로 해석될 때, 이러한 숫자의 배열은 각 행과 열에 오직 한 점만을 갖는 제약조건이 있기 때문에, 따라서 순열 행렬이 되는 속성을 가진다.따라서 주어진 n에 대한 코스타스 배열은 순서 n의 순열 매트릭스의 하위 집합이다.

배열은 일반적으로 모든 행에 대한 열을 지정하는 일련의 지수로 설명된다.어떤 컬럼이든 1점만 있다고 주어지기 때문에 배열을 1차원적으로 나타낼 수 있다.예를 들어, 다음은 유효한 코스타스 배열의 순서 N = 4이다.

0	0	0	1
0	0	1	0
1	0	0	0
0	1	0	0

좌표에 점들이 있다: (1,2), (2,1), (3,3) (4,4)

x 좌표가 선형적으로 증가하기 때문에, 우리는 이것을 모든 y 좌표의 집합으로 속기할 수 있다.그러면 세트에서 위치가 x 좌표일 것이다.관찰: {2,1,3,4}이(가) 앞서 언급한 어레이를 설명할 것이다.따라서 주어진 N 순서에 따라 배열을 쉽게 통신할 수 있다.

알려진 배열

코스타스 어레이 수는 주문 1부터 29까지로^[2] 알려져 있다(OEIS의 순서 A008404).

주문	숫자
1	1
2	2
3	4
4	12
5	40
6	116
7	200
8	444
9	760
10	2160
11	4368
12	7852
13	12828
14	17252
15	19612
16	21104
17	18276
18	15096
19	10240
20	6464
21	3536
22	2052
23	872
24	200
25	88
26	56
27	204
28	712
29	164

다음은 알려진 배열:N = 1 {1}

N = 2 {1,2} {2,1}

N = 3 {1,3,2} {2,1,3} {2,3,1} {3,1,2}

N = 4 {1,2,4,3} {1,3,4,2} {1,4,2,3} {2,1,3,4} {2,3,1,4} {2,4,3,1} {3,1,2,4} {3,2,4,1} {3,4,2,1} {4,1,3,2} {4,2,1,3} {4,3,1,2}

N = 5 {1,3,4,2,5} {1,4,2,3,5} {1,4,3,5,2} {1,4,5,3,2} {1,5,3,2,4} {1,5,4,2,3} {2,1,4,5,3} {2,1,5,3,4} {2,3,1,5,4} {2,3,5,1,4} {2,3,5,4,1} {2,4,1,5,3} {2,4,3,1,5} {2,5,1,3,4} {2,5,3,4,1} {2,5,4,1,3} {3,1,2,5,4} {3,1,4,5,2} {3,1,5,2,4} {3,2,4,5,1} {3,4,2,1,5} {3,5,1,4,2} {3,5,2,1,4} {3,5,4,1,2} {4,1,2,5,3} {4,1,3,2,5} {4,1,5,3,2} {4,2,3,5,1} {4,2,5,1,3} {4,3,1,2,5} {4,3,1,5,2} {4,3,5,1,2} {4,5,1,3,2} {4,5,2,1,3} {5,1,2,4,3} {5,1,3,4,2} {5,2,1,3,4} {5,2,3,1,4} {5,2,4,3,1} {5,3,2,4,1}

N = 6 {1,2,5,4,6,3} {1,2,6,4,3,5} {1,3,2,5,6,4} {1,3,2,6,4,5} {1,3,6,4,5,2} {1,4,3,5,6,2} {1,4,5,3,2,6} {1,4,6,5,2,3} {1,5,3,4,6,2} {1,5,3,6,2,4} {1,5,4,2,3,6} {1,5,4,6,2,3} {1,5,6,2,4,3} {1,5,6,3,2,4} {1,6,2,4,5,3} {1,6,3,2,4,5} {1,6,3,4,2,5} {1,6,3,5,4,2} {1,6,4,3,5,2} {2,3,1,5,4,6} {2,3,5,4,1,6} {2,3,6,1,5,4} {2,4,1,6,5,3} {2,4,3,1,5,6} {2,4,3,6,1,5} {2,4,5,1,6,3} {2,4,5,3,6,1} {2,5,1,6,3,4} {2,5,1,6,4,3} {2,5,3,4,1,6} {2,5,3,4,6,1} {2,5,4,6,3,1} {2,6,1,4,3,5} {2,6,4,3,5,1} {2,6,4,5,1,3} {2,6,5,3,4,1} {3,1,2,5,4,6} {3,1,5,4,6,2} {3,1,5,6,2,4} {3,1,6,2,5,4} {3,1,6,5,2,4} {3,2,5,1,6,4} {3,2,5,6,4,1} {3,2,6,1,4,5} {3,2,6,4,5,1} {3,4,1,6,2,5} {3,4,2,6,5,1} {3,4,6,1,5,2} {3,5,1,2,6,4} {3,5,1,4,2,6} {3,5,2,1,6,4} {3,5,4,1,2,6} {3,5,4,2,6,1} {3,5,6,1,4,2} {3,5,6,2,1,4} {3,6,1,5,4,2} {3,6,4,5,2,1} {3,6,5,1,2,4} {4,1,2,6,5,3} {4,1,3,2,5,6} {4,1,6,2,3,5} {4,2,1,5,6,3} {4,2,1,6,3,5} {4,2,3,5,1,6} {4,2,3,6,5,1} {4,2,5,6,1,3} {4,2,6,3,5,1} {4,2,6,5,1,3} {4,3,1,6,2,5} {4,3,5,1,2,6} {4,3,6,1,5,2} {4,5,1,3,2,6} {4,5,1,6,3,2} {4,5,2,1,3,6} {4,5,2,6,1,3} {4,6,1,2,5,3} {4,6,1,5,2,3} {4,6,2,1,5,3} {4,6,2,3,1,5} {4,6,5,2,3,1} {5,1,2,4,3,6} {5,1,3,2,6,4} {5,1,3,4,2,6} {5,1,6,3,4,2} {5,2,3,1,4,6} {5,2,4,3,1,6} {5,2,4,3,6,1} {5,2,6,1,3,4} {5,2,6,1,4,3} {5,3,2,4,1,6} {5,3,2,6,1,4} {5,3,4,1,6,2} {5,3,4,6,2,1} {5,3,6,1,2,4} {5,4,1,6,2,3} {5,4,2,3,6,1} {5,4,6,2,3,1} {6,1,3,4,2,5} {6,1,4,2,3,5} {6,1,4,3,5,2} {6,1,4,5,3,2} {6,1,5,3,2,4} {6,2,1,4,5,3} {6,2,1,5,3,4} {6,2,3,1,5,4} {6,2,3,5,4,1} {6,2,4,1,5,3} {6,2,4,3,1,5} {6,3,1,2,5,4} {6,3,2,4,5,1} {6,3,4,2,1,5} {6,4,1,3,2,5} {6,4,5,1,3,2} {6,4,5,2,1,3} {6,5,1,3,4,2} {6,5,2,3,1,4}

200개 주문,^[3] 500개^[4] 주문 및 1030개^[5] 주문에 대해 알려진 코스타스 어레이를 열거할 수 있다.이러한 코스타스 배열의 목록과 데이터베이스는 거의 완성될 가능성이 있지만, 이 목록에 없는 29개 이상의 주문을 가진 다른 코스타스 배열은 존재할 수 있다.

시공

웰치

웰치-코스타스 어레이, 또는 그냥 웰치 어레이는 다음 방법을 사용하여 생성된 코스타스 어레이로, 1965년 에드거 길버트에 의해 처음 발견되었고 1982년 로이드 R에 의해 재발견되었다. Welch. Welch-Costas 어레이는 원시 루트 g를 취하고 어레이 ${\displaystyle A_{}}$를 $A{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle 1}$ ${\displaystyle A_{i},j}=1}(j$${\displaystyle }j$ ${\displaystyle {}^{}}$ ${\displaystyle mod}$ p ${\displaysty j\equiv$ g$^{i}{\bmod$ {$p},$그 밖의 경우)로 정의하여 생성된다.결과는 크기 p - 1의 코스타스 배열이다.

예:

3은 원시 원소 모듈로 5이다.

3¹ = 3 ≡ 3 (모드 5)

3² = 9≡ 4 (모드 5)

3³ = 27≡ 2 (모드 5)

3⁴ = 81≡ 1 (모드 5)

따라서 [3 4 2 1]은 코스타스 순열이다.좀 더 구체적으로 말하자면, 이것은 기하급수적인 웰치 배열이다.배열의 전위치는 로그 웰치 배열이다.

특정 크기에 대해 존재하는 Welch-Costas 어레이의 수는 전체 함수에 따라 달라진다.

렘펠-골롬

렘펠-골롬 구조는 α와 β를 유한장 GF(q)의 원시 요소로 삼고,${\displaystyle {}_{}}$${\displaystyle {\alpha }^{}}$ i${\displaystyle {}^{}}$+ ${\displaystyle {}^{}}$ ${\displaystyle j^{}}$=${\displaystyle {}_{}}$${\displaystyle 1}$ ${\displaystyle$ $A_$${i}=1$$}$을(를$)$ 다르게 정의한다$.$결과는 크기 q - 2의 코스타스 배열이다. α + β = 1이면 첫 번째 행과 열을 삭제하여 크기 q - 3의 또 다른 코스타스 배열을 형성할 수 있다: 그러한 원시 요소 쌍은 모든 primary power q>2에 존재한다.

테일러, 렘펠, 골롬의 확장자

1열이나 1쌍을 구석에 두고 한 줄/칼럼이나 두 줄이나 한 쌍을 더하거나 빼서 새로운 코스타스 배열의 세대는 세대 방법에^[6] 초점을 맞춘 논문과 골롬과 테일러의 랜드마크 1984년 논문에 발표되었다.^[7]

웰치, 렘펠 또는 골롬브 발전기가 생성한 기존 코스타스 어레이의 행과 열을 삭제하여 새로운 코스타스 어레이를 생성하는 보다 정교한 방법이 1992년에 출판되었다.^[8]이러한 발전기가 코스타스 어레이를 생산하는 순서에 상한이 없다.

기타 방법

행과 열을 더 복잡하게 추가 또는 삭제하는 방법을 사용하여 최대 52개의 코스타스 배열을 발견한 두 가지 방법이 2004년과^[9] 2007년에 출판되었다.^[10]

변형

육각 격자 위의 코스타스 배열을 벌집 배열이라고 한다.이러한 배열은 6각형 모양으로 배열된 원소의 수가 홀수일 수밖에 없는 것으로 나타났다.현재 12개의 그러한 배열(대칭까지)이 알려져 있는데, 이는 총수로 추측되어 왔다.^[11]

참고 항목

• 순열
• 디헤드랄군
• 조합 설계

메모들

참조

• Barker, L.; Drakakis, K.; Rickard, S. (2009), "On the complexity of the verification of the Costas property" (PDF), Proceedings of the IEEE, 97 (3): 586–593, doi:10.1109/JPROC.2008.2011947, archived from the original (PDF) on 2012-04-25, retrieved 2011-10-10.
• Beard, James (March 2006), "Generating Costas Arrays to Order 200", 2006 40th Annual Conference on Information Sciences and Systems, IEEE, doi:10.1109/ciss.2006.286635.
• Beard, James K. (March 2008), "Costas array generator polynomials in finite fields", 2008 42nd Annual Conference on Information Sciences and Systems, IEEE, doi:10.1109/ciss.2008.4558709.
• Beard, James K. (2017), Costas arrays and enumeration to order 1030, IEEE Dataport, doi:10.21227/H21P42.
• Beard, J.; Russo, J.; Erickson, K.; Monteleone, M.; Wright, M. (2004), "Combinatoric collaboration on Costas arrays and radar applications", IEEE Radar Conference, Philadelphia, Pennsylvania (PDF), pp. 260–265, doi:10.1109/NRC.2004.1316432, archived from the original (PDF) on 2012-04-25, retrieved 2011-10-10.
• Beard, James; Russo, Jon; Erickson, Keith; Monteleone, Michael; Wright, Michael (April 2007), "Costas array generation and search methodology", IEEE Transactions on Aerospace and Electronic Systems, 43 (2): 522–538, doi:10.1109/taes.2007.4285351.
• Costas, J. P. (1965), Medium constraints on sonar design and performance, Class 1 Report R65EMH33, G.E. Corporation
• Costas, J. P. (1984), "A study of a class of detection waveforms having nearly ideal range-Doppler ambiguity properties" (PDF), Proceedings of the IEEE, 72 (8): 996–1009, doi:10.1109/PROC.1984.12967, archived from the original (PDF) on 2011-09-30, retrieved 2011-10-10.
• Drakakis, Konstantinos; Rickard, Scott; Beard, James K.; Caballero, Rodrigo; Iorio, Francesco; O'Brien, Gareth; Walsh, John (October 2008), "Results of the Enumeration of Costas Arrays of Order 27", IEEE Transactions on Information Theory, 54 (10): 4684–4687, doi:10.1109/tit.2008.928979, hdl:2262/59260.
• Drakakis, Konstantinos; Iorio, Francesco; Rickard, Scott (2011), "The enumeration of Costas arrays of order 28 and its consequences", Advances in Mathematics of Communications
• Drakakis, Konstantinos; Iorio, Francesco; Rickard, Scott; Walsh, John (August 2011), "Results of the enumeration of Costas arrays of order 29", Advances in Mathematics of Communications, 5 (3): 547–553, doi:10.3934/amc.2011.5.547.
• Gilbert, E. N. (1965), "Latin squares which contain no repeated digrams", SIAM Review, 7: 189–198, doi:10.1137/1007035, MR 0179095.
• Golomb, Solomon W. (1984), "Algebraic constructions for Costas arrays", Journal of Combinatorial Theory, Series A, 37 (1): 13–21, doi:10.1016/0097-3165(84)90015-3, MR 0749508.
• Golomb, Solomon W. (1992), "The ${\displaystyle T_{4}}$ and ${\displaystyle G_{4}}$ constructions for Costas arrays", IEEE Transactions on Information Theory, 38 (4): 1404–1406, doi:10.1109/18.144726, MR 1168761
• Golomb, S. W.; Taylor, H. (1984), "Construction and properties of Costas arrays" (PDF), Proceedings of the IEEE, 72 (9): 1143–1163, doi:10.1109/PROC.1984.12994, archived from the original (PDF) on 2011-09-30, retrieved 2011-10-10.
• Guy, Richard K. (2004), "Sections C18 and F9", Unsolved Problems in Number Theory (3rd ed.), Springer Verlag, ISBN 0-387-20860-7.
• Moreno, Oscar (1999), "Survey of results on signal patterns for locating one or multiple targets", in Pott, Alexander; Kumar, P. Vijay; Helleseth, Tor; et al. (eds.), Difference Sets, Sequences and Their Correlation Properties, NATO Advanced Science Institutes Series, vol. 542, Kluwer, p. 353, ISBN 0-7923-5958-5.
• Rickard, Scott (2004), "Searching for Costas Arrays using Periodicity Properties", IMA International Conference on Mathematics in Signal Processing.

외부 링크

• MacTech 1999 Programmer's 챌린지:코스타스 배열
• 온라인 정수 시퀀스 백과사전:
  • A008404: 순서가 n인 코스타스 배열의 수(회전 및 플립을 구별하여 계산함)
  • A001441: 분면 그룹 아래의 불평등 코스타스 배열 수입니다.
• "Costas array", Encyclopedia of Mathematics, EMS Press, 2001 [1994]