14 papers · ranked by Valyu relevance
Yixin Wang, Tingting Zhu, Xiao Ma
We propose in this paper to exploit convolutional low density generator matrix (LDGM) codes for transmission of Bernoulli sources over binary-input output-symmetric (BIOS) channels. To this end, we present a new framework to prove the coding theorems for linear codes, which unifies the channel coding theorem, the…
Xiangping Zheng, Xiao Ma
In this paper, we prove that the sub-field images of generalized Reed-Solomon (RS) codes can achieve the symmetric capacity of p-ary memoryless channels. Unlike the totally random linear code ensemble, as a class of maximum distance separable (MDS) codes, the generalized RS code ensemble lacks the pair-wise…
Shuichi Hirahara, Zhenjian Lu, Mikito Nanashima
The coding theorem for Kolmogorov complexity states that any string sampled from a computable distribution has a description length close to its information content. A coding theorem for resource-bounded Kolmogorov complexity is the key to obtaining fundamental results in average-case complexity, yet whether any…
Romie Banerjee
This paper establishes a direct analogue of the classical Coding Theorem in the setting of symmetry groups. We consider computable bijections on the set of binary strings, called symmetries and define the symmetry prior of a string as the probability that a randomly chosen symmetry from a given group has the string as…
Sudan, Madhu
We survey the notion and history of error-correcting codes and the algorithms needed to make them effective in information transmission. We then give some basic as well as more modern constructions of, and algorithms for, error-correcting codes that depend on relatively simple elements of applied algebra. While the…
Roni Con, Dorsa Fathollahi, Ryan Gabrys, Mary Wootters + 1 more
'Eitan Yaakobi'] Robust Gray codes were introduced by (Lolck and Pagh, SODA 2024). Informally, a robust Gray code is a (binary) Gray code G so that, given a noisy version of the encoding G(j) of an integer j, one can recover ˆj that is close to j (with high probability over the noise). Such codes have found…
Kengo Hashimoto, Iwata Ken-ichi
The class of k-bit delay decodable codes, source codes allowing decoding delay of at most k bits for k ≥ 0, can attain a shorter average codeword length than Huffman codes. This paper discusses the general properties of the class of k-bit delay decodable codes with a finite number of code tables and proves two theorems…
Spencer Congero, K. Zeger
For any finite discrete source, the competitive advantage of prefix code C1 over prefix code C2 is the probability C1 produces a shorter codeword than C2, minus the probability C2 produces a shorter codeword than C1. For any source, a prefix code is competitively optimal if it has a nonnegative competitive advantage…
Benjamin Gunby, Xiaoyu He, Bhargav Narayanan, Sam Spiro
A family of sets A is said to be an antichain if x 6⊂ y for all distinct x, y ∈ A, and it is said to be a distance-r code if every pair of distinct elements of A has Hamming distance at least r. Here, we prove that if A ⊂ 2 [n] is both an antichain and a distance-(2r + 1) code, then |A| = Or(2nn −r−1/2 ). This result…
Alix Petit, Aida Koch, Logan Lewis, Christian Schmidt + 1 more
'Adrain Vdberg'] Abstract: given the importance of the claim, we want to start by exposing the following consideration: this claim comes out more than a year after the article "Practical applications of Set Shaping Theory in Huffman coding" which reports the program that carried out an experiment of data compression in…
Grigorescu, Elena, Kumar, Vinayak M. + 4 more
A locally decodable code (LDC) : {0, 1 } → {0, 1 } is an error-correcting code that allows one to recover any bit of the original message with good probability while only reading a small number of bits from a corrupted codeword. A relaxed locally decodable code (RLDC) is a weaker notion where the decoder is…
Wenkai Zhang, Zhiying Wang
DNA, with remarkable properties of high density, durability, and replicability, is one of the most appealing storage media. Emerging DNA storage technologies use composite DNA letters, where information is represented by probability vectors, leading to higher information density and lower synthesizing costs than…
Søren Riis
Term Coding asks: given a finite system of term identities Γ in v variables, how large can its solution set be on an n–element alphabet, when we are free to choose the interpretations of the function symbols? This turns familiar existence problems for quasigroups, designs, and related objects into quantitative extremal…
Hongyang Liu, Wei Yan
For the discrete memoryless sources with a countably infinite alphabet, we prove that for any positive integer $k$, there exists a corresponding probability interval such that if the largest symbol probability $p_{1}$ falls in this interval, the optimal code length for the symbol equals $k$. Furthermore, for infinite…