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
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 ...
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 ...
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 ...
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 ...
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-...
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. ...
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$...
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 ...
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 ...
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,...
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$ ...
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 ...
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-...
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 ...
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\...
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=...
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)$....
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)$ ...
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 ...
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 ...
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 ...
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 ...
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^+\...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$ ...
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 ...
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 ...
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 &...
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 $...
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$...
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$)...
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 ...
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 ...
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 ...
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 ...
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 $\...
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 ...
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)\...
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 ...
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 ...
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 ...
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 ...
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 ...
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 $...
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 ...