1
vote
1answer
14 views

When Errors Go Undetected in CRC

I understand that CRC will not be able to detect errors if: The remainder of $E(x) / G(x) = 0$ $E(x) = G(x).Z(x)$ for some polynomial $Z(x)$ I understand the first point, which means that if the ...
5
votes
2answers
89 views

Efficiently factoring polynomials over $\Bbb F_2$

I am attempting to write some software which is intended to generically answer the question of which Cyclic Redundancy Code (CRC) generating polynomial is used for a given set of sample messages using ...
1
vote
1answer
57 views

Choosing a polynomial for CRC

CRC checksum is a homomorphism from polynomials over $\mathbb F_2$ to itself. As I understand, the map $f\mapsto g$ it is simply remainder from division $f$ by $p$, where $p$ is a fixed polynomial for ...
1
vote
0answers
64 views

Extension field of F2 , expressing roots and primitive elements in that field

Let $\Phi$ be an extension field of $\Bbb{F}_2$ of extension degree s >1. Let $a(x)$ be a non-zero polynomial with the coefficients in $\Bbb{F}_2$. (a) Show that if $\beta$ is a root of the ...
0
votes
0answers
37 views

Reed-Solomon encoding in GF2?

I'm vaguely familiar with Reed-Solomon encoding + know that it's generally done in GF(256). Is there any way to use GF(2)? If I have a hardware LFSR (as is used for CRC calculation), can I make use ...
1
vote
1answer
38 views

Cyclic Codes over $GF(q)$

Does the set of cyclic codewords / codeword polynomials themselves form a field ? I think they donot because the modulo operation is with respect to $x^n-1$ which is not a prime polynomial. Also the ...
1
vote
1answer
163 views

Discover parameters of a Reed-Solomon code from its output

chirp.io is a site/app for sharing e.g a photo identified by a short FSK audio chirp. The chirp is 10 symbols of data, then 8 symbols of error correction. Thes symbols are 32-valued (5 bits/symbol) ...
0
votes
1answer
36 views

Given a syndrome $wH$, $GF(2^4)$ and $\beta$ (class of $x$), determine if $d(v,w) \leq 2$ for some $v$ in a BHC code $C$

I would like to know what is the best way to do that manually. Consider the following case: $GF(2^4)$ is constructed as $K[x]$ modulo $1 + x + x^4$. $\beta$ is the class of $x$ so $1 + \beta + ...
2
votes
1answer
38 views

Prove that for two vectors x,y over GF(q), the number of vectors that are closer to x is the same as the number of vectors that closer to y.

Let $x,y\in\mathbb F_q^n$ be vectors. We'll define: $X= \{ u\in\mathbb F_q^n \mid d(x,u)<d(y,u)\}$ $Y= \{ u\in\mathbb F_q^n \mid d(y,u)<d(x,u)\}$ Prove that $|X|=|Y|$. Well. ...
6
votes
3answers
57 views

Find the minimal $n$ such that there exists $[n,n-5]$ cyclic binary code with generator polynomial $g(x)=1+x^4+x^5$

Find the minimal $n$ for there exists $[n,n-5]$ cyclic binary code with generator polynomial $g(x)=1+x^4+x^5$. I couldn't figure out the answer. The only way I could think of is find out all the ...
2
votes
1answer
279 views

Structure of Parity Check Matrix of Non-Systematic Tensor Product Codes

Let $[n_i,k_i,d_i]_q$ for $i=1,2,\dots,r$ be a set of $r$ non-systematic linear codes over $\Bbb F_q$ with $k_i \times n_i$ generator matrix $G_i$ each and $n_i \times (n_i - k_i)$ parity check matrix ...
1
vote
2answers
441 views

Why should we append zeros during CRC calculation?

Say we have M as message bits , why do we need to append r-zeros to M message bits before performing the division to obtain r-bit checksum. Why don't we directly perform the division on the M message ...
1
vote
1answer
42 views

a codeword over $\operatorname{GF}(4)$ -> two codewords over $\operatorname{GF}(2)$ using MAGMA

A codeword $X$ over $\operatorname{GF}(4)$ is given. How can I write it as $X= A+wB$ using MAGMA? where $A$ and $B$ are over $\operatorname{GF}(2)$ and $w^2 + w =1$. Is there an easy way, or do I have ...
2
votes
2answers
160 views

The linearity of the extended code

If we add a last digit to the code $C$ of length $n$, we obtain a new code called extended code. My question is: If the code $C$ is linear, can we prove that the extended code $C'$ is linear too? ...
1
vote
1answer
95 views

extended linear codes over the field $\mathbb F_q$

