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".
22
questions
29
votes
2
answers
3k
views
Is there a Kolmogorov complexity proof of the prime number theorem?
Lance Fortnow uses Kolmorogov complexity to prove an Almost Prime Number Theorem (https://lance.fortnow.com/papers/files/kaikoura.pdf, after theorem $2.1$): the $i$th prime is at most $i(\log i)^2$. ...
- 13.7k
13
votes
3
answers
2k
views
Hot-topics in error correcting coding related to interesting math. ?
What are topics in error-correcting coding which are related to interesting math. ?
I am primarely interested in nowdays hot topics, but old days topics are also welcome.
Let me try to mention what ...
6
votes
3
answers
575
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 ...
- 1,985
9
votes
1
answer
599
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$ ...
- 284
35
votes
1
answer
3k
views
"The Two Sheriffs" puzzle
This puzzle is taken from the book Mathematical puzzles: a connoisseur's collection by P. Winkler.
Two sheriffs in neighboring towns are on the track of a killer, in a
case involving eight ...
- 11.9k
22
votes
1
answer
1k
views
Codes, lattices, vertex operator algebras
At the end of "Notes on Chapter 1" in the Preface to the Third Edition of Sphere packings, lattices and groups, Conway and Sloane write the following:
Finally, we cannot resist calling attention to ...
- 2,130
14
votes
1
answer
1k
views
Hamming distance to primes
There is a positive density of odd numbers which are of the form $2^n+p$ (due to Romanoff), and a positive density which are not of this form (due to van der Corput and Erdos, see this paper for a ...
- 286
12
votes
2
answers
617
views
“The Two Sheriffs” puzzle -2: threshold for security
I've already asked a question “The Two Sheriffs” puzzle with wrong assumption. Yoav Kallus in his amazing answer using Fano plane showed that the problem has a solution in the case of seven suspects.
...
- 11.9k
10
votes
4
answers
3k
views
"sparse graphs are locally tree-like"
I would like to be able to state with confidence that sparse graphs (graphs with small numbers of edges) are locally tree-like (they have few short cycles). Apparently "Sparse graphs are locally tree ...
- 101
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 ...
- 1,362
6
votes
3
answers
420
views
On the rank of a matrix $S$ with coefficients in $\mathbb F_{2^m}$
Let $\mathbb F$ be a finite field with characteristic 2 and let $S \in M(2k, 2k, \mathbb F)$ be the matrix defined as follows
$$ S=\left[\begin{array}{ccccccc}
0 & \...
- 307
6
votes
1
answer
368
views
Enumeration of field generators of a finite field over $\mathbb{F}_{q}$, which are $m^{th}$ powers in the same field
Consider the finite field extension $\mathbb{F}_{{q}^{d}}$ over $\mathbb{F}_{q}$, where $q=p^a$ for some prime $p$. We assume $d\geq 2$. Let,
$$ S=\{ \alpha \in \mathbb{F}_{q^d}\hspace{0.1 cm} | \...
- 430
6
votes
0
answers
300
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,...
- 10.8k
5
votes
1
answer
175
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 {\...
- 1,096
3
votes
1
answer
3k
views
Cyclic Hamming Code
I know that Hamming codes can be arranged in cyclic form. But my question is how can I prove this.
My idea was to find a generator/primitive polynomial $p(x)$?
For example I want to show that the $[...
- 31
3
votes
1
answer
149
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)$....
- 31
2
votes
2
answers
272
views
Need help with paper written in Russian... Yorgov's paper on self-dual codes with automorphisms of odd order
I came across this paper by V.I.Yorgov named "Binary self-dual codes with automorphisms of odd order". (Actually I was first reading another paper by Borello that cited this paper. It later become ...
- 165
1
vote
2
answers
286
views
How many k-nomials of deg N divisible by X^16+x^12+x^5 +1 ? (Spectrum of CRC-16-CCITT erroc-correcting code ?)
Let us consider polynoms over $F_2$.
Consider the linear SUBSPACE of polynoms divisible by $x^{16}+x^{12}+x^5 +1$ and of degree less or equal $N$ (e.g. 40).
Question: How many k-nomials belong to ...
1
vote
2
answers
524
views
Is this general form of Lovasz theta function of circulant graphs?
Let $G$ be a cirulant graph with no loops at vertices and vertex degree $d$. Is the Lovasz theta function of this graph given by:
$\vartheta(G) = \max_{i}\frac{-N\epsilon_{i}}{-\epsilon_{i}+d-1}$?
...
- 13.7k
1
vote
0
answers
172
views
Null Space of Parity Check Matrix
We know that if $\alpha$ be s a primitive element of $F_q$ where $q$ is a prime power then the null space of the following matrix generates a cyclic code of designed distance $\mu$[1].
$$
G_{\alpha}^{...
- 325
1
vote
1
answer
331
views
Mutual information staying constant under composition of channels
Consider the following scenario: one has 2 communication channels $C_1$ and $C_2$. Denote by $p(x)$ the input probability distribution.
The mutual information between the input and the output of $C_1$...
- 163
0
votes
1
answer
218
views
Multiplication by polynomials x^2+1 ; x^2+x+1. Does minimal Hamming norm of image equal to 5 ?
Everything over F_2. Let us define Hamming norm of polynom |p(x)| = number of non-zero monoms.
Respectivly for a pair of polynoms |[p ; g]| = |p| +|g|.
Consider linear map $F_2[x] \to F_2[x] \oplus ...