The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Les codes de permutation sont des codes correcteurs d'erreurs sur des groupes symétriques. Nous nous concentrons sur les codes de permutation sous Chebyshev (l∞) distance. Un code de permutation inventé par Kløve et al. est de longueur n, taille 2n-d et, distance minimale d. On note le code par φn,d. Ce code est le plus grand code de longueur connu n et distance minimale de Chebyshev d > n/2 jusqu'à présent, au meilleur des connaissances des auteurs. Ils ont également conçu des algorithmes efficaces de codage et de décodage à décision dure (HDD) qui surpassent le décodage à distance limitée. Dans cet article, nous dérivons une limite supérieure stricte de la probabilité d’erreur de décodage du disque dur. Par formalisation de graphe factoriel, nous dérivons un algorithme de décodage de probabilité a-postérieure maximum efficace pour φn,d. Nous explorons la concaténation des codes de permutation de φn,d=0 avec des codes externes binaires pour une correction d'erreur plus robuste. Une pseudo-distance naturellement induite sur les codes externes binaires caractérise avec succès la distance de Chebyshev des codes de permutation concaténés. En utilisant cette distance, nous avons limité la distance minimale de Chebyshev des codes concaténés. Nous découvrons comment concaténer des codes linéaires binaires pour atteindre la borne supérieure. Nous dérivons la distribution de distance de codes de permutation concaténés avec des codes externes aléatoires. Nous démontrons que les performances de décodage du produit somme des codes concaténés avec des codes de contrôle de parité externe à faible densité surpassent les schémas conventionnels.
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.
Copier
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 2n-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
Copier
@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 2n-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},}
Copier
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 2n-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 -