Locally Constrained Guessing Codeword Decoding of Short Block Codes

This paper is concerned with a universal guessing codeword decoding (GCD) of linear block codes, referred to as locally constrained GCD (LC-GCD), which does not require the online Gaussian elimination (GE). Distinguished from the GCD algorithm, the proposed LC-GCD queries the partial error patterns using the serial list Viterbi algorithm (SLVA) over a trellis specified by a local parity-check matrix, typically reducing the number of queries. Moreover, we introduce a parallel implementation of the LC-GCD algorithm to reduce decoding latency without compromising performance. Numerical results show that the LC-GCD requires a fewer number of queries than the GCD without performance loss, indicating a lower complexity in general. The comparisons with other decoding algorithms are also provided to demonstrate the potential advantage in complexity of the LC-GCD.

I. Introduction

The ultra-reliable low-latency communication (URLLC), enabling applications that require high reliability and very low latency, is an important use case of beyond 5G and 6G communication networks [1]–[4]. To meet the stringent requirements of URLLC, the utilization of short block codes with efficient decoding algorithms has rekindled a great deal of interest [5]. As a class of maximum-likelihood (ML) decoding algorithms for short linear block codes, the guessing codeword decoding (GCD) algorithm [6] produces a list of codewords by re-encoding patterns in an information set. A typical GCD, known as the ordered statistics decoding (OSD) [7], [8] produces a list of codewords by querying and re-encoding the patterns in the most reliable basis (MRB), where the querying process is implemented in an order of non-decreasing soft weight [7] or Hamming weight [8]. The OSD is universal and applicable to any short linear block codes (from low rates to high rates). To reduce the complexity in terms of the number of queries, several improved OSD algorithms have been proposed, such as segmentation-discarding OSD (SD-OSD) [9], probability-based OSD (PB-OSD) [10] and linear-equation