On the rank decoding problem over finite principal ideal rings (Q6584334)

Let \(M\) be a finitely generated \(R\)-module. The rank of \(M\), denoted by \(r_k(M),\) is the smallest number of elements in \(M,\) generating it is an \(R\)-module. Let \(A\in R_{m\times n},\) its rank, denoted by \(r_k(A),\) is the rank of the \(R\)-submodule generated by the column (or row) vectors of A. Some properties of the rank for matrices over finite fields do not generalize for matrices over finite rings due to zero divisors. The minimum rank distance \(d (\mathcal{C})\) is an essential parameter for the code \(\mathcal{C}\). It allows to evaluate the error correction capacity of the code.\N\NThe generalizations of certain classes of rank-metric codes from finite fields to finite rings have motivated the authors to study the rank decoding problem in the case of finite rings. Using the structure theorem for finite commutative rings, the authors prove that solving the rank decoding problem over finite principal ideal rings is equivalent to solving the same problem over finite chain rings. It is shown that the rank decoding problem over finite chain rings is at least as hard as the rank decoding problem over finite fields. This is achieved using the socle and the injective envelope of modules over finite chain rings. As for the problem of computing the minimum rank distance for linear codes over finite principal ideal rings, this paper shows that it's equivalent to the same problem for linear codes over finite fields.\N\NCombinatorial-type algorithms for solving the rank decoding problem over finite chain rings are also provided. The average complexity of these algorithms is evaluated by using the shape of modules. This gives a formula that allows to count the number of submodules of fixed rank for a finitely generated module over a finite chain ring.