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
4 votes
1 answer
136 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 ...
Berk U.'s user avatar
  • 379
4 votes
1 answer
206 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 ...
Justin McInroy's user avatar
4 votes
1 answer
339 views

Capacity of a channel with random phase rotation

Consider a wireless channel $h=e^{j\theta}$, where $\theta$ is a uniform random variable in $[0,2\pi]$ independent of the input messages and the independent of the noise. The channel randomly rotates ...
Jeff's user avatar
  • 482
4 votes
1 answer
363 views

Most orthogonal lattice basis

Let $n \in \mathbf{N}$ be a natural number and $v_1,\cdots,v_n$ a set of basis vectors in $\mathbb{R}^n$. How does one find the matrix $g \in \mathbf{GL}_n(\mathbb{Z})$ orthogonalizing these best ...
Tiffy's user avatar
  • 97
4 votes
1 answer
830 views

Intersecting Hamming spheres: is $|A\stackrel k+E|\ge|A|$?

Since my original posting some ten days ago, I discovered an amazing example which changed significantly my perception of the problem. Accordingly, the whole post got re-written now. The most general ...
Seva's user avatar
  • 22.8k
4 votes
0 answers
127 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-...
Veit Elser's user avatar
  • 1,045
4 votes
0 answers
155 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 ...
Brendan McKay's user avatar
4 votes
0 answers
115 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\...
R B's user avatar
  • 608
4 votes
1 answer
506 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)$. Any rate $C-\varepsilon$ can be achieved by ...
Christian Chapman's user avatar
4 votes
0 answers
383 views

Fully Homomorphic Error Correction?

Consider a field $F$. Suppose we have two vectors $a,b\in F^n$, and an invertible matrix $G\in F^{n\times n}$. Let $c\in F^n$ be the point-wise product of $a$ and $b$, that is, $c_i=a_ib_i$. Let $x=...
Bill Bradley's user avatar
  • 3,809
3 votes
3 answers
895 views

Structure of F_p[G], for finite group G ?

Consider group algebra k[G] of finite group G. If k is alg.closed then every irrep lives there with multiplicity equal to dimension. (More conceptually as bimodule over GxG it is multiplicity free and ...
Alexander Chervov's user avatar
3 votes
3 answers
768 views

A different criterion for equivalence of codes?

I've been thinking about equivalence of codes (two codes that are equal up to order of positions of the letters, or permutations of the letters in a fixed position). It is obvious that if we have two ...
Rob's user avatar
  • 31
3 votes
1 answer
281 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} = ...
Dimitri Koshelev's user avatar
3 votes
1 answer
167 views

Maximal neighbour-full partition of $\{0,1\}^n$

What is the largest complete minor of the $n$-dimensional hypercube? (which we call $k(n)$) Alternatively, what is the partition of $\{0,1\}^n$ with each set connected and neighboring each other that ...
Real's user avatar
  • 178
3 votes
3 answers
592 views

On MDS code property

Is there a code that is Maximum Distance Separable and not isomorphic to Reed Solomon Codes? When is a MDS code isomorphic to Reed Solomon Code? Is there an easy test? If so, could someone provide ...
Turbo's user avatar
  • 13.7k
3 votes
3 answers
132 views

Block error-correcting codes over inhomogeneous alphabets

For $n := (n_1,\dots,n_N) \in \mathbb{N}_{>1}^N$, let $X_n := \prod_{j=1}^N [n_j]$, where as usual $[m] := \{1,\dots,m\}$. Are there any known generic constructions for (Hamming) sphere ...
Steve Huntsman's user avatar
3 votes
1 answer
284 views

Effects of many degree-2 variable nodes in the Tanner graph during the decoding of LDPC codes

Suppose that we have a LDPC code $C$ with a $(n -k )\times n $ parity check matrix $H$, and there exist approximately $ \sqrt n$ numbers of degree-2 columns. It means that there are approximately $\...
Bruce Fang's user avatar
3 votes
1 answer
3k views

Cyclic Hamming Code

I know that Hamming codes can be arranged in cyclic form. But my question is how can I prove this. My idea was to find a generator/primitive polynomial $p(x)$? For example I want to show that the $[...
cl14's user avatar
  • 31
3 votes
1 answer
615 views

Generator Matrices of Best Known Linear Codes

Is there a location where one can access generator matrices (not just bounds) of best known linear codes?
Turbo's user avatar
  • 13.7k
3 votes
1 answer
501 views

How many vectors of Hamming weight L in "random" K dimensional subspace of F_2^N ? Or how good/bad is random linear block code ?

Consider linear $N$-dimensional space $F_2^N$. Consider its $K$ dimensional subspace $V \subset F_2^N$. Let us calculate $w(k,V,N)$ number of vectors in $V$ of Hamming weight $k$ in $V$. Since there ...
Alexander Chervov's user avatar
3 votes
1 answer
184 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 ...
Saúl RM's user avatar
  • 7,916
3 votes
2 answers
3k views

Hat Problem/Hamming Codes

I've been reading about how hamming codes are used to 'solve' the Hat Problem, and I understand how it 'assigns' one person to be the speaker, and how that speaker knows the answer. Everything I read ...
Jon Brant's user avatar
3 votes
1 answer
149 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\...
domotorp's user avatar
  • 18.3k
3 votes
2 answers
228 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 ...
user124784's user avatar
3 votes
1 answer
110 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 ...
Theo Johnson-Freyd's user avatar
3 votes
1 answer
180 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}\...
Campello's user avatar
  • 800
