講演名 | 2009-03-10 主パス追跡内点法に基づく最大分数距離計算法の改善(情報通信基礎サブソサイエティ合同研究会) 三輪 誠, 和田山 正, 内匠 逸, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 2元線形符号の最大分数距離は,線形計画(LP)復号法のAWGN通信路における誤り率に深く関わっている.また,最大分数距離は最小疑似距離の下界を与えるため,符号の最小疑似距離を解析する上でも重要な量である.本稿では,主パス追跡内点法に基づく効率的な最大分数距離計算法を提案する.提案法では,最大分数距離を得るためのLP問題を主パス追跡内点法を用いて解く.また双対ギャップを用いることにより,提案法の計算量を削減する手法も提案する.提案法により,符号長4000のLDPC符号の最大分数距離を計算することに成功した. |
抄録(英) | The max-fractional distance of a binary linear code is deeply related to the performance of an linear programming (LP) decoder on the AWGN channel. In this paper, we propose an efficient algorithm for evaluating the max-fractional distance of LDPC codes. The proposed method is based on efficient interior point method for solving LP problems. By using the proposed algorithm, the max-fractional distance of length up to 4000 has been successfully obtained. |
キーワード(和) | LDPC符号 / 線形計画復号法 / 最大分数距離 / 内点法 / ニュートン法 |
キーワード(英) | LDPC codes / Linear Programming Decoding / Max-Fractional Distance / Interior-Point Method |
資料番号 | IT2008-108,ISEC2008-166,WBS2008-121 |
発行日 |
研究会情報 | |
研究会 | WBS |
---|---|
開催期間 | 2009/3/2(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Wideband System(WBS) |
---|---|
本文の言語 | ENG |
タイトル(和) | 主パス追跡内点法に基づく最大分数距離計算法の改善(情報通信基礎サブソサイエティ合同研究会) |
サブタイトル(和) | |
タイトル(英) | An Efficient Method for Evaluating Max-Fractional Distance Based on A Primal Path-Following Interior Point Method |
サブタイトル(和) | |
キーワード(1)(和/英) | LDPC符号 / LDPC codes |
キーワード(2)(和/英) | 線形計画復号法 / Linear Programming Decoding |
キーワード(3)(和/英) | 最大分数距離 / Max-Fractional Distance |
キーワード(4)(和/英) | 内点法 / Interior-Point Method |
キーワード(5)(和/英) | ニュートン法 |
第 1 著者 氏名(和/英) | 三輪 誠 / Makoto MIWA |
第 1 著者 所属(和/英) | 名古屋工業大学 Nagoya Institute of Technology |
第 2 著者 氏名(和/英) | 和田山 正 / Tadashi WADAYAMA |
第 2 著者 所属(和/英) | 名古屋工業大学 Nagoya Institute of Technology |
第 3 著者 氏名(和/英) | 内匠 逸 / Ichi TAKUMI |
第 3 著者 所属(和/英) | 名古屋工業大学 Nagoya Institute of Technology |
発表年月日 | 2009-03-10 |
資料番号 | IT2008-108,ISEC2008-166,WBS2008-121 |
巻番号(vol) | vol.108 |
号番号(no) | 474 |
ページ範囲 | pp.- |
ページ数 | 7 |
発行日 |