Turbo kodlar için serpiştirici tasarımı
Interleaver design for turbo codes
Yazar: FERKAN YILMAZ
Danışman: PROF. DR. ÜMİT AYGÖLÜ
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı / Elektronik ve Haberleşme Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2002
Konu: Elektrik ve Elektronik Mühendisliği = Electrical and Electronics Engineering
Dizin: Hata başarımı = Error performance ; Hata düzeltme = Error correction ; Kablosuz uygulama protokolü = Wireless application protocol ; Kod çözme = Decoding ; Turbo kodlama = Turbo coding

Özet:
TURBO KODLAR İÇİN SERPIŞTİRİCİ TASARIMI ÖZET Günümüz iletişim sistemlerinde yüksek kalitede sayısal veri iletimine giderek artan bir gereksinim vardır. Son yıllarda veri iletimini sayısal olarak gerçekleyen iletişim sistemleri giderek yaygınlaşmaktadır. Sayısal işaretlerin en önemli özelliği gürültülü kanallara analog işaretlere göre daha uygun olmalarıdır. Alıcı, sayısal işaretlerin yalnızca 0 ya da 1 olmasıyla ilgilendiğinden gürültünün kuvvetli olmadığı ortamlarda hata yapma oranı küçüktür. Hata düzeltme kodlan iletilen bilginin doğruluğunu ve verimliliğini antırmak için kullanılır. Bir iletişim sisteminde, veri vericiden alıcıya bir iletim ortamında veya kanalda iletilmektedir. Kanal genellikle iletilen verinin içinde bit hatalarına neden olan sönümlemeden ve gürültüden etkilenmektedir. Hata düzeltme kodlan kanaldan kaynaklanan bit hatalannı düzelştmek için kullanılan bir tür işaret işleme tekniğidir. Bu işlem, verinin kodlanması ve kodlanan veriye eşlik bitlerinin eklenmesiyle gerçekleştirilir. Bu işlem sonucunda kod çözücü iletilen veriyi eşlik bitlerini ve tanımlanan kodlama biçimini kullanarak tekrar elde edebilmektedir. Kodlama tekniğindeki en büyük kaygı güvenilir bir iletişim sağlayabilmek için hatalann kontrolünün sağlanmasıdır. Son yıllarda turbo kod adlı çok ilgi çekici ve çok önemli bir kodlama tekniği geliştirilmiştir. Bu kodlama tekniğiyle iletişim kanalının Shanon sımnna yakın bir hata başanmım elde etmek mümkün olmaktadır. Bu kodlama tekniğinin bu kadar ilgi görmesinin en önemli nedeni budur. Turbo kodlama yapısında, turbo kodlayıcı en az iki tane sistematik katlamalı kodlayıcının bir serpiştirici sayesinde paralel olarak bağlanmasından oluşur. Burada sistematik katlamalı kodlayıcılara bileşen kodlayı denir. Sonlu uzunluklu sayısal bilgi dizisi birinci bileşen kodlayıcıyla kodlanır fakat bu sonlu uzunluklu bilgi disizi ikinci bileşen kodlayıcıya girmeden önce serpiştirilir ve sonra ikinci bileşen kodlayıcı tarafından kodlanır. Burada serpiştiri, kod sözcüğü yapısı üzerinde değişiklik yapmak amacıyla değilde bilgi dizisi üzerinde simgelerin yerlerini değiştirmek amacıyla kullanılmıştır. Serpiştiricinin uzunluğu sayısal bilgi dizisinin uzunluğuna eşittir. Turbo kodun band verimliliğini arttırmak için her bileşen koldayıcının çıkışla rı deliklenebilir. Sayısal bilgi dizisinin kodlanmasından sonra her bileşen kodlayıcının durumları sıfıra getirilmelidir. Böylece alıcı ile verici arasında eş zamanlı uyum sağlanabilecektedir. Turbo kodlayıcındaki serpiştiricinin varlığı turbo kod çözme yapısının karmaşıklığını çok fazla arttırmaktadır. Turbo kod çözücüde yumuşak kararlı kod çözücülere (YGYÇ) ihtiyaç vardır. Eğer turbo kod çözücü yapısında iki tane YGYÇ varsa, hata patlamalarını önlemek için bu YGYÇ kod çözücüler birbirlerine bir serpiştirici ve bir ters serpiştirici ile kaskad olarak bağlanmışlardır. Serpiştiriciler sayesinde aynı bilgi dizisi için elimizde iki tane Markov süreci elde edilmiş olur. YGYÇ kod çözücülerden her biri bir Markov bilgi dizisi ile XVilgilenmekte ve diğerlerinden bağımsız olarak simgelerin kestirimini yapmaktadır. Kestirim işlemleri sonucunda elde ettiği bilgileri bir sonraki YGYÇ kod çözücüye göndermektedir. Bir sonraki YGYÇ kod çözücünün kullanması için gönderilen bilgi bloğuna önsel bilgi denmektedir. Her YGYÇ'nin kestirimlerinin olduğu bilgi bloğuna ise yönsel bilgi denmektedir. Turbo kod çözme yapısında, YGYÇ kod çözücüsünde MAP algoritması veya ŞOVA algoritması kullanılabilir. ŞOVA, yumuşak girişli yumuşak çıkışlı viterbi algoritmasıdır. Turbo kod çözücü yapısı için her iki algoritma kullanılabilmesine rağmen, MAP kod algoritmasını kullanan turbo kod çözücünün hata başanmının ŞOVA algoritmasını kullanan turbo kodun hata başanmından daha iyidir. ŞOVA algoritması kod sözcüklerinin hatalı olup olmadığıyla ilgilenirken, MAP algoritması ise durum geçişlerine göre blok içindeki her bir simgeyle ilgilenir. Bunun doğal sonucu olarak, ŞOVA algoritmasını çerçeve hata olasılığım (FER) düşürürken, MAP algoritması bit hata olasılığım (BER) düşürmektedir. Bu tezde, matrisi (1, 5/7)s olan MAP algotirmasını kullanan turbo kodlarla ilgilenilmiştir. Turbo kodların başaranım etkileyen en önemli faktör kullanılacak olan serpiştiricinin yapısıdır. Turbo kodun hata başaranını iyileştirmek için serpiştiriri oluşturma yöntemleri geliştirilmiştir. Oluşturma yöntemlerine göre serpiştiriciler raslantısal ve cebirsel serpiştiriciler olarak iki kışıma ayrılmıştır. Literatürde, turbo kodların hata başaranlarını iyileştirecek serpiştirme yöntemleri geliştirilmiştir. Bu geliştirilen serpiştiricilerin farklı blok uzunlukları için hata başaranlarının değiştiği görülmüştür. Bunun sonucunda, küçük ve büyük blok uzunlukları için farklı serpiştirme yöntemleri geliştirilmiştir. Rasgele serpiştiriri, yan rasgele serpiştiriri, blok serpiştiriciler, sarmal serpiştiriciler, ilişki serpiştiricileri küçük blok uzunlukları için geliştirilen bu serpiştiricilerden bir kaçıdır. Bu tezde, küçük, orta ve büyük blok uzunlukları için turbo kodlarda kullanılabilecek olan bir karma serpiştiricisi önerilmiştir. Karma serpiştiriri bazı özellikleri açısından raslantısal serpiştiricilere, bazı özellikleri açısından da cebirsel serpiştiricilere benzemektedir. Karma serpiştiricinin üstünlüklerini ortaya koymak amacıyla yapılan bilgisayar benzetimlerinde turbo kodun kodlama oranı R = 1 / 3 olarak seçilmiştir. Karma serpiştiriciler sayesinde serpiştiriri B blok uzunluklu ardışıl dizinin simgelerini diğer serpiştiriri türlerinden daha iyi serpiştirmektedir. Kısaca karma serpiştiricilerin serpiştirme yetenekleri diğer serpiştiricilerin serpiştirme yeteneklerinden daha iyidir. Bundan dolayı, karma serpiştiriciler, hata patlamannna karşı bitlerin birbirlerinden " daha iyi uzaklaştırmaktadır. Karma serpiştiriri girişinde B blok uzunluklu simge dizisini uzunluğu K < B olan alt bloklara ayırmakta ve bu blokları kendi aralarında sarmal serpiştiriri yöntemiyle serpiştirmektedir. Bir sonraki aşamada ise sırasıyla her K uzunluklu alt bloklardan simgeler rasgele seçilir. Böylece simgeler birbirlerinden daha iyi serpiştirilmektedir. Büyük blok uzunlukları için karma serpiştiricilerin hata başaranlarını iyileştirmek için K alt blok uzunluğu K > - olacak şekilde seçilmelidir. Bu koşulla serpiştiricinin B blok uzunluğu büyüdükçe K alt blok uzunluklarmmda büyümesi sağlanmaktadır. K alt blok uzunluğu büyüdükçe karma serpiştiricinin simgeleri serpiştirme yeteneği artmaktadır. Karma serpiştiriciler küçük blok uzunlukları için en kötü hata başanmı, içinde barındırdığı cebirsel serpiştiricinin hata başaranına eşittir. En kötü durumda alt xvıblok uzunluğu K = 1 olmaktadır. Bu durumda karma serpiştiriri cebirsel serpiştiriciye dönüşmekte ve hata başarımı küçük blok uzunlukları için yine iyi kalmaktadır. B = 20 blok uzunluğu için karma serpiştiririnin (5x4) matrisli sarmal serpiştiriciyi kullandığı durumda alt blok uzunluğu K = 1 olmaktadır. Bu durumda karma serpiştiririnin hata başarımı (5x4) matrisli cebirsel serpiştiririnin hata başanmına eşit olmaktadır. B blok uzunluğu büyüdükçe K alt blok uzunluğuda büyümektedir. B = 3000 için (5x4) matrisli sarmal serpiştiriciyi kullanan karma B 3000 serpiştiririnin alt blok uzunluğu K = = = 150 olmaktadır. Ardışıl bir dizinin karma serpiştirmeden geçirilmesiyle her hangi iki simge arasındaki minimum uzaklık S = K = 150 ile sınırlanmıştır. Burada S simgelerin serpiştirilmesinden sonra aralarındaki minimum uzaklığı ifade etmektedir. Bu minimum uzaklık yan rasgele serpiştiriri için S = J- = J «38 olmaktadır. (60x50) sarmal serpiştiricisini kullanan serpiştiriri için S = 50 olmaktadır. Verilen bu S değerlerinden görüldüğü gibi bu tezde geliştirilen karma serpiştiricisinin serpiştirme yeteneği diğer serpiştirilerin serpiştirme yeteneğinden daha iyidir. Karma serpiştiricilerin serpiştirme yeteneğinin iyi olmasının doğal sonucu olarak bu serpiştiriri türünün hata başanmlan diğer serpiştiricilerin hata başaranlarından daha iyidir. Örneğin, 2dB işaret gürültü oranı için (60x50) matrisli sarmal serpiştiririnin bit hata olasılığı 4x1 0"5, B = 3000 blok uzunluklu rasgele serpiştiririnin bit hata olasılığı 2x1 0"6, (5x4) matrisli sarmal serpiştiriciyi kullanan ve alt blok uzunluğu K = 150 olan karma serpiştiririnin bit hata olasılığı ise 3.5xl0"7'dir. TC YÜKSEKMRFrtM KDftOUr MHdTMAffiASVUN M£BKKZt XV11

