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

learn more… | top users | synonyms

0
votes
0answers
17 views

Binary Polynomial Factoring

I just need confirmation that I've done my math right. If $a(x) = x^4 + x^3 + x + 1$ and $b(x) = x^2 + x + 1$ are binary polynomials, find binary polynomials s(x) and r(x) such that $x^4 + x^3 + x + ...
0
votes
0answers
5 views

Primitive elements of GF(8)

I'm trying to find the primitive elements of GF(8), the minimal polynomials of all elements of GF(8) and their roots, and calculate the powers of α^i for x^3 + x + 1. If i did my math correct, I ...
0
votes
0answers
12 views

Generator matrix of a Reed-Muller code [duplicate]

I need to find a generator matrix (2,4) of the Reed-Muller code (2,4), the dimension of R(2,4) and the minimum distance of R(2,4). I know that R(r,m) of order r, then length: n^m, dimension k = 1 + ...
0
votes
1answer
18 views

Find out the primitive polynomial GF(3)

1.) $x^2 + 2x$ 2.) $x^2 + 1$ 3.) $x^2 + 2$ 4.) $x^2 + 2x$ 5.) $x^2 + 2x + 1$ 6.) $x^2 + 2x + 2$ 7.) $x^2 $ 8.) $x^2 + x + 2$ 9.) $x^2 + x + 1$ Can any one help me in listing out primitive polynomials ...
1
vote
1answer
17 views

When Errors Go Undetected in CRC

I understand that CRC will not be able to detect errors if: The remainder of $E(x) / G(x) = 0$ $E(x) = G(x).Z(x)$ for some polynomial $Z(x)$ I understand the first point, which means that if the ...
0
votes
1answer
13 views

List primitive elements of GF(2^3) = {0, 1, a, a^2,…, a^6} [on hold]

I need the find the primitive elements of GF(2^3) = {0, 1, a, a^2,....., a^6}, could any one help me out how to go about it?
0
votes
1answer
32 views

How many primitive elements does GF(256) have?

I know the answer for this is 36 but I don't exactly know how to reach to this. Can you any one help me in understanding this.
0
votes
1answer
17 views

Polynomial Arithmetic Modulo 2 (CRC Error Correcting Codes)

I'm trying to understand how to calculate CRC (Cyclic Redundancy Codes) of a message using polynomial division modulo 2. The textbook Computer Networks: A Systems Approach gives the following rules ...
1
vote
1answer
35 views

Problem with itinerary of a coding problem with infinite 1's

If $f(x)=2x \ mod \ 1$ on $[0,1)$. Then if we code $x \in [0,1)$ with its itinerary w.r.t. the partition $P_0=[0,1/2)$ and $P_1=[1/2,1)$. Can you show that there is no point $x$ whose itinerary has ...
3
votes
1answer
32 views

Error-correcting codes used in real life

I am very interested in coding theory and I wonder if there is a particular kind of codes used in practice. For example I read that Reed-Solomon codes are often used for encoding data on a compact ...
2
votes
3answers
53 views

Code is not cyclic for any q

I have code $C$ over $F_p$ with generator matrix which looks like $G = \begin{pmatrix} 0 &0& 0& 1& 0& 1& 1 &1\\ 1& 0 &0& 0 &1 &0 &1& 1\\ ...
1
vote
1answer
37 views

Monomially-equivalent linear codes?

I am trying to show that the linear transformation of two monomially-equivalent linear codes preserves the minimum distance and the two equivalent codes have the same dimension. First, what is the ...
1
vote
1answer
15 views

Singleton bound

I am looking at the proof of the singleton bound and I don't understand the first step. I want to show that $A_q(n,d)\leq q^{n-d+1}$ where $A_q(n,d)$ is the code of maximal size given these ...
1
vote
3answers
94 views

Proof verification: A $(16,5,8)$ binary code does exist.

