# Systematic Encoding and Shortening of PAC Codes
## 2 PAC Codes
This condition is not as restrictive as it may appear since it is satisfied by the preferred choices for the data index set \(\mathcal{A}\), such as when \(\mathcal{A}\) is chosen according to a polar coding design rule or a Reed-Muller design rule [1]. For clarity, we restate the systematic encoding problem considered in the rest of this section as follows. Given a data word \(\mathbf{d}\in\mathbb{F}_{2}^{K}\) and a data index set \(\mathcal{A}\) for which \(\mathbf{L}_{\mathcal{A}^{c},\mathcal{A}}=\mathbf{0}\), find a codeword \(\mathbf{x}\in\mathbb{F}_{2}^{N}\) so that  
\[\mathbf{x}=\mathbf{v}\mathbf{T}\mathbf{L},\quad\mathbf{v}_{\mathcal{A}^{c}}= \mathbf{f},\quad\mathbf{x}_{\mathcal{A}}=\mathbf{d}. \tag{7}\]  
The systematic encoding problem (7) can be solved by a method consisting of the following three steps. (i) Generate an auxiliary word \(\mathbf{c}\in\mathbb{F}_{2}^{K}\) by computing \(\mathbf{c}=\mathbf{d}\left(\mathbf{L}_{\mathcal{A},\mathcal{A}}\right)^{-1}\). (ii) Compute a convolution input-output pair \((\mathbf{v},\mathbf{u})\) so that  
\[\mathbf{u}=\mathbf{v}\mathbf{T},\quad\mathbf{u}_{\mathcal{A}}=\mathbf{c}, \quad\mathbf{v}_{\mathcal{A}^{c}}=\mathbf{f}. \tag{8}\]  
(iii) Obtain the systematic codeword by computing the polar transform \(\mathbf{x}=\mathbf{u}\mathbf{L}\). The second and third steps ensure that \(\mathbf{x}=\mathbf{v}\mathbf{T}\mathbf{L}\), with \(\mathbf{v}_{\mathcal{A}^{c}}=\mathbf{f}\). Therefore, \(\mathbf{x}\) is a codeword in the PAC code. Moreover, we have  
\[\mathbf{x}_{\mathcal{A}}=\mathbf{u}_{\mathcal{A}}\mathbf{L}_{\mathcal{A}, \mathcal{A}}+\mathbf{u}_{\mathcal{A}^{c}}\mathbf{L}_{\mathcal{A}^{c}, \mathcal{A}}=\mathbf{c}\mathbf{L}_{\mathcal{A},\mathcal{A}}=\mathbf{d},\]  
since \(\mathbf{L}_{\mathcal{A}^{c},\mathcal{A}}=\mathbf{0}\), \(\mathbf{u}_{\mathcal{A}}=\mathbf{c}\), and \(\mathbf{c}=\mathbf{d}\left(\and let \(\mathbf{A}=\mathbf{L}\) and \(\mathbf{B}=\mathbf{L}^{-1}=\mathbf{L}\). Therefore, we have \(\mathbf{c}=\mathbf{d}(\mathbf{L}_{\mathcal{A},\mathcal{A}})^{-1}=\mathbf{d} \mathbf{L}_{\mathcal{A},\mathcal{A}}\). Now, prepare a vector \(\mathbf{x}^{\prime}\in\mathbb{F}_{2}^{N}\) by setting \(\mathbf{x}^{\prime}_{\mathcal{A}}=\mathbf{d}\) and \(\mathbf{x}^{\prime}_{\mathcal{A}^{c}}=\mathbf{0}\), apply a polar transform \(\mathbf{u}^{\prime}=\mathbf{x}^{\prime}\mathbf{L}\), and extract \(\mathbf{c}\) from \(\mathbf{u}^{\prime}\) by setting \(\mathbf{c}=\mathbf{u}^{\prime}_{\mathcal{A}}\). This yields the desired result since  
\[\mathbf{u}^{\prime}_{\mathcal{A}}=\mathbf{x}^{\prime}_{\mathcal{A}}\mathbf{L}_ {\mathcal{A},\mathcal{A}}+\mathbf{x}^{\prime}_{\mathcal{A}^{c}}\mathbf{L}_{ \mathcal{A}^{c},\mathcal{A}}=\mathbf{d}\mathbf{L}_{\mathcal{A},\mathcal{A}}.\]  
**Proposition 4**: _The system of equations (8) in the second step of Proposition 2 can be solved by a sequential method of complexity \(\mathcal{O}(mN)\) for a PAC code with a convolution impulse response \(\mathbf{g}=(g_{0},g_{1},\ldots,g_{m})\) (where \(g_{0}\
eq 0\) by definition of PAC codes)._  
Proof: To develop a sequential method that solves (8), we begin by rewriting the convolution Equation (1) as follows  
\[u_{i}=g_{0}v_{i}+g_{1}v_{i-1}+\cdots+g_{m}v_{i-m}=v_{i}+s_{i},\quad i=1,2, \ldots,N \tag{9}\]  
where we used \(g_{0}=1\) and have defined \(s_{i}=g_{1}v_{i-1}+\cdots+g_{m}v_{i-m}\) as an \(i\)th feed-forward variable. Please also note that in (9), we have used the convention that \(v_{j}=0\) for \(j<1\). Observe that, for each \(1\leq i\leq N\), either \(i\in\mathcal{A}\) or \(i\in\mathcal{A}^{c}\). In the former case, we obtain \(u_{i}\) from the constraint \(\mathbf{u}_{\mathcal{A}}=\mathbf{c}\); in the latter case, we obtain \(v_{i}\) from \(\mathbf{v}_{\mathcal{A}^{c}}=\mathbf{f}\). Given the value of one of the elements of the pair \((v_{i},u_{i})\), the other can be found from the relation \(u_{i}=v_{i}+s_{i}\). Also, observe that \(s_{i}\) depends only on the knowledge of \((v_{1},v_{2},\ldots,v_{i-1})\).