American Institute of Mathematical Sciences

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

On the non-Abelian group code capacity of memoryless channels

Jorge P. Arpasi ,

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

* Corresponding author

Received  November 2018 Revised  August 2019 Published  August 2020 Early access  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.

Keywords: Group codes, symmetric channels, group encoding capacity, non-Abelian group codes, converse of Shannon's coding theorem, achievement of channel capacity.
Mathematics Subject Classification: Primary: 94A05, 94A24; Secondary: 94B60.
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. Kim, J. 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. Peterson, J. 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. Kim, J. 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. Peterson, J. 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 $
Table Options

Download as excel

$ \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) $
Table Options

Download as excel

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]

Cristina García Pillado, Santos González, Victor Markov, Consuelo Martínez, Alexandr Nechaev. New examples of non-abelian group codes. Advances in Mathematics of Communications, 2016, 10 (1) : 1-10. doi: 10.3934/amc.2016.10.1
[2]

Sergio Estrada, J. R. García-Rozas, Justo Peralta, E. Sánchez-García. Group convolutional codes. Advances in Mathematics of Communications, 2008, 2 (1) : 83-94. doi: 10.3934/amc.2008.2.83
[3]

Crnković Dean, Vedrana Mikulić Crnković, Bernardo G. Rodrigues. On self-orthogonal designs and codes related to Held's simple group. Advances in Mathematics of Communications, 2018, 12 (3) : 607-628. doi: 10.3934/amc.2018036
[4]

Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385
[5]

Jamshid Moori, Amin Saeidi. Some designs and codes invariant under the Tits group. Advances in Mathematics of Communications, 2017, 11 (1) : 77-82. doi: 10.3934/amc.2017003
[6]

Steven T. Dougherty, Cristina Fernández-Córdoba, Roger Ten-Valls, Bahattin Yildiz. Quaternary group ring codes: Ranks, kernels and self-dual codes. Advances in Mathematics of Communications, 2020, 14 (2) : 319-332. doi: 10.3934/amc.2020023
[7]

Eldho K. Thomas, Nadya Markin, Frédérique Oggier. On Abelian group representability of finite groups. Advances in Mathematics of Communications, 2014, 8 (2) : 139-152. doi: 10.3934/amc.2014.8.139
[8]

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
[9]

Olof Heden, Fabio Pasticci, Thomas Westerbäck. On the existence of extended perfect binary codes with trivial symmetry group. Advances in Mathematics of Communications, 2009, 3 (3) : 295-309. doi: 10.3934/amc.2009.3.295
[10]

Axel Kohnert, Johannes Zwanzger. New linear codes with prescribed group of automorphisms found by heuristic search. Advances in Mathematics of Communications, 2009, 3 (2) : 157-166. doi: 10.3934/amc.2009.3.157
[11]

Tobias Sutter, David Sutter, John Lygeros. Capacity of random channels with large alphabets. Advances in Mathematics of Communications, 2017, 11 (4) : 813-835. doi: 10.3934/amc.2017060
[12]

Carolyn Mayer, Kathryn Haymaker, Christine A. Kelley. Channel decomposition for multilevel codes over multilevel and partial erasure channels. Advances in Mathematics of Communications, 2018, 12 (1) : 151-168. doi: 10.3934/amc.2018010
[13]

Elena Celledoni, Brynjulf Owren. Preserving first integrals with symmetric Lie group methods. Discrete & Continuous Dynamical Systems, 2014, 34 (3) : 977-990. doi: 10.3934/dcds.2014.34.977
[14]

Steven T. Dougherty, Joe Gildea, Abidin Kaya, Bahattin Yildiz. New self-dual and formally self-dual codes from group ring constructions. Advances in Mathematics of Communications, 2020, 14 (1) : 11-22. doi: 10.3934/amc.2020002
[15]

Bernardo Gabriel Rodrigues. Some optimal codes related to graphs invariant under the alternating group $A_8$. Advances in Mathematics of Communications, 2011, 5 (2) : 339-350. doi: 10.3934/amc.2011.5.339
[16]

Joe Gildea, Adrian Korban, Abidin Kaya, Bahattin Yildiz. Constructing self-dual codes from group rings and reverse circulant matrices. Advances in Mathematics of Communications, 2021, 15 (3) : 471-485. doi: 10.3934/amc.2020077
[17]

Maria Bortos, Joe Gildea, Abidin Kaya, Adrian Korban, Alexander Tylyshchak. New self-dual codes of length 68 from a $ 2 \times 2 $ block matrix construction and group rings. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020111
[18]

Joe Gildea, Abidin Kaya, Adam Michael Roberts, Rhian Taylor, Alexander Tylyshchak. New self-dual codes from $ 2 \times 2 $ block circulant matrices, group rings and neighbours of neighbours. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021039
[19]

John Franks, Michael Handel. Some virtually abelian subgroups of the group of analytic symplectic diffeomorphisms of a surface. Journal of Modern Dynamics, 2013, 7 (3) : 369-394. doi: 10.3934/jmd.2013.7.369
[20]

Steven T. Dougherty, Joe Gildea, Adrian Korban, Abidin Kaya. Composite constructions of self-dual codes from group rings and new extremal self-dual binary codes of length 68. Advances in Mathematics of Communications, 2020, 14 (4) : 677-702. doi: 10.3934/amc.2020037

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (186)
  • HTML views (374)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences