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
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
2 votes
0 answers
149 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 ...
user38148's user avatar
6 votes
3 answers
573 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 ...
Favst's user avatar
  • 1,985
0 votes
2 answers
2k 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 ...
Rishi Sharma's user avatar
4 votes
2 answers
297 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 ...
Anton Geraschenko's user avatar
8 votes
0 answers
395 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 well-...
Dietrich Burde's user avatar
1 vote
2 answers
326 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 ...
Favst's user avatar
  • 1,985
5 votes
3 answers
907 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 ...
Favst's user avatar
  • 1,985
2 votes
2 answers
701 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 ...
2 votes
1 answer
440 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 $...
Igor Gribanov's user avatar
3 votes
0 answers
229 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)$ ...
aelguindy's user avatar
  • 343
4 votes
1 answer
193 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 ...
rita's user avatar
  • 6,213
1 vote
1 answer
146 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 ...
Alexander Chervov'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
6 votes
1 answer
742 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 ...
Brazen's user avatar
  • 61
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
7 votes
2 answers
609 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 ...
rishig's user avatar
  • 71
4 votes
2 answers
319 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}, E_{n}...
M Koerner's user avatar
2 votes
1 answer
2k 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, ...
Alexander Chervov's user avatar
0 votes
1 answer
147 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 ...
Alex Beutel's user avatar
1 vote
1 answer
445 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 ...
Alexander Chervov's user avatar
1 vote
1 answer
1k 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 ...
Alexander Chervov's user avatar
3 votes
0 answers
147 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 ...
Alexander Chervov's user avatar
0 votes
1 answer
218 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 ...
Alexander Chervov's user avatar
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
1 vote
1 answer
232 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 ...
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
4 votes
3 answers
648 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?
Kelvin Lee's user avatar
5 votes
1 answer
449 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 ...
Zahra Taheri's user avatar
2 votes
1 answer
502 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 ...
Alexander Chervov's user avatar
5 votes
2 answers
626 views

The chromatic number of a Hamming-related graph

For integer $1\le k\le n$, let ${\overline H}_n^k$ denote the complement of the $k$-th power of the Hamming graph on the vertex set ${\mathbb F}_2^n$; that is, two vectors from ${\mathbb F}_2^n$ are ...
Seva's user avatar
  • 22.8k
2 votes
1 answer
497 views

What is matrix A such that Hamming weight of [x, Ax] is maximal ? (Min distance of 1/2 block code?)

Everything over F_2. For any matrix $A$ define the number $N(A) = min_{x}$ HammingWeight $( [x , Ax])$. Where $x$ is vector and [a,b] is just concatenation of vectors: (a_1,...a_n, b_1,...,b_m). ...
Alexander Chervov's user avatar
1 vote
2 answers
286 views

How many k-nomials of deg N divisible by X^16+x^12+x^5 +1 ? (Spectrum of CRC-16-CCITT erroc-correcting code ?)

Let us consider polynoms over $F_2$. Consider the linear SUBSPACE of polynoms divisible by $x^{16}+x^{12}+x^5 +1$ and of degree less or equal $N$ (e.g. 40). Question: How many k-nomials belong to ...
Alexander Chervov's user avatar
4 votes
1 answer
343 views

What odd-length binary codes have Hamming weights restricted to be multiples of eight?

Let $G$ be a $k$ by $n$ binary matrix with row vectors $\lbrace \vec{x}_j {\rbrace} _{j=1}^k$. We can interpret $G$ as a generator matrix of a linear $[n,k]$ code $\cal{C}$ whose codewords consist of ...
Jim Harrington's user avatar
0 votes
1 answer
412 views

Is there any relationship between a tree(graph theory) and semi-metric?

suppose we have a tree(undirected) with $n$ vertices.The edges are weighted(distances). Is it possible to impose a semi-metric structure on the graph using these distances and adjacency matrix?
K A Khan's user avatar
  • 243
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
2 votes
1 answer
1k views

A covering problem for the Hamming cube

Consider the set of all $k$-subsets of $\{1,\dots,n\}$, naturally identified with a subset $A$ of $\{0,1\}^n$ where each element has exactly $k$ ones. Is there a sharp bound known for $\epsilon$-...
passerby51's user avatar
  • 1,639
19 votes
3 answers
2k views

