0
$\begingroup$

So I have a list of codewords. The codewords have length 64, so there are 64 codewords in my code. My code is over an alphabet of 4 (the code can be thought of as having four elements $0,1,2,3$ and operations over mod4).

Think of the codewords as vectors of length 6.

I want to find a list of vectors $V$ which, when multiplied with each of the specified codewords $c \in C$, gives $0$.

i.e $V=$ { $v \text{ }| \text{ } v.c=0 \text{ }\forall \text{} c \in C$ }

I figured that $V$ must consist of all the tuples of length 6 over the four-symbol alphabet:

tuples=Tuples[{0,1,2,3}, 6]

I then created a table of values storing the result of each tuple being multiplied (dot product) by each codeword

table=Table[tuples[[i]].codewords[[j]], {i,1,Length[tuples]}, {j,1,Length[codewords]}]

I then attempted to iterate through the table and if there are any entries of 64 zeroes, then we store the tuple corresponding that those zeroes in $V$

If[Total[table[[#]]]==0, tuples[[#]], Nothing]

However, I think this is far too big for mathematica to handle. It keeps crashing. Is there any way of condensing this, or not iterating over everything so that I can find $V$?


Note, I actually constructed my code over GF[4] using the finite fields package, however, my problem is just with the largeness of the dataset of tuples over a four letter alphabet of length 6, so the bones of the question remain the same if you assume it is just a code over mod4 consisting of {0,1,2,3}

$\endgroup$
3
  • 1
    $\begingroup$ I think I am misunderstanding the question, but could you use the NullSpace of the list of codewords and pick the vectors in the null space that consist only of elements 0,1,2, or 3? $\endgroup$
    – ydd
    Nov 13, 2023 at 15:04
  • 1
    $\begingroup$ If I run codewords=RandomChoice[Range[4],{64,6}]; Solve[Thread[Array[a,6].#&/@codewords==0],Array[a,6],Integers], the only solution found is a vector of zeroes. How am I misunderstanding your question? Can you add a (small) sample of your codewords together with a possible solution? $\endgroup$
    – MarcoB
    Nov 14, 2023 at 12:31
  • $\begingroup$ I think perhaps I overestimated how simple the question would translate from mod4 to finite fields. I will add an answer to my question now, although NullSpace[] command certainly worked for my purposes with some adjustments. $\endgroup$
    – am567
    Nov 15, 2023 at 13:56

1 Answer 1

1
$\begingroup$

This answer works over finite fields (package already established and GF(4) already established, not included in code below), however, I think you would just need to use NullSpace[codewords, Modulus->4] in order to work over $\mathbb{Z}4$ instead.

Rather than attempt to find all of the possible tuples of {f4[0], f4[1], f4[2], f4[3]} of length 6 and then finding which of these tuples is orthogonal to every vector in "codewords", instead I followed @ydd's approach of using the null space of my codewords.

I found the null space of my codewords, which provides a basis for all the vectors which are orthogonal to the codewords (i.e satisfy the equation C.x == 0, where C are the codewords and x is a vector in GF(4) orthogonal to every codeword).

I then found all of the possible combinations of the row space multiplied by elements from the finite field, in order to find every vector orthogonal to the codewords in GF(4).

Then, I found the Union of this result to remove duplicate vectors.

dualcodewords = Module[{H, row1, row2, row3},
  H = RowReduce[NullSpace[codewords]];
  row1 = H[[1]];
  row2 = H[[2]];
  row3 = H[[3]];
  table = Table[
            f4[i] row1 + f4[j] row2 + f4[k] row3, 
            {i, 0, 4}, {j, 0, 4}, {k, 0, 4}
          ];
  Union[Flatten[table, 2]]
 ]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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