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

3
votes
1answer
262 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 ...
2
votes
1answer
228 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). ...
1
vote
1answer
188 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 ...
2
votes
0answers
172 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 ...
0
votes
1answer
284 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?
3
votes
2answers
175 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 ...
1
vote
1answer
370 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 ...
13
votes
3answers
733 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 ...
1
vote
1answer
230 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, ...
9
votes
0answers
288 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 ...
4
votes
1answer
192 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. ...
4
votes
2answers
900 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 ...
3
votes
3answers
2k 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 ...
7
votes
3answers
832 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 ...
5
votes
2answers
827 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 ...
0
votes
0answers
177 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} ...
0
votes
1answer
828 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 ...
2
votes
2answers
237 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 ...
4
votes
2answers
2k 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 ...
0
votes
0answers
298 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 ...
3
votes
1answer
298 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 ...
7
votes
3answers
603 views

Error correcting codes - basic question

Hi, I have a basic question regarding error correcting codes. Suppose I want to encode a finite information $F$ (say a finite string) into a string $x$ of $n$ bits ($n$ can be as large as you want), ...
1
vote
1answer
155 views

What are the key applications of the MacWilliams identities in coding theory?

The MacWilliams identities relate the weight enumerators of a code and its dual code. I treated the version for linear codes in my combinatorics class, but felt unsatisfied because I didn't have a use ...
0
votes
2answers
466 views

Hamming graphs and power series

Let $i$ and $h$ be two adjacent nodes in a Hamming graph and let $a$ be any positive real. Let us denote by $d_{ij}$ the distance between node $i$ and node $j$ in the graph. I'm trying to find a ...
6
votes
2answers
378 views

request sources about self-dual cyclic codes

X. Kai and S. Zhu in the paper "On cyclic self-dual codes", AAECC, vol. 19, pp. 509-525, 2008, at page 510 in line 6 said that, It is well Known that there are no cyclic self-dual codes over $F_q$ ...
1
vote
1answer
292 views

stabilizer always abelian? [closed]

Let G be a finite group acting on a finite dimensional vector space V. Let C be a nontrivial subspace of V. Let H be the subgroup of G that fixes C pointwise (the stabilizer of C). I'm fairly sure ...
0
votes
1answer
151 views

Subset-Free Codes

For each non-negative integer $n$, what antichain(s) in $\{0,1\}^n$ with the pointwise partial order: $\;\;$ 1. $\;$ have the most elements $\;\;$ 2. $\;$ minimize the maximum of its elements' sum ...
2
votes
1answer
720 views

The generator polynomial of cyclic code

Let $q$ be a power of prime number $p$ and let $F_{q^2}$ be a finite field of order $q^2$. Suppose that "-" be a conjugation operation that is defined as follow: $-:F_{q^2} ‎\longrightarrow‎ ...
4
votes
1answer
412 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 ...
0
votes
1answer
230 views

Lovasz theta function - uses

Lovasz theta function bounds the Shannon capacity of graphs. What are some other uses of the function - especially in asymptotic coding theory and optimization problems?
0
votes
1answer
227 views

Number of points on a complex sphere with pairwise inner product restriction

Considered the following inner products: $(1)$ $\langle x,y \rangle = \sum_{t=1}^{n}x_{t}y_{t}$ $(2)$ $\langle x,y \rangle_{c} = \sum_{t=1}^{n}x_{t}\bar{y}_{t}$ consider the following surfaces: ...
7
votes
2answers
551 views

Can you hide a letter without losing information?

Consider the following game between Alice and Bob. $\Sigma$ is a finite nonempty alphabet, $\Delta \notin \Sigma$ denotes a special symbol, and $k > 0$ is a positive integer constant representing ...
9
votes
1answer
278 views

An isoperimetric problem on the hypercube

