In this paper, we propose a fixed-to-fixed length coding approach to near-lossless compression by leveraging block Markov superposition transmission (BMST) of generalized Reed-Solomon (GRS) codes. To compress non-uniform non-binary sources, we propose two schemes: multi-level coding with a natural mapper and single-level coding with a mapper called sparsifier. The multi-level coding can be proved to achieve the source entropy, while the single-level coding is more suitable for practical use. Both the natural mapper and the sparsifier map non-binary symbols with higher probability to sparser binary vectors of fixed length. When compared with variable-length coding, the most distinguished feature of the proposed coding is that the error propagation caused by a few erroneous bits can be controlled. Even more, the proposed scheme can be easily extended as joint source-channel coding (JSCC) with a wide range of code rates by fixing the input while lengthening the output. Numerical results show that the proposed codes can approach the Shannon limits for transmitting non-uniform sources over noisy channels, providing a universal way to trade off bandwidth and the transmission power.

This paper proposes an improved ordered statistics decoding (OSD) algorithm, termed OSD with pre-stored systematic matrices (PSM-OSD), which completely avoids online Gaussian elimination by pre-storing multiple systematic generator matrices (SGMs) and selecting one based on the received sequence for decoding. To further improve the search efficiency, the local-constraint mechanism is combined with the PSM-OSD, resulting in the LC-PSM-OSD. We then address three critical questions for design: how many SGMs should be pre-stored, how they should be constructed, and how to select one for decoding. For the first question, we introduce the notion of maximum reliable-information coverage, which characterizes how well the pre-stored SGMs match the reliable bit positions. For construction and selection, we introduce a Reed-Muller-based design to ensure high basis diversity, and the sum-reliability strategy provides superior decoding performance among the tested selection criteria. A saddlepoint-based analytical framework is developed to estimate both the frame error rate (FER) upper bound and the average number of searches, enabling pre-stored matrix design without exhaustive decoding simulations. We also prove that, with tailored early stopping and unlimited maximum number of searches, the proposed algorithm is a non-exhaustive-search ML decoding algorithm. Numerical results and analysis demonstrate that the proposed decoding algorithms are effective across various coding schemes, including random linear codes, BCH codes, and 5G polar codes. Moreover, the results show that the proposed LC-PSM-OSD can closely approach the finite-length capacity over almost all code rates for the considered codes, and outperforms conventional OSD, guessing codeword decoding (GCD), and LC-GCD. © 2026 IEEE.

In this paper, we prove that the sub-field image of generalized Reed-Solomon (RS) code ensemble can achieve the symmetric capacity ofp-ary memoryless channels. Unlike the totally random linear code ensemble, as a class of maximum distance separable (MDS) codes, the generalized RS code ensemble lacks the pair-wise independence among codewords and has non-identical distributions of nonzero codewords. To prove the coding theorem for thep-ary images of generalized RS code ensemble, we analyze the exponential upper bound on the error probability of the generalized RS code in terms of its spectrum using random coding techniques. In the finite-length region, we present an ML decoding algorithm for the generalized RS codes over the binary erasure channels (BECs). In particular, the algebraic structure of the generalized RS codes allows us to implement the parallel Lagrange interpolation to derive an ordered systematic matrix. Subsequently, we can reconstruct the ML codeword through a change of basis, accelerating the conventional Gaussian elimination (GE), as validated in the simulation results. Additionally, we apply this decoding technique to the ordered statistic decoding with local constraints (LC-OSD) algorithm over the additive white Gaussian noise (AWGN) channels with binary phase shift keying (BPSK) modulation and three-level pulse amplitude modulation (3PAM). Simulation results show that, in the high-rate region, generalized RS codes defined over fields of characteristic three with 3PAM perform better than those defined over fields of characteristic two with BPSK.

This paper proposes an enhanced guessing codeword decoding (GCD) algorithm, termed GCD with most reliable cyclic basis (MRCB-GCD), specifically tailored for BCH codes. Unlike original GCD, the proposed method selects the k consecutive bits with the highest aggregate reliability as the re-encoding basis, leveraging the cyclic structure of BCH codes. To further enhance search efficiency, a local constraint (LC) mechanism is introduced, where the extended reliable bits of length k+δ enable the algorithm to skip numerous unnecessary test error patterns (TEPs). To stop the search process, we introduce two termination criteria and prove that the proposed approach with the trivial termination criterion forms a non-exhaustive-search maximum likelihood (ML) decoding algorithm. A saddlepoint-based numerical method is developed to approximately calculate the upper bound on the performance gap to the ML decoding and estimate the average number of searches, showing the advantages of the proposed MRCB-GCD over the original GCD in terms of both decoding performance and search efficiency. Simulation results demonstrate that: 1) MRCB- GCD outperforms original GCD in both frame error rate (FER) and number of searches, 2) the LC mechanism and termination criteria further reduce the number of searches, and 3) the proposed approach achieves finite-length capacity across various code rates but without requiring Gaussian elimination.

