1
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ 14 is a weird alphabet size, it's not of the form $p^k$ (with $p$ prime) so it's hard to use Galois field theory (the standard technique, to build linear codes with maximum distance). If we had 16 instead, we could try some Reed Solomon construction. I doubt that there is a construction procedure for 14. BTW: you didn't specify if you want it linear, nor how do you intend to decode it. BWT2 : be aware that maximing the minimun distance is not equivalent to "creating the best possible code" math.stackexchange.com/questions/1843604/… $\endgroup$
    – leonbloy
    Aug 3 '16 at 17:27
  • $\begingroup$ What leonbloy says is all true. Sometimes it just happens that the numerology is determined by someone else (or by other system design decisions). I recall having once been called upon to design a cyclic code of length ten and alphabet size six. Sheesh... Gimme a moment... $\endgroup$ Aug 4 '16 at 5:44
  • $\begingroup$ these weird numbers are out of my control, they are a reading from a magnetic badge, made of a six character string where each character is 0...9 + A,B,C,D. The need for the code is because the readings are very unreliable, usually 1 or two digits gets corrupted. $\endgroup$ Aug 4 '16 at 8:08
  • $\begingroup$ also, decoding will be done simply by taking the nearest valid codeword. $\endgroup$ Aug 4 '16 at 8:10
  • $\begingroup$ > decoding will be done simply by taking the nearest valid codeword Nearly always that (brute force) decoding is too slow to be practical. $\endgroup$
    – leonbloy
    Aug 4 '16 at 15:50
4
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ thanks a lot !!! I will try to generate the code. The d=4 with 1372 codewords is interesting too because perhaps I can lower my constraint from 2048 to 1372 not sure if I can, but anyway thanks you very much. $\endgroup$ Aug 4 '16 at 8:16
  • $\begingroup$ and BTW, as I said in a comment above, this code will be used for an unreliable magetic badge reading that has six-characters, [0-9] + [A-D], and where errors corrupt 1 or two digits. $\endgroup$ Aug 4 '16 at 8:20
  • $\begingroup$ @nino.porcino Hmm. Can you run a sim to see how well a code works? Also you need to think what kind of errors you absolutely want to avoid. For ID badges it may be kind a severe, if one badge passes for another. Probably not your decision only, but in your position I would run a sim so that I would be able to say to the next guy up that if we select this scheme, then this type of an error event will happen with this probability et cetera. I would think that you would cover your ass nicely by giving such data for a few codes, and then leave the final decision to your superiors. $\endgroup$ Aug 4 '16 at 16:04
  • $\begingroup$ Also, you may want to look up magnetic recording codes (or some buzzword like that). It may easily happen that certain multiple character error events are more likely than others: the magnetic structure may disturb adjacent symbols et cetera, the device may begin to read from the second symbol instead of the first (in which case a cyclic code like this is could be a bad idea). Use your engineering mind! $\endgroup$ Aug 4 '16 at 16:08
  • $\begingroup$ thanks for the suggestions, I am indeed already running simulations. As you have said, the situation I want to cover is one ID passing as another which is causing a lot of troubles with our existing 4 digits code (where all codes were generated sequentially). All I can do is extend the code to 6 digits, use more digits (base 14 instead of 10) and build a better code. $\endgroup$ Aug 6 '16 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.