相補配列

生物学における相補配列については、「相補性（分子生物学）」を参照してください。相補的な要素集合を持つ整数配列については、「ランベック・モーザーの定理」を参照してください。

応用数学において、相補数列( CS ) は、位相のずれた非周期自己相関係数の合計がゼロになるという有用な性質を持つ数列のペアです。バイナリ相補数列は、1949 年にMarcel JE Golayによって初めて導入されました。1961～1962 年に Golay は、長さ 2 ^Nの数列を構成するいくつかの方法を示し、長さ 10 と 26 の相補数列の例を示しました。1974 年に RJ Turyn は、長さmとnの数列から長さmnの数列を構成する方法を示し、これにより、2 ^N 10 ^K 26 ^Mの形式の任意の長さの数列を構成できます。

その後、相補配列の理論は他の研究者によって多相相補配列、多段階相補配列、および任意の複雑な相補配列へと一般化された。相補集合も検討されており、これらは2つ以上の配列を含むことができる。

( a ₀ , a ₁ , ..., a _{N − 1}   ) と ( b ₀ , b ₁ , ..., b _{N − 1}   ) を双極性シーケンスのペアとする。つまり、 a ( k ) とb ( k ) の値は +1 または− 1である。シーケンスxの非周期自己相関関数を次のように定義する。

${\displaystyle R_{x}(k)=\sum _{j=0}^{Nk-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) です。                          
• Golay が挙げた長さ 10 の例は (+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, 2, 1) と (10, 3, 0, 1, 0, − 1, 2, 1, − 2, − 1) です。                                  

• 相補的なシーケンスは相補的なスペクトルを持つ。自己相関関数とパワースペクトルはフーリエ対を形成するため、相補的なシーケンスも相補的なスペクトルを持つ。しかし、デルタ関数のフーリエ変換は定数であるため、次のように書くことができる。

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

ここでC _Sは定数である。

S _aとS _bは、シーケンスのフーリエ変換の二乗として定義されます。フーリエ変換は、シーケンスの直接 DFT である場合もあれば、ゼロ パディングされたシーケンスの 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 φ}で乗じても、それらは相補性を維持します。
• どちらかの配列を逆にしても、それらは相補的な関係を保つ。
• どちらかの配列が遅延しても、それらは相補的な関係を維持する。
• 配列を入れ替えても、それらは相補性を維持する。
• 両方の数列に同じ定数（実数または複素数）を乗算すると、それらは相補的な関係を維持する。
• 両方のシーケンスの交互のビットを反転しても、それらは相補性を保ちます。一般に、任意の複素シーケンスの場合、両方のシーケンスにe ^{j π kn / N} (ここでkは定数、nは時間インデックス) を乗算すると、それらは相補性を保ちます。
• 新しい相補配列のペアは、[ a b ] および [ a  − b ] として形成できます。ここで、[..] は連結を表し、aとbは CS のペアです。
• { a b } と { a  − b }という新しいシーケンスのペアを形成できます。ここで、{..} はシーケンスのインターリーブを表します。
• a  + bとa − 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 はGolay 多項式のペアを形成する。例としては、長さが2 のべき乗の相補的な数列を生成するShapiro 多項式がある。

• マルチスリット分光法
• 超音波測定
• 音響測定
• レーダーパルス圧縮
• Wi-Fiネットワーク、
• 3G CDMA無線ネットワーク
• OFDM通信システム
• 列車の車輪検出システム^{[ 1 ] [ 2 ]}
• 非破壊検査（NDT）
• コミュニケーション
• 符号化開口マスクは、相補的な配列の2次元一般化を用いて設計される。

• バイナリゴレイ符号（誤り訂正符号）
• 金の配列
• 笠見シーケンス
• 多相配列
• 擬似乱数バイナリシーケンス（最大長シーケンスまたはMシーケンスとも呼ばれる）
• 三値ゴレイ符号（誤り訂正符号）
• ウォルシュ＝アダマール系列
• ザドフ・チューシーケンス