how to build 14-ary code of lenght 6 with minimum distance

139 Views Asked by At

I need to generate a list of at least 2048 codewords of length 6 in base 14, with the property that any two codewords taken from the list must have in common no more than "n" equal digits in the same position. In other words, codewords must be as different as possible regarding their base-14 digits.

My questions are:

1) what is the minimum "n" ? Is there a way to calculate/estimate it?

2) how to build the actual codewords? is there some known iterative process?

3) what kind of codes should I look for in the literature?

As such codes are to be used in a project that won't change for several years, I would like to be mathematically sure I'm creating the best possible codes.

1

There are 1 best solutions below

6
On BEST ANSWER

Fourteen is a weird alphabet size and weird constructions are called for. For lack of a suitable theory I will just explore some possibilities. Let's do ... Chinese remainder theorem. $$ 14=2\cdot7 $$ so let's combine a binary code with one of alphabet $\Bbb{Z}_7$. Length six you said? Dandy! Reed-Solomon codes over $\Bbb{Z}_7$ have just that length. So as a building block we might use a 7-ary code generated by $$ G_1=\left(\begin{array}{cccccc} 1&1&1&1&1&1\\ 1&2&3&4&5&6\\ 1&4&2&2&4&1 \end{array}\right) $$ that generates a code with $343$ 7-ary words sharing at most two components (so differing in at least $d=4$).

What about the binary component code? If we want to stick to $d=4$, then we cannot do better than $$ G_2=\left(\begin{array}{cccccc} 1&1&1&1&0&0\\ 1&1&0&0&1&1 \end{array}\right) $$ but that has only $4$ codewords. That's too bad, because $4\cdot343=1372<2048$. So may be $d=4$ is too ambitious? To describe the CRT-based construction let us relax and aim at $d=3$ only. Then we can use a shortened Hamming code as the binary component. For example the code generated by $$ G_2'=\left(\begin{array}{cccccc} 1&1&0&1&0&0\\ 0&1&1&0&1&0\\ 0&0&1&1&0&1 \end{array}\right). $$ This gives us a code of $8$ binary words of length six differing from each other at at least $d=3$ positions.

Now we can CRT-combine 7-ary words gotten with $G_1$ and binary words gotten with $G_2'$ to get $2^3\cdot7^3=2744$ words with alphabet $\Bbb{Z}_{14}$ that differ from each other at $\ge3$ positions. The recipe goes as follows.

  1. Build a list $C_1$ of $343$ 7-ary words with alphabet $\Bbb{Z}_7$ by calculating the matrix products $(x_1,x_2,x_3)G_1$ where $x_1,x_2,x_3$ range over $\Bbb{Z}_7$.
  2. Build a list $C_2$ of $8$ binary words by calculating the matrix products $(b_1,b_2,b_3)G_2'$ with $b_1,b_2,b_3$ ranging over $\Bbb{Z}_2$.
  3. Build a list $C$ of $2744$ words with alphabet $\Bbb{Z}_{14}$ as follows. Let $w_1$ be any word of $C_1$ and $w_2$ be any word of $C_2$. Transform the alphabet of $w_1$ to $\Bbb{Z}_{14}$ by doubling all the entries (technically: apply the additive homomorphism $f:\Bbb{Z}_7\to\Bbb{Z}_{14}, \overline{n}\mapsto \overline{2n}$ to its components. Similarly transform the alphabet of $w_2$ by multiplying the componetnst by seven (or $0\mapsto0,1\mapsto7$). Then calculate the sum $2w_1+7w_2$ modulo $14$.

For any distinct pairs $(w_1,w_2)\neq(w_1',w_2')$ either the $C_1$-components or the $C_2$-components are different, and consequently the sum words $2w_1+7w_2$ and $2w_1'+7w_2'$ differ in at least three components.

The code $C$ thus consists of vectors of the form $$ (x_1\ x_2\ x_3)\left(\begin{array}{cccccc} 2&2&2&2&2&2\\ 2&4&6&8&10&12\\ 2&8&4&4&8&2 \end{array}\right)+ (b_1\ b_2\ b_3)\left(\begin{array}{cccccc} 7&7&0&7&0&0\\ 0&7&7&0&7&0\\ 0&0&7&7&0&7 \end{array}\right) $$ with $0\le x_1,x_2,x_3<7$, $b_1,b_2,b_3\in\{0,1\}$. All the arithmetic done modulo $14$. Any two resulting words share at most three components. Because the $C_1$ components share at most two components we can more precisely say that each word shares three components with exactly $2^3-1=7$ other words, and at most two components with the remaining words.


I don't know if it is possible to improve upon this and guarantee that we always get at most two shared components. I couldn't bend the parameters of the CRT-method and known component codes to achieve that, but there may be other methods. Exploring them sounds like work (read: I would need to get paid, and I don't have the time anyway). Undoubtedly you have searched for ring codes. Do observe that by using a bigger 7-ary Reed-Solomon code we can actually construct a code with $2^3\cdot7^4=19208$ words agreeing in at most $3$ components.