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
2answers
474 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
397 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
312 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
152 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
741 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
448 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
245 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
233 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
561 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
288 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
1k 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
106 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
266 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
308 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
214 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
263 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
322 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 ...
8
votes
5answers
784 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
751 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
328 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
476 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
958 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
286 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
424 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
278 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 ...
4
votes
4answers
624 views

how to find vector $(\pm 1, \pm 1, \pm 1, … \pm 1)$ which is most close to given vector (r_1,…r_l) ? Is it NP-problem ? What algorithms are available ?

Given: some vector $R=(r_1...r_l)$ - real numbers, and a set of distinct vectors with $+1$ or $-1$ coordinates $$\begin{array}{c} V_1=(c_{1,1} ... c_{1,l}),\\\ V_2=(c_{2,1} ... c_{2,l}),\\\ ...
10
votes
3answers
605 views

MacWilliams Identity for Asymptotic Weight Spectrum of a Code

Introduction Let $C$ be a code of block length $n$ having $A_i^C$ words of Hamming weight $i$, for $i\in [n]$, where $[n]:=\{0,\ldots,n\}$. Then, the sequence $\{ A_i^C \}_{i \in [n]} $ is called the ...
4
votes
2answers
394 views

A Boolean function that is not constant on affine subspaces of large enough dimension

I'm interested in an explicit Boolean function $f \colon \{0,1\}^n \rightarrow \{0,1\}$ with the following property: if $f$ is constant on some affine subspace of $\{0,1\}^n$, then the dimension of ...
7
votes
1answer
2k views

12 balls weighing puzzle

In an article describing the twelve balls weighing problem, the author mentions a solution that involves the finite projective plane of order 3, discovered by Rick Wilson. Does anyone know what this ...
1
vote
1answer
328 views

Algorithm for generating a size k error-correcting code on n bits

I want to generate a code on n bits for k different inputs that I want to classify. The main requirement of this code is the error-correcting criteria: that the minimum pairwise distance between any ...
5
votes
2answers
555 views

Binary codes with large distance

Suppose $C \subset \lbrace 0,1\rbrace^{n}$ is a binary code with distance $\delta * n$, for $1/2 < \delta < 1$. Can $|C|$ be arbitrarily large (if I allow n to be arbitrarily large)? Note that ...