August  2020, 14(3): 423-436. doi: 10.3934/amc.2020058

On the non-Abelian group code capacity of memoryless channels

Avenida Tiaraju 810, Alegrete, RS, 97541-151, Brazil

* Corresponding author

Received  November 2018 Revised  August 2019 Published  January 2020

Fund Project: The author is supported by Fundação Universidade Federal do Pampa - UNIPAMPA, Brazil

In this work is provided a definition of group encoding capacity $ C_G $ of non-Abelian group codes transmitted through symmetric channels. It is shown that this $ C_G $ is an upper bound of the set of rates of these non-Abelian group codes that allow reliable transmission. Also, is inferred that the $ C_G $ is a lower bound of the channel capacity. After that, is computed the $ C_G $ of the group code over the dihedral group transmitted through the 8PSK-AWGN channel then is shown that it equals the channel capacity. It remains an open problem whether there exist non-Abelian group codes of rate arbitrarily close to $ C_G $ and arbitrarily small error probability.

Citation: Jorge P. Arpasi. On the non-Abelian group code capacity of memoryless channels. Advances in Mathematics of Communications, 2020, 14 (3) : 423-436. doi: 10.3934/amc.2020058
References:
[1]

R. Ahlswede, Group codes do not achieve shannon's channel capacity for general discrete channels, The Annals of Mathematical Statistics, 42 (1971), 224-240.  doi: 10.1214/aoms/1177693508.  Google Scholar

[2]

J. P. Arpasi, One example of a non-Abelian group code over AWGN channels, Proceedings of the 14th Canadian Workshop on Information Theory, (2015), 115–119. doi: 10.1109/CWIT.2015.7255165.  Google Scholar

[3]

G. Como, Group codes outperform binary-coset codes on non-binary memoryless channels, IEEE Trans. Inform. Theory, 56 (2010), 4321-4334.  doi: 10.1109/TIT.2010.2054330.  Google Scholar

[4]

G. Como and F. Fagnani, The capacity of abelian group codes over symmetric channels, IEEE Trans. Inform. Theory, 45 (2009), 3-31.   Google Scholar

[5]

G. Como and F. Fagnani, Average spectra and minimum distance of low-density parity-check codes over abelian groups, SIAM J. Discrete Math., 23 (2008/09), 19-53.  doi: 10.1137/070686615.  Google Scholar

[6]

T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd edition, Wiley InterScience, Piscataway, NJ, 2006.  Google Scholar

[7]

G. D. Forney, Geometrically uniform codes, IEEE Trans. Inform. Theory, 37 (1991), 1241-1260.  doi: 10.1109/18.133243.  Google Scholar

[8]

R. Gallager, Information Theory and Reliable Communication, Wiley and Sons, 1970. doi: 10.1007/978-3-7091-2945-6.  Google Scholar

[9]

F. Garin and F. Fagnani, Analysis of serial turbo codes over abelian groups for symmetric channels, SIAM J. Discrete Math., 22 (2008), 1488-1526.  doi: 10.1137/07068802X.  Google Scholar

[10]

I. N. Herstein, Topics in Algebra, 2nd edition, Wiley and Sons, New York, 1975.  Google Scholar

[11]

H. J. KimJ. B. Nation and A. V. Shepler, Group coding with complex isometries, IEEE Trans. Inform. Theory, 61 (2015), 33-50.  doi: 10.1109/TIT.2014.2365020.  Google Scholar

[12]

H. A. Loeliger, Signal sets matched to groups, IEEE Trans. Inform. Theory, 37 (1991), 1675-1682.  doi: 10.1109/18.104333.  Google Scholar

[13]

H. A. Loeliger and T. Mittelholzer, Convolutional codes over groups. Codes and complexity, IEEE Trans. Inform. Theory, 42 (1996), 1660-1686.  doi: 10.1109/18.556664.  Google Scholar

[14]

T. Mittelholzer and J. Lahtonen, Group codes generated by finite reflection groups, IEEE Trans. Inform. Theory, 42 (1996), 519-528.  doi: 10.1109/18.485721.  Google Scholar

[15]

W. W. PetersonJ. B. Nation and M. P. Fossorier, Reflection group codes and their decoding, IEEE Trans. Inform. Theory, 56 (2010), 6273-6293.  doi: 10.1109/TIT.2010.2080571.  Google Scholar

[16]

