All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD3-S5-T2.2
Paper Title Solving Monoshift Systems and Applications in Random Coding
Authors Yiheng Zhang, Ximing Fu, Xuanchen Wu, Shenghao Yang, Kenneth W. Shum, The Chinese University of Hong Kong, Shenzhen, China
Session D3-S5-T2: Topics in Coding II
Chaired Session: Wednesday, 14 July, 23:20 - 23:40
Engagement Session: Wednesday, 14 July, 23:40 - 00:00
Abstract A monoshift matrix is a matrix that has binary poly- nomails 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 full- rank probability increases to 1 almost exponentially fast as the matrix size increases. This is quite different compared with square random matrices over a fixed finite field, where the full-rank probability decreases when the matrix size increases. Certain coding problems can benefit from this special property of monoshift systems, as demonstrated by two applications: distributed storage with decentralized encoding and batched network coding.