More Like this

1. Decoder Error Propagation Mitigation for Spatially Coupled LDPC Codes

   Zhu, Min; Mitchell, D; Lentmaier, M; Costello, D (March 2021, International Symposium on Information Theory and its Applications)

   In this paper, we introduce two new methods of mitigating decoder error propagation for low-latency sliding window decoding (SWD) of spatially coupled low-density parity-check (SC-LDPC) codes. Building on the recently introduced idea of check node (CN) doping of regular SC-LDPC codes, here we employ variable node (VN) doping to fix (set to a known value) a subset of variable nodes in the coupling chain. Both of these doping methods have the effect of allowing SWD to recover from error propagation, at a cost of a slight rate loss. Experimental results show that, similar to CN doping, VN doping improves performance by up to two orders of magnitude compared to un-doped SC-LDPC codes in the typical signal-to-noise ratio operating range. Further, compared to CN doping, VN doping has the advantage of not requiring any changes to the decoding process. In addition, a log-likelihood-ratio based window extension algorithm is proposed to reduce the effect of error propagation. Using this approach, we show that decoding latency can be reduced by up to a significant fraction without suffering any loss in performance. 

   more » « less
2. Decoder Error Propagation Mitigation for Spatially Coupled LDPC Codes

   Zhu, M; Mitchell, D; Lentmaier, M; Costello, D (October 2020, Proc. International Symposium on Information Theory and Its Applications)

   null (Ed.)

   In this paper, we introduce two new methods of mitigating decoder error propagation for low-latency sliding window decoding (SWD) of spatially coupled low density parity check (SC-LDPC) codes. Building on the recently introduced idea of check node (CN) doping of regular SC-LDPC codes, here we employ variable node (VN) doping to fix (set to a known value) a subset of variable nodes in the coupling chain. Both of these doping methods have the effect of allowing SWD to recover from error propagation, at a cost of a slight rate loss. Experimental results show that, similar to CN doping, VN doping improves performance by up to two orders of magnitude compared to undoped SC-LDPC codes in the typical signal-to-noise ratio operating range. Further, compared to CN doping, VN doping has the advantage of not requiring any changes to the decoding process.In addition, a log-likelihood-ratio based window extension algorithm is proposed to reduce the effect of error propagation. Using this approach, we show that decoding latency can be reduced by up to a significant fraction without suffering any loss in performance 

   more » « less
3. On guaranteed correction of error patterns with artificial neural networks

   Ivaniš, P; Brkic, S.; Vasić, B. (July 2022, Telfor Journal)

   In this paper, we analyze applicability of singleand two-hidden-layer feed-forward artificial neural networks, SLFNs and TLFNs, respectively, in decoding linear block codes. Based on the provable capability of SLFNs and TLFNs to approximate discrete functions, we discuss sizes of the network capable to perform maximum likelihood decoding. Furthermore, we propose a decoding scheme, which use artificial neural networks (ANNs) to lower the error-floors of low-density parity-check (LDPC) codes. By learning a small number of error patterns, uncorrectable with typical decoders of LDPC codes, ANN can lower the error-floor by an order of magnitude, with only marginal average complexity incense. 

   more » « less
4. Polar Codes with Local-Global Decoding

   Zhu, Ziyuan; Wu, Wei; Siegel, Paul H. (March 2023, Proceedings of 14th Annual Non-Volatile Memories Workshop)

   Error correction coding schemes with local-global decoding are motivated by practical data storage applications where a balance must be achieved between low latency read access and high data reliability. As an example, consider a 4KB codeword, consisting of four 1KB subblocks, that supports a local-global decoding architecture. Local decoding can provide reliable, low-latency access to individual 1KB subblocks under good channel conditions, while global decoding can provide a “safety-net” for recovery of the entire 4KB block when local decoding fails under bad channel conditions. Recently, Ram and Cassuto have proposed such local-global decoding architectures for LDPC codes and spatially coupled LDPC codes. In this paper, we investigate a coupled polar code architecture that supports both local and global decoding. The coupling scheme incorporates a systematic outer polar code and a partitioned mapping of the outer codeword to semipolarized bit-channels of the inner polar codes. Error rate simulation results are presented for 2 and 4 subblocks. 

   more » « less
5. Polynomial-time Trace Reconstruction in the Smoothed Complexity Model

   https://doi.org/10.1145/3560819  

   Chen, Xi; De, Anindya; Lee, Chin Ho; Servedio, Rocco; Sinha, Sandip (July 2025, ACM Transactions on Algorithms)

   In thetrace reconstruction problem, an unknown source stringx∈ {0,1}ⁿis sent through a probabilisticdeletion channelthat independently deletes each bit with probability δ and concatenates the surviving bits, yielding atraceofx. The problem is to reconstructxgiven independent traces. This problem has received much attention in recent years both in the worst-case setting wherexmay be an arbitrary string in {0,1}ⁿ[7,8,10,11,12,23] and in the average-case setting wherexis drawn uniformly at random from {0,1}ⁿ[7,8,12,13,25]. This article studies trace reconstruction in thesmoothed analysissetting, in which a “worst-case” stringx^worstis chosen arbitrarily from {0,1}ⁿ, and then a perturbed versionxofx^worstis formed by independently replacing each coordinate by a uniform random bit with probability σ. The problem is to reconstructxgiven independent traces from it. Our main result is an algorithm that, for any constant perturbation rate 0< σ < 1 and any constant deletion rate 0 < δ < 1, uses poly(n) running time and traces and succeeds with high probability in reconstructing the stringx. This stands in contrast with the worst-case version of the problem, for which\(\text{exp}(\tilde{O}(n^{1/5}))\)is the best known time and sample complexity [8]. Our approach is based on reconstructingxfrom the multiset of its short subwords and is quite different from previous algorithms for either the worst-case or average-case versions of the problem. The heart of our work is a new poly(n)-time procedure for reconstructing the multiset of allO(logn)-length subwords of any source stringx∈ {0,1}ⁿgiven access to traces ofx. 

   more » « less