Intereting Posts

What's the quickest way to solve $3^i \equiv 1 \mod 28$
what's the difference between Syntactic consequence ⊢ and Semantic consequence ⊨
Free Throw Probability and Expected Number of Points
Generating function solution to previous question $a_{n}=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3 \rfloor}+a_{\lfloor n/6\rfloor}$
How to solve implicit differential equation?
Is there a closed form expression for this sum involving Stirling number of second kind
Relation between $\gcd$ and Euler's totient function .
$\int_t^T 1_C\cdot A\;d\!X=1_C\cdot\int_t^T A\;d\!X$ for $C\in\mathcal F_t$?
Showing that ${\rm E}=\sum_{k=0}^\infty P(X>k)$ for a discrete random variable
Fixed points in category theory
AM-GM inequality basic
Show that, for $t>0$, $\log t$ is not a polynomial.
Intuition behind $dx \wedge dy=-dy \wedge dx$
What are the prerequisites for taking introductory abstract algebra?
How to prove that: $\tan(3\pi/11) + 4\sin(2\pi/11) = \sqrt{11}$

Consider the $[4,2]$ ternary Hamming code with check matrix $ \left( \begin{array}{ccc}

1 & 1 & 2 &0\\

0 & 1 & 1 & 1\end{array} \right). $ Clearly, the code has $4$-tuple minimum-weight error vectors $\{\vec e_{m1}=\vec0,…,\vec e_{m9} \}$ corresponding to all the syndromes $\{\vec s_1=\vec0,…,\vec s_9 \}$. My textbook says to list $\vec0$ and all the eight 4-tuples whose weight is $1$, since *nonzero 4-tupple error vectors have minimum weight 1*. Sounds reasonable, except that I don’t understand why the italized statement is so nor why each coset has at least one such vector.

More importantly, in general, given a linear code, **is there an algorithm to determine the minimum-weight error vectors corresponding to the syndromes**, without having to first list out all the possible cosets?

(I understand that multiple such vectors may correspond to a syndrome, and also realise that different coset leaders may have different weights.)

- Distance of bch code
- Factorize polynomial over $GF(3)$
- Calculating CRC by long division: How to decide the top number of long division?
- Proof of Closed Form Formula to convert a binary number to it's Gray code
- Huffman optimal code
- Minimum distance of a binary linear code

- CRC computation
- Cryptography and Coding Theory
- An easy reference for genetic algorithm
- What is the difference between the sphere and projective space?
- Which polynomials with binary coefficients evaluate only to 0 or 1 over an extension field?
- What requirements should a CRC polynomial satisfy?
- Is there a $(6,9,3)_2$ code?
- Using Extended Euclidean Algorithm to find multiplicative inverse
- Reed Solomon Polynomial Generator
- Huffman optimal code

I am not aware of a general efficient algorithm for doing this. Again a few remarks listing some obvious things and then trying to explain why this is difficult in general.

First the easy parts. If the minimum distance of the code is $d$, then any vector of weight $\le(d-1)/2$ is the leader of its coset. This follows immediately from the triangle inequality (applied to the Hamming metric). If the weight of a vector $x$ is $w>(d-1)/2$, then $x$ may or may not be a coset leader. If $w>d/2$, then we can always find some vectors of weight $w$ that are not coset leaders. If $w=d/2$, then $x$ is a coset leader, but there may be other vectors of weight $w$ in the same coset, and it is not at all clear which of those should be included in the syndrome dictionary!

Then the difficult part. In general we do not know the maximum weight of a coset leader! This maximum has another name. It is better known as the *covering radius* of the code. The covering radius is known only for relatively few of the well studied linear codes, such as the Hamming code. If the covering radius of a code $C$ is $\rho$, this means that any vector is within Hamming distance $\le\rho$ from a codeword of $C$. For example the covering radii of BCH-codes are known in a few specific cases, and in the asymptotic case (keep the designed distance but let the length grow). These were studied in highly non-trivial research papers, so I won’t get into details here.

However, we can easily settle the truth of the italicized statement in your question! While doing that we actually prove that the covering radius of this code is $1$, but you don’t need to necessarily worry about that.

You correctly observed that the syndrome of this code has nine possible values.

Furthermore, we know that the minimum distance of this code is $d=3$. In my answer to an earlier version of this question I explained, why there are nine vectors of weight $\le1$ in

the Hamming space $\mathbb{F}_3^4$. Because their weights are all $\le(d-1)/2$, they belong to distinct coset of the code (see the “easy part”). Therefore they cover all the nine cosets between them. A miracle occurred!

There is another way of seeing this. The syndrome of the zero vector is obviously zero. But the syndrome of the vector with three zeros and a single one is the corresponding column of the check matrix. Similarly the syndrome of the vector with three zeros and a single two is the corresponding column multiplied by $2=-1$. Now, you should check that if you list all the four columns of your check matrix together with the versions multiplied by $2$ (or $-1$), your list contains all the eight non-zero vectors with two ternary components.

- Suppose that a sequence is Cesaro summable. Prove…
- Is there an algebraic closure for the quaternions?
- Multivariate function interpolation
- How many times are the hands of a clock at $90$ degrees.
- The order of the number of integer pairs satisfying certain arithmetical function relationships
- Idealizer of one-sided ideal
- Function that sends $1,2,3,4$ to $0,1,1,0$ respectively
- Cardinality of power set of $\mathbb N$ is equal to cardinality of $\mathbb R$
- Prove that matrices have equal rank.
- How would you evaluate $I:=\int_ {0}^{\infty} \frac {\cos(ax)} {(x^2 + b^2)^n} \ \mathrm{d}x$?
- Is it possible to create a completely random integer between 1 and 13 using standard dice in a D&D dice kit?
- Archimedean Property – The use of the property in basic real anaysis proofs
- Prove $n\binom{p}{n}=p\binom{p-1}{n-1}$
- Prime number generator, how to make
- Why is $\arccos(-\frac 13)$ the optimal angle between bonds in a methane ($\rm CH_4$) molecule?