スマートフォンを持ったまま地下鉄の階段を降りていくと、アンテナのバーが4本から2本に減り、動画の画質が少し落ちます。けれども通信そのものは切れません。このとき基地局と端末のあいだでは、電波の状況に合わせて符号化率（1つの情報ビットに何ビットの符号ビットを割り当てるか）が刻々と切り替えられています。電波が強いときは冗長を削って速く、弱いときは冗長を厚くして堅く、というわけです。
ここで素朴な疑問が浮かびます。符号化率が $1/2, 2/3, 3/4, 5/6, 7/8$ と5種類あるなら、送信機には符号器が5個、受信機には復号器が5個、それぞれ別々に載っているのでしょうか。誤り訂正符号の復号器はチップ上でかなりの面積を占める回路です。5個も並べたら電池も面積も持ちません。
答えは「復号器は1個だけ」です。使うのはパンクチャリング（puncturing、穿孔）という驚くほど単純な技法で、$r=1/2$ の1つの母符号（mother code）の出力ビットを、決められたパターンで規則的に間引いて捨てるだけです。捨てたぶんだけ送るビットが減るので符号化率は上がります。受信側は、間引かれた位置に「情報ゼロ」を意味する軟判定値 $0$ を挿入して、母符号のトレリスをそのまま流用します。符号器も復号器も1つのまま、レートだけが自在に変わる — これがパンクチャリングの威力です。
全体像を1枚の絵にしたのが上の図です。送信側は $r=1/2$ の母符号器の出力にマスクをかけて一部を捨て、受信側は捨てられた位置に $0$ を詰め戻してから、無改造のビタビ復号器に流し込みます。レートを $1/2$ から $7/8$ まで変えても、書き換わるのは中央の破線で囲んだマスクレジスタだけで、符号器も復号器も状態数64・合流数2のまま一切変わりません。この「変わらなさ」こそが、パンクチャリングが数十年にわたって通信規格に採用され続けている理由です。
パンクチャリングを理解すると、次のような領域が一気に見通せるようになります。
- 携帯電話のレートマッチング: LTE/5G NRでは、符号語長を割り当てられた物理リソース量にぴったり合わせる「レートマッチング」が必須です。循環バッファからの読み出し量を変えることで、パンクチャにもリピティションにもなります。IR-HARQ（再送のたびに違う冗長ビットを送る方式）も、この仕組みの上に成り立っています
- 衛星通信・宇宙通信: CCSDS（宇宙データシステム諮問委員会）標準やDVB-S（デジタル衛星放送）では、$K=7$、$r=1/2$ の畳み込み符号を母符号とし、パンクチャで $2/3, 3/4, 5/6, 7/8$ を作ります。降雨減衰でリンクが痩せたらレートを落とし、晴天時はレートを上げてスループットを稼ぎます
- Wi-Fi（IEEE 802.11a/g/n/ac）: まったく同じ $K=7$、生成多項式 $(133, 171)_8$ の母符号にパンクチャをかけ、変調方式との組み合わせでMCS（Modulation and Coding Scheme）のテーブルを作っています
- 適応変調符号化（AMC）: 変調多値数と符号化率のペアを瞬時のSNRに応じて選ぶ仕組み。符号化率側の可変性を安価に提供しているのがパンクチャリングです
本記事の内容
- なぜ「1つの符号で複数の符号化率」が必要なのか — レートマッチングの動機
- パンクチャリング行列の定義と、$r=1/2 \to 3/4$ をビット単位で追う具体例
- パンクチャ後の符号の正体 — 周期的時変畳み込み符号と、高レート符号を直接設計しない理由
- 自由距離 $d_{\text{free}}$ がどれだけ下がるか、その計算法（状態×位相の積グラフ上の最短経路）
- 漸近符号化利得 $10\log_{10}(R \, d_{\text{free}})$ の導出
- パンクチャリング行列の設計 — 全探索で最適パターンを見つける
- 復号側の核心 — ゼロ挿入（消失扱い）で母符号のトレリスを流用する
- Pythonで $r=1/2, 2/3, 3/4, 5/6, 7/8$ のBER曲線を実測し、レートと所要 $E_b/N_0$ のトレードオフ表を作る
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- 畳み込み符号とビタビ復号の理論 — 母符号となる畳み込み符号の構造、トレリス、ACS演算
- 軟判定復号の理論 — パンクチャリングは軟判定を前提とします。LLRと相関メトリック
- 誤り訂正符号とは — 符号化率、最小距離、符号化利得の基本
なぜ「1つの符号で複数の符号化率」が要るのか
リンクは動く、要求も動く
無線リンクの品質は固定されていません。移動体通信ならフェージングで数msのうちに10 dB以上変動しますし、衛星通信なら仰角と降雨で数dBが日単位で動きます。深宇宙探査機なら、地球からの距離が伸びるにつれて受信電力が距離の2乗で落ちていきます。
このとき符号化率を1つに固定するとどうなるでしょうか。$r=1/2$ の堅い符号に固定すれば、リンクが良好なときにも常に情報の2倍のビットを送ることになり、使えたはずのスループットを半分捨てることになります。逆に $r=7/8$ の軽い符号に固定すれば、リンクが少し悪化しただけで誤り率が跳ね上がり、通信が成立しなくなります。だから「そのときのSNRに見合った符号化率を選ぶ」必要があるのです。
「レートマッチング」というもう一つの動機
符号化率を可変にしたい理由は、リンク適応だけではありません。もっと即物的な理由があります。
無線フレームの中で、あるデータチャネルに割り当てられる物理的な変調シンボル数は、スケジューラが決める整数値です。たとえば「今回は $N = 1584$ シンボル分の器を使ってよい」と決まったとします。一方、符号器の出力ビット数は情報ビット数と符号化率で決まる別の整数です。この2つがぴったり一致する保証はどこにもありません。
そこで、符号器の出力を器のサイズに合わせて削るか水増しする操作が要ります。これがレートマッチング（rate matching）です。削る操作こそがパンクチャリングであり、水増しする操作がリピティション（繰り返し送信）です。つまりパンクチャリングは「符号化率を離散的に選ぶための道具」であると同時に、「符号語長を任意の整数長に合わせるための道具」でもあるのです。3GPPの規格書でレートマッチングという章が独立して存在するのは、この役割が本質的だからです。
素朴な解法とその問題
「レートごとに別の符号を設計すればいいのでは」と考えるのが素朴な解法です。$r=2/3$ には $r=2/3$ の最良の畳み込み符号があり、$r=3/4$ には $r=3/4$ の最良の符号があります。距離特性だけを見れば、当然そちらのほうが優れています。
しかし実装を考えると事情が変わります。$r=k_0/n_0$ の畳み込み符号を直接ビタビ復号すると、トレリスの各時刻で1つの状態に $2^{k_0}$ 本の枝が合流します。$r=3/4$ なら8本、$r=7/8$ なら128本です。ACS（Add-Compare-Select）回路は「2本のうち大きいほうを選ぶ」のが最も安く、合流数が増えると比較器のツリーが深くなって面積も遅延も増えます。さらに、レートごとに枝メトリックのテーブルもトレースバックの構造も違うため、5種類のレートに対応するには実質5種類の復号器を用意することになります。
パンクチャリングは、この問題を「符号器の出力にマスクをかける」というただ1つの操作に還元します。復号器は常に $r=1/2$、合流数は常に2、状態数は常に64のまま。レートを変えるのはマスクレジスタの中身だけです。距離特性で少し損をしてでも、この実装上の利益が圧倒的に大きい — これが1979年にケイブアーズ（Cain, Clark, Geist）がパンクチャ畳み込み符号を提案して以来、通信規格が一貫してこの方式を採り続けている理由です。
では、その「母符号」がどんなものかを確認してから、間引きの仕組みに入っていきましょう。
母符号 — $r=1/2$、拘束長 $K=7$ の畳み込み符号
本記事を通して使う母符号を固定します。業界標準となっている、拘束長 $K=7$、符号化率 $r=1/2$ の畳み込み符号です。生成多項式は8進表記で
$$ g_1 = (133)_8 = 1011011_2, \qquad g_2 = (171)_8 = 1111001_2 $$
です。この符号はNASAの深宇宙標準、CCSDS標準、IEEE 802.11a/g、DVB-S など、驚くほど多くの規格で同じものが使われています。「ザ・標準畳み込み符号」と呼んでよい存在です。
回路図で見ると構造は拍子抜けするほど単純です。入力ビットが7段のシフトレジスタを流れていき、生成多項式の $1$ が立っている位置（タップ）から線を引き出してXORで足し合わせる。それだけで出力 $x_t$ と $y_t$ の2本ができます。赤い破線で囲んだ後段6ビットがそのまま符号器の状態であり、$2^6 = 64$ 通りしかないことが図から読み取れます。緑と紫のタップ位置が食い違っていることにも注目してください。後で「$x$ と $y$ のどちらをどの位相で削るかで距離特性が変わる」理由が、この非対称性から生じます。
構造は単純です。入力ビット $u_t$ を長さ7のシフトレジスタに押し込み、レジスタ内容と生成多項式の論理積のパリティ（1の個数の偶奇）を2本取り出します。時刻 $t$ でのレジスタ内容を $\bm{v}_t = (u_t, u_{t-1}, \dots, u_{t-6})$ と書くと、2本の出力は
$$ x_t = \bigoplus_{i=0}^{6} g_{1,i} \, u_{t-i}, \qquad y_t = \bigoplus_{i=0}^{6} g_{2,i} \, u_{t-i} $$
です。ここで $\oplus$ はXOR（法2の加算）、$g_{j,i}$ は生成多項式 $g_j$ の第 $i$ ビットを表します。過去6ビット $(u_{t-1}, \dots, u_{t-6})$ が符号器の状態であり、状態数は $2^{K-1} = 2^6 = 64$ です。入力1ビットあたり出力2ビットなので符号化率は $1/2$、つまり情報の2倍の量を送ることになります。
この母符号の自由距離は $d_{\text{free}} = 10$ です（後ほど数値的に確認します）。自由距離とは、全ゼロ経路から分岐して再び全ゼロ経路に合流する経路のうち、出力の重み（1の個数）が最小のものの値です。直感的には「符号語同士が最も近づいたときの距離」で、これが大きいほど誤り訂正能力が高くなります。$K=7$ の $r=1/2$ 符号としては $d_{\text{free}}=10$ が最良で、これも $(133,171)_8$ が選ばれている理由です。
母符号が決まりました。次は、この符号の出力2本 $\{x_t\}$, $\{y_t\}$ から、どのビットをどう間引くかを規定する道具 — パンクチャリング行列 — を導入します。
パンクチャリングとは — 直感から
緩衝材を抜く
引っ越しの荷造りを想像してください。壊れやすい食器を送るときは、箱の隙間を緩衝材でぎっしり埋めます。壊れる確率はほぼゼロになりますが、箱は大きく重くなり、送料も高くつきます。一方、送り先が近所で、道もきれいに舗装されているとわかっているなら、緩衝材を半分抜いても割れないでしょう。箱は小さくなり、送料も安くなります。
母符号の出力2ビットのうち片方は、まさにこの緩衝材です。$r=1/2$ の符号は「1情報ビットあたり1ビットぶんの保護」を持っています。リンクが良ければ、保護のすべてを送る必要はありません。3ビットに1ビットくらい抜いても、残りの冗長で十分に守れることが多いのです。抜いたぶん帯域が空き、そこに次の情報を詰められます。
ただし、この比喩には1点だけ大事な違いがあります。荷物なら緩衝材を抜いても中身は変わりませんが、符号では「抜いたビットの位置を受信側が知っている」ことが決定的に重要です。抜いた位置がわかっていれば、受信側はそこを「読めなかった」（消失）として扱えます。位置がわからないと、抜けたことに気づかずビット列が全部ずれてしまい、復号は完全に破綻します。
「送らない」は「0を送る」ではない
初学者が最もつまずくのがここです。パンクチャで間引いたビットは、値 $0$ を送るのではありません。そもそも送信しないのです。受信側から見れば、そのビットについては何の情報も届いていない — つまり $\Pr(c=0) = \Pr(c=1) = 1/2$ の状態です。これは通信路符号理論でいう消失（erasure）そのものです。
この違いは実装で致命的に効きます。後の実験節で、間引き位置に「$0$ を受信した」つもりで軟判定値 $+1$ を挿入すると、BERが $10^{-4}$ 級から $0.48$（ほぼコイン投げ）まで崩壊する様子を実測します。「情報がない」ことを正しく表現できないと、復号器は存在しない情報を確信して誤った経路を選んでしまうのです。
直感が固まったところで、間引きのパターンを数学的に書き下しましょう。
パンクチャリング行列の定義
定義
母符号が符号化率 $r_0 = k_0/n_0$（本記事では $k_0=1$, $n_0=2$）であるとします。パンクチャリング行列 $\bm{P}$ を、$n_0$ 行 $p$ 列の $0/1$ 行列として定義します。
$$ \begin{equation} \bm{P} = \begin{pmatrix} P_{1,1} & P_{1,2} & \cdots & P_{1,p} \\ P_{2,1} & P_{2,2} & \cdots & P_{2,p} \\ \vdots & & \ddots & \vdots \\ P_{n_0,1} & \cdots & & P_{n_0,p} \end{pmatrix}, \quad P_{j,i} \in \{0, 1\} \end{equation} $$
ここで $p$ をパンクチャ周期（puncturing period）と呼びます。行 $j$ は母符号の第 $j$ 出力ストリームに対応し、列 $i$ は周期内の位相（時刻を $p$ で割った余り）に対応します。ルールはひとつだけです。
$$ P_{j,i} = 1 \ \Longrightarrow\ \text{第 } j \text{ 出力の位相 } i \text{ のビットを送信する} $$ $$ P_{j,i} = 0 \ \Longrightarrow\ \text{そのビットは送信しない（穿孔する）} $$
時刻 $t$（$t = 1, 2, 3, \dots$）のビット $c_{t,j}$ が送信されるかどうかは、位相 $i = ((t-1) \bmod p) + 1$ を使って $P_{j,i}$ が決めます。パターンは周期 $p$ で無限に繰り返されます。
符号化率の計算
$p$ 時刻ぶん（＝情報ビット $k_0 p$ 個ぶん）を1周期と見ます。母符号の出力は $n_0 p$ ビットですが、実際に送られるのは $\bm{P}$ の1の個数 $w(\bm{P}) = \sum_{j,i} P_{j,i}$ ビットだけです。したがってパンクチャ後の符号化率は
$$ \begin{equation} R = \frac{k_0 \, p}{w(\bm{P})} \end{equation} $$
となります。本記事の母符号は $k_0 = 1$, $n_0 = 2$ なので、単に $R = p / w(\bm{P})$ です。
この式から、狙いたい符号化率 $R = a/b$（既約分数）を作るには $p = a$、$w(\bm{P}) = b$ と取ればよいことがわかります。たとえば $R = 3/4$ なら周期 $p=3$、$2\times 3 = 6$ 個のマス目のうち $4$ 個を $1$ にすればよい、というわけです。
代表的なパンクチャリング行列
規格でよく使われるパターンを並べます（行の上が $x$ ストリーム、下が $y$ ストリーム）。
| 符号化率 $R$ | 周期 $p$ | 送信ビット数 $w(\bm{P})$ | パンクチャリング行列 $\bm{P}$ |
|---|---|---|---|
| $1/2$（母符号） | 1 | 2 | $\begin{pmatrix} 1 \\ 1 \end{pmatrix}$ |
| $2/3$ | 2 | 3 | $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ |
| $3/4$ | 3 | 4 | $\begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}$ |
| $5/6$ | 5 | 6 | $\begin{pmatrix} 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \end{pmatrix}$ |
| $7/8$ | 7 | 8 | $\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$ |
同じ表を色つきのマス目で描いたのが上の図です。シアンが送信するビット、灰色が捨てるビットで、レートが上がるほど灰色のマスが増えていく様子が一目でわかります。$7/8$ に注目すると、$x$ 行は7つの位相すべてを送るのに対し、$y$ 行は最初の位相しか送っていません。母符号の出力の片方をほぼ丸ごと捨てているわけで、これが後で見る $d_{\text{free}} = 3$ という厳しい値につながります。
念のため検算しておきます。$3/4$ の行列は $1$ が $4$ 個、周期は $3$ なので $R = 3/4$。$5/6$ の行列は $1$ が $6$ 個、周期は $5$ なので $R = 5/6$。$7/8$ の行列は $1$ が $8$ 個、周期は $7$ なので $R = 7/8$ です。すべて期待どおりです。
ここで重要な制約が1つあります。どの列も全ゼロにしてはいけません。ある位相で $x$ も $y$ も両方捨ててしまうと、その時刻の入力ビットに関する情報が符号語から完全に消え、その1ビットはどう頑張っても復元できなくなります（実効的に自由距離が0になる状況を作ってしまいます）。上の表のどのパターンも、各列に最低1つは $1$ が入っていることを確認してください。
行列の意味がわかったところで、$r=3/4$ のパターンを実際のビット列に適用して、1ビットずつ追いかけてみましょう。
$r=1/2 \to r=3/4$ をビット単位で追う
符号化する
情報ビット列 $\bm{u} = (1, 0, 1, 1, 0, 1)$ を、$K=7$ の母符号器に全ゼロ状態から入力します。シフトレジスタの内容（新しいビットが左）と2本の出力を1時刻ずつ計算すると、次の表が得られます（後掲のPythonコードで生成した実測値です）。
| 時刻 $t$ | 入力 $u_t$ | 直前の状態（新→旧） | 出力 $x_t$ | 出力 $y_t$ |
|---|---|---|---|---|
| 1 | 1 | 000000 | 1 | 1 |
| 2 | 0 | 100000 | 0 | 1 |
| 3 | 1 | 010000 | 0 | 0 |
| 4 | 1 | 101000 | 0 | 1 |
| 5 | 0 | 110100 | 1 | 0 |
| 6 | 1 | 011010 | 0 | 1 |
1行目を手で確かめてみます。$t=1$ ではレジスタ内容が $1000000_2$ です。$g_1 = 1011011_2$ との論理積は $1000000_2$ で、1の個数は1個なのでパリティは $x_1 = 1$。$g_2 = 1111001_2$ との論理積も $1000000_2$ で、$y_1 = 1$。表と一致します。2行目は、レジスタ内容が $0100000_2$、$g_1$ との論理積が $0000000_2$ で $x_2 = 0$、$g_2$ との論理積が $0100000_2$ で $y_2 = 1$。これも一致します。
母符号の出力は、$x$ と $y$ を交互に並べた
$$ \bm{c} = (x_1 y_1 \, x_2 y_2 \, x_3 y_3 \, x_4 y_4 \, x_5 y_5 \, x_6 y_6) = (11\,01\,00\,01\,10\,01) $$
の12ビットです。情報6ビットに対して12ビット、まさに $r=1/2$ です。
穿孔する
ここに $\bm{P} = \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}$ を周期3で適用します。位相は $t=1,4$ が第1列、$t=2,5$ が第2列、$t=3,6$ が第3列です。$x$ 行（上）は「送・送・捨」、$y$ 行（下）は「送・捨・送」を繰り返します。
| 時刻 $t$ | 位相 | $x_t$ | $P_{1,\cdot}$ | $x$ の扱い | $y_t$ | $P_{2,\cdot}$ | $y$ の扱い | 送信ビット |
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 送信 | 1 | 1 | 送信 | 1, 1 |
| 2 | 2 | 0 | 1 | 送信 | 1 | 0 | 穿孔 | 0 |
| 3 | 3 | 0 | 0 | 穿孔 | 0 | 1 | 送信 | 0 |
| 4 | 1 | 0 | 1 | 送信 | 1 | 1 | 送信 | 0, 1 |
| 5 | 2 | 1 | 1 | 送信 | 0 | 0 | 穿孔 | 1 |
| 6 | 3 | 0 | 0 | 穿孔 | 1 | 1 | 送信 | 1 |
送信されるビット列は
$$ \bm{c}’ = (1,\ 1,\ 0,\ 0,\ 0,\ 1,\ 1,\ 1) $$
の8ビットです。情報6ビットに対して8ビットですから、符号化率は $6/8 = 3/4$。狙いどおりです。周期3ごとに、母符号の6ビットから2ビット（$x_3$ と $y_2$ に相当する位置）が消えていることが表から読み取れます。
いまの表を絵にしたのが上の図です。上段の情報6ビットが母符号器で12ビットに膨らみ、赤い×が付いた4ビット（$x_3, x_6, y_2, y_5$）が捨てられて、最下段の8ビットだけが送信されます。$12 \to 8$ という減り方が、そのまま $1/2 \to 3/4$ というレートの上昇に対応しています。×の位置が周期3で繰り返し、しかも $x$ 行と $y$ 行を行ったり来たりしていることも図から確認できます。
注目してほしいのは、消えたビットが「常に $y$」でも「常に $x$」でもなく、位相ごとに $x$ と $y$ を交互に間引いている点です。これは偶然ではありません。片方のストリームだけを集中的に間引くと、生成多項式の片方に偏った情報しか届かず距離特性が急激に悪化します。$x$ と $y$ をバランスよく削るほうが良い符号になる、というのが経験則であり、後の全探索でも確認できます。
受信側での「戻し方」
受信側は、8個の軟判定値 $r_1, \dots, r_8$ を受け取ります。これを母符号のトレリスに入れるには、$(x, y)$ のペアが6組そろっている必要があります。そこで、穿孔した位置に $0$ を挿入して、元の12スロットを復元します。
$$ \begin{array}{c|cccccc} t & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \hat{x}_t & r_1 & r_3 & \bm{0} & r_5 & r_7 & \bm{0} \\ \hat{y}_t & r_2 & \bm{0} & r_4 & r_6 & \bm{0} & r_8 \end{array} $$
上の図がこの「戻し方」を絵にしたものです。受信側に届くのは連続した8個の値 $r_1, \dots, r_8$ だけで、どれが $x$ でどれが $y$ かの区別は付いていません。パンクチャリング行列を知っているからこそ、$r_1$ は $\hat{x}_1$、$r_2$ は $\hat{y}_1$、$r_3$ は $\hat{x}_2$、そして $\hat{y}_2$ は空欄……と正しく配り直せます。赤枠の $0$ が入った4つのスロットが、まさに1つ前の図で赤い×が付いていた位置に対応していることを確かめてください。
これで枠が埋まりました。あとは何も改造していない $r=1/2$ のビタビ復号器に流し込むだけです。なぜ $0$ を入れるのが正解なのか — その理由は後の節で、対数尤度比の観点からきちんと説明します。
ビット単位の動きが見えました。ここで自然な疑問が生まれます。パンクチャした結果できあがった符号は、いったい「どんな符号」なのでしょうか。
パンクチャ符号の正体 — 周期的時変畳み込み符号
時変になる
母符号は時不変です。状態と入力が決まれば、時刻によらず同じ出力が出ます。ところがパンクチャをかけると、同じ状態・同じ入力でも、時刻の位相によって出るビットの本数と種類が変わります。$t=1$ では2ビット、$t=2$ では1ビット（$x$ のみ）、$t=3$ では1ビット（$y$ のみ）というふうにです。
つまりパンクチャ符号は、周期 $p$ で出力写像が変化する周期的時変畳み込み符号（periodically time-varying convolutional code）です。これは符号理論的には少し扱いにくい対象で、「自由距離を求めるには位相まで含めて考えないといけない」という後述の面倒さの原因になります。
等価な高レート時不変符号
一方で、$p$ 時刻ぶんをひとまとめにして「1ステップ」と見ると、時不変な符号として書き直せます。$r=3/4$ の例なら、3個の入力ビット $(u_{3m+1}, u_{3m+2}, u_{3m+3})$ を1ブロックとして受け取り、4個の出力ビットを吐く、$k_0 = 3$, $n_0 = 4$ の畳み込み符号と等価です。
$$ \text{パンクチャ } (r_0 = 1/2, \ \bm{P} \in \{0,1\}^{2 \times p}) \ \equiv \ \text{時不変 } (k_0, n_0) = (p, \ w(\bm{P})) \text{ 符号} $$
この等価性は理論的に重要です。「パンクチャ符号は特殊な変わり種ではなく、ちゃんとした高レート畳み込み符号の一種である」ことを保証してくれるからです。実際、良いパンクチャ行列を選べば、同じ状態数の高レート符号として最良に近い距離特性が得られることが知られています。
では、なぜ直接設計しないのか
等価なのだから、はじめから $r=3/4$ の $(3,4)$ 符号を設計すればいいのでは、と思うかもしれません。ここで冒頭の実装論が効いてきます。
$(k_0, n_0) = (3, 4)$ の符号を直接ビタビ復号すると、トレリスの1ステップで各状態に $2^{k_0} = 8$ 本の枝が合流します。ACS演算は「8個の候補メトリックを計算し、最大のものを選び、どれを選んだか3ビットで記録する」という処理になります。$r=7/8$ なら $2^7 = 128$ 本の合流です。回路規模も消費電力も跳ね上がります。
対してパンクチャ方式では、トレリスは母符号のまま、つまり1状態あたり常に2本の合流です。位相によって枝メトリックの計算に使う受信値の本数が変わるだけで、それも「$0$ を掛ける」だけで吸収できます。復号器のデータパスは完全に共通で、レートを切り替えるのはデパンクチャ器のマスクレジスタだけ。$1/2$ から $7/8$ まで、同じ回路が同じ速度で動きます。
さらに、この構造はHARQとも相性が良好です。最初は $r=7/8$ で送り、復号に失敗したら、最初に捨てたビットの一部を追加で送ります。受信側は初回の軟判定値と追加ぶんを合わせて $r=3/4$ 相当のトレリスを走らせられます。母符号が同じだからこそ、後から冗長を「足す」ことができるのです。
構造がわかったので、次は性能の話に移ります。ビットを間引いた代償は、どのくらいの大きさなのでしょうか。
自由距離 $d_{\text{free}}$ の低下
自由距離の定義（復習）
畳み込み符号は線形符号なので、任意の2つの符号語間の距離は「ある符号語と全ゼロ符号語の距離」に帰着します。自由距離 $d_{\text{free}}$ は、全ゼロ経路から分岐し、有限時間後に再び全ゼロ状態に合流する非ゼロ経路のうち、出力の重み（1の個数）が最小のものの重みとして定義されます。
$$ \begin{equation} d_{\text{free}} = \min_{\substack{\text{経路 } \pi:\ 0 \to 0,\ \pi \neq \text{全ゼロ}}} w\big(\bm{c}(\pi)\big) \end{equation} $$
これが大きいほど、符号語同士が「離れて」いて、雑音で取り違える確率が小さくなります。$K=7$, $r=1/2$ の母符号では $d_{\text{free}} = 10$ です。
パンクチャは距離を下げる方向にしか働かない
パンクチャリング後の重みは、送信されるビットだけを数えます。経路 $\pi$ の位相 $i$ での出力を $(c_{t,1}, c_{t,2})$ とすると、パンクチャ後の重みは
$$ \begin{equation} w_{\bm{P}}(\pi) = \sum_{t} \sum_{j=1}^{n_0} P_{j,\, ((t-1) \bmod p) + 1} \cdot c_{t,j} \end{equation} $$
です。$P_{j,i} \in \{0,1\}$ なので、各項は元の $c_{t,j}$ 以下です。したがって任意の経路について $w_{\bm{P}}(\pi) \le w(\pi)$ が成り立ち、最小を取っても
$$ d_{\text{free}}^{(\bm{P})} \le d_{\text{free}}^{(\text{母符号})} $$
です。パンクチャは自由距離を増やすことは決してなく、たいてい減らします。これがレートを上げる代償の正体です。
位相を含めた最短経路問題
自由距離を実際に計算するとき、パンクチャ符号では厄介な点が1つあります。時変符号なので、「どの位相で全ゼロ経路から分岐したか」によって経路の重みが変わるのです。したがって
$$ \begin{equation} d_{\text{free}}^{(\bm{P})} = \min_{\varphi_0 \in \{1,\dots,p\}} \ \min_{\pi:\ (0,\varphi_0) \to (0,\cdot)} w_{\bm{P}}(\pi) \end{equation} $$
と、開始位相についても最小を取る必要があります。
計算は、状態 $\times$ 位相の積グラフ上の最短経路問題として定式化できます。ノードを $(s, \varphi)$（$s$ は64状態、$\varphi$ は $p$ 個の位相）とし、入力 $b \in \{0,1\}$ による遷移を、重み $w = \sum_j P_{j,\varphi} c_j(s,b)$ の有向辺とします。ノード数は $64p$、辺数は $128p$ の小さなグラフなので、ダイクストラ法で一瞬です。
手順は次のとおりです。
- 開始位相 $\varphi_0$ を1つ固定する
- 状態 $0$ から入力 $b=1$ で分岐する（これで全ゼロ経路から離れる）。到達先は $(32, \varphi_0 + 1)$、初期コストはその枝のパンクチャ後重み
- そこからダイクストラ法で、状態 $0$ に戻るノード $(0, \cdot)$ への最短距離を求める
- すべての $\varphi_0$ について繰り返し、最小値を取る
実際にこの手順で $R=3/4$ の最小重み経路を求めて描いたのが上の図です。灰色の直線が全ゼロ経路、赤い折れ線が最小重み経路で、各枝に付いた $w$ がその時刻に送信されるビットのうち $1$ の個数です。目を引くのは $w=0$ の枝がずらりと並ぶことで、これは「その時刻の母符号出力が $1$ を持っていても、そのビットがちょうど穿孔される位相に当たった」ことを意味します。穿孔がなければ重みを稼げたはずの区間がタダで通過されてしまい、17時刻もかけて戻ってくる長い経路の合計重みが $5$ にとどまる — これが $d_{\text{free}}$ が $10$ から $5$ へ半減する仕組みそのものです。
この計算を実装して $K=7$ の各パターンに適用した結果が次の表です。
| 符号化率 $R$ | パンクチャリング行列 | $d_{\text{free}}$ | 母符号比 |
|---|---|---|---|
| $1/2$ | $\begin{pmatrix} 1 \\ 1\end{pmatrix}$ | 10 | — |
| $2/3$ | $\begin{pmatrix} 1 & 1 \\ 1 & 0\end{pmatrix}$ | 6 | $-4$ |
| $3/4$ | $\begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1\end{pmatrix}$ | 5 | $-5$ |
| $5/6$ | $\begin{pmatrix} 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1\end{pmatrix}$ | 4 | $-6$ |
| $7/8$ | $\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0\end{pmatrix}$ | 3 | $-7$ |
この数値は、安田ら（Yasuda et al., 1984）の古典的な論文で報告されている $K=7$ パンクチャ符号の自由距離と完全に一致します。レートを上げるほど自由距離が単調に減り、$7/8$ では母符号の3割にまで落ち込むことがわかります。
自由距離が減ることはわかりました。では、その「減り方」は性能にどう跳ね返るのでしょうか。ここを定量的に結びつけるのが漸近符号化利得です。
漸近符号化利得の導出
対経路誤り確率から始める
軟判定ビタビ復号の性能を支配するのは、対経路誤り確率（pairwise error probability）— 正しい経路より、距離 $d$ だけ離れた誤った経路のほうがメトリックで勝ってしまう確率 — です。これを丁寧に導きます。
BPSK変調・AWGN通信路を仮定します。符号ビット $c \in \{0,1\}$ は $x = 1 – 2c \in \{+1, -1\}$ に写され、シンボルあたりのエネルギーを $E_s$ として送信されます。受信値は
$$ r_i = \sqrt{E_s}\, x_i + n_i, \qquad n_i \sim \mathcal{N}\!\left(0, \tfrac{N_0}{2}\right) $$
です。ビタビ復号器は相関メトリック $\sum_i r_i x_i$ を最大化する経路を選びます。
正しい経路の符号ビット列を $\bm{x}$、誤った経路のそれを $\bm{x}’$ とし、両者が異なる位置の集合を $\mathcal{D}$（$|\mathcal{D}| = d$）とします。異なる位置では $x_i’ = -x_i$ です。2経路のメトリック差は、一致する位置がキャンセルするので $\mathcal{D}$ 上の和だけが残ります。
$$ \Delta = \sum_{i \in \mathcal{D}} r_i x_i’ – \sum_{i \in \mathcal{D}} r_i x_i = \sum_{i \in \mathcal{D}} r_i(-x_i) – \sum_{i \in \mathcal{D}} r_i x_i = -2\sum_{i \in \mathcal{D}} r_i x_i $$
誤りが起きるのは $\Delta > 0$ のとき、つまり $\sum_{i \in \mathcal{D}} r_i x_i < 0$ のときです。ここに受信値の定義 $r_i = \sqrt{E_s} x_i + n_i$ を代入すると、$x_i^2 = 1$ を使って
$$ \sum_{i \in \mathcal{D}} r_i x_i = \sum_{i \in \mathcal{D}} \left(\sqrt{E_s}\, x_i^2 + n_i x_i\right) = d\sqrt{E_s} + \underbrace{\sum_{i \in \mathcal{D}} n_i x_i}_{\displaystyle N} $$
となります。$N$ は独立なガウス変数の和なので $N \sim \mathcal{N}(0, d N_0/2)$ です（$x_i = \pm 1$ は分散を変えません）。したがって
$$ P_2(d) = \Pr\!\left[N < -d\sqrt{E_s}\right] = Q\!\left(\frac{d\sqrt{E_s}}{\sqrt{d N_0/2}}\right) = Q\!\left(\sqrt{\frac{2 d E_s}{N_0}}\right) $$
を得ます。ここで $Q(\cdot)$ は標準正規分布の上側確率です。
情報ビットあたりのエネルギーに直す
いま比較したいのは「同じ情報ビットあたりエネルギー $E_b$ を使ったときの優劣」です。符号化率 $R$ の符号では、1情報ビットぶんのエネルギーが $1/R$ 個のシンボルに分配されるので
$$ E_s = R \, E_b $$
です。これを代入すると、対経路誤り確率は
$$ \begin{equation} P_2(d) = Q\!\left(\sqrt{\frac{2 R d E_b}{N_0}}\right) \end{equation} $$
となります。高SNR領域では $Q(\cdot)$ が急激に減衰するため、和のうち最小距離 $d = d_{\text{free}}$ の項が支配的になります。つまりBERはおおむね $Q\!\left(\sqrt{2 R \, d_{\text{free}} \, E_b/N_0}\right)$ の振る舞いをします。
未符号化BPSKとの比較
一方、符号化しないBPSKのビット誤り率は
$$ P_b^{\text{uncoded}} = Q\!\left(\sqrt{\frac{2 E_b}{N_0}}\right) $$
です。2つの式を見比べると、両者は $Q$ の引数の中身が $R \, d_{\text{free}}$ 倍だけ違うだけの、まったく同じ形をしています。同じBERを達成するのに必要な $E_b/N_0$ の比が符号化利得ですから、デシベル表記で
$$ \begin{equation} G_a = 10 \log_{10}\left(R \cdot d_{\text{free}}\right) \quad [\text{dB}] \end{equation} $$
が漸近符号化利得（asymptotic coding gain）です。「漸近」と付くのは、$Q$ の最小距離項だけを残す近似が高SNRでしか正当化されないためです。実SNR領域では、$d_{\text{free}}$ より大きい距離の経路も無視できない数だけ寄与するので、実測利得はこの値より小さくなります。
この式に先ほどの $d_{\text{free}}$ を代入します。
| 符号化率 $R$ | $d_{\text{free}}$ | $R \cdot d_{\text{free}}$ | 漸近利得 $G_a$ [dB] |
|---|---|---|---|
| $1/2$ | 10 | 5.00 | 6.99 |
| $2/3$ | 6 | 4.00 | 6.02 |
| $3/4$ | 5 | 3.75 | 5.74 |
| $5/6$ | 4 | 3.33 | 5.23 |
| $7/8$ | 3 | 2.625 | 4.19 |
この表を3枚の棒グラフにしたのが上の図です。左は $d_{\text{free}}$ で、$10, 6, 5, 4, 3$ と大きく崩れていきます。しかし中央の積 $R \cdot d_{\text{free}}$ を見ると $5.00 \to 2.62$、右の漸近利得に至っては $6.99$ dB $\to 4.19$ dB と、目減りはずっと穏やかです。左のグラフだけを見ると「パンクチャは符号を7割も弱くする破壊的な操作」に見えますが、右のグラフでは「$2.8$ dBの授業料でスループットが $1.75$ 倍」という別の顔が現れる — 見る量を変えると印象が逆転する、この記事でいちばん大事な図です。
きれいな傾向が読み取れます。$R$ が上がるにつれて $d_{\text{free}}$ は減りますが、$R$ 自体は増えるので、積 $R \cdot d_{\text{free}}$ の減り方は $d_{\text{free}}$ 単独よりずっと緩やかです。$1/2$ から $7/8$ へ、スループットを $1.75$ 倍にしても、符号化利得の目減りは $2.8$ dBに収まります。これがパンクチャリングという技法が実用的である理由の核心です。
もう1つ、この式は $R \cdot d_{\text{free}}$ が「符号の良さ」の指標になることを教えてくれます。同じレートなら $d_{\text{free}}$ が大きいほど良く、$d_{\text{free}}$ が $1$ 違うだけで $10\log_{10}(5/4) \approx 0.97$ dBの差が出ます。ならば、良いパンクチャリング行列を選ぶ作業には大きな意味がある、ということになります。次にそれを実際にやってみましょう。
パンクチャリング行列の設計 — 全探索してみる
探索空間は驚くほど小さい
$R = 3/4$ を作るパンクチャリング行列は、$2 \times 3 = 6$ マスのうち $4$ マスを $1$ にする組み合わせなので $\binom{6}{4} = 15$ 通りしかありません。$R = 5/6$ でも $\binom{10}{6} = 210$ 通り、$R = 7/8$ でも $\binom{14}{8} = 3003$ 通りです。$d_{\text{free}}$ の計算がダイクストラ1回で済むことを考えると、全探索は一瞬で終わります。
そこからさらに、全ゼロ列を持つパターン（その位相で情報が消えてしまうので使えない）を除外して総当たりし、$d_{\text{free}}$ を最大にする行列を探しました。結果は次のとおりです。
| 符号化率 | 全組み合わせ | 有効な候補数 | 最大 $d_{\text{free}}$ | 最適行列（同点の例） |
|---|---|---|---|---|
| $2/3$ | 4 | 4 | 6 | $\begin{pmatrix}1&1\\1&0\end{pmatrix}$, $\begin{pmatrix}1&1\\0&1\end{pmatrix}$ |
| $3/4$ | 15 | 12 | 5 | $\begin{pmatrix}1&1&0\\1&0&1\end{pmatrix}$, $\begin{pmatrix}1&0&1\\0&1&1\end{pmatrix}$, $\begin{pmatrix}0&1&1\\1&1&0\end{pmatrix}$ |
| $5/6$ | 210 | 80 | 4 | $\begin{pmatrix}1&1&0&1&0\\1&0&1&0&1\end{pmatrix}$ ほか |
| $7/8$ | 3003 | 448 | 3 | $\begin{pmatrix}1&1&1&1&1&1&1\\1&0&0&0&0&0&0\end{pmatrix}$ ほか |
全探索で出てきた $d_{\text{free}}$ の分布をヒストグラムにすると、上の図のようになります。$R=3/4$ では有効な12通りのうち最良の $d_{\text{free}}=5$ を達成するのはわずか3通りで、残り9通り（つまり75%）は $d_{\text{free}}=4$ に落ちます。$R=5/6$ ではさらに厳しく、80通り中で $d_{\text{free}}=4$ に届くのは10通りだけ、しかも $d_{\text{free}}=2$ という壊滅的なパターンも10通り混ざっています。「$1$ の個数さえ合っていればどう並べてもよい」わけではないことが、この分布から数として見えてきます。
得られた最大値 $6, 5, 4, 3$ は、規格や教科書に載っている値と完全に一致しました。つまり「全探索で最良を選ぶ」という素朴な方法が、そのまま標準パターンを再現します。
選び方を間違えるとどうなるか
面白いのは、同じ $R = 3/4$ でも行列の選び方で $d_{\text{free}}$ が変わることです。たとえば
$$ \bm{P}_{\text{opt}} = \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix} \ (d_{\text{free}} = 5), \qquad \bm{P}_{\text{sub}} = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} \ (d_{\text{free}} = 4) $$
の2つは、どちらも $x$ から2ビット、$y$ から2ビットを残す、見た目のよく似たパターンです。ところが $d_{\text{free}}$ は $5$ と $4$ で違います。漸近利得の差は $10\log_{10}(3.75/3.00) \approx 0.97$ dBです。
なぜこんなことが起きるかというと、$g_1 = (133)_8$ と $g_2 = (171)_8$ は対称ではないからです。低重みの経路がどちらのストリームに重みを落とすかには偏りがあり、その偏りとパンクチャの位相がうまく噛み合うかどうかで、生き残る重みが変わります。「$x$ を2ビット、$y$ を2ビット」という個数だけでは決まらず、どの位相で削るかが効くのです。実際にシミュレーションで両者を比べると（後述）、$\bm{P}_{\text{sub}} $ は $\bm{P}_{\text{opt}}$ に対してBER $10^{-5}$ 点で約 $0.6$ dB損をします。理論予測（$0.97$ dB）よりやや小さいのは、有限SNRでは $d_{\text{free}}$ 以外の距離の寄与も効くためです。
距離スペクトルという細かい話
$d_{\text{free}}$ が同じでも符号の優劣が付くことがあります。BERのユニオンバウンドは
$$ P_b \le \sum_{d = d_{\text{free}}}^{\infty} \frac{\beta_d}{k_0} \, Q\!\left(\sqrt{\frac{2 R d E_b}{N_0}}\right) $$
と書けます。ここで $\beta_d$ は重み $d$ の経路が運ぶ情報ビット誤り数の総和（距離スペクトルの係数）です。$d_{\text{free}}$ が同じでも $\beta_{d_{\text{free}}}$ が小さいほうが良い符号です。厳密な設計では、$d_{\text{free}}$ を最大化したうえで $\beta_{d_{\text{free}}}, \beta_{d_{\text{free}}+1}, \dots$ を辞書式に最小化します。本記事では $d_{\text{free}}$ までで話を止めますが、規格で使われるパターンはこのレベルまで詰められたものです。
符号側の設計は以上です。いよいよ、パンクチャリングを実用技術たらしめている復号側の仕掛けに入ります。
復号側の核心 — ゼロ挿入（消失扱い）
なぜ $0$ なのか — LLRで考える
対数尤度比（LLR）を使うと、「$0$ を入れる」ことの意味が透明になります。符号ビット $c$ に対するLLRは
$$ L(c) = \ln \frac{\Pr(c = 0 \mid r)}{\Pr(c = 1 \mid r)} $$
と定義されます。BPSK・AWGNで事前確率が等しい場合、ベイズの定理から事後確率比は尤度比に等しく、ガウス密度を代入すると
$$ L(c) = \ln \frac{\exp\!\left(-\frac{(r – \sqrt{E_s})^2}{N_0}\right)}{\exp\!\left(-\frac{(r + \sqrt{E_s})^2}{N_0}\right)} = \frac{(r+\sqrt{E_s})^2 – (r-\sqrt{E_s})^2}{N_0} = \frac{4\sqrt{E_s}}{N_0}\, r $$
となり、受信値 $r$ に比例します。展開の途中で $(r+a)^2 – (r-a)^2 = 4ar$ を使いました。
さて、穿孔されたビットについて受信側が持っている情報は、文字通りゼロです。そのビットが $0$ だったのか $1$ だったのかを示す観測が存在しないので、
$$ \Pr(c = 0 \mid \text{観測なし}) = \Pr(c = 1 \mid \text{観測なし}) = \frac{1}{2} \quad \Longrightarrow \quad L(c) = \ln \frac{1/2}{1/2} = 0 $$
です。LLRが $0$ とは「どちらとも言えない」という尤度中立の状態を表します。そして $L \propto r$ なので、LLRを $0$ にするには受信値のスロットに $r = 0$ を入れればよい、ということになります。これがゼロ挿入の理論的根拠です。
枝メトリックの上でどう効くか
ビタビ復号器の枝メトリックは、相関形で書くと
$$ \begin{equation} \lambda_t(s \to s’) = \sum_{j=1}^{n_0} m_{j,t} \cdot r_{t,j} \cdot \big(1 – 2 c_{t,j}(s \to s’)\big) \end{equation} $$
です。ここで $m_{j,t} = P_{j, ((t-1) \bmod p)+1}$ はパンクチャマスクです。$m_{j,t} = 0$ の項は、$r_{t,j}$ が何であっても寄与が $0$ になります。つまりその位置は「枝の識別に使われない」— 通る枝が $c_{t,j} = 0$ でも $c_{t,j} = 1$ でも、メトリックがまったく同じになります。
この「寄与が消える」現象を、受信値 $r = (0.8, -1.3)$ を例に棒グラフで見たのが上の図です。左（穿孔なし）では4本の枝のメトリックが $-0.5, +2.1, -2.1, +0.5$ と全て違う値になり、復号器は4本を区別できます。ところが右（$y$ を穿孔して $r_2 \to 0$）では、$y$ 側の符号ビットが $0$ でも $1$ でもメトリックが変わらないため、枝AとB、枝CとDがそれぞれ完全に同点になります。復号器から見て「$y$ が $0$ か $1$ かは判断材料にならない」という状態が、この同点として現れているわけです。
これが消失を正しく表現しているということです。復号器は、その位置のビットについては何も判断せず、他の位置から来る情報だけで経路を決めます。マスクを掛ける代わりにデパンクチャ器で $r_{t,j} \leftarrow 0$ を挿入しても、数式的にはまったく同じことです。実装では後者のほうが好まれます。ビタビ復号器のコアに一切手を入れずに済むからです。
実装アーキテクチャ
以上をまとめると、パンクチャ対応の送受信系は次のようになります。
送信: 情報ビット → [母符号器 r=1/2, K=7] → [パンクチャ器: マスクPで間引き] → 変調
受信: 復調(軟判定) → [デパンクチャ器: 穿孔位置に0を挿入] → [ビタビ復号器 r=1/2, K=7] → 情報ビット
レートを $3/4$ から $5/6$ に変えたいとき、変わるのはパンクチャ器とデパンクチャ器が参照するマスクテーブルだけです。母符号器もビタビ復号器も、状態数64・合流数2のまま一切変わりません。これがパンクチャリングの実装上の勝利です。
やってはいけないこと
穿孔位置に $0$ 以外を入れるとどうなるでしょうか。たとえば「送らなかったんだから $0$ を送ったことにしよう」と考えて、BPSKで $c=0$ に対応する軟判定値 $+1$ を挿入したとします。これは復号器に「このビットは $0$ です、確信度は通常の受信値と同程度です」と嘘の情報を与えることに他なりません。実際には $50\%$ の確率で $1$ だったはずのビットに、$0$ という高い確信を与えるわけです。
$r=3/4$ では全スロットの $1/3$ が穿孔位置ですから、符号ビットの3分の1に無作為な確信が注入されます。後の実験節で、この操作がBERを $0.48$（ほぼコイン投げ）まで悪化させることを実測で示します。「情報がない」を表現する値は $0$ しかない、というのは決して些細な実装上の注意ではなく、消失通信路の本質なのです。
位相同期（ノード同期）
もう1つ実務上の重要事項があります。デパンクチャ器は「いま受信しているビットが周期のどの位相か」を知っていなければなりません。位相が1つずれると、$x$ のスロットに $y$ の値を入れるといった致命的な取り違えが起き、復号は完全に失敗します。
実装では、$p$ 通り（さらに $x/y$ の入れ替わりも考えれば $2p$ 通り）の位相候補を並列に、あるいは順に試し、ビタビ復号器のパスメトリック成長率や再符号化した符号語との不一致率が最良になる候補を選びます。これをノード同期（node synchronization）と呼びます。母符号 $r=1/2$ 単独でも $x/y$ の入れ替わり2通りの同期が必要ですが、パンクチャすると候補数が $p$ 倍に増える、という点は覚えておくとよいでしょう。
理論と実装の要点がそろいました。ここからPythonで、いま述べたすべてを実際に動かして確かめます。
Pythonでの実装
母符号器のテーブルを作る
まず $K=7$ の符号器を、状態遷移テーブルと出力テーブルとして先に構築します。トレリスを走るとき何度も引くので、事前計算しておくのが定石です。
import numpy as np
K = 7 # 拘束長
G = [0o133, 0o171] # 生成多項式（8進）: 91, 121
NS = 1 << (K - 1) # 状態数 = 64
# next_state[s, b] : 状態sに入力bを与えたときの次状態
# out_bits[s, b, j]: そのときの第j出力ビット
next_state = np.zeros((NS, 2), dtype=np.int64)
out_bits = np.zeros((NS, 2, 2), dtype=np.int64)
for s in range(NS):
for b in (0, 1):
reg = (b << (K - 1)) | s # 新しいビットを最上位に押し込む
next_state[s, b] = reg >> 1 # 1ビットシフトして古いビットを捨てる
for j, g in enumerate(G):
# レジスタと生成多項式の論理積のパリティ
out_bits[s, b, j] = bin(reg & g).count("1") & 1
def encode(bits):
"""情報ビット列(F, L)を畳み込み符号化して (F, L, 2) を返す"""
F, L = bits.shape
s = np.zeros(F, dtype=np.int64)
out = np.zeros((F, L, 2), dtype=np.int64)
for t in range(L):
b = bits[:, t]
out[:, t, 0] = out_bits[s, b, 0]
out[:, t, 1] = out_bits[s, b, 1]
s = next_state[s, b]
return out
# 記事本文の具体例を再現する
info = np.array([[1, 0, 1, 1, 0, 1]])
cw = encode(info)[0]
print("x:", cw[:, 0])
print("y:", cw[:, 1])
実行すると x: [1 0 0 0 1 0]、y: [1 1 0 1 0 1] が表示されます。これは本文の表と完全に一致します。手計算で確かめた $t=1$ の $(x,y)=(1,1)$、$t=2$ の $(x,y)=(0,1)$ もそのとおりです。符号器が正しく実装できたことが確認できました。
パンクチャとデパンクチャ
次に、パンクチャリング行列を適用する処理と、受信側で $0$ を戻す処理を書きます。実装上のコツは「行列を時間方向にタイル展開してマスク配列にしてしまう」ことで、こうすると穿孔もデパンクチャも要素ごとの掛け算1回で書けます。
import numpy as np
PATTERNS = {
"1/2": np.array([[1], [1]]),
"2/3": np.array([[1, 1], [1, 0]]),
"3/4": np.array([[1, 1, 0], [1, 0, 1]]),
"5/6": np.array([[1, 1, 0, 1, 0], [1, 0, 1, 0, 1]]),
"7/8": np.array([[1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0, 0]]),
}
def rate_of(P):
"""パンクチャ後の符号化率 R = p / w(P)"""
return P.shape[1] / P.sum()
def make_mask(P, L):
"""長さLのマスク配列 (L, 2) を作る（Lは周期pの倍数とする）"""
p = P.shape[1]
return np.tile(P.T, (L // p, 1)) # P.T は (p, 2)
# 符号化率の確認
for name, P in PATTERNS.items():
print(f"{name}: R = {rate_of(P):.4f}, 周期 p = {P.shape[1]}, "
f"送信ビット数 w(P) = {P.sum()}")
# 本文の r=3/4 の穿孔例を再現
P = PATTERNS["3/4"]
mask = make_mask(P, 6)
sent = cw[mask == 1] # 送信されるビットだけを取り出す
print("送信ビット列:", sent, "→", len(sent), "ビット")
出力は 1/2: R = 0.5000、3/4: R = 0.7500、5/6: R = 0.8333 のように、定義どおりの符号化率になります。$r=3/4$ の穿孔例では送信ビット列が [1 1 0 0 0 1 1 1] の8ビットとなり、本文の表で手計算した結果と一致しました。情報6ビットに対して8ビットなので、確かに $3/4$ です。
軟判定ビタビ復号器（ゼロ挿入対応）
復号器の本体です。ポイントは、この関数がパンクチャリングのことを何も知らないことです。受け取るのは常に $(L, 2)$ 形の軟判定値で、穿孔位置にはすでに $0$ が入っています。母符号のトレリスをそのまま走らせるだけです。
import numpy as np
# 各状態の「先行状態」と、そのとき使われた入力ビットを事前計算
prev = np.zeros((NS, 2), dtype=np.int64) # 先行状態
prev_in = np.zeros((NS, 2), dtype=np.int64) # そのときの入力
for sp in range(NS):
for c in (0, 1):
s = ((sp << 1) | c) & (NS - 1)
prev[sp, c] = s
prev_in[sp, c] = sp >> (K - 2) # 入力は次状態の最上位ビット
sym = 1 - 2 * out_bits # BPSK写像: 0→+1, 1→−1
sym0 = sym[prev[:, 0], prev_in[:, 0]] # (NS, 2)
sym1 = sym[prev[:, 1], prev_in[:, 1]]
def viterbi(r):
"""軟判定ビタビ復号。r: (F, L, 2)。穿孔位置は 0 が入っている前提"""
F, L, _ = r.shape
pm = np.full((F, NS), -1e9); pm[:, 0] = 0.0 # 全ゼロ状態から開始
dec = np.zeros((F, L, NS), dtype=np.uint8) # 選択記録
for t in range(L):
y = r[:, t, :]
# 相関メトリック sum_j r_j * x_j （0 の位置は寄与しない＝消失）
c0 = y[:, 0:1] * sym0[:, 0] + y[:, 1:2] * sym0[:, 1]
c1 = y[:, 0:1] * sym1[:, 0] + y[:, 1:2] * sym1[:, 1]
m0, m1 = pm[:, prev[:, 0]] + c0, pm[:, prev[:, 1]] + c1
take1 = m1 > m0
pm = np.where(take1, m1, m0) # ACS: 大きいほうを残す
dec[:, t, :] = take1.astype(np.uint8)
# テイルビットで全ゼロ状態に終端させているので、状態0からトレースバック
s = np.zeros(F, dtype=np.int64)
bits = np.zeros((F, L), dtype=np.int64)
fidx = np.arange(F)
for t in range(L - 1, -1, -1):
c = dec[fidx, t, s]
bits[:, t] = s >> (K - 2)
s = ((s << 1) | c) & (NS - 1)
return bits
この復号器の枝メトリック計算 y[:, 0:1] * sym0[:, 0] + y[:, 1:2] * sym0[:, 1] に注目してください。穿孔位置では y の該当成分が $0$ なので、その項はまるごと消えます。$c_{t,j}=0$ の枝も $c_{t,j}=1$ の枝も同じメトリックになり、その位置は経路選択に一切影響しません。本文で述べた「消失として扱われる」が、コード上ではこの掛け算1つで実現されているわけです。
自由距離をダイクストラで求める
理論節で述べた「状態 $\times$ 位相の積グラフ上の最短経路」をそのまま実装します。
import heapq
import numpy as np
def dfree(P):
"""パンクチャ符号の自由距離を、(状態, 位相) の積グラフ上の最短経路で求める"""
p = P.shape[1]
best = np.inf
for phi0 in range(p): # 分岐する位相を全通り試す
dist, pq = {}, []
# 全ゼロ経路から入力1で分岐する最初の枝
w0 = int(sum(out_bits[0, 1, j] * P[j, phi0] for j in range(2)))
heapq.heappush(pq, (w0, (int(next_state[0, 1]), (phi0 + 1) % p)))
while pq:
d, node = heapq.heappop(pq)
if node in dist:
continue
dist[node] = d
s, ph = node
if s == 0: # 全ゼロ状態に再合流した
best = min(best, d)
continue
for b in (0, 1):
w = int(sum(out_bits[s, b, j] * P[j, ph] for j in range(2)))
nb = (int(next_state[s, b]), (ph + 1) % p)
if nb not in dist:
heapq.heappush(pq, (d + w, nb))
return int(best)
print(f"{'率':>5} {'d_free':>7} {'R*d_free':>9} {'漸近利得[dB]':>12}")
for name, P in PATTERNS.items():
R, df = rate_of(P), dfree(P)
print(f"{name:>5} {df:7d} {R*df:9.2f} {10*np.log10(R*df):12.2f}")
実行結果は次のとおりです。
率 d_free R*d_free 漸近利得[dB]
1/2 10 5.00 6.99
2/3 6 4.00 6.02
3/4 5 3.75 5.74
5/6 4 3.33 5.23
7/8 3 2.62 4.19
母符号の $d_{\text{free}} = 10$ が正しく再現され、パンクチャによって $6, 5, 4, 3$ と単調に減っていく様子が確認できました。これらの値は文献に報告されている $K=7$ パンクチャ符号の自由距離と完全に一致します。積 $R \cdot d_{\text{free}}$ の列を見ると、レートを $1.75$ 倍にしても符号化利得の目減りが $2.8$ dBにとどまることが数値で確かめられます。
最適なパンクチャリング行列を全探索する
$d_{\text{free}}$ が高速に計算できるので、行列の全探索が現実的になります。
import itertools
import numpy as np
def search_best(p, keep):
"""周期p、送信keepビットの全パンクチャ行列を試し d_free 最大を探す"""
results = []
for combo in itertools.combinations(range(2 * p), keep):
P = np.zeros(2 * p, dtype=int); P[list(combo)] = 1
P = P.reshape(2, p)
if P.sum(axis=0).min() == 0:
continue # 全ゼロ列は情報が消えるので除外
results.append((dfree(P), P.copy()))
results.sort(key=lambda t: -t[0])
return results
for p, keep, label in [(2, 3, "2/3"), (3, 4, "3/4"), (5, 6, "5/6")]:
res = search_best(p, keep)
print(f"[{label}] 候補{len(res)}通り, 最大 d_free = {res[0][0]}")
for d, P in res[:3]:
print(f" d_free={d} P={P.tolist()}")
出力から、$3/4$ の最大 $d_{\text{free}}$ は $5$ で、$\bm{P} = [[1,1,0],[1,0,1]]$ がそれを達成することがわかります。一方、$1$ の個数も配置の対称性もよく似た $[[1,0,1],[1,1,0]]$ は $d_{\text{free}}=4$ にとどまります。生成多項式 $(133)_8$ と $(171)_8$ が非対称であるため、どのストリームのどの位相を削るかで結果が変わる、という理論節の指摘が数値で裏付けられました。
BERシミュレーション
いよいよ性能測定です。ランダムな情報ビットにテイルビット（$K-1=6$ 個の $0$）を付けて符号化し、パンクチャして、BPSK・AWGNを通し、デパンクチャして復号します。雑音の分散は $\sigma^2 = 1/(2 R E_b/N_0)$ です。
import numpy as np
def simulate(P, ebn0_db, fill=0.0, n_info=1024, batch=400,
max_frames=60000, target_err=500, seed=0):
"""指定レート・指定Eb/N0でのBERを測る。fillは穿孔位置に入れる値"""
rng = np.random.default_rng(seed)
p, R = P.shape[1], rate_of(P)
sigma = np.sqrt(1.0 / (2 * R * 10 ** (ebn0_db / 10)))
Lp = int(np.ceil((n_info + K - 1) / p) * p) # 周期pの倍数に切り上げ
m = make_mask(P, Lp).astype(float) # (Lp, 2)
errs = nbits = 0
while nbits < max_frames * n_info:
info = rng.integers(0, 2, size=(batch, Lp))
info[:, n_info:] = 0 # テイルビット
x = 1.0 - 2.0 * encode(info) # BPSK
y = x + sigma * rng.standard_normal(x.shape)
y = y * m[None] + fill * (1 - m)[None] # 穿孔＆デパンクチャ
dec = viterbi(y)
errs += int(np.sum(dec[:, :n_info] != info[:, :n_info]))
nbits += batch * n_info
if errs >= target_err: # 十分な誤り数が貯まったら終了
break
return errs / nbits
y = y * m[None] + fill * (1 - m)[None] の1行が、送信側のパンクチャと受信側のデパンクチャを同時に表現しています。マスクが $1$ の位置は受信値をそのまま通し、$0$ の位置は fill で置き換えます。既定値の fill=0.0 が正しいゼロ挿入です。この fill を後で $\pm 1$ に変えて、間違った復号を実演します。
BER曲線を描く
各レートについて $E_b/N_0$ を掃引します。
import numpy as np
import matplotlib, matplotlib.pyplot as plt
from scipy.special import erfc
for cand in ["Hiragino Sans", "Yu Gothic", "Noto Sans CJK JP", "IPAexGothic"]:
if any(cand == f.name for f in matplotlib.font_manager.fontManager.ttflist):
plt.rcParams["font.family"] = cand
break
plt.rcParams["axes.unicode_minus"] = False
grids = {"1/2": np.arange(1.0, 5.51, 0.5), "2/3": np.arange(1.5, 6.01, 0.5),
"3/4": np.arange(2.0, 6.51, 0.5), "5/6": np.arange(2.5, 7.01, 0.5),
"7/8": np.arange(3.0, 7.51, 0.5)}
plt.figure(figsize=(9, 6))
for i, (name, P) in enumerate(PATTERNS.items()):
e = grids[name]
ber = [simulate(P, x, seed=1000 * i + int(x * 10)) for x in e]
plt.semilogy(e, np.maximum(ber, 1e-7), "o-",
label=f"パンクチャ後 $r={name}$（$d_{{free}}$={dfree(P)}）")
eb = np.arange(0, 11, 0.25)
plt.semilogy(eb, 0.5 * erfc(np.sqrt(10 ** (eb / 10))), "k--",
label="未符号化BPSK（理論）")
plt.xlabel("$E_b/N_0$ [dB]"); plt.ylabel("ビット誤り率 BER")
plt.title("パンクチャ畳み込み符号のBER特性（母符号 $K=7$, 軟判定ビタビ）")
plt.grid(True, which="both", alpha=0.3); plt.legend(); plt.ylim(1e-6, 1)
plt.tight_layout(); plt.show()
実測されたBERは次のようになりました（各点は誤りが500個以上たまるまで、最大で6千万ビットを走らせた結果です）。
| $E_b/N_0$ [dB] | $r=1/2$ | $r=2/3$ | $r=3/4$ | $r=5/6$ | $r=7/8$ |
|---|---|---|---|---|---|
| 3.0 | $3.37\times10^{-4}$ | $1.85\times10^{-3}$ | $6.91\times10^{-3}$ | $2.69\times10^{-2}$ | $7.45\times10^{-2}$ |
| 3.5 | $8.38\times10^{-5}$ | $3.18\times10^{-4}$ | $1.93\times10^{-3}$ | $6.91\times10^{-3}$ | $2.96\times10^{-2}$ |
| 4.0 | $1.51\times10^{-5}$ | $8.58\times10^{-5}$ | $3.41\times10^{-4}$ | $2.08\times10^{-3}$ | $6.56\times10^{-3}$ |
| 4.5 | $2.67\times10^{-6}$ | $1.20\times10^{-5}$ | $6.40\times10^{-5}$ | $4.13\times10^{-4}$ | $1.22\times10^{-3}$ |
| 5.0 | $1.14\times10^{-7}$ | $2.80\times10^{-6}$ | $1.55\times10^{-5}$ | $1.06\times10^{-4}$ | $2.74\times10^{-4}$ |
| 5.5 | — | $1.95\times10^{-7}$ | $2.41\times10^{-6}$ | $1.62\times10^{-5}$ | $6.35\times10^{-5}$ |
| 6.0 | — | — | $4.88\times10^{-7}$ | $2.16\times10^{-6}$ | $1.06\times10^{-5}$ |
このBER曲線から3つのことが読み取れます。第一に、実用域（BER $10^{-4}$ 以下）ではどのレートの曲線も未符号化BPSK（$10^{-5}$ に $9.59$ dBを要する）よりはるかに左にあり、パンクチャしてもなお十分な符号化利得が残っています。ただし図をよく見ると、$r=7/8$ の曲線は $E_b/N_0$ が $4$ dBを下回るあたりで、$r=5/6$ も $3$ dB付近で、未符号化BPSKと交差しています。冗長を削りすぎた符号は低SNR域では逆に不利になる、という符号化利得の一般的な性質がここにも現れています。第二に、レートが上がるほど曲線は右にシフトしますが、そのシフト量は $1/2 \to 7/8$ で $2$ dB弱と穏やかです。第三に、曲線の傾き（$E_b/N_0$ を $1$ dB上げたときのBERの下がり方）はレートが高いほど緩やかで、これは $d_{\text{free}}$ が小さいことの直接的な現れです。$Q(\sqrt{2Rd_{\text{free}}E_b/N_0})$ の形から、指数の中身に $d_{\text{free}}$ が入っているためです。
レートと所要 $E_b/N_0$ のトレードオフ表
各曲線から、BER $=10^{-5}$ と $10^{-4}$ を達成する $E_b/N_0$ を対数線形補間で読み取り、表にまとめます。
import numpy as np
from scipy.special import erfc
from scipy.optimize import brentq
def required_ebn0(e, ber, target):
"""BER曲線から目標BERを達成する Eb/N0 を対数線形補間で求める"""
lb = np.log10(np.maximum(ber, 1e-12)); t = np.log10(target)
i = np.where((lb[:-1] > t) & (lb[1:] <= t))[0][0]
return e[i] + (t - lb[i]) * (e[i+1] - e[i]) / (lb[i+1] - lb[i])
# 未符号化BPSKの所要 Eb/N0（比較の基準）
unc = brentq(lambda x: 0.5 * erfc(np.sqrt(10 ** (x / 10))) - 1e-5, 0, 15)
print(f"未符号化BPSKの所要 Eb/N0 (BER=1e-5): {unc:.2f} dB")
# シャノン限界（実AWGN, 符号化率R）: Eb/N0 > (2^{2R} - 1) / (2R)
for name, P in PATTERNS.items():
R = rate_of(P)
lim = 10 * np.log10((2 ** (2 * R) - 1) / (2 * R))
print(f"r={name}: シャノン限界 = {lim:.2f} dB")
この計算と先ほどのBER測定を突き合わせると、次の総括表が得られます。
| 符号化率 $R$ | $d_{\text{free}}$ | 漸近利得 [dB] | 所要 $E_b/N_0$ @ $10^{-4}$ | 所要 $E_b/N_0$ @ $10^{-5}$ | 実測利得 @ $10^{-5}$ | シャノン限界 [dB] | 限界との差 |
|---|---|---|---|---|---|---|---|
| $1/2$ | 10 | 6.99 | 3.44 | 4.12 | 5.47 | 0.00 | 4.12 |
| $2/3$ | 6 | 6.02 | 3.94 | 4.56 | 5.03 | 0.57 | 3.99 |
| $3/4$ | 5 | 5.74 | 4.37 | 5.12 | 4.47 | 0.86 | 4.26 |
| $5/6$ | 4 | 5.23 | 5.01 | 5.62 | 3.97 | 1.16 | 4.46 |
| $7/8$ | 3 | 4.19 | 5.34 | 6.02 | 3.57 | 1.31 | 4.71 |
| 未符号化 | — | — | 8.40 | 9.59 | 0 | — | — |
この表を2枚のグラフにしたのが上の図です。左では、所要 $E_b/N_0$（青と緑）が右上がりのほぼ直線で並び、その下の灰色のシャノン限界との縦の隔たりが $4.1, 4.0, 4.3, 4.5, 4.7$ dBとどのレートでもほとんど変わらないことが見て取れます。同じ強さの母符号を使い回している以上、限界からの距離が一定になるのは自然な結果です。右のグラフは漸近利得（薄い青）と実測利得（濃い青）の対比で、どのレートでも実測が $0.6 \sim 1.5$ dBほど下回っています。漸近利得はあくまで「これ以上は望めない上限」であって、実際に得られる利得ではないことがはっきりします。
この表がパンクチャリングの費用対効果をすべて語っています。読み取れることを整理します。
- レートを上げる代償は驚くほど小さい。$r=1/2$ から $r=7/8$ へ、スループットを $1.75$ 倍にするのに必要な追加電力は $6.02 – 4.12 = 1.90$ dBだけです。もし符号化をやめてスループットを2倍にしたら、$9.59 – 4.12 = 5.47$ dBの追加が必要になります。パンクチャは「符号化をやめる」よりずっと有利な帯域の買い方です。
- 実測利得は漸近利得より小さい。たとえば $r=1/2$ の漸近利得は $6.99$ dBですが、BER $10^{-5}$ での実測利得は $5.47$ dBです。差の約 $1.5$ dBは、$d_{\text{free}}$ 以外の距離を持つ経路の寄与によるものです。漸近利得はあくまで $E_b/N_0 \to \infty$ での極限値であり、実用SNR域では「上限の目安」として使うべき数字です。
- シャノン限界との差はどのレートでもほぼ一定（$4.0 \sim 4.7$ dB）。これは $K=7$ 畳み込み符号という「同じ強さの母符号」を使い回している以上、当然の結果です。この $4$ dBのギャップを埋めるのがターボ符号やLDPC符号であり、実際にそれらの符号でもレート可変にはパンクチャリングが使われます。
- 所要 $E_b/N_0$ とレートの関係はほぼ線形。$4.12, 4.56, 5.12, 5.62, 6.02$ と、レートを上げるごとに $0.5$ dB前後ずつ増えていきます。これは適応変調符号化のMCSテーブルを設計するときに便利な性質で、「SNRが $0.5$ dB改善したら1段上のMCSに上げる」という単純な制御が成り立ちます。
実験1: パンクチャリング行列の選び方の影響
理論節で、同じ $r=3/4$ でも行列の選び方で $d_{\text{free}}$ が $5$ か $4$ かに分かれることを見ました。それが本当に性能に効くのか実測します。
import numpy as np
P_opt = np.array([[1, 1, 0], [1, 0, 1]]) # d_free = 5
P_sub = np.array([[1, 0, 1], [1, 1, 0]]) # d_free = 4
print(f"P_opt の d_free = {dfree(P_opt)}, P_sub の d_free = {dfree(P_sub)}")
for e in [3.0, 3.5, 4.0, 4.5, 5.0, 5.5]:
a = simulate(P_opt, e, target_err=400, seed=int(e * 10) + 7)
b = simulate(P_sub, e, target_err=400, seed=int(e * 10) + 7)
print(f"Eb/N0={e:.1f}dB 最適(d=5): {a:.3e} 非最適(d=4): {b:.3e}"
f" 比 = {b / max(a, 1e-12):.1f}倍")
実行結果は次のとおりです。
| $E_b/N_0$ [dB] | 最適 $\bm{P}$（$d_{\text{free}}=5$） | 非最適 $\bm{P}$（$d_{\text{free}}=4$） | BER比 |
|---|---|---|---|
| 3.0 | $6.27\times10^{-3}$ | $1.37\times10^{-2}$ | 2.2倍 |
| 4.0 | $2.91\times10^{-4}$ | $1.35\times10^{-3}$ | 4.6倍 |
| 5.0 | $1.88\times10^{-5}$ | $1.47\times10^{-4}$ | 7.8倍 |
| 5.5 | $3.52\times10^{-6}$ | $2.35\times10^{-5}$ | 6.7倍 |
左のグラフでは、2本の曲線が単に平行移動しているのではなく、SNRが上がるにつれてじわじわ開いていくのがわかります。右の棒グラフはその開き具合を比で示したもので、$3.0$ dBで $2.2$ 倍だったものが $5.0$ dBでは $7.8$ 倍にまで拡大します。曲線が平行なら比は一定になるはずですから、比が増えること自体が「2本の傾きが違う」ことの証拠であり、その傾きを決めているのが $d_{\text{free}}$ の $5$ と $4$ という差なのです。
$1$ を4個残すという条件はまったく同じで、配置だけが違う2つの行列です。それでもBERは高SNR側で7倍以上開き、BER $10^{-5}$ を達成する $E_b/N_0$ にすると約 $0.6$ dBの差になります。しかもBER比がSNRとともに拡大している点に注目してください。これは曲線の傾きが違う — つまり $d_{\text{free}}$ の違いが効いている — 証拠です。漸近利得の予測差 $0.97$ dBよりやや小さいのは、この SNR 域ではまだ漸近域に入りきっていないためです。パンクチャリング行列は「なんとなく間引く」のではなく、設計対象なのだと納得できる結果です。
実験2: ゼロ挿入でないとどうなるか
最後に、復号側のゼロ挿入が本当に必要かを確かめます。穿孔位置に $0$ の代わりに $+1$（「$c=0$ を確信度高く受信した」に相当）や $-1$（「$c=1$ を確信度高く受信した」に相当）を入れてみます。
import numpy as np
P = PATTERNS["3/4"]
print(f"{'Eb/N0':>7} {'fill=0（正しい）':>18} {'fill=+1':>12} {'fill=-1':>12}")
for e in [3.0, 4.0, 5.0]:
z = simulate(P, e, fill=0.0, target_err=400, seed=int(e * 10) + 3)
p1 = simulate(P, e, fill=1.0, target_err=400, seed=int(e * 10) + 3)
m1 = simulate(P, e, fill=-1.0, target_err=400, seed=int(e * 10) + 3)
print(f"{e:7.1f} {z:18.3e} {p1:12.3e} {m1:12.3e}")
結果は劇的です。
| $E_b/N_0$ [dB] | fill=0（正しい） |
fill=+1 |
fill=-1 |
|---|---|---|---|
| 3.0 | $7.07\times10^{-3}$ | $4.82\times10^{-1}$ | $4.83\times10^{-1}$ |
| 4.0 | $3.31\times10^{-4}$ | $4.81\times10^{-1}$ | $4.81\times10^{-1}$ |
| 5.0 | $1.40\times10^{-5}$ | $4.75\times10^{-1}$ | $4.76\times10^{-1}$ |
対数目盛のこの図では、正しいゼロ挿入（青）が右下がりに $7.1\times10^{-3}$ から $1.4\times10^{-5}$ まで3桁近く下がっていくのに対し、$+1$（赤）と $-1$（橙）は $0.5$ の点線に張り付いたまま完全な水平線になっています。しかも $+1$ と $-1$ の2本がほぼ重なっている点も示唆的で、「どちらの嘘をついたか」は結果に関係なく、「嘘をついた」という事実だけがBERを決めているのです。
$\pm 1$ を挿入した場合、BERは $E_b/N_0$ をいくら上げても $0.48$ 前後から動きません。これは「ほぼコイン投げ」であり、復号が完全に破綻していることを意味します。全符号ビットの $1/3$ に無根拠な確信を注入したせいで、ビタビ復号器は誤った経路を強く支持してしまい、正しい経路が生き残れなくなるのです。
さらに重要なのは、$E_b/N_0$ を上げても改善しない点です。通常の雑音による誤りなら電力を上げれば減りますが、この誤りは雑音由来ではなく「復号器に嘘の情報を与えている」ことによる系統的誤りなので、電力ではどうにもなりません。ゼロ挿入は「あったほうがよい工夫」ではなく、パンクチャ方式が成立するための必要条件だということが、この実験から明確にわかります。
数値検証がそろいました。最後に、いま学んだ原理が実際の通信規格でどう使われているかを見ておきましょう。
実システムでのレートマッチング
3GPP方式 — 循環バッファ
LTE/5G NRのレートマッチングは、パンクチャリングをより一般化した形で実装されています。手順の概略は次のとおりです。
- ターボ符号（LTE）またはLDPC符号（NR）で符号語を作る
- 符号ビットをサブブロックインタリーバで並べ替え、循環バッファ（circular buffer）に格納する
- 割り当てられた物理リソース量から必要ビット数 $N$ を決める
- 循環バッファの指定位置（冗長バージョン RV: Redundancy Version）から $N$ ビットを順に読み出す
左のリングが循環バッファで、シアンが初回に読み出されるビット、灰色が読まれない（＝穿孔される）ビットです。この例では母符号24ビットのうち16ビットを読むので $R = 12/16 = 3/4$ になり、記事前半でパンクチャリング行列を使って作ったのと同じ符号化率が、「読み出し量を決める」という別の言い方で実現されています。右のグラフは読み出し量 $N$ と実効符号化率の関係で、$N$ を整数で1つずつ動かすだけでレートが連続的に変わり、標準パターンの $1/2, 2/3, 3/4, 5/6, 7/8$ はその曲線上の飛び飛びの点に過ぎないことがわかります。バッファ長の $24$ を超えて読めば同じビットが2度読まれ、$R < 1/2$ のリピティション領域（橙）に入ります。
この方式が優れているのは、$N$ がバッファ長より小さければ読み出されなかったビットが自動的に穿孔され（パンクチャリング）、$N$ がバッファ長より大きければバッファを一周して同じビットが再び読まれる（リピティション）点です。1つの読み出し規則が両方を吸収します。しかも $N$ は任意の整数でよいので、レートは離散的な $1/2, 3/4, \dots$ に限られず、連続的に近い細かさで調整できます。
IR-HARQ — 後から冗長を足す
冗長バージョンの仕組みは、インクリメンタル・リダンダンシHARQ（IR-HARQ）と直結しています。初回送信では RV0 から $N$ ビットを読み出して送ります。復号に失敗したら、次は RV2 のように別の開始位置から読み出して送ります。すると、初回に穿孔されて届かなかったビットが今度は届きます。
受信側は初回の軟判定値と再送ぶんを保持し、同じ位置のビットについては合成（軟合成）し、初回に $0$ だった位置には新しく届いた値を入れます。結果として、実効的な符号化率が $3/4$ から $1/2$ へ、さらに $1/3$ へと段階的に下がり、復号成功率が上がっていきます。母符号が共通だからこそ、「後から冗長を継ぎ足す」というこの芸当が可能になるのです。パンクチャリングは単なるレート調整の道具にとどまらず、再送プロトコルの土台でもあるわけです。
パンクチャリングとショートニング
LDPC符号やターボ符号の文脈では、ショートニング（shortening）という別の操作もよく登場します。
- パンクチャリング: 符号語ビットを送信しない。受信側はそこをLLR $=0$（消失）として扱う。符号化率は上がる
- ショートニング: 情報ビットの一部を固定値（通常 $0$）にして送らない。受信側はそこをLLR $= +\infty$（完全に既知）として扱う。符号化率は下がる
どちらも「送らない」点は同じですが、受信側で入れるLLRが $0$ か $\pm\infty$ かで正反対です。前者は「知らない」、後者は「完璧に知っている」を表します。この違いは本記事の実験2と地続きの話で、「送らなかったビットについて、受信側が何を知っているか」を正しくLLRに反映することが復号の生命線だという点で共通しています。
5G NRのLDPC符号では両方が使われます。ベースグラフの先頭 $2Z$ 個の変数ノードは常に穿孔され（送信されない）、情報ブロックのサイズ調整にはフィラービットによるショートニングが使われます。
畳み込み符号系の規格
本記事で扱った $K=7$、$(133,171)_8$ の母符号にパンクチャをかける構成は、次の規格で採用されています。
- IEEE 802.11a/g/n/ac（Wi-Fi）: $r = 1/2, 2/3, 3/4$（さらに802.11n以降で $5/6$）。変調（BPSK/QPSK/16QAM/64QAM）との組み合わせでMCSインデックスを構成
- DVB-S / DVB-T（デジタル衛星・地上波放送）: $r = 1/2, 2/3, 3/4, 5/6, 7/8$。降雨減衰や受信環境に応じて選択
- CCSDS（宇宙データシステム）: 深宇宙・地球周回ミッションの標準。$r=1/2$ を基本とし、リンクに余裕があるときはパンクチャレートを使用
これらの規格が同じ母符号を共有していることは、偶然ではありません。$K=7$ という拘束長は「64状態のビタビ復号器なら合理的なコストで作れる」上限に近く、$(133,171)_8$ はその制約下での最良の生成多項式です。そして、そこから先のレートの多様性はすべてパンクチャリングが供給している、という構図になっています。
限界と注意点
最後に、パンクチャリングの限界も押さえておきましょう。
専用の高レート符号には少し劣る: 等価な高レート時不変符号として最良のものと比べると、パンクチャで作った符号はわずかに距離特性が劣ることがあります。母符号という制約の下での最良でしかないからです。ただしその差は多くの場合 $0.1 \sim 0.3$ dB程度で、復号器を共有できる利益のほうが圧倒的に大きいと判断されています。
位相同期のコスト: 前述のとおり、デパンクチャ位相の同期が必要です。周期 $p$ が大きいほど候補が増え、同期の獲得時間が延びます。$r=7/8$ の周期7では、$x/y$ の入れ替わりも含めて14通りを試すことになります。
高レートほどエラーフロアが見えやすい: $d_{\text{free}}$ が $3$ や $4$ しかないと、少数の低重み経路がBERを支配します。距離スペクトルの係数 $\beta_{d_{\text{free}}}$ が大きい行列を選んでしまうと、高SNR域で曲線が寝てしまいます。
反復復号符号ではより繊細: ターボ符号やLDPC符号にパンクチャをかける場合、どのビットを穿孔するかがメッセージ伝搬の収束性を直接左右します。LDPC符号では、次数の低い変数ノードを穿孔すると、そのノードが最後まで情報を得られず復号が止まってしまうことがあります。畳み込み符号のように「距離だけ見ればよい」とはいかず、グラフ構造まで考慮した設計が必要です。
まとめ
本記事では、パンクチャリングとレートマッチングの理論を、$K=7$、$r=1/2$ の母符号を題材に解説しました。
- パンクチャリングの原理: $n_0 \times p$ のパンクチャリング行列 $\bm{P}$ が、母符号の出力のうちどれを送るかを周期的に指定します。符号化率は $R = k_0 p / w(\bm{P})$ で、$\bm{P}$ の $1$ の個数だけで決まります。$\bm{P} = [[1,1,0],[1,0,1]]$ を使えば、6情報ビットあたりの送信が12ビットから8ビットに減り、$r=1/2$ が $r=3/4$ になることをビット単位で確認しました
- パンクチャ符号の正体: 周期 $p$ の時変畳み込み符号であり、$p$ 時刻をまとめれば $(p, w(\bm{P}))$ の時不変高レート符号と等価です。それでも直接設計せずパンクチャを使うのは、復号器のトレリスを母符号のまま（合流数2、64状態）に保てるからです
- 自由距離の低下: パンクチャは経路重みを減らす方向にしか働かず、$d_{\text{free}}$ は $10 \to 6 \to 5 \to 4 \to 3$ と単調に下がります。計算は状態 $\times$ 位相の積グラフ上のダイクストラで行えます
- 符号化利得との関係: 対経路誤り確率 $Q(\sqrt{2Rd E_b/N_0})$ の導出から、漸近符号化利得が $10\log_{10}(R \, d_{\text{free}})$ になることを示しました。実測では $r=1/2$ で $5.47$ dB、$r=7/8$ で $3.57$ dB（BER $10^{-5}$ 基準）の利得が得られ、レートを $1.75$ 倍にする代償は $1.90$ dBにとどまりました
- 行列の選び方は設計問題: 同じ $r=3/4$ でも配置が違えば $d_{\text{free}}$ が $5$ と $4$ に分かれ、実測で約 $0.6$ dB、BER比で7倍以上の差が出ます。全探索で最適パターンを求めると、規格の値がそのまま再現されます
- ゼロ挿入が要: 穿孔ビットは「$0$ を送った」のではなく「情報が存在しない」状態です。LLRの定義から $L=0$、すなわち軟判定値 $0$ を入れるのが正解で、これにより母符号のトレリスを無改造で流用できます。$\pm 1$ を入れるとBERは $0.48$ に張り付き、電力を上げても改善しません
パンクチャリングは、「符号を新しく作る」のではなく「既にある符号から必要なぶんだけ取り出す」という発想の転換です。この考え方は、循環バッファによるレートマッチング、IR-HARQ、5G NRのLDPC符号のレート適応へとまっすぐつながっています。ハードウェアを共有しながら性能を連続的に調整するという設計思想は、通信システム設計の中でも特に美しい部分だと思います。
次のステップとして、以下の記事も参考にしてください。
- 畳み込み符号とビタビ復号の理論 — 母符号とトレリス復号の基礎
- 軟判定復号の理論 — ゼロ挿入が成り立つ前提となるLLRの扱い
- ターボ符号の理論 — 反復復号符号におけるパンクチャリング
- LDPC符号の理論 — 5G NRのレートマッチングが適用される符号
- トレリス符号化変調（TCM） — 符号化と変調を統合してレートと距離を両立させる別のアプローチ