Multi-Matrix Representative Ordered Statistics Decoding

ObjectiveRepresentative Ordered Statistics Decoding (ROSD) is a class of efficient decoding algorithms originally proposed for staircase matrix codes. ROSD supports parallel Gaussian Elimination (GE), enabling low-latency implementations. This paper extends ROSD to general linear block codes using the Minimum-Weight Staircase Generator Matrix (MWSGM) construction, which produces staircase-structured matrices for arbitrary linear codes. Based on this construction, a Multi-Matrix Representative Ordered Statistics Decoding (MM-ROSD) framework is proposed. MM-ROSD exploits the diversity of multiple candidate staircase matrices to improve decoding performance and reduce decoding complexity. For performance evaluation, a saddlepoint-approximation-based analytical framework is developed to predict the upper bound of the Frame Error Rate (FER) and to estimate the required average number of searches.MethodsThe proposed MM-ROSD algorithm consists of two main components. (1) Multi-matrix construction and selection strategy: In the construction phase, the first $ M $ minimum-weight candidate codewords are retained as the first row, that is, the first staircase. For each candidate, the remaining rows are searched independently. This process generates $ {M} $ staircase generator matrices with enhanced basis diversity. In the decoding phase, the optimal staircase matrix is selected according to the sum of reliabilities of the available re-encoding bases within each candidate matrix. ROSD is then applied to the selected staircase matrix. (2) Saddlepoint-based performance analysis: A saddlepoint approximation method is used to estimate the FER upper bound and the required average number of searches. This analysis provides guidance for complexity-performance trade-offs and parameter tuning.Results and DiscussionsExtensive simulations are performed over binary phase-shift keying modulated additive white Gaussian noise channels using 5G CA-polar codes $ \mathcal{C}[128{,}64] $ concatenated with an 11-bit Cyclic Redundancy Check (CRC). The main results are summarized as follows. Accuracy of saddlepoint approximation: The predicted FER upper bound closely matches the simulation results over the entire signal-to-noise ratio range. It also tightly approaches both the maximum-likelihood lower bound and the random coding union bound. The estimated average number of searches agrees well with simulation results in the medium and high signal-to-noise ratio regions, validating the accuracy of the analytical framework. Effect of multi-matrix diversity: Increasing the number of pre-stored staircase matrices $ M $ improves basis quality and decoding performance. For example, with $ {M}\in \{1{,}2,8\} $ and a limited maximum number of searches $ {\ell}_{\max }\in \{{10}^{4},{10}^{5},{10}^{6}\} $, the FER performance improves significantly and approaches the finite-length capacity and the ML lower bounds (Fig. 2(a)). Under a limited search list (e.g., $ {\ell}_{\max }={10}^{4} $), both the FER and the average number of searches decrease substantially as $ M $ increases. This improvement mainly results from the higher quality of the re-encoding basis enabled by the multi-matrix strategy. Under larger search budgets (e.g., $ {\ell}_{\max }={10}^{6} $), increasing $ M $ primarily reduces the average number of searches.ConclusionsThis work extends ROSD to general linear block codes and proposes an efficient MM-ROSD framework based on the MWSGM construction. By leveraging the diversity of multiple candidate staircase matrices and the low-latency property of parallel GE, the proposed approach improves decoding performance and reduces the average number of searches. The saddlepoint-based analytical framework accurately predicts both the FER and the average number of searches, providing theoretical support for practical system design. Simulation results show that, under identical maximum search constraints, MM-ROSD achieves notable FER gains and substantial reductions in the average number of searches compared with single-matrix ROSD. These results indicate that MM-ROSD is a promising decoding framework for short-block codes in ultra-reliable low-latency communication and hyper-reliable low-latency communication scenarios.