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

learn more… | top users | synonyms

1
vote
1answer
35 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
1answer
15 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\}$
1
vote
0answers
30 views

Soccer betting in coding theory [on hold]

Problem 4.14(Ron Roth) A soccer betting form contains a list of 13 matches. Next to each listed match there are three fill-in boxes which correspond to the following three possible guesses: “first ...
0
votes
0answers
5 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
34 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
25 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
34 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
23 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
37 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
0answers
37 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
57 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} ...
0
votes
1answer
17 views

reed muller code with parameters

Although the details of the code are not given, use the code's parameters to determine how many errors the (32, 64, 16) Reed-Muller code correct. what does this exactly mean? HELP
0
votes
0answers
31 views

Can we find any relation between weight enumerator of code and dual code using graphs of both?

I have taken a code as input and calculated the dual code using MacWilliams' identity. Is there any way to relate the two using graph ?
1
vote
1answer
65 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)$ ...
0
votes
0answers
28 views

Parity check matrix operations

Let $C_1$ and $C_2$ be linear codes of the same length over the finite field $F$, and let $H_1$ and $H_2$ be parity-check matrices of $C_1$ and $C_2$ respectively. Define $C_3$ as the code $C_3 = ...
1
vote
0answers
41 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
34 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
28 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
50 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 ...
3
votes
1answer
42 views

Fermat Curve example and questions from coding theory.

I've been studying the basics of Algebraic Geometry for coding theory using the Pless-Huffman book. However since this is mostly self study, and without good resources I still feel a little shaky on ...
2
votes
1answer
40 views

Intersection Multiplicity and Multiplicity of Zeros in Polynomial

I study coding theory and we use the textbook Fundamentals of Error-Correcting Codes . In the section related to Algebraic Geometry Code, we need to compute Intersection Multiplicity of two curve in ...
1
vote
1answer
27 views

information and coding theory weakly independent problem

$X$ is weakly independent of $Y$ if the rows of the transition matrix $\begin{bmatrix}p(x|y)\end{bmatrix}$ are linearly dependent. Show that if $X$ and $Y$ are independent, then $X$ is weakly ...
3
votes
0answers
20 views

Hadamard and Golay sequences

Please can someone recommend a good introductory book that covers Walsh-Hadamard codes, and Golay complementary sequences (in particular in relation to their merit factors and other correlation ...
3
votes
1answer
44 views

Projective points of a Fermat Curve

This is a problem from my coding theory book which I am trying to wrap my head around. Consider the curve $f_3F(q)$ given by $x^3+y^3+z^3=0$ A) Find the three projective points (x:y:z) of $P^2(F_2)$ ...
4
votes
0answers
81 views

Coding Theory Problem to save Humanity

For starters, this problem doesn't originate from me, it's a friend's coding theory problem and I got interested, thinking about it, but I can't think of any as I only have very basic coding theory ...
-1
votes
0answers
47 views

Question related to algebraic coding theory

How to show that $\mathbb{F}(\chi)$is a field containing $\mathbb{F}$ as a subfield (where $\mathbb{F}$ is identified with the constant polynomial and $\chi$ is projective curve.)
1
vote
0answers
31 views

Upper bound for constant weight code L(n,d,w), with n=128, d=4

I would like to find an upper bound: L(n,d,w) <= f(n,d,w) for a constant weight code L(n,d,w), where w is the maximum weight, d is the Hamming distance between codes, and n is the code length. I ...
2
votes
0answers
65 views

Out of all combinations (n,k), largest set such that each combination overlaps with others by d or less.

This problem is relevant to determining the number of discriminable combinations of components in a sensory perception task. Suppose that there are N components to choose from, and we are only ...
1
vote
2answers
87 views

Parity check matrix and error syndromes

I have been asked to create a parity check matrix for a code made up of the codewords C=(0000,1110,1011,0101). I created a generator set {0101,1011} this set creates 1110 when the codewords in the set ...
0
votes
0answers
28 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
43 views

When is a minimum distance decoder also a maximum likelihood decoder?

It is well known that if we have a binary symmetric channel with crossover probability $\epsilon<0.5$ and we send a word $x$ through it, the most likely word is the one with minimum hamming ...
0
votes
1answer
25 views

Coding theory, rank metric codes

Let $S$ be a subset in $Mat_{k\times n}(\mathbb{F}_q)$ ($k\times n$ matrices with entries in $\mathbb{F}_q$) and $d(A,B)= rank(A-B)$, $dist(S)= \min\{d(A,B) \mid A,B \in S, A\neq B\}$ What is maximal ...
0
votes
0answers
27 views

