Geri Dön

High-speed bidirectional fano algorithm implementation

Yüksek süratli ve çift yönlü fano algoritma uygulaması

PDF İndir

  1. Tez No: 365702
  2. Yazar: ÖZGÜR ATEŞ
  3. Danışmanlar: PROF. DR. TAŞKIN KOÇAK
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Elektrik ve Elektronik Mühendisliği, Computer Engineering and Computer Science and Control, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2014
  8. Dil: İngilizce
  9. Üniversite: Bahçeşehir Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 93

Özet

Bu tezin konusu, yüksek süratli ve çift yönlü Fano algoritmasının C ve CUDA dillerinde uygulanmasıdır. Kısa adı BFA olan çift yönlü Fano algoritması, yüksek süratte evrişimli kod çözmede kullanılır. Bu, simültane bir biçimde ileri ve geri kod çözme algoritmasıdır. WirelessHD gibi modern kablosuz dijital iletişim araçları yüksek hız gerektirir. İşte bu yüksek BFA hızı için, CUDA ile paralel işlem yapabilecek bir ana bant işlem birimi kullanılabilir. Bu tezde, CUDA ile BFA'nın 4.4Gbps'lik bir hıza erişmesi sağlanıyor. Her kod ayrı bir thread kullanılarak çözülüyor. Her adımda bir thread başlangıçtan sona doğru kod çözüyor, ardından da sondan başa doğru. 3.1Gbps hızındaki diğer bir BFA kod çözümünde ise her kod için çift thread kullanılıyor. Burada da bir thread başlangıçtan sona doğru, öbür thread sondan başlangıca doğru kod çözüyor. UFA, aynı GTX650 cihazında 5.0Gbps hızına ulaşabiliyor. BFA'nın yavaşlığının, UFA'ya daha fazla hafıza kullanmasından ve ek kontrol mekanizmalarından kaynaklandığını düşünüyoruz. Ancak, BER, NoI ve TpI analizlerinden BFA için daha iyi sonuçlar elde edilebiliyor. Bundan da anlaşılan şu ki BFA daha yavaş olmasına karşı UFA'dan daha verimli kod çözüyor. Bu hızlara ulaşabilmek için metrik, çıkan değer v.b. hesap yerine taramalı tablo kullanımı gibi bazı optimizasyonlar yapıldı. Bir başka yöntem, bir önceki sekiz adımı hafızada tutmak için klasik bir dizi yerine indeksli çember sıra kullanmak oldu. Xu et al. (2009) tarafından yapılan BFA araştırmasının simülasyonu MATLAB'da yapılmıştı. Başka bir simülasyon da FPGA'da 100Mbps hızında olmuştu. Bu tezde, CUDA ile birkaç Gbps hızında BFA araştırması simülasyon yapmayı hedefliyoruz. Xu ve Koçak (2010) tarafından yapılan araştırmada ileri ve geri kod çözücülerinin birleşmesinin kontrol edilmesinde taramalı tablo kullanılmasını önermişti. Bu tezde de metrik, çıkan değer v.b. hesap yerine taramalı tablo okuma yapılmış; üstelik bu hem UFA hem BFA için uygulanmıştır.

Özet (Çeviri)

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.

Benzer Tezler

  1. Tez No

    286122

    A bidirectional LMS algorithm for estimation of fast time-varying channels

    Zamanla hızlı değişen kanalların kestirimi için iki yönlü LMS algoritması

    YAVUZ YAPICI

    Doktora

    İngilizce

    İngilizce

    2011

    Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik Üniversitesi

    Elektrik ve Elektronik Mühendisliği Bölümü

    DOÇ. DR. ALİ ÖZGÜR YILMAZ

  2. Tez No

    391913

    Taşınabilir bilgisayar sistemleri için çift yönlü USB beslemeli, yüksek verimli yüksek hızlı pil dolduruculu besleme sistemi

    USB powered and bidirectional, high efficiency power supply with high speed battery charger for embedded computer systems

    LEVENT YAVAŞ

    Yüksek Lisans

    Türkçe

    Türkçe

    2014

    Elektrik ve Elektronik MühendisliğiSüleyman Demirel Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    DOÇ. DR. SELÇUK ÇÖMLEKÇİ

  3. Tez No

    828672

    İmplant üretim toleransının implant-abutment arası mikro aralık ve sızdırmazlığa olan etkisinin değerlendirilmesi

    Evaluation the effect of implant manufacturing tolerance on microgap and microleackage between implant-abutment

    ÖVGÜ ÖZYÜREK

    Diş Hekimliği Uzmanlık

    Türkçe

    Türkçe

    2022

    Diş HekimliğiEge Üniversitesi

    Periodontoloji Ana Bilim Dalı

    PROF. DR. NEJAT NİZAM

  4. Tez No

    859785

    Dikgen olmayan çoklu erişim tabanlı 5G ve ötesi haberleşme sistemlerinin başarım analizi

    Performance analysis of non-orthogonal multiple access-based 5G and beyond communication systems

    İNCİ UMAKOĞLU

    Doktora

    Türkçe

    Türkçe

    2024

    Elektrik ve Elektronik MühendisliğiKütahya Dumlupınar Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MUSTAFA NAMDAR

    DR. ÖĞR. ÜYESİ ARİF BAŞGÜMÜŞ

  5. Tez No

    720163

    Şebekeye bağlı üç fazlı sic tabanlı hibrit anpc evirici yapısının kontrolü ve tasarımı

    Control and design of the grid connected three-phase sic based hybrid npc inverter

    İSLAM DELİBAŞ

    Yüksek Lisans

    Türkçe

    Türkçe

    2022

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektrik Ana Bilim Dalı

    DOÇ. DR. MURAT YILMAZ

    DR. ÖĞR. ÜYESİ DENİZ YILDIRIM

    DOÇ. DR. ATİYE HÜLYA OBDAN

Geri Dön