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,829
questions
1
vote
0
answers
9
views
Varshamov bound is stronger than Gilbert bound
In the class of Error-correcting Code, the professor showed us $2$ result:
Theorem 1(Gilbert)
$$ B_q(n,d)\geqslant \frac{q^n}{V_q(n,d-1)}$$
where $V_q(n,d-1)$ denotes the cardinality of the ball $B_{d-...
- 357
2
votes
1
answer
32
views
How to find the generator matrix for $C/C^{\perp}$?
Background/my workings:
I am reading a paper which talks about the $[6,5,2]$ classical binary single parity-check code $C$.
I understand that from the given parameters we can find its parity check ...
- 329
0
votes
0
answers
14
views
The proof of asymptotic Giibert-Varshamov lower bound
In a book, the Gilbert-Varshamov lower bound is given as follow.
Suppose $0 \leq \delta < \frac{1}{2}$. Then there exists an infinite sequence of $[n,k,d]$ binary linear code with $d/n \geq \delta$ ...
- 161
4
votes
0
answers
47
views
Relationship between BCH code and asymmetric Ramanujan bipartite graph ( possibility for a research collaboration)
I have been working on a research topic that deals with the binary matrices arising from the BCH codes by selecting code vectors of specific weight while discarding the rest of the code vectors that ...
- 41
1
vote
1
answer
58
views
Generate Max Number of Sequences Separated by Hamming Distance of 3
I'm interested in whether there is an algorithm for generating the maximum possible number of DNA sequences that are $7$ nucleotides long that differ by at least $3$...
- 11
0
votes
1
answer
65
views
Finding BCH code syndromes
I' m not getting how syndromes are calculated for bch codes so I tried finding examples but still I don't seem to have it
To calculate the first syndrome for the received message polynomial
$R(x)=1+...
- 315
6
votes
2
answers
268
views
Linear algebra question: does it have a solution?
Given $k\in\mathbb{N}$, $p$ a prime number, $s = (s_1, s_2,..., s_{2k+1})\in \mathbb{M}_{(2k+1)*1}(\mathbb{F}_p)$, the Hankel matrix generated by $s$ is denoted as $H$ where
$$
H = \begin{pmatrix}
s_1 ...
- 61
1
vote
1
answer
74
views
Asymptotic upper bound on nullity of biadjacency matrix of connected bipartite graph of bounded-degree
Let $G$ be a bipartite graph with parts $V$ and $W$ of sizes $m$ and $n$, respectively. The edge-set is $E \subseteq V \times W$. The adjacency matrix of $G$ takes the form
$$
A = \begin{pmatrix}
0 &...
- 271
0
votes
0
answers
25
views
Subcodes of Reed-Solomon codes
I would like to create a list of meaningful subcodes of Reed-Solomon codes. By "meaningful" I mean codes that have their own interest in some area of information theory.
For example, Tamo-...
- 1,128
0
votes
1
answer
33
views
Check if a code is cyclic and find its generator polynomial
Let $C$ be a code over $\mathbb{Z}_7$ with the generator matrix
$ G = \begin{bmatrix}
1 & 3 & 4 & 0 & 0 & 0 \newline
1 & 4 & 0 & 4 & 0 & 0 \newline
0 & 1 &...
- 27
2
votes
0
answers
89
views
Does a code being perfect have a specific effect on its automorphism group?
I know that the Perfect Binary Golay Code is very exceptional as it is the only perfect binary code that is not one of a few infinite families (Trivial, Simple Repitition, Hamming). The automorphism ...
- 121
0
votes
1
answer
27
views
Let $ C $ be a linear code of length $ n $, dimension $ k $, and $ e $ the maximum number of errors that the code $ C $ can correct.
Let $ C $ be a linear code of length $ n $, dimension $ k $, and $ e $ the maximum number of errors that the code $ C $ can correct. Then $ 2^{n-k} \geq 1 + \binom{n}{1} + \ldots + \binom{n}{e} $.
...
user1316790
1
vote
0
answers
39
views
Multiplication of matrix by submatrices
I have a $J \times J$ matrix $C$ that is upper triangular. Also, $C'C$ is positive definite. I also have a matrix $A$ formed by submatrices of size $J \times K$ as follows $A = \begin{bmatrix} A_1 \\ ...
- 11
0
votes
1
answer
34
views
$[n,k,3]$ linear code exists iff Hamming bound holds
Show that: $[n,k,3]$ linear code exists iff the Hamming bound holds, i.e.
$$ q^k\leqslant \frac{q^n}{1+n(q-1)}$$
I have no idea how to show this, does the construction of such code have anything to do ...
- 357
1
vote
1
answer
28
views
Confusion regarding standard generator matrix
I think I have a misconception regarding standard generator matrices. Let $G$ be a generator matrix for a code. Then by performing row operations we can put it in reduced row-echelon form. These ...
- 2,067