| Presentation | 2018-03-08 Optimality for the Iterative Construction Scheme of AIFV-$m$ codes Ryusei Fujita, Ken-ichi Iwata, Hirosuke Yamamoto, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Yamamoto, Tsuchihashi, and Honda proposed binary AIFV (almost instantaneous fixed-to-variable length) codes, which allow at most 2-bit decoding delay. The AIFV codes achieve better or equal compression ratios than ones of Huffman codes. Furthermore, Hu, Yamamoto, and Honda proposed a new class of binary AIFV-$m$ codes consisted of $m$ code trees with at most $m$-bit decoding delay, and they proved the worst-case redundancies of the binary AIFV-$m$ codes are $1/m$ for $m leq 4$. Iwata and Yamamoto proposed an iterative algorithm to obtain the optimal AIFV-$m$ code with $m$ code trees for a given source probability distribution. In this paper, we generalize the optimization problem of AIFV-$m$ code trees to the optimization problem of the average performance of a finite Markov system with $m$-states, which have a unique stationary distribution. Then, we prove that the generalized iterative algorithm can derive the optimal system with $m$-states, and hence, the original iterative algorithm can derive the optimal AIFV-$m$ code. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | noiseless source codes / optimal codes / AIFV codes / AIFV-$m$ codes / finite markov system |
| Paper # | IT2017-111,ISEC2017-99,WBS2017-92 |
| Date of Issue | 2018-03-01 (IT, ISEC, WBS) |
| Conference Information | |
| Committee | WBS / IT / ISEC |
|---|---|
| Conference Date | 2018/3/8(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Katsusika Campas, Tokyo University of Science |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | joint meeting of IT, ISEC, and WBS |
| Chair | Fumiaki Maehara(Waseda Univ.) / Masayoshi Ohashi(Fukuoka Univ.) / Kazuto Ogawa(NHK) |
| Vice Chair | Masanori Hamamura(Kochi Univ. of Tech.) / Fumie Ono(NICT) / Jun Muramatsu(NTT) / Atsushi Fujioka(Kanagawa Univ.) / Shiho Moriai(NICT) |
| Secretary | Masanori Hamamura(Mitsubishi Electric) / Fumie Ono(Ibaraki Univ.) / Jun Muramatsu(Yokohama College of Commerce) / Atsushi Fujioka(UEC) / Shiho Moriai(Tohoku Univ.) |
| Assistant | Akira Nakamura(Tokyo Univ. of Science) / Ryohei Nakamura(National Defense Academy) / Sigeaki Kuzuoka(wakayama univ.) / Keita Emura(NICT) / Yuichi Komano(TOSHIBA) / Yuuji Suga(IIJ) |
| Paper Information | |
| Registration To | Technical Committee on Wideband System / Technical Committee on Information Theory / Technical Committee on Information Security |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Optimality for the Iterative Construction Scheme of AIFV-$m$ codes |
| Sub Title (in English) | |
| Keyword(1) | noiseless source codes |
| Keyword(2) | optimal codes |
| Keyword(3) | AIFV codes |
| Keyword(4) | AIFV-$m$ codes |
| Keyword(5) | finite markov system |
| 1st Author's Name | Ryusei Fujita |
| 1st Author's Affiliation | University of Fukui(Univ. of Fukui) |
| 2nd Author's Name | Ken-ichi Iwata |
| 2nd Author's Affiliation | University of Fukui(Univ. of Fukui) |
| 3rd Author's Name | Hirosuke Yamamoto |
| 3rd Author's Affiliation | The University of Tokyo(The Univ. of Tokyo) |
| Date | 2018-03-08 |
| Paper # | IT2017-111,ISEC2017-99,WBS2017-92 |
| Volume (vol) | vol.117 |
| Number (no) | IT-487,ISEC-488,WBS-489 |
| Page | pp.pp.49-54(IT), pp.49-54(ISEC), pp.49-54(WBS), |
| #Pages | 6 |
| Date of Issue | 2018-03-01 (IT, ISEC, WBS) |