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

Filter by
Sorted by
Tagged with
2 votes
1 answer
115 views

Verify if array is orthogonal

This is a repost from the computer science stackexchange. The question has been offered a bounty, but received no answers. Therefore, I would like to ask this question here. Orthogonal arrays often ...
user avatar
  • 470
4 votes
1 answer
230 views

Bipartite version of Hamming bound (two families of codewords with large Hamming distance)?

Update: In light of Fedor Petrov's answer, I added an additional requirement that all strings in $A$ and $B$ have Hamming weight exactly $n/2$, which hopefully makes the question more interesting. ...
user avatar
  • 43
1 vote
1 answer
31 views

(Approximation) Algorithms for Weight Distribution / Subspace Weights Problem in coding theory

The Weight Distribution / Subspace Weights Problem in coding theory is defined as this: Instance: A binary $m$ by$n$ matrix $H$ and an integer $k > 0$ Question: Is there a set of $k$ columns of $...
user avatar
4 votes
3 answers
186 views

Existence of (near) equidistant codewords

My question is originally related to coding theory, but fairly easy to state in pure combinatorial way. Fix $k\in\mathbb{N}$, $\beta\in(0,1)$ and consider the binary cube $\Sigma_n = \{0,1\}^n$ ...
user avatar
  • 1,076
4 votes
1 answer
118 views

Existence of a joint distribution on Bernoulli variables with same probability of being pairwise different

