0
votes
0answers
50 views

Syndrome Leaders

I've been stuck on this problem for a long time and I can't figure it out. I need to find the set of coset leaders and their syndromes. I have my coset leaders (I think) but I can't figure out how to ...
0
votes
1answer
51 views

Is there a binary [10,6,4] code?

Using the sphere padding packing bound formula I can conclude that 1 + 12 + 66 $\ge$ $2^{6}$ which indicates that there MAY be a binary [10,6,4] code, however I cannot prove that there is. How can I ...
0
votes
0answers
24 views

Finding a parity check matrix of a binary code

I'm supposed to find a parity check matrix of a binary [6,3,3] code. Given a generator matrix G I can find a parity check matrix by row reducing until I get the identity matrix, then take $-A^{\top} ...
0
votes
1answer
23 views

Finding a standard generator matrix given a binary code

My question is how do I find the standard generator matrix of a binary [7,6,2] code? From what I understand a generator matrix for $C$ is any $ k \times n$ matrix $ G$ with entries in $ ...
3
votes
2answers
60 views

$\dim (D-P)=\dim (D)-1$

I'm trying to prove this question: Let $D$ be a divisor in $F|K$ such that $\dim (D)\gt 0$ and $0 \neq f\in \mathscr L(D)$. Thus $f\notin \mathscr L(D-P)$ for almost all $P$. Then show that ...
3
votes
0answers
24 views

Linear code from larger linear code

Question 2.16 of Essential Coding Theory by Guruswami, Rudra and Sudan asks to produce a $[n - d, k - 1, d'\geq\lceil d/q\rceil]_q$ code from an arbitrary $[n, k, d]_q$ code. Here we are working over ...
0
votes
0answers
42 views

Proving that number of codes with even weight is the same as number of codes with odd weight for a specific code book

Consider the $[n,n]$ code-book $C_0=\{0,1\}^n$ with $n$ being odd and the codes $c_i \in C_0=[c_1,c_2,...,c_{2^n}]$ being sorted in the ascending order of hamming weight (from $0$ to $n$). Now let's ...
1
vote
2answers
41 views

Proving that only the linear codes pass parity check

An exercise in my book goes as follows: Let $C$ be a binary $(n,k)$ linear code with parity-check matrix $H$. We know $Hc=0$ for all $c\in C$. Show that $Hw=0$ implies $w\in C$. My idea: Let ...
2
votes
2answers
47 views

Linear Code (9,5): Is my Parity Check correct?

I have an exercise about designing parity checks for the Hamming (9,5) group code with minimum distance $3$. I use the following notation for the generator matrix: $$ ...
1
vote
0answers
34 views

Generator Matrix

I have a C in $F_2^6$ $(x_1,x_2,x_3,x_4) \to (x_1,x_2,x_3,x_4,x_1+x_2,x_3+x_4)$ for $x = (1,0,1,1)$ i get $c = (1,0,1,1,1,0)$ we know that $$c = G . x$$ G is the Generator Matrix in the solution ...
3
votes
0answers
39 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
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
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$, ...
5
votes
0answers
29 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 ...
-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
42 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
51 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
77 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
62 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
72 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
66 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
93 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
19 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
270 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
288 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
41 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
96 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
97 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
148 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
133 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
184 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
82 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
1k 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
72 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
3k 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
93 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
294 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
172 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
398 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
605 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
201 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
118 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
488 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
659 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
347 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
91 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
374 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
186 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 ...