Row reduction applied to decoding of rank-metric and subspace codes

详细信息    查看全文

• 作者：Sven Puchinger ; Johan Rosenkilde né Nielsen ; Wenhui Li…
• 关键词：Skew polynomials ; Row reduction ; Module minimisation ; Gabidulin codes ; Shift register synthesis ; Mahdavifar–Vardy codes
• 刊名：Designs, Codes and Cryptography
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：82
• 期：1-2
• 页码：389-409
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Coding and Information Theory; Data Structures, Cryptology and Information Theory; Data Encryption; Discrete Mathematics in Computer Science; Information and Communication, Circuits;
• 出版者：Springer US
• ISSN：1573-7586
• 卷排序：82

文摘

We show that decoding of \(\ell \)-Interleaved Gabidulin codes, as well as list-\(\ell \) decoding of Mahdavifar–Vardy (MV) codes can be performed by row reducing skew polynomial matrices. Inspired by row reduction of \(\mathbb {F}[x]\) matrices, we develop a general and flexible approach of transforming matrices over skew polynomial rings into a certain reduced form. We apply this to solve generalised shift register problems over skew polynomial rings which occur in decoding \(\ell \)-Interleaved Gabidulin codes. We obtain an algorithm with complexity \(O(\ell \mu ^2)\) where \(\mu \) measures the size of the input problem and is proportional to the code length n in the case of decoding. Further, we show how to perform the interpolation step of list-\(\ell \)-decoding MV codes in complexity \(O(\ell n^2)\), where n is the number of interpolation constraints.