encoder()

grassmanntn.param.encoder(index)

The encoder-switching function—convert the canonical index to parity-preserving index and vice versa.

Parameters:

  • index: int

    The composite index \(I\) in the canonical or parity-preserving encoder.

Returns:

  • out: int

    The composite index in a different encoder.

Description

The composite index can be under two encodings: canonical and parity-preserving.

\[I_\text{canonical}(i_1,\cdots,i_n) = \sum_{a=1}^n 2^{a-1}i_a,\]
\[\begin{split}I_\text{parity-preserving}(i_1,\cdots,i_n) = \left\{ \begin{array}{ll} \sum_{a=1}^n 2^{a-1}i_a & ; i_2+\cdots+i_n\;\text{even},\\ 1-i_1+\sum_{a=2}^n 2^{a-1}i_a & ; i_2+\cdots+i_n\;\text{odd}. \end{array} \right.\end{split}\]

Please see the paper for more details. This function is self-inverse (see the proof below), so it will operate with the assumption that the input is in the canonical encoder, without loss of generality. The function first convert \(I\) into the bits representation, then the parity-preserving encoding is applied.

Proof of the self-inverse

The encoder-switching function \(\varepsilon(I)\), where \(I\) is in the canonical encoder, can be written in a compact form as

\[\begin{split}\varepsilon(I) = \left\{ \begin{array}{ll} I & ; p(I)-i_1\;\text{even},\\ 1-2i_1+I & ; p(I)-i_1\;\text{odd}. \end{array} \right.\end{split}\]

Since \(i_1=I\;\text{mod}\;2\), we have

\[\begin{split}\varepsilon(I) = \left\{ \begin{array}{ll} I & ; p(I)-I\;\text{even},\\ 1-2(I\;\text{mod}\;2)+I & ; p(I)-I\;\text{odd}. \end{array} \right.\end{split}\]

We next consider applying \(\varepsilon\) twice on an integer \(I\). There are three possible cases:

  • Both \(I\) and \(p(I)\) are of the same parity

    Then \(p(I)-I\) is even, which means that \(\varepsilon(I)=I\) and thus \(\varepsilon(\varepsilon(I))=I\).

  • \(I\) is odd and \(p(I)\) is even

    Then \(\varepsilon(I)=I-1\) is even. Note that when \(I\) is odd, then the first bit must be 1, meaning that every bits of \(I-1\) is the same as \(I\) except for the first one which is 0. It also means that if \(p(I)\) is even, then \(p(I-1)=p(\varepsilon(I))\) must be odd because there is only one bit that are different between \(I\) and \(I-1\). All of this implies that \(p(\varepsilon(I))-\varepsilon(I)\) must be odd. It follows that

\[\varepsilon(\varepsilon(I)) = \varepsilon(I-1) = 1-2( (I-1)\;\text{mod}\;2 ) + (I-1) = I.\]

  • \(I\) is even and \(p(I)\) is odd

    Then \(\varepsilon(I)=I+1\) is odd. Using the same logic about the first bit as in the previous case, we arrive at the fact that \(p(\varepsilon(I))-\varepsilon(I)\) must be odd. It follows that

\[\varepsilon(\varepsilon(I)) = \varepsilon(I+1) = 1-2( (I+1)\;\text{mod}\;2 ) + (I+1) = I.\]

In every case above, we have \(\varepsilon(\varepsilon(I))=I\) which means that \(\varepsilon(I)\) is self-inverse.

QED