| 講演名 | 2004-09-17 長さ4のサイクルを取り除く符号等価なタナーグラフの変換 笠井 健太, 渋谷 智治, 坂庭 好一, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | Belief Propagation(BP)復号は、線形符号を表すタナーグラフにサイクルが無ければビット毎の最大事後確率復号になる。サイクルがあるタナーグラフを持つ線形符号にBP復号を適用する場合には、特に長さ4のサイクルが存在すると復号性能が劣化する事が知られている。 Yedidiaらはパンクチャビットを加えパリティ検査方程式を書き換える事によって、低密度ではないパリティ検査行列から一一般化パリティ検査行列と呼ばれる低密度なパリティ検査行列を得る変換を提案した。本研究では、Yedidiaらの変換の特殊な場合であるの長さ4のサイクルを取り除くパリティ検査行列の変換に注目し、消失通信路で発生した消失を復元する場合には、この変換によって得られた行列を用いて復元に失敗する消失パターンの集合は、元の行列を用いて復元に失敗する消失パターンの集合に含まれる事を示す。また、ハミング符号を例に、この変換をほどこすことによって復元できる消失パターンが増える符号が存在することを示す。 |
| 抄録(英) | Belief Propagation(BP) decoding is equivalent to Maximum a Posteriori(MAP) decoding when the Tanner graph of the code is free of cycles. Performance of BP decoding with Tanner graph with cycle is often not good if the Tanner graph has cycles of length four. Adding redundant parity-checks and puncturing bits, Yedidia et al. transformed high-density parity-check matrices to low-density ones. In this report, we investigate the transformation of parity-check matrices (or equivalently of Tanner graphs) removing cycles of length four in Tanner graphs, which is the special case of Yedidia's transformation. We prove that, when transmission over erasure channels, under the transformation, BP-recoverable erasures are preserved. We show transforming Tanner graph of (7,4,3) Hamming code makes some new BP-recoverable erasures. |
| キーワード(和) | 低密度パリティ検査符号 / 停止集合 / 消失通信路 / BP復号 |
| キーワード(英) | low-density parity-check codes / stopping set / erasure channel / Belief Propagation |
| 資料番号 | IT2004-42 |
| 発行日 |
| 研究会情報 | |
| 研究会 | IT |
|---|---|
| 開催期間 | 2004/9/10(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Theory (IT) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 長さ4のサイクルを取り除く符号等価なタナーグラフの変換 |
| サブタイトル（和） | |
| タイトル（英） | A Code-Equivalent Transfomation Removing Cycles of Length Four in Tanner Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 低密度パリティ検査符号 / low-density parity-check codes |
| キーワード(2)（和/英） | 停止集合 / stopping set |
| キーワード(3)（和/英） | 消失通信路 / erasure channel |
| キーワード(4)（和/英） | BP復号 / Belief Propagation |
| 第 1 著者 氏名（和/英） | 笠井 健太 / Kenta KASAI |
| 第 1 著者 所属（和/英） | 東京工業大学大学院理工学研究科集積システム専攻 Department of Communications and Integrated Systems, Tokyo Institute of Technology |
| 第 2 著者 氏名（和/英） | 渋谷 智治 / Tomoharu SHIBUYA |
| 第 2 著者 所属（和/英） | メディア教育開発センター研究開発部 Department of Research and Development, National Institute of Multimedia Education |
| 第 3 著者 氏名（和/英） | 坂庭 好一 / Kohichi SAKANIWA |
| 第 3 著者 所属（和/英） | 東京工業大学大学院理工学研究科集積システム専攻 Department of Communications and Integrated Systems, Tokyo Institute of Technology |
| 発表年月日 | 2004-09-17 |
| 資料番号 | IT2004-42 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 302 |
| ページ範囲 | pp.- |
| ページ数 | 4 |
| 発行日 | |