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

learn more… | top users | synonyms

-1
votes
0answers
8 views

Huffman's Code Question about optimality [on hold]

Suppose P is a source with N Symbols and L(C) is the total length of the codewords in an optimal binary code C for P. Show that if C, $C^1$,...,C$^{N-1},C$^{N-2} is the sequence of codes constructed ...
2
votes
0answers
11 views

ternary code from Hadamard matrix

I am looking for a direct proof of this statement: "A $12\times 12$ Hadamard matrix is the generator matrix of a ternary selfdual (linear) $[12,6,6]$ code $C$." That the length is 12 is clear. As ...
0
votes
0answers
19 views

Constant-weight code for error correction

I need some Constant-weight code for error correction. Understanding how these codes generated is really hard for me. The papers of this topic are focus on lower bound and upper bound. What I need is ...
4
votes
0answers
20 views

How to number the natural numbers lexicographically with minimal overhead (and provide a lower bound for the overhead)?

Working in binary, note that the number 100 is lexicographically smaller than the number 11 even though $100 > 11$. How can we devise a function $f$ such that $f(a)$ is lexicographically smaller ...
1
vote
0answers
20 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 + ...
1
vote
1answer
16 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
13 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
19 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
18 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
14 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 ...
4
votes
1answer
34 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
76 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
73 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
74 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
43 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
28 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
45 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 ...