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

224
questions

**2**

votes

**1**answer

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

**1**

vote

**1**answer

116 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

24 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

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

**3**

votes

**2**answers

195 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

112 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

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

**0**

votes

**0**answers

26 views

### Algorithm for constacyclic codes

I am asking if there is a decoding algorithm for the constacyclic codes. I know many decoding algorithm for cyclic codes but i didn't found any result

**2**

votes

**0**answers

95 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

269 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

222 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

139 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

67 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

109 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

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

**3**

votes

**1**answer

179 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

61 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

124 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

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

**0**

votes

**0**answers

21 views

### Can I find such an encoding scheme so that I can eliminate certain rows of a vector?

Given a secret binary vector B=$\left( {\begin{array}{*{20}{c}}
{{b_0}}\\
{{b_1}}\\
\vdots \\
{{b_{n-1}}}
\end{array}} \right)$, and a public uniformly random matrix $A = \left( {\begin{array}{*{20}{...

**6**

votes

**1**answer

168 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

209 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

384 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

51 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

117 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

202 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

283 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

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

**3**

votes

**1**answer

194 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

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

**6**

votes

**1**answer

396 views

### Minimum number of operations necessary to arrive at any configuration

Let $k \geq 2$ and $N_1, N_2, ..., N_k$ be positive integers.
Let $S=\{(a_1,a_2,...,a_k) \in \mathbb{Z}^k:1 \leq a_i \leq N_i\}$ and $A=\{1,2,...,\prod_{i=1}^{k} N_{i}\}$.
Given a bijective map $f:...

**1**

vote

**1**answer

59 views

### An Extension of an $\operatorname{MDS}$ Code over $\operatorname{GF}(2^q)$

Let $q$ be a power of $2$.
Assume that elements of the finite field $\operatorname{GF}(q)$ are denoted by $\beta_i$
for $0\leq i \leq q-1$. We divide elements of $\operatorname{GF}(q)$ in two parts ...

**1**

vote

**0**answers

71 views

### How can I compute minimal distance of the AG-code on the Hirzebruch surface $\mathbb{F}_3$?

Let $\mathbb{F}_3$ be the Hirzebruch surface (with index $3$) over a finite field $\mathbb{F}_q$ and $\pi\!: \mathbb{F}_3 \to \mathbb{P}^1$ be the unique $\mathbb{P}^1$-fibration on $\mathbb{F}_3$. ...

**3**

votes

**1**answer

96 views

### How many length-24 Type III codes have no words of Hamming weight 3?

From W. Cary Huffman (2005), On the classification and enumeration of self-dual codes, Finite Fields and Their Applications
11(3) pp 451-490, I learn that there are at least 140 Type III codes of ...

**2**

votes

**1**answer

106 views

### Importance of the $2^{\tau(G)}\leqslant A(n,g(G))$ conjecture

During a course about finite dynamical systems the following conjecture was presented to us :
Let G be a directed graph of order n.
Let $\tau(G)$ be the minimum size of a subset of $V(G)$, $I$ ...

**5**

votes

**1**answer

242 views

### Explicit Formula of Delsarte's Linear Programming Upper Bound for $A_q(n,3)$

The problem of giving an explicit formula for $A_q(n,d)$ is sometimes referred to as "the main problem in coding theory." The value of $A_q(n,d)$ is given by the maximum number of codewords in a q-ary ...

**1**

vote

**0**answers

185 views

### On discrepancy properties of $\{0,\pm1\}$ sequences arising from cyclotomic polynomials

Given $n=2^k p^r q^m$ take a $d\in\Bbb Z$ with $d\mid n$ such that each $a_i$ is in $\{0,\pm1\}$ in $$f_{d,n}(x)=\frac{x^n-1}{\Phi_d(x)}=a_0+a_1x+\cdots+a_{\deg(f_{d,n}(x))}x^{\deg(f_{d,n}(x))}.$$
...

**4**

votes

**3**answers

543 views

### Application of simple Lie algebras over finite fields

I am now interested in simple Lie algebras over finite fields. In Lie algebras over the complex numbers, there are several applications and some related topics.
Is there any potential application for ...

**6**

votes

**1**answer

363 views

### Binary weight of shifted integers

Suppose $n_2$ denotes the binary representation of the integer number $n$. Let $X_2(n)=[1_22_2\ldots n_2]$,$n\geq3$, be a binary vector which is obtained by concatenating of binary representation of ...

**3**

votes

**1**answer

120 views

### Computing the decimation ratio between two m-sequences

Let's suppose I have an LFSR that generates an m-sequence $y_1[k]$ --- in other words, the LFSR has $N$ bits and $y_1[k]$ has period $m=2^N - 1$.
Now suppose I know someone has decimated this and ...

**8**

votes

**3**answers

206 views

### Minimal number of n/2-subsets of [n] that contains every d-subset

Let $d , n$ be positive integers such that $d < n/2$. Consider collections $\mathcal{F}$ consisting of subsets of $[n] = \{1,2,\ldots, n\}$ of size $n/2$. Question: what is the minimal size of a ...

**1**

vote

**1**answer

143 views

### On Shannon information theoretic capacity to coding distance metric translation

Shannon theory says that given a channel source variable $X$ and received variable $Y$ and channel $Y/X$ there is a capacity associated with this channel.
The notion of maximum likelihood leads from ...

**1**

vote

**0**answers

110 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}^{...

**2**

votes

**1**answer

153 views

### “Sparse” Theta Series

The number of integer points with a given norm in the integer grid $\mathbb{Z} \times \mathbb{Z}$ may be calculated via the generating function
$$\theta_3(q)^2= \left(\sum_{n \in \mathbb{Z}} q^{n^2}\...

**3**

votes

**1**answer

78 views

### Source coding lexicographic index of finite alphabet sequence with weight (partitions)

My goal is to determine the lexicographic index of an $M$-ary $n$-sequence $\mathbf{x}$ on the subset with an $M$-weight sum constraint:
$$S = \{ \mathbf{x} \in \{0, \ldots, M-1\}^n: \sum_{j=1}^n x_j =...

**1**

vote

**0**answers

32 views

### Optimal Encoding of Sets with DeBruijn-likeSequences

A DeBruijn sequences of order $n$ encodes all possible strings of length $n$ over an alphabet with $k$ symbols and algorithms for their construction are well known among those familiar with the ...

**3**

votes

**0**answers

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

**2**

votes

**1**answer

134 views

### How to encode subgraphs as hyperedges

Hi i was reading a paper "Propagating Distributions on a Hypergraph by Dual Information Regularization by Koji Tsuda", and one section stood out to me.
hypergraphs have more flexibility
in ...