Majority logic decoding of affine Grassmann codes over nonbinary fields

DOI10.1007/S10623-026-01915-WMaRDI QIDQ7312757zbMATH OpenFDO

Authors Fernando Piñero-González, Prasant Singh, Rohit Yadav

Publication date 12 August 2026

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10623-026-01915-W

Applications to coding theory and cryptography of arithmetic geometry (14G50) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Decoding (94B35)

Review text

Decoding procedures for affine Grassmann codes over nonbinary fields are presented. The dual \(L^{\perp}\) of a \((n,k)\)-linear code \(L<\mathbb{F}_q^n\), being \(q\) a power of a prime, is a \((n,n-k)\)-linear code. An index permutation \(\sigma\in S_n\) is an automorphism for \(L\) if whenever \(\mathbf{x}=\left(x_i\right)_{i=0}^{n-1}\) is in \(L\) the permuted word \(\sigma(\mathbf{x})=\left(x_{\sigma(i)}\right)_{i=0}^{n-1}\) is also in \(L\). Naturally the collection of autmorphisms \(\Aut(L)\) is a subgroup of the symmetric group \(S_n\). A subset \(U\subset L^{\perp}\) is orthogonal on the \(i\)-th coordinate if for each \(\mathbf{u}\in U\), \(u_i=1\), and for \(\mathbf{u},\mathbf{v}\in U\), \(\mathbf{u}\not=\mathbf{v}\), the only coordinate for which both \(u_i\), \(v_i\) are non-zero is the \(i\)-th coordinate.\N\NFor \(m_0,m_1\in\mathbb{Z}^+\), \(m_0\leq m_1\), let \(m_a=m_0+m_1\) and \(m_p=m_0\cdot m_1\). Any word \(\mathbf{w}\in\mathbb{F}_q^{m_p}\) is realized as a \((m_0\times m_1)\)-planar array and an array \(\mathbf{X}\) of \(m_p\) polynomial variables is realized as well as an array \(\left(X_{ij}\right)_{0\leq i\leq m_0-1}^{0\leq j\leq m_1-1}\). Let \(\Delta(m_0,m_p)\) consist of the \((i\times i)\)-minors of \(\mathbf{X}\) for \(0\leq i\leq m_0-1\). Then \(\Delta(m_0,m_p)\subset\mathbb{F}_q[\mathbf{X}]\). Let \(\mathcal{F}(m_0,m_p) = \langle\Delta(m_0,m_p)\rangle\). The evaluation map is \(Ev:\mathbb{F}_q[\mathbf{X}]\mapsto\mathbb{F}_q^{m_p}\), \(p(\mathbf{X})\mapsto\left(p(\mathbf{x})\right)_{\mathbf{x}\in\mathbb{F}_q^{m_p}}\), and the corresponding affine Grassmann code is \(G(m_0,m_p):=Ev(\mathcal{F}(m_0,m_p))<\mathbb{F}_q^{m_p}\), which is a \(\left(q^{m_p},\binom{m_a}{m_0}\right)\)-linear code. The authors calculate the minimal distances \(d_{G(m_0,m_p)}=q^{m_p}\prod_{i=1}^{m_0}\left(1-\frac{1}{q^i}\right)\) and \(d_{G(m_0,m_p)^{\perp}}\) with value 3 if \(q>2\) and 4 if \(q=2\), and they characterize the automorphism group of \(G(m_0,m_p)\) as the semidirect product \(\mathbb{F}_q^{m_0\times m_1}\rtimes_{\theta}(G/Z)\) where \(G= \mathrm{GL}(\mathbb{F}_q^{m_0})\times \mathrm{GL}(\mathbb{F}_q^{m_1})\), \(Z=\{(k\mbox{Id}_{m_0},k\mbox{Id}_{m_1})|\ k\in\mathbb{F}_q^*\}\) and \(\theta\) is the homomorphism \((A,B)\,Z\mapsto\theta((A,B)\,Z):\mathbf{x}\mapsto A\mathbf{x}B^{-1}\).\N\NFor \(r\leq m_0\), by selecting a collection \(\mathcal{A}\) consisting of \(r\) subsets of \(\mathbb{F}_q^*\), each of cardinality \(r\), and \(r\)-dimensional linear subspaces \(U_0<\mathbb{F}_q^{m_0}\), \(U_1<\mathbb{F}_q^{m_1}\) the authors construct \((2^r+1,2^r)\)-linear codes, seen as linear varieties within \(\mathbb{F}_q^{m_0\times m_1}\). Through this construction, the authors may select a family \(F_0\) of great cardinality \(c_{m_0m_1}\) consisting of parity check words for \(G(m_0,m_p)\), orthogonal with respect to the first coordinate, and, by applying proper automorphisms, similar families with the same cardinality \(c_{m_0m_1}\) orthogonal with respect to any coordinate are obtained. This system allows codeword decoding over \(G(m_0,m_p)\) using a majority logic, correcting up to \(\left\lfloor\frac{c_{m_0m_1}-1}{2}\right\rfloor\) errors. The whole procedure has time complexity \(O\left(q^{m_p}c_{m_0m_1}\right)\) and it can be reduced to \(O\left(q^{m_p}\right)\) when \(m_0\) is fixed. The authors illustrate the decoding procedure for \((q,m_0,m_1) = (3,2,2)\).

Cites work

This page was built for publication: Majority logic decoding of affine Grassmann codes over nonbinary fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7312757)