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

learn more… | top users | synonyms

1
vote
0answers
19 views

How to find orthogonal vectors in GF(2)

I've 13 rows in a matrix, which are linearly independent.(number of columns is 20), in GF(2). Now i have to find 20 orthogonal vectors in GF(2). I've added 20 more rows which are the rows of an ...
0
votes
0answers
11 views

generating orthogonal parity check matrix, from a random generator matrix

I have a matrix G of dimension 13x20. It is a full rank matrix. It is not in the standard form of a generator matrix. Now for the parity check matrix 'H', I need a standard representation H=[-P;I]. ...
2
votes
0answers
44 views
+50

LDPC encoder with rate 3/4

If an LDPC encoder with code rate 3/4 was used and parity check matrix of dimension $H=168$ rows $\times 672$ columns is used, is it correct to say that the maximum number of information bits in each ...
1
vote
0answers
21 views

Cyclic Redundancy Check of an input sequence using MATLAB

I understand how to mathematically calculate the cyclic redundancy check CRC of bits, for example if the CRC is of length 16 $$ CRC(D) = (M(D) + I (D)) D^{16} \,\,\, mod \,\,\,\ G(D)$$ where $M(D)$ ...
2
votes
0answers
14 views

Question about periodic points in shift spaces

Let $A$ be a finite set endowed with the discrete topology. Then, the pair $(A^{\mathbb{Z}}, \sigma)$ is said to be the full shift over the alphabet $A$ where $A^{\mathbb{Z}}$ is endowed with the ...
0
votes
2answers
31 views

Application of Reed Solomon codes

In an example I read in technical paper that used ReedSolmon Codes. I encountered the following statement: Using an outer RS(224,208) reed solomon block code and if the length of data TO BE encoded ...
1
vote
0answers
22 views

FSR function of the component-wise product, sum, of two LFSR sequences

Let $T_1$, $T_2$ be two $m$-sequences over $\mathbb{F}_q$ of length $q^n-1$, say $T_1 = (\text{Tr}_{q^n | q}(\alpha^i))_{i \geq 0}$, $T_2 = (\text{Tr}_{q^n | q}(\beta^i))_{i \geq 0}$, for some ...
0
votes
1answer
16 views

General Questions regarding LDPC codes

I am currently learning LDPC codes, I have the following general question regarding LDPC codes, 1) when encountering a term such as LDPC$(672,504)$ are we referring to the code rate or the matrix ...
0
votes
1answer
22 views

Smallest odd $n$ for which there exists a proper linear cyclic code of dimension $5$

Find the smallest odd value of $n$ for which there is a proper linear cyclic code of length $n$ and dimension $k = 5$. For a proper code, $k < n$. So $n \geq 7$. My notes say we need a proper ...
0
votes
0answers
18 views

An application of LDPC codes

The following problem is an application of LDPC codes in communication system that I encountered and I am trying to verify if it is correct, as there is no explanation given within the text. A ...
3
votes
1answer
91 views

Fun/Frustration With Coding Coding Theory

it's time for practical coding theory. I am trying to write a simple program that will detected if a given binary code word is "correct" or not. If it is not correct, I want to detect/correct (since ...
2
votes
2answers
145 views

Why is math so difficult for me? [closed]

I'm an aspiring software engineer and currenly in college for computer science. For some reason, no matter what I try, math is so unbearably difficult and indecipherable until I design a program for ...
1
vote
0answers
31 views

Finding a check polynomial for a cyclic code

I'm trying to solve the following problem: $C$ is a binary cyclic $[7,4]$ code with generator matrix $$ \begin{pmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 1 ...
1
vote
1answer
46 views

How secure is a generated 8 digit code that can be cross referenced to see if its valid?

I'm in the middle of creating a website that basically hands out codes. Each code is 8 digits long. Each digit can be any of the following: 0-9 numbers 26 lower case alpha 26 upper case alpha ...
0
votes
1answer
51 views

Given a biased coin $P(X=0)=.75$, can someone show me a compression scheme that beats 1 bit

Given a biased coin $P(X=0)=.75$, I've been unable to find a coding scheme which beats the identity code of $0\to0$ and $1\to1$, which of course is an efficiency of 1 bit per transmission. The ...
3
votes
1answer
43 views

Are there any applications of checksums and/or cryptographic hash functions in pure mathematics?

Are there any applications of checksums and/or cryptographic hash functions in pure mathematics? I've tried Googling this and haven't found anything. If you've got any other application of ...
0
votes
1answer
37 views

ternary cyclic codes of length 27

With $k = 1,2,3,\ldots,26$, is it possible to find a ternary cyclic code of length $27$ and dimension $k$? How can i show that it exists - if it does?
0
votes
0answers
30 views

Building a generator matrix

given $g(x) = (1+x)(1+x+x^3) \in F_2[x]$ as the generator polynomial of a binary (7,3)-code, I am trying to construct a generator matrix (of the form $(I_3|A)$ ) and parity check matrix. Below is my ...
1
vote
1answer
38 views

Number of (binary) cyclic codes of length 21

what are all the binary cyclic codes of length $21$? Is it possible to find all values of k for which $[21,k]$ is a binary cyclic code? How do i go about this problem, does finding the cyclotomic ...
0
votes
0answers
15 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
21 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
38 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
17 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
17 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
30 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
26 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
23 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
23 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
71 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
31 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
33 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
10 views

$(n,m,d)-$code Hamming bound

I have the $(n,m,d)-$ code $(6,4,4)$ which can clearly be constructed $$\begin{pmatrix} 000000 \\111100 \\ 001111 \\ 110011 \end{pmatrix}$$ However, if i try using the hamming bound on $m$ i have, ...
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
37 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
34 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
29 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
49 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
37 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
48 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
40 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
76 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
25 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
49 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
14 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
19 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$. ...
1
vote
0answers
19 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 ...