符号の「漸近性能」というのは、
簡単に言うと、
符号長 (n) を無限に大きくしたとき、
どれくらい効率よく誤り訂正できるか
を見ています。
つまり有限サイズの「この符号は性能が良い」という話ではなく、
- どれくらい情報を詰め込めるか
- どれくらい誤りに強いか
を、大規模化した極限で見る。
基本的に見る量
主に見るのはこの2つです。
1. レート (R)
$$
R = \frac{k}{n}
$$
- (n): 符号長
- (k): 情報長
です。
これは、
「全体のうち、どれくらい本物の情報を送れているか」
を意味する。
例えば：
- (R=0.9) → 90% が情報
- (R=0.5) → 半分しか情報じゃない
つまり高いほど効率が良い。
2. 相対距離 ($\delta$)
$$
\delta = \frac{d}{n}
$$
- (d): 最小距離
です。
これは、
「符号長に対してどれくらい誤りに耐えられるか」
を意味します。
例えば：
$$
d=100,\ n=1000
$$
なら、
$$
\delta=0.1
$$
です。
なぜ「相対」が重要？
もし単に
$$
d=100
$$
だけ見ても、
- (n=1000)
- (n=10^9)
では意味が全然違う。
だから、
$$
d/n
$$
を見る。
漸近性能とは何か
つまり、
$$
n \to \infty
$$
で、
- (R)
- (\delta)
を同時にどれだけ維持できるか。
これが「漸近性能」です。
理想状態
理想は：
- (R > 0)
- ($\delta > 0$)
を両方保ったまま、
$$
n \to \infty
$$
にできること。
つまり：
- 情報量も減らない
- 誤り耐性も減らない
巨大化できる。
これは非常に強い。
ランダム符号
ランダム符号は理論上かなり強く、
Gilbert–Varshamov bound に近づけます。
大雑把には：
$$
R \ge 1 - H_2(\delta)
$$
です。
ここで ($H_2$) は二項エントロピー。
つまり：
- 誤り耐性を上げると
- 情報効率は下がる
というトレードオフ。
BCH や Goppa を比較するとき
「漸近性能」というのは、
(n) を巨大にしたとき、
BCH と Goppa の
(R)-($\delta$) 関係がどうなるか
を比較している。
例えば：
- BCH は構造が強く、漸近でレートが落ちやすい
- Goppa はランダム符号に近づきやすい
みたいな話。
暗号ではさらに別
暗号では単に性能だけではなく、
- 復号困難性
- 構造秘匿
- distinguishability
- decoding attack 耐性
も必要。
だから：
通信路符号として優秀
≠ 暗号として安全
です。
ここが面白いところですね。
どうすれば漸近性能を満たす復号ができるの？
Coding Theory で「漸近性能を満たす復号」というと、普通は
符号長 ($n \to \infty$) にしても、
良いレート (R) と相対距離 ($\delta$) を維持しながら、
現実的計算量で復号できるか
を意味します。
つまり単に「復号できる」ではなく、
- 高レート
- 高誤り耐性
- 多項式時間復号
- 大規模化可能
を同時に満たしたい。
これはかなり難しい。
基本問題
理論上、ランダム符号は性能が良いです。
でも：
一般線形符号の最尤復号は NP 困難
です。
つまり、
- 性能最強
- 復号不能
になりやすい。
だから実際の符号理論は、
「復号しやすい構造」をどう入れるか
の歴史です。
漸近性能を満たす典型的方法
1. 反復復号（LDPC/Turbo/Polar）
現代ではこれが主流。
例えば：
- Low-Density Parity-Check Code
- Polar Code
など。
これらは：
- 疎行列
- グラフ構造
- メッセージパッシング
を使う。
LDPC の考え方
検査行列 (H) を疎にする：
$$
Hx^T = 0
$$
すると、
- 1ビット修正の影響範囲が局所化
- belief propagation が効く
ようになる。
その結果、
$$
O(n)
$$
近い計算量で巨大符号を復号できる。
しかも Shannon 限界に近い。
これは「漸近性能が良い復号」の代表。
2. リスト復号
もう一つ重要なのが：
List Decoding
です。
普通の一意復号では、
$$
t < d/2
$$
が限界。
でもリスト復号なら、
$$
t > d/2
$$
でも候補列挙できる。
これにより漸近性能が改善する。
特に：
- Reed–Solomon
- folded RS
- expander code
などで重要。
3. Expander 構造
良いグラフを使う。
例えば：
- 高連結性
- 小次数
を両立。
すると局所誤りが拡散される。
これは：
- LDPC
- Sipser–Spielman
- Tanner graph
系に繋がる。
4. Polarization
Channel Polarization
を使う。
これは：
- 良いチャネル
- 悪いチャネル
に分離する。
その後、
- 良い部分だけ情報を流す。
これで Shannon capacity に漸近到達。
BCH/Goppa の限界
BCH や Goppa は：
- algebraic decoding
- syndrome decoding
が中心。
これは非常に美しいけど、
巨大化すると：
- 復号複雑度
- 構造制約
が効いてくる。
だから現代通信では：
- LDPC
- Polar
へ移行した。
暗号では逆になる
ここが面白い。
暗号では：
「誰でも高速復号できる」
と危険。
だから：
- 正規ユーザーだけ復号可能
- 攻撃者には NP 困難
が欲しい。
つまり通信理論と逆。
あなたの方向との関係
あなたが以前考えていた：
- HQC 的復号
- intersection structure
- fake decoding
- multiple explanation
は、
「復号を少し曖昧化する」
方向です。
普通の通信理論は：
一意に最速復号したい
でもあなたは：
多義性を残しながら制御したい
を考えている。
これはむしろ：
- リスト復号
- probabilistic decoding
- soft decoding
に近い発想です。
かなり研究的テーマです。