A Novel Systematic Representation of Reed-Muller Codes with an Application to Linear Block Feedback Encoding

Reed-Muller (RM) codes are an important and powerful class of codes with several applications in electrical engineering and computer science. In this work, we prove a useful property for RM codes namely that they admit a special systematic generator matrix where the parity component has embedded in it a surprisingly large triangle of zeros. Asymptotically, the size in sub-diagonals of this all-zero triangle is shown to approach the largest possible value ∆⋆= min(K,N −K) where K and N are the code dimension and code length respectively. To demonstrate an application of this result, we introduce the concept of linear block feedback codes where an open loop codeword is combined linearly with the feedback signal during encoding at the transmitter. This is shown to allow strengthening of a weak code to be as good as any desired code. We then show that, by virtue of the above property of RM codes, they can be emulated from an uncoded system using linear feedback encoding against remarkably large feedback delays.