講演抄録/キーワード |
講演名 |
2019-05-24 09:30
2元コンパクト符号を簡便に構成可能な3値無記憶拡大情報源に関する一検討 ○宮 希望(青学大)・吉田隆弘(横浜商科大)・地主 創(青学大) IT2019-7 EMM2019-7 |
抄録 |
(和) |
アルファベットサイズが$D$である無記憶情報源の$n$次拡大情報源に対し,平均符号語長が最小の$2$元瞬時符号すなわち$2$元コンパクト符号は例えばハフマンのアルゴリズムにより構成されるが,その計算量は$n$に関し指数的に大きくなる.そこで$D = 2$においてハフマンのアルゴリズムを直接実行することなく対応する$2$元コンパクト符号を簡便に構成する手法が提案されている.この手法は,生起確率の等しい情報源記号全体を同一グループとすると,ハフマンのアルゴリズムにおいて``縮約がグループをまたがない''といった条件が満たされるならば,対応するコンパクト符号を構成するものである.本稿では,$D = 3$における``縮約がグループをまたがない''条件を導出し,$D = 2$における手法をそのまま$D = 3$に対して適用できることを示す. |
(英) |
The complexity of Huffman procedure grows with exponential order of $n$ for the $n$-th degree extended memoryless sources whose alphabet size is $D$. A simple construction of binary compact codes without Huffman procedure for $D = 2$, i.e., the alphabet is ${ 0, 1}$. Let the probability of source symbols with $k$ symbols of $1$ be $P_k = p^{n - k}(1 - p)^k$ for $k = 0, 1, dots , n$, where $p ge 1 / 2$ denotes the probability of symbol $0$. If $p$ satisfies $sum_{i = k}^nbinom{n}{i}P_i le P_{k - 1}$ for $k = 0, 1, dots , n - 1$ and for a given $n$, this simple construction gives a binary compact codes. We derive the condition under which this simple construction can be applied for $D = 3$. |
キーワード |
(和) |
情報源符号化 / データ圧縮 / 2元コンパクト符号 / ハフマンのアルゴリズム / 3値無記憶情報源 / 拡大情報源 / / |
(英) |
source coding / data compression / binary compact codes / Huffman procedure / ternary memoryless sources / extended sources / / |
文献情報 |
信学技報, vol. 119, no. 47, IT2019-7, pp. 31-36, 2019年5月. |
資料番号 |
IT2019-7 |
発行日 |
2019-05-16 (IT, EMM) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IT2019-7 EMM2019-7 |
|