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

learn more… | top users | synonyms

0
votes
0answers
9 views

Idempotent generators of the four binary QR codes of length 7

I have a coding theory assignment and I thought it would be a good idea to double check before I hand it in. I'm asked to find the idempotent generators of the four binary QR codes C1, C2, C3, C4, of ...
1
vote
0answers
16 views

Give the generator polynomial of a binary cyclic [9, 2] code.

I'm new to Cyclic Codes and I'm not sure the process to find a generator polynomial of a cyclic code. I know what a cyclic code is, but not sure how to find a generator polynomial. Since the question ...
2
votes
3answers
36 views

question on morse code

The morse code is made up of marks called dots and dashes."Q", for example is (--,--).Is it possible to make up such a code so that every letter of the alphabet is represented by at most three marks? ...
0
votes
0answers
13 views

Encode A11B modulo 37

Encode the word A11B modulo 37 using the encoding 0=0, 1=1, . . . , 9=9, A=10, B=11, . . . , Z=35, blank space=36. I took the weighted sum: 5(10) + 4(1) + 3(1) + 2(11) + 1(c) ≡ 0 mod 37 Solving, i ...
1
vote
0answers
56 views

Why does the eigenvector have to be positive here?

The following Pictures are taken from "Symbolic Dynamics and Coding" by Lind and Marcus.! Can you tell me why it is so important that the eigenvector $v$ is positive? Where exactly is this ...
0
votes
0answers
26 views

self orthogonal binary code

I know the definition of a self-orthogonal (or weakly self-dual) code; however, I am experiencing a bit of a trouble in building such codes - well, except trivial ones, but that is not interesting. ...
-1
votes
0answers
33 views

Berlekamp-Massey Algorithm [closed]

I am using this algorithm to find the connection polynomial of (1,0,0,0,1,1,0) over the binary. I computed it by hand but I come on a wrong polynomial. In fact after the first iteration I get $d=1$ ...
2
votes
0answers
21 views

Leech Lattice and Golay Code

Consider the following Miracle Octat Generator or MOG. Choose the sign $\pm 3$ and fill in the blanks $\pm 1$ to create a point $x$ in the Leech lattice $\Lambda_{24}$ with $||x||^2=8$. $ ...
0
votes
1answer
14 views

Construct a 2-error correcting Reed-Solomon code over GF(11).

I'am trying to construct a 2-error correcting Reed-Solomon code over GF(11). Cna anyone help me to start?
0
votes
1answer
10 views

Self-dual code from parity-check matrix

I am trying too make a self-dual code from this parity-check matrix: _ _ | 1 1 1 1 1 1 1 1 | | 1 1 1 1 0 0 0 0 | H= | 1 1 0 0 1 1 0 0 | |1 0 1 0 1 0 1 0| ...
2
votes
1answer
51 views

Existence of a BCH-code?

I would like to ask about existence of a $[31,11,12]$ binary BCH-code. How to prove its existence, if it does i have to find the generator polynomial? Can i use some specific bound that could show or ...
2
votes
1answer
35 views

Code Correction-Detection

From theory: If, for a code C, d(C)≥ s+ 1 then C can detect up to s errors. If d(C) ≥ 2t+ 1 then the code C can correct up to t error. Assume that we have C={00001, 00010, 00100, 01000, 10000} ...
2
votes
1answer
21 views

Parity Bit Detecting Odd Bit Errors

I'm going over a past paper which has a true or false question with the following statement. A single parity bit computed over 128 data bits can detect an error when bit-flips occur in exactly 93 ...
2
votes
1answer
17 views

Undetected Errors in 2 Dimensional Parity

Given a two dimensional parity with a data block of two rows and two columns what is the probability that a four bit error goes undetected? The naive method would be to look at all ways in which an ...
2
votes
2answers
53 views

Coding theory - polynomial

Let $C \in (\mathbb{Z}/5)^3$ be the code consisting of all elements $(x_1,x_2,x_3)$ satisfying $x_1 +3x_2 +2x_3 = 0$ Show that this is a 1-error detecting code. What is the minimal distance of $C$? ...
0
votes
1answer
34 views

(32,7) Reed Muller code [closed]

I was wondering if someone can give me a hint on the problem I have. I came across (32,7) RM code that I am trying to decode. I was given the generator matrix that obviously contains R(1,5) and an ...
1
vote
1answer
43 views

Code that can be generated from 3 of 5 trusted people?

Suppose a computer contains sensitive data protected by a 3-digit passcode. (I understand this does not provide much security in the real world, but for the sake of the problem, assume only 3 digits.) ...
0
votes
1answer
46 views

Explicit formula for Nth string of Gray Code.

From Wolfram MathWorld, we have: "A Gray code is an encoding of numbers so that adjacent numbers have a single digit differing by 1. The term Gray code is often used to refer to a "reflected" code, ...
1
vote
2answers
43 views

Show that four codewords is the maximal size for a code in V^8 = {(a1,…a8) | ai is in {0,1}} that corrects 2 errors

Here's what I have: The size of the set $V^8$ is $2^8=256$. If the code can correct 2 errors, the minimum distance of the code must be 5. Then the size of an open ball of radius 5 around the code ...
0
votes
1answer
27 views

Highest pairwise Hamming distance between k bitvectors of length n

What is the highest achievable pair-wise Hamming distance $d$ between all possible pairs from $k$ bitvectors each having a length of $n$ bits? The content of each bitvector can be arbitrary, only the ...
-1
votes
1answer
32 views

Find the number of primitive elements

How can i find the number of primitive elements over the field of order q? GF(27) for example. Is there a formula that I can follow? I'm really confused on how to find them. Any help would be much ...
2
votes
2answers
20 views

Palindromic Hypotenuses?

What is the largest seven-digit palindrome which can be expressed as the sum of two perfect squares? I tried Java but couldn't get the right answer, and unfortunately OEIS ends at around 5 digits in. ...
0
votes
1answer
46 views

How does an alphabet size relate to the Kraft-McMillan Inequality?

I'm trying to figure out how the alphabet size m relates to the McMillan Inequality. I'm using Norman L Bigg's equation which is $\sum_{i=1}^M \frac{ni}{b^i}$$=\frac{n_1}{b^1}, \frac{n_2}{b^2}, . . . ...
1
vote
1answer
28 views

Calculation of polynomial in the finite field

I'm trying to understand the McEliece cryptosystem and I'm looking to this paper http://www.mif.vu.lt/~skersys/vsd/crypto_on_codes/goppamceliece.pdf On page 26 they are calculating syndrome and ...
0
votes
0answers
22 views

Explaining of lost probalbity over random loss channel

I am reading a paper about packet loss probability over random loss channel. In this paper, the author give a equation about loss probability as $(1)$. However, I cannot understand the meaning of it. ...
0
votes
1answer
30 views

Counting binary words distance one from codewords

If you have a [15,11] hamming code, how would you count the number of binary words that are distance 1 from codewords? I know this code will have 2048 codewords, and there are 32768 binary words of ...
2
votes
0answers
13 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
23 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
23 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
33 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
31 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
14 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
21 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
21 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
42 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
40 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
36 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
47 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
57 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
42 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
24 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
104 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 ...
2
votes
3answers
192 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
28 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
14 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
18 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
38 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
66 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
76 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
76 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 ...