All Questions
Tagged with coding-theory linear-algebra
268 questions
-1
votes
0
answers
11
views
Fast Hadamard Transform in Reed Muller Code
The post-quantum cryptograhy HQC using the Reed-Muller code as internal code.
The using the fast Hadamard transform to decode the Reed-Muller code. I cannot find the book or document where describe ...
- 173
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
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
2
votes
1
answer
131
views
Column Rank and Column Orthogonality for Space-Time Block Codes with $ \pm 1$ Entries?
I am a network engineer who does not have mathematical rigor and is currently working with matrices that have entries $\pm 1$ for space-time block code applications. I would like to understand certain ...
2
votes
2
answers
116
views
Minimum distance of the dual code in terms of the code
Let $C \subset \mathbb{F}_q^n$ be an $[n,k,d]_q$-code.
Is it possible to describe the minimum distance $d(C^\perp)$ of $C^\perp$ in terms of $d(C)$ or do we have a bound for it?
My question comes from ...
- 125
3
votes
2
answers
103
views
How to prove the dual of the tensor product code $(C_1\otimes C_2)^\perp = C_1^\perp\otimes \mathbb{F}_2^n +\mathbb{F}_2^n\otimes C_2^\perp$
Given $n\in\mathbb{Z}_+$ and subspaces (are also called codes) $C_1,C_2\subseteq \{0,1\}^n$. All calculations are on $\mathbb{F}_2$. The dual of $C_1$ is $C_1^\perp=\{x\in\mathbb{F}_2^n: \forall y\in ...
- 1,099
5
votes
2
answers
95
views
Equivalent codes (semilinear isometries)
When considering equivalent error correcting codes, we are interested in codes that have the same Hamming metricial properties although they may appear superficially different. For the sake of ...
- 157
2
votes
0
answers
66
views
Non-systematic parity check matrix syndrome calculation problem
I have a problem with calculating the 2t m-bit syndrome from the non-systematic parity-check matrix for the BCH code or general cyclic code.
I know the 2t syndrome ...
- 21
1
vote
2
answers
67
views
How to construct the generator matrix of a Hamming code, given the parity check matrix
If we are given a Hamming code $H^{5}_{4}$ with parity check matrix $$H = \begin{bmatrix}
0 & 1 & w & w & 1 \\
1 & w & w & 1 & 0
\end{bmatrix}.$$
This is a linear code ...
- 353
1
vote
1
answer
56
views
For two linear codes $C$ and $D$, why is $D^\perp \subset C$ equivalent to $H_C\times H_D^T=0$?
I have been reading this paper about Quantum QC-LDPC codes which are a subset of CSS codes, and it says that "For the linear codes $C$ and $D$, it is said that $C$ and $D$ satisfy the twisted ...
- 13
2
votes
1
answer
80
views
Find complement of the union of two row spaces
Given two $\mathbb{F}_2^{N\times N}$ matrices with rank $N - 1$, I want to find the complement of the union of the two row spaces.
Example:
Let
$$A = \left [ \begin{matrix}
1 & 0 & 0 & ...
- 21
0
votes
1
answer
78
views
Hamming Code $H_3$ : Generator Matrix & Polynomial\ldots doesn't generate the same code. Why?
The generator matrix of the $H_3$ Hamming code is given by
$$
\mathcal{G} =
\begin{pmatrix}
1 & 0 & 0 & 0 & 1 & 1 & 0\\
0 & 1 & 0 & 0 & 1 & 0 & ...
- 13
0
votes
0
answers
69
views
How Hamming Distance changes with added vector
Suppose we have $k$ vectors, $v_1, \dots, v_k$, where $v_i = (v_{i,1}, \dots, v_{i,n})$, all of the same length $n$ over a finite field $\mathbb{F}_p$. We can construct a matrix $V$:
\begin{equation}
...
- 477
0
votes
1
answer
106
views
Formulas for the Hamming weight of $x+y$
Let $x,y\in \mathbb{F}_q^n$, $\mathrm{wt}(x):=|\mathrm{supp}(x)|$ be the Hamming weight.
Case I: When $q=2$, it is easy to prove
$$ \mathrm{wt}(x+y)=\mathrm{wt}(x)+\mathrm{wt}(y)-2\left\langle x,y\...
- 1,298
1
vote
0
answers
35
views
How to find the generator matrix for the quotient group $C/C^{⟂}$ using a list of coset representatives of $C^{⟂}$ in $C$?
$C$ is the $[6,5,2]$ classical binary code.
I am trying to find the generator matrix for the quotient group $C/C^{⟂}$ from the list of coset representatives of $C^{⟂}$ in $C$.
My question refers to ...
- 353