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
5 votes
0 answers
74 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$ ...
9 votes
1 answer
598 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$ ...
3 votes
1 answer
109 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 ...
3 votes
1 answer
534 views

Lovasz theta and circulant graphs

Let $\theta(G)$ denote Shannon zero error capacity of graph $G$ and $\vartheta(G)$ be Lovasz upper bound for $\theta(G)$. Let $C_{2n+1}$ denote cycle graph with $2n+1$ nodes. We know following two ...
6 votes
3 answers
573 views

Reference for partial Hadamard matrices

Definition. An $m\times n$ matrix is said to be a partial Hadamard matrix (let's say PHM) if its entries are chosen from $\lbrace -1, 1 \rbrace$ such that the dot product of each pair of row vectors ...
2 votes
1 answer
171 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
1 answer
277 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 ...
0 votes
1 answer
108 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 ...
9 votes
2 answers
771 views

How did they come up with the MRRW bound?

Among the good asymptotic bounds in coding theory in the MRRW bound. It is obtained by using the linear programming problem of Delsarte's and providing a solution. The LP problem is Suppose $C \...
3 votes
1 answer
148 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
3 answers
406 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 ...
2 votes
0 answers
84 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 ...
1 vote
0 answers
102 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
156 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 ...
19 votes
3 answers
2k views

Can you cover the Boolean cube $\{0,1\}^n$ with $O(1)$ Hamming-balls each of radius $n/2-c\sqrt{n}$?

(where c>0 and the balls need not be disjoint?) This is an embarrassingly simple question, yet somehow I couldn't find an answer (not even, "this is a well-known open problem") after spending some ...
1 vote
0 answers
68 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
127 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-...
3 votes
1 answer
182 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 ...
2 votes
0 answers
182 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 $...
4 votes
2 answers
242 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
44 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 $\...
3 votes
1 answer
281 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
1 answer
131 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 ...
1 vote
0 answers
72 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
358 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
87 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
100 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 ...
4 votes
0 answers
155 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
121 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$)...
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 {\...
0 votes
0 answers
123 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 + \...
7 votes
0 answers
132 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
1 answer
378 views

System of equations - Proof that a solution exists

Let $ a = (a_1,a_2, \ldots,a_{10})\in \{ 0,1\}^{10}$ be a binary vector of length $10$. Question: Without using a computer-aided method, how to prove that there exists binary vectors $x_{i,j} \in \{ ...
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
72 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
145 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
309 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
71 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 $...
3 votes
3 answers
768 views

A different criterion for equivalence of codes?

I've been thinking about equivalence of codes (two codes that are equal up to order of positions of the letters, or permutations of the letters in a fixed position). It is obvious that if we have two ...
4 votes
3 answers
246 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
174 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
105 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\...
5 votes
1 answer
2k views

Lovász $\delta$ condition for LLL Algorithm

http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm What is the importance of the $\delta$ parameter for LLL bases called Lovász condition? ...
4 votes
0 answers
115 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,...
2 votes
2 answers
400 views

Lovasz theta function - uses

Lovasz theta function bounds the Shannon capacity of graphs. What are some other uses of the function - especially in asymptotic coding theory and optimization problems?
4 votes
2 answers
1k views

How to quantify the error correction capacity of LDPC code?

As shown in title, I am studying the LDPC code recently. However, I still can not calculate the error correction capacity of it, maybe due to complex decoding algorithm. And there lacks easy ...
7 votes
2 answers
417 views

How to count the number of tensors over a finite field of tensor rank $r$?

For simplicity, work over $\mathbb F_2$ and only consider order-$3$ equilateral tensors. For $r\in\mathbb Z_{>0}$, how many tensors $\mathfrak{T}\in\mathsf{Ten}_{n}^{\otimes 3}(\mathbb F_2)$ are ...

1
2 3 4 5 6