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

**4**

votes

**2**answers

115 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

153 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

40 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

96 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

181 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

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

**12**

votes

**0**answers

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

**0**

votes

**0**answers

97 views

### Unicity of punctured Hadamard codes in terms of maximum distance

Let $n>2$ and assume that a binary linear code of length $n$ has MAXIMUM distance $D\leq (n+1)/2$. Assume that all coordinates of the code are essential in the sense that some codeword is 1 there.
...

**3**

votes

**1**answer

138 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

167 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

376 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

47 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

66 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

92 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

102 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

124 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

180 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

430 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

329 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

90 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

194 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

135 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

74 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

136 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

77 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

26 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

78 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

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

**5**

votes

**3**answers

269 views

### Request for reference for some proofs about Gowers' norm

For any map $f : \mathbb{F}_2^n \rightarrow \mathbb{C}$ we define its $d^{th}-$Gowers' Norm (for $1 \leq d \leq n$) as, $\|f\|_{U^d(\mathbb{F}_2^n)}^{2^d} = \mathbb{E}_{L : \mathbb{F}_2^d \rightarrow \...

**15**

votes

**3**answers

299 views

### Is primality essential in Varshamov's bound?

Let $v_q(n,r)=\sum_{i=0}^r \binom{n}i (q-1)^i$ denote a number of points in a ball of radius $r$ in the Hamming metric on the cube $\Sigma^n$, where $|\Sigma|=q$. What is the maximal number of points ...

**3**

votes

**1**answer

61 views

### Certain Integer Sets of Elements with Common Hamming-weight Preserving Integer Function

In a meanwhile deleted question I had mentioned my observation, that $$H\left(2^m-1\right) = H\left(3*(2^m-1)\right) = H\left(3*(2^m-1)\ +\ 1\right)$$
where $H()$ denotes the Hamming weight.
...

**7**

votes

**1**answer

68 views

### Codes with a twisted cyclic action

Are there interesting examples of linear binary codes that are closed under the operation of removing the first bit of the codeword and appending the complement of that bit to the end of the codeword?

**2**

votes

**0**answers

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

**4**

votes

**1**answer

92 views

### Counting overlaps for $n$ Boolean vectors in a Hamming ball of radius $r$

Say I have set of $m$ Boolean vectors $$B = \{x_1,\ldots, x_m\}$$ where $x_i \in \{0,1\}^n$.
We know the following about the vectors $x_i \in B$:
(i) $\|x_i\| \in [1,n-1]$ for all $x_i \in B$ (at ...

**5**

votes

**1**answer

138 views

### Binary codes with length and distance a power of 2

Let $A_2(n,d)$ denote the maximum number of words in a binary code (not necessarily linear) with length $n$ and distance $d$. The value of this function is not known in general, though there are ...

**3**

votes

**1**answer

64 views

### Binary linear codes, juxtaposition and similarity

My question is about binary linear codes and some properties which are fairly straightforward but I don't know whether there is a name for in the literature. I haven't been able to find anything on ...

**1**

vote

**0**answers

95 views

### Known results about maximum size of a code with minimum hamming distance K

Let $W(r,n)$ be the set of all words of length $r$ on $n$ letters.
For two words $a,b \in W(r,n)$ define the Hamming distance $d(a,b)$ as the number of places that they have different letters.
Let ...

**1**

vote

**0**answers

60 views

### Recursive method to construct self-dual codes

I'm looking for the recursive methods of constructing self-dual binary codes. Recently, I found an interesting way to constructing such codes here. In this method, by using $[2n,n,d]$ self-dual code, ...

**4**

votes

**2**answers

392 views

### How to quantify the error correction capacity of LDPC code?

As shown in title, I am studying the LDPC code recently. However, I still can not calculate the error correction capacity of it, maybe due to complex decoding algorithm. And there lacks easy ...

**2**

votes

**2**answers

269 views

### On a number theoretic problem coming from multiuser coding?

Can Chinese remainder theorem be used to solve this problem in multiuser coding?
We have two transmitters sending integers $q,q'>0$ to a common receiver. The duty of the receiver is to recover ...

**0**

votes

**0**answers

30 views

### how to analysis the symbol error rate considering different modulation method and error correction code?

The question is the title:
how to analysis the symbol error rate considering different modulation method and error correction code?
Actually, I am also asking how can we beat the efficiency against ...

**4**

votes

**2**answers

173 views

### LDPC codes construction

According to Google Scholar original Gallager's article Low-density parity-check codes is cited more than 10000 times. It looks scary for non-experts.
I suspect that the number of algorithms for ...

**4**

votes

**1**answer

395 views

### Backwards random codebook generation

$$X \longrightarrow \fbox{$\phantom{\int}P_{Y|X}\phantom{\int}$}\longrightarrow Y$$
The information capacity of this channel is $C=\max_{P_X} I(X;Y)$, and it can be achieved by associating each ...

**3**

votes

**1**answer

118 views

### Binary subspace membership testing with signed vectors

Say we are working in $\mathbb{F}^{2n}_2$ where vectors can be written as pairs $(a,b)$ with $a,b \in \mathbb{F}^{n}_2$. Given a list of basis vectors for an $n-1$ dimensional subspace $S \subset \...

**27**

votes

**1**answer

1k views

### What is the name of this combinatorial object and place to read about it?

The title is admittedly noninformative but I could not figure out how to squeeze into it the description of the object I am interested in. Judge by yourself.
I have an alphabet on $d$ symbols. I want ...

**1**

vote

**1**answer

129 views

### A polynomial recovery problem

Suppose we know $deg(m(x))=n-1=deg(f_1(x))=deg(f_2(x))$.
Suppose we know $C_1(x),C_2(x)$ where $deg(C_i)=n$.
Then given $n$ values of $$C_1(x)(x+1)m(x) +C_1(x)(x+2)f_1(x)\in\Bbb F_q[x]$$ and $n$ ...

**2**

votes

**0**answers

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

**4**

votes

**2**answers

265 views

### Self-dual binary codes of Hamming weight divisible by 8?

Recall that a binary code is a subgroup $C \subset \mathbb F_2^n$; the elements of $C$ are called code words. The Hamming weight of a code word $c\in C$ is the number of $1$s in it. A binary code is ...

**0**

votes

**0**answers

72 views

### The effect of channel error on the determinant of transmitted matrix

Assume the following matrix
$$
E:=\left(
\begin{array}{ccccc}
e_1 & e_2 & \cdots & e_{p-1} & e_{p}\\
e_{p+1} & e_{p+2} & \cdots & e_{2p-1} & e_{2p} \\
\...

**1**

vote

**0**answers

128 views

### When can a binary matrix be transformed into a certain form

I have a $k \times n$ matrix $G$ over ${\mathbb F_2}$ that's full rank.
This can always be put in systematic form : $G \sim [I_k \mid P]$ where $I_k$ is a $k \times k$ identity matrix and $P$ is a $k \...