| 講演名 | 2009-03-10 最多一致に基づく符号化法のユニバーサル性の証明(情報通信基礎サブソサイエティ合同研究会) 林 雁かお, 植松 友彦, 松本 隆太郎, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | KiefferとYangによる文法に基づく符号では,与えられた系列に対して,その系列だけを生成する文脈自由文法を作成した後,作成した文法を2元系列に変換することで符号化を行う.本論文では,与えられた系列を生成する文法を作成する手法として,最も多く出現する部分列を簡約化する手法を取り上げ,定常状態情報源からの出力系列を文法に基づいて符号化するときに,系列を長くすると一文字あたりの符号のビット数の平均はその情報源のエントロピーレートに収束することを証明している. |
| 抄録(英) | In the grammar based code proposed by Kieffer and Yang, for a given data string, we first produce a context-free grammar which produces the given data string only, then transform the grammar into a binary data string. In this paper, we focus on the grammar transform based on most frequent match which simplifies most frequently appearing partial data strings, and prove that the expected codeword length per symbol converges to the entropy rate of the source, when the length of the data string becomes sufficiently long. |
| キーワード(和) | ユニバーサル符号 / 文法に基づく符号 / 最多一致 |
| キーワード(英) | universal code / grammar based code / most frequent match |
| 資料番号 | IT2008-96,ISEC2008-154,WBS2008-109 |
| 発行日 |
| 研究会情報 | |
| 研究会 | WBS |
|---|---|
| 開催期間 | 2009/3/2(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Wideband System(WBS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 最多一致に基づく符号化法のユニバーサル性の証明(情報通信基礎サブソサイエティ合同研究会) |
| サブタイトル（和） | |
| タイトル（英） | A proof of universality of the source coding by most frequent match |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ユニバーサル符号 / universal code |
| キーワード(2)（和/英） | 文法に基づく符号 / grammar based code |
| キーワード(3)（和/英） | 最多一致 / most frequent match |
| 第 1 著者 氏名（和/英） | 林 雁かお / Yangao LIN |
| 第 1 著者 所属（和/英） | 東京工業大学大学院集積システム専攻 Dept. of Communications and Integrated Systems, Tokyo Institute of Technology |
| 第 2 著者 氏名（和/英） | 植松 友彦 / Tomohiko UYEMATSU |
| 第 2 著者 所属（和/英） | 東京工業大学大学院集積システム専攻 Dept. of Communications and Integrated Systems, Tokyo Institute of Technology |
| 第 3 著者 氏名（和/英） | 松本 隆太郎 / Ryutaroh MATSUMOTO |
| 第 3 著者 所属（和/英） | 東京工業大学大学院集積システム専攻 Dept. of Communications and Integrated Systems, Tokyo Institute of Technology |
| 発表年月日 | 2009-03-10 |
| 資料番号 | IT2008-96,ISEC2008-154,WBS2008-109 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | 474 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |