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

learn more… | top users | synonyms

0
votes
0answers
6 views

How to find generator matrix given a PCM of a Hamming code?

I'm having trouble as how to begin solving this. I'm given a Hamming Parity Check Matrix, and I have to find code vector V and generator matrix G. H = \begin{bmatrix} ...
0
votes
0answers
35 views

Using Fermat's Little Theorem?

I have this problem: Let $f(x)=\prod_{i\in K}(x-\alpha^i)$ where $K$ is a subset of $\{0,1,\dots,n-1\}$. Show that $f(x)$ has coefficients in $GF(q)$ iff $k\in K\Rightarrow qk\,(mod\,n)\in K$. My ...
0
votes
0answers
20 views

Dictionary learning for sparse coding using ADMM

I'm trying to formulate an ADMM for performing dictionary learning (for sparse coding) on a set of data. Let's assume we have a data matrix of $X \in \mathbb{R}^{M \times N}$, a dictionary of $D \in ...
2
votes
1answer
41 views

Which polynomials with binary coefficients evaluate only to 0 or 1 over an extension field?

Consider the polynomial $p(x) = 1+x^5+x^{10}$ with binary coefficients. Consider the multiplicative group of $\mathbb{F}_{16}$, and let $p(x)$ be evaluated at each of these $15$ elements. The only ...
-1
votes
0answers
11 views

equivalence of binary matrices in GF(2)

I have a binary matrix [G] of size 13x20. After column exchanges i obtained [G1]=[I : P]. G1 is an augumented matrix. I is an identity matrix of 13x13 and [P] is of size 13x7. Now my question is that ...
0
votes
1answer
23 views

Finding a generator matrix for C in standard form using only row operations

Let $C$ be the [5,4] code over $F_7$ with generator matrix $G=$ $$\begin{pmatrix} 1 & 0 & 3 & 5 & 4 \\ 0 & 0 & 2 & 3 & 5\\ 2 & 1 & 0 & 3 & 0\\ 1 ...
0
votes
1answer
16 views

Equivalent Codes and weight

If $C$ and $D$ are equivalent linear codes, how can I show that the number of words with weight $w$ in Code $C$ is equivalent to number of words with weight $w$ in Code D?
0
votes
0answers
26 views

Generator Matrix G

The question is: Suppose C is a linear $[3,2]$-code over $\Bbb{F_q}$ with generator matrix $G$. Show that using elementary operations, we can transform $G$ into one of the matrices: $$ M_1 = ...
0
votes
1answer
37 views

Probability in a Random Matrix

Assume the following random matrix with $N$ rows and $L$ columns consisting of elements in {0,1}. \begin{bmatrix} 1 &0 & 1 & ...&0 \\ 1 & 0 & 0& ... &1 \\ 1 & 0 ...
1
vote
0answers
20 views

Binary Goppa Codes: Calculating code characteristics (traces, length L, distance d, k)

I am having (many) troubles with binary Goppa Codes. My question is at the moment: How do I calculate the trace on given points $tr(\alpha^u)$? For example: Given a finite field $GF(2^6)$ and the ...
1
vote
1answer
22 views

Equivalence of Codes

Consider the binary codes below: C1= {0000, 1100, 1010, 0110} C2= {0111, 0100, 0010, 0001} C3= {1000, 0100, 0010, 0001} Show that C1 is not equivalent to C3. Is C2 equivalent to C3? When we say two ...
0
votes
0answers
31 views

What are the possible dimensions of a binary cyclic code of length 37?

What about the possible dimensions of a 16-ary cyclic code of length 37? [Edit]: The cyclic codes of length $37$ are in a bijective correspondence with factors of $x^{37}-1$. Furthermore, the ...
4
votes
1answer
32 views

Hamming(7,4) matrix for decoding?

Encoding a 4bit word (vector) $w$ can easily be done by $c := Gw$. Decoding a codeword of the Hamming(7,4) code is normally done by first computing $p = Hc$ where $p$ is zero, if there is no 1-bit ...
0
votes
1answer
37 views

How to prove that a code has an unique decodability

I have the alphabet: $A=\{a,d,k,u\}$, The code: $c=110011100111010$ An code words: $$ \begin{array}{|c|c|c|c|} \hline x \in A& a & d & k & u \\ \hline \gamma (x) & 001 & ...
2
votes
0answers
57 views

Picking codewords that are close

Let $[n,k,d]$ be a linear code over $\Bbb F_q$ with minimum distance $d$ and number of minimum weight codewords $N_d$. How many ways can you select codewords $c_1,\dots,c_T$ (assume $T\ll q^k$) such ...
3
votes
1answer
76 views

Upper bounds for the dimension of a binary cyclic code

Let $\mathbb{F}_2 = \{0,1\}$ denote the field with two elements. Consider a binary $N$-tuple $a = a_0 a_1 \ldots a_{N-1}$, of elements $a_i \in \mathbb{F}_2$. The cyclic code $C_a$ corresponding to ...
0
votes
1answer
30 views

Huffman coding - conditions for perfect tree output

The question is: Given 4 characters and their frequencies, what's the max possible difference between the frequency of the rarest character and that of the most common character, so the output Huffman ...
1
vote
0answers
30 views

The rate of a code with prescribed minimum distance

Fix $\delta\in(0,1)$. For integer $n$, what is the largest size of a subset $C\subset\{0,1\}^n$ such that any two elements of $C$ are at least $\delta n$ away from each other in the Hamming metric? In ...
0
votes
1answer
33 views

If $n=(b_k,b_{k−1},…,b_1)_2$ where $b_i$ are the digits of n in binary, what is the binary expression of $n+1$?

I have a curiosity. If $n=(b_k,b_{k−1},...,b_1)_2$ where $b_i$ are the digits of n in binary, what is the binary expression of $n+1$? Is there a relationship that binds $n+1$ to $b_i$ (ie the digits ...
0
votes
0answers
19 views

Prove a relation on Gray code $(0,b_k,…,b_3,b_2)+(b_k,b_{k−1},…,b_2,b_1)$.

Suppose we want to find the n-th entry in the binary Gray code. Write $n=(b_k,b_{k−1},...,b_1)_2$ where $b_i$ are the digits of n in binary. Then, prove that the corresponding Gray code entry is ...
0
votes
1answer
15 views

Cryptographic encoding scheme that enables counting

Suppose there are $n$ players. Each player has a $k$-length bit vector. Is there an efficient way of encoding the $k$ length bit vectors, such that after receiving the $n$ encoded outputs, one can ...
1
vote
1answer
21 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 ...
1
vote
0answers
42 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
28 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
38 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
17 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, ...
1
vote
1answer
25 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

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.
1
vote
0answers
44 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
48 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
52 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
52 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
39 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
59 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 ...
2
votes
1answer
53 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
24 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
20 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
10 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
51 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
24 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
130 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
148 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
54 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
46 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
49 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
46 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? ...