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

learn more… | top users | synonyms

0
votes
1answer
86 views

In a finite field with characteristic 2, how can I check if a given polynomial is divisible by (x^2+1)? [on hold]

Given the 0 or 1 coefficients of a very high degree polynomial $P(x)$ over GF(2), where x is an element of $GF(1024)$, is there a simple algorithmic way to find out if this polynomial is divisible ...
0
votes
2answers
77 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
0answers
44 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
1answer
74 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
0answers
129 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
0answers
92 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
1answer
79 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
1answer
461 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
2answers
129 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
1answer
102 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
1answer
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
3answers
332 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
0answers
90 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
2answers
109 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
0answers
107 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 ...
0
votes
0answers
141 views

Isomorphic Algebraic Geometric codes

Let $\chi/\Bbb F_q$ be an algebraic curve over a finite field $\Bbb F_q$ with $q^s$ rational points for some $s\in(0,1)$. Let $L(D)$ be the riemann roch space with prescribed zeros and poles. Let ...
1
vote
1answer
138 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
1answer
302 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
2answers
171 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
2answers
131 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
1answer
233 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
0answers
106 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
1answer
128 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
1answer
171 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
2answers
225 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
0answers
161 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
1answer
151 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
3answers
301 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
2answers
375 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
1answer
145 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
0answers
170 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
1answer
153 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
1answer
117 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
1answer
242 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
1answer
209 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
1answer
221 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
2answers
527 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
2answers
265 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
1answer
330 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, ...
0
votes
1answer
119 views

How many combinations exist of $M'$ items from a set of $M$ items such that each combination is not similar at more than $m$ elements?

I apologize if this has been answered before. I would like to know how many ways there are to choose $M'$ elements from a set of $M$ elements such that any two sets selected are not similar at more ...
0
votes
1answer
276 views

What are “best” polynoms f(x) g(x) of degree n ? I.e. ideal generated by them is as far from zero as possible ? (Best convolutional codes.)

Consider polynoms f(x) g(x) of degree at most n. (I am mostly interested about F_2[x]). Let us multiply them by arbitrary polynoms p(x) i.e. consider ideal (p f , p g) in $F_2[x]\oplus F_2[x]$. Let ...
1
vote
1answer
543 views

“Trellis graph” is it standard term in graph theory ? What are its properties ?

In coding theory (convolutional codes) the graph called "trellis diagramm" is used to visualize something. I wonder is it a standard term in graph theory? Corresponding Wikipedia article is not ...
2
votes
0answers
123 views

Find polynoms f,g such that for any polynom p(x): |fp|+|gp|>= |f|+|g| ? Where |*| is number of non-zero monoms.

How to construct examples (describe all) polynoms f,g such that for any polynom p(x) not equal to zero: |fp|+|gp|>= |f|+|g| ? Where |*| is number of non-zero monoms (=Hamming weight, by the way it ...
0
votes
1answer
179 views

Multiplication by polynomials x^2+1 ; x^2+x+1. Does minimal Hamming norm of image equal to 5 ?

Everything over F_2. Let us define Hamming norm of polynom |p(x)| = number of non-zero monoms. Respectivly for a pair of polynoms |[p ; g]| = |p| +|g|. Consider linear map $F_2[x] \to F_2[x] \oplus ...
3
votes
3answers
493 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 ...
1
vote
1answer
191 views

Given g1(x), g2(x) minimize over p(x) Hamming weight of [p(x)g1; p(x)g2(x) ] ? (Or how to find minimal distance of convolutional code?)

Fix polynoms g1(x), g2(x) over F_2[x]. Question: How to find minimum over polynoms p(x) of the: HammingWeight(p(x) g1(x) ) + HammingWeight(p(x) g2(x) ) ? By HammingWeight of polynom I mean number ...
2
votes
3answers
347 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
3answers
418 views

Good codes in practice for correcting combination of errors and erasures

In practice, both errors and erasures might be introduced in the channel. Could you point me to some good codes for correcting such combinations. Also what are their correction capabilities?
3
votes
1answer
241 views

Special polynomials over finite fields

My field of research is coding theory and I am working on cyclic codes. During my research, I tackled an algebraic problem. After some simple definitions, I asked my question. I will appreciate any ...
2
votes
1answer
285 views

Error correcting codes obtained as superposition of two codes e.g. CRC+Convolutional

Setup reminder: linear block error-correcting code is some linear subspace $C$ in $F_2^N$. (Correcting error means to find a point $c \in C$ which is "nearest" to a given $r$ in $F_2^N$, $r$ is ...