Correctable bits

Consider the following codewords. What is the Max number of bits that are correctable? $00110011, 11110000, 00001111, 11001011$ I know there is a $C+D=M-1$ formula to use and if you line up the ...
0
votes
1answer
28 views

How many different $n$-bit Gray-code-like cycles are there?

The Question: How many different $n$-bit Gray-code-like cycles are there? It just needs some clarification: $i)$ The original $n$-bit Gray code is now considered as a cycle of all $n$-bit binary ...
0
votes
1answer
23 views

Distinguishing between hash function digest and message corruption

As an initial disclaimer, I know virtually nothing about coding theory. I apologize in advice for incorrect or inappropriate terminology. The problem space I'm exploring is ensuring the integrity of ...
3
votes
0answers
40 views

Sorted byte arrays with unique values - best possbile compression

I have byte arrays with following constraints: Length between 1 and 256 Length median about 128, but I have to verify this on larger dataset Values are sorted ascending Values are unique I am ...
2
votes
0answers
39 views

Prove $A_q(3, 2) = q^2$ for all $q \ge 2$

Prove $A_q(3, 2) = q^2$ for all $q\ge 2$ I've tried using the sphere packing bound to find a max M for a (3, M, 2) code (with hamming distance 1), and found $M< {q^3\over 4q-3} < q^2$. I then ...
1
vote
3answers
63 views

How does one generally use partial function in logical statements?

How does one generally use partial function in logical statements? How it's done in practice? Specifically, let $M$ by a Turing machine, $f_M:\{0,1\}^*\to\{0,1\}$ the characteristic function which ...
4
votes
2answers
79 views

Logic behind the ID checksum?

I'm a resident of Kuwait and I just learnt that the CIVIL ID numbers allotted to us follow a checksum. The ID is 12 digit number following the algorithm below - ...
1
vote
1answer
118 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) ...
1
vote
1answer
43 views

Control Matrix from a generator matrix

Given a [8,4]-Code over field $\mathbb{Z}_2$ and it's basis, I need to calculae the control matrix. In my homework, we are given (0,0,0,0,1,1,1,1), (0,0,1,1,0,0,1,1), (0,1,0,1,0,1,0,1), and ...
2
votes
1answer
76 views

Prove that a code is linear

Show that the repetition code of order r (i.e. each bit of the original word is sent r times) is a linear code. Determine a generating matrix and a check matrix of this code. So we have a $(r*k,k)$ ...
0
votes
1answer
34 views

Periodic streams

I have problems proving the following result; Suppose you have two periodic streams $x_n$ with period $M$ and $y_n$ with period $N$. The streams $x_n+y_n$ and $x_n y_n$ are periodic with periods ...
0
votes
1answer
38 views

Perfect code in graphs not distance-transitive

Why do we consider a graph as distance-transitive graph when we talk about a perfect code in a graph? Indeed, When there is a non-trivial perfect code in a graph, is the graph a distance-transitive or ...
3
votes
0answers
134 views

Bachelor Thesis - Galois Theory Research Topics?

I'm on the last semester of my bachelor's degree (undergrad degree) and I will be writing my thesis next semester. I have talked to a professor at my university and one of the topics he suggested was ...
0
votes
1answer
33 views

Tell if parity check matrix is linearly independent

I know these are parity check matrixes of linear codes $C_1$ and $C_2$. $H_1= \begin{matrix} 1 & 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 0 ...
2
votes
1answer
42 views

Determine the number of divisors in $K[x]$ of $1 + x^{15}$ and of $1+x^{120}$

where $K[x]$ is the set of all polynomials where coefficients are elements of $K$ $(0,1)$ Is this related to the problem of finding how many cyclic linear codes there are if $n = 15$ and $120$? I've ...
0
votes
1answer
31 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 + ...
1
vote
1answer
81 views

How can I compute the polynomial generator for BCH?

For instance, let $C$ the binary BCH code of length $n=31$ and designed distance with auxiliary finite field $F_{32}=F_2[X]/(X^5 + X^2 + 1)$. First, we compute the cyclonitomic clases ...
0
votes
2answers
85 views

How can I factor the polynomial $x^7-1$ in GF(2)?

The result is $(x+1)(x^3+x+1)(x^3+x^2+1)$, but I don't understand how I can calculate it.