# Systematic Encoding and Shortening of PAC Codes
## 2 PAC Codes  
A PAC code over \(\mathbb{F}_{2}\) is a linear block code parametrized by \((N,K,\mathcal{A},\mathbf{f},\mathbf{g})\) where \(N\) is a code block length, \(K\) is a code dimension, \(\mathcal{A}\) is a data index set, \(\mathbf{f}\in\mathbb{F}_{2}^{N-K}\) is a frozen word, and \(\mathbf{g}=(g_{0},g_{1},\ldots,g_{m})\in\mathbb{F}_{2}^{m+1}\) is a convolution impulse response with \(g_{0}=1\), \(g_{m}=1\), with \(g_{i}\) subject to design for \(0<i<m\). The data index set \(\mathcal{A}\) is a subset of \(\{1,2,\ldots,N\}\) with size \(|\mathcal{A}|=K\). The parameter \((1+m)\) will be called the span of the impulse response \(\mathbf{g}\). The span of any impulse response \(\mathbf{g}\) that we consider here will be bounded by the block length \(N\). Sometimes, when the span cannot or need not be shown explicitly, we will write \(\mathbf{g}=(g_{0},g_{1},\ldots,g_{N-1})\) to denote an impulse response, with the understanding that \(g_{i}=0\) for \(i\) greater than or equal to the span of \(\mathbf{g}\). An encoder for a PAC code encodes data words \(\mathbf{d}\in\mathbb{F}_{2}^{K}\) into codewords \(\mathbf{x}\in\mathbb{F}_{2}^{N}\) by computing a convolution followed by a polar transform. In the convolution step, a convolution input word \(\mathbf{v}\in\mathbb{F}_{2}^{N}\) is prepared by setting \(\mathbf{v}_{\mathcal{A}}=\mathbf{d}\) and \(\mathbf{v}_{\mathcal{A}^{c}}=\mathbf{f}\), and a convolution \(\mathbf{u}=\mathbf{v}*\mathbf{g}\) is applied to \(\mathbf{v}\) to obtain a polar transform input word \(\mathbf{u}\in\mathbb{F}_{2}^{N}\). (\(\mathcal{A}^{c}\) denotes the complement of \(\mathcal{A}\) in \(\{1,2,\ldots,N\}\).) In the polar transform step, the codeword \(\mathbf{x}\in\mathbb{F}_{2}^{N}\) is obtained by computing \(\mathbf{x}=\mathbf{u}\mathbf{L}\), where \(\mathbf{L}=\mathbf{F}^{\otimes n}\) is the polar transform matrix, defined as the \(n\)th Kronecker power of a kernel matrix \(\mathbf{F}=\left[ \begin{smallmatrix}1&0\\ 1&1\end{smallmatrix} \right]\). The convolution step \(\mathbf{u}=\mathbf{v}*\mathbf{g}\) involves the computation  
\[u_{i}=\sum_{j=0}^{m}v_{i-j}g_{j},\quad\text{for }i=1,2,\cdots,N, \tag{1}\]  
where \(v_{i-j}\) is interpreted as \(0\) if \(i-j\leq 0\). In the following analysis, we will represent the convolution alternatively as a linear transformation \(\mathbf{u}=\mathbf{v}\mathbf{T}\) where \(\mathbf{T}\in\mathbb{F}_{2}^{N\times N}\) is an upper-triangular Toeplitz matrix of the form  
Figure 1: BER comparison for systematic and non-systematic PAC codes. (Since \(\mathbf{G}\) is the product of two invertible matrices, it is invertible; hence, all its principal submatrices are invertible.) We summarize this result as follows. The systematic encoding problem (3) for PAC codes has a solution whenever \(\mathcal{B}^{c}=\mathcal{A}\), and the solution is given by  
\[\mathbf{x}_{\mathcal{A}^{c}}=\mathbf{d}\left(\mathbf{G}_{\mathcal{A},\mathcal{ A}}\right)^{-1}\mathbf{G}_{\mathcal{A},\mathcal{A}^{c}}+\mathbf{f}\left[ \mathbf{G}_{\mathcal{A}^{c},\mathcal{A}^{c}}-\mathbf{G}_{\mathcal{A}^{c}, \mathcal{A}}\left(\mathbf{G}_{\mathcal{A},\mathcal{A}}\right)^{-1}\mathbf{G}_ {\mathcal{A},\mathcal{A}^{c}}\right]. \tag{6}\]  
Thus, in principle, we have already provided a solution to the systematic encoding problem for any PAC code. However, the complexity of solving the systematic encoding problem by computing \(\mathbf{x}_{\mathcal{A}^{c}}\) using (6) involves \(\mathcal{O}((N-K)^{2})\) arithmetic operations (additions and multiplications in \(\mathbb{F}_{2}\)), which may be prohibitively complex for many applications. In the rest of this section, we develop a low-complexity systematic encoder for PAC codes under the assumption that the data index set \(\mathcal{A}\) is chosen so that \(\mathbf{L}_{\mathcal{A}^{c},\mathcal{A}}=\mathbf{0}\) is satisfied.