Skip to main content

Questions tagged [coding-theory]

The mathematical theory of codes, as used in communication, data compression, and cryptography.

Filter by
Sorted by
Tagged with
4 votes
0 answers
84 views

Is there a standard interpretation of this quantity?

Define an encoding scheme by a pair of functions: $$\mathsf{encode} : \mathcal{M}\to\mathcal{X},\quad \mathsf{decode} : \mathcal{X}\to\mathcal{M}$$ Typical examples of encoding schemes are things like ...
Mark Schultz-Wu's user avatar
4 votes
0 answers
103 views

Where in $PH$ are these problems?

Is 'Given two codes with alphabet in $\mathbb F_2$ with Generator matrices $G_1$ and $G_2$ do they have the same minimum distance?' in $NP$ or is it in $coNP$ (I can see it in $P^{NP}$)? If $G_1$ is ...
Turbo's user avatar
  • 13k
4 votes
0 answers
118 views

What is the largest noise rate $\eta(n)$ for which learning parities with noise is easy?

Learning Parity with Noise (LPN) is usually stated with constant noise rate $\eta < 1/2$ on the labels, and it is believed to be hard to learn because of the high statistical dimension of the ...
Jeremy Kun's user avatar
  • 1,318
3 votes
2 answers
374 views

Information and Coding Theory Texts

I am coming from a pure mathematics (in analysis) background and am curious to learn some information and coding theory. I am after some recommendations on texts. Due to my personal background I am ...
Zeta-Squared's user avatar
3 votes
2 answers
4k views

How many different Huffman encoding for a given number of symbols

In Huffman coding, if we have two symbols to be encoded, we will get the result either 01 or 10. If we have three symbols, we ...
Yang Xia's user avatar
  • 153
3 votes
2 answers
422 views

Minimum distance of a code

Is there a way to compute minimum distance of a code given a systematic parity check matrix? I know that min dist is smallest number $d$ such that there exists $d$ linearly dependant columns. I am ...
Root's user avatar
  • 387
3 votes
1 answer
177 views

Maximal uniquely decodable codes

