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".
311 questions
0
votes
0
answers
30
views
Upper bound on the intersection of two radius-r Hamming balls in binary constant-weight codes when codewords are at Hamming distance 2
Let $\mathcal{B}(n,w)$ be the set of all binary vectors of length $n$ and constant weight $w$, i.e.,
$\mathcal{B}(n,w) = \{ x \in \{0,1\}^n : \mathrm{wt}(x) = w \}$.
The Hamming ball of radius $r$ (in ...
- 1
4
votes
1
answer
278
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
87
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,819
1
vote
0
answers
91
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
561
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
79
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
224
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
309
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
156
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
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
12
votes
1
answer
545
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