講演抄録/キーワード |
講演名 |
2017-11-28 16:35
[招待講演]準瞬時FV符号とその拡張符号 ○山本博資(東大) IT2017-54 |
抄録 |
(和) |
符号木を用いる情報源符号化において,一意復号可能なFV符号(fixed-to-variable length code)中で最小の平均符号長を達成できる最適な符号は,クラフトの定理とマクミランの定理から,ハフマン符号であると結論づけられていた.しかし,マクミランの定理は,1つの符号木を用いることを仮定しているため,定常無記憶情報源の場合でも,複数の符号木を用いるとハフマン符号より平均符号長の短い符号を構成できる可能性がある.実際,2個以上の符号木を用い,最大復号遅延を符号アルファベットが2元の場合は2ビット,$K$元($Kgeq 3$)の場合は1符号シンボル許す準瞬時FV符号 (almost instantaneous fixed-to-variable length code, AIFV符号)は,ハフマン符号よりも短い平均符号長を達成することができる.本稿では,準瞬時FV符号の制約条件,符号化・復号化アルゴリズム,符号の構成法,準瞬時FV符号の拡張符号などについて紹介する. |
(英) |
In source coding based on a code tree, it was concluded from Kraft's and McMilan's theorems that
the Huffman code is the optimal FV (fixed-to-variable length) code attaining the shortest average code length in the class of uniquely decodable codes. However, since McMillan's theorem assumes that a single code tree is used in encoding and decoding, it may be possible to construct an FV code that can attain shorter average code length than the Huffman code even for stationary memoryless sources if we use multiple code trees. Actually, the binary (resp.~$K$-ary) AIFV (almost instantaneous FV) code can attain better compression than the binary (resp.~$K$-ary) Huffman code
by using two (resp.~$K-1$) code trees and allowing decoding delay with at most two bits (resp.~one code symbol). In this paper, we introduce several topics of AIFV codes, e.g. the condition of AIFV code trees, AIFV coding and decoding algorithms, the construction methods of AIFV codes, and several extended AIFV codes. |
キーワード |
(和) |
準瞬時FV符号 / 一意復号可能符号 / ハフマン符号 / 符号木 / 情報源符号化 / / / |
(英) |
AUFV cide / uniquely decodable code / Huffman code / code tree / source coding / / / |
文献情報 |
信学技報, vol. 117, no. 327, IT2017-54, pp. 19-26, 2017年11月. |
資料番号 |
IT2017-54 |
発行日 |
2017-11-21 (IT) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IT2017-54 |