{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:12:33Z","timestamp":1760242353009,"version":"build-2065373602"},"reference-count":31,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2017,5,20]],"date-time":"2017-05-20T00:00:00Z","timestamp":1495238400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>This paper presents a coding theorem for linear coding over finite rings, in the setting of the Slepian\u2013Wolf source coding problem. This theorem covers corresponding achievability theorems of Elias (IRE Conv. Rec. 1955, 3, 37\u201346) and Csisz\u00e1r (IEEE Trans. Inf. Theory 1982, 28, 585\u2013592) for linear coding over finite fields as special cases. In addition, it is shown that, for any set of finite correlated discrete memoryless sources, there always exists a sequence of linear encoders over some finite non-field rings which achieves the data compression limit, the Slepian\u2013Wolf region. Hence, the optimality problem regarding linear coding over finite non-field rings for data compression is closed with positive confirmation with respect to existence. For application, we address the problem of source coding for computing, where the decoder is interested in recovering a discrete function of the data generated and independently encoded by several correlated i.i.d. random sources. We propose linear coding over finite rings as an alternative solution to this problem. Results in K\u00f6rner\u2013Marton (IEEE Trans. Inf. Theory 1979, 25, 219\u2013221) and Ahlswede\u2013Han (IEEE Trans. Inf. Theory 1983, 29, 396\u2013411, Theorem 10) are generalized to cases for encoding (pseudo) nomographic functions (over rings). Since a discrete function with a finite domain always admits a nomographic presentation, we conclude that both generalizations universally apply for encoding all discrete functions of finite domains. Based on these, we demonstrate that linear coding over finite rings strictly outperforms its field counterpart in terms of achieving better coding rates and reducing the required alphabet sizes of the encoders for encoding infinitely many discrete functions.<\/jats:p>","DOI":"10.3390\/e19050233","type":"journal-article","created":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T01:47:33Z","timestamp":1495504053000},"page":"233","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Linear Coding over Finite Rings and Applications to Computing"],"prefix":"10.3390","volume":"19","author":[{"given":"Sheng","family":"Huang","sequence":"first","affiliation":[{"name":"Communication Theory Lab, School of Electrical Engineering, KTH Royal Institute of Technology, Stockholm 10044, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikael","family":"Skoglund","sequence":"additional","affiliation":[{"name":"Communication Theory Lab, School of Electrical Engineering, KTH Royal Institute of Technology, Stockholm 10044, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,5,20]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1109\/TIT.1973.1055037","article-title":"Noiseless Coding of Correlated Information Sources","volume":"19","author":"Slepian","year":"1973","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","first-page":"37","article-title":"Coding for Noisy Channels","volume":"3","author":"Elias","year":"1955","journal-title":"IRE Conv. Rec."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1109\/TIT.1982.1056524","article-title":"Linear Codes for Sources and Source Networks: Error Exponents, Universal Coding","volume":"28","year":"1982","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1109\/TIT.1979.1056022","article-title":"How to Encode The Modulo-Two Sum of Binary Sources","volume":"25","author":"Marton","year":"1979","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1109\/TIT.1983.1056669","article-title":"On Source Coding with Side Information via a Multiple-Access Channel and Related Problems in Multi-User Information Theory","volume":"29","author":"Ahlswede","year":"1983","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Huang, S., and Skoglund, M. (2012, January 1\u20136). Polynomials and Computing Functions of Correlated Sources. Proceedings of the 2012 IEEE International Symposium on Information Theory, Cambridge, MA, USA.","DOI":"10.1109\/ISIT.2012.6284664"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Huang, S., and Skoglund, M. (2012, January 28\u201331). Computing Polynomial Functions of Correlated Sources: Inner Bounds. Proceedings of the International Symposium on Information Theory and Its Applications, Honolulu, HI, USA.","DOI":"10.1109\/ISIT.2012.6284664"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1109\/TIT.1987.1057272","article-title":"A Dichotomy of Functions F(X, Y) of Correlated Sources (X, Y) from the Viewpoint of the Achievable Rate Region","volume":"33","author":"Han","year":"1987","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"2037","DOI":"10.1109\/TIT.2009.2015992","article-title":"The Capacity of Finite Abelian Group Codes over Symmetric Memoryless Channels","volume":"55","author":"Como","year":"2009","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"4321","DOI":"10.1109\/TIT.2010.2054330","article-title":"Group codes outperform binary-coset codes on nonbinary symmetric memoryless channels","volume":"56","author":"Como","year":"2010","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1495","DOI":"10.1109\/TIT.2010.2103852","article-title":"Distributed Source Coding Using Abelian Group Codes: A New Achievable Rate-Distortion Region","volume":"57","author":"Krithivasan","year":"2011","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Rotman, J.J. (2010). Advanced Modern Algebra, American Mathematical Society. [2nd ed.].","DOI":"10.1090\/gsm\/114"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/BF01950276","article-title":"Polynomial functions (modm)","volume":"44","author":"Mullen","year":"1984","journal-title":"Acta Math. Hung."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Hungerford, T.W. (1980). Algebra (Graduate Texts in Mathematics), Springer.","DOI":"10.1007\/978-1-4612-6101-8"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Lam, T.Y. (2001). A First Course in Noncommutative Rings, Springer. [2nd ed.].","DOI":"10.1007\/978-1-4419-8616-0"},{"key":"ref_16","unstructured":"Dummit, D.S., and Foote, R.M. (2003). Abstract Algebra, Wiley. [3rd ed.]."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Anderson, F.W., and Fuller, K.R. (1992). Rings and Categories of Modules, Springer. [2nd ed.].","DOI":"10.1007\/978-1-4612-4418-9"},{"key":"ref_18","unstructured":"Yeung, R.W. (2008). Information Theory and Network Coding, Springer. [1st ed.]."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Cover, T.M., and Thomas, J.A. (2006). Elements of Information Theory, Wiley. [2nd ed.].","DOI":"10.1002\/047174882X"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Huang, S., and Skoglund, M. (2013, January 7\u201312). On achievability of linear source coding over finite rings. Proceedings of the 2013 IEEE International Symposium on Information Theory Proceedings (ISIT), Istanbul, Turkey.","DOI":"10.1109\/ISIT.2013.6620573"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Huang, S., and Skoglund, M. (2013). Encoding Irreducible Markovian Functions of Sources: An Application of Supremus Typicality, KTH Royal Institute of Technology.","DOI":"10.1109\/ISIT.2014.6875313"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1090\/S0002-9939-1982-0652441-4","article-title":"Nomographic Functions are Nowhere Dense","volume":"85","author":"Buck","year":"1982","journal-title":"Proc. Am. Math. Soc."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Huang, S., and Skoglund, M. (2012, January 24\u201326). Linear Source Coding over Rings and Applications. Proceedings of the IEEE Swedish Communication Technologies Workshop, Lund, Sweden.","DOI":"10.1109\/Swe-CTW.2012.6376282"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1002\/j.1538-7305.1968.tb02486.x","article-title":"Group Codes for the Gaussian Channel","volume":"47","author":"Slepian","year":"1968","journal-title":"Bell Syst. Tech. J."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1214\/aoms\/1177693508","article-title":"Group Codes do not Achieve Shannon\u2019s Channel Capacity for General Discrete Channels","volume":"42","author":"Ahlswede","year":"1971","journal-title":"Ann. Math. Stat."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1797","DOI":"10.1109\/18.165454","article-title":"On the Hamming distance properties of group codes","volume":"38","author":"Forney","year":"1992","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"918","DOI":"10.2307\/2312421","article-title":"Rings of Order Four","volume":"71","author":"Singmaster","year":"1964","journal-title":"Math. Assoc. Am."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Chan, T.H., and Grant, A. (2007, January 24\u201329). Entropy vector and network codes. Proceedings of the IEEE International Symposium on Information Theory, Nice, France.","DOI":"10.1109\/ISIT.2007.4557448"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1277","DOI":"10.1109\/18.508859","article-title":"Group Block Codes Over Nonabelian Groups are Asymptotically Bad","volume":"42","author":"Interlando","year":"1996","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_30","unstructured":"Du, J., and Andersson, M. Personal Communication."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Lidl, R., and Niederreiter, H. (1997). Finite Fields, Gambridge University Press. [2nd ed.].","DOI":"10.1017\/CBO9780511525926"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/19\/5\/233\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:36:31Z","timestamp":1760207791000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/19\/5\/233"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,20]]},"references-count":31,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2017,5]]}},"alternative-id":["e19050233"],"URL":"https:\/\/doi.org\/10.3390\/e19050233","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2017,5,20]]}}}