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

learn more… | top users | synonyms

0
votes
0answers
8 views

Constructing binary codes and n-bit words of given length over given finite fields.

Given $(x_1,x_2,...,x_n)\in\Bbb F_{2}^n$, how can I construct a linear binary code $C$ of length $l$. Then construct a $y-bit$ code word $\in C$? Then later on generate a parity check matrix and a ...
0
votes
0answers
18 views

Constructing a ternary (n,M,d) code

We have ternary (3,9,2) code called $C$. I know that such a code does exist. What I have trouble with is writing down all the code-words of $C$. I know that the first two digits in each code-word can ...
1
vote
1answer
30 views

Code-word length of given maximal length

If the maximum allowable code-word length is $672$ bits and assuming we are using an LDPC parity check matrix with rate $1/2$, $3/4$, what is the maximal number of data bits in each LDPC code-word? ...
1
vote
1answer
10 views

How many binary vectors of weight 3 can you have before their span contains one of weight 2?

In other words, I am looking for the smallest $k$ for which the following is always true: Let $v_i \in \mathbb{F}_2^n$ for $i = 1\ldots k$ be distinct vectors of Hamming weight 3, that is, vectors ...
1
vote
0answers
13 views

LDPC codes general question

Today I was reading wireless communication book chapter about coding. I have little knowledge in coding. So I ask for help in the following paragraph. For the encoding, a low-density parity check ...
1
vote
0answers
16 views

Complementary Golay sequences and sum of their autocorrelation function

Golay complementary sequences are aperiodic sequences made up of +1 and -1 that have nice property which is that their autocorrelation that sum up as korneckr delta function. Example $G_{a4}=(+1, +1, ...
1
vote
0answers
21 views

How to calculate the Cyclic redundancy check CRC given an input sequence?

In digital communications a cyclic redunduncy check CRC is an error detecting code that are used to protect a number of given bits similar to concept of parity bit. I have included a picture of block ...
0
votes
1answer
22 views

Number of different cycles in cyclic codes with length n

I am studying Information theory, coding theory in particular at the moment, and I am having trouble determining how many different cycles are defined by a certain generator polinomial? Given a ...
0
votes
0answers
18 views

Determine the Minumum Distance using the Minimum Distance Theorem for Linear Codes

Let $C$ be a linear code over $\Bbb{F}_2=\{0,1\}$ with generator matrix $$G= \begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 ...
1
vote
0answers
18 views

Most efficient method for constructing a linear code with large minimum distance

I have a problem in which I can estimate the minimum distance needed for my linear code to be quite large, around 400-500. I also have a target k value of $k=32$. The value for n is flexible by design ...
1
vote
0answers
65 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
26 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
29 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
32 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
33 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
15 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
27 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
28 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
46 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
34 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
35 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
70 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
19 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
42 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
22 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
32 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
29 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
51 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
26 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
62 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
31 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
56 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
52 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
81 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
31 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 ...