# A Modified KNN Algorithm for High-Performance Computing on FPGA of Real-Time m-QAM Demodulators
## 3 Modified KNN Algorithm to Reduce Operations in M-Qam  
The implementation of the KNN algorithm presented in the previous section can be modified to take advantage of the symbol geometric distribution seen in a constellation diagram. QAM schemes have characteristics that differentiate them from other applications that use the KNN algorithm. In this case, the inputs are symbols represented as a pair of real numbers. The symbols arrive at the receiver in a different position inside constellation. It happens because of noise and distortions in the travel through the channel. The recovery possibility of the symbols depends on how far they are from the initial position. In a successful transmission, we expect the symbols in certain zones of the constellation to consider recoverable. We propose the following hypothesis:  
**Hypothesis (H1)**: _For an input symbol to be correctly classified using the KNN algorithm, it must belong to the cluster-block to which the nearest ideal cluster belongs._  
Moreover, we present the following definition:  
_Cluster-Block_: _It is an 8-connected neighborhood of nine clusters: a central cluster and the eight clusters surrounding it._  
Algorithm 2 shows the modified KNN for m-QAM. The algorithm adds two steps before step 1, seen in Algorithm 1. Step 0.1 calculates the Euclidean distance between the input symbol and the \(m\) clusters of the ideal constellation. According to our hypothesis, the cluster with the closest distance or one of the 8-connected neighbors contains the input symbol label. Because of this, in step 0.2, we carry out the labels corresponding to the cluster-block. In this modified KNN algorithm, the training data are organized by labels and and the memory addressing is established to access only the positions corresponding to the selected Cluster-Block. The algorithm considerably reduces operations by using only the training data associated with a cluster-block. Figure 4 shows a square-shaped constellation of size \(m\geq 8\). The cluster-block size varies depending on the constellation position, but we always have a size of 4 clusters for the blocks at the corners, 6 clusters for the blocks at the edges, and 9 clusters for the blocks in the center of the constellation. The figure shows an example of the application of cluster-blocks on a constellation diagram for 16-QAM. It also follows that for constellations without corners, we would have values of 5 and 8 clusters for the blocks near the corners. The other sizes are 6 and 9 clusters, as in the constellations with corners. Figure 3: Sort Distances and Calculate Mode CuPUs by processing N symbols. The labels are copied N times to be operated in parallel. The algorithm reduces the \(L\) training data in Calculate Distance CuPU and Sort Distance CuPU. In this case, we express the total length of training data as \(L=Lc\times m\), where \(L_{c}\) is the length of the training data for a cluster, and remember that \(m\geq 8\). In this way, \(L\) is much bigger than the number of training data for the biggest cluster-block. Calculate Mode CuPU depends on the value of \(K\), and the reduction in \(L\) does not affect it, but this CuPU is the least amount of operations performed within the KNN algorithm because it assumes \(K<<L\). Algorithm 2 implementation on FPGA uses the CuPUs as in Algorithm 2, but with a smaller training data length due to reduction of operations, as described in this section, i.e., we propose the implementation of the modified KNN algorithm using a scalable multicore architecture to process the input symbols in parallel, as in Algorithm 1. The CuPUs were implemented with optimization directives to increase the concurrency of operations within each processing unit. Figure 5 shows the architecture of the algorithm for the modified KNN. A new processing unit is attached to performs the Cluster-Block assignment to the input symbols. This block measures the distance to the ideal constellation and selects the training data taking only those belonging to the Cluster-Block.