Can you cover the Boolean cube $\{0,1\}^n$ with $O(1)$ Hamming-balls each of radius $n/2-c\sqrt{n}$?

(where c>0 and the balls need not be disjoint?) This is an embarrassingly simple question, yet somehow I couldn't find an answer (not even, "this is a well-known open problem") after spending some ...
Scott Aaronson's user avatar
2 votes
2 answers
351 views

Will "error locating codes" have higher rates than ECCs?

I'm wondering to detect all the errors (i.e. their positions) in a codeword $(c_0, c_1, \cdots, c_{n-1})\in Q$ where $Q$ is an alphabet set with size $q$, i.e., to know whether $c_i$ is faulty or not, ...
Kelvin Lee's user avatar
9 votes
0 answers
458 views

How small parallelograms are we guaranteed to get, when we select the two sides from different plane lattices?

Title question description: Select two lattices $\Lambda_1$ and $\Lambda_2$ (here a lattice=additive free abelian group without accumulation points) of maximal rank two in the real plane. We normalize ...
Jyrki Lahtonen's user avatar
4 votes
1 answer
213 views

Partial backups

Suppose you have some storage medium of a given size M, and can make some kind of backup on another medium of size B with M > B. You can choose the scheme to determine the contents of the backup. ...
Matthias Goergens's user avatar
5 votes
2 answers
3k views

Reed-Muller-Codes

Let $F$ be the field with two elements, $V_m=F^{2^m}$.Let $R(r, m)\subset V_m$ be the binary Reed-Muller Code. Define $R_m:=R(1, m)$. Then the dimension of $R_m$ is $1+m$ and its minimal distance is ...
Sebastian Petersen's user avatar
4 votes
3 answers
9k views

Computing channel capacities for non-symmetric channels

I'm studying information theory right now and I'm reading about channel capacities. I know that there are known expressions for computing the capacities for some well known simple channels such as ...
Kelvin Lee's user avatar
13 votes
3 answers
2k views

Hot-topics in error correcting coding related to interesting math. ?

What are topics in error-correcting coding which are related to interesting math. ? I am primarely interested in nowdays hot topics, but old days topics are also welcome. Let me try to mention what ...
7 votes
2 answers
2k views

Are algebraic geometry error correcting codes (Goppa codes) "good" ?

Question (informal version): Are algebraic geometry error correcting codes (V.D. Goppa codes) "good" ? Some details. There is certain construction of error-correcting codes by means of algebraic ...
Alexander Chervov's user avatar
0 votes
0 answers
191 views

Asymtotic Complexity Analysis using logarithms and binomial coefficients

On page 11 of "Smaller decoding exponents: ball-collision decoding" by Berstein et.al. they have the formula \begin{equation}\lim_{n \rightarrow \infty} \frac{1}{n}\log_{2}\left(\dbinom{k_{1}}{p_{1}}\...
Nick Peterson's user avatar
5 votes
2 answers
3k views

What is "automorphism group of an error-correcting code" ?

Here in Wikipedia is written: "The automorphism group of the binary Golay code is the Mathieu group M23." What is "automorphism group of code" ? PS Are there other nice examples of relation ...
Alexander Chervov's user avatar
2 votes
2 answers
387 views

Ax=0, estimate min(Hamming(x)) ? Equivalently: Bipartite graph. How to find (estimate) minimal number of vertices1 which are connected with EVEN number of vertices2 ? Equivalently: estimate minimal weight of error correcting code ?

Consider system of linear equations Ax=0 over $F_2$ (field with two elements {0,1}). Where number of variables is bigger than equations - so we have many solutions $x$. Question How to estimate ...
Alexander Chervov's user avatar
9 votes
2 answers
9k views

If graph is tree what can be said about its adjacency matrix ?

Question If graph is tree what can be said about its adjacency matrix ? And vice versa ? Especially I am interested in case when graph is bipartite graph. Such graphs are related to error-...
Alexander Chervov's user avatar
2 votes
0 answers
587 views

Adjacency matrices of graphs as parity check matrices of error correcting codes

Consider bipartite graph. Consider its adjacency matrix. It will have a form 0 A^t A 0 Take matrix $A$. Consider the null-space $L$ of $A$ over $F_2^N$. Question Can we say something about the $...
Alexander Chervov's user avatar