Low-Complexity Ordered Reliability Direct Error Pattern Testing (ORDEPT) Decoding with Likelihood Thresholding
Reza Hadavian, Dmitri Truhachev · 2025
Read Low-Complexity Ordered Reliability Direct Error Pattern Testing (ORDEPT) Decoding with Likelihood Thresholding by Reza Hadavian, Dmitri Truhachev (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-20079.txt.
Introduction
Reza Hadavian and Dmitri Truhachev published a 2025 paper on faster decoding of error-correcting codes. Digital messages are sent with extra structure so receivers can fix errors. One decoding method, ORDEPT, tests likely error patterns in order until a valid message appears, but testing many patterns is slow.
The authors add an early stopping rule based on likelihood, a measure of how well a candidate matches the received signal. Once a candidate falls below a set threshold of difference, decoding ends at once. Error performance stayed the same as before. At the same time, delay and computing cost fell several-fold compared with leading methods. The gain matters for fast, low-power communication devices.
Catalog record
| CREATOR | Reza Hadavian, Dmitri Truhachev |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 17 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-20079
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Low-Complexity Ordered Reliability Direct Error Pattern Testing (ORDEPT) Decoding with Likelihood Thresholding Reza Hadavian, Dmitri Truhachev Abstract 1 Introduction The design of new low-complexity and latency soft decoding algorithms for short block codes is receiving increased research interest due to developments in high-speed optical and massive wireless communications. Fiber-optical communication modules that reach speeds of terabit per second on a single wavelength require low-complexity, near-error-free error-correction coding, typically constructed by concatenation of short codes [ 1 , 2 ] . Massive machine-to-machine (M2M) communications, remote industrial automation, Internet-of-Things (IoT), virtual reality, telehealth, and many other applications within the realm of 5G and 6G mobile communications necessitate reliable ultra low-latency short packet communications. Therefore, the traditional ordered statistic decoding (OSD) and the industry-standard Chase decoding [ 3 ] have recently been complemented by a variety of new algorithms such as soft versions of guessing random additive noise decoding (GRAND) [ 4 , 5 ] , direct error-pattern testing (DEPT) and ORDEPT [ 6 , 7 ] , and guessing codeword decoding (GCD) [ 8 , 9 ] . Typically, these algorithms test error patterns in the order of their approximate likelihood until one or several candidate codewords are found and the best candidate is selected. The complexity of such pattern-based search is largely determined by the number of queries and the operations associated with testing of each query. Lowering testing complexity is crucial for making the hardware implementation of such algorithms competitive. In this work we propose a low-complexity ORDEPT decoding with likelihood-based termination. The decoding operates as follows: 1) Instead of testing complete error patterns in the order of their likelihood, the algorithm tests partial error patterns which are missing one error position. The final position is found on-the-fly by a combinational logic function, reducing the overall number of queries dramatically. 2) In addition, once a candidate codeword is found, its log-likelihood difference to the received sequence is compared to a preset threshold and the decoding decision is instantly made in case the likelihood deviation is below the threshold. We demonstrate that while keeping the same block error rate (BLER) performance, the proposed algorithm’s latency and complexity is multiple times smaller than that of all other state-of-the art competitors including the Chase II, ORBGRAND, GCD and the very recent ORDEPT with Soft-Output GRAND termination [ 10 ] which necessitates several multiplications in each query processing. The results for decoding of Bose–Chaudhuri–Hocquenghem (BCH) (256,239) code serving as a component code in 400ZR+ [ 1 , 2 ] , BCH(32,21) codes, and (128,116) Polar code are demonstrated in Section 5 . We can observe that the proposed algorithm’s BLER performance is at par with the competitors’, while the numbers of required operations (computational complexity) are orders of magnitude smaller. 2 System Model Consider a binary information vector of length k , which is encoded using a binary linear (n,k) block code \mathcal{C} . The encoding procedure produces an n -bit codeword \boldsymbol{c}=({c}_{0},{c}_{1},\ldots,{c}_{n-1}) , where {c}_{i}\in\{0,1\} for i\in\{0,\ldots,n-1\} . The codeword \boldsymbol{c} is subsequently modulated using binary phase-shift keying (BPSK). Each element c_{i} of the codeword is mapped to x_{i}\in\{-1,1\} according to the relation x_{i}=1-2c_{i} . The resulting modulated signal \boldsymbol{x}=({x}_{0},{x}_{1},\ldots,{x}_{n-1}) is transmitted over a real-valued additive white Gaussian noise (AWGN) channel. The channel output is expressed as \boldsymbol{y}=\boldsymbol{x}+\boldsymbol{\zeta}, (1) where \boldsymbol{\zeta} is a vector of independent and identically distributed (i.i.d.) Gaussian random variables with zero mean and variance \sigma^{2} . The system model is depicted in Fig 1 . Using ( 1 ), the hard-decision received sequence \boldsymbol{w} is obtained by computing \boldsymbol{w}=\frac{1}{2}(\mathrm{sign}(\boldsymbol{y})+1) . The noise effect, represented as {\boldsymbol{z}} , is defined as the difference between the transmitted codeword \boldsymbol{c} and the hard-decision sequence \boldsymbol{w} , i.e., {\boldsymbol{z}}=\boldsymbol{c}\oplus\boldsymbol{w} . \mathrm{Encoder} BPSK Modulator AWGN \boldsymbol{\zeta}\sim\mathcal{N}(0,\sigma^{2}) \boldsymbol{u}=(u_{0},\ldots,u_{k-1}) u_{i}\in\{0,1\} \boldsymbol{c}=(c_{0},\ldots,c_{n-1}) c_{i}\in\{0,1\} \boldsymbol{x}=(x_{0},\ldots,x_{n-1}) x_{i}\in\{-1,1\} \boldsymbol{y}=\boldsymbol{x}+\boldsymbol{\zeta} Figure 1: Block diagram of system model. We denote the absolute values of the received sequence bit LLRs as |\boldsymbol{l}|=(|l_{0}|,|l_{1}|,\ldots,|l_{n-1}|) , where l_{i}=2y_{i}\sigma^{-2} for i=0,1,\ldots,n-1 . These values can be sorted in ascending order using a permutation \boldsymbol{\pi}=(\pi_{0},\ldots,\pi_{n-1}) . Depending on how the LLR vector and the ordering permutation \boldsymbol{\pi} are utilized, various universal soft-decoding techniques can be identified, which aim to recover \boldsymbol{x} from \boldsymbol{y} . 3 Decoding Algorithms Consider the following decoding algorithms, recently proposed in literature. 3.1 ORBGRAND Operates on a list of test error patterns \hat{\boldsymbol{e}}^{(1)},\ldots,\hat{\boldsymbol{e}}^{(q)},\ldots , where \hat{\boldsymbol{e}}^{(q)}=(\hat{e}_{0}^{(q)},\ldots,\hat{e}_{n-1}^{(q)}) , \hat{e}_{i}^{(q)}\in\{0,1\} , are ordered from most likely to list likely. The algorithm checks if (\boldsymbol{w}\oplus\tilde{\boldsymbol{e}}^{(Q)}){\bf H}^{\textrm{T}}=\boldsymbol{0} . The first codeword for which this equality holds will be output. In the list ORBGRAND [ 11 ] , the decoder continues the search to find C_{\mathrm{max}} codewords where C_{\mathrm{max}} is maximum number of found codewords. Then, the most likely codeword is output. 3.2 ORDEPT The ORDEPT algorithm operates on a list of PEPs instead of full error patterns. A PEP, represented as \boldsymbol{e} , is a binary vector where each element e_{i} indicates a potential error at the i -th position by being set to 1 . However, the final error position — which is associated with the lowest likelihood and thus the highest index — remains 0 , along with all other components of \boldsymbol{e} . The key idea is to determine whether a given PEP can be completed by appending an index for the last error position, resulting in a valid codeword. Applying a PEP represented by \boldsymbol{e} , which contains N-1 ones at the positions e_{j_{0}},e_{j_{1}},\ldots,e_{j_{N-2}} , to the hard-decision received sequence \boldsymbol{w} results in the computation of a partial syndrome vector as follows: \tilde{\boldsymbol{s}}=(\boldsymbol{w}\oplus{\boldsymbol{e}}){\bf H}^{\textrm{T}}=\boldsymbol{s}\oplus\boldsymbol{h}{j_{0}}\oplus\boldsymbol{h}{j_{1}}\oplus\cdots\oplus\boldsymbol{h}_{j{N-2}}, (2) where \boldsymbol{h}_{j_{i}} denotes the j_{i} -th column of the code’s parity-check matrix \bf{H} for i=0,\ldots,N-2 , and \boldsymbol{s} is the (n-k) -bit syndrome vector defined by \boldsymbol{s}=\boldsymbol{w}{\bf H}^{\textrm{T}} . This partial syndrome \tilde{\boldsymbol{s}} is subsequently used to determine the final error position, denoted as j_{*} , which completes the PEP \boldsymbol{e} so that the full error pattern \tilde{\boldsymbol{e}} yields a valid codeword. Here, \tilde{\boldsymbol{e}} represents the completed error pattern such that \tilde{e}_{j}=e_{j} for all j\neq j_{*} , and \tilde{e}_{j_{*}}=1 . Identifying j_{*} means finding a column in {\bf H} for which \tilde{\boldsymbol{s}}=\boldsymbol{h}_{j_{*}} . This association is performed using a function f(\tilde{\boldsymbol{s}}) that maps the column vector \boldsymbol{h}_{j}=\tilde{\boldsymbol{s}} of \bf{H} to its corresponding index j_{*} : f(\tilde{\boldsymbol{s}})=\begin{cases}j_{*}&\mathrm{if}\quad\tilde{\boldsymbol{s}}=\boldsymbol{h}_{j_{*}}\\ -1&\mathrm{otherwise.}\end{cases} (3) A result of f(\tilde{\boldsymbol{s}})=-1 indicates that no column index j_{*} satisfies \boldsymbol{h}_{j_{*}}=\tilde{\boldsymbol{s}} . When j_{*} is successfully located and f(\tilde{\boldsymbol{s}})\neq-1 , the corrected codeword is given by \tilde{\boldsymbol{c}}=\boldsymbol{w}\oplus\tilde{\boldsymbol{e}}. (4) The performance of the proposed algorithm can be enhanced if it continues to search for additional candidate codewords after finding the first one. In such a scenario, the LLR summation of the completed error patterns, that is denoted via \epsilon(\tilde{\boldsymbol{c}}) are calculated, and the candidate with the smallest LLR summation is selected as the decoded codeword. 3.3 ORDEPT with SOGRAND-based thresholding For each decoding, SOGRAND provides an a-posteriori probability that a codeword is correct or the decoding is not in the list. Denoting the a-posteriori probability of each guessed word via p(\boldsymbol{y}^{(i)}|\boldsymbol{l})=\prod_{j=0}^{n-1}\left\{\begin{array}[]{ll}\displaystyle\frac{1}{1+\mathrm{exp}(-l_{j})},&\quad y_{j}^{i}=0\\[10.00002pt] \displaystyle\frac{1}{1+\mathrm{exp}(l_{j})},&\quad y_{j}^{i}=1\end{array}\right., (5) during the guessing procedure, the algorithm accumulates the probabilities of the guesses \boldsymbol{y}^{(i)} from p_{\mathrm{noise}}=\sum_{i=1}^{q}p(\boldsymbol{y}^{(i)}|\boldsymbol{l}), (6) where q is the number of guesses. Let \mathcal{L}\subset\mathcal{C} be a list of the codewords that the decoder has