講演名 | 2019-05-24 2元コンパクト符号を簡便に構成可能な3値無記憶拡大情報源に関する一検討 宮 希望(青学大), 吉田 隆弘(横浜商科大), 地主 創(青学大), |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | アルファベットサイズが$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 |
資料番号 | IT2019-7,EMM2019-7 |
発行日 | 2019-05-16 (IT, EMM) |
研究会情報 | |
研究会 | EMM / IT |
---|---|
開催期間 | 2019/5/23(から2日開催) |
開催地(和) | 旭川市国際会議場 |
開催地(英) | Asahikawa International Conference Hall |
テーマ(和) | 情報セキュリティ,情報理論,情報ハイディング,一般 |
テーマ(英) | Information Security, Information Theory, Information Hiding, etc. |
委員長氏名(和) | 岩村 惠市(東京理科大) / 村松 純(NTT) |
委員長氏名(英) | Keiichi Iwamura(TUC) / Jun Muramatsu(NTT) |
副委員長氏名(和) | 栗林 稔(岡山大) / 小嶋 徹也(東京高専) / 和田山 正(名工大) |
副委員長氏名(英) | Minoru Kuribayashi(Okayama Univ.) / Tetsuya Kojima(NIT,Tokyo College) / Tadashi Wadayama(Nagoya Inst. of Tech.) |
幹事氏名(和) | 姜 玄浩(東京高専) / 村田 晴美(中京大) / 太田 隆博(長野県工科短大) / 八木 秀樹(電通大) |
幹事氏名(英) | Kan Hyonho(NIT, Tokyo) / Harumi Murata(Tyukyo Univ.) / Takahiro Ohta(Nagano Pref Inst. of Tech.) / Hideki Yagi(UEC) |
幹事補佐氏名(和) | 秋山 寛子(長野高専) / 金田 北洋(キヤノン) / 吉田 隆弘(横浜商科大) |
幹事補佐氏名(英) | Hiroko Akiyama(NIT, Nagano College) / キタヒロ カネダ(CANON) / Takahiro Yoshida(Yokohama College of Commerce) |
講演論文情報詳細 | |
申込み研究会 | Technical Committee on Enriched MultiMedia / Technical Committee on Information Theory |
---|---|
本文の言語 | JPN |
タイトル(和) | 2元コンパクト符号を簡便に構成可能な3値無記憶拡大情報源に関する一検討 |
サブタイトル(和) | |
タイトル(英) | A Consideration on Extended Ternary Memoryless Sources with a Simple Construction of Binary Compact Codes |
サブタイトル(和) | |
キーワード(1)(和/英) | 情報源符号化 / source coding |
キーワード(2)(和/英) | データ圧縮 / data compression |
キーワード(3)(和/英) | 2元コンパクト符号 / binary compact codes |
キーワード(4)(和/英) | ハフマンのアルゴリズム / Huffman procedure |
キーワード(5)(和/英) | 3値無記憶情報源 / ternary memoryless sources |
キーワード(6)(和/英) | 拡大情報源 / extended sources |
第 1 著者 氏名(和/英) | 宮 希望 / Nozomi Miya |
第 1 著者 所属(和/英) | 青山学院大学(略称:青学大) Aoyama Gakuin University(略称:Aoyama Gakuin Univ.) |
第 2 著者 氏名(和/英) | 吉田 隆弘 / Takahiro Yoshida |
第 2 著者 所属(和/英) | 横浜商科大学(略称:横浜商科大) Yokohama College of Commerce(略称:Yokohama College of Commerce) |
第 3 著者 氏名(和/英) | 地主 創 / Hajime Jinushi |
第 3 著者 所属(和/英) | 青山学院大学(略称:青学大) Aoyama Gakuin University(略称:Aoyama Gakuin Univ.) |
発表年月日 | 2019-05-24 |
資料番号 | IT2019-7,EMM2019-7 |
巻番号(vol) | vol.119 |
号番号(no) | IT-47,EMM-48 |
ページ範囲 | pp.31-36(IT), pp.31-36(EMM), |
ページ数 | 6 |
発行日 | 2019-05-16 (IT, EMM) |