J. J. Rotman, An Introduction to the Theory of the Groups, 4th edition, Graduate Texts in Mathematics, 148. Springer-Verlag, New York, 1995. doi: 10.1007/978-1-4612-4176-8.  Google Scholar

[17]

A. G. Sahebi and P. S. Pradhan, Abelian group codes for channel coding and source coding, IEEE Trans. Inform. Theory, 61 (2015), 2399-2414.  doi: 10.1109/TIT.2015.2407874.  Google Scholar

[18]

N. Shulman and M. Feder, Random coding techniques for non-random codes, IEEE Trans. Inform. Theory, 45 (1999), 2101-2104.  doi: 10.1109/18.782147.  Google Scholar

[19]

D. Slepian, Group codes for the gaussian channels, Bell Systems Technical Journal, 47 (1968), 575-602.  doi: 10.1002/j.1538-7305.1968.tb02486.x.  Google Scholar

show all references

References:
[1]

R. Ahlswede, Group codes do not achieve shannon's channel capacity for general discrete channels, The Annals of Mathematical Statistics, 42 (1971), 224-240.  doi: 10.1214/aoms/1177693508.  Google Scholar

[2]

J. P. Arpasi, One example of a non-Abelian group code over AWGN channels, Proceedings of the 14th Canadian Workshop on Information Theory, (2015), 115–119. doi: 10.1109/CWIT.2015.7255165.  Google Scholar

[3]

G. Como, Group codes outperform binary-coset codes on non-binary memoryless channels, IEEE Trans. Inform. Theory, 56 (2010), 4321-4334.  doi: 10.1109/TIT.2010.2054330.  Google Scholar

[4]

G. Como and F. Fagnani, The capacity of abelian group codes over symmetric channels, IEEE Trans. Inform. Theory, 45 (2009), 3-31.   Google Scholar

[5]

G. Como and F. Fagnani, Average spectra and minimum distance of low-density parity-check codes over abelian groups, SIAM J. Discrete Math., 23 (2008/09), 19-53.  doi: 10.1137/070686615.  Google Scholar

[6]

T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd edition, Wiley InterScience, Piscataway, NJ, 2006.  Google Scholar

[7]

G. D. Forney, Geometrically uniform codes, IEEE Trans. Inform. Theory, 37 (1991), 1241-1260.  doi: 10.1109/18.133243.  Google Scholar

[8]

R. Gallager, Information Theory and Reliable Communication, Wiley and Sons, 1970. doi: 10.1007/978-3-7091-2945-6.  Google Scholar

[9]

F. Garin and F. Fagnani, Analysis of serial turbo codes over abelian groups for symmetric channels, SIAM J. Discrete Math., 22 (2008), 1488-1526.  doi: 10.1137/07068802X.  Google Scholar

[10]

I. N. Herstein, Topics in Algebra, 2nd edition, Wiley and Sons, New York, 1975.  Google Scholar

[11]

H. J. KimJ. B. Nation and A. V. Shepler, Group coding with complex isometries, IEEE Trans. Inform. Theory, 61 (2015), 33-50.  doi: 10.1109/TIT.2014.2365020.  Google Scholar

[12]

H. A. Loeliger, Signal sets matched to groups, IEEE Trans. Inform. Theory, 37 (1991), 1675-1682.  doi: 10.1109/18.104333.  Google Scholar

[13]

H. A. Loeliger and T. Mittelholzer, Convolutional codes over groups. Codes and complexity, IEEE Trans. Inform. Theory, 42 (1996), 1660-1686.  doi: 10.1109/18.556664.  Google Scholar

[14]

T. Mittelholzer and J. Lahtonen, Group codes generated by finite reflection groups, IEEE Trans. Inform. Theory, 42 (1996), 519-528.  doi: 10.1109/18.485721.  Google Scholar

[15]

W. W. PetersonJ. B. Nation and M. P. Fossorier, Reflection group codes and their decoding, IEEE Trans. Inform. Theory, 56 (2010), 6273-6293.  doi: 10.1109/TIT.2010.2080571.  Google Scholar

[16]

J. J. Rotman, An Introduction to the Theory of the Groups, 4th edition, Graduate Texts in Mathematics, 148. Springer-Verlag, New York, 1995. doi: 10.1007/978-1-4612-4176-8.  Google Scholar

[17]

A. G. Sahebi and P. S. Pradhan, Abelian group codes for channel coding and source coding, IEEE Trans. Inform. Theory, 61 (2015), 2399-2414.  doi: 10.1109/TIT.2015.2407874.  Google Scholar

