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

242
questions

**8**

votes

**2**answers

225 views

### Maximum of the weighted binomial sum $2^{-r}\sum_{i=0}^r\binom{m}{i}$

Let $m$ be a positive integer and let $f_m(r)=2^{-r}\sum_{i=0}^r\binom{m}{i}$. Clearly $f_m(0)=f_m(m)=1$ and $f_{2r+1}(r)=2^{2r}$.
Conjecture: If $m>12$, then the maximum value of $f_m(r)$ for $r\...

**7**

votes

**0**answers

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

**2**

votes

**1**answer

69 views

### Low-Hamming weight vectors in low-dimensional subspaces of $\mathbb{F}_p^n$

What is the maximum number vectors of Hamming weight at most $w$ in a $d$-dimensional subspace of $\mathbb{F}_p^n$, where $w,d,p$ are constant and $p$ is odd. (The Hamming weight is the number of ...

**1**

vote

**1**answer

85 views

### Almost-parallel corners of the hypercube in high dimensions

Say I would like a collection of k "almost-parallel" boolean vectors $X_1,...,X_k \in \{\pm 1\}^n$, such that $(X_i,X_j)/n \approx 1-\epsilon$ for some small $\epsilon$. How many ways are ...

**1**

vote

**1**answer

59 views

### Simple non-asymptotic upper-bound for packing number of a hamming cube

Looking for a simple upper-bound for the packing number of hamming cube, I'm led to consider the following. Fix $p \in (0,1/2]$. For a positive integer $n$, define $S_n(p) := \sum_{i=1}^{\lfloor np\...

**2**

votes

**1**answer

103 views

### Are there any homomorphic analog error correction code?

Are there any analog error correction codes that are additively and multiplicatively homomorphic?

**5**

votes

**2**answers

221 views

### Maximum number of vectors with upper bound on pairwise inner products

I have a collection $\{v_1,...,v_k\}$ of vectors in $\{\pm 1\}^n$ with the property that for all $i\neq j$ we have $\langle v_i, v_j \rangle \le c\log_2(n)$. I am looking for an upper bound on $k$ in ...

**1**

vote

**1**answer

160 views

### Upper bounds for high-dimensional spherical codes given the covering radius

I assume that this sort of question has already been considered at great length. Nevertheless, I could not find an answer to this question in the related literature.
Given a constant $a\in (0,2]$, ...

**1**

vote

**0**answers

72 views

### A variant of Huffman code

Given an alphabet of $n$ symbolswith probabilities $p_i$ for symbol $i$, we need to encode the symbols (in a prefix-free way) to binary codewords $c(i)$ with length $\ell(c(i))$ to minimize the ...

**1**

vote

**1**answer

85 views

### error correcting huffman code [closed]

I am looking for a code that can correct errors with variable and limited length like huffman code. I am not an expert in coding theory. Is there any code or related literature on this?

**2**

votes

**0**answers

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

**6**

votes

**0**answers

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

**8**

votes

**1**answer

190 views

### Perfect sphere packings (as opposed to perfect ball packings)

I came across this question when I was discussing the rather wonderful Devil's Chessboard Problem with my colleague, Francis Hunt.
We realised that there is a nice connection to a packing question in $...

**8**

votes

**1**answer

169 views

### Weight enumerator classifiers

Let $f(x,y)$ be a polynomial with integer coefficients. What conditions guarantee that this is the weight enumerator of a binary linear code of size $n$ and dimension $k$?
I’m almost certain that the ...

**6**

votes

**1**answer

130 views

### Characterization of metrics such that the volume of balls doesn't depend on their centers?

Given a finite metric space $(X,d)$,
when does it hold that for all $y\in X$ and $r>0$, $\#B(y,r)$ does not depend on $y$?
Here $ B(y,r):=\{x\in X: d(x,y)\le r\} $ denotes a ball of radius $r$ ...

**2**

votes

**1**answer

73 views

### Strong Data Processing Inequality for capped channels

Let $X$ and $Y$ be two $\rho$ correlated Gaussian vectors, such that $X,Y\sim N(0,1)^n$ and $E[X_iY_i]=\rho$.
Let $M_X = f(X)$ and $M_Y = f(Y)$ be $k$-bit functions of $X$ and $Y$, that is $H(X)=H(Y)=...

**3**

votes

**0**answers

114 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)$ ...

**1**

vote

**1**answer

