Lossless data compression with polar codes

Abstract

Bu çalışmada, gürültüsüz ortamda sonlu kaynak alfabeleri için yitimsiz kutupsal veri sıkıştırma yöntemleri önerilmektedir. İlk kısımda, Arıkan tarafından tanıtılan, ikilik kaynaklar için yitimsiz kutupsal kodlama yöntemi genel asal boyutlu kaynak alfabelerine genişletilmiştir. Konvansiyonel ardışık iptal kod çözücüsüne ek olarak, pratik blok uzunluklarında iyileştirilmiş performans için ardışık iptal liste kod çözücüsü kullanılmıştır. Kod yapımı için, Tal ve Vardy tarafından önerilen yoğunluk evrimi için açgözlü yaklaşıklama algoritması ikilik olmayan kaynak alfabelerine uyarlanmıştır. İkinci bölümde Cronie ve Korada?nın çalışmaları esas alınarak, asal boyutlu alfabeler için değişken uzunluklu, sıfır hata kutupsal sıkıştırma şeması geliştirilmiştir. önerilen kodlama şemasının ardışık iptal kod çözücüsü ile blok uzunluğuyla asimptotik olarak minimum kaynak kodlama oranına erişmenin yanı sıra pratik blok uzunluklarında minimum kaynak kodlama oranına yakın oranlar sağladığı nümerik olarak gösterilmektedir. Pratik blok uzunluklarında iyileştirilmiş performans için ardışık iptal liste kod çözücüsü tabanlı bir şema geliştirilmiştir. önerilen yöntemler, çoklu seviye yaklaşımı kullanılarak rastgele sonlu kaynak alfabelerine genelleştirilmiştir. Pratik uygulamalar için, önerilen sıfır hata sıkıştırma yönteminin kaynak dağılımındaki belirsizliğe karşı gürbüzlüğü araştırılmıştır. Bu araştırma esas alınarak, pratik blok uzunluklarında her kaynak dağılımı için özel bir enformasyon kümesi oluşturmak yerine önceden inşa edilmiş enformasyon kümeleri öbeği kullanılabileceği gösterilmiştir. Bu tezde önerilen sıkıştırma yöntemleri evrensel olmadığı için bir kaynağın olasılık dağılımı alıcıda bilinmelidir. Bu durum, kaynak belirsizliği varlığında vericinin alıcıyı kaynak dağılımı hakkında bilgilendirmesini zorunlu kılar. Bu soruna bir çözüm olarak, kaynak olasılık dağılımını etkin bir şekilde sıkıştırılmış kelime ile gönderebilmek için bir ölçeklemeli sırasal basamaklama algoritması önerilmiştir.

In this study, lossless polar compression schemes are proposed for finite source alphabets in the noiseless setting. In the first part, lossless polar source coding scheme for binary memoryless sources introduced by Ar{/i}kan is extended to general prime-size alphabets. In addition to the conventional successive cancellation decoding (SC-D), successive cancellation list decoding (SCL-D) is utilized for improved performance at practical block-lengths. For code construction, greedy approximation method for density evolution, proposed by Tal and Vardy, is adapted to non-binary alphabets. In the second part, a variable-length, zero-error polar compression scheme for prime-size alphabets based on the work of Cronie and Korada is developed. It is shown numerically that this scheme provides rates close to minimum source coding rate at practical block-lengths under SC-D, while achieving the minimum source coding rate asymptotically in the block-length. For improved performance at practical block-lengths, a scheme based on SCL-D is developed. The proposed schemes are generalized to arbitrary finite source alphabets by using a multi-level approach. For practical applications, robustness of the zero-error source coding scheme with respect to uncertainty in source distribution is investigated. Based on this robustness investigation, it is shown that a class of prebuilt information sets can be used at practical block-lengths instead of constructing a specific information set for every source distribution. Since the compression schemes proposed in this thesis are not universal, probability distribution of a source must be known at the receiver for reconstruction. In the presence of source uncertainty, this requires the transmitter to inform the receiver about the source distribution. As a solution to this problem, a sequential quantization with scaling algorithm is proposed to transmit the probability distribution of the source together with the compressed word in an efficient way.