In this paper, we propose a new coding approach to near-lossless compression of$Q$-ary sources by utilizing a sparsifier and block Markov superposition transmission (BMST) codes. The symbols from a$Q$-ary source are mapped to fixedlength binary vectors by the sparsifier such that the symbols with higher probabilities are mapped to vectors of lower weights. The binary sparse sequences are then compressed in a BMST manner. The most distinguished feature of the proposed source coding is that the error propagation can be mitigated in the presence of noise. Numerical results show that the proposed scheme performs well for$Q$-ary sources, providing a universal but simple way to achieve near-lossless coding at rates approaching the source entropy.

This paper is concerned with a new list decoding algorithm called list coset decoding. With the recently proposed linear coding framework, we first give a theorem for the optimality of the list coset decoding. Different from the commonly accepted list decoding, which attempts to find a list ofLmost probable candidate codewords, we form a list (with a constrained size) that may not contain all theLmost reliable candidate codewords but still contains the transmitted (uncoded) vector with high probability. The list coset decoding divides the space into subspaces so that the transmitted vector can be reached with high probability. We then apply the list coset decoding to the ordered statistics decoding with local constraints (LC-OSD) to implement the parallel decoding for linear block codes. With the dynamic approximate ideal (DAI) early stopping criterion, the newly proposed algorithm can reduce the decoding delay, compared with the serial implementation. To numerically evaluate the decoding delay, we propose to use the saddlepoint approximation, which is a high-accuracy counting method. Simulation results show that the estimation matches well with the simulation results in high signal-to-noise ratio (SNR) region. To further reduce the decoding delay, we propose several offline test error pattern (TEP) generation methods. Then, the parallel decoding can exploit the pre-stored TEPs for each coset list. Simulation results demonstrate that the parallel list coset decoding in LC-OSD, utilizing offline TEP generation based on empirical reliability, has minimal performance degradation. The simulation results also show that, on average, one or two trials in parallel are sufficient for near maximum-likelihood (ML) performance.

In this paper, we prove that the generalized Reed-Solomon (RS) codes are capacity-achieving over binary-input output-symmetric (BIOS) channels, in terms of frame error rate (FER) under maximum likelihood (ML) decoding. In the finite-length region, we present the ordered statistics decoding with local constraints (LC-OSD) algorithm for the generalized RS codes. In particular, the extended most reliable basis (MRB) is derived based on a systematic matrix calculated by the parallel Lagrange interpolation, accelerating the conventional Gaussian elimination (GE). Additionally, we propose a joint source-channel coding (JSCC) scheme that incorporates generalized RS codes and classified enumerative (CE) coding, where the partition of the source is optimized by the k-means++ clustering algorithm. At the transmitter, we implement the CE coding to encode the source information. Then the variable-length codeword of the CE coding is transformed into a fixed-length codeword by the multiple-rate generalized RS encoding and superimposed with a class label for transmission. At the receiver, parallel LC-OSD is performed to recover the source. Simulation results demonstrate that the proposed JSCC scheme outperforms the double polar JSCC scheme (exhibiting a coding gain of up to 1.4 dB) and the JSCC scheme based on polarizing matrix extension (exhibiting a coding gain of up to 0.6 dB), as predicted by Gallager’s JSCC bound.

This paper is concerned with a guessing codeword decoding (GCD) of linear block codes, which is optimal and typically requires a fewer number of searches than the naive exhaustive search decoding (ESD). Compared with the guessing random additive noise decoding (GRAND), which is only efficient for high-rate codes, the GCD is efficient for not only high-rate codes but also low-rate codes. We prove that the GCD typically requires a fewer number of queries than the GRAND. Compared with the conventional ordered statistics decoding (OSD), the GCD does not require the online Gaussian elimination (GE). In addition to limiting the maximum number of searches, we suggest limiting the radius of searches in terms of soft weights or tolerated performance loss to further reduce the decoding complexity, resulting in the so-called truncated GCD. The performance gap between the truncated GCD and the optimal decoding can be upper bounded approximately by the saddlepoint approach or other numerical approaches. The derived upper bound captures the relationship between the performance and the decoding parameters, enabling us to balance the performance and the complexity by optimizing the decoding parameters of the truncated GCD. We also introduce a parallel implementation of the (truncated) GCD algorithm to reduce decoding latency without compromising performance. Another contribution of this paper is the application of the GCD to the polar codes. We propose a multiple-bit-wise decoding algorithm over a pruned tree for the polar codes, referred to as the successive-cancellation list (SCL) decoding algorithm by GCD. First, we present a strategy for pruning the conventional polar decoding tree based on the complexity analysis rather than the specific bit patterns. Then we apply the GCD algorithm in parallel aided by the early stopping criteria to the leaves of the pruned tree. Simulation results show that, without any performance loss as justified by analysis, the proposed decoding algorithm can significantly reduce the decoding latency of the polar codes.

