# Tagged Questions

**0**

votes

**0**answers

46 views

### Optimal covering

Let consider a problem of optimal covering of Hamming space.
So we have Hamming space $\{0,1\}^n$ and some integer $r$. We want to find a set $A \subseteq \{0,1\}^n$ such that any point from ...

**2**

votes

**0**answers

120 views

+50

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

**3**

votes

**2**answers

189 views

### Picking codewords that are close

I posted this question in http://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

**3**answers

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

**0**

votes

**0**answers

89 views

### Minimum-size spanning group using hamming distance

For given natural numbers $N$ and $D$, we will define $F$ as all the non-negative integers less than $2^N$. A group $A \subseteq F$ will be "spanning", if and only if every number $x$ in $F$ satisfies ...

**1**

vote

**1**answer

53 views

### Correlation between two continuous-time stochastic processes

Consider two continous-time stochastic processes $\{A(t)\}_{t \ge 0}$ and $\{B(t)\}_{t \ge 0}$ with $A(t)=t$ and $B(t)=t$. Each process starts at $t=0$ and emits "ticks" at increasing time slots. For ...

**1**

vote

**0**answers

163 views

### Polynomial existence over finite field

Denote $\mathcal{F_n}$ as collection of multiaffine polynomials $f\in\Bbb F_2[x_1,\dots,x_n]$.
Denote total degree of $f\in\mathcal{F_n}$ as $deg(f)$ (note $deg(f)\leq n$).
Denote ...

**2**

votes

**0**answers

73 views

### On subset of Deterministic games

Denote strings $u,v$ from $\{0,1\}^n$.
Denote concatenated pair $[uv]$.
Denote
$$[uv]_{1}=\{[uv]\oplus e_i\}_{i=1}^{2n}$$
collection of pairs with Hamming distance $1$ from $[uv]$ string ...

**2**

votes

**1**answer

191 views

### Minimally intersecting subsets of fixed size

The question I have, is how to generate the following collection of subsets:
Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each ...

**1**

vote

**0**answers

63 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

**1**answer

105 views

### Balanced binary code that “resists” local decoding?

I am looking for a construction that can be stated as the following coding problem: a binary code with good distance ($d = \Omega(n)$ where codeword length is $n$) that "resists local decoding" in the ...

**9**

votes

**0**answers

166 views

### Maximum number of vectors in a hypercube satisfying given conditions

$\mathcal{C}$ is a collection of binary vectors of length $n$, i.e. $\mathcal{C}\subseteq\{0,1\}^n$. For arbitrary $x,y,z\in\mathcal{C}$ and $x\neq z$, $y\neq z$, there always holds that the Euclidean ...

**31**

votes

**1**answer

509 views

### What measurable quantity can constrain the number of odors human can discriminate?

This is not a very typical MO question, but I hope you bear with me. It concerns a recent disagreement in the biology literature about how many different odors humans can discriminate. The authors of ...

**0**

votes

**2**answers

108 views

### Form of the Shannon capacity for Heptagon?

Is the $0$-error capacity of $7$-cycle:
$(1)$ known to be of form $7^q$ for some $q\in \mathbb Q$?

**1**

vote

**0**answers

62 views

### Coding for channels with concentrated error

