Uzay-zaman Blok Kodlardan Kutupsal Kodlara Verimli En Büyük Olabilirlikli Kodçözme

Abstract

Disiplinler arası bir araştırma alanı olan kodlama kuramı başta bilgi kuramı ve haberleşme mühendisliği olmak üzere matematik ve bilgisayar bilimleri gibi çeşitli disiplinlerce çalışılmaktadır. Kodlama, güvenilir bir başarımla veri aktarımını gerçekleştiren etkin ve sistematik metotların tasarlanmasının amaçlandığı bir araştırma konusudur. Bilgi kuramının önde gelen uygulama alanlarından olan kodlama kuramı iki önemli başlık altında incelenebilir. Kaynak kodlama ve kanal kodlama olarak adlandırılan bu iki başlık, güncel olarak yoğun bir şekilde çalışılan önemli araştırma konuları olmuştur. Bunlardan bizim ilgilendiğimiz kanal kodlama başka bir ifadeyle hata düzeltme kodlaması kısaca; bir mesajın gürültülü iletişim kanalından daha az hata ile iletimini sağlayan yöntemlerin tasarlanması ve bu yöntemlerin basitçe gerçeklenmesi üzerine odaklanır. Kodlama kuramı ile ilgili kabul edilen en önemli teoremlerden biri kanal kapasitesinin tanımı ile verilmiştir. Öyle ki, basit bir haberleşme sisteminde vericiden gönderilen ve gürültülü bir kanal üzerinden alıcı birime ulaşan bilginin iletimi için güvenilir bir şekilde ulaşılabilecek olan iletim hızı kanal kapasitesi ile sınırlıdır. Bu sınır aşıldığında gerçekleşen iletimin güvenirliliğinden söz edilemez. İletişim ihtiyacının doğası gereği, gürültülü iletişim kanalından olabildiğince güvenilir ve hızlı, başka bir deyişle kanal kapasitesine erişebilen, kodlama yöntemlerinin varlığı gösterilmiş olsa da bu kodların tasarlanması önemli bir problem olarak yoğun bir şekilde araştırılmıştır. Oldukça güncel olarak tanıtılan kutupsal kodlar Shannon kanal kapasitesine ulaştığı ispatlanan ilk kodlama sınıfını tanımlamaktadır. Bu nedenle, kutupsal kodlar ile bu problem çözülmüş ve başta bilgi kuramında olmak üzere oldukça önemli bir gelişme olarak kabul edilmiştir. Kutupsal kodlar ile ulaşılan bu gelişme beraberinde çözülmeyi bekleyen birkaç farklı problemi de ortaya çıkartmıştır. Bu tez kapsamında kodçözme amaçlı bir algoritma çalışması sunulmaktadır. İlk olarak genel bir yaklaşımla optimum kodçözme problemi çeşitli haberleşme sistemleri için irdelenmiş olup problem çözümünün zorluğu tartışılmıştır. Görülmüştür ki bu konuda yürütülmüş olan farklı araştırmalar üstün kodlara ilişkin tasarım yöntemlerinin belirli kodçözme teknikleri altında geliştirilmesine dayanmaktadır. Bu doğrultuda verimli bir optimum kodçözme yöntemi için kod tasarımı çalışmaları etkin bir yaklaşım olarak kabul edilebilir. Literatürde farklı haberleşme sistemleri için önerilmiş olan pek çok optimum olmayan kodçözücü belirli teknolojik kısıtlar altında tasarlanmış olsa da aynı kodçözme yöntemi farklı haberleşme sistemleriyle kullanılabilmektedir. Bu doğrultuda ilk olarak arama ağacı tekniğine dayanan çoklu antenli sistemler için önerilmiş bir koçözücünün kanal kodlama için de kullanılabileceğini gösterebiliyoruz.İlk olarak iyi bilinen uzay zaman blok kodlarına sahip çoklu antenli sistemler için kodlama merkezli en iyi olabilirlikli kodçözme yöntemleri öneriyoruz. Bu amaçla çalışmanın ilk kısmında düşük karmaşıklığa ve düşük kodçözme gecikmelerine sahip kodçözme algoritmaları ele alıyoruz. Bu algoritmalar BLAST sistemler için ayrıştırılmıs ̧ matris yapısı tekniğine, Golden kod için ise boyutsal indirgeme tekniklerine dayanan en büyük olabilirlikli kodçözme yöntemleridir.Burada, ayrıştırılmıs ̧ matris yapısı tekniği küresel kodçözme yönteminde kullanılan üst üçgen matrisinin karakteristik özelliklerinin kullanımına dayanmaktadır ve kodçözme karmaşıklığını işlem sayısı cinsinden azaltır. Bir diğer taraftan boyutsal indirgeme teknikleriyse küresel kodçözme algoritmasındaki arama ağacının kodun karakteristiğine bağlı olarak kısaltılmasını ve böylece kodçözme gecikmesinin azaltılmasını amaçlar.Ayrıca, yürüttüğümüz çalışma sonucunda kodlama merkezli en büyük olabilirlikli kodçözme yaklaşımı Reed-Muller ve kutupsal kodlar gibi kanal kodlama teknikleri için sağlanmıştır. Bu doğrultuda ikili arama ağacına yönelik algoritma çalışmalarımız sonucunda kısa kutupsal ve Reed-Muller kodların optimum başarımlı kodçözücüleri geliştirilmiştir.Kanal kodlamada optimum başarımlı kodçözmeyi daha uzun kodlar için de gerçeklenebilir yapabilmek amacıyla arama ağacını katlama yöntemini verimli kodçözme amacıyla öneriyoruz. Bu amaçla, Kronecker tabanlı kodlarda kullanılan Fn matrisinin oldukça kurallı olan fraktal yapısı kullanılarak ikili arama ağacının katlanmış ikili olmayan daha kısa bir arama ağacına dönüştürülebildiğini gösterebiliyoruz. Bu özellik yardımıyla en büyük olabilirlikli kodçözmeyi daha verimli bir şekilde gerçekleyip daha uzun kodlar için kullanılabileceğini gösteriyoruz. Böylece blok uzunluğu 256'ya kadar olan kodların önerdiğimiz yöntemle çözülebildikleri gösterilebilmiştir.Ayrıca bu doğrultuda yaptığımız çalışmalar göstermiştir ki verilen bir kutupsal kodun farklı karmaşıklıklara sahip olan alternatif katlanmış ağaç yapılarıyla çözülebilmesi verimli kodçözücülerin gerçeklenmesinde bir avantaj oluşturmaktadır.Bunların yanında ağaç arama prosedürünü optimum bas ̧arımı kaybetmeksizin hızlandırmak amacıyla çeşitli yan teknikler geliştirilmiştir. Bunlar kısaca, tablo indirgeme, çoklu zıplama, tek adımda kodçözme ile adlandırılmıştır.Kodçözme yönteminin dinamik davranışını araştırmak amacıyla yaptığımız deneyler sonucunda, önerdiğimiz kod çözücünün beklenen karmaşıklığının önemli bir bas ̧arim kaybı olmaksızın sınırlanabileceği gösterilmiştir. Bunun sonucunda önerilen yöntemin pratik uygulamalar için gerçeklenebilir olduğu değerlendirilmiştir.Ayrıca tanıttığımız arama ağacı katlama tekniği kullanılarak kutupsal kodlar için konvansiyonel kodçözücü olan optimum altı bas ̧arıma sahip ardışıl yinelemeli koçözücünün kod çözme gecikmesi önemli oranda düşürülebilmiştir. Bu doğrultuda, standart ikili kutupsal kodların ikili olmayan katlanmış ardışıl yinelemeli kodçözücü ile çözülebildiği gösterilmiştir.Önerdiğimiz optimum başarımlı katlamalı ağaç kodçözücüyü hızlandırmak amacıyla arama ağacı üzerinde seviyeler arasında çoklu zıplamalara dayanan bir teknik önerilmiştir. Kutupsal kodların tasarımında önerdiğimiz bu yöntemden daha fazla faydalanabilmek amacıyla kod tasarımı üzerinde arama ağacını daha hızlı çözülebilecek şekilde oluşturmamıza olanak sağlayacak kısıtlar tanımlanabilmiştir. Bu yöntem ile önerdiğimiz kodçözücü kullanılarak ulaşılamayacak olan 512 uzunluklu kutupsal kod benzeri kodların tasarlanabileceği gösterilmiştir. Önerilen kodların optimum kodçözme altındaki hata başarımı standart bilinen kutupsal kodların ardışıl yinelemeli kodçözücü altındaki hata başarımından daha iyi olabileceği gösterilmiştir.Sonuç olarak, optimum bas ̧arıma sahip en büyük olabilirlikli kodçözmenin kutupsal kodlar için verimli bir şekilde gerçeklenebileceği gösterilebilmiştir. Bunun yaninda, geliştirdiğimiz hızlı yöntemler kullanılarak kutupsal kodların bilinen kodçözücüsü olan ardışıl yinelemeli kodçözücünün gecikmesi önemli miktarda düşürülebilmiştir. Bunlara ek olarak, hızlı çözülebilen kutupsal kod tasarımına benzer bir tasarım kriteri tanıtılmıştır.

