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,883 questions
0
votes
1
answer
47
views
+50
Transforming $\sum_{j= 1}^{i}jx_{j}\equiv n\pmod{b}$ into $\sum_{j= 1}^{i}x_{j}q^{j- 1}\equiv {n}'\pmod{a}$ for constrained coding
I am working on a constrained coding problem where I need to construct a sequence $\left ( x_{1}, x_{2}, \ldots, x_{n} \right )$ so that:
$$\sum_{j= 1}^{i}jx_{j}\equiv n\pmod{b}$$
where $x_{j}\in\left\...
- 43
4
votes
0
answers
53
views
An interesting volume inequality in Hamming ball with total variation constraint, help me
Here is an interesting inequality that is simulated to be correct but I can not prove it. Can someone helps me?
The question is that: For any binary vector $\mathbf{y}\in\{0,1\}^n$, prove that
\begin{...
- 41
0
votes
0
answers
71
views
+50
To find combinatorial or algebraic invariants that imply $a\succcurlyeq b$ without resorting to full symbolic algebraic computation
In the context of polar code design over BEC channels, the capacity function associated to a binary string $a\in\left\{ 0, 1 \right\}^{n}$ is defined recursively by
$$I_{0}\left ( x \right )= x^{2}, \...
- 43
0
votes
0
answers
31
views
Asymptotically good code over finite alphabet with non-trivial dual weight
I'm looking for a linear code $𝐶$ with the following properties:
It's over a constant-size alphabet (i.e., $𝐶 \subseteq \mathbb{F}_q^n$ with $q$ fixed).
Constant rate (i.e., $|C| \in \Omega(n)$).
...
- 658
1
vote
2
answers
62
views
Complementary substrings with ordering
Let $X = \{1, \ldots, n\}$, and $C = \{x_1, \ldots, x_k\}$, $D = \{y_1, \ldots, y_k\}$ be subsets of $X$ of size $k: 2k < n$, with $C \cap D = \emptyset$. We define $C<D$, if $x_j < y_j$ for ...
- 493
1
vote
0
answers
22
views
Can we use the Plotkin construction for quasi-cyclic/constacyclic codes over $\mathbb{F}_2$ of even length?
For binary cyclic codes $C$ of even length $2n$, we can use Van Lint's construction to analyse its properties. In particular, for codes with generator matrix $g_1^2(x)g_2(x)$, we can look at two ...
- 227
0
votes
1
answer
49
views
Why opposite notations for polynomial basis representation in Algebra (Fields) as compared to that in Coding theory?
In books on Fields, an extension field polynomial representation uses the notation where right most bit is considered as $a_0$ & left most is $a_{n-1}$
For e.g. in $F_{2^4}$
$11 = 1,0,1,1 = x^3 + ...
- 662
7
votes
2
answers
588
views
Finite Fields in Coding Theory
I have a reasonable understanding of finite fields. But I have a few questions in this part I came across in a Coding Theory Book.
The Book is Coding Theory, A First Course by San Ling & Chaoping ...
- 662
1
vote
1
answer
68
views
Computation of the minimum distance of $q$-ary linear codes with large $q$
Let $C$ be a $q$-ary $[n,k,d]$ code. It is well known that finding the true minimum distance $d$ of $C$ is NP-hard in general, so we probably cannot hope for a subexponential algorithm to e.g. find a ...
- 280
2
votes
0
answers
59
views
Dual view of Reed Solomon codes: same codeword viewed as values calculated from a polynomial or as coefficients to a polynomial
A summary of the video linked to below: with given constraints on the evaluation points used to generate a RS codeword $\{1, \gamma, \gamma^2, \ldots, \gamma^{q-2} \}$, that codeword of a set of ...
- 47
5
votes
2
answers
198
views
Is there a way to show a (6,3) Hamming code using Venn Diagrams?
I saw a very good explanation of a (7,4) Hamming Code using Venn Diagrams
message = $x_1\space x_2\space x_3\space x_4$
encoded message = $x_1\space x_2\space x_3\space x_4\quad x_2 + x_3 + x_4\...
- 662
7
votes
1
answer
886
views
How many 10 digit numbers.
So I was calling someone when I realized that I dialed a number wrong by $1$ digit and the call went to someone else.
Now I wanted to make sure that it did not call anyone if the phone number was ...
- 760
0
votes
1
answer
50
views
Capacity of Gaussian Channels: Shannon’s Second Theorem - Achievability Proof
I was reading the achievability proof of Shannon's second theorem and my textbook reports the following :
"Indeed, as for the discrete counterpart, we can choose a good codebook and delete the ...
- 3
1
vote
0
answers
72
views
On the coefficients of linear combinations of some polynomials.
Let $m$ be an integer divisible by $3$. Let
$$
f_j(y) = (1+14y+y^2)^{m-3j}(y(1-y)^4)^j, \quad j \in [0,m/3]
$$
and $g_j(y) = (1+17y+187y^2+51y^3)f_j(y)$ for $j \in [0,m/3]$.
The question is: Is there ...
- 307
1
vote
0
answers
36
views
Linear program bound for orthogonal arrays
In Orthogonal Arrays by Hedayat, Sloane, and Stufken, (4.29) says $|C|\leq\frac{s^k}{N_{LP}(k,d)}$, where $C$ is a simple code (codewords are distinct) with minimum distance $d$ and dual distance $d^\...
- 1,987