اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLinear hash-functions and their applications to error detection and correction
156
0
0.0
(
0
)
تأليف
Boris Ryabko
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We describe and explore so-called linear hash functions and show how they can be used to build error detection and correction codes. The method can be applied for different types of errors (for example, burst errors). When the method is applied to a model where number of distorted letters is limited, the obtained estimate of its performance is slightly better than the known Varshamov-Gilbert bound. We also describe random code whose performance is close to the same boundary, but its construction is much simpler. In some cases the obtained methods are simpler and more flexible than the known ones. In particular, the complexity of the obtained error detection code and the well-known CRC code is close, but the proposed code, unlike CRC, can detect with certainty errors whose number does not exceed a predetermined limit.
قيم البحث
اقرأ أيضاً
Motivated by mutation processes occurring in in-vivo DNA-storage applications, a channel that mutates stored strings by duplicating substrings as well as substituting symbols is studied. Two models of such a channel are considered: one in which the s
ubstitutions occur only within the duplicated substrings, and one in which the location of substitutions is unrestricted. Both error-detecting and error-correcting codes are constructed, which can handle correctly any number of tandem duplications of a fixed length $k$, and at most a single substitution occurring at any time during the mutation process.
We consider linear network error correction (LNEC) coding when errors may occur on edges of a communication network of which the topology is known. In this paper, we first revisit and explore the framework of LNEC coding, and then unify two well-know
n LNEC coding approaches. Furthermore, by developing a graph-theoretic approach to the framework of LNEC coding, we obtain a significantly enhanced characterization of the error correction capability of LNEC codes in terms of the minimum distances at the sink nodes. In LNEC coding, the minimum required field size for the existence of LNEC codes, in particular LNEC maximum distance separable (MDS) codes which are a type of most important optimal codes, is an open problem not only of theoretical interest but also of practical importance, because it is closely related to the implementation of the coding scheme in terms of computational complexity and storage requirement. By applying the graph-theoretic approach, we obtain an improved upper bound on the minimum required field size. The improvement over the existing results is in general significant. The improved upper bound, which is graph-theoretic, depends only on the network topology and requirement of the error correction capability but not on a specific code construction. However, this bound is not given in an explicit form. We thus develop an efficient algorithm that can compute the bound in linear time. In developing the upper bound and the efficient algorithm for computing this bound, various graph-theoretic concepts are introduced. These concepts appear to be of fundamental interest in graph theory and they may have further applications in graph theory and beyond.
In this paper, a linear $ell$-intersection pair of codes is introduced as a generalization of linear complementary pairs of codes. Two linear codes are said to be a linear $ell$-intersection pair if their intersection has dimension $ell$. Charact
erizations and constructions of such pairs of codes are given in terms of the corresponding generator and parity-check matrices. Linear $ell$-intersection pairs of MDS codes over $mathbb{F}_q$ of length up to $q+1$ are given for all possible parameters. As an application, linear $ell$-intersection pairs of codes are used to construct entanglement-assisted quantum error correcting codes. This provides a large number of new MDS entanglement-assisted quantum error correcting codes.
In this work we establish some new interleavers based on permutation functions. The inverses of these interleavers are known over a finite field $mathbb{F}_q$. For the first time M{o}bius and Redei functions are used to give new deterministic interle
avers. Furthermore we employ Skolem sequences in order to find new interleavers with known cycle structure. In the case of Redei functions an exact formula for the inverse function is derived. The cycle structure of Redei functions is also investigated. The self-inverse and non-self-inver
In this paper, we construct several classes of maximum distance separable (MDS) codes via generalized Reed-Solomon (GRS) codes and extended GRS codes, where we can determine the dimensions of their Euclidean hulls or Hermitian hulls. It turns out tha
t the dimensions of Euclidean hulls or Hermitian hulls of the codes in our constructions can take all or almost all possible values. As a consequence, we can apply our results to entanglement-assisted quantum error-correcting codes (EAQECCs) and obtain several new families of MDS EAQECCs with flexible parameters. The required number of maximally entangled states of these MDS EAQECCs can take all or almost all possible values. Moreover, several new classes of q-ary MDS EAQECCs of length n > q + 1 are also obtained.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
