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

learn more… | top users | synonyms

2
votes
2answers
54 views

Basic irreducible polynomial

I'm studying cyclic codes over a ring $R$. It is well known that a cyclic code over $R$ of length $n$ is an ideal of $R\left[ x \right]/\left( {{x^n} - 1} \right)$. Hence the factorization of ...
1
vote
1answer
28 views

Source coding and Entropy

Hell people, I have a small question I came by , but I am not quite sure about the right approach to it. Suppose that we have a source that transmits 5 symbols. We have two cases. When all ...
2
votes
1answer
29 views

Check entry extended ternary Golay code

The extended ternary Golay code is the linear $[12,6,6]$-code with the following generator matrix: $$ C=\left( \begin{array} &1&0&0&0&0&0&0&1&1&1&1&1\\ ...
1
vote
1answer
34 views

Calculate Huffman code length having probability?

Having an alphabet made of 1024 symbols, we know that the rarest symbol has a probability of occurrence equal to 10^(-6). Now we want to code all the symbols with Huffman Coding. How many bits ...
0
votes
1answer
31 views

Modulation and translation properties of DFT

Consider the discrete fourier transform over a finite field $GF(q)$. Let also $\omega$$\in$$GF(q)$ be an element of order $n$ and which is an $n$-th root of unity. Definition 1. Let $v$ = ($v_0$, ...
3
votes
0answers
34 views

Extending generator matrix in coding theory

I have an $m \times n$ matrix $M$ where $m < n$ over finite field of size $2^w$. This matrix has the property that every $m \times m$ matrix formed by a $m$-subset of its columns is invertible. Is ...
2
votes
0answers
44 views

Shannon-Fano analysis, Binary-search-like

Prove that the codewords of the Shannon-Fano code satisfy $l_i \leq \left \lceil \log _2 \frac1{p_i}\right \rceil$. Elementary wording: given positive numbers in descending order $p_1,...,p_n$, ...
0
votes
1answer
47 views

Berlekamp Massey and DFT

I was looking into the Berlekamp Massey algortihm, for LFSR, over GF(2) wondering if there was any DFT(alternately FFT), for the above scheme. Also, is there any generalization to Fn, ie, start ...
0
votes
1answer
32 views

How do we know a linear code have even weight?

In coding theory, How do we know a linear code have even weight? For example, we have a linear code (12,3,6), how to identify each word of it get even weight?
0
votes
0answers
28 views

Counting the 1s in each row of the incidence matrix of a 2-design

Consider the $2 - (4t-1, 2t, t)$ design where $t$ is an odd number and $A$ is the incidence matrix. I suspect that the number of elements with value $1$ in each row of $A$ is equal to $2t$ but I can't ...
2
votes
1answer
68 views

Is there a combinatorial explanation for this identity related to Kraft's inequality?

Kraft's inequality involves the quantity: $$\sum_{x \in X} \frac 1 {b^{\ell(x)}} \tag 1$$ Where we are considering a code mapping symbols in the alphabet $X$ to strings in an alphabet of $b$ ...
0
votes
1answer
17 views

Unclarities on Adaptive Huffman Code

I'm trying to code a simple string abbcccad. I started with: Computing the "valor" of each letter. Ordering them by their valor. Adding the last 2 of them ...
0
votes
0answers
24 views

Studying a code in cryptography

So,i'm given a binary code $C$ with it's generator matrix $G=(A,B)$ where $A,B$ are given matrices. The task is to study the code. First question: What does this form $(A,B)$ mean? how would $G$ look ...
0
votes
0answers
29 views

What connections between computer science and ergodic theory?

I have a background in ergodic theory, but I am switching to computer science/programming. I would like to know if tools from ergodic theory could be useful, especially something around coding of ...
2
votes
1answer
52 views

Linear $f\colon \mathbb{F}^t \to \mathbb{F}^s$ injective on any ball of radius $\epsilon t$?

This may be well-known or trivial, but I cannot find any relevant pointer on the subject. Let $t\geq 1$ be an integer, and fix $\epsilon\in(0,1)$. I would like to find an integer $s=s(t,\epsilon)$ and ...
1
vote
1answer
28 views

Uniqueness of Hamming Code up to parameters.

"Show that the Hamming code $H_r$ is unique, i.e. any linear code with parameters $[2^r − 1, 2^r − 1 − r, 3]$ is equivalent to $H_r$." I see that Hamming codes are perfect and packs the whole space, ...
11
votes
3answers
156 views

Deducing correct answers from multiple choice exams

I am looking for an algorithmic way to solve the following problem. Problem Say we are given a multiple choice test with 100 questions, 4 answers per question (exactly one of those four being ...
0
votes
1answer
23 views

Finding Minimum Hamming Distance From Zero

Can anyone give me a shor explanation why in this picture, they started of the last 0 from first vector and why what is noted with a is 8? ...
1
vote
0answers
28 views

Good low-rate, short-length block codes

I am highly unsure whether this question is appropriate for this site (as it is at no point a math problem), yet searching in the stackexchange universe for similar topics showed the most hits on ...
0
votes
1answer
27 views

A few detection and correction questions

I need a bit of help with error detection and correction. We have: C = {01010101, 10101010, 00000000, 11111111} I need to: ...
1
vote
0answers
30 views

Squaring is linear in Galois Field 2

In the context of cyclic codes and BCH, consider the generation function of a codeword $c = [c_0 \ldots c_n-1]$ to be $c(x) = c_0 + \cdots + c_{n-1} * x^{n-1}$. Now, in the finite field $F_2[x]$, why ...
1
vote
1answer
43 views

Existence and construction of asymmetric codes

By a $[n,k]_2$-code I mean a $k$-dimensional $\mathbb{F}_2$-subspace of $\mathbb{F}_2^n$. Such a code $C$ admits a symmetry $\sigma \in S_n$ if for any word $w \in C$ we also have $w^\sigma \in C$, ...
2
votes
1answer
33 views

Hamming (7,4) and Parity Matrix

currently I am studying a few introductory things on Coding Theory but I have a small problem on understanding a few things. I really cant understand how can I create a Parity matrix for H(7,4) if I ...
4
votes
0answers
19 views

Decoding of Gabidulin code

Consider the space of matrices in $\mathbb{F}_q^{n \times m}$ where $\mathbb{F}_q$ is the finite field with $q$ elements. We can define a metric on this space, given by $d(A,B) := rank(A-B)$, called ...
4
votes
1answer
48 views

A question about optimal codes

Recall that a code attaining any bound is called an optimal code. Is the dual code of an optimal code also an optimal code?
0
votes
0answers
37 views

Generator polynomial for 16-ary [15, 11] Reed-Solomon code

I am trying to find a generator polynomial for a 16-ary [15, 11] Reed-Solomon code (elements are in $F_{16}$, codewords are length 15, message words are length 11), but I can't quite seem to figure ...
1
vote
1answer
53 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
1answer
55 views

How to build a generator polynomial for Reed Solomon code?

Go through all of the necessary steps to build a generator polynomial for a 3-error correcting 11-ary Reed-Solomon code of length $10$. How to go about this? Based on the formula, $(x−βl+j)$, what ...
3
votes
0answers
40 views

Huffman codes: does less entropy imply less weighted average codeword length?

Let $\Sigma$ be a source alphabet with a probability distribution over its symbols $P$. Then, the Shannon entropy of $\Sigma$ is $$-\sum p_j \times -\mbox{log}_2(p_j)$$ where $p_j$ is the probability ...
0
votes
1answer
30 views

Number of correctable symbol erasures in a code

In a code with distance $d$, the maximum number of correctable errors is $\lfloor \frac{1}{2}(d-1) \rfloor$. But apparently, the maximum number of correctable erasures is $d-1$. How come? Isn't an ...
0
votes
0answers
53 views

Describe all the cyclic codes of length $7$.

$V^7$ is the set of length $7$ codewords. $V^7[x] = \mathbb F_2[x]/ \langle x^7-1\rangle $. I know that each of these cyclic codes is constructed from a canonical generator (divisor of $x^7-1$). So ...
0
votes
0answers
38 views

Simple way to show the ideal $\langle 1+x \rangle$ in $V^5[x]$ corresponds to the code in $V^5$ with all words of even weight?

$V^5$ is the set of length $5$ codewords. $V^5[x] = \mathbb F_2[x]/ \langle x^5-1\rangle $. Show that the ideal $\langle 1+x \rangle$ in $V^5[x]$ corresponds to the code in $V^5$ with all words of ...
-1
votes
1answer
37 views

abandon a column, also $n$ different row vectors

$A$ is a $n\times n$ matrix, whose $n$ row vectors are all different. then, we can get rid of one column of $A$(there exist a column, we abandon this column ), such that the new $n\times (n-1)$ ...
0
votes
1answer
41 views

Show by arithmetical arguments that there cannot be a perfect binary code of length $n$ which corrects $e$ errors.

Show by arithmetical arguments that there cannot be a perfect binary code of length $n$ which corrects $e$ errors when: (i) $n=5,e=1;$ (ii) $n=10,e=2;$ I'm not sure I understand what a perfect code ...
0
votes
2answers
52 views

Covering Radius of linear code

Covering Radius of a linear code: Show that if C is a linear [n, k, d] code over a finite field $F_{q}$, then R ≤ n − k.
1
vote
1answer
49 views

A question of algebraic geometry applied to field theory

I’ve come across this question in a coding theory course, and it has stumped me. Any hints and/or suggestions would be appreciated. Let $F$ be a field (for our purposes, assumed to be finite of ...
0
votes
0answers
35 views

Group action of $G<\mathbb Z^\infty_2$ over the Golden mean shift

I'm am looking for an action of an infinite subgroup of $\mathbb Z^\infty_2$ over the golden mean shift space $$X=\{x\in \{0,1\}^\mathbb N : x_i=1\Rightarrow x_{i+1}=0\}$$ such that any element of $G$ ...
1
vote
1answer
35 views

enumerator weight polynomial of Golay code

Let $C$ be a code and let $X_{i}=| \lbrace x\in C : w(x)=i \rbrace|$, where $w(x)$ denotes the weight of $x\in C$. I would like to know how to compute the numbers $X_{i}$, in the particular case where ...
2
votes
0answers
68 views

From Shortened Code to Reed Muller code

[Ok people, before scolding me, let me tell you this thing is giving me headaches..] I have a $C$ = $C(8,3)$ described by this matrix: $$G=\begin {bmatrix} ...
0
votes
1answer
39 views

Question on Hamming distance

Let V_n be n-dimentional vector space over GF(q). E is k-dimentional vector subspace which is a linear q-ary (n,m,d) code and also consider the radius e = [(d-1)/2]. Assume that E is not a perfect ...
0
votes
1answer
54 views

Perfect code and even minimum distance

I am reading up on perfect code and there's a statement that puzzles me a bit: We remark that the extended Golay code is not perfect (and indeed cannot be because d is even!) This makes me ...
0
votes
0answers
37 views

Maximizing variance of Hamming distance of a system

I have a system as shown below, where 4 registers have 8 bit input A,B,C,...
2
votes
1answer
47 views

puzzle on [13,10,3] perfect Hamming code over $\mathbb F_{3}$

The soccer betting form contains a list of 13 games. There are three possible outcomes for each game: “the first team won”, “the second team won” and “draw”. Each betting form allows to chose one ...
2
votes
1answer
71 views

linear binary code problem

Let $\mathcal C$ be a $[n,k,d]$ linear binary code such that $\mathcal C$ has a systematic generator matrix $G=[I_k\mid A]$. (i) Prove that $u\in (\mathbb F_2)^k$ is coded by $c=(u\mid uA)\in ...
1
vote
0answers
66 views

Shortened Generator Matrix

goodmorning, could someone tell me if the following code has been handled correctly? I have this generator matrix (which I should modify in order to have it correct): $$G=\begin {bmatrix} ...
1
vote
2answers
84 views

Fano's inequality and error rate

The Wire-tap channel II (http://link.springer.com/chapter/10.1007%2F3-540-39757-4_5) article in proof of Theorem 1 uses Fano's inequality to estimate the entropy $H(S|\hat{S}) \leq K \cdot h(P_e)$ ...
1
vote
0answers
60 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 ...
2
votes
1answer
40 views

counting vector pairs with a given hamming distance

Let $\mathbb{F}_2$ denote the binary field. For integer $t\geq 0$, define $W_t = \{(x,y)\in \mathbb{F}_2^n\times \mathbb{F}_2^n: d_H(x,y)=t\}$, where $d_H(\cdot,\cdot)$ denotes the Hamming distance. ...
1
vote
1answer
37 views

Number [n,k]-linear codes with one fixed vector

I need to find the number of $[n,k]$-linear binary codes with one fixed codeword x (non zero) in it. So I guess, I need to count the number of $k$-dimensional ...
5
votes
0answers
58 views

Maximal hamming distance

Here is a combinatorial problem : let $\Sigma=\{\alpha_1,\ldots,\alpha_n\}$ be an alphabet and we consider any words over $\Sigma$ of length $n$. We also define over the set of such words the Hamming ...