Suppose we extend the $[n,k]$ linear code $C$ over the field $\Bbb F_q$ to the code $C'$, where $$ C' = \{(x_1,\ldots ,x_n,x_{n+1})\in \Bbb F_q^{n+1} : (x_1,\ldots,x_n) \in C \text{ and } ...
8
votes
3answers
345 views

Using Hensel's Lemma to Factor a Polynomial over $\mathbb{Z}_4[x]$

We recently learned about codes over $\mathbb{Z}_4$, and Hensel's Lemma. The lemma is as follows: Let $f(x) \in \mathbb{Z}_4[x]$. Suppose $\mu(f(x)) = h_1(x)h_2(x) \cdots h_k(x)$, where $h_1(x), ...
8
votes
1answer
214 views

Error correction code handling deletions and insertions

I have data which is expressed in form of fixed-length sequence of decimal digits, typically 10 digits in length. I'm looking for error correction code that would allow me to append one or more ...
2
votes
2answers
112 views

Encode the message $[1,1,0,1,1,0,1]$ in BCH code based on the field $\mathbb F = \frac{\mathbb Z_{2}[x]}{x^4+x+1}$

So here's what I understand so far: $\mathbb F = \frac{\mathbb Z_{2}[x]}{x^4+x+1} = GF(16)$ The code is written as $[x^{14},x^{13},x^{12},x^{11},x^{10},x^{9},x^{8}$ $|$ ...
1
vote
1answer
175 views

Efficient method to determine if a set of vectors span a finite field with some constraints on the constants.

In a finite field $\{0,1,2\}^2$, given a set of vectors $[0\:1],[1\:0],[1\:1],[2\:2]$, we can have the linear combination, $c_1[1\:0]+c_2[0\:1]+c_3[1\:1]+c_4[2\:2] = [s_1\:s_2]\in\{0,1,2\}^2$, where ...
0
votes
1answer
658 views

Reed-Solomon Code calculation

I have a Reed-Solomon Code which can correct t=2 errors. The generator polynomial is $p(X) = X^3 + X + 1$ and $p(a) = a^3 + a + 1 = 0$ this means $a^3 = a + 1$ What is the degree of generator ...
2
votes
2answers
121 views

irreducible , extension field, coding

The following is a theorem I am trying to understand. If $n$ is a positive integer and $m=2*3^{n-1}$ We know that $t^m+t^{m/2}+1$ is irreducible over GF(2). I am looking at the case when ...
2
votes
1answer
2k views

finding the LFSR and connection polynomial for binary sequence

I have written a C implementation of the Berlekamp-Massey algorithm to work on finite fields of size any prime. It works on most input, except for the following binary GF(2) sequence: 0110010101101 ...
4
votes
2answers
823 views

Factorize polynomial over $GF(3)$

I want to factorize $x^{11}-1$ over $GF(3)$ but I'm stuck at $(x-1)(x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1).$ I have tried to do it trial and error but failed. Is $$ ...
1
vote
0answers
698 views

Generator and char. polynomial for a binary Galois Field produced by an external-XOR LFSR

My question is regarding LFSRs (Linear Feedback Shift Registers), and the binary Galois Field produced by them (also commonly termed GF($2^n$) ). I understand that a given n-bit LFSR produces a ...
6
votes
1answer
217 views

Is correcting 2 consecutive error's in 9 messages from $ GF(2^6) $ by turning tham into 3 messages and solving Reed-Solomon code $ (3, 18) $ possible?

2 consecutive messages have errors. We have 9 messages from $ GF(2^6, x^6+x+1) $. Messages were encoded with $ (x+1)(x+a)(x+a^2)\sum_{i=1}^6X_ix^{i-1}=\sum_{l=1}^9Y_lx^{l-1} $ , where $ ...
1
vote
1answer
125 views

How to decode encoded, and corrupted in transmission message in Galois Field $2^5$ with one error?

We are given $GF(2^5, x^5+x^2+1 )$. We had some $ X_1, ..., X_5 $ message items from our $ GF(32) $ which we do not know and need to find. Thay were encoded via service blocks $ Y_1...Y_7 $ with next ...
9
votes
3answers
7k views

Addition and multiplication in a Galois Field

I am attempting to generate QR codes on an extremely limited embedded platform. Everything in the specification seems fairly straightforward except for generating the error correction codewords. I ...
1
vote
1answer
835 views

Question about LFSR

I am reading a paper and say this "The idea is to load $f(X)$ into LFSR to multiply by $X$ mod $g(X)$(primitive polynomial deg $g=n$). We next compute a polynomial h(X) whose coefficients are given ...
6
votes
2answers
5k views

Reed Solomon Polynomial Generator

I am developing a sample program to generate a 2D Barcode. And i am using reed solomon error correction code. By Going through this article i am developing the program. But i couldn't understand how ...
4
votes
2answers
793 views

Galois Field Fourier Transform

there are two definitions for Reed-Solomon codes, as transmitting points and as BCH code ( http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction ). On Wikipedia there is written that we ...
0
votes
1answer
109 views

Shifting an LFSR loop in O(1) time?

I'm looking for a way to mathematically combine two concepts: LFSRs, and Barrel Shifters I'm looking for a way, in O(1) time, to shift an LFSR loop a given number of shifts. What I'm hoping to find ...
6
votes
2answers
484 views

What requirements should a CRC polynomial satisfy?

What requirements should a CRC polynomial of a given degree satisfy to make the CRC catch a maximum of errors? edit I'm talking about GF(2) polynomials. As an example of the kind of requirements ...