The Complete SC-Invariant Affine Automorphisms of Polar Codes

Let $F=\begin{bmatrix}1&0\\ 1&1\end{bmatrix}$ and $G_{m}=F^{\otimes m}$, where $m$ is the code dimension. A polar code $(n=2^{m},K)$ is generated by selecting $K$ rows of $G_{m}$. The set $\mathcal{I}\subseteq\{0,1,...,n-1\}$ of indices of selected rows is the information set, and $\mathcal{F}=\mathcal{I}^{c}$ is the frozen set. Denote the polar code with information set $\mathcal{I}$ by $C(\mathcal{I})$.

Polar codes can be described as monomial codes [6]. The monomial set is

and the evaluation of $g\in\mathcal{M}$ is

Then each row of $G_{m}$ can be represented by $\text{eval}(g)$ for some $g\in\mathcal{M}$. For example, assume $z\in\{0,1,...,2^{m}-1\}$, there is a unique binary representation $a=(a_{1},...,a_{m})^{T}$ of $2^{m}-z-1$, where $a_{1}$ is the least significant bit, such that

Then the evaluation of monomial $\text{eval}(x_{1}^{a_{1}}...x_{m}^{a_{m}})$ is exactly the $(2^{m}-z-1)$-th row of $G_{m}$. Therefore, the information set $\mathcal{I}$ can be regarded as a subset of $\{0,...,n-1\}$ or a subset of $\mathcal{M}$. As seen, the three representations, i.e., the number $z$, the binary representation of $2^{m}-1-z=(a_{1},...,a_{m})^{T}$ and the corresponding monomial $x_{1}^{a_{1}}...x_{m}^{a_{m}}$ all refer to the same thing.

Two monomials of the same degree are ordered as $x_{i_{1}}...x_{i_{t}}\preccurlyeq x_{j_{1}}...x_{j_{t}}$ if and only if $i_{l}\leq j_{l}$ for all $l\in\{1,...,t\}$, where we assume $i_{1}<...<i_{t}$ and $j_{1}<...<j_{t}$. This partial order is extended to monomials with different degrees through divisibility, namely $f\preccurlyeq g$ if and only if there is a divisor $g^{\prime}$ of $g$ such that $f\preccurlyeq g^{\prime}$.

An information set $\mathcal{I}\subseteq\mathcal{M}$ is decreasing if $\forall g\preccurlyeq f$ and $f\in\mathcal{I}$ we have $g\in\mathcal{I}$. A decreasing monomial code $C(\mathcal{I})$ is a monomial code with a decreasing information set $\mathcal{I}$. If the information set is selected according to the Bhatacharryya parameter, polar codes will be decreasing monomial codes [6], [12]. In this way, polar codes can be generated by $\mathcal{I}_{\text{min}}$, where the information set is the smallest decreasing set containing $\mathcal{I}_{\text{min}}$. From now on, we always suppose $\mathcal{I}$ is decreasing.

Let $C$ be a decreasing monomial code with length $n$. A permutation $\pi$ in the symmetric group Sym$(n)$ is an automorphism of $C$ if for any codeword $c=(c_{0},...,c_{n-1})\in C$, $\pi(c)=(c_{\pi(0)},...,c_{\pi(n-1)})\in C$. The automorphism group Aut$(C)$ is the subgroup of Sym$(n)$ containing all automorphisms of $C$.

Let $M$ be an $m\times m$ binary invertible matrix and $b$ be a length-$m$ binary column vector. The affine transformation $(M,b)$ permutes $a\in\mathbb{F}_{2}^{m}$ to $Ma+b$.

A matrix $M$ is lower-triangular if $M(i,i)=1$ and $M(i,j)=0$ for all $j>i$. The LTA group is the group of all affine transformations $(M,b)$ where $M$ is lower-triangular. Similarly, a matrix $M$ is upper-triangular if $M(i,i)=1$ and $M(i,j)=0$ for all $j<i$.

BLTA$([s_{1},...,s_{l}])$ is a BLTA group of all affine transformations $(M,b)$ where $M$ can be written as a block matrix of the following form

where $B_{i,i}$ are full-rank $s_{i}\times s_{i}$ matrices. BLTA equals the complete automorphisms of decreasing polar codes that can be formulated as affine transformations [8].

