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
271
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
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
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
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
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
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
0
votes
0
answers
73
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
1
vote
3
answers
474
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
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
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 $\...
6
votes
2
answers
285
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
3
votes
3
answers
473
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
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
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
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
0
votes
1
answer
235
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
4
votes
2
answers
396
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,043
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
2
votes
1
answer
167
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 $...
- 301
1
vote
1
answer
201
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/...
- 349
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
2
votes
0
answers
242
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
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
0
votes
0
answers
208
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 + \...
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