Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [coding-theory]

Use this tag for questions about source coding, error-correcting codes, error-detecting codes, and related algebraic and/or combinatoric constructions.

0
votes
1answer
11 views

How to compute the syndrome polynomial? BCH code

I just copy the notation quickly. A variable with a space and then a number it means is a power. I have BCH cyclic code like that: B = BCH(7) of length 15 = 2 4 − 1. F 16 = F 2 [x]/(x 4 + x + 1), α ...
3
votes
1answer
39 views

Optimal code for simple game

Setup: Alice and Bob are playing a cooperative game. Alice chooses a number $y \in \{1, 2, 3, 4\}$ uniformly at random. Bob doesn't observe $y$; his goal is to guess $y$. Alice can send Bob a message $...
0
votes
1answer
22 views

What is the theory behind seeding a CRC?

The basic CRC check is a polynomial division in this form: $$ Q(x)Gen(x) + Rem(x) = \frac {x^nMsg(x) } { Gen(x) } $$ It's recommended that the polynomial is seeded so that an all-zero message does ...
1
vote
2answers
86 views

Find the smallest positive integer $\ell$ such that $3 \cdot \left(4^m + 1\right)$ divides $2^\ell-1$

Find the smallest positive integer $\ell$ such that $3 \cdot \left(4^m + 1\right)$ divides $2^\ell-1$ Hint: The sought $\ell$ is the multiplicative order of $2$ in the ring of integer residues ...
0
votes
1answer
61 views

q-ary symmetric channel error probability

Why is it valid to assume that $0< p < (q-1)/q$, where $p$ is the probability of symbol error. When $(q-1) / q< p <1$, why are we able to flip it? We are not in binary channel, so we are ...
1
vote
1answer
40 views

Generator matrix for Reed-Solomon code

Given $\,f(t)=t^3+t+1,\,$ let $\,\mathbb{F}_{2^3}=\frac{\mathbb{F}_2\left[t\right]}{\langle f\,\rangle}\,$ be a finite field and $\,\xi=t\,\left(\textrm{mod}\,f\right).$ Let also $\,\mathcal{C}\,$ be ...
0
votes
1answer
42 views

Binary codes that can correct one error and what is encoded/decoded has rate “arbitrarily close” to $1$

Task: Show that there exist binary codes that can correct one error and that have rate arbitrarily close to $1$. This is asking for an existence proof, so either by contruction or using some well-...
1
vote
1answer
35 views

Check a word given a generator matrix G

