JCCA2026_Wei
>100 Views
September 04, 26
スライド概要
🤖 Assistant Prof. at TTI | Machine Learning × Communications | Gifu 🏔️ 🚃→ Nagoya 🏙️ 🚗 → TTI commuter | ⭐ Stargazing enthusiast | 🕸️ Homepage: https://h.weilantian.net
（ダウンロード不可）
関連スライド
各ページのテキスト
近接勾配復号における非符号語停留状態と メタダイナミクスによる回避 魏 藍天 豊田工業大学 JCCA 離散数学とその応用研究集会 2026 ミニシンポジウム「暗号・符号・人工知能」 2026 年 8 月 18 日
はじめに 背景 • 近接勾配復号 [Wadayama ISIT2021]：通信路の尤度と符号制約を合わせ， 復号を連続最適化として扱うアプローチ • 単純な演算のみで構成され，並列処理にも向く • 通信路モデルに応じて拡張しやすい（例：MIMO 検出との一括処理） 動機 • AWGN 通信路では BP に対して大きな性能差が残る • 主な原因は，反復が非符号語停留状態に陥ること 本日の内容 • 近接勾配復号の既存の改善法を紹介 • メタダイナミクスに基づく新しい改善法を提案 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 2 / 21
LDPC 符号と符号語の条件 スパースなパリティ検査行列 H ∈ {0, 1}m×n ，符号 C(H) = {b ∈ {0, 1}n : Hb = 0} バイポーラ表現（BPSK 写像）：b 7→ x = 1 − 2b ∈ {+1, −1}n 符号語であるための 2 条件 バイポーラ制約： xj ∈ {±1} (∀j) Q パリティ検査制約： j∈A(i) xj = 1 (∀i) (1) (2) ここで A(i) = { j : Hij = 1 }（検査 i に関与するビット位置の集合） 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 3 / 21
符号制約多項式 両制約 (1)(2) を一つの多項式にまとめる（符号制約多項式）： h(x) = n X j=1 | m Y 2 X 2 xj2 − 1 + xj − 1 (3) i=1 j∈A(i) {z } バイポーラ制約 | {z パリティ検査制約 } h(x) ≥ 0，かつ h(x) = 0 ⇐⇒ x はバイポーラ符号語 勾配は閉形式で計算できる（B(j) = { i : Hij = 1 }）： Y X Y ∂h = 4xj xj2 − 1 + 2 xl − 1 ∂xj i∈B(j) l∈A(i) xl (4) l∈A(i)\{j} x がバイポーラ符号語 ⇒ ∇h(x) = 0．逆は成り立たない（例：x = 0 でも ∇h = 0） → h には符号語でない停留点が存在する 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 4 / 21
近接勾配復号 [Wadayama ISIT2021] 受信語 y から，二つの項の和を連続最適化として最小化 目的関数 min x∈Rn L(x; y) | {z } 通信路項：負対数尤度 (5) h(x) |{z} + γ 符号制約項：符号語集合への引き込み 反復式 r (t) = s (t) − ω ∇L(s (t) ; y) s (t+1) = r (t) − γ ∇h r (t) （通信路項の勾配ステップ） (6) （符号制約項の近接ステップ） (7) 例：MIMO 通信路 y = Ax + w では ∇L = A> (As − y) → 検出と復号を分離せず一括処理できる 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 5 / 21
MIMO 通信路での性能 ρ = 0.0 (uncorrelated) ρ = 0.4 (correlated) 10−1 BER 10−2 10−3 Proximal tanh detector 10 MMSE + BP −4 MMSE 5 6 7 8 9 5 SNR [dB] 6 7 8 9 SNR [dB] 102 × 102 相関 MIMO，符号長 n = 204 相関が強い通信路ほどベースライン（MMSE+BP）との差が広がる 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 6 / 21
AWGN 通信路での性能：BP との差 AWGN 通信路 y = x + w では，(5) の L = 12 kx − yk22 ， ∇L(s; y) = s − y 10−1 10−2 BER 10−3 10−4 10−5 10−6 Proximal BP 10−7 2.0 2.5 3.0 3.5 4.0 4.5 5.0 Eb/N0 [dB] AWGN では BP との差が大きい（同水準の誤り率で約 2 dB） 主な原因は反復が非符号語停留状態に陥ること [Tsouchlos, IEEE Commun. Lett. 2024] 目的：近接勾配復号の性能を改善し，BP との差を縮める． 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 7 / 21
復号失敗の実像：非符号語停留状態 violated checks 失敗フレームの典型例（n = 204，3.5 dB） 20 シンドロームが非零のまま bit errors 0 10 ビット誤りが残ったまま ‖st + 1 − st‖2 0 100 更新量は 0 に収束しない 10−3 0 50 100 150 200 250 300 iteration t 硬判定は凍結し，連続状態は狭い領域内で振動し続ける 反復を増やしても抜け出せない 失敗の原因は収束の遅さではなく，非符号語停留状態に陥ること． 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 8 / 21
既存の改善法 1：リストベース最適化 [Tsouchlos 2024] 失敗時：∇L と ∇h が逆向きに振動し続ける 振動の大きいビットほど誤り確率が高い 反復終了後，振動の大きい N ビットを反転した 2N 個の候補に対して ML 復号（約 +1 dB，N = 8） 限界：誤り位置が N ビットに含まれなければ救えない．復号力学は変えな い後処理 図：[Tsouchlos, Jäkel, Schmalen, IEEE Commun. Lett. 2024] Fig. 3, 4 より 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 9 / 21
既存の改善法 2：SAEPD [Yang 2025] SAEPD：Sequential Automorphism-Enhanced Proximal Decoding 巡回符号の自己同型群（巡回シフト）を利用 受信語 y を置換 π(y) して同じ復号器に入力し，成功するまで置換 を変えて再復号．結果を逆置換して出力 巡回符号（EG 符号など）では min-sum 復号に匹敵する性能 限界 自己同型構造を持つ符号にしか使えない 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 10 / 21
最初の試み：ランダム初期値による並列復号 ランダム初期値 s (0) = 0.1 ε，ε ∼ N (0, I ) から P 個の復号を並列実行 選択：シンドロームを満たす候補のうち y との相関が最大のもの 10−1 10−2 BER 10−3 10−4 P = 1 (baseline) 10−5 P = 10 P = 100 BP 10−6 2.0 2.5 3.0 3.5 4.0 4.5 5.0 5.5 Eb/N0 [dB] P を増やすほど改善：近接勾配復号はまだ伸びしろがある しかし計算量は P 倍．長い符号ほど必要な P も増え，実用的でない 陥ったことはパリティ検査で即座に分かる（一般の非凸最適化にはない利 点） ．→ 陥ったら脱出する仕組みへ 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 11 / 21
離散側の先例：Tabu 型ビットフリッピング復号 GDBF [Wadayama 2010]：同じ目的関数を {±1}n 上で最適化するビット反 転復号 NGDBF [Sundararajan 2014]：雑音を加えて局所解から抜け出す Tabu 型 [Zhang 2019; Cui 2019]：最近反転したビットを記憶し，しばらく 再反転を禁止することで同じ状態への逆戻りを防ぐ 離散側での知見 「どこにいたか」を記憶する復号器は，記憶しない復号器より強い では，連続の場合は？ 連続状態空間 Rn では，何を，どのような形で記憶すればよいか 離散：反転したビット → 禁止リスト 連続：陥った非符号語停留状態 → 空間上の反発ポテンシャル 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 12 / 21
メタダイナミクス：停留状態にポテンシャルを置く 分子動力学の手法 [Laio & Parrinello 2002]：訪れた場所にガウス型ポテン シャルを積み上げ，同じ谷に戻れなくする 本手法では，陥った非符号語停留状態 c 1 , . . . , c r にポテンシャルを置く r kx − c k2 X k 2 Vr (x) = ρ exp − , ρ：ポテンシャルの高さ，σ：広がり (8) 2σ 2 k=1 反復式 (7) には勾配項を 1 つ加えるだけ（再開時は c r から微小にずらして 出発） ： s (t+1) = r (t) − γ ∇h(r (t) ) + ∇Vr (r (t) ) (9) −∇Vr は各 c k から遠ざける力．ポテンシャルは局所的で，遠くの地形は ほぼ変えない 陥った停留状態をすべて記憶し，ポテンシャルを蓄積していく 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 13 / 21
提案復号器の全体フロー 近接勾配復号 （最大 100 反復） シンドローム = 0 ? ポイント はい 出力 （追加処理なし） いいえ 停留状態 c r を記録し ポテンシャルを 1 つ追加 ウォームリスタート s (0) = c r + 0.05 ε，ε ∼ N (0, I ) ポテンシャル付き反復 （∇h + ∇Vr ，100 反復） ポテンシャルを置くのはシ ンドロームが非零の状態だ け．符号語の上には置か ない 一発で成功したフレームは 通常の復号と全く同じ 追加ラウンドは平均 0.2 回/フレーム（n = 204， 4.5 dB） 最大 r = 19 ラウンド（総反復数 2000） 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 14 / 21
‖st − strap‖2 脱出の実例：同一フレーム・同一初期値での比較 ポテンシャルに押されて谷の外へ 最初の 100 反復：トラップ内で振動 10 5 0 violated checks bit errors count 15 復号成功 10 5 0 0 50 100 150 200 cumulative kernel iteration 受信語も初期値も失敗例と同じ．ポテンシャルを 2 つ置き，計 236 反復で 復号成功 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 15 / 21
復号性能：並列復号との比較（n = 204） FER 10−1 10−2 baseline parallel decoding, P = 4 parallel decoding, P = 10 metadynamics, r = 3 10−3 metadynamics, r = 9 metadynamics, r = 19 3.0 3.5 4.0 4.5 5.0 Eb/N0 [dB] 再開回数 r を増やすほど改善し，r = 9 で並列復号 P = 10 を上回る r = 19 でも平均反復数は baseline の 1.6 倍（再開は失敗フレームだけ）． 並列復号は全フレームで P 倍 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 16 / 21
性能と計算量のトレードオフ 横軸は実測の平均反復数（n = 204，4.5 dB）．右に行くほど計算量 が大きい 10−1 baseline parallel decoding, P = 4 FER metadynamics, r = 3 10−2 P = 10 r=9 r = 19 10−3 20 30 50 100 200 300 500 mean iterations per frame 記憶を深める（r ↑）とほぼ真下へ，並列数を増やす（P ↑）と右へ流れる 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 17 / 21
復号性能（n = 204） 100 10−1 FER 10−2 10−3 baseline 10 list-based optimization −4 parallel decoding, P = 10 metadynamics, r = 19 10−5 BP 2.0 2.5 3.0 3.5 4.0 4.5 5.0 Eb/N0 [dB] リストベース最適化より約 1 dB 改善．ただし BP との差はなお残る． 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 18 / 21
より長い符号への適用 ρ, σ は n = 204 の値のまま再調整せずに適用 n = 816 n = 1008 100 FER 10−1 10−2 10−3 baseline list-based optimization 10 parallel decoding, P = 10 −4 metadynamics, r = 19 3.0 3.5 4.0 4.5 5.0 3.0 Eb/N0 [dB] 3.5 4.0 4.5 Eb/N0 [dB] 符号長が変わっても，再調整なしで同程度の改善． 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 19 / 21
まとめ 方式 考え方 性能 / 計算量（対 baseline） リストベース最適化 振動の大きいビットを反転し候補選択 約 +1 dB / 後処理のみ SAEPD 自己同型群の置換で再復号 min-sum 級（巡回符号）/ 置換数倍 ランダム初期値並列 複数初期値から並列復号 FER 1/6（P = 10）/ P 倍 メタダイナミクス 停留状態にポテンシャルを置き再開 FER 1/27（r = 19）/ 1.6 倍 今後の課題 BP との性能差をさらに縮める 再開の判断や記憶の管理を，復号の状況に応じて適応的に行う仕組み 符号語の停留性をより保つポテンシャルの設計 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 20 / 21
参考文献 T. Wadayama and S. Takabe, “Proximal decoding for LDPC codes,” Proc. IEEE ISIT, 2021; IEICE Trans. Fundamentals, vol. E106-A, no. 3, pp. 359–367, 2023. A. Tsouchlos, H. Jäkel, and L. Schmalen, “List-based optimization of proximal decoding for LDPC codes,” IEEE Commun. Lett., vol. 28, no. 11, pp. 2464–2467, 2024. T. Yang, Y. Shi, and H. Liu, “Enhanced proximal decoding of cyclic codes based on their automorphism,” Proc. Int. Conf. Computer and Communications (ICCC), pp. 2032–2036, 2025. A. Ito, L. Wei, and T. Wadayama, “Enhancing proximal decoding for LDPC codes through deep unfolding,” Proc. ISITA, 2024. T. Wadayama, K. Nakamura, M. Yagita, Y. Funahashi, S. Usami, and I. Takumi, “Gradient descent bit flipping algorithms for decoding LDPC codes,” IEEE Trans. Commun., vol. 58, no. 6, pp. 1610–1614, 2010. G. Sundararajan, C. Winstead, and E. Boutillon, “Noisy gradient descent bit-flip decoding for LDPC codes,” IEEE Trans. Commun., vol. 62, no. 10, pp. 3385–3400, 2014. L. Zhang, N. Liu, Z. Pan, and X. You, “Tabu-list noisy gradient descent bit flipping decoding of LDPC codes,” Proc. WCSP, pp. 1–5, 2019. H. Cui, J. Lin, and Z. Wang, “An improved gradient descent bit-flipping decoder for LDPC codes,” IEEE Trans. Circuits Syst. I, vol. 66, no. 8, pp. 3188–3200, 2019. Y. Chen, R. Wang, J. Zhu, and Z. Wen, “Decoding LDPC codes by using negative proximal regularization,” IEEE Trans. Commun., vol. 71, no. 7, pp. 3835–3846, 2023. A. Laio and M. Parrinello, “Escaping free-energy minima,” Proc. Natl. Acad. Sci. USA, vol. 99, no. 20, pp. 12562–12566, 2002. 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 21 / 21
付録 A1．目的関数・勾配・更新式の完全形 ペナルティ勾配の成分表示（B(j) = { i : Hij = 1 }：ビット j が関与する検査の 集合） ： Y X Y ∂h = 4xj xj2 − 1 + 2 xl − 1 xl ∂xj i∈B(j) l∈A(i) l∈A(i)\{j} バイアス勾配（閉形式；−∇Vr が反発方向）： ∇Vr (x) = − r kx − c k2 ρ X k 2 exp − (x − c k ) σ2 2σ 2 k=1 1 反復の更新式（バイアス勾配の評価点は通信路ステップ後の r (t) ）： r (t) = s (t) − ω(s (t) − y), γ = ω = 0.05 ρ = 16 η = 1.5 σ = 1.0 s (t+1) = Π[−η,η] r (t) − γ[∇h(r (t) ) + ∇Vr (r (t) )] 1 ラウンド 100 反復 再開 s (0) = c r + 0.05 ε 最大 r = 19（総反復数 2000） 乱数系列固定（共通乱数で対応のある比較） 実装との対応：参照実装と軌道レベルで比較し，20/20 フレームで数値的に一致． 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 1/7
付録 A2．非符号語停留状態の判定と統計 実装上の判定：早期停止に至らず反復上限に達し，その時点の硬判定がシ ンドローム検査を満たさない場合（勾配ノルム条件は不使用） 集計条件：n = 204，3.5 dB，baseline で失敗した 796 フレームを 300 反復 まで追跡 観測 値 準停留（終盤の k∆sk < 10−3 ） 硬判定が t ≤ 100 で凍結 終盤の振動直径／更新ノルム（中央値） t = 300（反復数 3 倍）でも未復号 停留状態から最近傍符号語へのハミング距離 8.2 % のみ 65.7 %（最終変化の中央値 t = 70） 0.38 ／ 0.74 86.6 % 中央値 4 bit 帰結：大半は厳密な不動点ではない→「非符号語停留状態（硬判定凍結＋ 有界振動） 」という呼称 リストベース最適化 [Tsouchlos 2024] における振動に基づく信頼度尺度と も整合する観測 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 2/7
付録 A3．記憶を消すと：効いているのは記憶そのもの ρ = 0：ポテンシャルのみを無効化した対照（再開と初期摂動の手続 きは同一） FER 10−1 10−2 baseline 10−3 warm restart only (ρ = 0, r = 19) metadynamics, r = 19 3.0 3.5 4.0 4.5 5.0 Eb/N0 [dB] 記憶なしの再開は，反復数を 4 倍費やしても FER は baseline とほぼ同じ ポテンシャルを戻すだけで 1 桁以上改善．計算量の追加では説明できない 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 3/7
付録 A5．ρ, σ 感度：広い平坦域があり，精密な調整は 不要 n = 204，4.0 dB，r = 9（★＝採用設定 (ρ, σ) = (16, 1.0)，全実験で固定） FER 4 0.042 0.025 mean rescue rounds (all frames) 0.036 0.052 4 0.68 0.57 0.62 0.75 0.75 0.70 8 0.034 0.025 0.024 0.039 16 0.030 0.021 0.020 0.032 32 0.028 0.019 0.018 0.026 0.5 0.75 1 1.5 3 × 10−2 ρ (hill height) ρ (hill height) 4 × 10−2 8 0.58 0.52 0.51 0.61 16 0.54 0.48 0.46 0.52 32 0.53 0.47 0.45 0.49 0.5 0.75 1 1.5 0.65 0.60 0.55 0.50 σ (hill width) 2 × 10−2 0.45 σ (hill width) 4 × 4 の全格子点で FER 0.018–0.052 ＜ baseline 0.132（2.5–7 倍改善の平 坦域） ．平均救済ラウンド数も 0.45–0.75 と安定 独立乱数系列（seed 2025）でも相対利得 25 倍／ 4.0 倍を再現（評価系列 への過適合なし） 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 4/7
付録 A6．符号語近傍でのバイアスの大きさ：定量評価 1.0 0.8 CDF over initially-failed frames 1.0 0.8 検出されたトラップ（中央値 4 bit） CDF 0.6 0.6 破線＝典型的な 復号勾配のスケール 配置したポテンシャル（中央値 8 bit） 0.4 0.2 harvested traps (n=39,193) deposited hills (n=3,121) 0.0 0 10 20 30 0.4 0.2 0.0 40 Hamming distance to the true codeword [bits] 10−6 10−5 10−4 10−3 10−2 10−1 100 ‖∇V(x *)‖2 / median ‖∇h‖2 右：送信符号語における k∇V k と典型的な復号勾配ノルムとの比の累積分 布．中央値 1.8 %，P95 28 %，最大 0.90（1 を超えるフレームなし） 約 88 % のフレームで比は 10 % 未満．ただし裾は存在（中心が符号語から 2–3 bit の場合） 符号語の停留性の厳密な保存は主張しない（非零の未検出誤り率と整合） 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 5/7
付録 A7．コンパクト台の多項式バイアス（概念実証） 指数関数を用いない四次のポテンシャル（台 d ≤ R の外では厳密に 0）： r h X d 2 i2 V (x) = ρ 1 − k2 , dk = kx − c k k2 R + k=1 設定（n = 204，3.5 dB，r = 9） FER 対ガウス型 ガウス型（ρ = 16，σ = 1.0） 0.068 — コンパクト台 R = 3 0.0677 同等 コンパクト台 R = 2 0.0733 やや劣化 コンパクト台 R = 4 0.0893 劣化 R = 4 の劣化：台が広いと影響が符号語近傍にまで及ぶ（付録 A6 の裾の 所見と整合） 位置付け：概念実証．指数関数を用いない実装と符号語停留性の両立に向 けた設計空間を示す 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 6/7
付録 A8．計算量の詳細（実測） 方式（n = 204，4.5 dB） FER 平均反復 失敗フレーム 平均救済 実測最大 （全フレーム） 条件付き平均 ラウンド ラウンド baseline 5.25 × 10−2 27.2 100 — — リストベース最適化 1.86 × 10−2 31.5 193 — — 並列復号 P = 10 8.70 × 10−3 431.3 960.8 — — ρ = 0（記憶なし） 4.52 × 10−2 112.7 1760.6 0.86 19 メタダイナミクス r = 19 1.94 × 10−3 44.1 430.0 0.20 19 反復数の上限：baseline 100 ／リストベース最適化 200（+28 候補）／並列復号 1100 ／再開系（ρ = 0，メタダイナミクス）2000 参考（n = 1008，4.0 dB）：baseline 66.4 → メタダイナミクス 101.0 反復 （1.5 倍）で FER 2.7 × 10−1 → 1.2 × 10−3 未検出誤り（UER） ：n = 204 の再開系で 4.0 dB で 2 フレーム，4.5 dB で 1 フレーム（検出誤りとは別に集計） メタダイナミクスの条件付き平均 430.0 と並列復号の全フレーム平均 431.3 は偶然近い値をとる別の量 魏 藍天 (豊田工業大学) 非符号語停留状態とメタダイナミクス 2026-08-18 7/7