Questions tagged [coding-theory]

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

Filter by
Sorted by
Tagged with
3 votes
1 answer
82 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
  • 131
3 votes
1 answer
82 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.6k
1 vote
1 answer
78 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
2 votes
0 answers
92 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
0 votes
0 answers
87 views

Existence of a family of size 2^Ω(n) of subsets of {1,...,n} each of cardinality n/4 where two subsets have at most n/8 elements in common

Let $\mathcal{G}$ be a family of $t=2^{\Omega(n)}$ subsets of $N=\{1,2,...,n\}$, each of cardinality $n / 4$ so that any two distinct members of $\mathcal{G}$ have at most $n / 8$ elements in common. ...
C. Mürtz's user avatar
  • 101
3 votes
1 answer
184 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
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
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
0 votes
0 answers
59 views

Is there a name/terminology for binary codes with evenly spaced number of ones?

I am generating a random binary matrix $A \in \{0, 1\}^{m \times n}$ with the number of ones in each row set to evenly spaced numbers from an interval. For example, if $n=50$, the number of ones for $...
randomprime's user avatar
1 vote
1 answer
91 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
5 votes
1 answer
213 views

Are all linear-rate and -distance classical linear codes expanding?

Consider a LDPC linear code defined as $\ker H$ for a $O(1)$ row- and column-sparse matrix $H \in \{0,1\}^{n \times r}$ with independent rows. Assume the code is linear-rate meaning $n - r = \Omega(n)$...
Chinmay Nirkhe's user avatar
1 vote
1 answer
99 views

Code indistinguishability assumption for Code based cryptography (in special cases)

Cryptosystems that are based on error correcting codes are often based with hardness of the two problem. Computational syndrome decoding is hard Indistinguishability Assumption (IA): Distinguishing ...
Root's user avatar
  • 387
3 votes
1 answer
171 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
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
0 votes
0 answers
156 views

Is the following graph an expander graph?

Let's say we have the following bipartite-graph, denoted $G=(L,R,E)$: It has the following adjacency matrix: I am having problems decoding a received word from what I was told is an expander code ...
Louie_the_unsolver's user avatar
6 votes
2 answers
221 views

Reference request for linear algebra over GF(2)

I have been looking for materials on the linear algebra over $GF(2)$ but so far I haven't found any substantial textbooks or notes on this subject. In fact in one of the notes I found the introduction ...
gen's user avatar
  • 260
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
2 votes
2 answers
337 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
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
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
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
10 votes
1 answer
446 views

Is subtractive dithering the optimal algorithm for sending a real number using one bit?

Consider the problem of sending a real number $x\in[0,1]$ using a single bit $X\in\{0,1\}$ in an unbiased manner. We assume that the sender and receiver have access to shared randomness $h\sim U[-1/2,...
R B's user avatar
  • 9,448
8 votes
1 answer
165 views

What are the general direction and target question in the field of quantum error correction?

After quantum error correction was introduced in mid '90s, in subsequent years many of the classical analogues regarding the structure of code (such as singleton bound, GV bound etc) were obtained in ...
Root's user avatar
  • 387
4 votes
1 answer
238 views

Survey on Quantum error correction

Are there any standard recent survey articles on quantum error correction (and may be including fault Tolerant computing)? The most standard ones that many people refer to are this and this. Both of ...
Root's user avatar
  • 387
2 votes
0 answers
188 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
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
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
3 votes
1 answer
207 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
0 votes
1 answer
118 views

Notation of sequences in rate distortion theory

I have been reading whatever sources I could get my hands on today, regarding this problem. Most notes online about rate distortion theory come from the book Elements of Information Theory by Thomas ...
sn3jd3r's user avatar
  • 133
2 votes
0 answers
110 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
1 vote
0 answers
86 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,733
0 votes
1 answer
55 views

weights in low density codes

Generally, low density parity codes are decoded using sum product decoder (also known as decoding under belief propagation). Such codes are usually decoded nicely if there are no short length cycles ...
Root's user avatar
  • 387
5 votes
1 answer
235 views

Complexity of finding automorphism group of code

What is the computational complexity (may be both classical or quantum) for finding automorphism group of a general linear code? Is there better bound on complexity if structure of code is known for ...
Root's user avatar
  • 387
2 votes
0 answers
109 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
5 votes
0 answers
121 views

Quantum security of cryptosystems: Are any non-Goppa code-based systems resistant to hidden subgroup attacks?

One of the main candidates for post-quantum cryptography is code-based cryptography (as opposed to lattice-based). The Niederreiter cryptosystem based on Goppa codes is shown to be resistant to hidden ...
Root's user avatar
  • 387
1 vote
0 answers
54 views

Underlying codes in Niederreiter cryptosystems

Niederreiter cryptosystem is usually described by a parity check matrix $H$ over $\mathbb{F}_{2^n}$. The minimum distance $d$ is given by $d= min\lbrace k \text{ such that there are $k$ linearly ...
Root's user avatar
  • 387
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
  • 12.9k
3 votes
2 answers
403 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
0 votes
0 answers
33 views

Minimum distance of a code [duplicate]

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
0 votes
2 answers
220 views

Bounds for maximum number of code-words in a ternary error correcting code with length n and distance d?

I'm not sure I can find an explicit formula. Wondering if anyone can come up with lower/upper bounds.
Mkch's user avatar
  • 113
2 votes
0 answers
121 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
2 answers
343 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
5 votes
0 answers
77 views

Error correction with asymmetric channel

Suppose A is trying to transmit a message to B over a noisy low bandwidth channel, while B has the ability to simultaneously transmit arbitrary amounts of information losslessly to A. Are there ...
Antimony's user avatar
  • 917
-1 votes
1 answer
119 views

Does a code need at least two symbols to be defined as a code? [closed]

I am wondering whether you could still call a code something that, if transmitting, only transmits one symbol. Or does the formal definition of code require 2 or more symbols? (and would the answer ...
magnolia1's user avatar
2 votes
1 answer
125 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
1 vote
1 answer
154 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
75 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
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
5 votes
2 answers
1k views

Relation between group theory and information theory

Motivation: I am interested about the application of group theory to information theory. To be precise, I am interested in data compression (source coding theory). Question: Is there any paper/survey ...
Michael's user avatar
  • 533
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