More Like this

1. ELF Codes: Concatenated Codes with an Expurgating Linear Function as the Outer Code

   https://doi.org/10.1109/ISTC57237.2023.10273535  

   Wesel, R.; Antonini, A.; Wang, L.; Sui, W.; Towell, B.; Grissett, H. (September 2023, IEEE)

   An expurgating linear function (ELF) is an outer code that disallows low-weight codewords of the inner code. ELFs can be designed either to maximize the minimum distance or to minimize the codeword error rate (CER) of the expurgated code. A list-decoding sieve can efficiently identify ELFs that maximize the minimum distance of the expurgated code. For convolutional inner codes, this paper provides analytical distance spectrum union (DSU) bounds on the CER of the concatenated code. For short codeword lengths, ELFs transform a good inner code into a great concatenated code. For a constant message size of K = 64 bits or constant codeword blocklength of N = 152 bits, an ELF can reduce the gap at CER 10−6 between the DSU and the random-coding union (RCU) bounds from over 1 dB for the inner code alone to 0.23 dB for the concatenated code. The DSU bounds can also characterize puncturing that mitigates the rate overhead of the ELF while maintaining the DSU-to-RCU gap. List Viterbi decoding guided by the ELF achieves maximum likelihood (ML) decoding of the concatenated code with a sufficiently large list size. The rate-K/(K+m) ELF outer code reduces rate and list decoding increases decoder complexity. As SNR increases, the average list size converges to 1 and average complexity is similar to Viterbi decoding on the trellis of the inner code. For rare large-magnitude noise events, which occur less often than the FER of the inner code, a deep search in the list finds the ML codeword. 

   more » « less
2. On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors

   https://doi.org/10.4230/LIPIcs.CCC.2023.14  

   Block, Alexander R.; Blocki, Jeremiah; Cheng, Kuan; Grigorescu, Elena; Li, Xin; Zheng, Yu; Zhu, Minshen (January 2023, 38th Computational Complexity Conference (CCC 2023))

   Ta-Shma, Amnon (Ed.)

   Locally Decodable Codes (LDCs) are error-correcting codes C:Σⁿ → Σ^m, encoding messages in Σⁿ to codewords in Σ^m, with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length m that is super-polynomial in n, for codes with constant query complexity and constant alphabet size. In a very surprising result, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (SICOMP 2006) show how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and almost linear codeword length over the binary alphabet, and used them to obtain significantly-improved constructions of Probabilistically Checkable Proofs. In this work, we study RLDCs in the standard Hamming-error setting, and introduce their variants in the insertion and deletion (Insdel) error setting. Standard LDCs for Insdel errors were first studied by Ostrovsky and Paskin-Cherniavsky (Information Theoretic Security, 2015), and are further motivated by recent advances in DNA random access bio-technologies. Our first result is an exponential lower bound on the length of Hamming RLDCs making 2 queries (even adaptively), over the binary alphabet. This answers a question explicitly raised by Gur and Lachish (SICOMP 2021) and is the first exponential lower bound for RLDCs. Combined with the results of Ben-Sasson et al., our result exhibits a "phase-transition"-type behavior on the codeword length for some constant-query complexity. We achieve these lower bounds via a transformation of RLDCs to standard Hamming LDCs, using a careful analysis of restrictions of message bits that fix codeword bits. We further define two variants of RLDCs in the Insdel-error setting, a weak and a strong version. On the one hand, we construct weak Insdel RLDCs with almost linear codeword length and constant query complexity, matching the parameters of the Hamming variants. On the other hand, we prove exponential lower bounds for strong Insdel RLDCs. These results demonstrate that, while these variants are equivalent in the Hamming setting, they are significantly different in the insdel setting. Our results also prove a strict separation between Hamming RLDCs and Insdel RLDCs. 

   more » « less
