# An Analytic Transform Kernel Derivation Method for Video Codecs
## 2 Proposed Common Sparse Unified Matrix
### Permutation Matrix (G)  
The permutation matrix **G** plays a crucial role in the derivation of the DST-7 transform kernel using the proposed grouping algorithm, as mentioned in the previous section. The process of deriving **G** in the proposed method is described in Figure 9, which shows the first group of 16-point DST-7 transform kernels represented with floating-point elements, where \(\textbf{S}_{7,(0,0)}\) is only stored in matrix **Q** in the common sparse unified matrix shown in Figure 1.  
The elements between the consecutive rows in the group are observed with specific patterns that appear based on the characteristics of DST-7 kernels. Figure 10 shows the patterns of the elements in consecutive rows. As shown in Figure 10, elements in the odd column (1 st, 3 rd,... ) of the 0 th row (\(\left[\textbf{S}_{7,(0,0)}\right]_{32}\)) are repeated in the left-half column in the next row. The elements in the right-half column are copied from the elements of even columns (0 th, 2 nd,... ) in the previous row vector in reverse order. Thus, this relation can be described in Equation (21). \[[\textbf{S}_{7,(i,1)}]_{N}=\left[\left(\left[\textbf{S}_{7,(i,1)}\right]_{N/2 }\right)_{L^{\prime}}\left(\left[\textbf{S}_{7,(i,1)}\right]_{N/2}\right)_{R} \right] \tag{21}\]  
Figure 8: Floating-point grouped 16-point DST-7 transform kernel elements. Figure 10: An example of patterns observed between two consecutive row vectors of 16-point DST-7 transform kernel. Figure 9: \(\textbf{S}_{7,(0,0)}\) dependent grouped 16-point DST-7 transform kernel. Based on Figure 7, (21) is the next row vector, composed of two parts, \(\left(\left[\mathbf{S}_{7,(i,1)}\right]_{N/2}\right)_{L}\) and \(\left(\left[\mathbf{S}_{7,(i,1)}\right]_{N/2}\right)_{R}\cdot\left(\left[ \mathbf{S}_{7,(i,1)}\right]_{N/2}\right)_{L}\) and \(\left(\left[\mathbf{S}_{7,(i,1)}\right]_{N/2}\right)_{R}\) represent the left and right halves of \(\left[\mathbf{S}_{7,(i,1)}\right]_{N}\). \(\left(\left[\mathbf{S}_{7,(i,1)}\right]_{N/2}\right)_{L}\) is derived using (22), where elements in the odd column (1 st, 3 rd,...) of the 0 th row (previous row) are selected. \(\left(\left[\mathbf{S}_{7,(i,1)}\right]_{N/2}\right)_{R}\) is derived using (23), where elements in the even column (0 th, 2 nd,...) of the 0 th row (previous row) are selected and substituted in a reverse way. Note that \(\left[\mathbf{S}_{7,(i,i),R}\right]_{N/2}\) denotes the element in the \(k\)-th column and \(j\)-th row vector of the \(i\)-th group for \(N\)-point DST-7. \[\left(\left[\mathbf{S}_{7,(i,1)}\right]_{N/2}\right)_{L} =\left[\mathbf{S}_{7,(i,0),2n-1}\right]_{N/2} \tag{22}\] \[\left(\left[\mathbf{S}_{7,(i,1)}\right]_{N/2}\right)_{R} =\left[\mathbf{S}_{7,(i,0),2n-2}\right]_{N/2} \tag{23}\]  
where \(n\) is the integer value, \(N/2<n>0\). Hence, a change of one element in the row vectors in a group may affect the other elements of the other vector of the same group. Figure 10 shows an example of patterns observed between two consecutive row vectors of the 16-point DST-7 transform kernel. From the patterns, \(\mathbf{G}\) comprising \(-1\), \(0\), and \(1\) can be derived. Figure 11 shows the \(\mathbf{G}\) matrix based on the pattern in Figure 10 for deriving the DST-7 transform kernel. As shown in Figure 11, a smaller \(\mathbf{G}\) can be embedded into a larger \(\mathbf{G}\) with identical patterns of element values. Figure 12 shows an algorithm for obtaining the matrix. Even if the memory size of \(\mathbf{G}\) in Figure 11 accounts for 256 bytes, there can be a case to derive \(\mathbf{G}\) on the fly using the algorithm shown in Figure 12, not using static memory to save \(\mathbf{G}\). Figure 11: An example of \(32-\)point permutation matrix (\(\mathbf{G}\)). As shown in Figure 12, the algorithm comprises two parts for the left column (S0) and right column part (S1) of **G**. First, variables used for the algorithm are initialized and the size (\(N\)) of the kernel matrix to derive is set.