Articles of coding theory

How to find all the coset leaders? (follow-up to a previous question)

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 […]

Generating a binary code with maximized Hamming distance

I have a (seemingly) simple question about coding theory. I feel like the answer to this should be very obvious, but I’m having some troubles with it. I’m trying to create binary code which is $N$ bits in length and consists of $M < 2^N$ codewords, $\{m_1, m_2, … , m_M\}$. For a given $N$ […]

Which polynomials with binary coefficients evaluate only to 0 or 1 over an extension field?

Consider the polynomial $p(x) = 1+x^5+x^{10}$ with binary coefficients. Consider the multiplicative group of $\mathbb{F}_{16}$, and let $p(x)$ be evaluated at each of these $15$ elements. The only possible evaluations are $0$ and $1$. I am looking for more such polynomials which have binary coefficients, which when evaluated on the elements of an extension field […]

Whether the code produced by CRC is a cyclic code?

Wikipedia says that CRC algorithm is based on cyclic codes, but it doesn’t say that it is a cyclic code. If I understood correctly, a linear code of length $n$ called cyclic if and only if its generator polynomial divides $x^n-1$. So I think that in general CRC codes are not cyclic. Is it true? […]

Understanding Reed-Solomon as it applies to Shamir secret sharing

I’m working on trying to understand how to use Reed-Solomon decoding to make Shamir secret sharing robust to cheaters as mentioned here. I’m following the setup shown at the bottom of page 40 in this paper. So, here is my simple example. I’m working in $\mathbb{Z}_{11}$. Let $p(x)=8+3x$ be the polynomial I’m using for sharing […]

The sum of a polynomial over a boolean affine subcube

Let $P:\mathbb{Z}_2^n\to\mathbb{Z}_2$ be a polynomial of degree $k$ over the boolean cube. An affine subcube inside $\mathbb{Z}_2^n$ is defined by a basis of $k+1$ linearly independent vectors and an offset in $\mathbb{Z}_2^n$. [See “Testing Low-Degree Polynomials over GF(2)” by Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron – – for more details] […]

What is the difference between the sphere and projective space?

I know about the antipodal mapping. What I want to know is what the most significant differences between the sphere and projective space are, and how to think of each of them and their relationship to one another. I come at this from a coding theory/vector quantization perspective; I’m trying to understand the difference between […]

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 distance: $$d(\omega,\omega’)=\#\{i\in \{1,\ldots,n\} \vert a_i\neq b_i\}$$ where $\omega=a_1\ldots a_{n}$ and $\omega’=b_1\ldots b_n$ are two words. The questions are the following: Let $\omega_0$ be the […]

An easy reference for genetic algorithm

My field is Coding Theory and my background is Algebraic, there are many applications of Genetic Algorithm in Coding Theory, I would to know the easiest and the most elementary and introductory note about “Genetic Algorithm in Coding Theory”, also is this algorithm using in Crypto too?

Bounds on the size of these intersecting set families

Are there good lower bounds on the size of a collection of $k$-element subsets of an $n$-element set such that each pair of subsets has at most $m$ elements in common?