# Tagged Questions

50 views

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 ...
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 ...
24 views

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 ...
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 ...
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 ...
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 ...
47 views

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$ ...
19 views

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$). ...
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, ...
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 ...
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$. ...
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 ...
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 ...
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 ...
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...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...