| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2017-05-23 14:25 2元AIFV-m符号の最適な符号木を構成する動的計画法 ○河井貴哉・岩田賢一（福井大）・山本博資（東大）  IT2017-14 EMM2017-14 |
|
| 抄録 | （和） | 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 / / / | |
| 文献情報 | 信学技報, vol. 117, no. 39, IT2017-14, pp. 79-84, 2017年5月. | |
| 資料番号 | IT2017-14 | |
| 発行日 | 2017-05-15 (IT, EMM) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IT2017-14 EMM2017-14 |
|
| 研究会情報 | |
| 研究会 | EMM IT |
| 開催期間 | 2017-05-22 - 2017-05-23 |
| 開催地（和） | 山形大学(米沢キャンパス) |
| 開催地（英） | Yamagata University(Yonezawa Campus) |
| テーマ（和） | 情報セキュリティ，情報理論，情報ハイディング，一般 |
| テーマ（英） | Information Security, Information Theory, Information Hiding, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | IT |
| 会議コード | 2017-05-EMM-IT |
| 本文の言語 | 日本語 |
| タイトル（和） | 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 |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第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) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2017-05-23 14:25:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IT |
| 資料番号 | IT2017-14, EMM2017-14 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | no.39(IT), no.40(EMM) |
| ページ範囲 | pp.79-84 |
| ページ数 | 6 |
| 発行日 | 2017-05-15 (IT, EMM) |
[研究会発表申込システムのトップページに戻る]