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

learn more… | top users | synonyms

0
votes
0answers
16 views

Entropy of linear codes

To find the theoretically performance-maximizing coding scheme, we need to find $P_{X^n}$ such that it maximizes entropy. The best linear coding scheme is the maximum entropy probability distribution ...
0
votes
1answer
21 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 ...
0
votes
1answer
14 views

Theorem : Let $x,y$ be words form $\mathbb{F}_{q}^{n}$. Then $d(x,y)=wt(x-y)$. In particular, $d(x,y)=wt(x)$

Error Correcting code prove : Theorem : Let $x,y$ be words form $\mathbb{F}_{q}^{n}$. Then $d(x,y)=wt(x-y)$. In particular, $d(x,0)=wt(x)$ This definition might be helpful to prove the theorem ...
0
votes
0answers
16 views

Reed Solomon Encoding [on hold]

I'm trying to make a Reed Solomon (VHDL) implementation of the 802.15.7 Physical I Layer. I have problems in understanding the encoding system. It is described as following: Galois Field (16), ...
3
votes
2answers
31 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
12 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
37 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 ...
0
votes
1answer
38 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 ...
0
votes
0answers
29 views

Intuitive explanation of Shannon's source entropy in information / communications theory

I am trying to calculate the number of bits required to encode a message. FOr that, I am applying Shannon's entropy, H. I have done the implementation and playing around with themessage length and ...
2
votes
1answer
27 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
43 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 ...
3
votes
1answer
65 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}> ...
3
votes
0answers
121 views
+50

Find example of bch code

I want to show that the dual of a BCH code is not necessarily a BCH code, by considering for example a binary BCH code of length $9$. The parity matrix of a binary BCH code is of the following form: ...
0
votes
0answers
18 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
25 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
10 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
13 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
58 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, ...
0
votes
0answers
9 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
39 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
106 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
24 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
399 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
14 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
32 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
110 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
13 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
37 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
33 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 ...
0
votes
0answers
34 views

Is there any two way algorithm for compressing numbers?

I have this question that is there any way we can convert a number to another number with less character in the new number? For example, Imagine we have 811008 and if we divide this 13 times by 2, we ...
0
votes
0answers
18 views

Removing short-cycles in LDPC codes

I am having a hard time understanding the concept of removal of short cycles(i.e. 4-cycles, 6-cycles, etc) in LDPC codes. Can someone elaborate on this concept and possibly provide an example?
1
vote
2answers
29 views

Take the derivative of a Hamming Weight Enumerator

Background: The Hamming weight enumerator can be written as such: $$A(z) = A_0 + A_1z + A_2z^2 + ... + A_nz^n$$ With $A_i$ being equal to the number of code words of weight i in the code book for an ...
2
votes
1answer
41 views

How do I find the order of an element if I am given the minimal polynomial of the element?

For example, let's say I am given an element $α$ in a field of characteristic $2$. Further, I am given the minimal polynomial of α with respect to $GF(2)$. Let's say that minimal polynomial is $f(x) = ...
0
votes
0answers
23 views

Dual Hamming code

The dual of Hamming code Ham($r$,2) is calling the simplex binary code. Proof that every non-zero codeword of the simplex code has weight $2^{r-1}$.I try to find a relation for the code like in ...
0
votes
0answers
12 views

Codewords with even weight form an MDS code

I am new to the area of coding theory and am really only studying it because it relates to a problem I have been working on. I have seen several places mention that the set of words with even hamming ...
0
votes
0answers
36 views

Convolutional codes in matlab

I'm trying to construct a convolutional code in Matlab and encode some random data. However the length of the codeword are not as expected. This is the problem information: ...
1
vote
0answers
28 views

Spectral Characterization of Reed-Solomon Codes

I am having trouble understanding the spectral characterization of Reed-Solomon codes. My script states the following: An evaluation codes is defined as: $$C = \{(c_0, \ldots, c_n) : c_l = ...
0
votes
3answers
63 views

Maximum number of colors that can be used for the vertices of a eight-dimensional hypercube

What is the maximum number of the colors what can be used to color the vertices of a eight-dimensional hypercube, such that for every vertex of the cube, every color is used as the color of a ...
0
votes
0answers
30 views

Error Correcting Code and Graph Theory

I am currently in an introductory graph theory class, and we are supposed to give a short presentation by the end of the semester. Recently, I've learned (a very small amount) about error correcting ...
0
votes
0answers
29 views

Cyclic code and its generating polynomial

Can someone give me an example of a $[3,2]$ linear cyclic code and its generating polynomial? Does this mean it is a binary cyclic code with length 3? Also how do I find all binary/ternary cyclic ...
0
votes
0answers
35 views

States of an encoder

Im having troubles coping with encoders in other than controller normal form. Given for example this encoder (i/o is in binary) It has 2 physical states, because it has one memory and stores u_1+u_2 ...
1
vote
1answer
47 views

Let C be a self-dual binary code with parameters $[n,k,d].$

Let C be a self-dual binary code with parameters $[n,k,d]. $ (i) Show that the all-one vector $(1, 1, . . . , 1)$ is in $C$. (ii) Show that either all the codewords in $C$ have weight divisible by ...
0
votes
0answers
27 views

Give a complete list of ternary cyclic code of length 3.

Give a complete list of ternary cyclic code of length 3. For $x^3-1\in\mathbb{F}_3[x]$, $x^3-1=(x-1)(x^2+x+1)$. Generator polynomials of ternary code of length $3$ are $\{1,x-1,x^2+x+1,x^3-1\}$, ...
0
votes
0answers
23 views

Let $C$ a linear binary code with $C=C^{\perp}$

Let $C$ a linear binary code with $C=C^{\perp}$. Prove that all the words of the code have weight a multiple by 4 or half of them have weight a multiple by 4 and the other half have weight a number ...
1
vote
3answers
95 views

How is this possible to convert a long string to a number with less characters?

I'm going to write a program (function) that can convert a long string to a number. For this, first I convert each character (letter) to a number; like ...
0
votes
0answers
25 views

Question about subfield subcode of a cyclic code

If $C$ is a cyclic code over $\mathbb{F}_{q^n}$, then $C|_{\mathbb{F}_q}$ is a cyclic code over $\mathbb{F}_q$. I know this holds for a linear code, what about a cyclic code? Thanks in advance