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

2
votes
2answers
181 views

Need help with paper written in Russian… Yorgov's paper on self-dual codes with automorphisms of odd order

I came across this paper by V.I.Yorgov named "Binary self-dual codes with automorphisms of odd order". (Actually I was first reading another paper by Borello that cited this paper. It later become ...
3
votes
0answers
193 views

On weight enumerators of codes

Are there $[n,k]_q$ constant rate $\frac kn$ and constant alphabet linear code families with automorphism group of size $\Omega((n-n^\beta)!)$ that have minimum distance $d=O(n^\alpha)$ and number of ...
1
vote
2answers
44 views

Finding minimum weight codeword of MDS RS code

For a $[n,k,n-k+1]_q$ Reed Solomon code is there a polynomial time algorithm to find at least one minimum weight $(n-k+1)$ codeword? I searched in literature and I could not find one and hence I am ...
5
votes
0answers
198 views

Partitions of $\mathbb{F}_2^n$ related to perfect $1$-error correcting binary codes

Edit. After a computer search found an example for $n=8$, I've rephrased my original question as a conjecture. This question is motivated by the existence of perfect $1$-error correcting binary codes,...
1
vote
1answer
121 views

Effects of shortening and puncturing on codes

Given a binary block code $C=[n,k]$ of codeword length $n$, and dimension $k$. Suppose I've determined these properties for it : $d_{min}$ (minimum distance), $N_{dmin}$ (number of codewords at $d_{...
0
votes
0answers
24 views

is any closed form relation that can state the error probability of code versus its variable and check node degree distributions?

In Low Density parity check code design, when bit (or frame) error probability of code is the objective of the design, we need a closed form relation between error probably (or even an approximate or ...
0
votes
1answer
75 views

How to analysis the relationship between the accuracy of erasure and the probability of decoding in RS code

As we all know, in RS code, when provide erasure (the position of error symbol), the decoding capacity of RS code is stronger. Specifically, $2e+v \leq (n-k)$, where $e$ is the number of errors, $v$ ...
1
vote
1answer
89 views

Weighted counting of circular codes

Given a circular code $X$ (for example: $X=\{ w,b \}$) with generating function $u(z)=\sum\limits_{k=0}^{\infty}{u_k z^k}$ (in this example : $u(z)=2z$), the generating function $p(z)=\sum\limits_{k=0}...
2
votes
0answers
85 views

Maximum number of $4$-cycles

Suppose we have a balanced bipartite planar maximum degree $k$ graph. How many such graphs on $2n$ vertices have at most $f(n)$ maximum number of $4$ cycles for a given function $f:\Bbb R^+\...
4
votes
1answer
230 views

Is the direct sum in Maschke's Theorem an orthogonal decomposition?

I am reading a paper on coding theory, and it uses a statement, which was claimed to be a reformulation of Maschke's Theorem. But I felt that was false... Let's say $\mathcal(V):=\mathcal{F}_2^n$ is ...
3
votes
0answers
54 views

Bounding the number of information sets in a linear binary code

A pretty well-known theorem regarding linear $(n,k,d)$ codes is that every $n-d+1$ coordinate positions contain an information set, but not all $n-d$ coordinate positions do. This is equivalent to a ...
3
votes
1answer
170 views

Relations between the parameters of the Best Linear Code

Let the triple $(n,k,d)$ be length and dimension and minimum distance of a code, respectively. For a fixed given numbers $n$, $k$ and $d$, what relations there are between BKLC$($GF(2)$,n,k)$ ,BLLC$($...
5
votes
1answer
440 views

Is this graph 3-colorable?

Consider the permutations of $0,1,1,2,2,3,3.$ Each permutation is corresponding to a vertex in graph $G$. So, the graph $G$ has $630$ vertices. Each vertex has exactly 6 neighbors. $P$ is connected $...
5
votes
1answer
164 views

Finite field analogue of Chebotaryov theorem on roots of unity?

Chebotarev's theorem on roots of unity says that all the minors of a prime-length DFT matrix over the complex numbers are nonzero. I was wondering if there was an analogue for finite fields. More ...
2
votes
0answers
171 views

Capacity of a channel with random phase rotation

Consider a wireless channel $h=e^{j\theta}$, where $\theta$ is a uniform random variable in $[0,2\pi]$ independent of the input messages and the independent of the noise. The channel randomly rotates ...
6
votes
0answers
97 views

irregular LDPC code construction algorithm

I want to construct a sparse random binary matrix ${{\bf{H}}_{m \times n}}$ that has the following properties 1- Faction of columns of weight $i$ is ${v_i}$ . 2- Fraction of rows of weight $i$...
0
votes
2answers
78 views

Binary Codes and its distance [closed]

Find n binary codes of length n such that distance between each pair is n/2 , where n is a even number , if possible?How to generate all codes? for example if n=4 we have 1110,1101,1011,0111 each pair ...
3
votes
1answer
112 views

Effects of many degree-2 variable nodes in the Tanner graph during the decoding of LDPC codes

Suppose that we have a LDPC code $C$ with a $(n -k )\times n $ parity check matrix $H$, and there exist approximately $ \sqrt n$ numbers of degree-2 columns. It means that there are approximately $\...
1
vote
1answer
71 views

Optimal covering and CSPNG

Consider a function $f: \{0,1\}^n \to \{0,1\}^{cn}$, where $c>1$. A random $f$ with high probability generates optimal covering of $\{0,1\}^{cn}$, i. e.: $\forall x \in \{0,1\}^{cn}$ $\exists y \...
13
votes
3answers
1k views

A question on representation of graphs

Take a complete graph $K_n$. You want to assign a vectors from $\Bbb F_2^d$ to every edge such that sum of vectors in every simple cycle does not sum to $0$ vector. The question is what is minimum $d$ ...
3
votes
0answers
99 views

Rank of a particular matrix

Denote $P_{2n}$ to be collection of homogeneous total degree $2$ real polynomials in exactly $2n$ variables such that coefficient of every monomial is either $1$ or $-1$. Split variable set into ...
4
votes
0answers
127 views

Application of finding shortest paths on Cayley graphs

For a fixed integer number $m$, Consider Cayley graph defined by all m-cycles in Symmetric group $Sym(n)$. I know that for $m=2$, there are some applications of finding shortest paths (or distance ...
2
votes
0answers
84 views

The significance of the Parvaresh-Vardy curve

Even though this seems like a computer science question, it is purely mathematical and concerns polynomials and curves over finite fields. Consider the Parvaresh-Vardy list decoder. As I understand ...
2
votes
1answer
140 views

Probability of Hamming weight

Given $s,t\in(0,1)$, $c>1$, $n\in\Bbb N$, pick ${n^t}$ random vectors $\{v_i\}_{i=1}^{{n^t}}$ such that each $v_i\in\{x\in\{0,1\}^{2^n}:|x|_{hamming}={2^{n-n^s}}\}$. Denote $v_j\cap v_j$ to be ...
3
votes
1answer
118 views

Maximal neighbour-full partition of $\{0,1\}^n$

What is the largest complete minor of the $n$-dimensional hypercube? (which we call $k(n)$) Alternatively, what is the partition of $\{0,1\}^n$ with each set connected and neighboring each other that ...
2
votes
0answers
230 views

Hamming weight probability of projections

Given $s,t\in(0,1)$, $c>1$, $n\in\Bbb N$, pick $2^{n^t}$ random vectors $\{v_i\}_{i=1}^{2^{n^t}}$ such that each $v_i\in\{x\in\{0,1\}^{2^n}:|x|_{hamming}={2^{n-n^s}}\}$. If $v_i^\perp$ is ...
1
vote
0answers
94 views

How do you use the bits you get back from Bits Back Coding?

Bits Back coding is a scheme to transmit an observation x. You can read about it here [1]. To my understanding, it works like this: The encoder samples a message z from a distribution Q(z|x) that it ...
0
votes
1answer
96 views

Information theoretic common sequence agreement (not secret key)

Supposing Alice and Bob share $\rho$-correlated sequences in $\{0,1\}^n$, what coding theory based schemes are available for Alice and Bod to extract sequences $A,B\in\{0,1\}^n$ respectively such that ...
7
votes
1answer
167 views

lower bound on A(k,4,floor(k/2))

A(k,4,r) is the independence number of the Johnson graph J(k,r). What is the best known asymptotic lower bound on A(k,4,floor(k/2)) ? I only obtained $\frac{{k\choose\lfloor{k/2}\rfloor}}{\lfloor{k^2/...
3
votes
1answer
189 views

Parity-check matrix for code with variable block size and minimum distance

Consider a linear error-correcting code with symbols in $GF(q)$, with codewords of length $k$ generated from messages of length $n$ and minimum distance $d+1 = k-n+1$. In the cases of interest, $q = ...
11
votes
2answers
499 views

“The Two Sheriffs” puzzle -2: threshold for security

I've already asked a question “The Two Sheriffs” puzzle with wrong assumption. Yoav Kallus in his amazing answer using Fano plane showed that the problem has a solution in the case of seven suspects. ...
30
votes
1answer
2k views

“The Two Sheriffs” puzzle

This puzzle is taken from the book Mathematical puzzles: a connoisseur's collection by P. Winkler. Two sheriffs in neighboring towns are on the track of a killer, in a case involving eight ...
1
vote
1answer
68 views

Bound on the weight of the minimum weight generator of [n,k] cyclic codes?

I'm looking at creating sparse generator matrices for cyclic codes of a given length and dimension. A generator matrix of an [n,k] cyclic code can be expressed as $G = \begin{bmatrix}g_0 & g_1 &...
1
vote
1answer
96 views

Optimal covering

Let consider a problem of optimal covering of Hamming space. So we have Hamming space $\{0,1\}^n$ and some integer $r$. We want to find a set $A \subseteq \{0,1\}^n$ such that any point from $\{0,1\...
3
votes
0answers
175 views

PRNG and coding theory

Let $k, n \in \mathbb{N}$, $k = (1 - \epsilon)n$ where $1 >\epsilon > 0$. I want to find $f: \{0,1\}^k \to \{0, 1\}^n$ such that: 1) $f(a) \not= f(b)$ if $a \not=b $ 2) for any $x \in \{0,1\}...
3
votes
2answers
225 views

Picking codewords that are close

I posted this question in http://math.stackexchange.com/questions/1142698/picking-codewords-that-are-close a week back. Let $[n,k,d]$ be a linear code over $\Bbb F_q$ with minimum distance $d$ and ...
3
votes
3answers
106 views

Block error-correcting codes over inhomogeneous alphabets

For $n := (n_1,\dots,n_N) \in \mathbb{N}_{>1}^N$, let $X_n := \prod_{j=1}^N [n_j]$, where as usual $[m] := \{1,\dots,m\}$. Are there any known generic constructions for (Hamming) sphere ...
1
vote
1answer
397 views

Correlation between two continuous-time stochastic processes

Consider two continous-time stochastic processes $\{A(t)\}_{t \ge 0}$ and $\{B(t)\}_{t \ge 0}$ with $A(t)=t$ and $B(t)=t$. Each process starts at $t=0$ and emits "ticks" at increasing time slots. For ...
1
vote
0answers
195 views

Polynomial existence over finite field

Denote $\mathcal{F_n}$ as collection of multiaffine polynomials $f\in\Bbb F_2[x_1,\dots,x_n]$. Denote total degree of $f\in\mathcal{F_n}$ as $deg(f)$ (note $deg(f)\leq n$). Denote $e_i=(0,\dots,0,\...
2
votes
0answers
88 views

On subset of Deterministic games

Denote strings $u,v$ from $\{0,1\}^n$. Denote concatenated pair $[uv]$. Denote $$[uv]_{1}=\{[uv]\oplus e_i\}_{i=1}^{2n}$$ collection of pairs with Hamming distance $1$ from $[uv]$ string ...
2
votes
2answers
354 views

Minimally intersecting subsets of fixed size

The question I have, is how to generate the following collection of subsets: Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each ...
2
votes
2answers
183 views

Hamming graph and independent sets

I'm defining the Hamming graph $H(d,q)$ in the usual way, so we have a set $S$ of $q$ elements, the hamming graph $H(d,q)$ has vertex set $S^{d}$ (the set of all ordered $d$-tuples of elements of $S$) ...
4
votes
1answer
134 views

Balanced binary code that “resists” local decoding?

I am looking for a construction that can be stated as the following coding problem: a binary code with good distance ($d = \Omega(n)$ where codeword length is $n$) that "resists local decoding" in the ...
13
votes
1answer
625 views

Maximum number of vectors in a hypercube satisfying given conditions

$\mathcal{C}$ is a collection of binary vectors of length $n$, i.e. $\mathcal{C}\subseteq\{0,1\}^n$. For arbitrary $x,y,z\in\mathcal{C}$ and $x\neq z$, $y\neq z$, there always holds that the Euclidean ...
32
votes
1answer
606 views

What measurable quantity can constrain the number of odors human can discriminate?

This is not a very typical MO question, but I hope you bear with me. It concerns a recent disagreement in the biology literature about how many different odors humans can discriminate. The authors of ...
0
votes
2answers
130 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
1answer
112 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
121 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
166 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
118 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 ...