| 講演名 | 2021-01-21 2元AIFV-m符号の最悪冗長度が1/mである予想の反例と改良 中村 優太(福井大), 植田 大智(福井大), 岩田 賢一(福井大), 山本 博資(東大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | Hu, Yamamoto, Honda は，2 元 AIFV-m 符号を定義し，m = 2, 3, 4 に対して，2 元 AIFV-m 符号の冗 長度の上界が 1/m であることを証明し，2 元 AIFV-m 符号の最悪冗長度は 1/m であると予想した.本稿では最適 な 2 元 AIFV-m 符号を構築する Fujita, Iwata, Yamamoto のアルゴリズムにおける動的計画法に用いるパラメータ c_{k,j} , 0 ? j, k ? m − 1 の値の上界と下界を与える.また，m = 12 において最悪冗長度が 1/m 以上である情報源の例 を確認し，2 元 AIFV-m 符号の最悪冗長度が 1/m である反例を示す.さらに，復号において最大 m ビットの遅延を 許容した場合において，情報源記号の最大出現確率が 1 に近づくとき，2 元 AIFV-m 符号よりも優れた冗長度を達成 する情報源符号を提案する. |
| 抄録(英) | Hu, Yamamoto, and Honda proposed the binary AIFV-m codes and proved that the redundancy of the optimal binary AIFV-m codes is bounded above by 1/m for m = 2, 3, 4. They conjectured that the worst-case redundancy of the binary AIFV-m code is 1/m if m ? 2. This paper proves that the parameters c _k,j,0 ? k,j ? m−1, which are used for dynamic programming in the Fujita, Iwata, and Yamamoto’s algorithm for constructing an optimal binary AIFV-m code, satisfy |ck,j| < 1. We also observe a source with worst-case redundancy greater than 1/m at m = 12 and show counterexamples with worst-case redundancy of 1/m for binary AIFV-m codes. Furthermore, we propose a source code that achieves better redundancy than a binary AIFV-m code when the maximum probability of the source symbol approaches 1 if allowing at most m-bit decoding delay. |
| キーワード(和) | 無歪みデータ圧縮 / 情報源符号 / AIFV-m符号 / 冗長度 / 反復最適化 |
| キーワード(英) | Noiseless data compression / source coding / AIFV-m code / redundancy / iterative optimization |
| 資料番号 | IT2020-73,SIP2020-51,RCS2020-164 |
| 発行日 | 2021-01-14 (IT, SIP, RCS) |
| 研究会情報 | |
| 研究会 | SIP / IT / RCS |
|---|---|
| 開催期間 | 2021/1/21(から2日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | 無線通信のための信号処理，学習，数理，情報理論および一般 |
| テーマ（英） | |
| 委員長氏名（和） | 林 和則(京大) / 和田山 正(名工大) / 岡本 英二(名工大) |
| 委員長氏名（英） | Kazunori Hayashi(Kyoto Univ.) / Tadashi Wadayama(Nagoya Inst. of Tech.) / Eiji Okamoto(Nagoya Inst. of Tech.) |
| 副委員長氏名（和） | 坂東 幸浩(NTT) / 田中 聡久(東京農工大) / 小嶋 徹也(東京高専) / 前原 文明(早大) / 西村 寿彦(北大) / 旦代 智哉(東芝) |
| 副委員長氏名（英） | Yukihiro Bandou(NTT) / Toshihisa Tanaka(Tokyo Univ. Agri.&Tech.) / Tetsuya Kojima(Tokyo Kosen) / Fumiaki Maehara(Waseda Univ.) / Toshihiko Nishimura(Hokkaido Univ.) / Tomoya Tandai(Toshiba) |
| 幹事氏名（和） | 小西 克巳(法政大) / 杉本 憲治郎(早大) / 野崎 隆之(山口大) / 廣友 雅徳(佐賀大) / 牟田 修(九大) / 村岡 一志(NEC) |
| 幹事氏名（英） | Katsumi Konishi(Hosei Univ.) / Kenjiro Sugimoto(Waseda Univ.) / Takayuki Nozaki(Yamaguchi Univ.) / Masanori Hirotomo(Saga Univ.) / Osamu Muta(Kyushu Univ.) / Kazushi Muraoka(NEC) |
| 幹事補佐氏名（和） | 田中 雄一(東京農工大) / 太田 隆博(専修大) / 安達 宏一(電通大) / 中村 理(シャープ) / 酒井 学(三菱電機) / 岩渕 匡史(NTT) / 奥山 達樹(NTTドコモ) |
| 幹事補佐氏名（英） | Yuichi Tanaka(Tokyo Univ. Agri.&Tech.) / Takahiro Ohta(Senshu Univ.) / Koichi Adachi(Univ. of Electro-Comm.) / Osamu Nakamura(Sharp) / Manabu Sakai(Mitsubishi Electric) / Masashi Iwabuchi(NTT) / Tatsuki Okuyama(NTT DOCOMO) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Signal Processing / Technical Committee on Information Theory / Technical Committee on Radio Communication Systems |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 2元AIFV-m符号の最悪冗長度が1/mである予想の反例と改良 |
| サブタイトル（和） | |
| タイトル（英） | A counterexample to the conjecture that the maximum redundancy of the AIFV-m codes is 1/m and an improvement |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 無歪みデータ圧縮 / Noiseless data compression |
| キーワード(2)（和/英） | 情報源符号 / source coding |
| キーワード(3)（和/英） | AIFV-m符号 / AIFV-m code |
| キーワード(4)（和/英） | 冗長度 / redundancy |
| キーワード(5)（和/英） | 反復最適化 / iterative optimization |
| 第 1 著者 氏名（和/英） | 中村 優太 / Yuta Nakamura |
| 第 1 著者 所属（和/英） | 福井大学(略称：福井大) University of Fukui(略称：Univ. of Fukui) |
| 第 2 著者 氏名（和/英） | 植田 大智 / Ueda Daichi |
| 第 2 著者 所属（和/英） | 福井大学(略称：福井大) University of Fukui(略称：Univ. of Fukui) |
| 第 3 著者 氏名（和/英） | 岩田 賢一 / Ken-ichi Iwata |
| 第 3 著者 所属（和/英） | 福井大学(略称：福井大) University of Fukui(略称：Univ. of Fukui) |
| 第 4 著者 氏名（和/英） | 山本 博資 / Hirosuke Yamamoto |
| 第 4 著者 所属（和/英） | 東京大学(略称：東大) The University of Tokyo(略称：The Univ. of Tokyo) |
| 発表年月日 | 2021-01-21 |
| 資料番号 | IT2020-73,SIP2020-51,RCS2020-164 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | IT-320,SIP-321,RCS-322 |
| ページ範囲 | pp.58-63(IT), pp.58-63(SIP), pp.58-63(RCS), |
| ページ数 | 6 |
| 発行日 | 2021-01-14 (IT, SIP, RCS) |