Lossless data compression with polar codes
Kutupsal kodlarla yitimsiz veri sıkıştırma
- Tez No: 335608
- Danışmanlar: PROF. DR. ORHAN ARIKAN, PROF. DR. ERDAL ARIKAN
- Tez Türü: Yüksek Lisans
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2013
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik ve Elektronik Mühendisliği Bölümü
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 74
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- Geriyansımalı yapay sinir ağının görüntü sıkıştırmada kullanılması
Image compression by backpropagation algorithm
MUSTAFA TOSUN
Yüksek Lisans
Türkçe
1997
Elektrik ve Elektronik MühendisliğiDumlupınar ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. M. ALİ EBEOĞLU
- Veri sıkıştırmada yeni yöntemler
New methods on data compression
ALTAN MESUT
Doktora
Türkçe
2006
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolTrakya ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
Y.DOÇ.DR. AYDIN CARUS
- Sıra korumalı dizgi eşleştirme tabanlı bağlam modellemesi ile kayıpsız veri sıkıştırma
Lossless data compress with order preserve patternmatching base context modelling
MUHAMMED VEYSEL KINGIR
Yüksek Lisans
Türkçe
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Bilimleri Ana Bilim Dalı
PROF. DR. MUHAMMED OĞUZHAN KÜLEKCİ
- EPIIC:: a novel encoding pluggable lossless data compression algorithm
EPIIC:: kodlama eklenebilir yeni bir kayıpsız data sıkıştırma algoritması
TAYLAN İSMAİL DOĞAN
Yüksek Lisans
İngilizce
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. YUSUF SAHİLLİOĞLU
- Kayıpsız veri sıkıştırma ve steganografi tekniğine dayalı yeni bir yöntem
A novel technique based on lossless data compression and steganography
ERTUĞRUL DUMAN
Yüksek Lisans
Türkçe
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSakarya ÜniversitesiBilgisayar ve Bilişim Mühendisliği Ana Bilim Dalı
PROF. DR. CEMİL ÖZ