**1**

vote

**1**answer

37 views

### Bound on the weight of the minimum weight generator of [n,k] cyclic codes?

I'm looking at creating sparse generator matrices for cyclic codes of a given length and dimension. A generator matrix of an [n,k] cyclic code can be expressed as
$G = \begin{bmatrix}g_0 & g_1 ...

**1**

vote

**1**answer

80 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

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

**3**

votes

**2**answers

198 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

82 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

97 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

59 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

170 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

76 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

203 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

69 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

109 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

170 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

526 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

110 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

65 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

89 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

138 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

93 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

694 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

139 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

107 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

335 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

98 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

125 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

162 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

459 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

181 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

281 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

108 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

149 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

247 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

230 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

188 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

160 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

342 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

432 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

157 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

156 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

247 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

230 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

268 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}, ...