An algorithmic study of decoding is presented in this thesis. First of all we consider general optimal decoding problem which is hardly resolved in various communication systems. In that case, several research directions have been carried-out to jointly design advanced code construction and decoding methods. It is introduced that methodologies of code construction for optimal decoding is a reasonable approach. However, there are a lot of sub-optimal decoder implementations for different communication systems under specific technological limitations, the same decoding techniques can be used for different communication systems. As a result of that, we show a tree search based decoder for multiple input multiple output systems that can be used for channel coding.We propose first code based maximum-likelihood decoding for multiple input multiple output system with well-known space time block codes. In this way, algorithmic studies to design low complexity and low decoding latency algorithms are proposed by the use of decomposed matrix structure and dimensionality reduction techniques for Bell-Labs Layered Space-Time system and the golden code, respectively. Then, a code based maximum-likelihood tree decoding approach is provided for channel coding schemes such as polar and Reed-Muller codes. In this way, an algorithmic study with the binary search tree for low decoding latency is provided in order to decode short polar and Reed-Muller codes with the exact maximum-likelihood decoding performance.Then, we provide the tree folding technique for efficiently decoding of Kronecker product-based codes not only for maximum-likelihood decoding but also successive cancellation decoding. In this way, we exploit the highly regular fractal structure of the n-fold Kronecker product of the kernel F to fold and construct a non-binary decoding tree structure. Firstly, we show that the previously proposed binary tree maximum-likelihood decoding can be re-designed as efficient non-binary tree for polar codes by the help of folding operation. Hence, longer codes can be achievable under the exact maximum-likelihood decoding for code lengths of up to 256. Secondly, the conventional successive cancellation decoder architecture can be re-designed by the proposed folding operation. Hence, decoding latency is significantly reduced by the multiple folded successive cancellation decoder. In this way, longer polar codes can be achievable in more practical implementations with significantly reduced decoding latency.From a global perspective, our result pursues the trend of designing codes for specific decoding architecture constraints. We have proposed an efficient tree search allowing for multiple jumps to increase the speed of the folded tree maximum-likelihood decoder of polar codes. Then, we show an example of a polar-like code for which the folded search tree search most likely has multiple jumps. We show that the exact maximum-likelihood decodable polar-like codes can be maximum-likelihood decoded for a code length up to 512. The proposed codes under maximum-likelihood decoding outperforms the standard polar code under the successive cancellation decoding.