Can we implement a reduced-error transmission over a channel with error frequency having $\liminf<\frac{1}{2}$ and $\limsup>\frac{1}{2}$?
We know that if a channel with error flips (in the ...

**-1**

votes

**1**answer

86 views

### Noise reduction in capacity-0 channels

Suppose we have a binary symmetric channel with $p=\frac{1}{3}$; that is, a communications channel in which each bit is flipped with independent probability $\frac{1}{3}$. I know that there is a code ...

**3**

votes

**0**answers

136 views

### On a problem of sphere-packing for Reed-Solomon codes

Suppose we have an $[n, k+1, n-k]$ Reed Solomon code $\mathcal C$ over $\mathbb F_q$, where $n-k=d$ is the minimum distance, and suppose that $d=2t+1$. We know that for every $r \in \mathbb F_q^n$ the ...

**3**

votes

**0**answers

98 views

### Applications of list decoding

This is citation from http://en.wikipedia.org/wiki/List_decoding:
Algorithms developed for list decoding of several interesting code families have found interesting applications in computational ...

**2**

votes

**1**answer

91 views

### Mutual information staying constant under composition of channels

Consider the following scenario: one has 2 communication channels $C_1$ and $C_2$. Denote by $p(x)$ the input probability distribution.
The mutual information between the input and the output of ...

**3**

votes

**1**answer

508 views

### “Codes” in which a group of words are pairwise different at a certain position

I read the following problem, claimed to be in the IMO shortlist in 1988:
A test consists of four multiple choice problems, each with three options, and the students should give an unique answer ...

**4**

votes

**2**answers

135 views

### Another formulation of error-correcting coding problem

Consider classic error-correcting problem:
there is finite set $A$ and string $a_1...a_n$, $a_i \in A$ in the begin.
in the end we have $b_1...b_n$. Set places of errors $E = \{i| a_i\not= b_i \}$, ...

**1**

vote

**1**answer

105 views

### Group action of $G<\mathbb Z^\infty_2$ over the Golden mean shif [closed]

I'm am looking for an action of an infinite subgroup of $\mathbb Z^\infty_2$ over the golden mean shift space $$X=\{x\in \{0,1\}^\mathbb N : x_i=1\Rightarrow x_{i+1}=0\}$$ such that any element of $G$ ...

**1**

vote

**1**answer

49 views

### Function field Towers of larger depth of recursion

A function field tower is a sequence of function fields
$$\mathcal{F}_0 \subset \mathcal{F}_1 \subset \mathcal{F}_2 \dots \subset \mathcal{F}_{n} \subset \mathcal{F}_{n+1} \subset \dots $$
over a base ...

**6**

votes

**3**answers

334 views

### On the rank of a matrix $S$ with coefficients in $\mathbb F_{2^m}$

Let $\mathbb F$ be a finite field with characteristic 2 and let $S \in M(2k, 2k, \mathbb F)$ be the matrix defined as follows
$$ S=\left[\begin{array}{ccccccc}
0 & ...

**3**

votes

**0**answers

96 views

### Certain subgroup of automorphism groups of binary codes

Suppose that $C$ is an binary linear code of length $n$ and dimension $k$ (i.e. it's a $k$-dimensional linear subspace of $\mathbb{F}_2^n$). As usual, the automorphism group of $C$ is the subgroup of ...

**1**

vote

**2**answers

114 views

### Designing almost orthogonal vectors in a deterministic manner

Consider the vector space $\mathbb{R}^n$, the standard inner product $\langle \cdot,\cdot \rangle:\mathbb{R}^n\times\mathbb{R}^n\rightarrow \mathbb{R}$, and some $0<\epsilon\leq ...

**4**

votes

**0**answers

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

**1**

vote

**1**answer

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

**1**

vote

**1**answer

436 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

**2**answers

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

**3**

votes

**2**answers

135 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

274 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?

**2**

votes

**0**answers

107 views

### Looking for Camion - Abelian codes

I am looking for a copy of the old report "Paul Camion - Abelian codes", Technical Report 1059, University of Wisconsin 1971. I have asked Paul himself, but he could not help me. Anyone out there has ...

**3**

votes

**1**answer

144 views

### Reference for partial Hadamard matrices

Definition. An $m\times n$ matrix is said to be a partial Hadamard matrix (let's say PHM) if its entries are chosen from $\lbrace -1, 1 \rbrace$ such that the dot product of each pair of row vectors ...

**0**

votes

**2**answers

234 views

### Comparison Huffman Encoding and Arithmetic Coding dependent on Entropy

Where can I get an understanding of how Arithmetic Coding and Huffman Encoding compare as entropy increases. I know Arithmetic Coding is better for low entropy distributions, but how can I get a sense ...

**4**

votes

**2**answers

228 views

### Is there a code which corrects corruption of any two bits in a block?

Background
I've just learned a bit about linear codes. Hamming codes have the property that up to one bit in a block can be corrupted, and we still communicate the message correctly. This is done by ...

**5**

votes

**0**answers

166 views

### When does the Lloyd polynomial have only integral roots?

For a $t$-error correcting code of length $n$ over the finite field $\mathbb{F}_q$, the Lloyd polynomial is given by
$$
L_t(n,x):=\sum_{j=0}^t(-1)^j\binom{x-1}{j}\binom{n-x}{t-j}(q-1)^{t-j}.
$$
A ...

**1**

vote

**1**answer

157 views

### Extended Hypercube Graph

Definition 1. The $n$-hypercube graph has vertices which are the elements of the set $\lbrace 0,1\rbrace^n$ of $n$-bit binary strings, and an edge is drawn between each pair of vertices representing a ...

**4**

votes

**3**answers

333 views

### Bounded Hamming distance

Definition 1. For each $n\in\mathbb{Z}^+$, the $n$-dimensional Hamming cube is the set of ordered $n$-tuples of $\lbrace 0,1\rbrace$, denoted by $\lbrace 0,1\rbrace ^n$.
Definition 2. The binary ...

**1**

vote

**2**answers

422 views

### Hamming codes from overlapping vectors

I am interested in whether the following problem is known.
For a given binary vector $V$ of length $n\geq m$, let $S$ be a subset of the possible subvectors of $V$ of length $m$ and say that the size ...

**0**

votes

**1**answer

156 views

### Isometry on a Hamming cube

Let $E^n$ be a Hamming cube of dimension $n$, and $\phi$ be a mapping from $E^n$ to $E^n$ that preserves Hamming distance, i.e. $d(x,y)=d(\phi (x),\phi (y))$. The question is the following: show that ...

**3**

votes

**0**answers

176 views

### Matrix where every subset of rows has maximal rank

I am looking for a class of matrices $M(n(m), m, k(m), \phi)$ with the following properties:
M is $n \times m$ where $n(m) > m$.
Every subset of rows of size $k$ has (maximal) rank $m$.
$n(m)$ ...

**4**

votes

**1**answer

155 views

### Lower bound on the dimension of a subspace of $\mathbb Z_2^r$?

This question may be very trivial, I apologize if it is so.
I have subspace $V\subset \mathbb Z_2^r$ with the property that for every choice of a subset $I$ of $k$ elements in $\{1,2,\dots r\}$, the ...

**1**

vote

**1**answer

119 views

### (A)periodicity and (In)dependence on the boundary condition for some discrete analog of ODE (convolutional codes)

(See also MO117508, MO116611). This post describes somewhat real problem with convolutional codes. Let me first try to give brief and vague formulation of the question, later give details.
Problem ...

**3**

votes

**1**answer

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

**4**

votes

**1**answer

246 views

### Best upper bound on rate for q-ary codes

Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch which states that the rate $R(\delta)$ corresponding to ...

**4**

votes

**1**answer

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

**7**

votes

**2**answers

531 views

### Automorphisms of subgroup of hamming cube under distance constraint

Let $S$ be a subset of $\{0,1\}^n$ such that any two elements of $S$ are at least (Hamming) distance 5 apart. I'm looking for an upper bound on the size of the automorphism group of $S$.
There's a ...

**3**

votes

**2**answers

267 views

### Cancellation theorem for lattices

By a lattice, we mean a finitely generated, free $\mathbb{Z}$-module together with a symmetric bilinear form. Typical examples are the hyperbolic lattices $U$ and the root lattices $A_{n}, D_{n}, ...

**1**

vote

**1**answer

419 views

### How to find next to optimal path in hidden Markov model or what should be LIST-Viterbi algorithm ?

The Viterbi algorithm is an algorithm for finding the most likely sequence of hidden states – called the Viterbi path.
Question If I am interested in list of several paths - optimal, sub-optimal, ...