# 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,832 questions
Filter by
Sorted by
Tagged with
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 ...
• 339
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 ...
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 ...
1 vote
22 views

• 315
287 views

• 271
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-...
• 1,128
33 views

• 11
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 ...
• 369
1 vote
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 ...
• 2,067
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 ...
• 116
1 vote
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 ...
• 305
96 views

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$,...
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 ...
• 281
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 ...
• 339
1 vote
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 ...
• 189
37 views

1 vote
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 ...
• 111
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}|\...
45 views

• 9,575
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 ...
1 vote
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 ...
• 368
1 vote
25 views

• 1,337
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 ...
• 287
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 ...
• 73
1 vote
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 ...
• 11