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

learn more… | top users | synonyms

1
vote
0answers
44 views

Generator polynomial creates a 127 bit sequence

I have been reading a paper that states that a generator polynomial $$ G(D)= 1+ D^4+D^7$$ creates a 127 bit sequence which is as follows 00001110 11110010 11001001 00000010 00100110 00101110 ...
1
vote
1answer
21 views

Tutorials on LDPC error correction codes

Please consider this as soft question. Recently, I have been studying channel coding and in particular error correction codes. I am looking for best tutorial (easy to understand) on LDPC error ...
0
votes
1answer
27 views

Error Correction Convolutional Codes - Coding Theory

This question is regarding convolutional encoders. I have come across an encoder that has a constraint length 7 and a generator polynomial of {133, 171}. My questions are next. 1- Does this mean ...
1
vote
1answer
31 views

Minimal polynomials

Can someone explain to me how the minimal polynomials in page 4 of this document are obtained? Please help me. http://web.ntpu.edu.tw/~yshan/BCH_code.pdf It should be something standard about ...
0
votes
2answers
32 views

parity check matrix of $\operatorname{ham}(3,3)$ code - struggling with $q=3$

I am confused about how to represent numbers when constructing a parity check matrix for a $\operatorname{ham}(3,3)$ code. I know that the dimension of a $\operatorname{ham}(r,q)$ matrix is $k=n-r$ ...
0
votes
0answers
14 views

Why the length of RS code is $2^m -1$

In 1960, Reed and Solomon suggest the codeword for a message $[x_0\ x_1\ \ldots\ x_k]$ as follows: $$[P_{(0)}\ P_{(\alpha)}\ P_{(\alpha^2)}\ \cdots\ P_{(\alpha^{2^m-1})}]$$ Where $$P_{(t)}=x_0 ...
0
votes
1answer
26 views

How to minimize the maximum Hamming distance of a linear block code.

I suspect it is possible to choose generators of 2^l so that: Each number 1-l is in some generator. The maximum Hamming distance between any two vectors would be at most (l+1)/2. For instance, ...
2
votes
0answers
26 views

How to find the power of generator defined over finite field , $\mathbb F_{2 ^m}$?

List item Actually ,I am trying to execute the algorithm to find the power of generator of field(group) as shown in table of attached file but when k=7 and onward ,I could not understand what is ...
0
votes
2answers
45 views

Checking irreducibility of a polynomial over a finite field

A part of a coding theory course I am doing includes some questions on irreducible polynomials. I have a question with solution but am worried I have interpreted it incorrectly. So for $\mathbb F_5$ ...
0
votes
0answers
21 views

Prove that in cyclic codes, ($C_1$+$C_2$)$^\perp$=$C_1^\perp$+$C_2^\perp$

Let $C_1$ and $C_2$ be cyclic codes over finite field with the same length. Prove that ($C_1$+$C_2$)$^\perp$=$C_1^\perp$+$C_2^\perp$. The direct conclusion is clear but how to prove the reverse ...
0
votes
0answers
33 views

Is there an alternative encoding scheme to binary where similarity of pattern correlates with size of number?

If I compare binary for 7 111 and binary for 8 1000 there is no correlation between these two patterns that suggests that ...
1
vote
0answers
33 views

Relationship between hamming weight and number of codewords of a binary code

Set $ N_c (i,4)$ as the number of codewords in a binary code C with hamming weights congruent to $i$ module $4$. Assuming C is of length $n$ and dimension $k$, how can it be proved that if $C$ is an ...
1
vote
1answer
37 views

Linearity of codes

Assuming $C$ is a binary linear code and let $a$ $\notin $ $C$ be any vector. Show that $C$ $\cup (a + C) $ is also linear. I know that for any $C_1,C_2 \in C $ then $\alpha C_1 + \beta C_2 \in C$ ...
1
vote
0answers
69 views

Vector distance of binary

Suppose $\overline{u},\overline{v},\overline{w},\overline{x}$ are four binary vectors, pairwise distance d apart. Show that d must be even, there's exactly one vector which is a distance $d\over 2$ ...
0
votes
1answer
18 views

Maximum code words

i am new to coding theory. i am trying to understand some of the basics by solving a few questions. I came across this one. Assuming $\\C$ is a binary (not necessarily linear) code of length $\\n$ and ...
0
votes
0answers
23 views

Intersection of balls in Hamming space [duplicate]

Let $B(x_1, r)$ and $B(x_2,r)$ be balls in $\{0,1\}^n$ (in Hamming distance). Denote by $d$ Hamming distance between $x_1$ and $x_2$. What is $|B(x_1, r) \cap B(x_2, r)|$ (asymptotically)? Upd: I ...
1
vote
0answers
40 views

DataMatrix convolutional codes

I'm trying to decode datamatrix code ECC 000-050 it uses convolutional codes for error correction. Could someone explain me how to decode the stream (e.g. few first bytes of the stream) or give some ...
0
votes
0answers
13 views

How to show a random matrix has large spectral gap?

If I know $Y$ is a random d-regular bipartite graph (tanner code in coding theory), can I show $Y^TY$ has large spectral gap with high probability? More specifically: If I know $Y=AX \in ...
1
vote
0answers
17 views

How to model a coding problem with Poisson Distribution

I've met a problem in information theory that deals with probability and number of occurrence. It states that: The probability of a single bit being corrupted is p. Now I have an error-correction ...
1
vote
1answer
18 views

One hypothesis concerning Hamming distance matrix

Suppose $a_1, a_2, \ldots, a_m$ are different strings of the same length n. And let $V = [v_1, v_2, \ldots, v_n]$ be a matrix such that $V_{i, j}$ is a Hamming distance between $a_i$ and $a_j$. ...
0
votes
0answers
20 views

