# 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".

294
questions

2
votes

0
answers

125
views

### Exp-Hamming distance in $\{0,1\}^k$

Let integer $k>0$ and let $\{0,1\}^k$ denote the set of all $1\times k$-dim vectors whose every coordinate is eithor 0 or 1, for example, $(0,1,1,0,\dots,1,0,0,1)$. For any such vector $\alpha$, ...

8
votes

1
answer

167
views

### Pick a homogeneous set of size $n$

Assume that the natural numbers have been colored with two colors: lavender and periwinkle. You don't know the coloring. You may sample as many (possibly overlapping) sets of size $n$ as you would ...

1
vote

0
answers

48
views

### Generalized Hamming weights for binary BCH codes

Cross posting from MSE. I think it might be a good fit here.
Given a linear binary code $C$, the $r$-th generalized Hamming weight $d_{r}(C)$ is the minimal support size of an $r$-dimensional subcode ...

0
votes

0
answers

68
views

### Extension of automorphism of shift of finite type

$\DeclareMathOperator\Aut{Aut}$Let $X$ and $Y$ be two subshifts of finite type and $X\subset Y$, and $\phi:X\rightarrow X$ be a homeomorphism commuting with the shift map. Is there any homeomorphism $\...

0
votes

0
answers

95
views

### Is there an inner product on $\mathbb{F}_p\left[S_n\right]$ for which $\langle x, x \rangle \ne 0$ for all $x$?

Let $\mathbb{F}_p\left[S_n\right]$ be the group algebra of the symmetric group $S_n$ over the finite field $\mathbb{F}_p$.
One can define an "inner product" in the usual way:
$$\langle x,y \...

6
votes

1
answer

192
views

### Subspaces of $\mathbb{F}_2^N$ containing many pairs of far apart vectors

Let $S$ be a subset of vectors in $\mathbb{F}_2^{3n}$ having Hamming weight $n$. Suppose that $S$ contains $m$ pairs of vectors having disjoint supports (that is, they are at Hamming distance $2n$ ...

4
votes

1
answer

284
views

### What are bit strings where all non-trivial rotations match at a minimum number of places called?

Basically, I'm trying to figure out the name of the thing I want to look up. All the terms I've looked up so far have been related, but not close enough to be useful.
I'm trying to find bit strings ...

3
votes

3
answers

412
views

### Maximal set of $n$-bit strings that does not span $\mathbb{R}^n$

I am trying to find out the maximum-sized subset $S\subseteq \{0,1\}^n$ of $n$-bit strings that does not span $\mathbb{R}^n$.
It is easy to show that $S$ has size at least $2^{n-1}$ when $S$ exactly ...

3
votes

1
answer

180
views

### Distribution of the change in Hamming distance between two sequences

Suppose I have two strings $s_1$ and $s_2$ of equal length $L$ with an alphabet size of $k \geq 2$. Suppose further that these two strings initially have a Hamming distance equal to $d_0 = H(s_1,s_2)$....

2
votes

0
answers

91
views

### Non-translation association schemes duality

In his thesis (1973), P. Delsarte defines a duality construction for association schemes. Nevertheless, this duality construction works only if some special regularity condition is satisfied. I find ...

3
votes

1
answer

155
views

### Binary codes with upper and lower bound on pairwise distance

The Gilbert-Varshamov bound provides a lower bound for codes of length $n$ with minimum pairwise distance (say $\frac{n}8$). If we wish for the codes to also have pairwise distances bounded above (say ...

1
vote

0
answers

112
views

### Generalization of error-correcting codes

If you have a binary single-error correcting code with n-bit codewords, then it is the case that taking only a fixed n-1 out of the n bits gives an “approximate” code with the property that, for any ...

1
vote

2
answers

168
views

### Perfect 1 error correcting codes non-isomorphic to Hamming codes?

In this question about perfect 2 error correcting codes on the Open Problem Garden, it is stated that:
Recent research activity has discovered a large number of previously unknown perfect 1-error ...

1
vote

0
answers

71
views

### Progressions in finite fields with bounded hamming weight

Given $k\ge 2$ and an additive set $S$ (understood to live some implicit group $G$), define $$\Delta_k(S) := \left\{ d \in G: \bigcap_{i=1}^k (S+i\cdot d) \neq \emptyset \right\} $$(i.e., this is the ...

4
votes

0
answers

130
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

1
answer

116
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 ...

3
votes

1
answer

200
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

269
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

45
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

135
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

288
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} = ...

1
vote

0
answers

76
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

483
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

89
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

177
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 &...

1
vote

1
answer

110
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 ...

10
votes

1
answer

609
views

### One question on circulant $\pm1$ matrices

Let $n > 13$ be a positive integer. Is there any $n \times n$ circulant $\pm1$ matrix $A$ satisfying the following property
$$AA^T=(n-1)I+J$$
where $I$ is the $n \times n$ identity matrix and $J$ ...

2
votes

0
answers

189
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

185
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

158
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

128
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

135
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

154
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

137
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

100
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

74
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

158
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

314
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

79
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

254
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

179
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

108
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

149
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

117
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

223
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

172
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

306
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

45
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

107
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 ...