[18]

N. Shulman and M. Feder, Random coding techniques for non-random codes, IEEE Trans. Inform. Theory, 45 (1999), 2101-2104.  doi: 10.1109/18.782147.  Google Scholar

[19]

D. Slepian, Group codes for the gaussian channels, Bell Systems Technical Journal, 47 (1968), 575-602.  doi: 10.1002/j.1538-7305.1968.tb02486.x.  Google Scholar

Table 1.  $ G(\mathit{\boldsymbol{l}}) $-Symmetric sub-channels the $ D_4 $-symmetric channel 8PSK-AWGN
$ \rho $ Array Sub-group $ G(\mathit{\boldsymbol{l}}_{ijk}) $ Sub-Constellation $ {\mathcal{X}}(\mathit{\boldsymbol{l}}_{ijk}) $
1 $\left( {\begin{array}{*{20}{c}} 1&1\\ 0&{} \end{array}} \right)$ $ 2 {\mathbb{Z}}_4\boxtimes \{0\}=\{e,a^2\} $ $ \{x_0,x_4\} $
$\left( {\begin{array}{*{20}{c}} 1&1\\ 1&{} \end{array}} \right)$ $ 2 {\mathbb{Z}}_4\boxtimes {\mathbb{Z}}_2 = \{e,b,a^2,a^2b\} $ $ \{x_0,x_1,x_4,x_5\} $
2 $\left( {\begin{array}{*{20}{c}} 1&2\\ 0&{} \end{array}} \right)$ $ {\mathbb{Z}}_4\boxtimes \{0\}=\{e,a,a^2,a^3\} $ $ \{x_0,x_2,x_4,x_6\} $
$\left( {\begin{array}{*{20}{c}} 1&2\\ 1&{} \end{array}} \right)$ $ {\mathbb{Z}}_4\boxtimes {\mathbb{Z}}_2 = D_4 $ $ {\mathcal{X}}_8 $
$ \rho $ Array Sub-group $ G(\mathit{\boldsymbol{l}}_{ijk}) $ Sub-Constellation $ {\mathcal{X}}(\mathit{\boldsymbol{l}}_{ijk}) $
1 $\left( {\begin{array}{*{20}{c}} 1&1\\ 0&{} \end{array}} \right)$ $ 2 {\mathbb{Z}}_4\boxtimes \{0\}=\{e,a^2\} $ $ \{x_0,x_4\} $
$\left( {\begin{array}{*{20}{c}} 1&1\\ 1&{} \end{array}} \right)$ $ 2 {\mathbb{Z}}_4\boxtimes {\mathbb{Z}}_2 = \{e,b,a^2,a^2b\} $ $ \{x_0,x_1,x_4,x_5\} $
2 $\left( {\begin{array}{*{20}{c}} 1&2\\ 0&{} \end{array}} \right)$ $ {\mathbb{Z}}_4\boxtimes \{0\}=\{e,a,a^2,a^3\} $ $ \{x_0,x_2,x_4,x_6\} $
$\left( {\begin{array}{*{20}{c}} 1&2\\ 1&{} \end{array}} \right)$ $ {\mathbb{Z}}_4\boxtimes {\mathbb{Z}}_2 = D_4 $ $ {\mathcal{X}}_8 $
Table 2.  Output probability densities $ \lambda_{\mathit{\boldsymbol{l}}_{ijk}} $ and capacities $ C_{\mathit{\boldsymbol{l}}_{ijk}} $ of the sub-channels $ G(\mathit{\boldsymbol{l}}) $ of the $ D_4 $-symmetric channel 8PSK-AWGN, where $ p_i(y): = p(y\vert x_i) $
Array Sub-Constell. $ {\mathcal{X}}(\mathit{\boldsymbol{l}}_{ijk}) $ Density $ \lambda_{\mathit{\boldsymbol{l}}_{ijk}} $ Capacity $ C_{\mathit{\boldsymbol{l}}_{ijk}} $
$\left( {\begin{array}{*{20}{c}} 1&1\\ 0&{} \end{array}} \right)$ $ \{x_0,x_4\} $ $ \frac{1}{2}(p_0+p_4) $ $ H(\lambda_{\mathit{\boldsymbol{l}}_{110}})-H(p_0) $
$\left( {\begin{array}{*{20}{c}} 1&1\\ 1&{} \end{array}} \right)$ $ \{x_0,x_1,x_4,x_5\} $ $ \frac{1}{4}(p_0+p_1+p_4+p_5) $ $ H(\lambda_{\mathit{\boldsymbol{l}}_{111}})-H(p_0) $
$\left( {\begin{array}{*{20}{c}} 1&2\\ 0&{} \end{array}} \right)$ $ \{x_0,x_2,x_4,x_6\} $ $ \frac{1}{4}(p_0+p_2+p_4+p_6) $ $ H(\lambda_{\mathit{\boldsymbol{l}}_{120}})-H(p_0) $
$\left( {\begin{array}{*{20}{c}} 1&2\\ 1&{} \end{array}} \right)$ $ {\mathcal{X}}_8 $ $ \frac{1}{8}(p_0+p_1+\dots+p_7) $ $ H(\lambda_{\mathit{\boldsymbol{l}}_{121}})-H(p_0) $
Array Sub-Constell. $ {\mathcal{X}}(\mathit{\boldsymbol{l}}_{ijk}) $ Density $ \lambda_{\mathit{\boldsymbol{l}}_{ijk}} $ Capacity $ C_{\mathit{\boldsymbol{l}}_{ijk}} $
$\left( {\begin{array}{*{20}{c}} 1&1\\ 0&{} \end{array}} \right)$ $ \{x_0,x_4\} $ $ \frac{1}{2}(p_0+p_4) $ $ H(\lambda_{\mathit{\boldsymbol{l}}_{110}})-H(p_0) $
$\left( {\begin{array}{*{20}{c}} 1&1\\ 1&{} \end{array}} \right)$ $ \{x_0,x_1,x_4,x_5\} $ $ \frac{1}{4}(p_0+p_1+p_4+p_5) $ $ H(\lambda_{\mathit{\boldsymbol{l}}_{111}})-H(p_0) $
$\left( {\begin{array}{*{20}{c}} 1&2\\ 0&{} \end{array}} \right)$ $ \{x_0,x_2,x_4,x_6\} $ $ \frac{1}{4}(p_0+p_2+p_4+p_6) $ $ H(\lambda_{\mathit{\boldsymbol{l}}_{120}})-H(p_0) $
$\left( {\begin{array}{*{20}{c}} 1&2\\ 1&{} \end{array}} \right)$ $ {\mathcal{X}}_8 $ $ \frac{1}{8}(p_0+p_1+\dots+p_7) $ $ H(\lambda_{\mathit{\boldsymbol{l}}_{121}})-H(p_0) $
[1]

