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".
289
questions
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 ...
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 ...
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 ...
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 ...
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 ...
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-...
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 ...
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\...
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 ...
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=...
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 ...
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 ...
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} = ...
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 ...
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 ...
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 ...
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 $\...
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 $[...
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?
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 ...
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 ...
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 ...
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\...
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 ...
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 ...
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}\...
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:...
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\...
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 ...
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 = ...
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 ...
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$) ...
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 ...
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 ...
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 ...
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$ ...
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$($...
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)$ ...
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\}...
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 ...
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 ...
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)$....
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)$ ...
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 ...
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 =...
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 ...
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 ...
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 \...
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 ...
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^+\...