| 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) |