1
vote
0answers
31 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
1answer
26 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 ...
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
38 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 ...
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 ...
0
votes
0answers
59 views

Computing a parity check matrix given the minimum code distance

As per the title, I would like to know if it is possible to construct a parity check matrix given the length of the code, dimension and the minimum distance of the code. For example, if I would like ...
2
votes
1answer
60 views

Spanning sets in linear block codes

Let $C$ be a binary linear code of length $n$ and rank $k$. Say that a codeword $c\in C$ satisfies the $i$-property in $C$ if $c$ has a $1$ in the $i$-th position and $$w(c)=min\{w(c') : c'\in C\text{ ...
1
vote
0answers
90 views

Distributing partially known data between n parties

Assume that $n = 2r+1$. There are $n$ elements $a_1,a_2,\ldots,a_n$ from a finite field $\mathcal{F}$, and $n$ parties. Each party knows the values of at least $r+1$ elements out of those $n$ ...
1
vote
0answers
18 views

Show C is not 1-error correcting by using Slepian decoding

Let C $\subseteq$ $ \mathbb{Z}_2^5$be a linear code with generator matrix $$G=\begin{bmatrix}1 & 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 1 & 1\\0 & 0 & 1 & 0 & ...
0
votes
1answer
43 views

product of vectors is zero then products of basis is.

Let $V$ be a vector space over a finite field $F_q$ and let $\{v_1, v_2, . . . , v_k\}$ be a basis of $V$. Show that the following two statements are equivalent: (i) $v\cdot v^\prime = 0$ for all $v, ...
2
votes
1answer
215 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 ...
0
votes
0answers
32 views

Forming a large set of vectors with minimal distance 3

I have the following problem related to error-correcting codes. Let $K = 2^{r+1}-1$ for some positive integer $r$ and suppose $C$ is a subspace of $\mathbb{F}_2^K$ is a subspace such that any pair of ...
1
vote
2answers
238 views

Finding the parity check matrix for (10,6,3) shortened Hamming Code

I am dealing with error correction using a (10,6,3) shortened hamming code. I can do the linear algebra for decoding a (7,4) hamming code so i sort of understand what going on here. However now I am ...
0
votes
1answer
39 views

A property of linear (error correcting) codes

Can someone prove the following problem? Let $C \subseteq \mathbb{F}_2^n$ be a linear code and let $$C^{\bot} = \{y \in \mathbb{F}_2^n \mid \langle x,y \rangle \mbox{ for all} \; x \in C\},$$ be the ...
2
votes
1answer
79 views

Cyclic error correcting code

Notation: I denote the field with $2$ elements by $\mathbb{F}_2$. For a vector $u\in\mathbb{F}_2^m$, I write $w(u)$ for the Hamming weight of $u$ (the number of components equal to $1$ in $u$). ...
2
votes
1answer
76 views

Equivalent codes: Are these two approaches the same?

In the usual theory of codes, a code $C$ of length $n$ of dimension $d$ over a finite field $F$ is a linear subspace $C$ of $\mathbb{F}^n$ of dimension $d$ normed by the Hamming metric. In this sense, ...
1
vote
0answers
134 views

How to find the parity check matrix for 101101101101101 in Hamming Codes (15,11) in graphic way?

I am trying to find hamming matrix for safe coded word: 101101101101101 My questions are: 1) What matrix check I should use? I mean there are two types of 15,11 => one starting with 1111 and one ...
2
votes
2answers
95 views

Minimum distance of the linear code $\{0,1\}$

Let $H$ be a check matrix for a linear code $C$. Then the minimum distance of $C$ is $d \in \mathbb N$ such that there exists a set of $d$, but no set of $d-1$, linearly dependent columns in $H$. ...
10
votes
1answer
151 views

Isomorphism between $E_8$ lattice and lattice defined by Extended Hamming Code

I have read that the following two lattices are isomorphic, and of course it seems believable, but it would be nice to have a sketch of how to construct the bijection. Let $C$ be some extended ...
1
vote
1answer
77 views

do linear block code codewords need to contain the original k bits?

In standard form, the Generator matrix of a linear block code will contain the Identity matrix. However, the generator matrix need not be in standard form. However, is it the case that k of the n ...
6
votes
2answers
865 views

Minimum distance of a binary linear code

I need to find parameters $n$, $k$ and $d$ of a binary linear code from its Generator Matrix. How can I find parameter $d$ efficiently? I know the method that compute all the codewords and take ...
0
votes
2answers
65 views

span set and min distance of a code

Let C have the spanning set $S$ where $S=\{v_1,v_2,v_3\}\subseteq \mathbb{F}^n_q$ then $d(C)=\min\{wt(v_1),wt(v_2),wt(v_3)\}$ Is that statement true?why? thank you for your answers...
3
votes
3answers
2k views

Finding the parity check matrix for $(15, 11)$ Hamming Codes

I understand how Hamming Codes and their error detection works, but I'm confused how the parity check matrix is found. How exactly is this computed?
1
vote
0answers
87 views

Rank-nullity theorem and binary codes

I am asked to prove the fact that if $C$ is an $[N,k]$ code, and $C^{\perp} = x \in \mathbb{F}_2^N$ $|$ $(x,c) = 0$  $\forall c \in C$, then $\dim C + \dim C^{\perp} = N$. I am regrettably far ...
2
votes
1answer
249 views

Properties of diagonal and permutation matrices.

I've been reading about equivalent codes, and the topic of monomial automorphisms came up. These are the set of monomial matrices (square matrices with exactly one nonzero entry in each row and ...
1
vote
1answer
155 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 ...
2
votes
2answers
351 views

Finding the information sets of a linear code.

I'm trying to get a better understanding of linear codes, so I decided to work on problems from various textbooks. I'm having trouble understanding how to do this problem, and I was wondering if ...
1
vote
2answers
559 views

Why are the rows of a parity-check matrix linearly independent?

I've been reading about error-correcting codes, and I came across the following definition for a parity-check matrix: ''There is an $(n-k) \times n$ matrix $H$, called a parity check matrix for an ...
0
votes
1answer
190 views

Decoding Reed-Muller code

Apparently, there seems to be many online resources that talk of the process of encoding into Reed-Muller code. However, I was not able to find online resources that explain the process of decoding ...
2
votes
1answer
117 views

What's the algebraic way to solve this coding problem?

I found this problem in here (Problem 6 on page 6) Consider the triple repeat code. What codewords are closest to $(1, 1, 0)$? Describe the set of vectors at distance $1$ or less from the ...
3
votes
1answer
451 views

Finding Null Space Basis over a Finite Field

I have more a systems background, but I have a math-y type question so I figured I'd give it a shot here...This is more of an implementation question, I don't need to prove anything at the moment. ...
1
vote
1answer
596 views

Probability of full rank of a random matrix.

Suppose, $G$ is a $k \times n$ binary matrix with $\operatorname{rank}(G) = k$. The first $k$ columns of $G$ are linearly independent and the next $n-k$ columns are linear combinations of the first ...
0
votes
0answers
337 views

increase the number of linearly independent rows/columns in a matrix

I have the following problem which is a part of a larger problem. I would like to hear your comments or point me to the correct direction. I am making use of a randomly generated boolean matrix of ...
1
vote
1answer
73 views

Unimodular matrices without stable sub-spaces of even weight?

For each N, is there an N×N invertible matrix T over ℤ/2ℤ which does not have a stable subspace of "even weight" -- i.e.  such that there does not exist a set of vectors over ...
5
votes
1answer
85 views

How to find the sparsest vector in a given subspace of $\mathbb{F}_2^n$

A subspace $C$ of $\mathbb{F}_2^n$ is given for some $n \geq 1$. The space $C$ is given by its basis. Is there a polynomial time algorithm to find the (nonzero) vector in $C$ of lowest hamming ...
0
votes
1answer
344 views

Multiplication of matrices in GF(2) and R

$H$ is an $n \times n$ matrix with elements in $ \{ -1,0,1 \}$ $G$ is an $n \times k$ matrix with elements in $GF(2)$ and also upper triangular, invertable $m$ is an $k \times 1$ vector with ...
6
votes
0answers
167 views

Is there a Mazur–Ulam theorem equivalent for vector spaces over finite fields?

I know that Mazur–Ulam theorem holds for normed linear spaces over $\mathbb{R}$. I wanted to know whether under some "weak" conditions on the map $f$, can we have Mazur-Ulam theorem for a vector ...
2
votes
1answer
247 views

Matrix column permutation under constraint

Apologize if you've read my question on Mathoverflow, I'm very curious about whether there's an answer to this. In coding theory, there are parity-check codes whose parity-check matrices H are ...
4
votes
3answers
282 views

Codes: Distance, number of codewords, etc

Let $p\geq 3$ be any prime and consider the code $C = N(H)\subseteq\mathbb{Z}_p^2$, where $H = \begin{pmatrix} 1 & 1 & 1 & \dots & 1 & 1 \\ 0 & 1 & 2 & \dots & p-2 ...
5
votes
1answer
122 views

Database of binary linear codes (including bad ones)

I am looking for all $k$-dimensional subspaces of $(\mathbb{Z}/2\mathbb{Z})^n$ up to permutational equivalence. Is there a database of all $[n,k]$-codes up to equivalence for reasonable values of ...