| Presentation | 2021-01-22 Optimal Non-binary Single Insertion Deletion Correcting Code Construction by Maximum Clique Enumeration Akira Mitsutake, Takayuki Nozaki, Etsuji Tomita, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The purpose of this research is to construct non-binary single deletion correcting codes with large cardinalities. It is known that a code is a single deletion correcting code if the minimum Levenshtein distance of thecode is 4. Hence, we obtain a single deletion correcting code with code length n by the following procedure; (i) Weconstruct a graph in which each vertex corresponds to the sequence of length n and two vertices are adjacent if andonly if Levenshtein distance between the corresponding sequences is greater than or equal to 4. (ii) We extract aclique from the graph. In this report, for short code length, we obtain all the non-binary single deletion correctingcodes with the largest cardinalities by enumerating maximum cliques. Moreover, we present an efficient algorithmconstructing single deletion correcting codes with large cardinalities. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Single deletion correcting code / Optimal code / Levenshtein distance / Maximum clique enumeration |
| Paper # | IT2020-89,SIP2020-67,RCS2020-180 |
| 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) | Optimal Non-binary Single Insertion Deletion Correcting Code Construction by Maximum Clique Enumeration |
| Sub Title (in English) | |
| Keyword(1) | Single deletion correcting code |
| Keyword(2) | Optimal code |
| Keyword(3) | Levenshtein distance |
| Keyword(4) | Maximum clique enumeration |
| 1st Author's Name | Akira Mitsutake |
| 1st Author's Affiliation | Yamaguchi University(Yamaguchi Univ.) |
| 2nd Author's Name | Takayuki Nozaki |
| 2nd Author's Affiliation | Yamaguchi University(Yamaguchi Univ.) |
| 3rd Author's Name | Etsuji Tomita |
| 3rd Author's Affiliation | The University of Electro Communications(UEC) |
| Date | 2021-01-22 |
| Paper # | IT2020-89,SIP2020-67,RCS2020-180 |
| Volume (vol) | vol.120 |
| Number (no) | IT-320,SIP-321,RCS-322 |
| Page | pp.pp.142-147(IT), pp.142-147(SIP), pp.142-147(RCS), |
| #Pages | 6 |
| Date of Issue | 2021-01-14 (IT, SIP, RCS) |