This question is about the Kraft-McMillan inequality: If $w_1,\ldots,w_n$ are words of lengths $l_1,\ldots,l_n$ from an alphabet with $r$ letters, which form a uniquely decodable code, then $$ \sum_{i=...
aiz89's user avatar
  • 33
3 votes
1 answer
352 views

reduction of maximum independet set to minimum distance of code

Is there a reference for direct reduction of computing maximum independent set of a suitably constructed graph to computing minimum distance of a linear code when the code is specified by its parity ...
v s's user avatar
  • 2,208
3 votes
1 answer
586 views

Distance of arbitrary vectors to Hadamard code

Let $n$ be a positive integer and $N = 2^n$. The Hadamrd code of "block length" $N$ can be generated using the inner product $f_u(x) = \langle u,x \rangle$ mod $2$ for all $u \in \{0,1\}^n$. It is ...
SpaceMonkey's user avatar
3 votes
1 answer
92 views

Testing if a distribution over $\mathbb{F}_2^n$ is heavily supported on a subspace

Let $P$ be a distribution over n-bitstrings which we will view as elements of $\mathbb{F}_2^n$. Given sample access to $P$, I am looking for an algorithm that tests if $P$ is heavily concentrated on a ...
Marsl's user avatar
  • 133
3 votes
1 answer
185 views

Theorem of Sudan, Trevisan and Vadhan about list-decoding

My question is about the following result about list-decoding of Sudan, Trevisan and Vadhan. (The formulation is taken from Shuichi Hirahara's paper.) I do not understand how this is possible. I ...
Alexey Milovanov's user avatar
3 votes
1 answer
210 views

Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?

I do not understand the assumption $X_1, X_2, \cdots$ are i.i.d. ~p(x) in the AEP proofs I have seen. I have read some different sources for understanding the Asymptotic Equipartition Property. Using ...
Fred Guth's user avatar
  • 143
3 votes
1 answer
189 views

Upperbound on cardinality of product of two string sets at pairwise Hamming distance $> 1$

I am considering products $U\times V$ of subsets $U, V\subset \{0, 1\}^p$ with a pairwise Hamming distance greater than 1 : $\forall uv\in U\times V, D(u,v) \geq 2$. Given $p$, I am looking for a ...
babou's user avatar
  • 1,542
3 votes
1 answer
277 views

Surveys on Algorithmic Problems in Coding Theory

Coding Theory has many algorithmic problems that enriched theoretical computer science. I want to learn specifically the connection between coding theory and the hardness of computational problems. I'...
Mohammad Al-Turkistany's user avatar
3 votes
1 answer
90 views

Application of PCP and error correcting codes to LLMs?

Are there any interesting results in applying error correcting codes and ideas from PCP (Probabilistically Checkable Proofs) to improve the quality of large language models (LLM), or connecting them ...
Kaveh's user avatar
  • 21.7k
3 votes
0 answers
155 views

Computational complexity of minimum distance of rate $\frac{1}{2}$ codes

We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing minimum distance of a (binary) ...
Root's user avatar
  • 387
3 votes
0 answers
76 views

Communication complexity of edit resilient synchronization

Supposing we have two strings $A$ and $B$ that are both edit distance $\tau$ from each other at two different sites is there a communication complexity model where synchronizing such strings have been ...
user avatar
3 votes
0 answers
54 views

Reference for randomized GMD decoding

The GMD decoder is an algorithm for decoding concatenated codes up to half their minimal distance. The standard presentation of this algorithm usually proceeds in two steps: First, one shows a ...
Or Meir's user avatar
  • 5,615
2 votes
3 answers
643 views

Is there a lower bound of number of redundant bits necessary to encode a word with certain Hamming distance?

Is there a lower bound (in coding theory or elsewhere) of number of redundant bits necessary to encode a word with certain Hamming distance? There is some known data for parity checks, CRC, Hamming ...
Halst's user avatar
  • 123
2 votes
2 answers
344 views

Why can't codes be defined over infinite fields?

In Coding Theory, people use $q$-ary alphabets: why do we need a finite set? Why can't we define codes over infinite sets. such as $\mathbb{R}$ or $\mathbb{C}$?
cruz's user avatar
  • 21
2 votes
1 answer
422 views

Question about "typical set" in Shannon's source coding theorem

I was following the textbook by David Mackay: Information theory inference and learning algorithms. I have question on asymptotic equiparition' principle: For an ensemble of $N$ $i.i.d$ random ...
kuku's user avatar
  • 123
2 votes
1 answer
121 views

Subspace-evasive set performance in the random case

A subspace evasive set is defined as a large subset of a vector space which has small intersection with any $k$ dimensional affine space. That is, it "evades" all affine subspaces of small enough ...
BharatRam's user avatar
  • 393
2 votes
1 answer
207 views

Explicit Bits-back Coding (a.k.a. Free Energy Coding) applied to Gaussian mixtures

I've been trying to understand Bits-back coding (Frey, B. J., and G. E. Hinton. 1997.) a bit more (pun intended), which can be used to encode data with latent variable models. This tutorial by Pieter ...
Daniel Severo's user avatar
2 votes
1 answer
126 views

Function which detects rotation of bit string

Consider a function $F: \mathbb{F}_2^d \to \mathbb{Z}^n = (f_1,\ldots,f_n)$ with the property that if $y \in \mathbb{F}_2^d$ is a rotation of $x \in \mathbb{F}_2^d$, i.e. $y$ is $x$ permuted by an ...
Max Hopkins's user avatar
2 votes
1 answer
140 views

Ambivalent Coding

Consider the following situation, I want to send one of two bitstrings, A or B, to a receiver. Clearly, I can do this by sending the shortest, but is there a better way? It seems that the requirement ...
Peter's user avatar
  • 459
2 votes
0 answers
100 views

The existence of (non-rectangular) two dimensional Gray code

A Gray code consists of $n$-bit distinct strings $s_1,s_2, \ldots,s_N$ such that each $s_i$ and $s_{i+1}$ differs by one bit. For example: $000, 001, 010, 011, 111, 110, 101, 100$. It is known that we ...
Kai-Yuan Lai 賴開元's user avatar
2 votes
0 answers
182 views

On the number of optimal prefix-free binary codes [closed]

Let $T$ be a text of length $L$ containing the symbols $$\mathcal{A}=\{a_1, a_2, \ldots, a_n\},$$ where each symbol appears at least once and no other symbol appears in $T$. Define the weights $$\...
Riccardo's user avatar
2 votes
0 answers
88 views

Approximate (in hamming distance) subset representation

Let us have a set $S$ and a subset $T \subseteq S$. I want to find an approximate representation of $T$, i.e. I want to represent (exactly) a set $T'$ that is close to $T$. That is, I want the ...
user2316602's user avatar
2 votes
0 answers
205 views

Damerau–Levenshtein distance with transposition of non-adjacent characters?

Wondering if it's possible to calculate Damerau–Levenshtein distance with transposition of non-adjacent characters (DL distance allows transposition of immediately adjacent characters only). I want ...
Ted's user avatar
  • 21
2 votes
0 answers
112 views

Relation between automorphism group of a linear code and its dual code

Are there any strong connections between automorphism groups of codes that are dual codes of each other? I am looking for statements like one charcterizes other or one gives bounds on other etc. In ...
Root's user avatar
  • 387
2 votes
0 answers
112 views

How hard is it to approximate distance of linear code

I'm trying to figure out what is the current knowledge about how hard it is, given a generating matrix of a linear code over a field $F_{q}$, approximate it's distance. I of course found that ...
Bartolinio's user avatar
2 votes
0 answers
122 views

Explicit Formula of Delsarte's Linear Programming Upper Bound for $A_q(n,3)$

The problem of giving an explicit formula for $A_q(n,d)$ is sometimes referred to as "the main problem in coding theory." The value of $A_q(n,d)$ is given by the maximum number of codewords in a q-ary ...
Max Hopkins's user avatar
2 votes
0 answers
159 views

Unit hypercube encodings

How can we chose to place $k$ points in $[0,1]^d$, such that the minimum Euclidian distance between any two points is maximized? Is there a more common term for these combinatorial designs than unit ...
Chad Brewbaker's user avatar
2 votes
0 answers
126 views

Universal constant for bivariate testing

In the seminal paper of Polishchuk and Spielman where they give a construction of nearly linear sized $PCP$ for an $NP$ problem, one of the key ingredients is a low-degree test for bivariate ...
BharatRam's user avatar
  • 393
2 votes
0 answers
87 views

Complexity of counting codeword length distribution

Suppose I have a code $C$ over $GF(2)$. I would like to count exactly the number of codewords of $C$ of weight $k$. Here $k$ should be thought of as small compared to the dimensions of the code. ...
David Harris's user avatar
  • 3,508
2 votes
0 answers
75 views

Weight enumerator and levels of polynomial hierarchy

Let $A_i$ be the number of codewords in a binary linear code $\mathcal{C}$ of weight $i$. It is known that: $A_k$ is in $P$, where $k = \mathcal{O}(\log_2 n)$. $A_{n}$ is in $\#P-Complete$, ...
Pavithran Iyer's user avatar
2 votes
0 answers
107 views

Bayesian compression

Suppose you have a sequence generated by an i.i.d. process (such as repeatedly rolling a die and recording the values in order) parameterized by some K-dimensional vector $\vec{\gamma}$ (the ...
user13501's user avatar
2 votes
0 answers
442 views

Lee metric, Gilbert-Varshamov and Hamming bounds for larger relative distance ranges

Gardy and Sole provide a Gilbert-Varshamov lower bound and a Hamming upper bound for the Lee metric when the distance between codewords is smaller than the length of the code (captured by $r = \delta ...
v s's user avatar
  • 2,208
1 vote
1 answer
156 views

Why are folded Reed Solomon Codes considered non linear?

This is for my understanding. What am I missing?
Jardine's user avatar
  • 395
1 vote
1 answer
77 views

Families of LDPC codes with constant error fraction corrected

I am looking for families of error-correcting LDPC codes with a constant error fraction corrected by a decoding algorithm. For example, I know that Sipser and Spielman proved that there is an ...
P.B.'s user avatar
  • 113
1 vote
1 answer
119 views

The noise distribution on $F_2^n$: probability of landing in a subspace versus a coset

Let $V = F_2^n$ be the $n$-dimensional vector space over the field of two elements. The $\epsilon$-noise distribution on $V$, denoted $\mu_\epsilon$, is a probability distribution on $V$ for which ...
Andrew Morgan's user avatar
1 vote
1 answer
79 views

Detecting Erroneous Corrections

A block code $C$, with minimum distance $d$ can be used to: Detect $d - 1$ errors Correct $\lfloor\frac{d - 1}{2}\rfloor$ errors However, the above usually assumes that the number of errors that are ...
Coziyu's user avatar
  • 11
1 vote
1 answer
92 views

Do Programming Languages classify as Language? [closed]

Much classification work has been done classifying programming languages, however do programming languages classify as languages themselves. Languages as "the primary means of communication",...
eljefedelrodeodeljefe's user avatar
1 vote
1 answer
192 views

Structured set of binary words

Definitions: Let $n\in \mathbb N$ be an integer, and consider the field $\mathbb K=GF(2^n)$. For $c\in \mathbb N$, let $S_c$ be a set of $n$ elements from $\mathbb K$ such that: Every element $e$ ...
wwjoze's user avatar
  • 205
1 vote
1 answer
237 views

fast range summable hash functions

I'm finding is there any range summable hash function. ADD: The hash function I refer to is the one that is typically used in tug-of-war sketch(AMS sketch). Please refer to The space complexity of ...
redplum's user avatar
  • 121
1 vote
0 answers
20 views

Coloring the $k$-deletion graph “constructively”

For $n,k\ge 1$, we define the graph $D_{n,k}$ to have vertex set $\{0,1\}^n$, with distinct $x,y$ being adjacent if $LCS(x,y)\ge n-k$. My question is: fixing $k>1$, does there exist some $C=C_k$ ...
Zach Hunter's user avatar
1 vote
1 answer
75 views

Non-random errors with a Reed Solomon code

If I have a RS code, say [46, 16, 31], then I have a guaranteed error correction up to 15 symbols. I have no idea if it matters, but the code I have in front of me ...
A. Nilsson's user avatar
1 vote
0 answers
77 views

BCH codes and polynomials with many values in a subfield

For points $P=\{x_1, \ldots, x_n\} \subset {\mathbb F}_{2^m}$ define $$\mathcal{C}(P, t) =\{(f(x_1), \ldots, f(x_n)) \mid \mbox{$f\in {\mathbb F}_{2^m}[X]$ has degree $t$}\}$$ and $\mathcal{C}'(P, t) =...
user6584's user avatar
  • 1,242
1 vote
0 answers
133 views

Quantum error correction and graph codes

I was reading combinatorial approach towards quantum correction. A lot of work in this is on finding diagonal distance of a graph. Let me add definition of diagonal distance so that this remains self-...
Root's user avatar
  • 387
1 vote
0 answers
87 views

Explicit binary codes with block length n, distance n / log n, rate 1 - o(1)?

What are the best (i.e., highest-rate) explicit binary codes with block length $n$ and minimum distance $d$, in the regime $d = n^{1 - o(1)}$? The "redundancy" of a code is the difference between the ...
William Hoza's user avatar
  • 1,743