error-correcting codes, error-detecting codes and related algebraic and/or combinatorial constructions

learn more… | top users | synonyms

0
votes
1answer
17 views

Understanding the hamming bound

I have a theorem for the hamming bound or the sphere packing bound. A q-ary $(n, m, 2e+1)$ code satisfies $$M \bigg\{ \binom {n}{0} + \binom{n}{1} (q-1)+...+\binom{n}{e}(q-1)^e\bigg\} \leq q^n $$ ...
0
votes
1answer
17 views

The probability of i errors in specified positions

In a binary code of length n p(exactly i errors in specified positions)=$t^i (1-t)^{n-i}$. I have an example where $C=\{000,111\}$, the binary repetition code of length 3. Suppose 111 is ...
-1
votes
0answers
10 views

Dimension of BCH code of length 80 [on hold]

I want to answer this question from Rudolf applied algebra. Determine the dimension of a 5-error-correcting BCH code over $F_3$ of length 80. Is there a fast way to do this ?
0
votes
0answers
20 views

degree of generator polynomial $m(x)$

Suppose $Q$ is cyclic $(h,q)$ code over $F_u$ such that $\gcd(h,u) = 1$. Prove that degree of the generator polynomial $m(x)$ of $Q$ is $h - q$. Why do we need the condition $\gcd(h,u) = 1$ ? Any ...
0
votes
1answer
18 views

Does generator matrix of a code $C$ must have linearly independent rows?

Def: A generator matrix $G$ with entries in $\mathbb{F}_q$ generates code $C$, and each rows of $G$ is basis of $C$. Does generator matrix of a code $C$ must have linearly independent rows? ...
1
vote
0answers
13 views

Minimize the rank of a matrix with some entries known

Let $m,n$ be two positive integers, with $m\geq n$. Suppose we have $m$ sets $A_1,\ldots, A_m\subseteq [n]$, with $|A_i|=d_i$. Let $\mathbb F$ be a finite field of size $q$. Let $D$ be the set ...
0
votes
0answers
7 views

Why extend the perfect binary Golay code?

The perfect Golay code [23,12,7] is most often seen in its extended version [24,12,8], with the added parity bit. The extended Golay code has had a lot of practical applications. But why not the ...
1
vote
1answer
30 views

Word lengths of optimal binary code

Given an optimal binary code (ie the expected word length if as small as possible while the code is still decipherable) with word lengths $s_1, \ldots,s_m$, I'd like to show the following ...
0
votes
0answers
5 views

Power moments identities for homogeneous weight

Pless power moments identities for the Hamming distance are a far reaching consequence of the MacWilliams identities. For codes in the homogeneous metric is there an analogue of the former when the ...
0
votes
0answers
24 views

Coding Theory Proof, prove C is m-1 Error - Correcting but not m error correcting

Let A be a q-ary alphabet where q ≥ 2. Let m ∈ N and let C be the repetition code of length 2m over A Prove that C is (m−1)-error correcting, but not m-error correcting So far I know that something ...
2
votes
2answers
43 views

trouble understanding calculation of signal-to-noise for ldpc codes

My apologies if the answer to this question is too easy. I am a mathematics student and the subject of low density parity check codes is new to me. In many papers on LDPC codes, there are plots ...
1
vote
0answers
16 views

Linear complexity of powers of a periodic sequences over finite fields

Let $\mathbf{a}^N = a_0 a_1\cdots a_{N-1}$ and let $\mathbf{a} = \mathbf{a}^N\mathbf{a}^N \cdots $ be an $N$-periodic sequence over the finite field $\mathbb{F}_q$ with $q$ elements, where $N \mid ...
2
votes
1answer
22 views

The algebraic structure of repeated root cyclic codes

Is there a generator theory for repeated root cyclic codes over finite fields? In other words is the ring $GF(q)[x]/(x^n-1)$ principal when $(n,q)>1$?
1
vote
1answer
13 views

Why a code has code words with length $3$ add a parity check matrix become length $4$

Let $\mathcal{C}$ be the code whose codewords are all the words of length 3. Let $D$ be the code formed by adding a parity check matrix digit to each codeword in the code $C$. Find $D$. The ...
1
vote
2answers
78 views

Show that there is precisely one cyclic code C of length 4 and dimension 2. Write down all the codewords in C.

I have shown there is one cyclic code, put not sure how to calculate the codewords in C. I think that the generator matrix is \begin{bmatrix}1&0&1&0\\0&1&0&1\end{bmatrix} but ...
0
votes
1answer
40 views

Codewords of C(6,K,4)

