Iterative Basis Update for Ordered Statistics Decoding of Linear Block Codes

Ordered statistics decoding (OSD) requires Gaussian elimination (GE) for obtaining the most reliable independent positions (MRIPs) of the received vector. However, GE has cubic time complexity. Its sequential nature also introduces high latency in practice. To address this, the letter proposes an iterative basis update (IBU) to reduce complexity and latency of GE. Specifically, the IBU utilizes a systematic generator matrix (SGM) whose identity submatrix corresponds to a symbol position set. This set will then be iteratively updated for obtaining the MRIPs. For cyclic codes, the IBU can be further simplified by selecting multiple symbol position sets for the SGM. Our analysis and simulations show that the proposed IBU can significantly facilitate OSD without compromising decoding performance.