長いコード（数学）

数学の論理
分類
タイプ	ブロックコード
ブロック長	${\displaystyle 2^{n}}$一部の人にとって${\displaystyle n\in \mathbb {N} }$
メッセージの長さ	${\displaystyle \log n}$
アルファベットのサイズ	${\displaystyle 2}$
表記	${\displaystyle (2^{n},\log n)_{2}}$-コード
ヴ t e

理論計算機科学および符号理論において、ロングコードとは、局所的にデコード可能な誤り訂正符号である。ロングコードのレートは非常に低いが、近似困難性の理論において基本的な役割を果たす。

を のすべての関数のリストとします。すると、メッセージのロングコードエンコードは文字列 となり、 は文字列の連結を表します。この文字列の長さは です。 ${\displaystyle f_{1},\dots ,f_{2^{n}}:\{0,1\}^{k}\to \{0,1\}}$${\displaystyle k=\log n}$${\displaystyle \{0,1\}^{k}\to \{0,1\}}$${\displaystyle x\in \{0,1\}^{k}}$${\displaystyle f_{1}(x)\circ f_{2}(x)\circ \dots \circ f_{2^{n}}(x)}$${\displaystyle \circ}$${\displaystyle 2^{n}=2^{2^{k}}}$

ウォルシュ・アダマール符号は長符号のサブコードであり、 2つの元を持つ有限体上の関数として解釈したときに線形関数となる関数のみを使用して取得できます。そのような関数は のみであるため、ウォルシュ・アダマール符号のブロック長は です。 ${\displaystyle f_{i}}$${\displaystyle \mathbb {F} _{2}^{k}\to \mathbb {F} _{2}}$${\displaystyle 2^{k}}$${\displaystyle 2^{k}}$

ロングコードの同等の定義は次のとおりです。 のロングコード符号化は、番目の座標上のブール独裁関数の真理値表、つまりの真理値表として定義されます。^[1] したがって、ロングコードは-ビット文字列を -ビット文字列として符号化します。 ${\displaystyle j\in [n]}$${\displaystyle j}$${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$${\displaystyle f(x_{1},\dots,x_{n})=x_{j}}$${\displaystyle (\log n)}$${\displaystyle 2^{n}}$

長いコードには繰り返しが含まれません。つまり、出力の 番目のビットを計算する関数は、出力の 番目のビットを計算する関数とは異なります。繰り返しを含まないすべてのコードの中で、長いコードは可能な限り最長の出力を持ちます。さらに、長いコードには繰り返しのないすべてのコードがサブコードとして含まれています。 ${\displaystyle f_{i}}$${\displaystyle i}$${\displaystyle f_{j}}$${\displaystyle j}$${\displaystyle j\neq i}$