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

learn more… | top users | synonyms

0
votes
0answers
12 views

What bound does the Hamming bound give you for the largest possible size of a $t$-error-correcting code of length $2t + 1$?

Let $\mathbb{A}$ = $\{0, 1\}$ and suppose $t$ is a positive integer. What bound does the Hamming bound give you for the largest possible size of a $t$-error correcting code of length $2t+1$? I have ...
-3
votes
0answers
21 views

How do I approach this question? [on hold]

Show that there is a unique cyclic code C of length 6 and dimension 3.
1
vote
0answers
31 views

Intuition behind the link between coding theory and group theory

I am trying to find an easy link between group theory and coding theory. The usual path that most of the texts follow is that they present introductory material on groups, fields, rings, etc., and ...
0
votes
1answer
20 views

How do I prove that if $x, y ∈ F_n^{2}$ then w(x) + w(y) + w(x+ y) is even and at most $2n$?

Let $w(x)$ denote the Hamming weight of a binary word $x = (x_1,x_2, \ldots, x_n) \in \mathbb F_2^n$. Show that if $x, y ∈ \mathbb F_2^n$ then $w(x) + w(y) + w(x+ y)$ is even and at most $2n$. I ...
0
votes
0answers
32 views

Maximum $M$ in Binary$ (5,M,3)$ Code

The sphere packing bound (hamming bound) gives that $M\leq5$, but I need to show 'by construction' that $M=4$. It would take a long time to write out all possible sets of code words of size $4$ and ...
0
votes
0answers
11 views

Determining generator matrix

Gents, I have the 128 codewords of a [14,7,4] binary linear code - which is actually the Plotkin $(a\mid a+b)$ construction of $Ham(3,2)$ and $Sim(3,2)$. Now, I want to have its generating matrix, ...
-2
votes
0answers
18 views

Weight distribution of Triple error correcting BCH codes [on hold]

if there are n choices of syndrome s 1 not equal to zero then how many choices for s 1 not equal to cube of s 3 in triple error co rrecting BCH codes
1
vote
1answer
23 views

properties of a non systematic code we can extract from his “systematic” version

Given a non systematic linear code matrix representation $G_{ns}$ (k rows and n columns) we say that the codeword $c$ is equal to $c=vG_{ns}$ (where $v$ is the input sequence) Is it ALWAYS ...
0
votes
0answers
22 views

Convert a q-symmetric channel with p>(q-1\q) to a functioning channel [closed]

How to convert a $q$-symmetric channel with $p>(q-1/q)$ to a functioning channel so that the new $p' < (q-1)/q$ ? Any hint will be appreciated, thanks.
0
votes
0answers
20 views

how to build big size parity check matix?

I want to do a project and I need to have a parity check matrix for LDPC code which has big size ( for example in size $400 \times400 $). please tell me how can I build a matrix with this size.
0
votes
0answers
31 views

I'm needing help understanding this coding theory assignment

I'm needing help understanding how to approach this assignment. Create a code consisting of binary codewords. The code must meet three requirements -- Contain at least 20 codewords -- Have a minimum ...
0
votes
1answer
40 views

Equivalent codes

I'm having problems by understanding the use one can do of equivalent codes. To solve problems about a linear code with a generator matrix G, can I always assume that the matrix is in systematic form ...
1
vote
0answers
20 views

Duplication code - error correction

Explain how the duplication code given by {00,11,22} with letters in the set $\mathbb{Z}$/3 can detect one error. If I were to construct a table of Hamming distances, I would show that the minimal ...
6
votes
0answers
51 views

Finding a separating family of subsets of $[n]$ of size $n+1$.

I have this friend who always tells me problems I can't solve. Here is the latest one. We are given a family $\mathcal F$ of at least $2^{n-1}+1 $ subsets $[n]$. We must prove that we can ...
3
votes
2answers
51 views

How to obtain $n$ maximally different binary vectors with equal number of zeros and ones?

Imagine the set of all binary vectors of length $2m$ where each of the vectors has $m$ ones and $m$ zeros. I want to select some $n$ of these vectors such that the shortest distance among all pairs of ...
0
votes
0answers
14 views

Bound problem of Coding Theory when distance is even

