اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدDecoding of Projective Reed-Muller Codes by Dividing a Projective Space into Affine Spaces
158
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A projective Reed-Muller (PRM) code, obtained by modifying a (classical) Reed-Muller code with respect to a projective space, is a doubly extended Reed-Solomon code when the dimension of the related projective space is equal to 1. The minimum distance and dual code of a PRM code are known, and some decoding examples have been represented for low-dimensional projective space. In this study, we construct a decoding algorithm for all PRM codes by dividing a projective space into a union of affine spaces. In addition, we determine the computational complexity and the number of errors correctable of our algorithm. Finally, we compare the codeword error rate of our algorithm with that of minimum distance decoding.
قيم البحث
اقرأ أيضاً
The notion of a Private Information Retrieval (PIR) code was recently introduced by Fazeli, Vardy and Yaakobi who showed that this class of codes permit PIR at reduced levels of storage overhead in comparison with replicated-server PIR. In the presen
t paper, the construction of an $(n,k)$ $tau$-server binary, linear PIR code having parameters $n = sumlimits_{i = 0}^{ell} {m choose i}$, $k = {m choose ell}$ and $tau = 2^{ell}$ is presented. These codes are obtained through homogeneous-polynomial evaluation and correspond to the binary, Projective Reed Muller (PRM) code. The construction can be extended to yield PIR codes for any $tau$ of the form $2^{ell}$, $2^{ell}-1$ and any value of $k$, through a combination of single-symbol puncturing and shortening of the PRM code. Each of these code constructions above, have smaller storage overhead in comparison with other PIR codes appearing in the literature. For the particular case of $tau=3,4$, we show that the codes constructed here are optimal, systematic PIR codes by providing an improved lower bound on the block length $n(k, tau)$ of a systematic PIR code. It follows from a result by Vardy and Yaakobi, that these codes also yield optimal, systematic primitive multi-set $(n, k, tau)_B$ batch codes for $tau=3,4$. The PIR code constructions presented here also yield upper bounds on the generalized Hamming weights of binary PRM codes.
Projective Reed-Muller codes were introduced by Lachaud, in 1988 and their dimension and minimum distance were determined by Serre and S{o}rensen in 1991. In coding theory one is also interested in the higher Hamming weights, to study the code perfor
mance. Yet, not many values of the higher Hamming weights are known for these codes, not even the second lowest weight (also known as next-to-minimal weight) is completely determined. In this paper we determine all the values of the next-to-minimal weight for the binary projective Reed-Muller codes, which we show to be equal to the next-to-minimal weight of Reed-Muller codes in most, but not all, cases.
In this paper we present several values for the next-to-minimal weights of projective Reed-Muller codes. We work over $mathbb{F}_q$ with $q geq 3$ since in IEEE-IT 62(11) p. 6300-6303 (2016) we have determined the complete values for the next-to-mini
mal weights of binary projective Reed-Muller codes. As in loc. cit. here we also find examples of codewords with next-to-minimal weight whose set of zeros is not in a hyperplane arrangement.
This paper presents a novel successive factor-graph permutation (SFP) scheme that significantly improves the error-correction performance of Reed-Muller (RM) codes under successive-cancellation list (SCL) decoding. In particular, we perform maximum-l
ikelihood decoding on the symmetry group of RM codes to carefully select a good factor-graph permutation on the fly. We further propose an SFP-aided fast SCL decoding that significantly reduces the decoding latency while preserving the error-correction performance of the code. The simulation results show that for the third and fourth order RM codes of length $256$, the proposed decoder reduces up to $85%$ of the memory consumption, $78%$ of the decoding latency, and more than $99%$ of the computational complexity of the state-of-the-art recursive projection-aggregation decoder at the frame error rate of $10^{-3}$.
A low-complexity tree search approach is presented that achieves the maximum-likelihood (ML) decoding performance of Reed-Muller (RM) codes. The proposed approach generates a bit-flipping tree that is traversed to find the ML decoding result by perfo
rming successive-cancellation decoding after each node visit. A depth-first search (DFS) and a breadth-first search (BFS) scheme are developed and a log-likelihood-ratio-based bit-flipping metric is utilized to avoid redundant node visits in the tree. Several enhancements to the proposed algorithm are presented to further reduce the number of node visits. Simulation results confirm that the BFS scheme provides a lower average number of node visits than the existing tree search approach to decode RM codes.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
