| 講演名 | 2017-05-23 2元AIFV-m符号の最適な符号木を構成する動的計画法 河井 貴哉(福井大), 岩田 賢一(福井大), 山本 博資(東大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | Yamamoto, Tsuchihashi, Hondaが提案した2元AIFV符号(almost instantaneous fixed-to-variable length code)は，復号において最大2ビットの遅延を許容し，符号木の葉のみならず不完全内節点にも情報源記号の割り当てを許し，複数の符号木を用いることでハフマン符号より優れた圧縮性能を実現している．さらに，Hu, Yamamoto, Hondaは，2元AIFV符号の拡張として，復号において最大$m$ビットの遅延を許容し，$m$個の符号木を用いる2元AIFV-$m$符号を提案し，$m leq 4$に対して最悪冗長度が$1/m$ビットであることを証明した．本稿では2元AIFV-$m$符号の構成に用いる動的計画法を計算複雑度$O(m n^{2m+1})$，空間複雑度$O(m n^{m+1})$で提案する．$n$は情報源アルファベットを構成する記号数である．提案する動的計画法と確率的に状態を遷移するシステムにおける平均性能最適化に関する反復アルゴリズムを組み合わせれば，定常無記憶情報源に対して$m leq 5$の最適な2元AIFV-$m$符号を構成できることを計算機実験で確認した． |
| 抄録(英) | Yamamoto, Tsuchihashi, and Honda proposed binary almost instantaneous fixed-to-variable length (AIFV) codes, which allow at most 2-bit decoding delay, assign source symbols to incomplete internal nodes in addition to leaves of two code trees. The AIFV codes achieve better or equal compression ratios than ones of Huffman codes. Furthermore, Hu, Yamamoto, and Honda proposed a new class of binary AIFV-$m$ codes consisted of $m$ code trees with at most $m$-bit decoding delay, and they proved the worst-case redundancies of the binary AIFV-$m$ codes are $1/m$ for $4 leq m$. In this paper, we proposed a dynamic programming (DP) algorithm, which can be used to obtain a set of code trees of binary AIFV-$m$ codes. The DP works with $O(m n^{2m+1})$ time and $O(m n^{m+1})$ space for source alphabet size $n$. Computer experiment confirmed that we red{can} obtain a set of optimal code trees on the class of binary AIFV-$m$ codes for stationary memoryless sources by combining the dynamic programming and the iterative algorithm for a probabilistic transition system with $m$ states if $m leq 5$. |
| キーワード(和) | 無歪み情報源符号 / 最適符号 / AIFV符号 / AIFV-m符号 / 動的計画法 |
| キーワード(英) | noiseless source codes / optimal codes / AIFV codes / AIFV-m codes / dynamic programming |
| 資料番号 | IT2017-14,EMM2017-14 |
| 発行日 | 2017-05-15 (IT, EMM) |
| 研究会情報 | |
| 研究会 | EMM / IT |
|---|---|
| 開催期間 | 2017/5/22(から2日開催) |
| 開催地（和） | 山形大学(米沢キャンパス) |
| 開催地（英） | Yamagata University(Yonezawa Campus) |
| テーマ（和） | 情報セキュリティ，情報理論，情報ハイディング，一般 |
| テーマ（英） | Information Security, Information Theory, Information Hiding, etc. |
| 委員長氏名（和） | 伊藤 彰則(東北大) / 大橋 正良(福岡大) |
| 委員長氏名（英） | Akinori Ito(Tohoku Univ.) / Masayoshi Ohashi(Fukuoka Univ.) |
| 副委員長氏名（和） | 川村 正樹(山口大) / 日置 尋久(京大) / 村松 純(NTT) |
| 副委員長氏名（英） | Masaki Kawamura(Yamaguchi Univ.) / Hirohisa Hioki(Kyoto Univ.) / Jun Muramatsu(NTT) |
| 幹事氏名（和） | 薗田 光太郎(長崎大) / 岩田 基(阪府大) / 葛岡 成晃(和歌山大) / 吉田 隆弘(横浜商科大) |
| 幹事氏名（英） | Kotaro Sonoda(Nagasaki Univ.) / Motoi Iwata(Osaka Pref. Univ.) / Nariaki Kuzuoka(Wakayama Univ.) / Takahiro Yoshida(Yokohama College of Commerce) |
| 幹事補佐氏名（和） | 生源寺 類(静岡大) / 藤吉 正明(首都大東京) / 岩本 貢(電通大) |
| 幹事補佐氏名（英） | Rui Shogenji(Shizuoka Univ.) / Masaaki Fujiyoshi(Tokyo Metropolitan Univ.) / Mitsugu Iwamoto(Univ. of Electro-Comm.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Enriched MultiMedia / Technical Committee on Information Theory |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 2元AIFV-m符号の最適な符号木を構成する動的計画法 |
| サブタイトル（和） | |
| タイトル（英） | A Dynamic Programming Algorithm to Construct Optimal Code Trees of Binary AIFV-m Codes |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 無歪み情報源符号 / noiseless source codes |
| キーワード(2)（和/英） | 最適符号 / optimal codes |
| キーワード(3)（和/英） | AIFV符号 / AIFV codes |
| キーワード(4)（和/英） | AIFV-m符号 / AIFV-m codes |
| キーワード(5)（和/英） | 動的計画法 / dynamic programming |
| 第 1 著者 氏名（和/英） | 河井 貴哉 / Takaya Kawai |
| 第 1 著者 所属（和/英） | 福井大学(略称：福井大) University of Fukui(略称：Univ. of Fukui) |
| 第 2 著者 氏名（和/英） | 岩田 賢一 / Ken-ichi Iwata |
| 第 2 著者 所属（和/英） | 福井大学(略称：福井大) University of Fukui(略称：Univ. of Fukui) |
| 第 3 著者 氏名（和/英） | 山本 博資 / Hirosuke Yamamoto |
| 第 3 著者 所属（和/英） | 東京大学(略称：東大) The University of Tokyo(略称：The Univ. of Tokyo) |
| 発表年月日 | 2017-05-23 |
| 資料番号 | IT2017-14,EMM2017-14 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | IT-39,EMM-40 |
| ページ範囲 | pp.79-84(IT), pp.79-84(EMM), |
| ページ数 | 6 |
| 発行日 | 2017-05-15 (IT, EMM) |