In cross-silo federated learning (FL), clients of common interest cooperatively train a global model without sharing local sensitive data, but they still face potential privacy leakage due to privacy threats from malicious attackers. Although some articles have proposed effective privacy-preserving mechanisms for FL (such as differential privacy (DP)), clients in cross-silo FL are usually different companies or organizations who may behave selfishly to optimize their own benefits. In this article, we study DP-based cross-silo FL where clients selfishly decide their participation levels (i.e., data sizes for model trainings) and privacy leakage tolerance levels to trade off between model accuracy loss and privacy loss, and we model clients’ interactions as a participation-dependent privacy preservation game. It is challenging to analyze the game since the comprehensive impact of participation levels and privacy leakage tolerance levels on model accuracy is unclear and the behaviors of heterogeneous clients are coupled in a highly complex manner. To capture the impact of participation and privacy preservation behaviors, we first characterize the optimality gap of DP-based cross-silo FL for both convex and non-convex models, where the privacy leakage tolerance levels and the participation levels are coupled nonlinearly. We model clients’ costs based on the optimality gap, and prove that clients’ selfish participation-dependent privacy preservation game is a potential game. To analyze the optimal strategies of heterogeneous clients in a stable state, we derive the closed-form expression for the unique Nash equilibrium (NE), where clients may choose full participation or partial participation, and the equilibrium privacy preservation strategy depends on clients’ accuracy-privacy preference ratios. We analyze the social efficiency of the NE by calculating the price of anarchy (PoA) and show that the PoA increases with the number of clients and the heterogeneity of clients’ model accuracy preferences. To improve the social efficiency achieved at equilibrium, we design a socially efficient incentive mechanism that allows clients with large model accuracy preferences to compensate clients with small model accuracy preferences. Extensive experiments verify our theoretical results for both the convex and non-convex models as well as both the i.i.d. data distribution case and the non-i.i.d. data distribution case.

This paper is concerned with the SCL-GCD algorithm of polar codes, which performs the successive-cancellation list (SCL) decoding algorithm for a lower rate sub-code and the guessing codeword decoding (GCD) algorithm for a higher rate sub-code. We propose to implement the GCD algorithm in a parallel way and design early stopping criteria for reducing complexity and decoding latency without sacrificing performance. Numerical results show that, when compared with the original SCL decoding algorithm, the SCL-GCD algorithm armed with the proposed early stopping criteria has lower computational complexity and decoding latency in the high signal-noise ratio (SNR) region.

In this paper, we propose an approach to construction of polar codes for successive cancellation list (SCL) decoding with a preset list size. For a given code length, we construct a trellis through which a path corresponds to a polar code. Then, we employ a sequential search algorithm to find an expected path based on four path metrics and five path selection rules. Additionally, for polarization-adjusted convolutional (PAC) construction, we optimize the convolutional generator polynomial based on our constructed polar code. Numerical results show that our polar/PAC codes can achieve satisfactory performance.

We propose quasi ordered statistic decoding (quasi-OSD) of binary image of Reed-Solomon (RS) codes and explore the application of RS codes to joint source-channel coding (JSCC). Unlike the conventional OSD algorithms that use Gaussian elimination to obtain the systematic matrix, the proposed quasi-OSD algorithm utilizes the parallel Lagrange interpolation at the symbol level, which achieves a lower complexity and comparable performance compared with the locally constrained OSD (LC-OSD), for high-rate RS codes in the high signal-to-noise ratio (SNR) region. Additionally, we apply RS codes to the JSCC with known source statistics. At the transmitter, a new partition criterion is introduced in the classified enumerative (CE) coding to encode the source information. Then the multiple-rate RS coding transforms the variable-length codeword of the CE coding into a fixed-length transmitted codeword. At the receiver, parallel decoding is performed to recover the source. Simulation results demonstrate that the proposed JSCC scheme outperforms the double polar JSCC scheme by one dB, as expected by Gallager's JSCC bound.

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.