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

74 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
16 votes
0 answers
392 views

Simple disproof of Danzer — Grünbaum conjecture

I asked this question on the MSE, but I did not get an answer. I hope that one of the experienced participants will check the correctness of the proof or the truth of the statement (and, perhaps, will ...
grizzly's user avatar
  • 269
15 votes
0 answers
403 views

The Monster Moonshine Module from the engineering or algorithmic point of view

From what I understand (see, e.g., this question), the Monster Moonshine Module is a kind if "third generation" (or "second quantization"?) after the Golay code (with automorphism group $M_{24}$) and ...
Gro-Tsen's user avatar
  • 29.8k
9 votes
0 answers
458 views

How small parallelograms are we guaranteed to get, when we select the two sides from different plane lattices?

Title question description: Select two lattices $\Lambda_1$ and $\Lambda_2$ (here a lattice=additive free abelian group without accumulation points) of maximal rank two in the real plane. We normalize ...
Jyrki Lahtonen's user avatar
8 votes
0 answers
146 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 ...
Arvind Rameshwar's user avatar
8 votes
0 answers
393 views

When does the Lloyd polynomial have only integral roots?

For a $t$-error correcting code of length $n$ over the finite field $\mathbb{F}_q$, the Lloyd polynomial is given by $$ L_t(n,x):=\sum_{j=0}^t(-1)^j\binom{x-1}{j}\binom{n-x}{t-j}(q-1)^{t-j}. $$ A well-...
Dietrich Burde's user avatar
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. ...
Alexander Chervov's user avatar
7 votes
0 answers
185 views

irregular LDPC code construction algorithm

I want to construct a sparse random binary matrix ${{\bf{H}}_{m \times n}}$ that has the following properties 1- Faction of columns of weight $i$ is ${v_i}$ . 2- Fraction of rows of weight $i$...
user51780's user avatar
  • 275
6 votes
0 answers
222 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
6 votes
0 answers
151 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 ...
azimut's user avatar
  • 253
6 votes
0 answers
298 views

Partitions of $\mathbb{F}_2^n$ related to perfect $1$-error correcting binary codes

Edit. After a computer search found an example for $n=8$, I've rephrased my original question as a conjecture. This question is motivated by the existence of perfect $1$-error correcting binary codes,...
Mark Wildon's user avatar
  • 10.8k
5 votes
0 answers
72 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
  • 530
5 votes
0 answers
196 views

Application of finding shortest paths on Cayley graphs

For a fixed integer number $m$, Consider Cayley graph defined by all m-cycles in Symmetric group $Sym(n)$. I know that for $m=2$, there are some applications of finding shortest paths (or distance ...
user75469's user avatar
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-...
Veit Elser's user avatar
  • 1,045
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 ...
Brendan McKay's user avatar
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\...
R B's user avatar
  • 608
4 votes
0 answers
382 views

Fully Homomorphic Error Correction?

Consider a field $F$. Suppose we have two vectors $a,b\in F^n$, and an invertible matrix $G\in F^{n\times n}$. Let $c\in F^n$ be the point-wise product of $a$ and $b$, that is, $c_i=a_ib_i$. Let $x=...
Bill Bradley's user avatar
  • 3,809
3 votes
1 answer
147 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
3 votes
0 answers
126 views

Cyclic codes: sparse codewords not orthogonal to the all-ones vector

Is it true that for any sufficiently large prime $p$, there exists a prime $q\ne p$ and a cyclic code of length $p$ over $\mathbb{F}_q$ that contains a codeword of Hamming weight at most ord$_p(q)$ ...
Jop's user avatar
  • 93
3 votes
0 answers
125 views

$\left< 15\right>^7/15$-womcode construction

In the article Womcodes constructed with projective geometries Frans Merkx constructed several good wom-codes (write-once memory codes, see How to reuse a "write-once" memory by Rivest & Shamir ...
Alexey Ustinov's user avatar
3 votes
0 answers
97 views

Applications of finite Bolyai-Lobachevsky planes

Google scholar gives more than 200 articles comcerning finite Bolyai-Lobachevsky (BL) planes. Usually they devoted to construction of such objects (axioms may be different). Are their any ...
Alexey Ustinov's user avatar
3 votes
1 answer
533 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 ...
Turbo's user avatar
  • 13.6k
3 votes
0 answers
228 views

On weight enumerators of codes

Are there $[n,k]_q$ constant rate $\frac kn$ and constant alphabet linear code families with automorphism group of size $\Omega((n-n^\beta)!)$ that have minimum distance $d=O(n^\alpha)$ and number of ...
Turbo's user avatar
  • 13.6k
3 votes
0 answers
115 views

Maximum number of $4$-cycles

Suppose we have a balanced bipartite planar maximum degree $k$ graph. How many such graphs on $2n$ vertices have at most $f(n)$ maximum number of $4$ cycles for a given function $f:\Bbb R^+\...
Turbo's user avatar
  • 13.6k
3 votes
0 answers
96 views

Bounding the number of information sets in a linear binary code

A pretty well-known theorem regarding linear $(n,k,d)$ codes is that every $n-d+1$ coordinate positions contain an information set, but not all $n-d$ coordinate positions do. This is equivalent to a ...
Benjamin Lindqvist's user avatar
3 votes
0 answers
113 views

Rank of a particular matrix

Denote $P_{2n}$ to be collection of homogeneous total degree $2$ real polynomials in exactly $2n$ variables such that coefficient of every monomial is either $1$ or $-1$. Split variable set into ...
Turbo's user avatar
  • 13.6k
3 votes
0 answers
268 views

Hamming weight probability of projections

Given $s,t\in(0,1)$, $c>1$, $n\in\Bbb N$, pick $2^{n^t}$ random vectors $\{v_i\}_{i=1}^{2^{n^t}}$ such that each $v_i\in\{x\in\{0,1\}^{2^n}:|x|_{hamming}={2^{n-n^s}}\}$. If $v_i^\perp$ is ...
Turbo's user avatar
  • 13.6k
3 votes
0 answers
224 views

On a problem of sphere-packing for Reed-Solomon codes

Suppose we have an $[n, k+1, n-k]$ Reed Solomon code $\mathcal C$ over $\mathbb F_q$, where $n-k=d$ is the minimum distance, and suppose that $d=2t+1$. We know that for every $r \in \mathbb F_q^n$ the ...
Sfarla's user avatar
  • 307
3 votes
0 answers
138 views

Applications of list decoding

This is citation from http://en.wikipedia.org/wiki/List_decoding: Algorithms developed for list decoding of several interesting code families have found interesting applications in computational ...
Alexey Milovanov's user avatar
3 votes
0 answers
138 views

Certain subgroup of automorphism groups of binary codes

Suppose that $C$ is an binary linear code of length $n$ and dimension $k$ (i.e. it's a $k$-dimensional linear subspace of $\mathbb{F}_2^n$). As usual, the automorphism group of $C$ is the subgroup of ...
Victor Miller's user avatar
3 votes
0 answers
229 views

Matrix where every subset of rows has maximal rank

I am looking for a class of matrices $M(n(m), m, k(m), \phi)$ with the following properties: M is $n \times m$ where $n(m) > m$. Every subset of rows of size $k$ has (maximal) rank $m$. $n(m)$ ...
aelguindy's user avatar
  • 343
3 votes
0 answers
147 views

Find polynoms f,g such that for any polynom p(x): |fp|+|gp|>= |f|+|g| ? Where |*| is number of non-zero monoms.

How to construct examples (describe all) polynoms f,g such that for any polynom p(x) not equal to zero: |fp|+|gp|>= |f|+|g| ? Where |*| is number of non-zero monoms (=Hamming weight, by the way it ...
Alexander Chervov's user avatar
2 votes
0 answers
83 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
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
2 votes
0 answers
181 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
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$...
lchen's user avatar
  • 459
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$)...
U. Haboeck's user avatar
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 ...
Shahrooz's user avatar
  • 4,738
2 votes
0 answers
652 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 ...
Avi's user avatar
  • 21
2 votes
0 answers
66 views

Linear-time logspace encodable error correcting code with constant

Is there a binary code with (quasi)constant rate, constant relative distance, and an encoder that takes (quasi)linear time and logspace simultaneously? Note that there are no constraints on ...
bean's user avatar
  • 479
2 votes
0 answers
256 views

3-uniform hypergraphs and their circuit space

So, I'll break this post into two questions. Both concern 3-uniform hypergraphs. A 3-uniform hypergraph $H=(V,E)$ consists of a set of vertices $V$ and a set of edges $E$, where each edge $e\in E$ is ...
anthony mann's user avatar
2 votes
0 answers
83 views

Packings with block size equal to $6$?

In design theory the following is the defintion of a packing : Definition : A $(v,k)$-packing is a pair $(V, \mathcal{B})$ of a finite set $V$ of cardinality $\vert V \vert = v$ and a finite set $\...
Elaqqad's user avatar
  • 203
2 votes
0 answers
129 views

Embedding a binary subspace to $l_2$ in a much lower dimension

I'm trying to find a way to embed a binary linear subspace of dimension $n$ (a linear code) to the Euclidian space while reducing the dimension significantly. The subspace (or code) contains points ...
GWB's user avatar
  • 181
2 votes
0 answers
263 views

Counting special metrics on finite fields

Define a Galois coding norm of degree n as a map $|\space| : \Bbb F_{2^n}\rightarrow {\Bbb Z}$ with the following properties : (I) $(\Bbb F_{2^n},|\space|)$ is a self-orthogonal code ; i.e. $(x,y)\...
Oliver Kayende's user avatar
2 votes
0 answers
73 views

Correspondence between information theoretic and coding theoretic language?

In information theory capacity or best rate achievement techniques are through showing existence if typical sequences of certain measure while in coding theory performance is measured by number of ...
Turbo's user avatar
  • 13.6k
2 votes
0 answers
121 views

Hamming weights of special vectors

The motivation of this question comes from number theory (I add the tag number theory for this reason, in that it is possible that someone with a number-theoretic background has already thought about ...
Ted90's user avatar
  • 21
2 votes
0 answers
111 views

The significance of the Parvaresh-Vardy curve

Even though this seems like a computer science question, it is purely mathematical and concerns polynomials and curves over finite fields. Consider the Parvaresh-Vardy list decoder. As I understand ...
BharatRam's user avatar
  • 939
2 votes
0 answers
95 views

On subset of Deterministic games

Denote strings $u,v$ from $\{0,1\}^n$. Denote concatenated pair $[uv]$. Denote $$[uv]_{1}=\{[uv]\oplus e_i\}_{i=1}^{2n}$$ collection of pairs with Hamming distance $1$ from $[uv]$ string ...
Turbo's user avatar
  • 13.6k
2 votes
0 answers
149 views

Looking for Camion - Abelian codes

I am looking for a copy of the old report "Paul Camion - Abelian codes", Technical Report 1059, University of Wisconsin 1971. I have asked Paul himself, but he could not help me. Anyone out there has ...
user38148's user avatar
2 votes
0 answers
586 views

Adjacency matrices of graphs as parity check matrices of error correcting codes

Consider bipartite graph. Consider its adjacency matrix. It will have a form 0 A^t A 0 Take matrix $A$. Consider the null-space $L$ of $A$ over $F_2^N$. Question Can we say something about the $...
Alexander Chervov's user avatar
2 votes
0 answers
287 views

Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric

Slight extension of cross posting from https://cstheory.stackexchange.com/questions/7408/lee-metric-gilbert-varshamov-and-hamming-bounds-for-larger-relative-distance-rang (closed there) The ...
user16007's user avatar
  • 780