Let $L_{i,t}$ be the log likelihood ratio (LLR) of the $i$-th node at stage $t$ and $L_{i,m}$ be the received LLRs from channels. $L_{i,t}$ are propagated from stage $t+1$ according to

At stage $0$, we have

Then hard decisions $u_{i,t}$ are propagated from stage $t-1$ according to

where $\oplus$ means the addition modulo $2$.

Let $\text{SC}_{\mathcal{I}}:\mathbb{R}^{n}\to\mathbb{F}_{2}^{n}$ map the received LLR vector $y=(L_{i,m})_{i\in\{0,...,n-1\}}\in\mathbb{R}^{n}$ to the SC decoding result $(u_{i,m})_{i\in\{0,...,n-1\}}=\text{SC}_{\mathcal{I}}(y)\in C(\mathcal{I})$.

Let $\pi_{1},...,\pi_{t}$ be $t$ different automorphisms of the code $C$ and $y\in\mathbb{R}^{n}$ be the received LLR vector. A list of decoders can independently decode each permuted LLR $\pi_{j}(y)$. The decoded candidate codeword of $y$ using $\pi_{j}$ is

A final decoding result is selected according to the minimum Euclidean distance rule:

For an automorphism $\pi$ of $C(\mathcal{I})$, we say $\pi$ commutes with $\text{SC}_{\mathcal{I}}$ if for all $y\in\mathbb{R}^{n}$, $\text{SC}_{\mathcal{I}}(\pi(y))=\pi(\text{SC}_{\mathcal{I}}(y))$. If $\pi$ commutes with $\text{SC}_{\mathcal{I}}$, the corresponding permuted SC decoder always outputs the same decoding result as the non-permuted SC decoder.

The automorphism $\pi$ in LTA group is SC-invariant for $C(\mathcal{I})$, which means it commutes with $\text{SC}_{\mathcal{I}}$ [5]. Moreover, in [10], two affine automorphisms $\pi,\pi^{\prime}$ are called equivalent for $C(\mathcal{I})$, denoted by $\pi\sim_{\mathcal{I}}\pi^{\prime}$, if for all $y\in\mathbb{R}^{n}$

The equivalence classes are defined as

Let $\mathds{1}$ be identity permutation, the equivalence class $[\mathds{1}]_{\mathcal{I}}$ consists of the complete affine automorphisms commuting with $\text{SC}_{\mathcal{I}}$, which is an automorphism subgroup. The authors of [10] proved that BLTA$([2,1...,1])\subseteq[\mathds{1}]_{\mathcal{I}}$, that is, automorphisms in BLTA$([2,1...,1])$ commute with $\text{SC}_{\mathcal{I}}$ of any decreasing monomial code $C(\mathcal{I})$ whose automorphism group includes BLTA$([2,1...,1])$. A natural question arises: are these the complete SC-invariant affine automorphisms?

Let $M$ be a full-rank matrix. We say $M$ has the block lower-triangular structure $s(M)=\langle s_{1},...,s_{l}\rangle$ if $M$ can be written as (1) and none of $B_{i,i}$ can be written as a block lower-triangular matrix with more than one block. Define $S_{t}=\sum_{i=1}^{t-1}s_{i}$ for $2\leq t\leq l+1$ and $S_{1}=0$.

Define $[a,b]$ to be the integer set $\{i\in\mathbb{N}|a\leq i\leq b\}$ for $a,b\in\mathbb{N}$, and $M([a,b],[c,d])$ to be the corresponding submatrix of $M$.

The affine transformation $(M,0)\subseteq[\mathds{1}]_{\mathcal{I}}$ if and only if $(M,b)\subseteq[\mathds{1}]_{\mathcal{I}}$ for any $b\in\mathbb{F}_{2}^{m}$. For convenience, define $\varphi(M)$ to be the permutation $(M,0)$ which permutes $a\in\mathbb{F}_{2}^{m}$ to $Ma$.

Define $\text{Ind}_{m}(a_{i_{1}}=c_{i_{1}},...,a_{i_{t}}=c_{i_{t}})=\{(a_{1},...,a_{m})^{T}\in\mathbb{F}_{2}^{m}|a_{i_{j}}=c_{i_{j}},\forall j=1,...,t\}$ to be a set of indices whose $i_{1},...,i_{t}$-th bits are fixed to be $a_{i_{1}},...,a_{i_{t}}$. Define

