{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T16:44:04Z","timestamp":1764175444729,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,5,6]],"date-time":"2023-05-06T00:00:00Z","timestamp":1683331200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,6]],"date-time":"2023-05-06T00:00:00Z","timestamp":1683331200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["16KISK022"],"award-info":[{"award-number":["16KISK022"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The sum-rank metric is a hybrid between the Hamming metric and the rank metric and suitable for error correction in multishot network coding and distributed storage as well as for the design of quantum-resistant cryptosystems. In this work, we consider the construction and decoding of folded linearized Reed\u2013Solomon (FLRS) codes, which are shown to be maximum sum-rank distance (MSRD) for appropriate parameter choices. We derive an efficient interpolation-based decoding algorithm for FLRS codes that can be used as a list decoder or as a probabilistic unique decoder. The proposed decoding scheme can correct sum-rank errors beyond the unique decoding radius with a computational complexity that is quadratic in the length of the unfolded code. We show how the error-correction capability can be optimized for high-rate codes by an alternative choice of interpolation points. We derive a heuristic upper bound on the decoding failure probability of the probabilistic unique decoder and verify its tightness by Monte Carlo simulations. Further, we study the construction and decoding of folded skew Reed\ufeff-Solomon codes in the skew metric. Up to our knowledge, FLRS codes are the first MSRD codes with different block sizes that come along with an efficient decoding algorithm.<\/jats:p>","DOI":"10.1007\/s10623-023-01214-8","type":"journal-article","created":{"date-parts":[[2023,5,6]],"date-time":"2023-05-06T05:01:56Z","timestamp":1683349316000},"page":"553-586","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Interpolation-based decoding of folded variants of linearized and skew Reed\u2013Solomon codes"],"prefix":"10.1007","volume":"92","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2217-9753","authenticated-orcid":false,"given":"Felicitas","family":"H\u00f6rmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7767-1513","authenticated-orcid":false,"given":"Hannes","family":"Bartz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,6]]},"reference":[{"issue":"8","key":"1214_CR1","doi-asserted-by":"publisher","first-page":"5026","DOI":"10.1109\/TIT.2021.3067318","volume":"67","author":"H Bartz","year":"2021","unstructured":"Bartz H., Jerkovits T., Puchinger S., Rosenkilde J.: Fast decoding of codes in the rank, subspace, and sum-rank metric. IEEE Trans. Inf. Theory 67(8), 5026\u20135050 (2021).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1214_CR2","doi-asserted-by":"crossref","unstructured":"Bartz H.: List and probabilistic unique decoding of high-rate folded Gabidulin codes. In: WCC 2015: The 9th International Workshop on Coding and Cryptography (2015).","DOI":"10.1109\/ISIT.2015.7282407"},{"key":"1214_CR3","unstructured":"Bartz H.: Algebraic decoding of subspace and rank-metric codes. Ph.D. thesis, Technische Universit\u00e4t M\u00fcnchen (2017)."},{"key":"1214_CR4","doi-asserted-by":"crossref","unstructured":"Bartz H., Jerkovits T., Rosenkilde J.: Fast K\u00f6tter-Nielsen-H\u00f8holdt interpolation over skew polynomial rings and its application in coding theory. submitted to: Des. Codes Cryptogr. (2022), available at arxiv:2207.01319.","DOI":"10.1016\/j.ifacol.2022.11.019"},{"key":"1214_CR5","doi-asserted-by":"crossref","unstructured":"Bartz H., Puchinger S.: Fast decoding of interleaved linearized Reed\u2013Solomon codes and variants. submitted to: IEEE Trans. Inf. Theory (2022), available at arxiv:2201.01339.","DOI":"10.1109\/ISIT45174.2021.9517834"},{"issue":"1","key":"1214_CR6","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/s10623-016-0195-6","volume":"82","author":"H Bartz","year":"2017","unstructured":"Bartz H., Sidorenko V.: Algebraic decoding of folded Gabidulin codes. Des. Codes Cryptogr. 82(1), 449\u2013467 (2017).","journal-title":"Des. Codes Cryptogr."},{"key":"1214_CR7","doi-asserted-by":"crossref","unstructured":"Bartz H., Wachter-Zeh A.: Efficient interpolation-based decoding of interleaved subspace and Gabidulin codes. In: 52nd Annual Allerton Conference on Communication, Control, and Computing, pp. 1349\u20131356 (2014).","DOI":"10.1109\/ALLERTON.2014.7028612"},{"issue":"9","key":"1214_CR8","doi-asserted-by":"publisher","first-page":"1991","DOI":"10.1007\/s10623-020-00789-w","volume":"88","author":"D Boucher","year":"2020","unstructured":"Boucher D.: An algorithm for decoding skew Reed\u2013Solomon codes with respect to the skew metric. Des. Codes Cryptogr. 88(9), 1991\u20132005 (2020).","journal-title":"Des. Codes Cryptogr."},{"issue":"3","key":"1214_CR9","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/s10623-012-9704-4","volume":"70","author":"D Boucher","year":"2014","unstructured":"Boucher D., Ulmer F.: Linear codes using skew polynomials with automorphisms and derivations. Des. Codes Cryptogr. 70(3), 405\u2013431 (2014).","journal-title":"Des. Codes Cryptogr."},{"key":"1214_CR10","doi-asserted-by":"crossref","unstructured":"Brauchle J.: On the error-correcting radius of folded Reed\u2013Solomon code designs. In: Coding Theory and Applications, pp. 77\u201386 (2015).","DOI":"10.1007\/978-3-319-17296-5_7"},{"issue":"10","key":"1214_CR11","doi-asserted-by":"publisher","first-page":"6456","DOI":"10.1109\/TIT.2021.3074190","volume":"67","author":"E Byrne","year":"2021","unstructured":"Byrne E., Gluesing-Luerssen H., Ravagnani A.: Fundamental properties of sum-rank-metric codes. IEEE Trans. Inf. Theory 67(10), 6456\u20136475 (2021).","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"6","key":"1214_CR12","doi-asserted-by":"publisher","first-page":"3806","DOI":"10.1109\/TIT.2022.3156206","volume":"68","author":"E Camps-Moreno","year":"2022","unstructured":"Camps-Moreno E., Gorla E., Landolina C., Garc\u00eda E.L., Mart\u00ednez-Pe\u00f1as U., Salizzoni F.: Optimal anticodes, MSRD codes, and generalized weights in the sum-rank metric. IEEE Trans. Inf. Theory 68(6), 3806\u20133822 (2022).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1214_CR13","unstructured":"Caruso X.: Residues of skew rational functions and linearized Goppa codes. arXiv preprint (2019), available at arxiv:1908.08430v1."},{"key":"1214_CR14","unstructured":"Chen H.: Linear MSRD codes with various matrix sizes and unrestricted lengths. arXiv preprint (2022), available at arxiv:2206.02330."},{"key":"1214_CR15","unstructured":"Chen H.: New explicit good linear sum-rank-metric codes. arXiv preprint (2022), available at arxiv:2205.13087."},{"key":"1214_CR16","first-page":"208","volume":"42\u201397","author":"K Cheung","year":"1989","unstructured":"Cheung K.: The weight distribution and randomness of linear codes. TDA Prog. Rep. 42\u201397, 208\u2013215 (1989).","journal-title":"TDA Prog. Rep."},{"key":"1214_CR17","volume-title":"Elements of Information Theory","author":"TM Cover","year":"2006","unstructured":"Cover T.M., Thomas J.A.: Elements of Information Theory. Wiley, New York (2006)."},{"issue":"3","key":"1214_CR18","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1111\/j.1751-5823.2002.tb00178.x","volume":"70","author":"AL Gibbs","year":"2002","unstructured":"Gibbs A.L., Su F.E.: On choosing and bounding probability metrics. Int. Stat. Rev. 70(3), 419 (2002).","journal-title":"Int. Stat. Rev."},{"issue":"1","key":"1214_CR19","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1109\/TIT.2007.911222","volume":"54","author":"V Guruswami","year":"2008","unstructured":"Guruswami V., Rudra A.: Explicit codes achieving list decoding capacity: error-correction with optimal redundancy. IEEE Trans. Inf. Theory 54(1), 135\u2013150 (2008).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1214_CR20","doi-asserted-by":"crossref","unstructured":"H\u00f6rmann F., Bartz H.: Efficient decoding of folded linearized Reed\u2013Solomon codes in the sum-rank metric. In: WCC 2022: The Twelfth International Workshop on Coding and Cryptography (2022).","DOI":"10.1109\/ISIT50566.2022.9834742"},{"key":"1214_CR21","unstructured":"Lam T.Y.: A General Theory of Vandermonde Matrices. University of California, Berkeley, Center for Pure and Applied Mathematics (1985)."},{"issue":"2","key":"1214_CR22","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0021-8693(88)90063-4","volume":"119","author":"TY Lam","year":"1988","unstructured":"Lam T.Y., Leroy A.: Vandermonde and Wronskian matrices over division rings. J. Algebra 119(2), 308\u2013336 (1988).","journal-title":"J. Algebra"},{"key":"1214_CR23","doi-asserted-by":"crossref","unstructured":"Lam T., Leroy A.: Algebraic conjugacy classes and skew polynomial rings. In: Perspectives in Ring Theory, pp. 153\u2013203 (1988).","DOI":"10.1007\/978-94-009-2985-2_15"},{"key":"1214_CR24","doi-asserted-by":"crossref","unstructured":"Le\u00a0Gall F.: Powers of tensors and fast matrix multiplication. In: International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 296\u2013303 (2014).","DOI":"10.1145\/2608628.2608664"},{"issue":"3","key":"1214_CR25","doi-asserted-by":"publisher","first-page":"321","DOI":"10.36045\/bbms\/1103408724","volume":"2","author":"A Leroy","year":"1995","unstructured":"Leroy A., et al.: Pseudolinear transformations and evaluation in Ore extensions. Bull. Belgian Math. Soc.-Simon Stevin 2(3), 321\u2013347 (1995).","journal-title":"Bull. Belgian Math. Soc.-Simon Stevin"},{"issue":"3","key":"1214_CR26","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1007\/s10623-012-9784-1","volume":"72","author":"S Liu","year":"2014","unstructured":"Liu S., Manganiello F., Kschischang F.R.: K\u00f6tter interpolation in skew polynomial rings. Des. Codes Cryptogr. 72(3), 593\u2013608 (2014).","journal-title":"Des. Codes Cryptogr."},{"key":"1214_CR27","doi-asserted-by":"crossref","unstructured":"Liu S., Manganiello F., Kschischang F.R.: Construction and decoding of generalized skew-evaluation codes. In: IEEE 14th Canadian Workshop on Information Theory (CWIT), pp. 9\u201313 (2015).","DOI":"10.1109\/CWIT.2015.7255141"},{"issue":"5","key":"1214_CR28","doi-asserted-by":"publisher","first-page":"1709","DOI":"10.1109\/TIT.2005.846403","volume":"51","author":"HF Lu","year":"2005","unstructured":"Lu H.F., Kumar P.V.: A unified construction of space-time codes with optimal rate-diversity tradeoff. IEEE Trans. Inf. Theory 51(5), 1709\u20131730 (2005).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1214_CR29","doi-asserted-by":"crossref","unstructured":"Mahdavifar H., Vardy A.: List-decoding of subspace codes and rank-metric codes up to Singleton bound. In: IEEE International Symposium on Information Theory (ISIT), pp. 1488\u20131492 (2012).","DOI":"10.1109\/ISIT.2012.6283511"},{"key":"1214_CR30","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1016\/j.jalgebra.2018.02.005","volume":"504","author":"U Mart\u00ednez-Pe\u00f1as","year":"2018","unstructured":"Mart\u00ednez-Pe\u00f1as U.: Skew and linearized Reed\u2013Solomon codes and maximum sum rank distance codes over any division ring. J. Algebra 504, 587\u2013612 (2018).","journal-title":"J. Algebra"},{"issue":"8","key":"1214_CR31","doi-asserted-by":"publisher","first-page":"4785","DOI":"10.1109\/TIT.2019.2912165","volume":"65","author":"U Mart\u00ednez-Pe\u00f1as","year":"2019","unstructured":"Mart\u00ednez-Pe\u00f1as U., Kschischang F.R.: Reliable and secure multishot network coding using linearized Reed\u2013Solomon codes. IEEE Trans. Inf. Theory 65(8), 4785\u20134803 (2019).","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"12","key":"1214_CR32","doi-asserted-by":"publisher","first-page":"7790","DOI":"10.1109\/TIT.2019.2924888","volume":"65","author":"U Mart\u00ednez-Pe\u00f1as","year":"2019","unstructured":"Mart\u00ednez-Pe\u00f1as U., Kschischang F.R.: Universal and dynamic locally repairable codes with maximal recoverability via sum-rank codes. IEEE Trans. Inf. Theory 65(12), 7790\u20137805 (2019).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1214_CR33","doi-asserted-by":"crossref","unstructured":"N\u00f3brega R.W., Uch\u00f4a-Filho B.F.: Multishot codes for network coding using rank-metric codes. In: 3rd IEEE International Workshop on Wireless Network Coding, pp.\u00a01\u20136 (2010).","DOI":"10.1109\/WINC.2010.5507933"},{"key":"1214_CR34","doi-asserted-by":"crossref","unstructured":"Parvaresh F., Vardy A.: Correcting errors beyond the Guruswami\u2013Sudan radius in polynomial time. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 285\u2013294 (2005).","DOI":"10.1109\/SFCS.2005.29"},{"issue":"8","key":"1214_CR35","doi-asserted-by":"publisher","first-page":"5075","DOI":"10.1109\/TIT.2022.3167629","volume":"68","author":"S Puchinger","year":"2022","unstructured":"Puchinger S., Renner J., Rosenkilde J.: Generic decoding in the sum-rank metric. IEEE Trans. Inf. Theory 68(8), 5075\u20135097 (2022).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1214_CR36","unstructured":"Stein W.A., et\u00a0al.: Sage Mathematics Software (Version 9.6). The Sage Development Team (2022), http:\/\/www.sagemath.org."},{"key":"1214_CR37","doi-asserted-by":"crossref","unstructured":"Wachter-Zeh A.: Decoding of block and convolutional codes in rank metric. Ph.D. thesis, Ulm University and University of Rennes 1 (2013).","DOI":"10.1109\/NETCOD.2012.6261875"}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-023-01214-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-023-01214-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-023-01214-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T22:33:10Z","timestamp":1729377190000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-023-01214-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,6]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["1214"],"URL":"https:\/\/doi.org\/10.1007\/s10623-023-01214-8","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"type":"print","value":"0925-1022"},{"type":"electronic","value":"1573-7586"}],"subject":[],"published":{"date-parts":[[2023,5,6]]},"assertion":[{"value":"31 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 March 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 May 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}