The Partial-Inverse Approach to Linearized Polynomials and Gabidulin Codes with Applications to Network Coding

Jiun Hung Yu, Hans Andrea Loeliger

Research output: Contribution to journalArticlepeer-review

Abstract

This paper introduces the partial-inverse problem for linearized polynomials and develops its application to decoding Gabidulin codes and lifted Gabidulin codes in linear random network coding. The proposed approach is a natural generalization of its counterpart for ordinary polynomials, thus providing a unified perspective on Reed–Solomon codes for the Hamming metric and for the rank metric. The basic algorithm for solving the partial-inverse problem is a common parent algorithm of a Berlekamp–Massey algorithm, a Euclidean algorithm, and yet another algorithm, all of which are obtained as easy variations of the basic algorithm. Decoding Gabidulin codes can be reduced to the partial-inverse problem via a key equation with a new converse. This paper also develops new algorithms for interpolating crisscross erasures and for joint decoding of errors, erasures, and deviations in random network coding.

Original languageEnglish
Pages (from-to)1
Number of pages1
JournalIEEE Transactions on Information Theory
DOIs
StateAccepted/In press - 2023

Keywords

  • Berlekamp–Massey algorithm
  • Codes
  • Decoding
  • Encoding
  • Euclidean algorithm
  • Gabidulin codes
  • Interpolation
  • Inverse problems
  • key equation
  • Measurement
  • Network coding
  • partial-inverse algorithm
  • partial-inverse problem

Fingerprint

Dive into the research topics of 'The Partial-Inverse Approach to Linearized Polynomials and Gabidulin Codes with Applications to Network Coding'. Together they form a unique fingerprint.

Cite this