Low-Rank Parity-Check Codes over Galois Rings
Preprint
Abstract
Low-rank parity-check (LRPC) are rank-metric codes over finite fields, which have been proposed by Gaborit et al. (2013) for cryptographic applications. Inspired by a recent adaption of Gabidulin codes to certain finite rings by Kamche et al. (2019), we define and study LRPC codes over Galois rings - a wide class of finite commutative rings. We give a decoding algorithm similar to Gaborit et al.'s decoder, based on simple linear-algebraic operations. We derive an upper bound on the failure probability of the decoder, which is significantly more involved than in the case of finite fields. The bound depends only on the rank of an error, i.e., is independent of its free rank. Further, we analyze the complexity of the decoder. We obtain that there is a class of LRPC codes over a Galois ring that can decode roughly the same number of errors as a Gabidulin code with the same code parameters, but faster than the currently best decoder for Gabidulin codes. However, the price that one needs to pay is a small failure probability, which we can bound from above.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Low Rank Parity Check Codes and their application in Power Line Communications smart grid networksInternational Journal of Communication Systems, 2017
- Joint Physical Layer Coding and Network Coding for Bidirectional RelayingIEEE Transactions on Information Theory, 2010
- A Rank-Metric Approach to Error Control in Random Network CodingIEEE Transactions on Information Theory, 2008
- Finite Commutative Rings and Their Applications2002
- The Z/sub 4/-linearity of Kerdock, Preparata, Goethals, and related codesIEEE Transactions on Information Theory, 1994
- Maximum-rank array codes and their application to crisscross error correctionIEEE Transactions on Information Theory, 1991
- Bilinear forms over a finite field, with applications to coding theoryJournal of Combinatorial Theory, Series A, 1978
- Codes over Zm, revisitedInformation and Control, 1978
- Codes over integer residue ringsInformation and Control, 1975
- Codes over certain ringsInformation and Control, 1972