Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConstructing Linear Codes with Good Joint Spectra
109
0
0.0
(
0
)
Added by
Shengtian Yang
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 binary 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 asserting 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 result 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 bounds 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-achieving 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
