Presentation | 2021-01-21 A counterexample to the conjecture that the maximum redundancy of the AIFV-m codes is 1/m and an improvement Yuta Nakamura, Ueda Daichi, Ken-ichi Iwata, Hirosuke Yamamoto, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | 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. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Noiseless data compression / source coding / AIFV-m code / redundancy / iterative optimization |
Paper # | IT2020-73,SIP2020-51,RCS2020-164 |
Date of Issue | 2021-01-14 (IT, SIP, RCS) |
Conference Information | |
Committee | SIP / IT / RCS |
---|---|
Conference Date | 2021/1/21(2days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | Online |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | Kazunori Hayashi(Kyoto Univ.) / Tadashi Wadayama(Nagoya Inst. of Tech.) / Eiji Okamoto(Nagoya Inst. of Tech.) |
Vice Chair | Yukihiro Bandou(NTT) / Toshihisa Tanaka(Tokyo Univ. Agri.&Tech.) / Tetsuya Kojima(Tokyo Kosen) / Fumiaki Maehara(Waseda Univ.) / Toshihiko Nishimura(Hokkaido Univ.) / Tomoya Tandai(Toshiba) |
Secretary | Yukihiro Bandou(Hosei Univ.) / Toshihisa Tanaka(Waseda Univ.) / Tetsuya Kojima(Yamaguchi Univ.) / Fumiaki Maehara(Saga Univ.) / Toshihiko Nishimura(Kyushu Univ.) / Tomoya Tandai(NEC) |
Assistant | 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) |
Paper Information | |
Registration To | Technical Committee on Signal Processing / Technical Committee on Information Theory / Technical Committee on Radio Communication Systems |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | A counterexample to the conjecture that the maximum redundancy of the AIFV-m codes is 1/m and an improvement |
Sub Title (in English) | |
Keyword(1) | Noiseless data compression |
Keyword(2) | source coding |
Keyword(3) | AIFV-m code |
Keyword(4) | redundancy |
Keyword(5) | iterative optimization |
1st Author's Name | Yuta Nakamura |
1st Author's Affiliation | University of Fukui(Univ. of Fukui) |
2nd Author's Name | Ueda Daichi |
2nd Author's Affiliation | University of Fukui(Univ. of Fukui) |
3rd Author's Name | Ken-ichi Iwata |
3rd Author's Affiliation | University of Fukui(Univ. of Fukui) |
4th Author's Name | Hirosuke Yamamoto |
4th Author's Affiliation | The University of Tokyo(The Univ. of Tokyo) |
Date | 2021-01-21 |
Paper # | IT2020-73,SIP2020-51,RCS2020-164 |
Volume (vol) | vol.120 |
Number (no) | IT-320,SIP-321,RCS-322 |
Page | pp.pp.58-63(IT), pp.58-63(SIP), pp.58-63(RCS), |
#Pages | 6 |
Date of Issue | 2021-01-14 (IT, SIP, RCS) |