How to make parity-check matrix

I'm working on exercise I found in book. There is a coding matrix, which elements are given as logarithm's values. Here is a matrix. $$G_c =\left( \begin{matrix} 2 & 1 & 1 & 0 & 1 ...
1
vote
0answers
18 views

Hat puzzle with non-standard number of players

I'm referring to the Ebert's version where the solution is closely related to Hamming codes. What happens if there are not 2^^K-1 players ? I wrote an algorithm to try to find how many N long ...
0
votes
0answers
23 views

Problem reducing a matrix modular 3

I am trying to reduce a matrix to the form $G = [I|-B^T]$ but I just cannot get my solution to match the solution in my notes. I am reducing it Mod 3 as it is part of a coding theory question. So my ...
0
votes
0answers
19 views

Reducing generator matrices for the codes $N_5(3,5)$ and $N_5(3,5)^\perp$ to a standard form $[IB]$ or $[BI]$

I am just covering a chapter on MDS codes and am attempting a question but not getting the same solution as in the notes. Here is the question: Write out the generator matrices for the codes ...
0
votes
1answer
31 views

a question about entropy of run length coding

I'm doing an exercise from chapter two of $\textit {elements of information theory}$. Here is the problem and its solution, . I'm not very clear about the equation 2.36 or say why does the equation ...
1
vote
0answers
28 views

Latin Squares and Olderogge Code

So I have two Latin Squares, $A$ and $B$ that form a pair of MOLS of order $m$. I then have an Olderogge code formed from $A$ and $B$, where each binary vector of length $m^2$ is encoded as a codeword ...
0
votes
1answer
47 views

Different BCH code between encoder and decoder

I am searching for the mathematical properties of the BCH codes that could explain that if I encode a message with a BCH defined by $(m=6,n=63,k=24,t=7)$, I can decode that message correctly with ...
0
votes
0answers
25 views

Sum of Coding rates of encoders accessible by decoder must be at least “h”, in order for “r” to be admissible. How?

Let we have one source with information rate "h" and 4 encoders with information rate r1, r2, r3 and r3 and r=[r1...r4]. Following conditions are necessary for r to be admissible. How? r1+r2 >= h ...
1
vote
2answers
71 views

How to represent a number in such a way that no more than 2 consecutive digits are the same?

The idea is to lower the probability of transcription errors when a person is reading the number on a paper and typing it on a computer, for instance. I'd be more interested in Base-58 notation, but ...
1
vote
1answer
16 views

Why Are The First and Last Entries of a Binary Reflected Gray Code Sequence Adjacent?

Some Information on Gray Codes If you're rusty or unfamiliar with Binary Reflected Gray Code, but want to try and help, here is a youtube tutorial explaining what they are: ...
1
vote
1answer
38 views

Bioinformatics meets Combinatorics. How to find a subset in a combinatorial problem?

I’m having a bioinformatics related problem. Let me walk you through it: The DNA base ambiguity code can be represented by 15 letters, where each codes for a different subset of DNA bases therefore ...
2
votes
0answers
39 views

Shortened Reed-Solomon proving p(D) is primitive

Assume we have a shortened $(n=18, k=12, t=3)$ Reed Solomon code in $GF(2^{8})$.Let $\alpha$ be a primitive element of $GF(2^{8})$. Consider the primitive polynomial given by: $p(D) = D^{8} + D^{4} + ...
1
vote
1answer
60 views

kind of mathematical puzzle

i was recently doing this problem--- problem statement You have r red, g green and b blue balloons. To decorate a single table for the banquet you need exactly three balloons. Three balloons ...
1
vote
0answers
30 views

Show a binary code does not exist. [duplicate]

Show that there is no $(6,9,3)$ binary code. I'm pretty sure the way to tackle this problem is to deal with it's generator matrix and then get a condradiction. However I seem to be getting no ...
0
votes
0answers
30 views

hamming weight of error correcting codes and BCH codes

In general the hamming weight of codewords of error correcting codes is well understood. If I were to write down the $k \times n$ generator matrix, with the span of the rows corresponding to the ...
3
votes
2answers
54 views

ISBN check digit

a ISBN-10 has 10 digits. The correctness of the last digit, the check digit, can be verified using the following formula: $$(x_1 + 2x_2 + 3x_3 + 4 x_4 + 5x_5 + 6x_6 + 7x_7 + 8x_8+9x_9+10m) \text{ mod ...
1
vote
1answer
51 views

Use a parity check matrix for Ham(4,2) and syndrome decoding

I have a coding theory question which I am confused about: Use a Parity check matrix for Ham(4,2), with the columns in lexicographical order, and syndrome decoding to decode a.) 00000 00000 11111 ...
0
votes
1answer
79 views

Weights of Binary Linear Code

I was looking at this problem related to coding theory: How do we know a linear code have even weight? Can anyone explain how we know either all codewords have even weight or half the codewords have ...
0
votes
2answers
29 views

Linear Code Problem, Weight & Minimum Distance

Please the highlighted part in the image below. I don't understand why w(c2) must be larger than s(c1, c2) considering s(c1, c2) is counting the position where c1 + c2 = 0, c1 != 0 and c2 != 0 while ...
1
vote
0answers
84 views

Latin square code dimension

I am need to understand what is the dimension of the code generated by the Olderogge Encoding: Given two mutually orthogonal latin squares, the encoding of a message of $m^2$ bits is: the message ...
0
votes
1answer
38 views

Calculating the information per symbol of a markov chain source

I have a 4-state 2nd order markov chain source with symbols 0 and 1. I have all the transition probabilities and have worked out the probabilities of each state. How do I go about finding the amount ...
0
votes
0answers
22 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
48 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
69 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 ...
0
votes
1answer
51 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
22 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
33 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
39 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
25 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
28 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 ...