Questions tagged [coding-theory]
Use this tag for questions about source-coding and channel-coding in information theory, error-correcting codes, error-detecting codes, and related algebraic and/or combinatoric constructions. This tag should not be used for questions about programming.
1,901 questions
2
votes
1
answer
46
views
Upper bound on the intersection of two radius-$r$ Hamming balls in binary constant-weight codes when codewords are at Hamming distance 2
Let $\mathcal{B}(n,w)$ be the set of all binary vectors of length $n$ and constant weight $w$, i.e.,
$\mathcal{B}(n,w) = \{ x \in \{0,1\}^n : \mathrm{wt}(x) = w \}$.
The Hamming ball of radius $r$ (in ...
- 21
1
vote
0
answers
87
views
Deletion error correction code for $\mathbb{Z}_{127}$
I'm having trouble finding an insdel code that works for elements of $\mathbb{Z}_{127}$. Most of what I find requires a square of a prime ($\mathbb{Z}_{121}$ is my closest) or to augment the alphabet ...
- 142
5
votes
0
answers
83
views
How can we rigorously bound the performance of the Fano code?
There are estimates on the expected codeworth length of the Fano symbol code (not to be confused with the Shannon code), but I don't know where they come from. Some definitions:
Let $\mathcal{X}$ be a ...
- 48.2k
1
vote
2
answers
166
views
Syndrome decoding of BCH codes
I have a problem understanding the differences in two syndrome decoding approaches for BCH codes.
I understand that syndrome decoding of a message $m$ amounts to evaluate the syndrome $s$ of $m$, and ...
- 13
1
vote
2
answers
217
views
Are there examples of codes with high distance relative to length?
For fixed $q,n$, where $q$ is prime are there examples of high distance codes of length $n$ over $ \mathbb{Z}_q $ of large distance relative to $n$? Preferably with $q$ small. For instance the
(...
- 530
1
vote
0
answers
53
views
Relation between spherical codes and complex spherical code
I am interested in complex spherical codes, which are defined as a set of complex d-dimensional unit vectors $\vec{x}_i\in \mathbb{C}^d$ with $|\vec{x}_i|=1$ such that:
\begin{align}
\max_{i\neq j} |\...
- 41
1
vote
0
answers
66
views
Linear property of decoding algorithm in erasure codes
Recently, I learned about erasure codes from Richardson & Urbanke's Modern Coding Theory, and I want to know the necessary condition to make a decoding algorithm satisfy the linear property. To ...
- 249
2
votes
0
answers
210
views
Reed Solomon original view encoding syndrome decoder
Question: who invented this decoding method?
Original view encoding is described in the Wikipedia article:
original view encoding
This is based on Reed and Solomon's 1960 paper, which was quickly ...
- 872
0
votes
1
answer
77
views
Obtaining the same Generalized Reed Solomon code by taking the multiplicative inverse of the evaluation points.
This question comes from https://users.math.msu.edu/users/halljo/classes/codenotes/grs.pdf problem 5.1.2.
Consider the code $C = GRS_{n,k}(\alpha, v)$ where $\alpha = (\alpha_1, \ldots, \alpha_n)$ are ...
- 1,168
2
votes
1
answer
110
views
Number of hypercube graph vertices with given in-degrees
Is there always an orientation of the edges of the hypercube graph $Q_d$ so that there are $\big\lfloor \frac {d2^{d-1}}k\big\rfloor$ vertices each with in-degree at least $k\in(\frac d2,d)$?
- 10.5k
0
votes
0
answers
55
views
How to calculate frame error rate of BCH Code in very high precision?
I want to calculate frame error rate(FER for short) of BCH Code in high precision, the formula is:
$$FER = 1 - \sum_{i=0}^t {n \choose i} p^i(1-p)^{n-i}$$
where $n = 2560, t = 41$, $p = 10^{-4}$ to $...
- 101
4
votes
1
answer
58
views
What's the importance of this condition in the definition of a quadratic residue code?
The quadratic residue code of length $n$ over $\mathbb{F}_p$ where $n$ and $p$ are primes is defined only when $p$ is a quadratic residue modulo $n$. Why is this restriction placed here? What goes ...
- 221
1
vote
1
answer
81
views
Using orthogonal relation of Krawtchouk polynomials
I am reading the paper Covering Radius and Dual Distance by A Tietaevaeinen. On page 8, it says
Because $K_u(i;q,n-1)/(i-\alpha_1)$ is a polynomial of $i$ of degree less than $u$, we thus see, by (3....
- 2,099
1
vote
0
answers
86
views
Which codimension $1$ space contains the smallest number of balanced vectors?
Let $F = \{0,1,2\}$ be the ternary finite field. A vector $b \in F^n$ is balanced if
$0,1,2$ appears in $b$ the same number of times ($n$ must be a multiple of $3$).
Let $B \subset F^n$ be the set of ...
- 439
1
vote
1
answer
120
views
Average weight increase of $k$-dimensional vector spaces in coding theory
In coding theory we look at k-dimensional subspaces $C$ of $\mathbb{F}_q^n$, where $ \mathbb{F}_q$ is a finite field with $q$ Elements. We denote by $ \check{C_i}$ the subspace of $\mathbb{F}_q^{n-...
- 23