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

learn more… | top users | synonyms

0
votes
1answer
13 views

What is the max size of subset of a Hamming Space with this property

Keep in mind I know virtually no coding theory, I simply recognized this as an equivalent formulation to another question I was considering. Let $F(r,n)$ denote the set of all words of length $r$ on ...
0
votes
1answer
41 views

What is a divisor (of an algebraic curve)?

So if I have a polynomial $p(x,y)$ and define a curve $C$ based on $p$, what is a divisor? In the context I'm looking at (where I'm trying to learn about Goppa codes), in Joyner et al.'s "Applied ...
0
votes
0answers
16 views

$C$ is a Reed-Solomon code. $1_n \in C$ iff $g(1)\neq 0$.

I have no idea how to prove the following. Could you help me? Let $C$ be a Reed-Solomon code of length $n$ and let $g$ be its generating polynomial. $1_n \in C$ iff $g(1)\neq 0$, where $1_n$ is a ...
1
vote
0answers
20 views

BCH Coding: Parity Check Matrix

I was referring to a publication on BCH codes in GF(64) (http://ipnpr.jpl.nasa.gov/progress_report2/42-38/38O.PDF) where I noticed that the Parity Check Matrix (attached image) that they have derived ...
0
votes
1answer
25 views

Probability of a word being incorrectly decoded.

Let C be the ternary repetition code of length 4 over the alphabet $\{0,1,2\}$. If the probability of each symbol being wrongly received is t and each symbol is likely the probability of a word being ...
0
votes
1answer
27 views

How to solve binary equation which has mod?

Three messages in binary format are sent $$ a_0 a_1 a_2 a_3 $$ and coded in binary format $$b_0 b_1 b_2 b_3 b_4 b_5 b_6$$ Symbols $$b_0,b_1,b_2,b_3,b_4,b_5,b_6$$ are the coefficients of the Boolean ...
-1
votes
2answers
44 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
18 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 [closed]

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 ?
1
vote
0answers
22 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
28 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
17 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
9 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
39 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
45 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
24 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
14 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
79 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
41 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
14 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
26 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 ...
2
votes
1answer
35 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
17 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
25 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
23 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
36 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
34 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
26 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
23 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
23 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
17 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
44 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
21 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
28 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 ...