0
votes
2answers
73 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$?
0
votes
0answers
23 views

Coding for channels with concentrated error

A note: I accidentally over-simplified my first attempt at this question to the point of triviality - unfortunately, I didn't recognize this until after I had already placed a bounty to draw ...
-1
votes
1answer
71 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
91 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 ...
2
votes
1answer
79 views

Mutual information staying constant under composition of channels

Consider the following scenario: one has 2 communication channels $C_1$ and $C_2$. Denote by $p(x)$ the input probability distribution. The mutual information between the input and the output of ...
4
votes
2answers
129 views

Another formulation of error-correcting coding problem

Consider classic error-correcting problem: there is finite set $A$ and string $a_1...a_n$, $a_i \in A$ in the begin. in the end we have $b_1...b_n$. Set places of errors $E = \{i| a_i\not= b_i \}$, ...
3
votes
0answers
89 views

Certain subgroup of automorphism groups of binary codes

Suppose that $C$ is an binary linear code of length $n$ and dimension $k$ (i.e. it's a $k$-dimensional linear subspace of $\mathbb{F}_2^n$). As usual, the automorphism group of $C$ is the subgroup of ...
4
votes
0answers
106 views

Fully Homomorphic Error Correction?

Consider a field $F$. Suppose we have two vectors $a,b\in F^n$, and an invertible matrix $G\in F^{n\times n}$. Let $c\in F^n$ be the point-wise product of $a$ and $b$, that is, $c_i=a_ib_i$. Let ...
1
vote
1answer
301 views

Cyclic Hamming Code

I know that Hamming codes can be arranged in cyclic form. But my question is how can I prove this. My idea was to find a generator/primitive polynomial $p(x)$? For example I want to show that the ...
3
votes
2answers
171 views

Binary codes with upper bound on pairwise distance

A fundamental problem in coding theory is: Given positive integers $k\le n$, determine or bound the maximal cardinality of a set $S\subset \mathbb{F}_{2}^{n}$ such that $\forall x,y\in S: x\ne ...
2
votes
0answers
105 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 ...
0
votes
1answer
170 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 ...
4
votes
2answers
223 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 ...
1
vote
1answer
117 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 ...
3
votes
1answer
242 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 ...
4
votes
1answer
207 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 ...
1
vote
1answer
330 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, ...
0
votes
1answer
276 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 ...
2
votes
0answers
123 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 ...
0
votes
1answer
179 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 ...
3
votes
3answers
493 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 ...
1
vote
1answer
191 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 ...
3
votes
3answers
418 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?
2
votes
1answer
285 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 ...
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
187 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
171 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
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, ...
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
829 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
824 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
1answer
822 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 ...
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 ...
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$ ...
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: ...
1
vote
0answers
204 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 ...
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
264 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 ...
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 ...
5
votes
2answers
538 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 ...