coding-theory

Backwards random codebook generation

by

$$X \longrightarrow \fbox{$\phantom{\int}P_{Y|X}\phantom{\int}$}\longrightarrow Y$$ The information capacity of this channel is $C=\max_{P_X} I(X;Y)$. Any rate $C-\varepsilon$ can be achieved by fixing a large-enough blocklength $n$ and associating each message $m\in \{1,\dots,2^{n(C-\varepsilon)}\}$ with a codeword $x^n_m\in \mathcal{X}^n$, each component of $x^n_m$ i.i.d. $\sim P^\ast_X$ where $P^\ast_X$ is the distribution that maximizes $I(X;Y)$. The distributions these codewords … Read more

What is the least compressible probability distribution? (under entropy constraint, for an expected squared error metric)

by

This is a cross-post from cstheory after a week with no answers/comments; I’m hoping someone here may have some thoughts. Consider a distribution D over the reals, a real parameter H∈R+, and an integer parameter k∈N. The Entropy-Constrained Quantization problem asks what is the best set of quantization levels Q⊂R, with |Q|≤k, that minimizes the … Read more

Intersecting Hamming spheres: is |Ak+E|≥|A||A\stackrel k+E|\ge|A|?

by

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 general form of the question I am interested in is as follows: Given integers n≥k≥1 and N≤2n, for a collection of N Hamming spheres in … Read more

Binary linear codes, juxtaposition and similarity

by

My question is about binary linear codes and some properties which are fairly straightforward but I don’t know whether there is a name for in the literature. I haven’t been able to find anything on it. This has applications to something I’m working on defining some algebras from codes. Let C be an (n,k) binary … Read more

Counting overlaps for nn Boolean vectors in a Hamming ball of radius rr

by

Say I have set of m Boolean vectors B={x1,…,xm} where xi∈{0,1}n. We know the following about the vectors xi∈B: (i) ‖ for all x_i \in B (at least 1 non-zero coordinate and one zero coordinate) (ii) d(x_i, x_j) \geq 1 for all x_i, x_j \in B (each vector is distinct) (iii) d(x_i, x_j) \leq r … Read more

Polynomial time decodable binary linear codes achieving $GV$ bound?

by

Are there explicit or random construction of linear codes that achieve the $GV$ bound with polynomial time decodable property with alphabet size $q=2$? Tsfasman, Manin, Vladut beat the bound at alphabet size $q\geq49$ and so is there any evidence the bound can be beaten at $q=2$ (I see possibility mentioned in Sudan’s and Guruswami’s notes … Read more

Partial backups

by

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. After you made that partial backup, an adversary (or a random process) will make a … Read more

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

by

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 all linear combinations of these vectors (with arithmetic defined for GF(2)). Let $H$ be a $(n-k)$ by $n$ binary matrix with … Read more

Self-dual binary codes of Hamming weight divisible by 8?

by

Recall that a binary code is a subgroup $C \subset \mathbb F_2^n$; the elements of $C$ are called code words. The Hamming weight of a code word $c\in C$ is the number of $1$s in it. A binary code is self-dual if $C = C^\perp := \{v \in \mathbb F_2^n : \langle v,c\rangle = 0\in … Read more