3 votes
1 answer
72 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. Question:...
Manfred Weis's user avatar
  • 12.6k
3 votes
2 answers
240 views

Binary codes with upper bound on pairwise distance

A fundamental problem in coding theory is: Given positive integers $k\le n$, determine or bound the maximal cardinality of a set $S\subset \mathbb{F}_{2}^{n}$ such that $\forall x,y\in S: x\ne y\...
Favst's user avatar
  • 1,985
3 votes
1 answer
219 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 ...
Jason S's user avatar
  • 653
3 votes
1 answer
603 views

Parity-check matrix for code with variable block size and minimum distance

Consider a linear error-correcting code with symbols in $GF(q)$, with codewords of length $k$ generated from messages of length $n$ and minimum distance $d+1 = k-n+1$. In the cases of interest, $q = ...
Dale's user avatar
  • 431
3 votes
2 answers
255 views

Picking codewords that are close

I posted this question in https://math.stackexchange.com/questions/1142698/picking-codewords-that-are-close a week back. Let $[n,k,d]$ be a linear code over $\Bbb F_q$ with minimum distance $d$ and ...
Turbo's user avatar
  • 13.7k
3 votes
2 answers
439 views

Hamming graph and independent sets

I'm defining the Hamming graph $H(d,q)$ in the usual way, so we have a set $S$ of $q$ elements, the hamming graph $H(d,q)$ has vertex set $S^{d}$ (the set of all ordered $d$-tuples of elements of $S$) ...
Pavan Sangha's user avatar
3 votes
2 answers
187 views

Techniques for showing optimality of given packing

There are some natural packing problems that have been asked in mathematics. Some of them are: 1)How many balls can be placed with in a cube? 2)How many equidistant points can be place on the ...
Turbo's user avatar
  • 13.7k
3 votes
1 answer
109 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 ...
Stephen Jiang's user avatar
3 votes
1 answer
141 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 ...
Kaiyi Zhang's user avatar
3 votes
1 answer
117 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$ ...
potato's user avatar
  • 131
3 votes
1 answer
412 views

Relations between the parameters of the Best Linear Code

Let the triple $(n,k,d)$ be length and dimension and minimum distance of a code, respectively. For a fixed given numbers $n$, $k$ and $d$, what relations there are between BKLC$($GF(2)$,n,k)$ ,BLLC$($...
Amin235's user avatar
  • 325
3 votes
2 answers
2k views

How do you use the bits you get back from Bits Back Coding?

Bits Back coding is a scheme to transmit an observation $x$. You can read about it here[1]. To my understanding, it works like this: The encoder samples a message $z$ from a distribution $Q(z|x)$ ...
Jonathan's user avatar
  • 223
3 votes
1 answer
280 views

PRNG and coding theory

Let $k, n \in \mathbb{N}$, $k = (1 - \epsilon)n$ where $1 >\epsilon > 0$. I want to find $f: \{0,1\}^k \to \{0, 1\}^n$ such that: 1) $f(a) \not= f(b)$ if $a \not=b $ 2) for any $x \in \{0,1\}...
Alexey Milovanov's user avatar
3 votes
1 answer
257 views

If "force" is periodic does it imply "velocity" is periodic ? (or decoding tail-bited conv. codes)

I'll try to translate certain problem about convolutional codes to more common language of ODE, hope my translation is correct, but welcome to criticize. Consider two given functions periodic ...
Alexander Chervov's user avatar
3 votes
2 answers
190 views

Are there subsets L in R^n such that it is "easy to find" closest point in L to a given P in R^n ? Vague question motivated by error-correcting codes

Math Motivation: consider LINEAR subspace $L$ in $R^n$ and given vector $E$ in $R^n$, then it is easy to find a closest vector $S \in L$ to $E$ - just ortogonal projection. Question Are they some ...
Alexander Chervov's user avatar
3 votes
1 answer
148 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)$....
Harry L's user avatar
  • 31
3 votes
0 answers
127 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)$ ...
Jop's user avatar
  • 93
3 votes
0 answers
125 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 ...
Alexey Ustinov's user avatar
3 votes
1 answer
85 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 =...
Salmonstrikes's user avatar
3 votes
0 answers
97 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 ...
Alexey Ustinov's user avatar
3 votes
1 answer
534 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 ...
Turbo's user avatar
  • 13.7k
3 votes
1 answer
224 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 \...
Patrick Rall's user avatar
3 votes
0 answers
228 views

On weight enumerators of codes

Are there $[n,k]_q$ constant rate $\frac kn$ and constant alphabet linear code families with automorphism group of size $\Omega((n-n^\beta)!)$ that have minimum distance $d=O(n^\alpha)$ and number of ...
Turbo's user avatar
  • 13.7k
3 votes
0 answers
115 views

Maximum number of $4$-cycles

Suppose we have a balanced bipartite planar maximum degree $k$ graph. How many such graphs on $2n$ vertices have at most $f(n)$ maximum number of $4$ cycles for a given function $f:\Bbb R^+\...
Turbo's user avatar
  • 13.7k