Abstract:
INTERLEAVE!* DESIGN FOR TURBO CODES SUMMARY There is a growing need for reliable transmission of high quality digital data in communication systems. In recent years, the number of communication systems that treat signals as a digital data is rapidly increasing. One of the important characteristics of digital systems is that they are more reliable in noisy environment than analog systems. In receiver, since the detector for digital data may only decide whether each symbol is a 0 or 1, digital symbols can often be detected perfectly provided that the noise is weak. The aim of a communication system is to provide a reliable communication in a noisy transmission channel. The objective of such a system is to remove the barriers that limit the reliable transmission at both ends of communication link. These systems are both power and band limited. In a power-limited environment, the desired system performance should be achieved with the smallest possible power. One solution is the use of error-correcting codes, which increase the power efficiency by adding extra bits to the transmitted symbol sequence. This procedure requires the modulator to operate at a higher data rate and hence requires a larger bandwidth. In a bandwidth-limited environment, increased efficiency in frequency utilization can be obtained by choosing higher-order modulation schemes, but a larger signal power would be needed to maintain the same signal separation and hence the same error probability. When both limitations are imposed simultaneously, it is most often not possible to achieve the desired throughput with either technique acting alone. Error corrective coding is used to enhance the efficiency and accuracy of information transmitted. In a communication system, data is transferred from a transmitter to a receiver across a physical medium of transmission or channel. The channel is generally affected by noise or fading which introduces errors in the data being transferred. Error-correcting code is a signal processing technique used for correcting errors introduced in the channel. It is done by encoding the data to be transmitted and introducing redundancy in it such that the decoder can later reconstruct the original data transmitted using the redundant information. The information source is a digital source. If it is not, it will be converted to digital. The digital source output is sent to an encoder to generate encoder output that is modulated and then transmitted over the physical channel. The decoder will make a best guess of the original information based on the received signal that is distorted by the channel. Major concern in coding technique is the control of errors so that reliable communications can be obtained. There are many coding schemes available. Turbo code is the most exciting and potentially important development in the coding theory in recent years. This powerful code is capable of achieving near Shannon capacity performance. xvmIn turbo coding scheme, the turbo encoder is a parallel concatenation of at least two recursive systematic convolutional encoders, called the constituent encoders. The digital information block, which has a finite length, is encoded by the first constituent encoder, but interleaved before it enters the other constituent encoders. Here, the interleaver operates on an information sequence, and not on code sequence. The interleaver size equals to block length. The output of the constituent encoders is punctured to increase the spectral efficiency. At the end of that encoding digital information block is encoding, all the constituent encoders in turbo encoders have to be terminated to provide synchronization between two ends of communication link. In another words, since the output of each constituent recursive systematic convolutional (RSC) encoder of a turbo code depends only on the last input bit (as well as a convolution operation), the encoding process of a turbo code can be considered as two joint Markov processes. In turbo decoding scheme, the presence of the interleaver in the structure of the turbo encoder adds a considerable amount of complexity to the decoding process required to obtain the information bits at the receiver. There are at least two soft input-soft output (SISO) decoders. If there are two SISO decoders in the turbo decoder, these two SISO decoders are connected to each other by one interleaver and one deinterleaver to prevent burst errors. Since the two Markov processes run on the same input data, turbo decoding can proceed by first independently estimating each process, then refining the estimates by iteratively sharing information between both decoders. This means that the output of one decoder can be used as a-priori information by the other decoder. In order to take advantage of this iterative decoding scheme, it is necessary for each decoder to produce soft-bit decisions, which are usually in the form of log-likelihood ratios (LLRs). The LLR serves as a priori information that informs on the probability that a transmitted message bit is a one rather than a zero. The inputs to the SISO decoder consist of systematic information, parity information, and the a priori information from the previous decoder, while the output is the LLR. Decoding commences when the first decoder receives the first encoder's parity bit and the systematic channel observations, as well as the a priori information derived from the second decoder's output. During the first iteration, since the second decoder has not produced any information, the a priori information is set to zero. The first decoder then produces the output LLR from which the extrinsic information is derived by subtracting the weighted systematic and a priori inputs of the first decoder. The extrinsic information is then interleaved to provide a priori information for the second decoder, which also receives the interleaved systematic observation and the parity bits of the second encoder. In the same way as for the first decoder, the extrinsic information is also derived from the LLR produced by the second decoder, after which it is deinterleaved before serving as a priori information for the first decoder. After the assigned number of iterations, the message bits are estimated by making a hard decision on the deinterleaved output of the second decoder. In turbo decoding scheme, two well-developed and widely used algorithms for determining the state sequence of a trellis encoder are the Viterbi algorithm (SOVA) and the maximum a posteriori (MAP) algorithm. The Viterbi algorithm is widely used for decoding of convolutional codes, but variants of the MAP xixalgorithm are more suitable for turbo-code decoding. Given the received observation sequence, the Viterbi algorithm determines the most probable state sequence. This implies that, the states estimated by the Viterbi algorithm will always form a connected path through the trellis. The MAP algorithm, on the other hand, attempts to determine each state transition, without regard to the overall sequence of the trellis. In the case of the MAP algorithm, the resulting trellis solution may contain discontinuities. On the basis of performance comparisons, it has been observed that the SOVA results in minimizing frame error rate (FER), while the MAP algorithm minimizes the bit error rate (BER). For this thesis, we will only focus on the MAP algorithm whose matrix is (1,5/ 7)8. To get a better performance, the main important part of turbo coding is the interleaver. Since changing its structure cause the performance of turbo coding to be better of worse, quite an effort in literature has been made to find good interleaver designs. Most of these efforts have been directed towards finding interleavers that result in codes with better distance spectra. There are previously proposed interleaver designs that give good iterative decoding performance, such as helical interleaver, block interleaver, random interleaver, and semi random interleaver. Superior performance of turbo codes compared to convolutional codes is only achievable when the length of interleaver is very large in the order of thousand bits. For large block size interleaver, most of random interleavers can perform well and it's not necessary to make any effort in the design of the interleaver. However, when the length of the interleaver is short, the performance of the turbo codes degrades substantially up to a point that its bit error rate (BER) performance is worse than conventional convolution codes. In many applications such as voice, delay is an important issue in choosing a coding scheme. For these applications, large block size interleavers used in turbo codes are not appropriate. Therefore, it is necessary to design an interleaver for turbo code that demonstrates good BER performance. Several authors have suggested interleaver design for turbo codes suitable for short and large block length to take the advantage of coding gains that turbo code offer. In this thesis, a new interleaver design method usable with turbo codes for short and large block size is proposed, and named as hybrid interleaver. Hybrid interleaver has not only the characteristics of the most random interleaver such as random interleaver, semi-random interleaver but also the characteristics of algebraic interleavers such as helical interleaver, block interleaver. Therefore, the interleaver designed with this method gives better bit error rate (BER) performance not only for short block size but also large block size. In computer simulation program written to indicate the superior performance of the hybrid interleaver, the coding rate of turbo coding is selected as R = 1/3. By the means of the hybrid interleaver, sequential bits are separated better each other after interleaving. Briefly, because of the fact that the interleaving ability of the hybrid interleaver is better than the interleaving ability of other interleaver, the hybrid interleaver provides better protection to information bits against burst errors occurred during transmission of information bits through communication channel. During interleaving, Hybrid interleaver divides B block sized sequential symbols into K < B sub-block sized sequential symbols and interleaves these sub-blocks. In next stage, symbols are randomly and successively selected from each sub block. To provide better performance for large block size, the length of sub-block should xxbe selected to provide the condition K> -. Thus, The length of sub-block is ^ 20 guarantied to be enough large to have the characteristics of the most random interleaver by the fact that B block length of interleaver is getting bigger. For short block size, the worse performance of hybrid interleaver is surprisingly equals to the performance of the algebraic interleaver it used in its interleaving structure. In worse situation, by the fact that the length of sub-block is K = 1, hybrid interleaver rums into the form of algebraic interleaver, so its performance is still better for short block size because algebraic interleaver has better performance for short block size. For large block size, the most random interleavers are generally used to get a better performance in turbo coding. But due to the better interleaving ability of hybrid interleaver, hybrid interleaver has more achievement in error correcting than other interleavers. To improve the interleaving ability of hybrid interleaver, the length of sub-block should be enough large in the conditions K < B and K > -. For 20 SNR = 2dB symbol noise ratio, the Bit error rate (BER) of the helical interleaver using (60x50) matrix is nearly 4xl0"5, the BER of random interleaver whose block size is B = 3000 is nearly 2x1ü"6, the BER of hybrid interleaver using helical interleaver with (5x4) matrix for B = 3000 block size is nearly 3.5xl0"7. xxi