Solving Monoshift Systems and Applications in Random Coding

A monoshift matrix is a matrix that has binary polynomials of degree at most 1 as entries, and a monoshift system is a system of linear equations over polynomials with a monoshift coefficient matrix. We propose an algorithm called augmented elimination to reduce a monoshift matrix to a form called augmented echelon form of degree at most 1. The monoshift system in augmented echelon form can be solved efficiently by successive cancellation. We further derive a recursive formula of the rank distribution of a uniformly random monoshift matrix. For a square uniformly random monoshift matrix, the deficient-rank probability decreases to 0 almost exponentially fast as the matrix size increases. This is quite different compared with the square random matrices over a fixed finite field, where the deficient-rank probability increases when the matrix size increases. Certain coding problems can benefit from this special property of monoshift systems, as demonstrated by the applications in distributed storage systems with decentralized encoding and in batched network coding.