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

learn more… | top users | synonyms

0
votes
0answers
7 views

Frobenius Finite Rings/ Modules Isomorphism

So, i have some issues, and maybe someone can help me. A Finite Frobenius Ring is a Ring $R$ such that: $_RR\simeq {_R}\hat{R}$ (As R-Modules) Where ${_R}\hat{R}$ is the Module of Characters For ...
0
votes
1answer
21 views

finding the error pattern from the syndrome

If the parity check matrix is $$ \begin{matrix} 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1\\ ...
0
votes
1answer
30 views

Hamming distance of a CRC

How do you calculate the Hamming distance of a CRC generator ploynomial? for example if they say that the generator polynomial has a hamming distance of 3, for a given data length, how is it ...
0
votes
0answers
18 views

Converting Walsh coefficients to values of a function

I assume I know the Walsh coefficients of a function f: $\mathbb{F}_{2^n}$ to $\mathbb{F}_{2}$. Is there any efficient possibility to get the values of the function f ?
0
votes
0answers
25 views

Finding Distinct Generator Matrices

C is a binary linear code C = {00000000, 01101111, 11011000, 11111101, 10010010, 00100101, 01001010, 10110111} I am trying to find two distinct generator matrices for C. I understand that generator ...
0
votes
0answers
43 views

Coset proofs for Binary Code

Can someone please help with the following proof: C is a binary [n, k, d]-code. Suppose d ≥ 2t + 1. Show that every word of weight ≤ t is a coset leader in every Slepian array for C. So i know n = ...
1
vote
1answer
33 views

Parity check Matrix for Plotkin construction of linear codes

Let's say I have 2 linear codes, $C_1 = [n,k_1]$ and $C_2 = [n,k_2]$, and I have the parity check matricies $H_1,H_2$ for them. I use the Plotkin construction to create the code $C$ out of them (for ...
0
votes
0answers
16 views

How can it be shown that $d \leq n-k+1$ in a $[n,k,d]$ linear code?

Assuming I have a $[n,k,d]$ linear code, how can it be shown that $d \leq n-k+1$ ?
1
vote
0answers
15 views

Hamming code Ham(2,11) fixing transposition of letters

Let's say I am using the $Ham(2,11)$ code - the hamming code for which r = 2 and q=11 (length of alphabet). Can I detect errors caused by the transposition of 2 letters? If not, why?
1
vote
0answers
8 views

How do you determine the number of errors in the Welch-Berlekamp method for decoding Reed-Solomon codes?

I asked this question on cs.stackexchange, but the community appears to be very small and I got no response. In the Welch-Berlekamp algorithm for decoding Reed-Solomon codes, one is given a list of ...
0
votes
1answer
23 views

Reed Solomon Encoding

I am trying to understand how Reed Solomon encoding works. Specifically, I am trying to re-generate the example shown in http://www.mathworks.com/help/comm/ref/integerinputrsencoder.html and check if ...
2
votes
1answer
32 views

Finding the Irreducible polynomials which are primitive as part of Coding theory course

I am taking a coding theory course where we have to be able to work out which polynomials over a field $\mathbb F_q$ are irreducible or reducible and then which of the irreducible ones are primitive. ...
2
votes
1answer
24 views

Determining if a code can be perfect

I am trying to answer the following short question: Consider a code $C$ of length 9 over an alphabet of size 6 with minimum distance 5. What is the upper bound of the number of codewords in $C$? ...
0
votes
2answers
44 views

When decoding a block code, how do you know which error a syndrome corresponds to?

I'm working with forward error correcting block codes such as Hamming(7,4) and Golay(23,12). I'm quite new to this field, so there are some things that I don't yet understand. I chose these codes ...
0
votes
1answer
19 views

Bit Error Probability, Binary Symmetric Channels

Here's the problem as it has been posed to me: Suppose a message sent through a binary symmetric channel with probability $p_1$ that a symbol is transmitted incorrectly. The received symbol is ...
0
votes
0answers
13 views

Resizing LDPC Parity Matrices

I am having a hard time trying to understand different optimizations for LDPC codes. Most important, I am finding it hard to understand how to compare different codes, given their lengths. For ...
0
votes
1answer
38 views

How would I find the Field's elments generator?

Suppose we would construct a Field $F=GF(2^4)$ by using $f(x)=x^4+x^3+x^2+x+1$. In this case the generator is $\alpha=x+1$. Why $\alpha$ here is equal to $x+1$ how would I find this?
1
vote
1answer
48 views

Verifying orthogonality between two binary sequences

I have studied that for orthogonality to exist between two binary sequences: [Number of bit agreements - Number of bit disagreements]/sequence length=0 Eg, for an orthogonal matrix X given by: ...
0
votes
0answers
21 views

Proofing among Coding Theory

Prove that if a code C can correct up to t errors in any codeword, then d(C) ≥ 2t + 1. So i understand that this therefore means if we know how many errors a code can correct, then we can determine a ...
2
votes
1answer
33 views

Coding Theory - Probability that word received has distance of at most 1?

Suppose the codeword x = 101101 is transmitted over the binary symmetric channel, with symbol error probability p. What is the probability that the word received has distance at most 1 from x? ...
1
vote
1answer
32 views

Distances within Coding Theory

Can someone please explain the following proof: that if $u$, $v$ are sequences of length $n$ over any alphabet such that $d(u, v) = a + b$, then there always exists a sequence $z$ such that $d(u, z) ...
2
votes
0answers
28 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
19 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
22 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
51 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
18 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
27 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
31 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
63 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
31 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
vote
2answers
43 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
33 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
62 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
35 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
38 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
40 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
22 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
24 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
25 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
105 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
168 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
39 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
62 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
47 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
41 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
33 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
45 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 ...