The search functionality is under construction.

The search functionality is under construction.

Errata[Uploaded on April 1,2023]

Permutation codes are error-correcting codes over symmetric groups. We focus on permutation codes under Chebyshev (*l*_{∞}) distance. A permutation code invented by Kløve et al. is of length *n*, size 2^{n-d} and, minimum distance *d*. We denote the code by *φ*_{n,d}. This code is the largest known code of length *n* and minimum Chebyshev distance *d* > *n*/2 so far, to the best of the authors knowledge. They also devised efficient encoding and hard-decision decoding (HDD) algorithms that outperform the bounded distance decoding. In this paper, we derive a tight upper bound of decoding error probability of HDD. By factor graph formalization, we derive an efficient maximum a-posterior probability decoding algorithm for *φ*_{n,d}. We explore concatenating permutation codes of *φ*_{n,d=0} with binary outer codes for more robust error correction. A naturally induced pseudo distance over binary outer codes successfully characterizes Chebyshev distance of concatenated permutation codes. Using this distance, we upper-bound the minimum Chebyshev distance of concatenated codes. We discover how to concatenate binary linear codes to achieve the upper bound. We derive the distance distribution of concatenated permutation codes with random outer codes. We demonstrate that the sum-product decoding performance of concatenated codes with outer low-density parity-check codes outperforms conventional schemes.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.3 pp.616-632

- Publication Date
- 2023/03/01

- Publicized
- 2022/09/21

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.2022EAP1058

- Type of Manuscript
- PAPER

- Category
- Coding Theory

Motohiro KAWASUMI

Nikkei Inc.

Kenta KASAI

Tokyo Institute of Technology

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Motohiro KAWASUMI, Kenta KASAI, "Concatenated Permutation Codes under Chebyshev Distance" in IEICE TRANSACTIONS on Fundamentals,
vol. E106-A, no. 3, pp. 616-632, March 2023, doi: 10.1587/transfun.2022EAP1058.

Abstract: Permutation codes are error-correcting codes over symmetric groups. We focus on permutation codes under Chebyshev (*l*_{∞}) distance. A permutation code invented by Kløve et al. is of length *n*, size 2^{n-d} and, minimum distance *d*. We denote the code by *φ*_{n,d}. This code is the largest known code of length *n* and minimum Chebyshev distance *d* > *n*/2 so far, to the best of the authors knowledge. They also devised efficient encoding and hard-decision decoding (HDD) algorithms that outperform the bounded distance decoding. In this paper, we derive a tight upper bound of decoding error probability of HDD. By factor graph formalization, we derive an efficient maximum a-posterior probability decoding algorithm for *φ*_{n,d}. We explore concatenating permutation codes of *φ*_{n,d=0} with binary outer codes for more robust error correction. A naturally induced pseudo distance over binary outer codes successfully characterizes Chebyshev distance of concatenated permutation codes. Using this distance, we upper-bound the minimum Chebyshev distance of concatenated codes. We discover how to concatenate binary linear codes to achieve the upper bound. We derive the distance distribution of concatenated permutation codes with random outer codes. We demonstrate that the sum-product decoding performance of concatenated codes with outer low-density parity-check codes outperforms conventional schemes.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2022EAP1058/_p

Copy

@ARTICLE{e106-a_3_616,

author={Motohiro KAWASUMI, Kenta KASAI, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Concatenated Permutation Codes under Chebyshev Distance},

year={2023},

volume={E106-A},

number={3},

pages={616-632},

abstract={Permutation codes are error-correcting codes over symmetric groups. We focus on permutation codes under Chebyshev (*l*_{∞}) distance. A permutation code invented by Kløve et al. is of length *n*, size 2^{n-d} and, minimum distance *d*. We denote the code by *φ*_{n,d}. This code is the largest known code of length *n* and minimum Chebyshev distance *d* > *n*/2 so far, to the best of the authors knowledge. They also devised efficient encoding and hard-decision decoding (HDD) algorithms that outperform the bounded distance decoding. In this paper, we derive a tight upper bound of decoding error probability of HDD. By factor graph formalization, we derive an efficient maximum a-posterior probability decoding algorithm for *φ*_{n,d}. We explore concatenating permutation codes of *φ*_{n,d=0} with binary outer codes for more robust error correction. A naturally induced pseudo distance over binary outer codes successfully characterizes Chebyshev distance of concatenated permutation codes. Using this distance, we upper-bound the minimum Chebyshev distance of concatenated codes. We discover how to concatenate binary linear codes to achieve the upper bound. We derive the distance distribution of concatenated permutation codes with random outer codes. We demonstrate that the sum-product decoding performance of concatenated codes with outer low-density parity-check codes outperforms conventional schemes.},

keywords={},

doi={10.1587/transfun.2022EAP1058},

ISSN={1745-1337},

month={March},}

Copy

TY - JOUR

TI - Concatenated Permutation Codes under Chebyshev Distance

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 616

EP - 632

AU - Motohiro KAWASUMI

AU - Kenta KASAI

PY - 2023

DO - 10.1587/transfun.2022EAP1058

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E106-A

IS - 3

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - March 2023

AB - Permutation codes are error-correcting codes over symmetric groups. We focus on permutation codes under Chebyshev (*l*_{∞}) distance. A permutation code invented by Kløve et al. is of length *n*, size 2^{n-d} and, minimum distance *d*. We denote the code by *φ*_{n,d}. This code is the largest known code of length *n* and minimum Chebyshev distance *d* > *n*/2 so far, to the best of the authors knowledge. They also devised efficient encoding and hard-decision decoding (HDD) algorithms that outperform the bounded distance decoding. In this paper, we derive a tight upper bound of decoding error probability of HDD. By factor graph formalization, we derive an efficient maximum a-posterior probability decoding algorithm for *φ*_{n,d}. We explore concatenating permutation codes of *φ*_{n,d=0} with binary outer codes for more robust error correction. A naturally induced pseudo distance over binary outer codes successfully characterizes Chebyshev distance of concatenated permutation codes. Using this distance, we upper-bound the minimum Chebyshev distance of concatenated codes. We discover how to concatenate binary linear codes to achieve the upper bound. We derive the distance distribution of concatenated permutation codes with random outer codes. We demonstrate that the sum-product decoding performance of concatenated codes with outer low-density parity-check codes outperforms conventional schemes.

ER -