Let $m\in\mathbb{N}$ and $p\in(0,1)$ be arbitrary. Is there a sequence $X_1,\dots,X_m$ of random variables with the following specs on their distribution: Each $X_i$ is unbiased Bernoulli: $X_i\sim {\...
user avatar
  • 1,076
2 votes
0 answers
84 views

Mutual benefits of coding theory and the reconstruction conjecture

Let $G_n$ denotes all graphs with $n$ nodes. For any graph $G$ in $G_n$, the adjacency matrix $A(G)$ can be viewed as a codeword of length $n^2$. Also, the codes arises from $G_n$ is a linear binary ...
user avatar
  • 4,431
0 votes
0 answers
22 views

Explicit family of Euclidean lattices which maximize $\lambda_1(L)\lambda_1(L^\vee)$?

For a lattice $L\subseteq\mathbb{R}^n$ (normalized to have determinant 1), one consequence of Minkowski's first theorem is that $$\lambda_1(L) \leq \sqrt{n},$$ where $\lambda_1(L) = \min_{x\in L\...
user avatar
  • 702
4 votes
1 answer
140 views

Coding over very noise channel

Suppose that I want to send a message (consisting of bits) over a channel where from $n$ transferred bits as many as $n/2-\varepsilon n$ might be flipped, i.e., the distance of the code is $n-2\...
user avatar
  • 17.1k
4 votes
0 answers
102 views

What is the least compressible probability distribution? (under entropy constraint, for an expected squared error metric)

This is a cross-post from cstheory after a week with no answers/comments; I'm hoping someone here may have some thoughts. Consider a distribution $\mathcal D$ over the reals, a real parameter $H\in\...
user avatar
  • 608
21 votes
2 answers
968 views

The chromatic number of the union of two graphs

Let $G_n$ be the graph on the set of all binary strings of length $n$ with two strings adjacent whenever they are Hamming distance $2$ away from each other, or one of them lies below another one; thus,...
user avatar
  • 21.3k
6 votes
0 answers
189 views

Gaussian coefficients identity

I am having difficulty showing the equivalence between (11) and (15) of Delsarte - Association schemes and $t$-designs in regular semilattices. It is somehow an application of Möbius inversion, but I ...
user avatar
2 votes
1 answer
110 views

Decoding the Reed–Muller $RM(m, m)$ code, and a matrix related to Pascal's triangle

The Reed–Muller $RM(m, m)$ code sends the message $p(X_0, \ldots , X_{m - 1}) = \sum_{S \subset \{0, \ldots , m - 1\}} \alpha_S \cdot X_S$ to its set of evaluations $\left\{ p(x_0, \ldots , x_{m - 1}) ...
user avatar
  • 61
6 votes
1 answer
196 views

How many Hamming spheres of radius 1 does it take to cover the cube?

I am looking for the sharpest known upper bound on $K(n, 1)$ as $n \rightarrow \infty$. This is the minimal cardinality of a (not-necessarily linear) covering code of $\{0, 1\}^n$ of radius 1. In ...
user avatar
  • 61
1 vote
0 answers
37 views

Computational complexity of rate $\frac{1}{2}$ codes

We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing the minimum distance of a (binary)...
user avatar
  • 71
1 vote
0 answers
91 views

Promise version of minimum distance

It has been known for some time that computing minimum distance of a linear code (minimum weight codeword) is NP-hard. This immediately also says that given a code $C$, calculating minimum hamming ...
user avatar
  • 71
2 votes
1 answer
85 views

Dense and decodable lattices in high dimensions

We are currently looking for both dense and decodable lattices. Precisely, we want a lattice which CVP can be solved in polynomial time like $O(n^2)$ or $O(n^3)$ where $n$ is the dimension like 128 or ...
user avatar
8 votes
2 answers
308 views

Maximum of the weighted binomial sum $2^{-r}\sum_{i=0}^r\binom{m}{i}$

Let $m$ be a positive integer and let $f_m(r)=2^{-r}\sum_{i=0}^r\binom{m}{i}$. Clearly $f_m(0)=f_m(m)=1$ and $f_{2r+1}(r)=2^{2r}$. Conjecture: If $m>12$, then the maximum value of $f_m(r)$ for $r\...
user avatar
  • 1,889
8 votes
0 answers
123 views

On the number of Reed–Muller codewords with no consecutive ones

$\DeclareMathOperator\RM{RM}\DeclareMathOperator\Eval{Eval}$Consider the polynomial ring $\mathbb{F}_2[x_1,x_2,\dotsc,x_m]$ and let $f\in \mathbb{F}_2[x_1,x_2,\dotsc,x_m]$. Let us now fix a Gray ...
user avatar
2 votes
1 answer
90 views

Low-Hamming weight vectors in low-dimensional subspaces of $\mathbb{F}_p^n$

What is the maximum number vectors of Hamming weight at most $w$ in a $d$-dimensional subspace of $\mathbb{F}_p^n$, where $w,d,p$ are constant and $p$ is odd. (The Hamming weight is the number of ...
user avatar
  • 93
1 vote
1 answer
96 views

Almost-parallel corners of the hypercube in high dimensions

Say I would like a collection of k "almost-parallel" boolean vectors $X_1,...,X_k \in \{\pm 1\}^n$, such that $(X_i,X_j)/n \approx 1-\epsilon$ for some small $\epsilon$. How many ways are ...
user avatar
  • 405
2 votes
1 answer
118 views

Simple non-asymptotic upper-bound for packing number of a hamming cube

Looking for a simple upper-bound for the packing number of hamming cube, I'm led to consider the following. Fix $p \in (0,1/2]$. For a positive integer $n$, define $S_n(p) := \sum_{i=1}^{\lfloor np\...
user avatar
  • 5,556
2 votes
1 answer
136 views

Are there any homomorphic analog error correction code?

Are there any analog error correction codes that are additively and multiplicatively homomorphic?
user avatar
  • 41
5 votes
2 answers
278 views

Maximum number of vectors with upper bound on pairwise inner products

I have a collection $\{v_1,...,v_k\}$ of vectors in $\{\pm 1\}^n$ with the property that for all $i\neq j$ we have $\langle v_i, v_j \rangle \le c\log_2(n)$. I am looking for an upper bound on $k$ in ...
user avatar
  • 63
1 vote
1 answer
210 views

Upper bounds for high-dimensional spherical codes given the covering radius

I assume that this sort of question has already been considered at great length. Nevertheless, I could not find an answer to this question in the related literature. Given a constant $a\in (0,2]$, ...
user avatar
1 vote
0 answers
94 views

A variant of Huffman code

Given an alphabet of $n$ symbolswith probabilities $p_i$ for symbol $i$, we need to encode the symbols (in a prefix-free way) to binary codewords $c(i)$ with length $\ell(c(i))$ to minimize the ...
user avatar
  • 491
1 vote
1 answer
154 views

error correcting huffman code [closed]

I am looking for a code that can correct errors with variable and limited length like huffman code. I am not an expert in coding theory. Is there any code or related literature on this?
user avatar
  • 491
2 votes
0 answers
338 views

Linear independence of Vandermonde matrix in systematic Reed-Solomon code

My question is about using a Vandermonde matrix vs a Cauchy matrix in erasure coding. In the Reed-Solomon (RS) code, encoding is done by multiplying a $N\times K$ ($N>K$) matrix with the code words ...
user avatar
  • 21
6 votes
0 answers
122 views

When are Hamming codes cyclic?

I've asked this question on math.stackexchange before, but it has not been solved. The following statement appears to be true: The $q$-ary Hamming code of codimension $r$ over $\mathbb{F}_q$ is ...
user avatar
  • 253
8 votes
1 answer
217 views

Perfect sphere packings (as opposed to perfect ball packings)

I came across this question when I was discussing the rather wonderful Devil's Chessboard Problem with my colleague, Francis Hunt. We realised that there is a nice connection to a packing question in $...
user avatar
  • 10.8k
8 votes
1 answer
183 views

Weight enumerator classifiers

Let $f(x,y)$ be a polynomial with integer coefficients. What conditions guarantee that this is the weight enumerator of a binary linear code of size $n$ and dimension $k$? I’m almost certain that the ...
user avatar
  • 560
6 votes
1 answer
140 views

Characterization of metrics such that the volume of balls doesn't depend on their centers?

Given a finite metric space $(X,d)$, when does it hold that for all $y\in X$ and $r>0$, $\#B(y,r)$ does not depend on $y$? Here $ B(y,r):=\{x\in X: d(x,y)\le r\} $ denotes a ball of radius $r$ ...
user avatar
2 votes
1 answer
87 views

Strong Data Processing Inequality for capped channels

Let $X$ and $Y$ be two $\rho$ correlated Gaussian vectors, such that $X,Y\sim N(0,1)^n$ and $E[X_iY_i]=\rho$. Let $M_X = f(X)$ and $M_Y = f(Y)$ be $k$-bit functions of $X$ and $Y$, that is $H(X)=H(Y)=...
user avatar
3 votes
0 answers
120 views

Cyclic codes: sparse codewords not orthogonal to the all-ones vector

Is it true that for any sufficiently large prime $p$, there exists a prime $q\ne p$ and a cyclic code of length $p$ over $\mathbb{F}_q$ that contains a codeword of Hamming weight at most ord$_p(q)$ ...
user avatar
  • 93
1 vote
1 answer
301 views

System of equations - Proof that a solution exists

Let $ a = (a_1,a_2, \ldots,a_{10})\in \{ 0,1\}^{10}$ be a binary vector of length $10$. Question: Without using a computer-aided method, how to prove that there exists binary vectors $x_{i,j} \in \{ ...
user avatar
2 votes
1 answer
224 views

Is this model of converting integers to Gray code correct?

The model shown in the figure converts all numbers that have k digits in the binary system to Gray code without any calculation, but I have no proof that guarantees this claim. Here is some ...
user avatar
14 votes
1 answer
1k views

Hamming distance to primes

There is a positive density of odd numbers which are of the form $2^n+p$ (due to Romanoff), and a positive density which are not of this form (due to van der Corput and Erdos, see this paper for a ...
user avatar
  • 286
2 votes
1 answer
185 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 \in ...
user avatar
  • 2,767
1 vote
1 answer
231 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. ...
user avatar
2 votes
0 answers
39 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 ...
user avatar
  • 459
2 votes
0 answers
179 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 ...
user avatar
3 votes
2 answers
212 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 ...
user avatar
4 votes
1 answer
419 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 ...
user avatar
  • 253
2 votes
0 answers
77 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 $\...
user avatar
  • 203
1 vote
0 answers
78 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 ...
user avatar
  • 1,698
2 votes
0 answers
111 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 ...
user avatar
  • 161
4 votes
2 answers
400 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 ...
user avatar
  • 27.6k
6 votes
1 answer
235 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$, $...
user avatar
  • 2,019
2 votes
0 answers
196 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)\...
user avatar
1 vote
0 answers
108 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'...
user avatar
3 votes
0 answers
114 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 ...
user avatar

1
2 3 4 5 6