# Questions tagged [coding-theory]

The theory of error-correcting codes stems from Shannon's 1948 _A mathematical theory of communication_, and from Hamming's 1950 "Error detecting and error correcting codes".

280
questions

3
votes

0
answers

90
views

### Does this code have a name?

Hamming-distance-4 binary codes have a very direct relationship to sphere packings. That's because we can identify the codewords with the cosets of $\mathbb{Z}^n/(2\mathbb{Z})^n$, and Hamming-distance-...

0
votes

0
answers

54
views

### Does the Plotkin bound mean that one can not achieve the Singleton bound asymptotically?

I am a little confused with the relationship between various bounds for error correcting codes.
Does the Plotkin bound mean that one can not achieve the Singleton bound asymptotically? That is, is ...

2
votes

1
answer

108
views

### Maximum cardinality of separated sets in the Hamming distance

This question is motivated by section 15.1 (Codes) of Alon and Spencer's The probabilistic method.
Fix $\alpha<\frac{1}{2}$ and for each $n\in\mathbb{N}$ let $\{0,1\}^n$ be the length $n$ binary ...

4
votes

2
answers

211
views

### Concentration of minimum Hamming distance between $N$ points sampled iid from uniform distribution on $n$-dim hypercube $\{0,1\}^n$

Let $n$ be a large positive integer. Sample $N \ge 2$ points $x_1,\ldots,x_N$ iid from the uniform distribution on the $n$-dimensional hypercube $\{0,1\}^n$. Define the gap $\delta_{N,n} := \min_{i \...

1
vote

1
answer

35
views

### Weight of a codeword in a cyclic code as a function of the number of solutions of an equation involving the trace function

Let $q = p^s$ and $r = q^m$, where $p$ is a prime, $s$ and $m$ are positive integers. Let $N>1$ be an integer dividing $r - 1$, and put $n = (r - 1)/N$.
Let $\alpha$ be a primitive element of $\...

1
vote

1
answer

108
views

### On the existence of symmetric matrices with prescribed number of 1's on each row

We are considering the following problem:
Given an integer $n$ and a sequence of integers $r_i,\ 1\le i\le n$, with $0\le r_i\le n-1$ does there exists a symmetric matrix $A$ such that the diagonal ...

3
votes

1
answer

257
views

### What do we know about the $\mathbb{F}_{q^2}$-curve $X^{q-1} + Y^{q-1} + Z^{q-1}$?

People have thoroughly studied the Hermitian $\mathbb{F}_{q^2}$-curve $H: X^{q+1} + Y^{q+1} + Z^{q+1} = 0$. What do we know about the similar $\mathbb{F}_{q^2}$-curve $C: X^{q-1} + Y^{q-1} + Z^{q-1} = ...

0
votes

0
answers

41
views

### Existence of full-weight codeword in a linear q-ary code

I'm new to coding theory but would like to ask the following question:
Let $C$ be a linear $q$-ary code over $\mathbb{F}_q$ of length $n$ and dimension $k$ where $\mathbb{F}_q$ is a finite field with $...

2
votes

1
answer

200
views

### Inner product over finite field

sorry for informals but is my first post.
In Coding theory (exactly in Coding theory a first course - San ling and Chaoping) found this definition:
$\langle , \rangle :\mathbb{F}_q^n\times\mathbb{F}_q^...

1
vote

1
answer

68
views

### Maximal number of $k$-subsets of an $n$-set such that any two subsets meet in at most $(k-2)$ points

I am interested in the maximal number of $k$-subsets of an $n$-set such that any two subsets meet in at most $(k-2)$ points. I found that for $k=3$ and $k=4$, we have the sequences http://oeis.org/...

2
votes

0
answers

169
views

### Existence of fully supported element in a finite-dimensional vector space over $\mathbb{F}_p$ (and in finite abelian groups)

Let $V$ be an $n$-dimensional vector space over $\mathbb{F} = \mathbb{Z} / (p)$, the field of $p$ elements, $p$ a prime, with $\{v_1, \dotsc, v_n \}$ a basis for $V$. An element $x \in V$ is called &...

0
votes

0
answers

18
views

### Do binary cyclic code asymptotics determine all $q$-ary code asymptotics?

An infinite family $\mathcal C$ of non-isomorphic $q$-ary codes is "asymptotically good" if for some $\delta>0$ there exist infinitely many $\mathcal C$ members with both relative rate ...

1
vote

1
answer

85
views

### Support of Fourier transform of random characteristic function

Let $\chi_X:\{-1,1\}^n\to \{0,1\}$ be the characteristic function of a subset $X\subseteq \{-1,1\}^n$, which is randomly drawn from all subsets with exactly $k$ elements.
Is the support of the Fourier ...

2
votes

0
answers

156
views

### Intersection of subspace and subcubes

Consider a $d$-dimensional linear subspace $V\subseteq\mathbb{F}_p^n$, and its intersection with subcubes of form $S_1\times\cdots\times S_n$, where $S_1,\ldots,S_n$ are arbitrary size-$s$ subsets of $...

2
votes

1
answer

120
views

### Optimal prefix-free code design with a complex objective function

We have a long message $m$ to encode. The message is composed of a set of symbols $\{s_i\}$. Let $p_i$ denote the number of appearance of $s_i$ in $m$. We seek to find a prefix-free code for each $s_i$...

4
votes

0
answers

146
views

### Multiset of Hamming distances for a tour of all subsets

Consider a list of all the subsets of $\{1,\ldots,n\}$, in any order. Using binary notation, one such list for $n=3$ is
$$ 010, 100, 110, 011, 000, 111, 001, 101. $$
Now consider the Hamming distance ...

2
votes

0
answers

87
views

### List decodability of Reed-Solomon codes beyond the Johnson bound

In a paper on a proximity test for Reed-Solomon codes the authors state an "extremely optimistical" conjecture on the list decodability of Reed-Solomon codes (over prime fields $\mathbb F_q$)...

0
votes

0
answers

86
views

### Given a binary parity check matrix, find a parity check matrix for the same code such that no row has weight greater than $k$

A parity check matrix for a binary linear code is a matrix $H$ (with linearly independent rows) such that the (right) kernel of $H$ is the codespace. Clearly we can replace any row $r_i$ by $r_i + \...

4
votes

1
answer

150
views

### Sequence design to optimize a combinatorial objective

Given a set $\cal N$ of $N$ objects, we seek to attribute a code, i.e., a binary sequence, to each of them to achieve the following objective of being capable to select any subset ${\cal S}\subseteq {\...

7
votes

0
answers

115
views

### Ideals, subalgebras, subgroups as error-correcting codes?

Context: roughly speaking the construction of a error correcting code is a problem to choose some subset in a metric space, such that the points of the subset pairwise as far-distant as possible. ...

1
vote

2
answers

94
views

### Name for the weight function defined as the integer sum of coordinate entries from ${\mathbf F}_p$

In ${\mathbb F}_p^n$, $p$ prime one may define a weight function on vectors in various ways such as Hamming, or Lee weight. (These two weights correspond nicely to the respective distances from $\bar ...

1
vote

1
answer

67
views

### How far from a sparse parity function can a function be and still look like such a function on small sets?

Let $\mathbb F_2^n$ denote the set of binary vectors of length $n$. A $k$-sparse parity function is a linear function $h:\mathbb F_2^n\to\mathbb F_2$ of the form $h(x)=u\cdot x$ for some $u$ of ...

2
votes

1
answer

128
views

### Verify if array is orthogonal

This is a repost from the computer science stackexchange. The question has been offered a bounty, but received no answers. Therefore, I would like to ask this question here.
Orthogonal arrays often ...

4
votes

1
answer

283
views

### Bipartite version of Hamming bound (two families of codewords with large Hamming distance)?

Update: In light of Fedor Petrov's answer, I added an additional requirement that all strings in $A$ and $B$ have Hamming weight exactly $n/2$, which hopefully makes the question more interesting.
...

1
vote

1
answer

49
views

### (Approximation) Algorithms for Weight Distribution / Subspace Weights Problem in coding theory

The Weight Distribution / Subspace Weights Problem in coding theory is defined as this:
Instance: A binary $m$ by$n$ matrix $H$ and an integer $k > 0$
Question: Is there a set of $k$ columns of $...

4
votes

3
answers

225
views

### Existence of (near) equidistant codewords

My question is originally related to coding theory, but fairly easy to state in pure combinatorial way.
Fix $k\in\mathbb{N}$, $\beta\in(0,1)$ and consider the binary cube $\Sigma_n = \{0,1\}^n$ ...

5
votes

1
answer

142
views

### Existence of a joint distribution on Bernoulli variables with same probability of being pairwise different

Let $m\in\mathbb{N}$ and $p\in(0,1)$ be arbitrary. Is there a sequence $X_1,\dots,X_m$ of random variables with the following specs on their distribution:
Each $X_i$ is unbiased Bernoulli: $X_i\sim {\...

2
votes

0
answers

98
views

### Mutual benefits of coding theory and the reconstruction conjecture

Let $G_n$ denotes all graphs with $n$ nodes. For any graph $G$ in $G_n$, the adjacency matrix $A(G)$ can be viewed as a codeword of length $n^2$. Also, the codes arises from $G_n$ is a linear binary ...

3
votes

1
answer

147
views

### Coding over very noise channel

Suppose that I want to send a message (consisting of bits) over a channel where from $n$ transferred bits as many as $n/2-\varepsilon n$ might be flipped, i.e., the distance of the code is $n-2\...

4
votes

0
answers

111
views

### What is the least compressible probability distribution? (under entropy constraint, for an expected squared error metric)

This is a cross-post from cstheory after a week with no answers/comments; I'm hoping someone here may have some thoughts.
Consider a distribution $\mathcal D$ over the reals, a real parameter $H\in\...

21
votes

2
answers

1k
views

### The chromatic number of the union of two graphs

Let $G_n$ be the graph on the set of all binary strings of length $n$ with two strings adjacent whenever they are Hamming distance $2$ away from each other, or one of them lies below another one; thus,...

6
votes

0
answers

212
views

### Gaussian coefficients identity

I am having difficulty showing the equivalence between (11) and (15) of Delsarte - Association schemes and $t$-designs in regular semilattices. It is somehow an application of Möbius inversion, but I ...

2
votes

1
answer

135
views

### Decoding the Reed–Muller $RM(m, m)$ code, and a matrix related to Pascal's triangle

The Reed–Muller $RM(m, m)$ code sends the message $p(X_0, \ldots , X_{m - 1}) = \sum_{S \subset \{0, \ldots , m - 1\}} \alpha_S \cdot X_S$ to its set of evaluations $\left\{ p(x_0, \ldots , x_{m - 1}) ...

6
votes

1
answer

249
views

### How many Hamming spheres of radius 1 does it take to cover the cube?

I am looking for the sharpest known upper bound on $K(n, 1)$ as $n \rightarrow \infty$. This is the minimal cardinality of a (not-necessarily linear) covering code of $\{0, 1\}^n$ of radius 1.
In ...

1
vote

0
answers

38
views

### Computational complexity 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 the minimum distance of a (binary)...

1
vote

0
answers

95
views

### Promise version of minimum distance

It has been known for some time that computing minimum distance of a linear code (minimum weight codeword) is NP-hard.
This immediately also says that given a code $C$, calculating minimum hamming ...

3
votes

1
answer

106
views

### Dense and decodable lattices in high dimensions

We are currently looking for both dense and decodable lattices.
Precisely, we want a lattice which CVP can be solved in polynomial time like $O(n^2)$ or $O(n^3)$ where $n$ is the dimension like 128 or ...

8
votes

2
answers

349
views

### Maximum of the weighted binomial sum $2^{-r}\sum_{i=0}^r\binom{m}{i}$

Let $m$ be a positive integer and let $f_m(r)=2^{-r}\sum_{i=0}^r\binom{m}{i}$. Clearly $f_m(0)=f_m(m)=1$ and $f_{2r+1}(r)=2^{2r}$.
Conjecture: If $m>12$, then the maximum value of $f_m(r)$ for $r\...

8
votes

0
answers

136
views

### On the number of Reed–Muller codewords with no consecutive ones

$\DeclareMathOperator\RM{RM}\DeclareMathOperator\Eval{Eval}$Consider the polynomial ring $\mathbb{F}_2[x_1,x_2,\dotsc,x_m]$ and let $f\in \mathbb{F}_2[x_1,x_2,\dotsc,x_m]$. Let us now fix a Gray ...

2
votes

1
answer

131
views

### Low-Hamming weight vectors in low-dimensional subspaces of $\mathbb{F}_p^n$

What is the maximum number vectors of Hamming weight at most $w$ in a $d$-dimensional subspace of $\mathbb{F}_p^n$, where $w,d,p$ are constant and $p$ is odd. (The Hamming weight is the number of ...

1
vote

1
answer

103
views

### Almost-parallel corners of the hypercube in high dimensions

Say I would like a collection of k "almost-parallel" boolean vectors $X_1,...,X_k \in \{\pm 1\}^n$, such that $(X_i,X_j)/n \approx 1-\epsilon$ for some small $\epsilon$. How many ways are ...

2
votes

1
answer

164
views

### Simple non-asymptotic upper-bound for packing number of a hamming cube

Looking for a simple upper-bound for the packing number of hamming cube, I'm led to consider the following. Fix $p \in (0,1/2]$. For a positive integer $n$, define $S_n(p) := \sum_{i=1}^{\lfloor np\...

2
votes

1
answer

195
views

### Are there any homomorphic analog error correction code?

Are there any analog error correction codes that are additively and multiplicatively homomorphic?

5
votes

2
answers

362
views

### Maximum number of vectors with upper bound on pairwise inner products

I have a collection $\{v_1,...,v_k\}$ of vectors in $\{\pm 1\}^n$ with the property that for all $i\neq j$ we have $\langle v_i, v_j \rangle \le c\log_2(n)$. I am looking for an upper bound on $k$ in ...

1
vote

1
answer

246
views

### Upper bounds for high-dimensional spherical codes given the covering radius

I assume that this sort of question has already been considered at great length. Nevertheless, I could not find an answer to this question in the related literature.
Given a constant $a\in (0,2]$, ...

1
vote

0
answers

104
views

### A variant of Huffman code

Given an alphabet of $n$ symbolswith probabilities $p_i$ for symbol $i$, we need to encode the symbols (in a prefix-free way) to binary codewords $c(i)$ with length $\ell(c(i))$ to minimize the ...

1
vote

1
answer

281
views

### error correcting huffman code [closed]

I am looking for a code that can correct errors with variable and limited length like huffman code. I am not an expert in coding theory. Is there any code or related literature on this?

2
votes

0
answers

500
views

### Linear independence of Vandermonde matrix in systematic Reed-Solomon code

My question is about using a Vandermonde matrix vs a Cauchy matrix in erasure coding.
In the Reed-Solomon (RS) code, encoding is done by multiplying a $N\times K$ ($N>K$) matrix with the code words ...

6
votes

0
answers

127
views

### When are Hamming codes cyclic?

I've asked this question on math.stackexchange before, but it has not been solved.
The following statement appears to be true:
The $q$-ary Hamming code of codimension $r$ over $\mathbb{F}_q$ is ...

8
votes

1
answer

234
views

### Perfect sphere packings (as opposed to perfect ball packings)

I came across this question when I was discussing the rather wonderful Devil's Chessboard Problem with my colleague, Francis Hunt.
We realised that there is a nice connection to a packing question in $...