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".
310 questions
4 votes
1 answer
266 views
On the number of $0$-$1$ vectors with pairwise distinct sums $v_i + v_j$
Let $n \ge 1$. A set of vectors $v_1, \ldots, v_m \in \{0,1\}^n$ is called admissible if all pairwise sums $v_i + v_j$ (with $1 \le i \le j \le m$) are distinct. We want to find the number $a(n)$, ...
- 13.5k
1 vote
0 answers
84 views
Packing real vectors at a fixed minimal angle
Let $\alpha$ be an angle contained in $(0,\pi/2]$ -- to fix ideas, let $\alpha = \pi/3$. Then with $d > 1$ a positive integer, what is a minimal bound $M_d(\alpha)$ for the maximum number of ...
- 4,791
1 vote
0 answers
90 views
How to give an efficient mappings for Hamming Distance?
Problem Statement: Consider two parties, a Sender holding a binary vector $s_1 \in \{0,1\}^d$ and a Receiver holding a binary vector $r_1 \in \{0,1\}^d$, where $d$ is the dimension and $\delta \geq 1$ ...
- 19
9 votes
0 answers
555 views
Is it hard to decide if two codes have the same weight enumerator polynomial?
Consider the following decision problem, which we will call COMPARE. We are given as input a pair $(V_0, V_1)$ of linear codes in $\mathbb{F}_2^n$, and asked to decide whether $V_0, V_1$ have the same ...
- 401
0 votes
0 answers
222 views
Combinatorial code design
I would like to know the feasibility of the following linear programming problem related to coding theory. Given a natural number $d$, binary entry matrix $X:=[x(i,j)\in B],\ B:=\{0,1\},\ i\in B^d,\ j\...
- 2,363
1 vote
0 answers
77 views
Smallest eigenvalue of the Caley graph over $F_3^n$ generated by balanced vectors?
A related post was already put here by me. But no comment received. So I decided to try my luck again here. Let $F = \{0,1,2\}$ be the ternary finite field. A vector $v \in F^n$ is balanced if each of ...
- 111
1 vote
1 answer
223 views
Evaluating the weight enumerator polynomial at special points
Let $C\subseteq\mathbb{F}_2^n$ be a linear code and let $P$ be the corresponding weight enumerator polynomial. That is, $$P(x)=a_nx^n+\cdots+a_1x+a_0$$ where, for $0\leq j\leq n$, we have $a_j:=\#\{v\...
- 401
5 votes
1 answer
308 views
Hardness of comparing weight partitions of an affine space over $\mathbb{F}_2$
Let $A$ be an affine subspace of $\mathbb{F}_2^n$. Let $m\leq n$ and $Q_0, Q_1$ be linear maps $\mathbb{F}_2^n\rightarrow\mathbb{F}_2^m$. Consider the following decision problem: Decide whether or not ...
- 401
3 votes
0 answers
121 views
Volume Inequality in Hamming Ball with Total Variation Constraint
Here is an interesting inequality that is simulated to be correct but I can not prove it. Can someone helps me? The question is that: For any binary vector $\mathbf{y}\in\{0,1\}^n$, prove that \begin{...
- 31
0 votes
0 answers
55 views
$q$-ary moments of finite affine space
$\;\;\;\;$ Fix a prime $p$, fix a power $q:=p^\aleph$, and consider the action of the Frobenius ring automorphism $\Psi:\vec{x}\mapsto\vec{x}^p$ on the product ring $\Bbb F_{q^m}^{(n)}:=\Bbb F_{q^m}\...
- 173
1 vote
1 answer
158 views
Global constraint to uniquely recover the boundary $1$’s in a binary sequence
Consider a binary sequence $$\mathbf{x}= \left ( x_{1}, x_{2}, \ldots, x_{n} \right ), \quad x_{i}\in\left \{ 0, 1 \right \}$$ and suppose that the total number of $1$’s in the sequence is known. ...
- 161
1 vote
1 answer
150 views
Method of constructing nonlinear codes. Nordstrom-Robinson code and its shortened versions
I will first explain this method in detail using a trivial example, then I will give examples of known nonlinear codes. 1. Trivial example. 1.a. Consider a linear code with a generating matrix ...
- 281
0 votes
0 answers
72 views
How to calculate hard and soft Shannon limit for BI-AWGN channel under BPSK modulation?
guys, I'm reading the book `Channel Codes:Classical and Modern' by W.E.Ryan and Shu Lin, in paper 15, there is an figure which gives out the hard and soft capacities curve for BI-AWGN channel, as ...
- 451
12 votes
1 answer
543 views
Collection closed under symmetric difference and translation
Basically my question is the following. Suppose $\mathcal{H}$ is a collection of finite subsets of the natural numbers (containing at least one non-empty set) closed under symmetric difference and ...
- 731
1 vote
2 answers
409 views
What is the mixed-radix numeral system of best radix economy?
Radix economy concerns itself with the efficiency of encoding numbers. For positional number systems that use a fixed base, base three is the most efficient choice among the integers, and $e$ is the ...
- 111
3 votes
0 answers
201 views
Efficient computation of $x^n \bmod g(x)$ in $\mathbb{F}_2[x]$
Related to this question. I wish to compute $x^n \bmod g(x)$ in $\mathbb{F}_2[x]$ for some fixed and known upfront $g$. This problem pops up in computing the 'pure' CRC function of a bit sequence of ...
- 139
8 votes
1 answer
214 views
Pick a homogeneous set of size $n$
Assume that the natural numbers have been colored with two colors: lavender and periwinkle. You don't know the coloring. You may sample as many (possibly overlapping) sets of size $n$ as you would ...
- 403
1 vote
0 answers
86 views
Generalized Hamming weights for binary BCH codes
Cross posting from MSE. I think it might be a good fit here. Given a linear binary code $C$, the $r$-th generalized Hamming weight $d_{r}(C)$ is the minimal support size of an $r$-dimensional subcode ...
- 235
0 votes
0 answers
121 views
Extension of automorphism of shift of finite type
$\DeclareMathOperator\Aut{Aut}$Let $X$ and $Y$ be two subshifts of finite type and $X\subset Y$, and $\phi:X\rightarrow X$ be a homeomorphism commuting with the shift map. Is there any homeomorphism $\...
0 votes
0 answers
162 views
Is there an inner product on $\mathbb{F}_p\left[S_n\right]$ for which $\langle x, x \rangle \ne 0$ for all $x$?
Let $\mathbb{F}_p\left[S_n\right]$ be the group algebra of the symmetric group $S_n$ over the finite field $\mathbb{F}_p$. One can define an "inner product" in the usual way: $$\langle x,y \...
- 591
6 votes
2 answers
279 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$ ...
- 549
5 votes
1 answer
353 views
What are bit strings where all non-trivial rotations match at a minimum number of places called?
Basically, I'm trying to figure out the name of the thing I want to look up. All the terms I've looked up so far have been related, but not close enough to be useful. I'm trying to find bit strings ...
- 205
3 votes
3 answers
472 views
Maximal set of $n$-bit strings that does not span $\mathbb{R}^n$
I am trying to find out the maximum-sized subset $S\subseteq \{0,1\}^n$ of $n$-bit strings that does not span $\mathbb{R}^n$. It is easy to show that $S$ has size at least $2^{n-1}$ when $S$ exactly ...
- 45
4 votes
1 answer
339 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)$....
- 41
2 votes
0 answers
126 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 ...
- 211
4 votes
1 answer
338 views
Binary codes with upper and lower bound on pairwise distance
The Gilbert-Varshamov bound provides a lower bound for codes of length $n$ with minimum pairwise distance (say $\frac{n}8$). If we wish for the codes to also have pairwise distances bounded above (say ...
- 141
1 vote
0 answers
160 views
Generalization of error-correcting codes
If you have a binary single-error correcting code with n-bit codewords, then it is the case that taking only a fixed n-1 out of the n bits gives an “approximate” code with the property that, for any ...
- 847
2 votes
2 answers
265 views
Perfect 1 error correcting codes non-isomorphic to Hamming codes?
In this question about perfect 2 error correcting codes on the Open Problem Garden, it is stated that: Recent research activity has discovered a large number of previously unknown perfect 1-error ...
- 10.6k
1 vote
0 answers
95 views
Progressions in finite fields with bounded hamming weight
Given $k\ge 2$ and an additive set $S$ (understood to live some implicit group $G$), define $$\Delta_k(S) := \left\{ d \in G: \bigcap_{i=1}^k (S+i\cdot d) \neq \emptyset \right\} $$(i.e., this is the ...
- 3,509
6 votes
0 answers
162 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-...
- 1,173
0 votes
1 answer
231 views
Does the Plotkin bound mean that one can not achieve the Singleton bound asymptotically?
I am a little confused with the relationship between various bounds for error correcting codes. Does the Plotkin bound mean that one can not achieve the Singleton bound asymptotically? That is, is ...
- 21
3 votes
1 answer
280 views
Maximum cardinality of separated sets in the Hamming distance
This question is motivated by section 15.1 (Codes) of Alon and Spencer's The probabilistic method. Fix $\alpha<\frac{1}{2}$ and for each $n\in\mathbb{N}$ let $\{0,1\}^n$ be the length $n$ binary ...
- 12.9k
4 votes
2 answers
394 views
Concentration of minimum Hamming distance between $N$ points sampled iid from uniform distribution on $n$-dim hypercube $\{0,1\}^n$
Let $n$ be a large positive integer. Sample $N \ge 2$ points $x_1,\ldots,x_N$ iid from the uniform distribution on the $n$-dimensional hypercube $\{0,1\}^n$. Define the gap $\delta_{N,n} := \min_{i \...
- 7,033
1 vote
1 answer
83 views
Weight of a codeword in a cyclic code as a function of the number of solutions of an equation involving the trace function
Let $q = p^s$ and $r = q^m$, where $p$ is a prime, $s$ and $m$ are positive integers. Let $N>1$ be an integer dividing $r - 1$, and put $n = (r - 1)/N$. Let $\alpha$ be a primitive element of $\...
- 219
1 vote
1 answer
173 views
On the existence of symmetric matrices with prescribed number of 1's on each row
We are considering the following problem: Given an integer $n$ and a sequence of integers $r_i,\ 1\le i\le n$, with $0\le r_i\le n-1$ does there exists a symmetric matrix $A$ such that the diagonal ...
- 13
3 votes
1 answer
329 views
What do we know about the $\mathbb{F}_{q^2}$-curve $X^{q-1} + Y^{q-1} + Z^{q-1}$?
People have thoroughly studied the Hermitian $\mathbb{F}_{q^2}$-curve $H: X^{q+1} + Y^{q+1} + Z^{q+1} = 0$. What do we know about the similar $\mathbb{F}_{q^2}$-curve $C: X^{q-1} + Y^{q-1} + Z^{q-1} = ...
- 1,873
1 vote
0 answers
104 views
Existence of full-weight codeword in a linear q-ary code
I'm new to coding theory but would like to ask the following question: Let $C$ be a linear $q$-ary code over $\mathbb{F}_q$ of length $n$ and dimension $k$ where $\mathbb{F}_q$ is a finite field with $...
- 191
2 votes
1 answer
862 views
Inner product over finite field
sorry for informals but is my first post. In Coding theory (exactly in Coding theory a first course - San ling and Chaoping) found this definition: $\langle , \rangle :\mathbb{F}_q^n\times\mathbb{F}_q^...
1 vote
1 answer
188 views
Maximal number of $k$-subsets of an $n$-set such that any two subsets meet in at most $(k-2)$ points
I am interested in the maximal number of $k$-subsets of an $n$-set such that any two subsets meet in at most $(k-2)$ points. I found that for $k=3$ and $k=4$, we have the sequences http://oeis.org/...
- 281
2 votes
0 answers
206 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 &...
- 191
1 vote
1 answer
148 views
Support of Fourier transform of random characteristic function
Let $\chi_X:\{-1,1\}^n\to \{0,1\}$ be the characteristic function of a subset $X\subseteq \{-1,1\}^n$, which is randomly drawn from all subsets with exactly $k$ elements. Is the support of the Fourier ...
- 459
9 votes
1 answer
731 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$ ...
- 418
2 votes
0 answers
241 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 $...
- 203
2 votes
1 answer
309 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$...
- 327
4 votes
0 answers
193 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 ...
- 38.3k
2 votes
0 answers
226 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$)...
- 91
0 votes
0 answers
207 views
Given a binary parity check matrix, find a parity check matrix for the same code such that no row has weight greater than $k$
A parity check matrix for a binary linear code is a matrix $H$ (with linearly independent rows) such that the (right) kernel of $H$ is the codespace. Clearly we can replace any row $r_i$ by $r_i + \...
4 votes
1 answer
203 views
Sequence design to optimize a combinatorial objective
Given a set $\cal N$ of $N$ objects, we seek to attribute a code, i.e., a binary sequence, to each of them to achieve the following objective of being capable to select any subset ${\cal S}\subseteq {\...
- 327
8 votes
0 answers
170 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. ...
- 26.3k
1 vote
2 answers
131 views
Name for the weight function defined as the integer sum of coordinate entries from ${\mathbf F}_p$
In ${\mathbb F}_p^n$, $p$ prime one may define a weight function on vectors in various ways such as Hamming, or Lee weight. (These two weights correspond nicely to the respective distances from $\bar ...
- 11