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,779
questions
2
votes
0
answers
19
views
The action of the error subgroups $S$ and $S'$ on the encoded space
From https://arxiv.org/pdf/quant-ph/9608006.pdf
$E$ is the group of possible errors in $n$ qubits
$S'$ is a subgroup of $E$ consisting of undetectable errors. These are errors $e$, in which ...
- 251
0
votes
0
answers
16
views
How to represent elements from $\bar{E}=E/Z(E)$ in the form $(a|b)$
From https://arxiv.org/abs/quant-ph/9608006
Background
The group $E$ of tensor products $\pm w_{1} \otimes \dots \otimes w_{n}$ and $\pm i w_{1} \otimes \dots \otimes w_{n}$, where each $w_{j}$ is one ...
- 251
1
vote
0
answers
24
views
When BCH and Reed-Solomon have the same number of parity bits (not symbols!), do they have the same burst error correction capability?
In Reed-Solomon codes, the symbols of a code word contains multiple bits. Since the error correction and detection happens at the symbol level, it doesn't matter how many errors there are within the ...
- 111
1
vote
2
answers
35
views
Is the method to prove that a code [n,k,d] punctured at $i$th index gives [n-1, k_i,d_i] code where $k_i\geq k-1$ is correct?
I am self teaching my self error correcting codes from the book Introduction to coding theory by Ron Roth. There is a question that says that suppose a code is given as $[n,k,d]$ where n is the code ...
- 23
0
votes
1
answer
21
views
In a generator matrix of a linear block code ,how does increasing linear vectors in a field $F^k$ has $q^k-q^i$ choices?
I am trying to study error control and coding theory by myself. There is an unsolved question which says that the total number of distinct generator matrices of a linear [n,k,d] code over $F=GF(q)$ is ...
- 571
0
votes
1
answer
92
views
How do we know that the quotient group $\bar{E} = E/Z(E)$ is an elementary abelian group
My question is:
How do we know that the quotient group $\bar{E}=E/Z(E)$ is an elementary abelian group?
Please find below some background information on the different relevant groups involved from ...
- 251
1
vote
1
answer
28
views
Does the method for finding dual codes change from binary codes to codes over GF(q)?
I understand that for a binary linear code $C$ (n,k) code, with generator matrix $G$ ($n \times k$ matrix), two ways of finding the dual code $C^{\perp}$ (n,n-k) code are:
Put $G$ into standard form $...
- 251
0
votes
0
answers
33
views
E.M. Gabidulin's "Theory of codes with maximum rank distance" article in English
I am trying to find a legible digital copy in English of the following paper:
E. M. Gabidulin. $\textbf{Theory of codes with maximum rank distance}$. Problemy Peredachi Informatsii, 21(1):3–16, 1985.
...
- 619
1
vote
1
answer
55
views
Finding automorphisms of a vector space using GAP
Goal:
Given a $K$-dimensional vector space $V \subseteq \mathbb{F}_2^N$ firstly find the group $A$ of all automorphisms $\alpha_i: V\to V $ and secondly find the subgroup $\widetilde{A} \subseteq A$ ...
1
vote
1
answer
41
views
Can minimum Hamming distance of a linear code over a finite field be found via minimum Hamming weight?
For a linear non-binary code over a finite field, what are the ways of finding the minimum Hamming Distance. I can use the SAGEmath minimum_distance() command, but I'd like to be able to do it without ...
- 251
0
votes
0
answers
31
views
Shamir Secret Sharing
Can anyone please explain to me why we have such equations below in part b) and c)? They are the solutions to the questions, but I can't really understand why and how to get that. Many thanks.
==== ...
- 11
0
votes
0
answers
65
views
self-orthogonal binary codes
From Robert Griess's article "Elementary abelian p-subgroups of algebraic groups":
(2.7) Definition. Let char$(\mathbb{K})\neq 2$ and let $V$ be an $m$-dimensional vector space with ...
- 1,443
1
vote
1
answer
40
views
Given one has a cyclic code, how would you deduplicate the other orientations of the codeword in a systematic way?
I've been recently working with Reed-Solomon codes and wanted to make use of their cyclic properties to uniquely identify something regardless of where the reading of the code started symbol-wise. Is ...
- 13
0
votes
0
answers
35
views
Hamming Bound-like upper bounds on q-element codes when the minimum distance is even
If there exists a q-tuple code (n, K, d) where $d = 2l$ is even, prove that
$q^n\ge K(q-1)\sum_{i=0}^{l-1}\binom{n}{i}(q-1)^i$
My thought was to take into account the number of vectors with distance $...
- 1
0
votes
1
answer
34
views
Detecting Erroneous Corrections
A block code $C$, with minimum distance $d$ can be used to:
Detect $d - 1$ errors
Correct $\lfloor\frac{d - 1}{2}\rfloor$ errors
However, the above usually assumes that the number of errors that are ...
- 1
0
votes
0
answers
35
views
Finding another encoder for a given code
I am a newcomer in Coding Theory and I am trying to solve the following question:
\begin{equation*}
\text{Let}\ \mathscr{C} \subset \mathbb{F}_3^4 \text{ be a code}, \text{with racio } 2/4, \text{and ...
- 125
2
votes
0
answers
44
views
how to find p-th primitive root of unity in GF(2^m)
The definition of quadratic residue codes involves finding a primitive p-th root of unity in some finite extension field of $GF(2)$. 2 is a quadratic residue of prime $p$.
By brute force search I ...
- 958
0
votes
1
answer
39
views
The direct sum of irreducible cyclic codes is still a cyclic code
Let $q$ be a prime power and $\gcd(n,q) = 1$. Let $h_1(x), h_2(x) \in \mathbb F_q [x]$, $\gcd(h_1(x), h_2(x)) = 1$, and $h_1(x) \cdot h_2(x) | x^n - 1$. Denote by $C, C_1, C_2$ the $q$-ary cyclic ...
- 13
0
votes
0
answers
24
views
If there is a binary vector space S , which is contained in it's dual S⊥ , does this mean that every element of S must be self-orthogonal?
If there is a binary vector space $\bar{S}$, which is contained in it's dual $\bar{S}^{\perp}$, does this mean that every element of $S$ must be self-orthogonal?
Let me explain the specific case (...
- 251
1
vote
2
answers
151
views
Prove that if binary words $x$ and $y$ have even weight, then so does $x+y$.
I am stuck on an exercise from "A Book of Abstract Algebra" by Charles C. Pinter, and there are technically three parts to the question:
Given that the weight of a binary word $x$ is the ...
- 63
1
vote
0
answers
56
views
Exact algorithms (e.g. in coding theory, cryptography) using the field of rational numbers
I noticed that most algorithms in coding theory or cryptography are based on the integers and some arithmetic results (e.g. RSA) or on the finite fields (e.g. Elliptic curve cryptography or BCH codes)....
- 441
3
votes
0
answers
117
views
A generalization of the edge isoperimetry problem for the hypercube
For any $n$, and any $1 \leq k \leq 2^n$, and any $1 \leq q \leq n-1$, we want $k$ binary vectors of length $n$, organized in a matrix $M$ with $k$ rows and $n$ columns, that will minimize $p(M,q)$ ...
0
votes
0
answers
30
views
Minimum hamming distance of concatenated codewords
So here is the question and I am trying to find a proof for the minimum hamming distance d3:
Let $C_1$ be a $(n_1, M, d_1)$ q-ary code and $C_2$ a $(n_2, M, d_2)$ q-ary code.
Assume that we have named ...
- 105
0
votes
1
answer
65
views
How would having a codeword withweight two affect the coset priority here? [closed]
I am trying to understand syndrome decoding. My understanding so far is that we calculate syndrome vector based on what we assume would be the error and that the coset leader vector chosen is to be ...
- 3
0
votes
0
answers
36
views
Reed-solomon coding: question on proof of minimum distance
In the "coefficient view" of Reed-Solomon encoding, the message is interpreted to be coefficients of a polynomial m(x). The code word is $c(x) = m(x)*g(x)$ where $g(x)$ is a generator ...
- 151
13
votes
1
answer
259
views
How much data can I store on used punch cards?
I have inherited a bunch of used punch cards filled with random data, which I plan to reuse to store my own data. The question is: how efficiently can I store my data?
Assume each punch card has some ...
- 16k
1
vote
1
answer
45
views
Proof of the Plotkin Bound "The Theory of Error Correcting Codes" MacWilliams/Sloane
This question pertains to the proof of Theorem 1 (The Plotkin Bound) in "The Theory of Error-Correcting Codes" by MacWilliams and Sloane.
The theorem states: For any $(n,M,d)$ code $C$, for ...
- 251
3
votes
1
answer
109
views
Decimation of Maximal-length sequence
Consider a Maximal-length sequence (hereby M-sequence) $S$ of minimal period $2^n-1$, as produced by an LFSR with a binary primitive polynomial. Note $s_0,s_1,\ldots$ the bits of $S$.
For some integer ...
- 1,646
1
vote
0
answers
37
views
Generating Sequences with Monotonically Increasing Entropy
Context:
Consider an ensemble $X = (x; A; P)$. Let's examine $X^N$, which represents the set of all possible strings of length $N $produced by $X$. The objective is to systematically derive sequences ...
- 111
0
votes
0
answers
61
views
Convolutional codes: free distance (Part 3)
This is a follow-up question of convolutional codes: free distance and
Convolutional codes: free distance (Part II), and is to confirm the following conjecture:
A convolutional code with "direct ...
- 3,055
0
votes
0
answers
60
views
Convolutional codes: free distance (Part 2)
This is a follow-up question of convolutional codes: free distance, and is meant to confirm a counter-example to it:
Specifically, if we terminate a convolutional code in some non-zero state, then the ...
- 3,055
1
vote
0
answers
30
views
Effect on the minimum distance of a code if we remove some rows/ column in its matrices
Suppose you are given a linear code with generator matrix $G$ and parity check
matrix $H$. The following is a list of ways you might modify your code. For
each, determine the possible effect on the ...
- 11
0
votes
3
answers
203
views
convolutional codes: free distance
It's commonly stated in the literature that the free distance of a convolutional code is the minimum Hamming distance between the all-zero path and any other (non-all-zero) path in the trellis ...
- 3,055
2
votes
1
answer
53
views
Partition of $0,1$ sequences with even $1$'s into groups s.t. elements in each group differ from a sequence by one entry
Consider $S$, the set of all $0,1$-sequences of length $n=2^k$ and there is an even number of $1$'s in the sequence. Clearly, $|S|=2^{n-1}$. Is it always possible to find $2^{n-1-k}$ representatives, ...
- 659
2
votes
1
answer
38
views
Equivalence of two constructions for $RM(r, m)$
I am currently studying about binary Reed-Muller codes, where we have first defined by the usual Boolean function definition:
Def The binary Reed-Muller code $RM(r, m)$ of order $r$ and length $2^m$ ...
- 1,106
1
vote
1
answer
42
views
How to find the zeroes of a BCH code and how do they define the dimensions of a parity check matrix?
I'm looking through the lecture notes by Alexandar Barg ENEE626:Error-Correcting Codes Lecture 13.
We are given an example which says:
"Consider the Hamming Code $H_{4}[15,11,3]$.
Let $\alpha$ be ...
- 251
1
vote
1
answer
64
views
How do we find the conjugates of a field element over $GF[2^{4}]$? And why can we take the LCM of just odd-indexed min.polynomials for g(x)?
I am following an example given by Writi M on a youtube video "an example of construction of BCH codes and encoding using BCH codes"
The example asks us to construct a BCH code that can ...
- 251
2
votes
0
answers
34
views
Can we generalize the idea of spatially coupled gaussian matrices to rotationally invariant matrices?
Setup: An $(\omega,\Lambda)$ base matrix $W\in\mathbb{R}^{R\times C}$ is described by the coupling width $\omega\geq1$ and the coupling length $\Lambda\geq2\omega-1$. The matrix has $R=\Lambda+\omega-...
- 730
1
vote
0
answers
16
views
How to find lattice vector with minimal projection along given vector?
Suppose I have a Construction A lattice $$\mathcal{L} = \left\{\left[G |2\mathbb{I}_n\right]z\ :\ z\in\mathbb{Z}^{n+k} \right\}$$ where $G$ is a $n\times k$ matrix generating a binary linear code and $...
- 51
0
votes
0
answers
27
views
Minimum mean length of code words
I need help with this task, so if anyone is willing to help me, I would be grateful.
The task is:
Given a discrete information source that generates symbols from the set ...
- 457
0
votes
2
answers
39
views
$Gx$ is distributed uniformly in the set $\Bbb Z_2 ^n$.
I read the probabilistic proof of the Gilbert Varshamov bound in Coding Theory, and I came across the following argument, which I would like to discuss:
Suppose that $G$ is a random matrix in $M_
{n×k}...
- 2,734
0
votes
1
answer
150
views
Minimum weight and minimum distance of a linear code
I got stuck at understanding the solution of an exercise from my coding theory course;
Question
Show that the minimum weight of a linear code C is equal to the minimum distance of C.
Solution
Let w be ...
- 576
4
votes
0
answers
83
views
How to find a sparse lattice basis?
I am working with lattice codes (see here, or here) and facing the following problem: I have a set of $k$ vectors $\left\{v_1,\ldots,v_k\right\}$ which I know generate an $n$-dimensional, full-rank ...
- 51
0
votes
0
answers
29
views
Compute parity matrix in $GF(3)$
I want to compute the control matrix/parity matrix $H$, when given a generating matrix $G$ for a linear code in $GF(3)$:
G = \begin{bmatrix}
2 & 1 & 1 & 1 & 0 & 0 \\
1 & 2 &...
- 109
3
votes
1
answer
56
views
Are Huffman code lengths monotonic with respect to probability?
Suppose you have an alphabet of $k$ symbols and a probability distribution $P = p_1, p_2, \ldots, p_k$ over them. Furthermore, assume that $p_i > 0$ for all $i$.
Let $minhuff_i(P)$ be the length of ...
- 271
0
votes
0
answers
107
views
Find the generator matrix (block code) given the codewords
So I was given the following (6,3) block code with some unknown values marked with x:
format: index,(msg) -> (code word)
1 (0 0 0) -> (0 0 0 0 0 0)
2 (1 0 0) -> (0 1 1 1 0 0)
3 (0 1 0) ...
2
votes
1
answer
102
views
Alternative expressions for Krawtchouk (Kravchuk) polynomials
For fixed non-negative integers $n$ and $q \geq 2$, the $k$-th Krawtchouk (Kravchuk) polynomial is defined as
$$K_k = \sum_{j=0}^k (-1)^j (q-1)^{k-j} \binom{X}{j} \binom{n-X}{k-j} \in \mathbb{Q}[X]$$
...
- 21.9k
0
votes
1
answer
52
views
How to determine the optimal shifting direction when decoding non-systematic cyclic code
Please excuse me for any wrong use of terminology as I'm studying Coding Theory at a non-English university.
As I have learned at my university, for non-systematic cyclic code, to find the original ...
- 13
1
vote
1
answer
245
views
Determine the number of binary codes with parameters $(n, 2, n) $ for $n ≥ 2$
Number of binary codes with parameters $(n, 2, n)$ for $n ≥ 2$ !?
I did the problem with my knowledge, I don't know whether it is True or false
For $n\geq 2$
$\{00000(n terms),11111(n terms)\}$ is ...
- 11
0
votes
0
answers
39
views
Control matrix for a code
I got stuck in the following problem.
We recursively define the matrices for all $i\in \mathbb N$
$G_1 :=\begin{bmatrix}
1 &1\\
0&1
\end{bmatrix}$
and $$G_{i+1} :=\begin{bmatrix}
G_i &G_i \...
