講演抄録/キーワード |
講演名 |
2018-03-08 13:25
AIFV-$m$符号の反復構成法における最適性 ○藤田龍星・岩田賢一(福井大)・山本博資(東大) IT2017-111 ISEC2017-99 WBS2017-92 |
抄録 |
(和) |
Yamamoto, Tsuchihashi, Hondaが提案した2元AIFV符号(almost instantaneous fixed-to-variable lengthcode)は,復号において最大2ビットの遅延を許容し,符号木の葉のみならず不完全内節点にも情報源記号の割り当て,複数の符号木を用いることでハフマン符号より優れた圧縮性能を実現している.さらに,Hu, Yamamoto, Hondaは,2元AIFV符号の拡張として,復号において最大$m$ビットの遅延を許容し,$m$個の符号木を用いる2元AIFV-$m$符号を提案し,$m leq 4$に対して最悪冗長度が$1/m$ビットであることを証明した. Iwata, Yamamotoは,情報源に対して最良の平均符号長を達成するAIFV-$m$符号の構成法として反復構成法を一般化した.本稿では,AIFV-$m$符号における平均性能に対する最適化問題の一般化として, 定常分布を有する有限マルコフシステムにおける平均性能に対する最適化問題を考え,反復構成法により最適化な有限マルコフシステムが与えられることを示す. |
(英) |
Yamamoto, Tsuchihashi, and Honda proposed binary AIFV (almost instantaneous fixed-to-variable length) codes, which allow at most 2-bit decoding delay. 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 $m leq 4$. Iwata and Yamamoto proposed an iterative algorithm to obtain the optimal AIFV-$m$ code with $m$ code trees for a given source probability distribution. In this paper, we generalize the optimization problem of AIFV-$m$ code trees to the optimization problem of the average performance of a finite Markov system with $m$-states, which have a unique stationary distribution. Then, we prove that the generalized iterative algorithm can derive the optimal system with $m$-states, and hence, the original iterative algorithm can derive the optimal AIFV-$m$ code. |
キーワード |
(和) |
無歪み情報源符号 / 最適符号 / AIFV符号 / AIFV-$m$符号 / 有限マルコフシステム / / / |
(英) |
noiseless source codes / optimal codes / AIFV codes / AIFV-$m$ codes / finite markov system / / / |
文献情報 |
信学技報, vol. 117, no. 487, IT2017-111, pp. 49-54, 2018年3月. |
資料番号 |
IT2017-111 |
発行日 |
2018-03-01 (IT, ISEC, WBS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IT2017-111 ISEC2017-99 WBS2017-92 |
|