All Questions
Tagged with finite-fields coding-theory
32 questions
14
votes
3
answers
1k
views
A question on representation of graphs
Take a complete graph $K_n$. You want to assign a vectors from $\Bbb F_2^d$ to every edge such that sum of vectors in every simple cycle does not sum to $0$ vector. The question is what is minimum $d$ ...
- 13.9k
7
votes
2
answers
440
views
How to count the number of tensors over a finite field of tensor rank $r$?
For simplicity, work over $\mathbb F_2$ and only consider order-$3$ equilateral tensors. For $r\in\mathbb Z_{>0}$, how many tensors $\mathfrak{T}\in\mathsf{Ten}_{n}^{\otimes 3}(\mathbb F_2)$ are ...
- 161
7
votes
2
answers
609
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$ ...
- 632
6
votes
3
answers
437
views
On the rank of a matrix $S$ with coefficients in $\mathbb F_{2^m}$
Let $\mathbb F$ be a finite field with characteristic 2 and let $S \in M(2k, 2k, \mathbb F)$ be the matrix defined as follows
$$ S=\left[\begin{array}{ccccccc}
0 & \...
- 307
6
votes
1
answer
378
views
Enumeration of field generators of a finite field over $\mathbb{F}_{q}$, which are $m^{th}$ powers in the same field
Consider the finite field extension $\mathbb{F}_{{q}^{d}}$ over $\mathbb{F}_{q}$, where $q=p^a$ for some prime $p$. We assume $d\geq 2$. Let,
$$ S=\{ \alpha \in \mathbb{F}_{q^d}\hspace{0.1 cm} | \...
- 428
6
votes
1
answer
443
views
Finite field analogue of Chebotaryov theorem on roots of unity?
Chebotarev's theorem on roots of unity says that all the minors of a prime-length DFT matrix over the complex numbers are nonzero. I was wondering if there was an analogue for finite fields.
More ...
- 115
6
votes
0
answers
173
views
When are Hamming codes cyclic?
I've asked this question on math.stackexchange before, but it has not been solved.
The following statement appears to be true:
The $q$-ary Hamming code of codimension $r$ over $\mathbb{F}_q$ is ...
- 253
5
votes
1
answer
473
views
Special polynomials over finite fields
My field of research is coding theory and I am working on cyclic codes. During my research, I tackled an algebraic problem. After some simple definitions, I asked my question. I will appreciate any ...
- 632
4
votes
0
answers
108
views
Differential duality: Triangular codes vs. VT codes / Single-substitution vs. Single-deletion
Here is the introduction to my problem:
Codes correcting single-deletion. Let $q$ and $n$ be non-negative integers, and let $\mathbf{x}= \left ( x_{1}, x_{2}, \ldots, x_{n} \right )\in\mathbb{Z}_{q}^{...
- 41
3
votes
1
answer
291
views
What do we know about the $\mathbb{F}_{q^2}$-curve $X^{q-1} + Y^{q-1} + Z^{q-1}$?
People have thoroughly studied the Hermitian $\mathbb{F}_{q^2}$-curve $H: X^{q+1} + Y^{q+1} + Z^{q+1} = 0$. What do we know about the similar $\mathbb{F}_{q^2}$-curve $C: X^{q-1} + Y^{q-1} + Z^{q-1} = ...
- 1,833
3
votes
3
answers
611
views
On MDS code property
Is there a code that is Maximum Distance Separable and not isomorphic to Reed Solomon Codes? When is a MDS code isomorphic to Reed Solomon Code?
Is there an easy test? If so, could someone provide ...
- 13.9k
3
votes
1
answer
232
views
Computing the decimation ratio between two m-sequences
Let's suppose I have an LFSR that generates an m-sequence $y_1[k]$ --- in other words, the LFSR has $N$ bits and $y_1[k]$ has period $m=2^N - 1$.
Now suppose I know someone has decimated this and ...
- 663
3
votes
2
answers
256
views
Picking codewords that are close
I posted this question in https://math.stackexchange.com/questions/1142698/picking-codewords-that-are-close a week back.
Let $[n,k,d]$ be a linear code over $\Bbb F_q$ with minimum distance $d$ and ...
- 13.9k
3
votes
0
answers
130
views
Cyclic codes: sparse codewords not orthogonal to the all-ones vector
Is it true that for any sufficiently large prime $p$, there exists a prime $q\ne p$ and a cyclic code of length $p$ over $\mathbb{F}_q$ that contains a codeword of Hamming weight at most ord$_p(q)$ ...
- 93
3
votes
1
answer
241
views
Binary subspace membership testing with signed vectors
Say we are working in $\mathbb{F}^{2n}_2$ where vectors can be written as pairs $(a,b)$ with $a,b \in \mathbb{F}^{n}_2$. Given a list of basis vectors for an $n-1$ dimensional subspace $S \subset \...
- 31
3
votes
0
answers
230
views
On weight enumerators of codes
Are there $[n,k]_q$ constant rate $\frac kn$ and constant alphabet linear code families with automorphism group of size $\Omega((n-n^\beta)!)$ that have minimum distance $d=O(n^\alpha)$ and number of ...
- 13.9k
2
votes
2
answers
273
views
Need help with paper written in Russian... Yorgov's paper on self-dual codes with automorphisms of odd order
I came across this paper by V.I.Yorgov named "Binary self-dual codes with automorphisms of odd order". (Actually I was first reading another paper by Borello that cited this paper. It later become ...
- 165
2
votes
1
answer
217
views
Low-Hamming weight vectors in low-dimensional subspaces of $\mathbb{F}_p^n$
What is the maximum number vectors of Hamming weight at most $w$ in a $d$-dimensional subspace of $\mathbb{F}_p^n$, where $w,d,p$ are constant and $p$ is odd. (The Hamming weight is the number of ...
- 93
2
votes
1
answer
612
views
Inner product over finite field
sorry for informals but is my first post.
In Coding theory (exactly in Coding theory a first course - San ling and Chaoping) found this definition:
$\langle , \rangle :\mathbb{F}_q^n\times\mathbb{F}_q^...
2
votes
0
answers
277
views
Counting special metrics on finite fields
Define a Galois coding norm of degree n as a map $|\space| : \Bbb F_{2^n}\rightarrow {\Bbb Z}$ with the following properties :
(I) $(\Bbb F_{2^n},|\space|)$ is a self-orthogonal code ; i.e. $(x,y)\...
- 173
2
votes
0
answers
112
views
The significance of the Parvaresh-Vardy curve
Even though this seems like a computer science question, it is purely mathematical and concerns polynomials and curves over finite fields.
Consider the Parvaresh-Vardy list decoder.
As I understand ...
- 949
1
vote
2
answers
290
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 ...
- 24.9k
1
vote
1
answer
139
views
A polynomial recovery problem
Suppose we know $deg(m(x))=n-1=deg(f_1(x))=deg(f_2(x))$.
Suppose we know $C_1(x),C_2(x)$ where $deg(C_i)=n$.
Then given $n$ values of $$C_1(x)(x+1)m(x) +C_1(x)(x+2)f_1(x)\in\Bbb F_q[x]$$ and $n$ ...
user94040
1
vote
1
answer
391
views
System of equations - Proof that a solution exists
Let $ a = (a_1,a_2, \ldots,a_{10})\in \{ 0,1\}^{10}$ be a binary vector of length $10$.
Question: Without using a computer-aided method, how to prove that there exists binary vectors $x_{i,j} \in \{ ...
user83947
1
vote
1
answer
115
views
An Extension of an $\operatorname{MDS}$ Code over $\operatorname{GF}(2^q)$
Let $q$ be a power of $2$.
Assume that elements of the finite field $\operatorname{GF}(q)$ are denoted by $\beta_i$
for $0\leq i \leq q-1$. We divide elements of $\operatorname{GF}(q)$ in two parts ...
- 313
1
vote
1
answer
239
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 ...
- 24.9k
1
vote
0
answers
81
views
On sparse $0/1$ linear equations solvable with compressed sensing
If you have a system of $m$ linearly independent equations in $n$ variables with domain $0/1$ and we know there is at least one solution with at most $d$ variables to be $1$ then if $m$ at least a ...
- 1,826
1
vote
0
answers
174
views
Null Space of Parity Check Matrix
We know that if $\alpha$ be s a primitive element of $F_q$ where $q$ is a prime power then the null space of the following matrix generates a cyclic code of designed distance $\mu$[1].
$$
G_{\alpha}^{...
- 313
1
vote
0
answers
207
views
Polynomial existence over finite field
Denote $\mathcal{F_n}$ as collection of multiaffine polynomials $f\in\Bbb F_2[x_1,\dots,x_n]$.
Denote total degree of $f\in\mathcal{F_n}$ as $deg(f)$ (note $deg(f)\leq n$).
Denote $e_i=(0,\dots,0,\...
- 13.9k
1
vote
0
answers
228
views
How can I decode efficiently a triple-error-correcting binary BCH code?
In a given $\mathrm{BCH}(N,K)$, $T=3$ code over $\mathrm{GF}(2^m)$, there are ways to find the error locations in a given $N$-bit codeword directly from the syndromes without going through the normal ...
- 87
0
votes
1
answer
146
views
Does the Plotkin bound mean that one can not achieve the Singleton bound asymptotically?
I am a little confused with the relationship between various bounds for error correcting codes.
Does the Plotkin bound mean that one can not achieve the Singleton bound asymptotically? That is, is ...
- 11
0
votes
0
answers
102
views
Is there an inner product on $\mathbb{F}_p\left[S_n\right]$ for which $\langle x, x \rangle \ne 0$ for all $x$?
Let $\mathbb{F}_p\left[S_n\right]$ be the group algebra of the symmetric group $S_n$ over the finite field $\mathbb{F}_p$.
One can define an "inner product" in the usual way:
$$\langle x,y \...
- 571