| 講演名 | 2000/3/16 アルファベット符号における競合最適性 丸山 剛, 山本 博資, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 情報源符号化で用いられるFV符号の符号語が, 情報源シンボルと同じ順序関係を満たすとき, そのFV符号をアルファベット符号という.平均符号語長が最小となる平均最適アルファベット符号の構成問題はHu-Tucker問題と呼ばれ, その最適な構成法が知られている.しかし, アルファベット符号の競合最適符号に関しては, 今まで全く研究が行われていない.本稿では, アルファベット符号の競合最適性を取り上げ, 次の事柄を明らかにする.(1)情報源の確率分布によっては, 競合最適アルファベット符号が存在しない場合がある.(2)競合最適アルファベット符号が存在する場合は, それは平均最適アルファベット符号でもある. |
| 抄録(英) | A FV code is called an alphabetic code if its codewords satisfy the same order as source symbols. The averagely optimal alphabetic code that attains the minimum average codeword length can be obtained by Hu-Tucker algorithm, Garsia-Wachs algorithm, etc. However, the competitively optimal alphabetic code has not been studied yet. In this paper, the competitive optimality is considered for alphabetic codes, and the following are proved. (1)The competitively optimal alphabetic code does not always exist for a given source probability distribution. (2)In the case that the competitively optimal alphabetic code exists, it is also averagely optimal. |
| キーワード(和) | アルファベット符号 / 平均最適符号 / 競合最適符号 / lmcp |
| キーワード(英) | alphabetic code / averagely optimal code / competitively optimal code / lmcp |
| 資料番号 | IT99-72,ISEC99-111,SST99-120 |
| 発行日 |
| 研究会情報 | |
| 研究会 | IT |
|---|---|
| 開催期間 | 2000/3/16(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Theory (IT) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | アルファベット符号における競合最適性 |
| サブタイトル（和） | |
| タイトル（英） | Competitive Optimality of Alphabetic Codes |
| サブタイトル（和） | |
| キーワード(1)（和/英） | アルファベット符号 / alphabetic code |
| キーワード(2)（和/英） | 平均最適符号 / averagely optimal code |
| キーワード(3)（和/英） | 競合最適符号 / competitively optimal code |
| キーワード(4)（和/英） | lmcp / lmcp |
| 第 1 著者 氏名（和/英） | 丸山 剛 / Go Maruyama |
| 第 1 著者 所属（和/英） | 東京大学大学院工学系研究科計数工学専攻 Department of Mathematical Engineering and Information Physics, University of Tokyo |
| 第 2 著者 氏名（和/英） | 山本 博資 / Hirosuke Yamamoto |
| 第 2 著者 所属（和/英） | 東京大学大学院工学系研究科計数工学専攻 Department of Mathematical Engineering and Information Physics, University of Tokyo |
| 発表年月日 | 2000/3/16 |
| 資料番号 | IT99-72,ISEC99-111,SST99-120 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 699 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |