Skip to main content

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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
9 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$. Below is a screenshot of ...
am567's user avatar
  • 339
0 votes
2 answers
30 views

How to study the cross-correlation distribution of the set of sequences consisting of both $m$-sequences and quadratic sequences?

Let $f(m):\mathbb{Z}^+ \rightarrow \mathbb{Z}^{+}_{even}$ is a function from the set of positive integer to the set positive even integer. Then by the $[f(m)-1]$-BCH code I mean the BCH code with ...
Dark Forest's user avatar
2 votes
2 answers
131 views

Can somebody prove my finding which I am proposing here as a conjecture regarding the binary BCH code?

I am a PhD student and I work in the area of applied mathematics. I am studying the different kind of uniform column weight binary matrices with prescribed inner products between its columns. I am ...
Dark Forest's user avatar
1 vote
0 answers
22 views

Varshamov bound is stronger than Gilbert bound

In the class of Error-correcting Code, the professor showed us $2$ results: 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_{...
Zoudelong's user avatar
  • 369
2 votes
1 answer
38 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 ...
am567's user avatar
  • 339
0 votes
0 answers
17 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$ ...
Laura's user avatar
  • 161
4 votes
1 answer
76 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 ...
Dark Forest's user avatar
1 vote
1 answer
62 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$...
Reed Trende's user avatar
0 votes
1 answer
67 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+...
user159729's user avatar
6 votes
2 answers
287 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 ...
Youzhe Heng's user avatar
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 &...
Pranay's user avatar
  • 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-...
Reyx_0's user avatar
  • 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 &...
Kris's user avatar
  • 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 ...
nph's user avatar
  • 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} $. ...
user avatar
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 \\ ...
LauraH's user avatar
  • 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 ...
Zoudelong's user avatar
  • 369
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 ...
kubo's user avatar
  • 2,067
0 votes
0 answers
29 views

How to find "extra" mutual information

Codewords $00$ and $11$ are sent with equal probability through a BSC with error probability p. Compute the mutual information between the codeword sent and the first digit received as output. I have ...
S. Chitratta's user avatar
1 vote
1 answer
41 views

Symmetric difference of Shannon's entropy satisfies triangle inequality

For random variables $X$ and $Y$, we define: $$\delta(X,Y) = H(X|Y) + H(Y|X)$$ Show that $\delta(X,Y)$ satisfies the triangle inequality. My attempt: I tried to write $H(X|Y) = H(X,Y) - H(Y)$, then I ...
vegetandy's user avatar
  • 305
0 votes
1 answer
96 views

showing that $x^4+x^3+2$ is primitive over $\Bbb F_3$

