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

learn more… | top users | synonyms

3
votes
1answer
19 views

Dimension of Linear code

Assume that $\alpha$ is a primitive element of $GF(q)$ and $n=q-1$. The $C$ code over $GF(q)$ with length $n$ defined as follows $$ \{(f(1),f(\alpha),\ldots,f(\alpha^{n-1}))\mid f \in GF(q)[x],\ ...
0
votes
0answers
30 views

Create a code with randomly skipped/duplicated bit?

Is it possible to create an error correcting code (linear or non linear) that is capable of handling a single skipped or duplicated bit? So lets assume that I transmit the code 1101 then the ...
2
votes
0answers
29 views

Neat argument for why $A(4,3)=2$

$A(n,d)$ is the size of a largest code of length $n$ and minimum distance at least $d$. (Im using Hamming distance as my distance) Im trying to show from first principles that $A(4,3)=2$ Its easy to ...
2
votes
1answer
33 views

Why can't we have a codeword of weight $d-1$?

There are no two words of a code $C$ that have weight $\leq \lfloor \frac{d-1}{2} \rfloor$. Proof: $e_1, e_2 \in x+C$ with $||e_1||, ||e_2|| \leq \lfloor \frac{d-1}{2} \rfloor$ then $||e_1-e_2|| ...
0
votes
0answers
16 views

General and restricted linear error correcting codes

I am reading a lecture where there is a term "general linear error correcting codes". My question is which is a difference between "general linear error correcting codes" and a linear code? Also ...
1
vote
0answers
20 views

Variation of the Linear Decoding Problem

The decoding linear problem is defined as Let $\textbf{s} \in \{0,1\}^r$. We denote the set of words in $\{0,1\}^n$ with syndrome $\textbf{s}$ by $$S_{\textsf{H}}^{-1}(\textbf{s})=\{\textbf{y} \in ...
0
votes
1answer
18 views

Finding the covering radius of $C=\{0000,1111,2222\}$

I am trying to find the covering radius of $C=\{0000,1111,2222\}$ I know the definition of the covering radius $S$ for a code $C$ is the smallest non negative integer y such that $$\cup_{x \in C} ...
2
votes
1answer
60 views

Minimum distance of a ternary linear code

How large can the minimum distance of a ternary linear code of length $n$ and dimension $k=n^{0.99}$ be? Clearly, it can be $n^{0.01}$: by choosing basis vectors with exactly $n^{0.01}$ many nonzero ...
1
vote
1answer
36 views

Finding the probability that a word is correctly received

Let $C=\{000,111,222,333,444\}$ The question is to find the probability $p_c$ of a word being correctly received if each symbol has the probability $t$ of being incorrectly received and each wrong ...
1
vote
1answer
20 views

Finding the minimum distance $d=d(C)$ of $C$

The parity check matrix of a generator matrix $G$ is given as $$H=\left[\begin{array}{ccccccc} 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0\\ ...
1
vote
1answer
42 views

Over $F_5$, why does $f(1)=-2$ where $f(x)=x^2+2$

I am working over $F_5$ and $f(x)=x^2+1$ I am told that $f(1)=-2$. I understand that $-2=3$mod$5$ Why can we not leave it as $f(1)=1^2+2=3$? Because $3$ mod $5$ $=3$ so why do we have to "change" ...
0
votes
1answer
40 views

Is the polynomial $x^2 + x+2$ primitive?

Let $F_5$ be the field of integers modulo $5$. I am trying to find out if $x^2 + x + 2$ is primitive or not. So first we see that the divisors of $24$ are $1,2,3,4,6,8,12$. We find $$x^2=-x-2$$ ...
0
votes
0answers
15 views

Does this definition of a primitive polynomial make sense?

I have this question in a past exam paper. Let $F_p$ be the field of integers modulo prime $p$. I have the question What is meant by saying $f$ is primitive? This is the solution I have. ...
0
votes
0answers
17 views

How to decompose a Finite State Machine (FSM) into a cascade of two or more FSMs?

I am coming from Electrical Engineering background and would like to know how can I decompose a given FSM into a cascade of two or more FSMs. To be more precise, I am looking at following questions ...
1
vote
1answer
27 views

Permutations acting on coordinates of codewords

Let $\mathcal{C}$ be a binary code of length $n$. The automorphism group of $\mathcal{C}$ is defined to be the set of permutations in $S_n$ that take $\mathcal{C}$ to itself. The text by MacWilliams ...
0
votes
2answers
42 views

Finding modular inverse of every number mod 26?

I am looking at cryptography, and need to find the inverse of every possible number mod 26. Is there a fast way of this, or am i headed to the algorithm every time?
0
votes
1answer
39 views

Proof regarding size and dimension of linear codes

The problem is stated as follows: Let C be a binary linear code of length n, dimension k and distance d and assume that C contains at least one element of odd weight. Let C' be the subset of C ...
0
votes
2answers
36 views

Repetition code and binary symmetric channel, where error is near 1/2

I want to send one bit $x$ over a noisy channel, specifically, a binary symmetric channel with error probability $p$, where $p=(1-\epsilon)/2$ and $\epsilon$ is small. In other words, the error ...
0
votes
0answers
12 views

Is the generating matrix for a Reed Solomon code always of the same general form?

Everything I've read about about Reed Solomon codes so far describes the generating matrix as being a $k \times n$ matrix of the form: $\left[ \begin{array}{ccccc} 1 & 1 & 1 & ... ...
0
votes
1answer
24 views

For linear codes, does the generator matrix need to be in standard form?

I've been given a generator matrix $G$ and for a linear code over $\mathbb{Z}_{2}$ and a message $m$ to encode. Now this seems simple enough because I know the encoded message $c$ should just be $c = ...
0
votes
0answers
33 views

Minimum distance of a code

Let C be an $[n,k.d]$ code of cardinality $q^k$ over a an alphabet of size $q$ then the minimum distance of C can be defined as follows $$d= n - max_{I \subset [n]} \lbrace |I| \; ; \; |C_I| < q^k ...
0
votes
0answers
25 views

Covering radius of binary simplex codes

I found the following statement: All non-zero codewords of a binary simplex code with dimension $r$ have the weight $2^{r-1}$, hence they have the distance of $2^{r-1}-1$ from the all-one-word ...
0
votes
1answer
24 views

The ball of radius one with center at $(0,0,0,0,0)$ in $\mathbb{F}_{2}$ consists of $(0,0,0,0,0)$ and all the words weight one. For $w=(1,0,1,1,0)$,

definition : Let $w$ be a word in $\mathbb{F}_{q}^{n}$ and $r$ a natural number. The ball of radius $r$ with center $w$, denoted by $B_{r}(w)=\{x \in \mathbb{F}_{q}^{n} : d(w,x) \leq r\}$ . Now ...
3
votes
2answers
33 views

Error Correcting Code

In my Linear Algebra book I have a chapter about error correcting code. there is an example involving Redundancy in the form of a check digit : we have $white=(0,0)$, $red=(1,0)$, $blue=(0,1)$, ...
0
votes
0answers
14 views

Existence of Type I Self Dual Codes

How would I prove Type I self-dual codes (binary self-dual codes that are not necessarily doubly even) exist for every even length $n$?
4
votes
1answer
40 views

What definition of Reed-Solomon code is correct?

In the discuss with @Evinda we have the contradiction with the definition of Reed-Solomon Codes (not generalized case) over the finite field $\mathbb{F}_q$. We have two papers and ...
1
vote
1answer
46 views

Find minimum distance of the code

I want to show that the minimum distance of a narrow-sense BCH code over $\mathbb{F}_q$ with length $n$ and designed distance $\delta$ is equal to $\delta$ provided that it holds that $\delta \mid ...
2
votes
1answer
32 views

Why is d in A(n,d) not always equal to 1?

In Communication Theory, for $A(n,d)$ (=the size of a largest code of length $n$ and minimum distance at least $d$), why is $d$ not always equal to $1$? If min. distance $= d$, for any code of length ...
3
votes
1answer
45 views

Rate of a binary linear code given all code words have weight integer multiple of 4

Supposed C is a linear binary code with the property that each code word is of Hamming weight n*4 (that is every word has a Hamming weight that is an integer multiple of 4). Show that the rate of C is ...
4
votes
1answer
68 views

Distance of bch code

I want to show that a binary , narrow-sense BCH code of length $n=2^m-1 $ and designed distance $ \delta=2t+1 $ has minimum distance $ \delta$ , given that $ \sum_{i=0}^{t+1} \binom{2^m-1}{i}> ...
0
votes
0answers
20 views

In a binary code, all coordinates partake in at least one non-information set

It is true that all non-MDS $(n,k)$ codes contains at least one $k$-sized coordinate subset that does not correspond to an information set (because all such subsets are information sets iff the code ...
0
votes
1answer
30 views

Identically zero coordinate of a linear code

In a book (Covering Codes by Cohen, Honkala, Litsyn, Lobstein) I found the statement that the covering radius of a linear code without identically zero coordinate is at most $\lfloor n / 2 \rfloor$. I ...
0
votes
1answer
30 views

Number of errors detected from a generator matrix

Consider the encoding function $\alpha : \mathbb{Z_2^2} \rightarrow \mathbb{Z_2^5} $ given by the Generator matrix $$ G = \begin{bmatrix}1&0 &1& 0& 0 \\0& 1 & 0 & 1 & ...
1
vote
0answers
14 views

Channel capacity of sum of symmetric channels

I've got a channel matrix $P$ of the form $\begin{bmatrix} Q \\ R \end{bmatrix}$ where $Q,R$ are channel matrices of symmetric channels, so they now have different input alphabets but the ...
1
vote
0answers
17 views

Dimension of repetition code

I read a proof that the dimension of a repetition code is 1 using the equivalence of $Rep_{n,k}$ with $Span\{e_1\}$ but it's not very intuitive for me and I'd like to understand it using the ...
1
vote
1answer
63 views

Decode the message $(1,1,1,0,1,1,1)$ using the Hamming $ (7,4)$ code

The question is asking me to decode $(1,1,1,0,1,1,1)$ using Hamming $(7,4)$ code. I know that I am suppose to set a $3 \times 7$ matrix ${\bf H}$ and multiply it by ${\bf r}$ and set it equal to zero, ...
1
vote
0answers
18 views

Extended Golay codes are self dual

Show that extended Golay code $G_{24}$ and $G_{12}$ are self dual. To show it have to show that any two rows of $G_{12}$ and $G_{24}$ are orthogonal, that is inner product of any two rows are zero. ...
0
votes
0answers
13 views

Relation between Completely regular codes and Perfect codes

I have a question about completely regular codes. I know that each perfect code is a completely regular codes? Is it right? If it is right, I want to know the proof.
1
vote
1answer
40 views

Find information about distance of code

Suppose that we have a binary cyclic code $C$ of length $n \geq 3$ with generator polynomial $b(x) \neq 1$, where $n$ is the smallest natural number such that $b(X) \mid X^n-1$. I want to show that ...
4
votes
1answer
107 views

List of $n$-bit strings that approximately preserves Hamming distance

If $x$ and $y$ are both $n$-bit strings then their Hamming distance $d_H(x,y)$ is the number of positions in which they differ. Suppose we write out the set of all $n$-bit strings in some order $s_1, ...
1
vote
1answer
28 views

Is a code BCH, and if so, find largest $\delta$ and Bose distance

So I am working with cyclic codes of length $n=15$ over $\mathbb{F}_{2}$. I have all my cyclotomic cosets modulo $15$: $C_0=\{0\}$, $C_1=\{1,2,4,8\}$, $C_3=\{3,6,12,9\}$, $C_5=\{5,10\}$, ...
0
votes
1answer
26 views

parameters of a linear code constructed from another

For $C$, a $[n,k,d]$ linear code, we'll construct the following new code: $$ \widetilde{C}=\{(c_1,c_2,...,c_{i-1},c_{i+1},..,c_n)|c=(c_1,c_2,...,c_{i-1},0,c_{i+1},..,c_n) \in C\} $$ Now, ...
2
votes
5answers
400 views

Meaning of distance between two codes in coding theory

Suppose I have been given two codes $x$ and $y$ such that $x = x_1 x_2 . . . .x_m$ and $y = y_1 y_2 . . . .y_m$ where ${x_i} 's$ and ${y_i} 's$ are binary digits. Then we define the concept of ...
0
votes
0answers
15 views

Is this result for MDS codes known for all alphabets or just when it is a field

Let $A_q(n,d)$ be the maximum size of a set of words on $q$ letters of length $n$ with minimum Hamming distance d. The Singelton bound gives $A_q(n,d) \le q^{n-d+1}$. A code which meets this bound ...
0
votes
0answers
37 views

Density function of the square root of a random number (uniformly distributed from 0 to 1)

These questions were posted as review for material I've been covering in class. Suppose we execute the following code: U = MTUniform (0); X = sqrt(U); Here both U and X are doubles. What is the ...
6
votes
0answers
114 views

Find distance to a set (subspace) without computing closest point

General setup: we have a finite-dimensional normed linear space $(V, \| \cdot \|)$, a subspace $U \subset V$, and a fixed vector $v_0 \in V$. We want to find the distance between $v_0$ and $U$. (No ...
0
votes
0answers
13 views

Equivalence class of codes when $C$ is cyclic in $\mathbb{F}_2$ and $n=15$

My text defines an equivalence class of codes as the set of all codes that are equivalent to one another. It then asks me to give a defining set for a representative of each equivalence class of the ...
0
votes
0answers
15 views

Proving a subcode is cyclic.

I have that $C$ is a cyclic code over $\mathbb{F}_q$, with defining set $T$, and generator polynomial $g(x)$. Let $C_e$ be the subcode of all even-like vectors in $C$. I am trying to prove: 1) That ...
1
vote
2answers
41 views

It is {$00$,$10$,$01$,$110$} a Huffman code?

It is {$00$,$10$,$01$,$110$} a Huffman code?( I think that the answer is no, because the corresponding binary tree has only one vertex on the last level)
0
votes
1answer
45 views

Sum of two cyclic codes is a cyclic code.

My text made a small comment about cyclic codes: The sum of two cyclic codes $C_1$ and $C_2$, defined by: $C_1+C_2=\{c_1+c_2: c_1\in C_1, c_2\in C_2 \}$ The sum of two cyclic codes is also a cyclic ...