I encounter the following two exercises when learning coding theory, but I can't get a proof. If there exists a $q$-ary code $(n,K,d)$, where $d=2l$ is an even number, prove that $q^n\geq ...
2
votes
2answers
35 views

Channel code for multiple bit errors

I've been exploring information theory out of personal interest and have a cursory understanding of Hamming Codes. From what I can tell, they're designed to exclusively detect the location of a single ...
3
votes
1answer
58 views

Sizes of Hamming balls on the discrete torus

Consider the discrete torus $\mathbb Z^2_k $, with $k$ even, i.e. the graph with vertex set $\{0,1,\dots, k-1\} \times \{0,1,\dots, k-1\}$ and edges between any pair of vertices which differ in ...
1
vote
1answer
33 views

Why the only binary MDS codes are trivial ones?

Why the only binary MDS codes are trivial ones? I have been thinking how to draw a contradiction by assuming the MDS code is not trivial. Thank you very much!
0
votes
0answers
22 views

Description length in model coding

In class, our professor posted the following: We will discretize $\theta$ (some model) into $1/\sqrt{n}$ distinct values. Intuitive argument: with N data points, our estimation error for $\hat ...
0
votes
0answers
21 views

How many different binary prefix-free encoding schemes with given lengths?

For length =3: Here is my thought process, since every word is length 3, they are all prefix-free from each other. Then, there are 8 choices for the first word, 7 for the second, etc. Therefore, ...
0
votes
0answers
25 views

List all vectors of the binary [9,2] cyclic code

How do I know how many vectors there will be? I know the length(dimension?) is 7. I also know the generator matrix is: ...
0
votes
0answers
18 views

Give the idempotent generators of the four binary QR codes C1 , C2 , C3 , C4 , of length 7.

I'm having trouble on some homework. This is the last problem and I can't figure it out. Can anyone help or point me in the right direction? Thanks! For each code Ci , 1 ≤ i ≤ 4, from part (a), give ...
0
votes
0answers
9 views

Generator polynomials of idempotent binary QR code

I'm doing some homework and I ran into a question that I just do not know how to do. I have to give the generator polynomials of the four binary quadratic residual codes of length 7. Quite honestly I ...
1
vote
1answer
38 views

Generator matrix of a binary cyclic code

I need to find the Generator and Parity check matrix of a binary cyclic [9,2] code. If I calculated right, the Generator polynomial is x^7 + x^6 + x^4 + x^3 + x + 1 and the check polynomial is x^2 - x ...
2
votes
0answers
22 views

Error correcting codes for asymmetric channels

Most work in error correction coding theory (Hamming, Cyclic, BCH, Reed-Solomon, Turbo Codes, LDPC...) deals with linear codes. Now, a linear code binary code is a good fit (only?) for a symmetric ...
1
vote
3answers
119 views

Irreducible factors of x^16 - 1 over GF(3)

Just want to double check my work. I'm trying to list the irreducible factors of $x^{16} − 1 $ over $GF (3)$ of degree $1$ and $2$ . Here's what I have: $$x + 1, x + 2, x^2 + x + 2, x^2 + 2x + 2$$ ...
0
votes
0answers
68 views

Finding a generator polynomial of all binary cyclic codes

I need to find the generator polynomials of all binary cyclic codes of length 7 that contain the vector (1, 1, 1, 0, 0, 1, 0). From what I know of generator polynomials of a cyclic code divides x^n - ...
2
votes
1answer
51 views

Show that the map $\varphi $ is an isomorphism.

We defined the Generalized Reed-Solomon codes the following way: $\alpha=(\alpha_0,\alpha_1,\ldots,\alpha_{n-1})\in \mathbb{F}_q$, distinct elements of the finite field $\mathbb{F}_q$, $n\leq q$, ...
1
vote
0answers
44 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 ...
2
votes
0answers
40 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
42 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
17 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
57 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 ...
8
votes
0answers
284 views

How can I construct a solution for this system of many inequalities?

Let there be types $\omega\in\{0,1\}^n$ drawn according to some probability distribution. Suppose that these types are relayed through some imperfect message service. Specifically, any type $\omega$'s ...
0
votes
0answers
34 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. ...
2
votes
0answers
29 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
23 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
27 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
58 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
39 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
36 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
26 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
60 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
40 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
44 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
62 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
62 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
32 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 ...
-2
votes
1answer
35 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 ...