Arseny Egorov. Morse coding for a Fuchsian group of finite covolume. Journal of Modern Dynamics, 2009, 3 (4) : 637-646. doi: 10.3934/jmd.2009.3.637

[2]

Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265

[3]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119

[4]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349

[5]

Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79

[6]

Raj Kumar, Maheshanand Bhaintwal. Duadic codes over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020135

[7]

V. Kumar Murty, Ying Zong. Splitting of abelian varieties. Advances in Mathematics of Communications, 2014, 8 (4) : 511-519. doi: 10.3934/amc.2014.8.511

[8]

Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133

[9]

Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.

[10]

Mao Okada. Local rigidity of certain actions of solvable groups on the boundaries of rank-one symmetric spaces. Journal of Modern Dynamics, 2021, 17: 111-143. doi: 10.3934/jmd.2021004

[11]

Ronald E. Mickens. Positivity preserving discrete model for the coupled ODE's modeling glycolysis. Conference Publications, 2003, 2003 (Special) : 623-629. doi: 10.3934/proc.2003.2003.623

[12]

Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617

[13]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185

[14]

Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022

[15]

Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329

[16]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378

[17]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[18]

Xinyuan Liao, Caidi Zhao, Shengfan Zhou. Compact uniform attractors for dissipative non-autonomous lattice dynamical systems. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1087-1111. doi: 10.3934/cpaa.2007.6.1087

[19]

Pascal Noble, Sebastien Travadel. Non-persistence of roll-waves under viscous perturbations. Discrete & Continuous Dynamical Systems - B, 2001, 1 (1) : 61-70. doi: 10.3934/dcdsb.2001.1.61

[20]

Vieri Benci, Marco Cococcioni. The algorithmic numbers in non-archimedean numerical computing environments. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1673-1692. doi: 10.3934/dcdss.2020449

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (114)
  • HTML views (371)
  • Cited by (0)

Other articles
by authors

[Back to Top]