有限サイズのInvertible Bloom Lookup Tablesの性能評価
スポンサーリンク
概要
- 論文の詳細を見る
Invertible Bloom Lookup Tables (IBLT)はkey-valueペアの挿大,削除,検索,リストアップ操作をサポートした確率的データ構造である.IBLTの一番の特徴は,すべてのkey-valueペアをリストアップする操作が可能な点であり,この操作はLDGM符号のヒーリングアルゴリズムと似た動作をする.本稿では,有限サイズにおけるリストアップ操作の性能評価を行う停止集合の解析手法を提案する.ユニオンバウンドに基づいて導出したリストアップ失敗確率の上界は,正確にエラーフロアの振る舞いを捉えていることが計算機実験により確認されている.解析の結果からエラーフロア領域における性能は,サイズ2の停止集合が大きく影響することが明らかとなった.さらに本稿では,サイズ2の停止集合の発生を抑えることを目的とした停止集合抑制ハッシュ関数を提案し,エラーフロア領域における性能を改善する.
- 一般社団法人電子情報通信学会の論文
- 2013-02-28
著者
関連論文
- 平均性能を指標とした改良型Index-less Indexedフラッシュ符号 (情報理論)
- 凸最適化を用いた同期CDMA方式におけるマルチユーザ検出法(フレッシュマンセッション,フレッシュマンセッション,一般)
- 圧縮センシングにおける完全再現十分条件について
- A-6-4 平均書き換え可能回数を指標としたIndex-less Indexedフラッシュ符号の改善(A-6.情報理論,一般セッション)
- A-6-3 主パス追跡内点法に基づくLP復号法の停止基準に関する検討(A-6.情報理論,一般セッション)
- IT2010-29 平均性能を指標とした改良型Index-less Indexedフラッシュ符号(フレッシュマンセッション,一般)
- 圧縮センシングにおける完全再現十分条件について
- A-6-10 反転候補集合を利用したビットフリッピング復号法の計算量削減手法(A-6.情報理論,一般セッション)
- 2元行列アンサンブルの見逃し誤り確率の平均誤り指数(LDPC符号,一般)
- A-6-2 複数の閾値を利用したGradient Descent-Bit Flipping復号法(A-6. 情報理論,一般セッション)
- LDPC符号のための勾配法に基づくビットフリップ復号法
- 復号時符号長選択可能なLDPC符号の構成
- 差分写像法に基づくLDPC符号に適した反復復号法(LDPC符号,一般)
- ペナルティ関数を利用した内点LP復号法の改良(LDPC符号,一般)
- 主パス追跡内点法に基づく最大分数距離計算法の改善(情報通信基礎サブソサイエティ合同研究会)
- 主パス追跡内点法に基づく最大分数距離計算法の改善(情報通信基礎サブソサイエティ合同研究会)
- 主パス追跡内点法に基づく最大分数距離計算法の改善(情報通信基礎サブソサイエティ合同研究会)
- 25pTD-13 2元行列アンサンブルの見逃し誤り確率の平均誤り指数(25pTD 情報統計力学,領域11(統計力学,物性基礎論,応用数学,力学,流体物理))
- AT-2-3 符号理論の観点から見た圧縮センシング(AT-2.リード・ソロモン符号50周年,チュートリアルセッション,ソサイエティ企画)
- A-6-1 ビット信頼度を用いたNormalized Min-Sum復号法の改良(A-6. 情報理論,一般セッション)
- 冗長行の検査行列への追加による Stopping Set 分布の改善について
- BPとガウス消去法を組み合わせたLDPC符号の消失誤り訂正法
- コンパクトな表現を持つ2値センシング行列のランダム構成法について(一般セッション,フレッシュマンセッション,一般)
- 冗長行を用いた基本凸多面体の最小重み頂点の削除による分数距離の改善
- 2次元クラスタ消失に適したLDPC符号の構成法
- フェージング通信路における消失訂正を利用したq元LDPC符号の復号法
- 一次マルコフモデルを用いた適応型最小エネルギー符号化法
- 二つのエッジタイプを持つLDPC符号のエラーフロア改善手法
- 2元行列アンサンブルの重み分布の共分散について
- 2.反復復号法の性能解析 : 密度発展法とその周辺(ターボ符号・LDPC符号と繰返し復号の理論)
- LP Decodable Permutation Codes based on Linearly Constrained Permutation Matrices (Frontiers in mathematical science through collaborations with other disciplines)
- 二次計画法に基づく同期CDMAマルチユーザ検出アルゴリズム(スペクトル拡散技術)
- 線形制約が課された置換行列について
- 2次元磁気記録方式のための隣接ビット制約符号化方式について(信号処理及び一般)
- バースト誤り通信路に適した反復復号法(情報論的学習理論論文)
- AT-1-1 復号・復調問題への凸最適化アプローチ(AT-1.通信路符号化の最近の進歩,チュートリアルセッション,ソサイエティ企画)
- 平均性能を指標とした改良型Index-less Indexedフラッシュ符号(符号理論)
- ランダムグラフにおけるネットワーク信頼度の評価(フレッシュマンセッション,一般)
- 符号理論と理論計算機科学の接点 : グラフのカット問題を中心として(LDPC符号,一般)
- 完全マッチング数え上げの高速な指数時間アルゴリズムについて (アルゴリズムと計算理論の新展開)
- 符号理論と完全マッチング計数問題の接点について
- Pure involution置換符号に基づく新しい置換符号について
- BT-1-1 よくわかるチャネル符号化 : LDPC符号を中心として(BT-1.よくわかるチャネル符号化と繰返し信号処理,チュートリアルセッション,ソサイエティ企画)
- Pure involution 置換符号に基づく新しい置換符号について
- 符号理論と完全マッチング計数問題の接点について
- 多元LDPC符号に適したバースト誤り訂正アルゴリズム(符号理論)
- 疎グラフに基づくグループテスト方式に関する情報理論解析について
- 疎グラフに基づくグループテスト方式に関する情報理論解析について
- 17-3 2次元磁気記録方式におけるボロノイ離散グレインモデルの計算機実装について(第17部門 マルチメディアストレージ1)
- 有限サイズのInvertible Bloom Lookup Tablesの性能評価
- 有限サイズのInvertible Bloom Lookup Tablesの性能評価
- 2次元重み制約に適した反復コセット符号化法
- 有限サイズのInvertible Bloom Lookup Tablesの性能評価
- 2次元重み制約に適した反復コセット符号化法
- 2次元重み制約に適した反復コセット符号化法
- 並列復号に適したプロトグラフ叉状結合型空間結合符号(誤り訂正符号,一般)