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

learn more… | top users | synonyms

2
votes
0answers
20 views

Words having weight near to minimum distance

I am studying the NP-Problem of the codes Syndrome Decoding. The formulation is show below. Input: a binary matrix $H$ of dimension $r \times n$ and a bit string $S$ of length $r$. Property: there ...
0
votes
1answer
16 views

Weight of words in Binary Reed-Muller code

Assuming we construct a $(2^m, 2^{m+1}, 2^{m-1})$ Reed-Muller code from the $(4,8,2)$ even-weight code and the $(4,2,4)$ repetition code, how many words will there be of each weight?
0
votes
1answer
21 views

What are instantaneous code words?

I need help understanding what instantaneous code words are. Example: Design an instantaneous code of length 3,2,3,2,2 2 00 2 01 2 10 3 100 Is my solution ...
1
vote
1answer
49 views

Rate calculation for sparse coding (significance coding)

How can I establish the approximate equality below? Let $M \ll N$ be the number of significant coefficients that is coded with $\log N$ bits. There are $\binom{N}{M}$ different sets of $M$ ...
3
votes
0answers
16 views

Maximum size of abandonable codes

Consider a keypad which accepts fixed-length numeric sequences from $b$ symbols and maps them uniquely to a set of actions. What is the largest set of actions which can be mapped for a given length of ...
0
votes
1answer
26 views

Lempel-Ziv-Welch Encoding of single character sequence

So I have this typical exam question: Consider an LZW coder for an alphabet with 32 symbols (thus represented by 5-bit symbols) using a dictionary of size 256 (thus indexed by 8-bit words). The ...
1
vote
1answer
27 views

What happens when both nodes of a tree have the same weight while constructing a Huffman code?

In figure 1.21, e and n2 have same weight. Why do we put ...
1
vote
1answer
29 views

How are codes assigned value in Shannon Fano Coding?

I am trying to understand how Shannon Fano Codes are being assigned values in the following example. Please help me understand it.
1
vote
0answers
57 views

Trellis Diagram - Viterbi decoding

I have the trellis diagram below which is used as Viterbi decoder. The coded message is the sequence of bits at the bottom of the picture. My question is this. t=0:The decoder starts from state 00 ...
1
vote
1answer
30 views

How original RS codes and the corresponding BCH codes are related?

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 ...
-1
votes
0answers
20 views

Coding theory using magma-cas

Blockquote Let F={a_1,..,a_q} a field with q elements and C={(f(a_1),..,f(a_q),f_{k-1}) : f in F[x], deg(f)'<'k}, where f_{k-1} is the coefficient of x^(k-1) in f. Find minimun distance, ...
1
vote
2answers
38 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
23 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]. ...
3
votes
0answers
60 views

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
29 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
20 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
36 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 ...
2
votes
1answer
37 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
19 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
23 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
20 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
98 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
152 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
34 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
53 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
45 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
40 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
31 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
43 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
16 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
25 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
39 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
18 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
42 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
32 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
29 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
28 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
73 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
35 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
34 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
12 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
34 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
38 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
24 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
43 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
50 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 ...