| 講演名 | 2009-03-10 逐次的な文法変換に基づくユニバーサル情報源符号化法(情報通信基礎サブソサイエティ合同研究会) 城野 将樹, 植松 友彦, 松本 隆太郎, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 文法に基づく符号はKiefferとYangによって提案された幅広いユニバーサル符号のクラスである.一般に文法に基づく符号は入力列を全て得た後でなければ対応する符号列を得ることができないという欠点を有していた.本研究では,まず入力列を読みながら,入力列の語頭について文法を作成できる逐次的な文法変換法を導入する.次に逐次的な文法変換法に対応した逐次的に符号化ならびに復号化可能な文法の2進列への変換手法を提案する.一方,既約文法と呼ばれる文法を作成する文法変換法のクラスを用いたとき,文法に基づく符号がユモバーサル符号となることが知られてめる.しかしながら,逐次的な文法変換法によって得られる文法は既約ではない.そこで,逐次的な文法変換法でも作成可能な準既約文法という文法のクラスを導入し,準既約文法を作成する文法変換法を用いたとき,提案する符号化アルゴリズムが定常エルゴード情報源に対してユニバーサル符号となることを示している. |
| 抄録(英) | The grammar-based code proposed by Kieffer and Yang is a large class of universal codes. Usually, the grammar-based codes can not encode a data string into a binary string before reading all the data string. In this paper, we introduce sequential grammar transforms which can construct grammars for some prefixes of the data string. To efficiently encode these grammars sequentially, we also propose sequential grammar encoding and decoding algorithms. Combined with the irreducible grammar transform, our encoding algorithm provides the universal code. However, the sequential grammar transforms can not be irreducible. To overcome this problem, we propose a new class of grammar transforms called quasi-irreducible, and show that quasi-irreducible grammar transforms together with the proposed algorithm provide a universal code for a class of stationary and ergodic sources. |
| キーワード(和) | 文法に基づく符号 / ユニバーサル符号 / 冗長度 / 逐次的データ圧縮 |
| キーワード(英) | grammar-based code / universal source code / redundancy / sequential data compression |
| 資料番号 | IT2008-98,ISEC2008-156,WBS2008-111 |
| 発行日 |
| 研究会情報 | |
| 研究会 | WBS |
|---|---|
| 開催期間 | 2009/3/2(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Wideband System(WBS) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 逐次的な文法変換に基づくユニバーサル情報源符号化法(情報通信基礎サブソサイエティ合同研究会) |
| サブタイトル（和） | |
| タイトル（英） | Universal Lossless Source Coding Based on Sequential Grammar Transforms |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 文法に基づく符号 / grammar-based code |
| キーワード(2)（和/英） | ユニバーサル符号 / universal source code |
| キーワード(3)（和/英） | 冗長度 / redundancy |
| キーワード(4)（和/英） | 逐次的データ圧縮 / sequential data compression |
| 第 1 著者 氏名（和/英） | 城野 将樹 / Masaki JONO |
| 第 1 著者 所属（和/英） | 東京工業大学大学院理工学研究科集積システム専攻 Department of Communications and Integrated Systems, Tokyo Institute of Technology |
| 第 2 著者 氏名（和/英） | 植松 友彦 / Tomohiko UYEMATSU |
| 第 2 著者 所属（和/英） | 東京工業大学大学院理工学研究科集積システム専攻 Department of Communications and Integrated Systems, Tokyo Institute of Technology |
| 第 3 著者 氏名（和/英） | 松本 隆太郎 / Ryutaroh MATSUMOTO |
| 第 3 著者 所属（和/英） | 東京工業大学大学院理工学研究科集積システム専攻 Department of Communications and Integrated Systems, Tokyo Institute of Technology |
| 発表年月日 | 2009-03-10 |
| 資料番号 | IT2008-98,ISEC2008-156,WBS2008-111 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | 474 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |