# Systematic Encoding and Shortening of PAC Codes
## 2 PAC Codes
These observations suggest a sequential method for carrying out the second step of Proposition 2. The sequential method begins with \(i=1\) with \(s_{1}=0\). Either \(1\in\mathcal{A}\) and \((v_{1},u_{1})=(c_{1},c_{1})\) where \(c_{1}\) is the first element of the auxiliary word \(\mathbf{c}\); or \(1\in\mathcal{A}^{c}\) and \((v_{1},u_{1})=(f_{1},f_{1})\) where \(f_{1}\) is the first element of the frozen word \(\mathbf{f}\). In either case, we can compute \(s_{2}\) before proceeding to the next step of the sequential method. In general, the \(i\)th step of the sequential method begins with \(s_{i}\) available from the \((i-1)\)th step and one determines the missing element of the pair \((v_{i},u_{i})\) using the relation \(u_{i}=v_{i}+s_{i}\). Thus, this method solves the system of equations (8). The method also provides a proof of existence and uniqueness of the solution. The complexity of the sequential method given above is dominated by the complexity of calculating the feed-forward variables \((s_{1},s_{2},\ldots,s_{N})\). From the definition of \(s_{i}\), it is clear that \(s_{i}\) can be calculated using at most \(m\) multiplications and \(m-1\) additions in \(\mathbb{F}_{2}\). Thus, the overall complexity is \(\mathcal{O}(mN)\). **Remark 1**: _An inspection of the above proof will show that the sequential method of Proposition 4 can be used to solve the system of equations (8) for any IUT matrix \(\mathbf{T}\); the Toeplitz property is not essential._  
The complexity \(\mathcal{O}(mN)\) of the sequential method of Proposition 4 corresponds to a significant savings if \(m\ll N\). If \(m\ll N\) is not true, it may be worth working with the inverse of \(\mathbf{T}\). To discuss this, we first cite a well-known result, see e.g., [6]. **Proposition 5**: _The class of all \(N\)-by-\(N\) IUT Toeplitz matrices form a group under matrix multiplication. Let \(\mathbf{T}\in\mathbb{F}_{2}^{N\times N}\) be an IUT Toeplitz matrix with its first row given by \(\mathbf{g}=(g_{0},g_{1},\ldots,g_{N-1})\in\mathbb{F}_{2}^{N}\). (If \(\mathbf{g}\) has span \(m+1\), then \(g_{i}=0\) for \(m<i\leq N-1\).) Then, \(\mathbf{T}^{-1}\in\mathbb{F}_{2}^{N\times N}\) is an IUT Toeplitz matrix with first row given by \(\mathbf{h}=(h_{0},h_{1},\ldots,h_{N-1})\in\mathbb{F}_{2}^{N}\) where \(h_{0}=(1/g_{0})\) and \(h_{k}=-\frac{1}{g_{0}}\sum_{i=1}^{k}g_{k-i}h_{i}\) for \(k=1,2,\ldots,N-1\)._  
Proposition 5 allows us to recast the convolution problem (8) in an inverted form: Compute a convolution input-output pair \((\mathbf{v},\mathbf{u})\) so that  
\[\mathbf{v}=\mathbf{u}\mathbf{T}^{-1},\quad\mathbf{v}_{\mathcal{A}^{c}}=\mathbf{ f},\quad\mathbf{u}_{\mathcal{A}}=\mathbf{c}. \tag{10}\]The inverted problem (10) has the same form as the original problem (8) with the roles of \(\mathbf{v}\) and \(\mathbf{u}\) reversed. Therefore, it can be solved using the same sequential method described above. There may be an advantage in solving the inverted problem if the span of the first row of \(\mathbf{T}^{-1}\) is shorter than that of \(\mathbf{T}\). For example, let \(\mathbf{T}\in\mathbb{F}_{2}^{16\times 16}\) be an IUT Toeplitz matrix with first row \(\mathbf{g}=(1,1,1,1,0,0,0,0,1,1,0,1,1,0,1,0)\), with a span of 15. The inverse \(\mathbf{T}^{-1}\in\mathbb{F}_{2}^{16\times 16}\) is the IUT Toeplitz matrix with first row \(\mathbf{h}=(1,1,0,0,1,1,0,0,0,0,1,0,0,0,0)\), which has a span of 11. We end this section by noting that for hardware implementations of the convolution operation in PAC encoding (both for systematic and non-systematic cases), one can use shift-register circuits that are commonly used in encoding algebraic codes. In particular, the convolution operation \(\mathbf{u}=\mathbf{v}*\mathbf{g}\) (or, equivalently the transform \(\mathbf{u}=\mathbf{v}\mathbf{T}\)) can be implemented as shown in Figure 2. A version of the same circuit, with the left-most stage eliminated, generates the feed-forward variable \(s_{i}\) at point \(A^{\prime}\) when \(v_{i-1}\) is provided as input at point \(A\).