Design of high performance low latency rateless codes

Abstract

İkili silme kanalları için tanımlanan Luby dönüşüm kodları bilim camiasında var olanilk oransız kodlardır. Bu kodların kodlayıcı kısımları veri paketlerinin rasgele birşekilde seçilerek birleştirilmesi mantığına göre hareket eder. Veri paketleri ise rasgeleolarak belli bir dağılıma göre üretilen sayılara göre yapılırlar. Oransız kodların alıcıtarafındaki çözümlenme başarıları bu kodların gönderici tarafında çözümlenebilirşekilde kodlanmalarına bağlı olmaktadır. Eğer kodlama tasarımı etkili bir şekildeyapılmazsa alıcı tarafında başarılı çözümleme yapılamaz ve veri paketleribirbirlerinden ayırt edilemez. Alıcı tarafında derecesi bir olan kod sözcüğü çözümlemeişleminin herhangi bir anında bulunamazsa çözümleme işlemi devam etmez, veçözümleme işlemine son verilir. Bu da o andan itibaren sonraki veri paketlerinin eldeedilememesi demektir. Bu tez çalışmasında çözümleme işlemi esnasında derecesi birolan kod sözcüğü bulunmaması durumunda çözümleme işlemine devam edebilmekiçin bir yöntem öneriyoruz. Önerilen yöntemle çözümleme esnasında meydana gelen tıkanmalar giderilerek çözümleme işlemine devam edilmesi sağlanmaktadır.Bilgisayar benzetimleri ile yapılan çalışmalarda önerilen yöntemin LT kodlarınınperformanslarını arttırdığı görülmüştür. Ve bu performans yükselmesi LT kodlarınınkullandığı derece üretimi için kullanılan dağılımlara bağlı olmadığı görülmektedir.Önerilen yöntem LT-RSD ve LT-MBRSD-BP kodlarına bütünleştirilmiş ve bukodlarda elde edilen performans artışı bilgisayar benzetimleri ile gözlemlenmiştir.Önerilen performans artırım yöntemi karar yayılımı örüntü tanıma ileisimlendirilmiştir. Önerilen yöntem Gaussian elimine karar yayılımı yöntemiylebenzeşimler gösterse de, önerilen yöntemin işlem karmaşıklığı daha azdır. Bu nedenleönerilen yöntemin zaman gecikmesi literatürde var olan Gauss elimine karar yayılımıyöntemine göre daha azdır.LT türü kodlar büyük uzunluklara sahip olan veri dosyaları için iyi performansgöstermektedir. Diğer yandan kısa uzunluktaki veri dosyaları için bu tür kodlarınperformansları iyi olmamaktadır. Bunun ana sebebi kısa uzunluktaki dosyalar içinçözücü tarafında bir dereceli kod sözcüklerinin daha yüksek olasılıklabulunmamalarıdır. Bu tez çalışmasında kod derecelerinin üretimi için deterministik biryöntem öneriyoruz. Önerilen yöntem küçük uzunluktaki veri dosyaları için oldukça iyiperformans göstermektedir. Önerilen deterministik derece üretimi derecelerinperiyodik bir şekilde üretilmesi kuralına dayanmaktadır. Dereceler ?? periyodu ileperiyodik bir şekilde üretimektedirler. Veri dosyası ?? adet pakete bölünüp daha sonraise üretilen dereceler göz önüne alınarak birleştirilmektedirler. Bilgisayar benzetimlerisonucunda elde edilen sonuçlara göre önerilen yöntem rasgele derece üretimyöntemlerine göre daha düşük BER oranlarına, daha küçük başlık bilgisine ve daha azişlem miktarına sahip olmaktadır.

Luby Transform (LT) codes are one of the best rateless codes mainly designed forbinary erasure channel. The characteristics of such codes perfectly performing whenused with bulk data files, however a performance degradation has been observed whenusing them with short length messages. In this thesis, we present a new design forrateless codes, particularly an efficient LT codes using robust soliton distribution(RSD) as a degree generation method and tested in both binary erasure channel (BEC)and noisy channels like the additive white Gaussian noise (AWGN) channel. First, anew proposed decoding technique is defined as belief propagation-pattern recognition(BP-PR) is implemented to enhance the decoding ability of the conventional (BP)algorithm to overcome the problem of losing degree-one coded symbols which causedearly decoding termination. The simulation results approve the improvement of theBP-PR when used with LT-RSD and outperforms the bit error rate (BER) records forthe state of art techniques like memory-based robust Soliton distribution usingconventional BP (LT-MBRSD-BP) or the Gaussian elimination assisted belief propagation (LT-RSD-BP-GE) and improve the records for the BER when used withMBRSD, ISD and optimal degree distribution (ODD), to form the new code called(LT-MBRSD-BP-PR),(LT-ISD-BP-PR) and (LT-ODD-BP-PR) respectively.Second, a new efficient deterministic encoding technique using deterministic degreegenerator with random data selection (LT-DE) is applied for extremely short datalengths. The degree generation method is based on creating the degrees in a repeatedframe with a limited upper value called repetition period (??) and the data symbolsare chosen sequentially from a truncated data file. The data file is truncated to segmentsof length (??) and each segment is chosen based on a random sequence. Testing this(LT-DE) against (LT-RSD-BP-PR), (LT-MBRSD-BP-PR) and (LT-ODD-BP-PR) ina BEC environment had approved the superiority of such code over all the othermentioned techniques. It has the lower error floor and higher successful decoding ratewith minimum overhead and computational cost. The formation of this (LT-DE)associates a mutual relation between the successive coded symbols which motivate usto present a new sequential decoding technique mainly used over (AWGN) channel.With such new encoding-decoding technique LT codes can approach the decodingcomplexity cost of Raptor codes with smaller overhead and less encoding complexityas well.