Well I have used spheres in coding with radius, $r=\left\lfloor\frac{\delta -1}{2} \right\rfloor=\left\lfloor\frac{8 -1}{2} \right\rfloor = 3$ and that means we have $\sum \limits_{i=0}^3 {16 \choose ...
1
vote
2answers
75 views

Find the neighbors in Gray Code sequence

I want to find a way to figure out what are the most closest neighbors in a Gray Code sequence. For example I have 010110, and I need to figure out which are its ...
0
votes
1answer
21 views

Write Generator Matrix (2,4) of Reed Muller code of (2,4)

I was wondering how to go about this sum, since I wasnt able to figure out how to solve this. Could any one help me out on this?
1
vote
1answer
13 views

If gen matrix has even weigth rows, do codewords have even weigth for non binary code?

Is that true that in a non binary code C every codeword has even weight if and only if every row of G has even weight?
1
vote
1answer
17 views

Subset of linear dual code

Hi I need to show that $$C_1 \subseteq C_2 \Leftrightarrow C_2^{⊥} \subseteq C_1^{\perp}$$ In guess I need to use standard form matrices for generator matrix and parity check matrix(also parity ...
1
vote
1answer
37 views

Matrix over GF(2)

Let B be a square matrix, let I be identity matrix of the same size, and let G be the generator matrix in standard form created by appending B to I. Prove that the code over GF(2) generated by G is ...
1
vote
1answer
65 views

Is there an error-correcting code where almost every word could be used as a codeword?

An error-correcting code for strings of length $n$ from a $K$ letter alphabet is a partition $\Pi$ of $K^n$ together with a choice function $\pi$ on $\Pi$. Let $A_i$ for $i<M$ enumerate $\Pi$, and ...
2
votes
2answers
70 views

Relative distance in Codes

I'm studying coding theory. In my lecture say that Hadamard codes have a optimal relative distance $1/2$. Where the relative distance of code $C$ with minimum distance $d(C)$ and block lenght $n$ is ...
0
votes
0answers
72 views

Determining the smallest burst error a system cannot correct.

Working on a question. I have an answer but fear I may have lost my grasp on the knowledge of this topic part way through as it seems I got to the answer too easily. So the question is: An error ...
0
votes
0answers
12 views

How do I use r code to solve for probability of normal distributions?

I don't understand which r code I am supposed to be using to figure these problems out. A brief explanation of what the code is doing would be amazing. The problems below are two different ...
1
vote
0answers
53 views

Information set of a linear code

I am trying to prove a couple of statements about information sets of linear codes, but i am having trouble with these proofs or i am not sure if i understand correct what i should prove. I would ...
0
votes
0answers
19 views

Pseudorandom Noise Sequences

A PN sequence based on LFSR can be analyzed using the Berlekamp-Massey algorithm. If I have a sequence that is a combination of two LFSR sequences, is there a similar way to recover the two LFSR ...
0
votes
1answer
26 views

Convolution/Deconvolution $\stackrel{?}{=}$ Coding/Decoding

In a strict mathematical sens, can a convolution/deconvolution be equivalent to a coding/decoding process ? I just got the remark from a reviewer that it's strictly different, it's a little surprising ...
3
votes
2answers
42 views

Proof of recursivity of Shannon's Entropy

Does anybody know a book where the proof of recursivity property of Shannon's Entropy can be found? I mean this: $$H(q_1,...,q_n)=H(q_1 + q_2, q_3,...,q_n) + (q_1 +q_2)H( \frac{q_1}{q_1+q_2} , ...
0
votes
0answers
23 views

Huffman code with specific source

There is n-ary Huffman code. Source has the following relative frequencies of t symbols: 1, $n$, $n^2$, $n^3$, . . . , $n^{t−1}$, where $t = 1 + k(n − 1)$ for some positive integer $k$. I need to find ...
0
votes
0answers
28 views

How do you construct a (6, 4, 4)-code?

I understand that the codewords in the code are of length 6, there are 4 codewords and the minimum distance of the code is 4.
1
vote
1answer
51 views

I am learning coding theory in discrete mathematics, can someone illustrate an example of an $alphabet$, code and codeword please?

I have that the following definitions; An $alphabet$ $\sum$ is a set of symbols. A code $y$ over $\sum$ is a collection of sequences of symbols. The members of $y$ are called codewords. Could ...
4
votes
0answers
44 views

On a problem of sphere-packing for Reed-Solomon codes

Suppose we have an $[n, k+1, n-k]$ Reed Solomon code $\mathcal C$ over $\mathbb F_q$, where $n-k=d$ is the minimum distance, and suppose that $d=2t+1$. We know that for every $r \in \mathbb F_q^n$ the ...
-3
votes
1answer
34 views

Coset Leaders and Syndromes

This is my Parity check matrix For Coset Leader 100010 Syndrome is 101 Could any one help me with the procedure, since I figured ...
0
votes
0answers
52 views

Syndrome Leaders

I've been stuck on this problem for a long time and I can't figure it out. I need to find the set of coset leaders and their syndromes. I have my coset leaders (I think) but I can't figure out how to ...
0
votes
1answer
57 views

Is there a binary [10,6,4] code?

Using the sphere padding packing bound formula I can conclude that 1 + 12 + 66 $\ge$ $2^{6}$ which indicates that there MAY be a binary [10,6,4] code, however I cannot prove that there is. How can I ...
0
votes
0answers
27 views

Finding a parity check matrix of a binary code

I'm supposed to find a parity check matrix of a binary [6,3,3] code. Given a generator matrix G I can find a parity check matrix by row reducing until I get the identity matrix, then take $-A^{\top} ...
1
vote
2answers
38 views

Parity Check Matrix From Hamming code length 15

I am not able to figure out whats the method the calculate the parity check matrix. I am not sure if this is the method which is 1 ,2 3,.........15. So I can write its binary 0001, 0010, 0011,..... ...
0
votes
1answer
28 views

Finding a standard generator matrix given a binary code

My question is how do I find the standard generator matrix of a binary [7,6,2] code? From what I understand a generator matrix for $C$ is any $ k \times n$ matrix $ G$ with entries in $ ...
-2
votes
0answers
40 views

Give the parity check matrix H of a binary Hamming code of length 15. [closed]

I am not able to figure out whats the method the calculate the parity check matrix. I am not sure if this is the method which is 1 ,2 3,.........15. So I can write 0001, 0010, 0011,..... 1111 and make ...
1
vote
0answers
23 views

Generalised Reed Solomon Codes Examples

Generalised Reed Solomon codes are defined as follow: From the definition, what is the range of $f$? Will any $f$ do? Also, what does $v_if(\alpha_i)$ mean? Does it mean multiplication in finite ...
0
votes
0answers
44 views

Good coding theory books?

Next week starts my coding theory course and i am really looking forward to it. Can anybody suggest me good coding theory books? I've already taken Cryptography class last semester and i studied it ...
2
votes
0answers
27 views

on basic theory over $\mathbb{Z}_4$-linear codes

I am a bit confused about this example in Huffman and Pless's Fundamentals in Error-Correcting Codes. This can be found in Chapter 12: Let $\mathcal{C}$ be a nonempty subset of $\mathbb{Z}{}^4_4$ ...
3
votes
2answers
64 views

$\dim (D-P)=\dim (D)-1$

I'm trying to prove this question: Let $D$ be a divisor in $F|K$ such that $\dim (D)\gt 0$ and $0 \neq f\in \mathscr L(D)$. Thus $f\notin \mathscr L(D-P)$ for almost all $P$. Then show that ...
1
vote
1answer
40 views

How many points does it take to identify a low-order polynomial in $\mathbb{Z}_N$?

I want to split the Bush's Baked Beans recipe into $M$ parts so that any set of $N<M$ people can reconstruct the recipe, but with the following constraints: Each person knows only a yes or no ...
3
votes
0answers
24 views

Linear code from larger linear code

Question 2.16 of Essential Coding Theory by Guruswami, Rudra and Sudan asks to produce a $[n - d, k - 1, d'\geq\lceil d/q\rceil]_q$ code from an arbitrary $[n, k, d]_q$ code. Here we are working over ...
5
votes
2answers
90 views

Efficiently factoring polynomials over $\Bbb F_2$

I am attempting to write some software which is intended to generically answer the question of which Cyclic Redundancy Code (CRC) generating polynomial is used for a given set of sample messages using ...
0
votes
1answer
34 views

Existence of linear code with length $7$, dimension $4$ and distance $4$

Suppose I want to construct a linear node such that the code has length $7$, dimension $4$ and distance $4$. Before constructing such a code, we need to prove the existence of the code. But I don't ...
1
vote
1answer
33 views

Ternary Golay codes and correction probability

We define the probability of a given linear binary code C [n,k] as: $$P_{corr}(C)=\sum_{i=0}^n\alpha_i(p)^i(1-p)^{n-i}$$ Where $\alpha_i$ is the number of coset leaders of weight $i$. I am asked to ...
1
vote
1answer
39 views

Extended Golay Code - Vectors of Odd Weight

In V(24,2) every vector of odd weight is at distance at most 3 from some code-word in $G_{24}$, the extended binary golay code. This seems to be a known result appearing in many texts and papers, ...
0
votes
0answers
65 views

Proving that number of codes with even weight is the same as number of codes with odd weight for a specific code book

Consider the $[n,n]$ code-book $C_0=\{0,1\}^n$ with $n$ being odd and the codes $c_i \in C_0=[c_1,c_2,...,c_{2^n}]$ being sorted in the ascending order of hamming weight (from $0$ to $n$). Now let's ...
2
votes
2answers
37 views

Binary Hamming code - number of words weight $i$

Define $A_i$ as the number of words in binary Hamming code of weight $i$. Prove: $$A_1=0, A_0=1$$ $$(i+1)A_{i+1}+A_i+(n-i+1)A_{i-1}= {n \choose i}$$ I am a tad clueless as to how to proceed. ...