278 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 \{ ...

**2**

votes

**1**answer

205 views

### Is this model of converting integers to Gray code correct?

The model shown in the figure converts all numbers that have k digits in the binary system to Gray code without any calculation, but I have no proof that guarantees this claim.
Here is some ...

**12**

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

**2**

votes

**1**answer

177 views

### Every element of $A$ and $B$ differ in at least $k$ positions

Let $m,n$ be positive integers, $m,n>1$ and $X = \{(x_1,x_2, ..., x_m) \in \mathbb{Z}^m :1 \le x_i \le n, \forall 1 \le i \le m\}$.
$A$ and $B$ are two disjoint subsets of $X$, such that if $a \in ...

**1**

vote

**1**answer

166 views

### Ternary error correction codes

Let`s define ternary ECC as a code that its codewords can be defined by $ \{ xyz f(y,z) f(x,z) f(x,y) | x,y,z \in \{0,1\}^m \} $ for some function $f$. $f$ returns bitstring of constant length.
...

**2**

votes

**0**answers

34 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

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

**4**

votes

**2**answers

208 views

### Lower bounding decoding error in a noisy adversarial channel

Problem description
Suppose we have a finite alphabet $\mathcal{X}$, where each letter $X \in \mathcal{X}$ indexes into some fixed set of distributions, $\{P_{1},\ldots,P_{|\mathcal{X}|}\}$. For ...

**4**

votes

**1**answer

325 views

### How do I check if two linear binary codes are equivalent?

Suppose I have a list of generator matrices $G_i$, $i=1,\ldots N$, of the same size (each defines an $n$-bit linear binary code encoding $k$ logical bits).
I consider two codes to be equivalent if ...

**2**

votes

**0**answers

76 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 $\...

**1**

vote

**0**answers

77 views

### On sparse $0/1$ linear equations solvable with compressed sensing

If you have a system of $m$ linearly independent equations in $n$ variables with domain $0/1$ and we know there is at least one solution with at most $d$ variables to be $1$ then if $m$ at least a ...

**2**

votes

**0**answers

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

**4**

votes

**2**answers

348 views

### When can this condition on linear codes be satisfied?

It would be useful to me to have a result of the following kind (which I would need to generalize, but this case is already interesting). Let $r<n$ be positive integers and let $\delta>0$ be a ...

**6**

votes

**1**answer

227 views

### Guessing the number of other $1$'s in a binary sequence

I have posed the following question on math.stackexchange.com but have not received an answer. So I would like to seek experts' opinion here.
Consider the set of all binary sequence of length $n+1$, $...

**2**

votes

**0**answers

168 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)\...

**1**

vote

**0**answers

76 views

### Strategy of Responder in Rényi Ulam Liar Games

I tried posting this in Math Stack Exchange but got no responses, so I figured I could try my luck here. My main concern is that I can't figure out how to get started on my "research" (bear with me, I'...

**3**

votes

**0**answers

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

**26**

votes

**2**answers

2k 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$. ...

**6**

votes

**1**answer

269 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} | \...

**2**

votes

**0**answers

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

**0**

votes

**1**answer

135 views

### Shortest possible good codes?

Good codes (those with positive rate $r=k/n$ and positive relative distance $\delta=d/n$) will achieve capacity on $BSC$ (binary symmetric channel) if the codes have lower rates than capacity where ...

**4**

votes

**1**answer

107 views

### Polynomial time decodable binary linear codes achieving $GV$ bound?

Are there explicit or random construction of linear codes that achieve the $GV$ bound with polynomial time decodable property with alphabet size $q=2$?
Tsfasman, Manin, Vladut beat the bound at ...

**6**

votes

**1**answer

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

**2**

votes

**1**answer

221 views

### Partitioning $\{0,1\}^n$ into $n$ sets

I am working on an answer to the question
Magic trick based on deep mathematics
and came across the following problem: I am trying to partition the cube $\{0,1\}^n$ into $n$ sets $P_1,\dots,P_n$ ...

**4**

votes

**2**answers

128 views

### Are cyclic codes bounded by a continuous function?

In coding theory, we know that if you take the function
\begin{equation}
\alpha_q(\delta) := \limsup_{n \rightarrow \infty} \ \max \{ R(C) \mid \delta(C) \ge \delta \mid C \subseteq \mathbb{F}_q^...

**6**

votes

**1**answer

426 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 \...

**1**

vote

**0**answers

54 views

### Spherical code for interesection of $k$-sparse vectors and unit sphere

Let us assume $X\in\mathbb{R}^{n\times d}, rank(X)=d$, integer $k\in\mathbb{N},k\ll d$, positive constant $0<\epsilon<1$, and $\mathcal{S}\subset \mathbb{R}^d$ denotes the unit sphere. We also ...

**1**

vote

**0**answers

127 views

### Error correcting codes via random matrices: How close to the Shannon bound?

I have a vague and probably rather naive question on error correcting codes.
Suppose we want to encode binary vectors of length $k$ as binary vectors of length $n$ in such a way that differences of ...

**6**

votes

**2**answers

227 views

### Nonlinear boolean functions

Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements. I wonder if there is any known algorithm/construction that, given any $n\geq 1$, returns a boolean function $f:\mathbb{F}^n_2\rightarrow \...

**14**

votes

**0**answers

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

**13**

votes

**0**answers

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

**4**

votes

**1**answer

201 views

### Why the dimension of bch code is unknown?

My professor told me that dimension of bch code is unknown in general, so I made a loop in SAGEMATH that create a BCH code of length $p^m-1$ over $GF(p)$ with every possible designed minimum distance $...

**2**

votes

**1**answer

233 views

### How to recover $k$ lost items in binary data $x_1,x_2,x_3 \dots,x_n$ via only XOR operator?

I asked this question in math.stackexchange (link) and I have had an answer for general case by using Reed-Solomon Code. More information for Reed-Solomon Coding for Fault-Tolerance in RAID-like ...