Fix integer $n\ge 1$, and let $E=\{e_1,...,e_n\}$ denote the standard basis of the vector space ${\mathbb F}_2^n$. Thus, for a set $A\subset{\mathbb F}_2^n$, the sumset $A+E:=\{a+e\colon a\in A,\ e\in ...
5
votes
1answer
995 views

binary code with constant hamming distance

I want as many 80-bits words as possible with the constraint that the hamming distance between any couple of words is exactly 40. How many can I generate? Is there a generic formula telling me how ...
0
votes
0answers
105 views

A search for optimal order ideals

At the behest of Gerhard Paseman I'll describe the problem that I alluded to in name for a partial order. Let $M = M(\infty)$ denote the set of all finite subsets of the positive integers ...
0
votes
1answer
260 views

Optimization problem related to parity check code

I have n data blocks and k parity blocks distributed across m boxes. Each parity block is Ex-or of some data block (for ease of understanding we can assume each data/parity block as a single bit) and ...
2
votes
1answer
301 views

Lee codes and $n$-torus

This is in continuation with this post: Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric Codes over alphabet $\mathbb{Z}_{q}$ of length $n$ for the Lee metric ...
1
vote
0answers
206 views

Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric

Slight extension of cross posting from http://cstheory.stackexchange.com/questions/7408/lee-metric-gilbert-varshamov-and-hamming-bounds-for-larger-relative-distance-rang (closed there) The following ...
20
votes
2answers
1k views

What is the complexity of this problem?

Recently on Dick Lipton and Ken Regan's blog there was a post about problems of intermediate complexity, that is, NP problems that are harder than P but easier than NP-complete. The main message of ...
2
votes
1answer
248 views

Doing column permutation under row overlap constraint

In coding theory, there are parity-check codes whose parity-check matrices $H$ are generated via column permutations. For instance, the binary LDPC codes constructed in Gallager's 1962 IRE Trans paper ...
4
votes
1answer
266 views

Probability of false decoding with LDPC codes

It is well known that given a binary linear code $C$ under maximum likelihood decoding the probability of false decoding $P_C$ in a Binary Symmetric Channel with cross over probability $p$, in other ...
6
votes
5answers
597 views

covering by spherical caps

Consider the unit sphere $\mathbb{S}^d.$ Pick now some $\alpha$ (I am thinking of $\alpha \ll 1,$ but I don't know how germane this is). The question is: how many spherical caps of angular radius ...
15
votes
1answer
690 views

Codes, lattices, vertex operator algebras

At the end of "Notes on Chapter 1" in the Preface to the Third Edition of Sphere packings, lattices and groups, Conway and Sloane write the following: Finally, we cannot resist calling attention ...
0
votes
1answer
319 views

Fixed Hamming distance property of binary deletion correcting codes

Let $x=(x_1x_2...x_n)$ be a binary sequence of length $n$. The Varshamov-Tenengolts code $VT_0(n)$ consists of all binary vectors $(x_1, . . . , x_n)$ satisfying $\Sigma_{i=1}^n i*x_i \equiv0 \pmod ...
2
votes
1answer
471 views

Even lattices and binary codes

I have a maybe simple question about even positive-definite lattices and lattices coming from binary codes. They seemed to be used in framed vertex operator algebras. What is known about even ...
14
votes
1answer
873 views

How to keep subsets disjoint?

Given positive integers $n$ and $k\le 2^n$, how to choose a subset $C\subset\{0,1\}^n$ of size $|C|=k$ to maximize the number of pairs $(c_1,c_2)\in C\times C$ with the supports of $c_1$ and $c_2$ ...
1
vote
1answer
277 views

Large subgroups of the Hamming cube

Let's consider the abelian group $\mathbb{Z}^N_2$ equipped with the Hamming metric (the hypercube). Suppose I have a subgroup of this hypercube (not necessarily a subcube) which is generated by a set ...
7
votes
4answers
1k views

“sparse graphs are locally tree-like”

I would like to be able to state with confidence that sparse graphs (graphs with small numbers of edges) are locally tree-like (they have few short cycles). Apparently "Sparse graphs are locally tree ...
1
vote
1answer
401 views

Matrix version of Berlekamp Massey algorithm

What are the most obvious generalizations of Berlekamp Massey algorithm [1] to matrix sequences? [1] Massey, J. L., "Shift-register synthesis and BCH decoding", IEEE Trans. Information Theory ...
2
votes
1answer
273 views

Optimal binary code for points in a metric+probability space

Does anyone know of any results on this topic? Basically I'm considering this problem. You have some space $X$ from which you can draw points $x$ and $y$, a distance metric $d(x,y)$, and a ...