Browsing by Author "Ateş, Özgür"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    High-speed bidirectional fano algorithm implementation
    (Bahçeşehir Üniversitesi Fen Bilimleri Enstitüsü, 2014-01) Ateş, Özgür; Koçak, Taşkın
    This thesis is about the implementation of Bidirectional Fano algorithm (BFA) and Unidirectional Fano algorithm (UFA or conventional Fano algorithm) in C and CUDA. BFA is derived from the Fano algorithm used in high speed convolutional code decoding. It is a simultaneous forward and backward codeword search decoder. The high throughput demanded by the latest wireless digital interfaces like WirelessHD may benefit from a parallel computing specific baseband processing unit that runs BFA at a high speed on CUDA. In this thesis, BFA reached a throughput of 4.4Gbps in CUDA with a single thread per codeword. Its iteration is characterised by one thread decoding first forward then backward. Another BFA decoding at 3.1Gbps was performed using dual threads per codeword. One thread is a forward decoder while the other is a backward decoder. Finally, on the same board, GTX650, UFA was found to have 5.0Gbps of throughput. It was concluded that additional memory transactions and check conditions were the source of throughput loss of BFA in comparison to UFA. However, BER, NoI and TpI analysis gave improved results for BFA, meaning that it decoded more efficiently than UFA. In order to obtain such throughputs, several optimization measures were taken such as the use of look-up tables instead of metric, output bit, state calculations. Another technique was to use an indexed circular queue to hold the previous eight steps in memory instead of using a conventional array. This thesis proposes BFA implementation in CUDA application as a complement to the research done by Xu et al. in 2009, in which simulation was conducted in MATLAB. Later, it has been implemented in FPGA at 100Mbps, and here we are aiming a throughput in several Gbps. The research done by Xu and Koçak (2010) proposed the use of LUT for checking merge conditions. LUT were used in this thesis, too, but this time to pre-calculate next metric, state, output bit calculations, and this contribution was applied to both UFA and BFA.