اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدConstructing Linear Codes with Good Joint Spectra
105
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The problem of finding good linear codes for joint source-channel coding (JSCC) is investigated in this paper. By the code-spectrum approach, it has been proved in the authors previous paper that a good linear code for the authors JSCC scheme is a code with a good joint spectrum, so the main task in this paper is to construct linear codes with good joint spectra. First, the code-spectrum approach is developed further to facilitate the calculation of spectra. Second, some general principles for constructing good linear codes are presented. Finally, we propose an explicit construction of linear codes with good joint spectra based on low density parity check (LDPC) codes and low density generator matrix (LDGM) codes.
قيم البحث
اقرأ أيضاً
One of the most important and challenging problems in coding theory is to construct codes with best possible parameters and properties. The class of quasi-cyclic (QC) codes is known to be fertile to produce such codes. Focusing on QC codes over the b
inary field, we have found 113 binary QC codes that are new among the class of QC codes using an implementation of a fast cyclic partitioning algorithm and the highly effective ASR algorithm. Moreover, these codes have the following additional properties: a) they have the same parameters as best known linear codes, and b) many of the have additional desired properties such as being reversible, LCD, self-orthogonal or dual-containing. Additionally, we present an algorithm for the generation of new codes from QC codes using ConstructionX, and introduce 35 new record breaking linear codes produced from this method.
A long standing problem in the area of error correcting codes asks whether there exist good cyclic codes. Most of the known results point in the direction of a negative answer. The uncertainty principle is a classical result of harmonic analysis as
serting that given a non-zero function $f$ on some abelian group, either $f$ or its Fourier transform $hat{f}$ has large support. In this note, we observe a connection between these two subjects. We point out that even a weak version of the uncertainty principle for fields of positive characteristic would imply that good cyclic codes do exist. We also provide some heuristic arguments supporting that this is indeed the case.
We prove that, for the binary erasure channel (BEC), the polar-coding paradigm gives rise to codes that not only approach the Shannon limit but do so under the best possible scaling of their block length as a~function of the gap to capacity. This res
ult exhibits the first known family of binary codes that attain both optimal scaling and quasi-linear complexity of encoding and decoding. Our proof is based on the construction and analysis of binary polar codes with large kernels. When communicating reliably at rates within $varepsilon > 0$ of capacity, the code length $n$ often scales as $O(1/varepsilon^{mu})$, where the constant $mu$ is called the scaling exponent. It is known that the optimal scaling exponent is $mu=2$, and it is achieved by random linear codes. The scaling exponent of conventional polar codes (based on the $2times 2$ kernel) on the BEC is $mu=3.63$. This falls far short of the optimal scaling guaranteed by random codes. Our main contribution is a rigorous proof of the following result: for the BEC, there exist $elltimesell$ binary kernels, such that polar codes constructed from these kernels achieve scaling exponent $mu(ell)$ that tends to the optimal value of $2$ as $ell$ grows. We furthermore characterize precisely how large $ell$ needs to be as a function of the gap between $mu(ell)$ and $2$. The resulting binary codes maintain the recursive structure of conventional polar codes, and thereby achieve construction complexity $O(n)$ and encoding/decoding complexity $O(nlog n)$.
In this paper motivated from subspace coding we introduce subspace-metric and subset-metric codes. These are coordinate-position independent pseudometrics and suitable for the folded codes introduced by Guruswami and Rudra. The half-Singleton upper b
ounds for linear subspace-metric and subset-metric codes are proved. Subspace distances and subset distances of codes are natural lower bounds for insdel distances of codes, and then can be used to lower bound the insertion-deletion error-correcting capabilities of codes. The problem to construct efficient insertion-deletion error-correcting codes is notorious difficult and has attracted a long-time continuous efforts. The recent breakthrough is the algorithmic construction of near-Singleton optimal rate-distance tradeoff insertion-deletion code families by B. Haeupler and A. Shahrasbi in 2017 from their synchronization string technique. However most nice codes in these recent results are not explicit though many of them can be constructed by highly efficient algorithms. Our subspace-metric and subset-metric codes can be used to construct systemic explicit well-structured insertion-deletion codes. We present some near-optimal subspace-metric and subset-metric codes from known constant dimension subspace codes. By analysing the subset distances of folded codes from evaluation codes of linear mappings, we prove that they have high subset distances and then are explicit good insertion-deletion codes
This paper studies several properties of channel codes that approach the fundamental limits of a given (discrete or Gaussian) memoryless channel with a non-vanishing probability of error. The output distribution induced by an $epsilon$-capacity-achie
ving code is shown to be close in a strong sense to the capacity achieving output distribution. Relying on the concentration of measure (isoperimetry) property enjoyed by the latter, it is shown that regular (Lipschitz) functions of channel outputs can be precisely estimated and turn out to be essentially non-random and independent of the actual code. It is also shown that the output distribution of a good code and the capacity achieving one cannot be distinguished with exponential reliability. The random process produced at the output of the channel is shown to satisfy the asymptotic equipartition property. Using related methods it is shown that quadratic forms and sums of $q$-th powers when evaluated at codewords of good AWGN codes approach the values obtained from a randomly generated Gaussian codeword.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
