اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدList Decoding of Direct Sum Codes
73
0
0.0
(
0
)
نشر من قبل
Fernando Granha Jeronimo
تاريخ النشر
2020
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We consider families of codes obtained by lifting a base code $mathcal{C}$ through operations such as $k$-XOR applied to local views of codewords of $mathcal{C}$, according to a suitable $k$-uniform hypergraph. The $k$-XOR operation yields the direct sum encoding used in works of [Ta-Shma, STOC 2017] and [Dinur and Kaufman, FOCS 2017]. We give a general framework for list decoding such lifted codes, as long as the base code admits a unique decoding algorithm, and the hypergraph used for lifting satisfies certain expansion properties. We show that these properties are satisfied by the collection of length $k$ walks on an expander graph, and by hypergraphs corresponding to high-dimensional expanders. Instantiating our framework, we obtain list decoding algorithms for direct sum liftings on the above hypergraph families. Using known connections between direct sum and direct product, we also recover the recent results of Dinur et al. [SODA 2019] on list decoding for direct product liftings. Our framework relies on relaxations given by the Sum-of-Squares (SOS) SDP hierarchy for solving various constraint satisfaction problems (CSPs). We view the problem of recovering the closest codeword to a given word, as finding the optimal solution of a CSP. Constraints in the instance correspond to edges of the lifting hypergraph, and the solutions are restricted to lie in the base code $mathcal{C}$. We show that recent algorithms for (approximately) solving CSPs on certain expanding hypergraphs also yield a decoding algorithm for such lifted codes. We extend the framework to list decoding, by requiring the SOS solution to minimize a convex proxy for negative entropy. We show that this ensures a covering property for the SOS solution, and the condition and round approach used in several SOS algorithms can then be used to recover the required list of codewords.
قيم البحث
اقرأ أيضاً
The Gilbert-Varshamov bound (non-constructively) establishes the existence of binary codes of distance $1/2 -epsilon$ and rate $Omega(epsilon^2)$ (where an upper bound of $O(epsilon^2log(1/epsilon))$ is known). Ta-Shma [STOC 2017] gave an explicit co
nstruction of $epsilon$-balanced binary codes, where any two distinct codewords are at a distance between $1/2 -epsilon/2$ and $1/2+epsilon/2$, achieving a near optimal rate of $Omega(epsilon^{2+beta})$, where $beta to 0$ as $epsilon to 0$. We develop unique and list decoding algorithms for (essentially) the family of codes constructed by Ta-Shma. We prove the following results for $epsilon$-balanced codes with block length $N$ and rate $Omega(epsilon^{2+beta})$ in this family: - For all $epsilon, beta > 0$ there are explicit codes which can be uniquely decoded up to an error of half the minimum distance in time $N^{O_{epsilon, beta}(1)}$. - For any fixed constant $beta$ independent of $epsilon$, there is an explicit construction of codes which can be uniquely decoded up to an error of half the minimum distance in time $(log(1/epsilon))^{O(1)} cdot N^{O_beta(1)}$. - For any $epsilon > 0$, there are explicit $epsilon$-balanced codes with rate $Omega(epsilon^{2+beta})$ which can be list decoded up to error $1/2 - epsilon$ in time $N^{O_{epsilon,epsilon,beta}(1)}$, where $epsilon, beta to 0$ as $epsilon to 0$. The starting point of our algorithms is the list decoding framework from Alev et al. [SODA 2020], which uses the Sum-of-Squares SDP hierarchy. The rates obtained there were quasipolynomial in $epsilon$. Here, we show how to overcome the far from optimal rates of this framework obtaining unique decoding algorithms for explicit binary codes of near optimal rate. These codes are based on simple modifications of Ta-Shmas construction.
Power decoding is a partial decoding paradigm for arbitrary algebraic geometry codes for decoding beyond half the minimum distance, which usually returns the unique closest codeword, but in rare cases fails to return anything. The original version de
codes roughly up to the Sudan radius, while an improved version decodes up to the Johnson radius, but has so far been described only for Reed--Solomon and one-point Hermitian codes. In this paper we show how the improved version can be applied to any algebraic geometry code.
As the first error correction codes provably achieving the symmetric capacity of binary-input discrete memory-less channels (B-DMCs), polar codes have been recently chosen by 3GPP for eMBB control channel. Among existing algorithms, CRC-aided success
ive cancellation list (CA-SCL) decoding is favorable due to its good performance, where CRC is placed at the end of the decoding and helps to eliminate the invalid candidates before final selection. However, the good performance is obtained with a complexity increase that is linear in list size $L$. In this paper, the tailored CRC-aided SCL (TCA-SCL) decoding is proposed to balance performance and complexity. Analysis on how to choose the proper CRC for a given segment is proposed with the help of emph{virtual transform} and emph{virtual length}. For further performance improvement, hybrid automatic repeat request (HARQ) scheme is incorporated. Numerical results have shown that, with the similar complexity as the state-of-the-art, the proposed TCA-SCL and HARQ-TCA-SCL schemes achieve $0.1$ dB and $0.25$ dB performance gain at frame error rate $textrm{FER}=10^{-2}$, respectively. Finally, an efficient TCA-SCL decoder is implemented with FPGA demonstrating its advantages over CA-SCL decoder.
This article discusses the decoding of Gabidulin codes and shows how to extend the usual decoder to any supercode of a Gabidulin code at the cost of a significant decrease of the decoding radius. Using this decoder, we provide polynomial time attacks
on the rank-metric encryption schemes RAMESSES and LIGA.
Turbo codes and CRC codes are usually decoded separately according to the serially concatenated inner codes and outer codes respectively. In this letter, we propose a hybrid decoding algorithm of turbo-CRC codes, where the outer codes, CRC codes, are
not used for error detection but as an assistance to improve the error correction performance. Two independent iterative decoding and reliability based decoding are carried out in a hybrid schedule, which can efficiently decode the two different codes as an entire codeword. By introducing an efficient error detecting method based on normalized Euclidean distance without CRC check, significant gain can be obtained by using the hybrid decoding method without loss of the error detection ability.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