3. Efficient Nested Key Equation Solver for Short Generalized Integrated Interleaved BCH Codes

   Zhenshan Xie and Xinmiao Zhang (May 2022, Proceedings IEEE International Symposium on Circuits and Systems)

   Generalized integrated interleaved (GII) codes can nest BCH sub-codewords to form stronger BCH codewords. They are among the best candidates for error correction in the new storage class memories (SCMs). However, SCMs require short codeword length and low redundancy. In this case, the nested key equation solver (KES), which is a key step in GII decoding, has a small number of iterations. The initialization and/or scalar pre-computation in previous nested KES designs have large area and may take even longer time than the iterations themselves. This paper proposes an efficient nested KES design for short GII-BCH codes. The polynomial updating is decomposed into two steps to reduce the critical path without requiring scalar pre-computation. Besides, the KES is reformulated to reduce the number of clock cycles without incurring any area overhead. For an example code over GF(2^{10}) that protects 2560 bits with 10% redundancy, the proposed design achieves at least 25% area reduction and 37% reduction on the area-time product averaged over the nested decoding rounds compared to prior efforts. 

   more » « less
4. CRC-Aided List Decoding of Convolutional and Polar Codes for Short Messages in 5G

   https://doi.org/10.1109/ICC45855.2022.9838726  

   King, J.; Kwon, A.; Yang, H.; Ryan, W.; Wesel, R. D. (May 2022, 2022 International Conference on Communications)

   This paper explores list decoding of convolutional and polar codes for short messages such as those found in the 5G physical broadcast channel. A cyclic redundancy check (CRC) is used to select a codeword from a list of likely codewords. One example in the 5G standard encodes a 32-bit message with a 24-bit CRC and a 512-bit polar code with additional bits added by repetition to achieve a very low rate of 32/864. This paper shows that optimizing the CRC length improves the Eb/N0 performance of this polar code, where Eb/N0 is the ratio of the energy per data bit to the noise power spectral density. Furthermore, even better Eb/N0 performance is achieved by replacing the polar code with a tail-biting convolutional code (TBCC) with a distance-spectrum-optimal (DSO) CRC. This paper identifies the optimal CRC length to minimize the frame error rate (FER) of a rate-1/5 TBCC at a specific value of Eb/N0. We also show that this optimized TBCC/CRC can attain the same excellent Eb/N0 performance with the very low rate of 32/864 of the 5G polar code, where the low rate is achieved through repetition. We show that the proposed TBCC/CRC concatenated code outperforms the PBCH polar code described in the 5G standard both in terms of FER and decoding run time. We also explore the tradeoff between undetected error rate and erasure rate as the CRC size varies. 

   more » « less
5. Belief propagation with quantum messages for quantum-enhanced classical communications

   https://doi.org/10.1038/s41534-021-00422-1  

   Rengaswamy, Narayanan; Seshadreesan, Kaushik P.; Guha, Saikat; Pfister, Henry D. (June 2021, npj Quantum Information)

   Abstract For space-based laser communications, when the mean photon number per received optical pulse is much smaller than one, there is a large gap between communications capacity achievable with a receiver that performs individual pulse-by-pulse detection, and the quantum-optimal “joint-detection receiver” that acts collectively on long codeword-blocks of modulated pulses; an effect often termed “superadditive capacity”. In this paper, we consider the simplest scenario where a large superadditive capacity is known: a pure-loss channel with a coherent-state binary phase-shift keyed (BPSK) modulation. The two BPSK states can be mapped conceptually to two non-orthogonal states of a qubit, described by an inner product that is a function of the mean photon number per pulse. Using this map, we derive an explicit construction of the quantum circuit of a joint-detection receiver based on a recent idea of “belief-propagation with quantum messages” (BPQM). We quantify its performance improvement over the Dolinar receiver that performs optimal pulse-by-pulse detection, which represents the best “classical” approach. We analyze the scheme rigorously and show that it achieves the quantum limit of minimum average error probability in discriminating 8 (BPSK) codewords of a length-5 binary linear code with a tree factor graph. Our result suggests that a BPQM receiver might attain the Holevo capacity of this BPSK-modulated pure-loss channel. Moreover, our receiver circuit provides an alternative proposal for a quantum supremacy experiment, targeted at a specific application that can potentially be implemented on a small, special-purpose, photonic quantum computer capable of performing cat-basis universal qubit logic. 

   more » « less