Skip to main content

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

Filter by
Sorted by
Tagged with
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$, ...
bc a's user avatar
  • 163
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 ...
Joe Miller's user avatar
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 ...
Daniel86's user avatar
  • 225
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 $\...
Ali Ahmadi's user avatar
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 \...
Jackson Walters's user avatar
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$ ...
Kevin's user avatar
  • 540
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 ...
BCS's user avatar
  • 195
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 ...
user43170's user avatar
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)$....
Harry L's user avatar
  • 31
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 ...
Daniel's user avatar
  • 211
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 ...
Stephen Jiang's user avatar
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 ...
Joe Shipman's user avatar
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 ...
kodlu's user avatar
  • 10.2k
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 ...
Zach Hunter's user avatar
  • 3,469
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-...
Veit Elser's user avatar
  • 1,065
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 ...
liu_c_6's user avatar
  • 11
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 ...
Saúl RM's user avatar
  • 10.4k
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 \...
dohmatob's user avatar
  • 6,824
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 $\...
José's user avatar
  • 219
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 ...
Jeremiah's user avatar
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} = ...
Dimitri Koshelev's user avatar
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 $...
Nick's user avatar
  • 191
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^...
Javier Astorga's user avatar
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/...
Jens Fischer's user avatar
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 &...
Nick's user avatar
  • 191
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 ...
BGJ's user avatar
  • 449
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$ ...
user369335's user avatar
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 $...
Wei Zhan's user avatar
  • 203
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$...
lchen's user avatar
  • 368
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 ...
Brendan McKay's user avatar
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$)...
U. Haboeck's user avatar
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 + \...
itsabijection's user avatar
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 {\...
lchen's user avatar
  • 368
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. ...
Alexander Chervov's user avatar
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 ...
TA_Math's user avatar
  • 11
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 ...
Jack M's user avatar
  • 633
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 ...
yarchik's user avatar
  • 482
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. ...
Octopus's user avatar
  • 43
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 $...
borekking's user avatar
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$ ...
hookah's user avatar
  • 1,096
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 {\...
hookah's user avatar
  • 1,096
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 ...
Shahrooz's user avatar
  • 4,746
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\...
domotorp's user avatar
  • 18.6k
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\...
R B's user avatar
  • 608
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,...
Seva's user avatar
  • 23k
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 ...
Leon Bankston's user avatar
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}) ...
BD107's user avatar
  • 63
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 ...
BD107's user avatar
  • 63
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)...
Root's user avatar
  • 71
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 ...
Root's user avatar
  • 71

1
2 3 4 5 6