Suppose we have code with length of binary words 6. Like 000000 000001 But with distance 4 like 000000 001111 (meaning ...
0
votes
0answers
13 views

“Canonical” choice of parity check matrix from generator matrix

Let $\mathcal{C}$ be a binary linear code of length $n$ and dimension $k$, given as the left-image of an $k \times n$ generator matrix $G$: $$ \mathcal{C} = \{ i G : i \in \mathbf F_2^k \} \subset ...
0
votes
1answer
13 views

Show code $C$ is a 1 error correcting

Let $C=\{(0,0,0,0,0),(1,1,1,0,0),(0,0,1,1,1),(1,1,0,1,1)\}\in\mathbb{F}_2$. Show $C$ is $1$ error correcting. Definition: a code $C\subseteq\mathbb{F}^n$ is t error correcting , if for any two ...
1
vote
1answer
25 views

Generator matrix of $E_5$

Let $E_5$ denote the binary even weight code of length 5. Write down a generator matrix of $E_5$. So I know the length $n = 5$ is the number of rows in the generator matrix and the number of ...
1
vote
1answer
29 views

higher moments of entropy… does the variance of $log x$ have any operational meaning?

The Shannon entropy is the average of the negative log of a list of probabilities $\{ x_1 , \dots , x_d\}$, i.e. $$H(x)= -\sum\limits_{i=1}^d x_i \log x_i$$ there are of course lots of nice ...
0
votes
0answers
15 views

Large sparse binary matrices with little row overlap

How can I construct sparse binary matrices $A : M \times N$, with ~ $N p$ ones in each row, so that rows don't overlap much, i.e. the maximum $\qquad \text{size} (\ A \text{ row } i \ \cap\ A ...
2
votes
0answers
16 views

Generator and check matrices of Hamming code

What is the method to find a generator matrix and a check matrix of a Hamming code? I'm current trying to find a generator matrix of Ham$(2,3$). This is how far I have got: $$n = \frac{q^s - 1}{q - ...
2
votes
1answer
23 views

$C\subseteq D \subseteq \mathbb{F}^n_q$ where $|C| < |D|$ and $C$ is a perfect code. Show that $d(C) > 2d(D)$.

You are given that $C\subseteq D \subseteq \mathbb{F}^n_q$ where $|C| < |D|$ and $C$ is a perfect code. Show that $d(C) > 2d(D)$. So that means that $M|S_t(\underline{0})| = q^n$ for $C$. ...
1
vote
0answers
19 views

Constructing generator matrix of a linear code

The linear code $C \cong \mathbb{F}^5_2$ is given by $C = \{(x_1, x_", x_3, x_4, x_5) | x_1 + x_2 + x_3 = 0, x_4 + x_5 = 0$ in $\mathbb{F}_2\}$. Write down a parity check matrix and a ...
0
votes
0answers
19 views

Design n length and k error correcting BCH code

I am trying to figure out, how to solve a type of exam question, but I am stuck. The example (usually asked for 1 or 2 error correction and n<10 length in $Z_2$ or $Z_3$): In ...
1
vote
1answer
21 views

Finding out the generator and correction matrices from a given codeword dictionary (hamming & linear codes - coding theory)

I'm struggling with a problem that I'm kinda lost. Here it is: A binary code $C$ with length $6$ is constructed as follows: for each tuple $(x_1,x_2,x_3)\in {\mathbb F}_2^3$ the code contains the ...
1
vote
1answer
35 views

Coding theory in group rings

I am doing some extra practice problems and I got stuck on this one: Show that every element in the group ring $Z_2 C_n$ with even support (i.e. $wt(u)$ is even) is a zero-divisor. (Hint: Show ...
0
votes
1answer
33 views

Parity check matrix intuition

I am currently learning algebraic coding theory. There is something I would like to understand, so according to my book the way we generate this parity check matrix is that we pick some matrix A and ...
3
votes
0answers
30 views

Asymmetric Multiple Error Correction

In some non-volatile memories, errors are only affect one logic state (just 1->0). Is there a coding technique which could correct k asymmetric errors? I know that the BCH code could correct k random ...
0
votes
1answer
24 views

why ISBN-13 does not always detect a transposition error as ISBN-10

For a valid 10-digit ISBN number, $x_{10}−x_9x_8x_7−x_6x_5x_4x_3x_2−x_1$, if we switch 2 digit, $x_{10}−x_9x_8x_2−x_6x_5x_4x_3x_7−x_1$, then it becomes a invalid number. But for a valid 13-digit ISBN ...
1
vote
0answers
49 views

Relation between ranks of submatrices of a matrix. [closed]

If $\text{rank}(S(i-1,j-1))=\text{rank}(S(i,j-1))=\text{rank}(S(i-1,j))$ then there is a unique value for $s_{ij}$ such that $\text{rank}(S(i,j))=\text{rank}(S(i-1,j-1))$, I want to know why does a ...
1
vote
1answer
22 views

How do we find the minimum distance of a narrow sense BCH code?

I know the designed distance, $d$, is a lower bound for the minimum distance, $d(C)$. Usually, in the examples I've seen, what we do is find the generator polynomial $g(x)$ of the code, then from $d ...
0
votes
0answers
22 views

number of strings with hamming distance exactly $d$

Given a set $S=\{x_1,x_2,\dots,x_n\}$ each $x_i$ can take a value from $\{0,1,2,\dots,k\}$ and a distance $d>0$, Let $D$ be the set of vectors that are pairwise different from each other by exactly ...
3
votes
0answers
108 views

Need help with the following problem on the decoding of BCH codes?

I have to write down a quasi parity check matrix of a BCH code of lenth 63 over $\mathbb{F}_{2^2}=\{0, 1, a, b=1+a\}$, then decode the vector ...
1
vote
0answers
27 views

Distance $d$-independent set in hypercube

Given a graph $G = (V, E)$, a distance $d$-independent set is a subset $S \subseteq V$ such that any two vertices $x, y \in S$ have distance at least $d$. Thus traditional independent sets are ...
0
votes
0answers
16 views

how to generate parity check matrix for a non-systematic generator matrix?

Introduction: Suppose $C$ is an $\left [ n,k \right ]$ code. Let $I_{k}$ be the $k\times k$ identity matrix. Let $P$ be a $k\times \left (n-k \right )$ matrix. Then, $\left ( I_{k} | P\right )$ is ...
1
vote
1answer
29 views

Show $[6,3]$ quaternary code $\mathcal{G}_6$ is self-dual.

The $[6,3]$ quaternary code $\mathcal{G}_6$ has generator matrix $G_6$ in standard form given by $G_6=\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & \omega & \omega\\ 0 ...
0
votes
1answer
43 views

How to generate all possible SEC matrices for $n$-bit

I want to know if there is an algorithm with which man can generate all possible forms of single error correction matrices for n bits of data, both linear and non-linear. For example all possible ...
0
votes
1answer
27 views

Why do we always combine the elements with least frequencies in Huffman Coding?

In Huffman coding, we start by combining elements with least frequencies and putting them in correct order, and once we reach a condition where there is only 1 element left, from there we start ...
2
votes
1answer
20 views

Recursive convolutional codes

I'm struggling with the concept of recursive convolutional codes. Say we have the generator matrix $$\begin{pmatrix} \frac{D}{1+D^3} & 1 & 0 \\ \frac{D^2}{1+D^3} & 0 & 1 ...
1
vote
0answers
14 views

Recursive encoder, binary delay operator, convolutional codes

Say we have a recursive encoder and we can write the codewords $x^j$ in terms of input bits $u^i$ and binary delay operators as $x^1 = \frac{D}{1-D^3}u^1 + \frac{D^2}{1-D^3}u^2$. Maybe this is ...
0
votes
1answer
27 views

What are the roots and conjugates of a minimum polynomial?

I have an exam coming up on coding theory stuff and I'm stumped on how to find the minimum polynomial. A study guide I was given is here: ...
0
votes
0answers
10 views

Error-free transmission through a channel

Question: Prove that if, for a given channel matrix $P$ of a channel $(A,B,P)$, there exists $C \subseteq A$ such that for every $a_i,a_j \in C (i \ne j) $, $(P^{t} P)_{i,j}=0$ where $P^t$ is $P$ ...
1
vote
0answers
16 views

Rate of Koetter-Kschischang Codes

I'm studying this article on coding theory. Here $W$ denotes a $N$-dimensional vector space over $\mathbb{F}_q$. A code $C$ then consists of code words $V\in C$, where $V\subseteq W$ is a subspace of ...
1
vote
1answer
40 views

Encoding the answers to questions somewhere in a binary tree

I have a sequence of binary questions $(U_1,\dots, U_N)$ with some distribution. I know the answer to $n\leq N$ (mod-)adjacent questions, and want to convey this knowledge with as few bits as ...
3
votes
1answer
30 views

What does it mean to represent elements of an ideal?

Say I have the polynomial $x^9 + 1$ Then: $x^9 + 1 = (x+1)(x^2 + x + 1)(x^6 + x^3 + 1)$ is a complete factorization over $GF(2)$ of $x^9 + 1$ The dimension of each ideal is: length $n - ...
0
votes
0answers
15 views

What is the cardinality of the inverse distance of elements in an integer group of bit strings?

What is the cardinality of the inverse distance of elements in an integer group of bit strings of length $3?$ Re-worded, for each element $w$ in integer group ${\mathbb Z_2}^3$, what is $|D^{-1}(w)|$ ...
1
vote
1answer
31 views

Construct generator matrix given generator polynomial?

How would I take a generator polynomial and construct a generator matrix out of it for a cyclic code? For example, I have a cyclic code in: $R_{15}=GF(2)[x] / \langle x^{15} + 1\rangle$ This is ...
1
vote
0answers
38 views

Finding all elements in GF(2^4) in terms of given polynomial

I'm working with polynomials over finite fields at the moment and a question. I found this table http://www.csee.umbc.edu/~lomonaco/f97/442/Peterson_Table.html and I picked a polynomial of degree 4 ...
2
votes
1answer
55 views

Suppose exist a $[n , k , d ]$ liner block code like $C$ can you get me hints to prove exist a $ [ n , k , d-1 ] $ liner block code like $C' $?

Suppose exist a $[n , k , d ]$ liner block code like $C$ from $\Bbb{F_q}^n $ can you get me hints to prove exist a $ [ n , k , d-1 ] $ liner block code like $C' $ from $\Bbb{F_q}^n $?