to be the information set of length-$2^{m-t}$ subcode consisting of indices in $\text{Ind}_{m}(a_{i_{1}}=c_{i_{1}},...,a_{i_{t}}=c_{i_{t}})$. $\mathcal{F}(\text{Ind}_{m}(a_{i_{1}}=c_{i_{1}},...,a_{i_{t}}=c_{i_{t}}))$ is defined in the same way.

For example, the factor graph of (8,4) polar code is shown in Fig. 1, where $\mathcal{I}=\{3,5,6,7\}$. In Fig. 1, $\mathcal{I}(\text{Ind}_{3}(a_{1}=1))=\{3\}$ (resp. $\mathcal{I}(\text{Ind}_{3}(a_{1}=0))=\{1,2,3\}$) is the information set of length-4 subcode consisting of indices that the least significant bit $a_{1}$ is equal to $1$ (resp. $0$), i.e. the even (resp. odd) bits. Similarly, $\mathcal{I}(\text{Ind}_{3}(a_{3}=1))=\{3\}$ (resp. $\mathcal{I}(\text{Ind}_{3}(a_{3}=0))=\{1,2,3\}$) is the information set of length-4 subcode consisting of indices that the most significant bit $a_{3}$ is equal to $1$ (resp. $0$), i.e. the first (resp. last) four bits. This definition simplifies the description of decomposed shorter subcodes in our proofs.

In this subsection, we provide two lemmas on matrix transformations.

Next, we show how to decompose upper-triangular transformation by exploiting its block lower-triangular structure.

Algorithm 1 determines whether affine automorphisms with the block lower-triangular structure $\langle s_{1},...,s_{l}\rangle$ commute with $\text{SC}_{\mathcal{I}}$ iteratively. We claim that $\pi=\varphi(M)$ commutes with $\text{SC}_{\mathcal{I}}$ if and only if DecAut$(s(M),\mathcal{I})$ outputs TRUE. Let $\pi_{1},\pi_{2},\tilde{\pi}_{1},\tilde{\pi}_{2}$ be the permutations defined in Definition 1. Note that $s(\tilde{\pi}_{1})=\langle s_{1},...,s_{l-1}\rangle$. We briefly describe procedures of Algorithm 1.

First, if $l=1$ (lines 5-7), $\pi$ is SC-invariant if and only if the code belongs to Rate-0, single parity check (SPC), repetition (Rep) or Rate-1 codes[13].

If $l\neq 1$, we recursively determine whether $\pi$ is SC-invariant. According to $s_{l}$, we consider two cases:

1) $s_{l}=1$ (lines 8-11), because $\pi_{2}$ is the identical permutation, $\pi$ is SC-invariant if and only if $\tilde{\pi}_{1}$ commutes with $C(\mathcal{I}(A_{1}))$ and $C(\mathcal{I}(A_{2}))$, i.e., the subcodes on upper half branch and lower half branch.

2) $s_{l}>1$ (lines 12-23), divide $[0,2^{m}-1]$ into $2^{s_{l}}$ blocks $[i2^{S_{l}},(i+1)2^{S_{l}}-1]$, $0\leq i\leq 2^{s_{l}}-1$. In this case, $\tilde{\pi}_{2}$ is not identical permutation, then $\pi$ is SC-invariant only if all frozen bits belong to the first block or all information bits belong to the last block. Furthermore, $\tilde{\pi}_{1}$ must commute with either the first subcode $C(\mathcal{I}(A_{1}))$ (lines 13-14) or the last subcode $C(\mathcal{I}(A_{2}))$ (lines 16-17) respectively.

In Theorem 1 and Theorem 2, we prove the sufficiency and necessity of Algorithm 1, respectively.

For convenience, denote by $L_{i,t}$ and $u_{i,t}$ the LLRs and hard decisions of the $i$-th node at stage $t$ before permutation, and $L^{\prime}_{i,t}$ and $u^{\prime}_{i,t}$ the LLRs and hard decisions after permutation (see Section II-C).