Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEfficient data compression from statistical physics of codes over finite fields
148
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper we discuss a novel data compression technique for binary symmetric sources based on the cavity method over a Galois Field of order q (GF(q)). We present a scheme of low complexity and near optimal empirical performance. The compression step is based on a reduction of sparse low density parity check codes over GF(q) and is done through the so called reinforced belief-propagation equations. These reduced codes appear to have a non-trivial geometrical modification of the space of codewords which makes such compression computationally feasible. The computational complexity is O(d.n.q.log(q)) per iteration, where d is the average degree of the check nodes and n is the number of bits. For our code ensemble, decompression can be done in a time linear in the codes length by a simple leaf-removal algorithm.
rate research
Read More
Reed-Muller codes are some of the oldest and most widely studied error-correcting codes, of interest for both their algebraic structure as well as their many algorithmic properties. A recent beautiful result of Saptharishi, Shpilka and Volk showed that for binary Reed-Muller codes of length $n$ and distance $d = O(1)$, one can correct $operatorname{polylog}(n)$ random errors in $operatorname{poly}(n)$ time (which is well beyond the worst-case error tolerance of $O(1)$). In this paper, we consider the problem of `syndrome decoding Reed-Muller codes from random errors. More specifically, given the $operatorname{polylog}(n)$-bit long syndrome vector of a codeword corrupted in $operatorname{polylog}(n)$ random coordinates, we would like to compute the locations of the codeword corruptions. This problem turns out to be equivalent to a basic question about computing tensor decomposition of random low-rank tensors over finite fields. Our main result is that syndrome decoding of Reed-Muller codes (and the equivalent tensor decomposition problem) can be solved efficiently, i.e., in $operatorname{polylog}(n)$ time. We give two algorithms for this problem: 1. The first algorithm is a finite field variant of a classical algorithm for tensor decomposition over real numbers due to Jennrich. This also gives an alternate proof for the main result of Saptharishi et al. 2. The second algorithm is obtained by implementing the steps of the Berlekamp-Welch-style decoding algorithm of Saptharishi et al. in sublinear-time. The main new ingredient is an algorithm for solving certain kinds of systems of polynomial equations.
In this paper, we present three new classes of $q$-ary quantum MDS codes utilizing generalized Reed-Solomon codes satisfying Hermitian self-orthogonal property. Among our constructions, the minimum distance of some $q$-ary quantum MDS codes can be bigger than $frac{q}{2}+1$. Comparing to previous known constructions, the lengths of codes in our constructions are more flexible.
This paper considers the construction of isodual quasi-cyclic codes. First we prove that two quasi-cyclic codes are permutation equivalent if and only if their constituent codes are equivalent. This gives conditions on the existence of isodual quasi-cyclic codes. Then these conditions are used to obtain isodual quasi-cyclic codes. We also provide a construction for isodual quasi-cyclic codes as the matrix product of isodual codes.
In this paper, we show that LCD codes are not equivalent to linear codes over small finite fields. The enumeration of binary optimal LCD codes is obtained. We also get the exact value of LD$(n,2)$ over $mathbb{F}_3$ and $mathbb{F}_4$. We study the bound of LCD codes over $mathbb{F}_q$.
Professor Cunsheng Ding gave cyclotomic constructions of cyclic codes with length being the product of two primes. In this paper, we study the cyclic codes of length $n=2^e$ and dimension $k=2^{e-1}$. Clearly, Dings construction is not hold in this place. We describe two new types of generalized cyclotomy of order two, which are different from Dings. Furthermore, we study two classes of cyclic codes of length $n$ and dimension $k$. We get the enumeration of these cyclic codes. Whats more, all of the codes from our construction are among the best cyclic codes. Furthermore, we study the hull of cyclic codes of length $n$ over $mathbb{F}_q$. We obtain the range of $ell=dim({rm Hull}(C))$. We construct and enumerate cyclic codes of length $n$ having hull of given dimension.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