I want to show that $x^4+x^3+2$ is primitive over $\mathbb{F}_3$. By definition, this means that $x^4+x^3+2$ is monic and has a root $\alpha$ that generates the multiplicative group of $\mathbb{F}_{3^...
doctor's user avatar
  • 419
1 vote
1 answer
49 views

How to solve, or quantify solutions of, polynomial equations in $\mathbb{F}_2[x,y]/\langle x^\mu - 1, y^\nu - 1\rangle$? [closed]

Suppose I was given an equation in $\mathbb{F}_2[x,y]$ under the identification $x^\mu = 1$ and $y^\nu = 1$ for some integers $\mu,\nu$, with some unknowns $c[x,y]$ and $d[x,y]$. For example: \begin{...
JoJo P's user avatar
  • 133
0 votes
1 answer
39 views

Does Entropy really change depending on the encoding? [closed]

So I'm self studying information theory, and I have a few doubts on entropy and encoding as a whole. I'm trying to compress a simple 16bit signed int sequence of values the best I can. I learned about ...
2 False's user avatar
  • 65
0 votes
1 answer
29 views

Lengths of binary Huffman codes for uniform distribution

A binary Huffman code for a pmf $(p_1,\dots,p_m)$ is constructed by starting with all $p_i$ as leaves and iteratively constructing a tree by merging the two nodes of lowest probability. Edges are then ...
hegash's user avatar
  • 197
1 vote
0 answers
29 views

Why does Elias's product code have vanishing error rate?

I am studying information theory and I just encountered a code constructed by Elias in 1954. I am struglling to understand why this code gives vanishing error rate, as is shown also in this lecture ...
ksks's user avatar
  • 11
0 votes
0 answers
48 views

Factorization and order of elements in splitting field

Example 4.4. Let $p=2$, $n=4$. Consider the polynomial $f=x^{2^{4}}-x=x^{16}-x$. Then $\text{GF}(16)$ is the splitting field of $f$ over $\text{GF}(2)$. The irreducible factors of $f$ over $\text{GF}(...
Paul Varghese's user avatar
0 votes
0 answers
16 views

Deduce $\begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ \end{bmatrix}$ or the simple parity-check matrix just from the final matrix-vector product equations

A linear combination like $A_{1}+ A_{2}$ serves as a backup of $A_{1}$ when $A_{2}$ is known, and serves as a backup of $A_{2}$ when $A_{1}$ is known. As a result of linearity, any two out of $A_{1}x$,...
triple_tactic's user avatar
2 votes
3 answers
83 views

Shannon source coding theorem and differential entropy

Loosely speaking, Shannon's source encoding theorem says that there is an encoder with rate at least $H(x)$ such that $n$ repetitions of the source can be mapped to at least $nH(x)$ bits, such that ...
nervxxx's user avatar
  • 281
3 votes
0 answers
85 views

Generalized Hamming weights for binary BCH codes

Given a linear binary code $C$, the $r$-th generalized Hamming weight $d_{r}(C)$ is the minimal support size of an $r$-dimensional subcode of $C$ (so $d_{1}(C)$ is simply the code's distance). For a ...
DanDan's user avatar
  • 339
1 vote
2 answers
46 views

Why does block coding via typical strings give messages longer than $nH(p)$?

This semester, I am taking a course on quantum information and quantum computing. Since I am rather new to information theory I have a problem with understanding a paragraph in my lecture notes. The ...
luki luk's user avatar
  • 189
0 votes
1 answer
37 views

Codes with low error-control rate

Suppose that $C \subset \mathbb{F}_2^n$ is a code, and let $d = d(C) = \min\{d(x,y): x,y\in C\}$ the minimum distance of $C$, where $d(\cdot, \cdot)$ is the Hamming distance. We can define $r = \frac{...
blomp's user avatar
  • 591
0 votes
0 answers
15 views

Does the two dimension erasure code have a corresponding generation matrix?

Here is a example of X-code, which is a kind of vertical code.Each column represents a disk, each matrix represents a data block, and each pair of numbers represents which parity block this data block ...
ZhuJerry's user avatar
0 votes
0 answers
16 views

$A(n,d)$ ... set of all binary codes $C$ of length $n$ with $\delta(C)=d$ and $M(n,d)$ ... maximum cardinality of $|C|$ over all $C \in A(n,d)$

Let $A(n,d)$ denote the set of all binary codes $C$ of length $n$ with $\delta(C)=d$. Define $M(n,d)$ as the maximum cardinality of $|C|$ over all $C \in A(n,d)$. Prove the following: (a) $M(n,2d-1) \...
user avatar
1 vote
0 answers
37 views

Calculate the simplest dyadic rational in half-open interval

Given a half-open interval $[a, b)$ can one calculate, without brute force or looping of any kind, the simplest dyadic rational within said range? Context: I'm reading about arithmetic coding which ...
tsujp's user avatar
  • 111
0 votes
1 answer
41 views

Why is the information rate of an error-correcting code defined by $\frac{\log_q\left(|\mathcal{C}|\right)}{n}$?

Let $\mathcal{C}$ be an error-correcting code of length $n$ and $q$ the number of distinct symbols of the alphabet. We define the information rate of $\mathcal{C}$ by $$\frac{\log_q\left(|\mathcal{C}|\...
Cyclotomic Manolo's user avatar
0 votes
1 answer
45 views

Proof of identity on sum of powers of primitive root.

Let $q = p^e$ for some prime $p$. Consider the trace function $\mathrm{Tr}_{\mathbb{F}_q/\mathbb{F}_p}:\mathbb{F}_q\to \mathbb{F}_p$ defined by $\mathrm{Tr}_{\mathbb{F}_q/\mathbb{F}_p}(x) = \sum_{i=0}^...
PTrivedi's user avatar
  • 1,011
5 votes
2 answers
144 views

"Encode" all $n$-permutations with the fewest number of swaps

The goal is to find $m$ swaps $s_1, s_2, \dots, s_m$ such that any $n$-permutation can be encoded as a binary sequence of length $m$, $x_1, x_2, \dots, x_m$, where $x_i$ indicates whether to perform ...
Jemtaly's user avatar
  • 51
2 votes
1 answer
52 views

Inconsistency of capability of random coding in information theory and coding theory

In information theory, it is well known that the capacity of a channel can be achieved asymptotically using random coding method (Section 7 of Cover & Thomas' textbook). However, in coding theory, ...
Jiawei Wu's user avatar
2 votes
1 answer
56 views

Volume of Hamming ball w.r.t power-law distribution on hypercube

Let $n$ be a large positive integer and let $X$ be a random element of hypercube $\{0,1\}^n$ such that $\mathbb P(|X|= \ell) \propto (\ell + 1)^{-\beta}$ for all $\ell \in \{0,1,\ldots,n\}$. Here $\...
dohmatob's user avatar
  • 9,575
-1 votes
1 answer
52 views

Definition of smallest cyclic code in $\mathbb F_2$

I am confused about what the the following statement means: "Being $C$ the smallest cyclic code on $\mathbb F_2$ containing the word $w = 110110$". Maybe it's a stupid question, but does the ...
francesco's user avatar
1 vote
1 answer
66 views

A good decoder must be non-linear?

I read a problem from the book "Algebraic Codes for Data Transmission" by Richard E. Blahut: A linear decoder is a decoder for which the decoder estimates the error pattern from the syndrome ...
Harry556's user avatar
  • 368
1 vote
0 answers
25 views

Weight of the error vector and syndrome vector

In the class, I learned a relationship between the weight of the error vector and the weight of the syndrome vector. But I don't know how to verify this. Let $\mathbf{H} = (\mathbf{A} | \mathbf{I}_{(n−...
Harry556's user avatar
  • 368
5 votes
2 answers
113 views

"Manin's theorem" reference, coding theory

Question: In the book [1], a theorem called "Manin's Theorem" is stated on page 19 "There exists a continuous decreasing function $\alpha_q : [0,1] \rightarrow [0,1]$ such that $\...
Aidan W. Murphy's user avatar
0 votes
1 answer
54 views

Huffman Code with Weight

I am trying to construct a Huffman tree with the symbols $A, B, C, D, E$ with the weights $1, 1.5, 3.1, 3.7, 2.2$. Now from looking at Huffman coding I order the symbols based on the highest weight ...
zellez11's user avatar
  • 287
2 votes
1 answer
153 views

Random codes in coding theory [closed]

What do people mean when they say that they choose a code at random for a probabilistic proof in coding theory ? What is random in the code ? This is for example used in Shannon’s proof for capacity ...
yosh's user avatar
  • 73
1 vote
0 answers
28 views

Distance of 7-ary dual code [closed]

How would I go about proving the statement: if $D \subseteq \mathbb{F}_7^n$ is a self-dual code, then $2<d(D)<(n+3)/2$. Where $d(D)$ is the minimum distance of the code D. I'm not sure where to ...
alex's user avatar
  • 11
0 votes
0 answers
25 views

basic formula in Sum Product Algorithm(SPA) for decoding : $P(x_i=x | y_i)=[1+exp(-2yx/\sigma^2)]^{-1}$

I am studying SPA for LDPC decoding. This is one of the PDFs I am studying and my question is on page 12 of it. http://tuk88.free.fr/LDPC/ldpcchap.pdf In binary-input AWGN channel, $x_i=\pm 1$ when $...
ksj's user avatar
  • 1
0 votes
2 answers
130 views

Reed-Solomon Code RS16(17, 19) - Number of Correctable and Detectable Symbols

In Reed-Solomon coding with 16-bit symbols, for a configuration RS16(17, 19) where there are 17 data symbols, 2 parity symbols, and a total of 19 symbols, how many symbols are correctable and how many ...
cashew_nuts's user avatar
0 votes
0 answers
27 views

A binary narrow-sense primitive BCH code is always symmetric, but which book has proof of this statement?

I will begin with the definition of BCH code. Definition: A cyclic code of length $\tilde{n}$ over $\mathbb{F}_q$ is called a BCH code of designed distance $d$ if its generator polynomial $g(x)$ is ...
shashank ranjan's user avatar
1 vote
2 answers
82 views

Syndrome-decoding: Why do we correct the error locations, rather than interpolating with the non-error locations?

so for setup, let's say we have an $[n,k]$- Reed-Solomon-Code over $\mathbb{F}_q$ for some prime power $q = p^m$. It could be $q \neq 2$. We turned a message $M$ of length $k$ into a codeword $W$ of ...
Efraim's user avatar
  • 11

1
2 3 4 5
37