Take the binary code C with generator matrix: $$ \left( \begin{array}{ccccc|cccc} 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 ...
0
votes
0answers
16 views

Underbound length of a ternary linear code

I have to prove the following theorem: Let $C$ be a ternary linear $[n,2,d]$-code. Prove that $d+ d/3 \leq n$. Now I don't really see what the best approach for this would be. I was thinking maybe ...
1
vote
2answers
30 views

Find the generator matrix

Given the parity check matrix $$H=$$ \begin{bmatrix} 4&1&4&2&0&4\\2&1&1&4&2&0\end{bmatrix} find its generator matrix I know generator matrix $G$ and $H$ ...
0
votes
1answer
25 views

Show that a binary perfect linear $[n,k,d]$ code is generated by its words of minimal weight.

Question Show that a binary perfect linear $[n,k,d]$ code is generated by its words of minimal weight. What I have so far We can try to solve this by induction on the weight of the words in the ...
-1
votes
1answer
16 views

How to check whether a matrix is a parity check matrix for a Hamming Code Ham(2,5) or not:

How to check whether a matrix is a parity check matrix for a Hamming Code Ham(2,5) or not: The matrix is \begin{bmatrix} 4&1&4&2&0&4\\2&1&1&4&2&0\end{bmatrix} ...
0
votes
0answers
11 views

verifying G*(transpose(H)) = 0 for generator matrix G and parity check matrix H.

I've got a non systematic generator matrix G given by, G= [1 1 0 1 0 0 0;0 1 1 0 1 0 0;0 0 1 1 0 1 0;0 0 0 1 1 0 1] I've converted this matrix by the following operations, (1)exchanging C3 and C6 (2)...
0
votes
2answers
36 views

Finding a binary prefix code provided lengths

Firstly, I am relatively new to this particular forum, and I usually use Stack exchange (maths). I do not know if this is the right place to post so please be aware in case, I should ask this question ...
0
votes
1answer
77 views

I can't solve a cyclic redundancy check

In my book there's an example of how to do a cyclic redundancy check with regular numbers. I've tried to complete the exercise with binary numbers but without success. In the book the given ...
1
vote
1answer
23 views

How flexibible can one choose the properties of algebraic-geometric codes?

Theorem 7.3 on page 67 in these lecture notes states the following. For every even power of a prime $q$, and every parameter $\delta < 1 - 1/(\sqrt{q} - 1)$, there exists an infinite family of $q$-...
0
votes
0answers
34 views

The Three Trivial Perfect Codes

On Coding Theory, there's three trivial perfect codes. They are: Binary codes of odd length Codes with contains only one codeword Codes that are the whole $A^n_q$ So, the $A^n_q$ case, considering ...
2
votes
0answers
18 views

Restricting an MDS code to a subset of coordinates

If we have an $(n,k)$ MDS code and we take a subset of coordinates in a set say $J$, where $|J| > k$. If $c$ is a codeword in the original MDS code let $c_J$ denote its projection on the set $J$. ...
1
vote
1answer
22 views

Dual of generalized Reed-Solomon code

I need to show that $GRS_{n,k}(\alpha,\mathbb{1})^{\perp}=GRS_{n,n-k}(\alpha,\alpha)$, where $\alpha=(1,a,\ldots,a^{n-1})$, $a$ is a primitive $n$-th root of unity, $\mathbb{1}=(1,1,\ldots,1)$. So, ...
-1
votes
1answer
27 views

Hamming(7,4) problem : Check my answer is correct or incorrect.

Find a data to be transmitted with Hamming(7,4) if given data bits : 1010. $a_1=a_3\oplus a_5\oplus a_7=1\oplus0\oplus0=1$ $a_2=a_3\oplus a_6\oplus a_7=1\oplus1\oplus0=0$ $a_3=a_5\oplus a_6\oplus ...
1
vote
0answers
23 views

Finding minimum weight codewords in a Code over F9.

Hello everyone reading this. I seem to have a problem understanding weights in Coding Theory, and will attempt to provide a solution to a problem - please correct me where I am wrong. Consider the ...
0
votes
0answers
22 views

Idempotents of binary cyclic codes

Let $e(x)$ be an idempotent in $R_n = \mathbb{F}_{2}[x]/\langle x^n - 1 \rangle$, where $n$ is odd. Let $\alpha$ be a primitive $n^{th}$ root ofunity in some extension of $\mathbb{F}_2$. I'm trying to ...
1
vote
0answers
13 views

Rank deficient LDPC code

I am new to working on LDPC codes and have gotten stuck on this issue for some time. I am struggling on how to deal with parity check matrices that are not of full rank. I generate the parity check ...
0
votes
0answers
12 views

Understanding the weight enumerator of the Ternary Golay code.

Im trying to calculate the weight enumerator of the ternay Golay Code $\mathcal{G}_{11}$, using help from this paper. I understand how we get $A_0$ and $A_5$, but not $A_6$. In the proof of the second ...
2
votes
1answer
26 views

Polynomial-time algorithm to generate the “opposite” of a binary Gray code?

I'm seeking to implement a function $\phi(n,k,i)$ of integers $n,k,i$ where $$1 \leq k < n\\1 \leq i \leq N\\N = {n \choose k}$$ that returns all possible $n$-element binary vectors containing $k$ $...
0
votes
2answers
31 views

What are linear codes having minimum distance 2 used for?

Consider the following parity check matrix $$H = \begin{bmatrix} 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 \...
0
votes
0answers
10 views

Problem about constructing extended ternary golay code from ternary golay code

I have one problem about some construction I'm about to explain. I'm asked to construct $\mathcal{G}_{12}$ from $\mathcal{G}_{11}$. In my notes I'm using those generator matrices (respectively): $G_{...
1
vote
1answer
26 views

Words of weight 5 in in Ternary Golay Code

I'm not really good at doing this type of exercices. But I'd like to know how to prove that ther are 132 words of weight 5 in the Ternary Golay Code. I am not allowed to use the weight enumerator. I ...
1
vote
1answer
32 views

Bound on code: $A(n,d) \leq 2A(n-1,d)$

Note: We are talking about binary codes. Definition 1: For integers $1 ≤ d ≤ n$, a code $C$ is an $(n, d)$-code if it has length $n$ and minimum distance $d_H (C) ≥ d$. An $(n, M, d)$-code is an $(n,...
0
votes
1answer
34 views

Coding Theory- minimum weight of dual codes

Let C be a linear code in (F^n)q with minimum weight w(C) = 1. Prove that the dual code C^⊥ has no codewords of weight n. I think that I might have to do a proof by contradiction but i'm not sure ...
0
votes
1answer
15 views

When the generator of a code satisfies $G\cdot G^T={\bf 0}$

Consider $A$ is an $k\times n-k$ matrix over $\mathbb{F}_q$. Consider an $k \times n$ matrix $G=(I_k\mid A)$ as a generator of a code $C$. My question: If $G\cdot G^T={\bf 0}$ over $\mathbb{F}_q$, ...
0
votes
1answer
37 views

On Reed Solomon Codes

I am trying to determine all possible values (parameters $n,k$) for which an RS-code exists over $GF(2^9)$. Using definition of RS-code, we know that $n|q-1$ and the designed distance $\delta \ge 2$ ...
0
votes
1answer
42 views

Showing that if the KL divergence between two multivariate Normal distributions is zero then their covariances and means are equal

We have two, k-dimensional multivariate normal distributions $\mathcal{N}_0(\mu_0,\Sigma_0)$ and $\mathcal{N}_1(\mu_1,\Sigma_1)$ with means $\mu_0$ and $\mu_1$ and covariances $\Sigma_0$ and $\Sigma_1$...
5
votes
3answers
185 views

Passing a binary message to a friend where one of the components is always “turned on”

Suppose I want to communicate an integer to a friend between 1 and 1000. In order to pass this message I use a $k$-vector whose entries can be set to $0$ or $1$. So for example if $k=3$, a natural way ...
1
vote
1answer
25 views

Constructing the binary Golay code

I'm reading up about the binary Golay code of length $23$. I know it's a cyclic code and I also know it's a quadratic residue code. I've read that we can consider the linear code over $\mathbb{F}_2$ ...
1
vote
1answer
71 views

Constructing generator polynomial for a BCH code

How can I construct a generator polynomial for a BCH code $(7,3)$ code over $GF(2^3)$ with designed distance $\delta =5$. Observe that $$x^7-1 = (x+1)(x^3+x+1)(x^3+x^2+1)=m_0(x)m_1(x)m_2(x)$$ where ...
1
vote
2answers
40 views

Hamming code of length $8$ self dual

I'm reading a paper by N.J.A Sloane on self dual codes, and he introduces the binary Hamming code of length $8$ with generator matrix $$ G = \begin{bmatrix} 1&1&1&1&1&1&1&...
0
votes
0answers
15 views

Affirmation in Ternary Golay Codes theory

There is an affirmation in Ternay Golay Codes Theory i don't get: Let's supose we have $u\in G_{12}$. Then, as far as we know $G_{12}$ is a self-dual code, so his generator matrix and his parity-...
0
votes
0answers
44 views

Comparison of two Huffman codes:

A set of eight messages with probabilities of $0.2$, $0.15$, $0.15$, $0.1$, $0.1$, $0.1$, $0.1$, and $0.1$ are encoded into a ternary Huffman code. One set of Huffman codewords are {$2, 01, 02, 10, ...
0
votes
3answers
86 views

Prove that the Hamming distances between three n-tuples cannot be 6,2,7

Let $x,y,z \in \{0,1\}^n$, and let $d_H(x,y)$ be the Hamming distance between codes x and y. Prove $d_H(x,y) = 6$, $d_H(y,z) = 2$, $d_H(x,z) = 7$ cannot happen.
1
vote
1answer
21 views

Finding the number of roots of u(X,Y) under certain restrictions

Suppose $q$ is a prime power, gcd($s$,$q$)$=1$ and gcd($s$,$t$)$=1$ and $f(X)$ is a polynomial of degree $t$ over $GF(q)$. Also $u(X,Y)=\sum_{i,j} u_{ij}X^iY^j$, where $u_{ij}\in GF(q)$, $0\leqslant i$...
1
vote
1answer
36 views

Maximal likelihood Error/Syndrome table for $[16, 11]$ hamming code

I think I have to start with a parity check matrix for $[16,11]$ Hamming code. $$H = \left( \begin{array}{cccccccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 &...
1
vote
0answers
36 views

Reference request about experimental mathematical using computers

I have graduated last year. During my corsus I've done a lot of abstract algebra especially coding theory. I wish to put that "knowledge" in use and I think that the first step is to master a ...
1
vote
0answers
16 views

Idempotents and number of proper cyclic codes

So, there was a question on my exam last year as follows: Using idempotents, determine the number of proper cyclic codes of length 17. I got the question right, but I can't remember how to do the ...
1
vote
2answers
48 views

Generator matrix of the extended hamming code

Given a check matrix $H$ of the $Ham(3,2)$ code, so $$H = \begin{bmatrix} 1&1&1&1&0&0&0\\ 1&1&0&0&1&1&0\\ 1&0&1&0&1&0&1 \end{...
1
vote
1answer
34 views

How to find actual code based on parity check matrix, generator matrix and received code?

We are given the parity check equations: $$\begin{align} x_5 &= x_1~x_3~x_4\\ x_6 &= x_1~x_2~x_3\\ x_7 &= x_2~x_3~x_4 \end{align}$$ the generator matrix, $G$ is $$\begin{align} ...
1
vote
1answer
28 views

How to show that in a self-dual code all words have weight divisible by 4 or half do it and the anther half don't.

The title is basically what i have to do: Let $C$ be a binary self-dual code: Show that all words have weight divisible by four or half are divisible and the another half don't. I showed that ...
0
votes
1answer
28 views

what means the redundacy of a code?

I was reading a paper about a transposition and single deletion error correcting code and they claim that the redundancy of the code was only $log(6n-3)$ bits. But what does that means? I was ...
0
votes
0answers
13 views

For any code $C$ over $\mathbb{F}_q$ and any $\alpha \in \mathbb{F}^*_q$

For any code C over $\mathbb{F}_q$ and any $\alpha \in \mathbb{F}^*_q$, let $\bar{C}_{\alpha} = \bigg\{ \bigg( c_1, \ldots, c_n, \alpha \sum\limits_{i=1}^{n} c_i \bigg) : (c_1, \ldots, c_n) \in C \...
0
votes
1answer
30 views

Linear coding theory problem. Syndrome

The problem says: Supose that H is a control matrix of a $[n,k]_q$-code C and let's consider $x\in\mathbb{F}_q^n$ wich $s(x)=xH^t=v\in\mathbb{F}_q^{n-k}$. If $y\in x+C$ and $w(y)=t$ then show that $v$...