# 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
Filter by
Sorted by
Tagged with
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 ...
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 ...
1 vote
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 ...
1 vote
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 ...
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 ...
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 ...
1 vote
28 views

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 ...
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 ...
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 ...
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 ...
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 (...
1 vote
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 ...
1 vote
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)....
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)$ ...
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 ...
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 ...
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 ...
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 ...
1 vote
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 ...
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 vote
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
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, ...
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 vote
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 ...
1 vote
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 ...
34 views