カバーコード

符号理論において、被覆符号とは、空間内の 要素（符号語と呼ばれる）の集合であり、空間内のすべての要素が何らかの符号語から一定の距離内にあるという特性を持つ。

、を整数とします。サイズ| Q | = qのアルファベットQ上のコードは 、すべてのワードに対してハミング距離 となるコードワードが存在する場合、長さnのq 元R被覆コードと呼ばれます 。言い換えると、Cのコードワードの周りのハミング距離 に関する半径Rの球(またはボールまたはルーク領域)は、有限距離空間を使い果たす必要があります。コードCの被覆半径は、 CがR被覆となる最小のRです。すべての完全なコードは、最小サイズの被覆コードです。 ${\displaystyle q\geq 2}$${\displaystyle n\geq 1}$${\displaystyle R\geq 0}$ ${\displaystyle C\subseteq Q^{n}}$ ${\displaystyle y\in Q^{n}}$ ${\displaystyle x\in C}$ ${\displaystyle d_{H}(x,y)\leq R}$ ${\displaystyle Q^{n}}$

C = {0134,0223,1402,1431,1444,2123,2234,3002,3310,4010,4341}は長さ4の5元2被覆符号である。^[1]

長さnのq元R被覆符号の最小サイズを決定することは非常に難しい問題です。多くの場合、上限と下限のみがわかっており、それらの間のギャップは大きくなっています。被覆符号を構成するたびに、 K _q ( n ,  R )の上限が与えられます。下限には、球面被覆境界とロデミッヒ境界およびが含まれます。^{[2]被覆問題は、 におけるパッキング問題、つまり長さ}nのq元e誤り訂正符号の最大サイズの決定と 密接に関連しています。 ${\displaystyle K_{q}(n,R)}$${\displaystyle K_{q}(n,1)\geq q^{n-1}/(n-1)}$${\displaystyle K_{q}(n,n-2)\geq q^{2}/(n-1)}$${\displaystyle Q^{n}}$

特別なケースとして、フットボール プールの賭けに基づくフットボール プール問題があります。この問題の目的は、結果に関係なく、最大でR回の「ミス」があるn 回のフットボールの試合に対する賭けシステムを見つけることです。したがって、最大で 1 回の「ミス」があるn回の試合に対して、3 元カバーK ₃ ( n ,1) が求められます。

すると^{3n - k}が必要となり、 n = 4、k = 2の場合は9個、 n = 13、k = 3の場合は59049個必要となる。^[3] 2011年時点で知られている最良の境界^[4]は以下の通りである。 ${\displaystyle n={\tfrac {1}{2}}(3^{k}-1)}$

カバーコードに関する標準的な研究^[5]には、以下のアプリケーションがリストされています。

• 歪みを伴う圧縮
• データ圧縮
• デコードエラーと消失
• 相互接続ネットワークにおける放送
• フットボールプール^[6]
• 一度だけ書き込み可能なメモリ
• ベルレカンプ対ゲイル戦
• 音声コーディング
• 携帯電話通信
• 部分集合和とケイリーグラフ

• カバーコードに関する文献
• K q ( n , R ) の境界 {\displaystyle K_{q}(n,R)}