On decoding interleaved Reed-solomon codes
Geçmeli Reed-solomon kodlarının çözümlenmesi üzerine
- Tez No: 297774
- Danışmanlar: PROF. DR. FERRUH ÖZBUDAK
- Tez Türü: Doktora
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2011
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Uygulamalı Matematik Enstitüsü
- Ana Bilim Dalı: Kriptografi Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 66
Özet
Bleichenbacher-Kiayias-Yung olasılıksal eşzamanlı polinom geriçatılması algoritması polinomların dereceleri farklı olduğu durumlara genelleştirilmiştir. Ayrıca, olasılığın ar\-tı\-rı\-la\-bi\-le\-ce\-ği de gözlemlenmiştir. Belirgin şekliyle, $\F$ sonlu bir cisimi için, $p_l(z_i) = y_{i,l}$ $i \in I$, $|I|=t$ ve $l \in [r]$ polinom değerleri verildiğinde, dereceleri sırasıyla $k_1,k_2,\ldots,k_r$ olan $p_1,\ldots, p_r \in \F[x]$ polinomlarını en azından $1 - (n - t)/|\F|$ olasılığı ve en çok $O((nr)^3)$ hesaplama karmaşıklığında eşzamanlı geriçatan olasılıksal bir algoritma sunulmuştur. Bu algoritmanın kullanımıyla geçmeli Reed-Solomon kodları için olasılıksal çözümleyici sunulmuştur. Bu çözümleyici, bigi oranı $R$ olan $\F$ üzerinde tanımlı $r$ geçmeli Reed-Solomon kodları $\frac{r}{r+1}(1 - R)$ yığılma hata oranına kadar olasılıksal çözümleyebilir. O\-la\-sı\-lık\-sal geçmeli Reed-Solomon kod çözümleyicisi kullanıldığında verilen bir Reed-Solomon kodu RS$(n;k)$ $R' = \frac{(k-1)(r+1)+2}{2n}$ için $\frac{r}{r+1}(1 - R')$ hata oranına kadar çözümlenebileceği ispatlanmıştır. Benzer şekilde, bir $\F_{q^2}$ sonlu cismi için, bilgi oranı $R$ olan ve $\F_{q^{2q}}$ üzerinde tanımlı $q$-katlı Hermityan kodlarının $\frac{q}{q+1}(1 - R)$ hata oranına kadar olasılıksal çözümlenebileceği istalanmıştır. Diğer taraftan, alt\-kod\-la\-rı\-nın en az aralıkları farklı olduğunda bile geçmeli kodların, altkodlarının en küçük liste çözümleme çapına kadar çözümlenebileceği gösterilmiştir. Diğer bir ifadeyle, en az aralıkları farklı olabilen $C_1,\ldots, C_b$ kodlarının geçirilmesi ile oluşan $C$ kodunu, $C_1,\ldots, C_b$ kodlarının en küçük liste çözümleme çapına kadar, $C_1,\ldots, C_b$ kodlarının en büyük liste boyutunun polinom katı liste büyüklüğünde ve bu büyüklük ve $b$ sabitinin bir polinom katı zamanda çözebilen bir algoritma sunulmuştur. Bu algoritmanın kullanımıyla tanımlandığı cisim büyüküğü $q$ olan ve herhangibir $h$ doğal sayısı için $qh$-katlı Hermityan kodlarını listeleme yöntemiyle çözümleyebilen yeni bir algoritma sunulmuştur. Bu algoritma, $qh$-katlı Hermityan kodlarını, Guruswami-Sudan algoritmasından daha iyi bir çapa kadar, $\F_{q^2}$ üzerinde tanımlı $h$-katlı Reed-Solomon kodlarının liste büyüklüğünün polinom katı hesap karmaşıklığında ve liste büyüklüğünde çözümler.
Özet (Çeviri)
Probabilistic simultaneous polynomial reconstruction algorithm of Bleichenbacher-Kiayias-Yung is extended to the polynomials whose degrees are allowed to be distinct. Furthermore, it is observed that probability of the algorithm can be increased. Specifically, for a finite field $\F$, we present a probabilistic algorithm which can recover polynomials $p_1,\ldots, p_r \in \F[x]$ of degree less than $k_1,k_2,\ldots,k_r$, respectively with given field evaluations $p_l(z_i) = y_{i,l}$ for all $i \in I$, $|I|=t$ and $l \in [r]$ with probability at least $1 - (n - t)/|\F|$ and with time complexity at most $O((nr)^3)$. Next, by using this algorithm, we present a probabilistic decoder for interleaved Reed-Solomon codes. It is observed that interleaved Reed-Solomon codes over $\F$ with rate $R$ can be decoded up to burst error rate $\frac{r}{r+1}(1 - R)$ probabilistically for an interleaving parameter $r$. It is proved that a Reed-Solomon code RS$(n;k)$ can be decoded up to error rate $\frac{r}{r+1}(1 - R')$ for $R' = \frac{(k-1)(r+1)+2}{2n}$ when probabilistic interleaved Reed-Solomon decoders are applied. Similarly, for a finite field $\F_{q^2}$, it is proved that $q$-folded Hermitian codes over $\F_{q^{2q}}$ with rate $R$ can be decoded up to error rate $\frac{q}{q+1}(1 - R)$ probabilistically. On the other hand, it is observed that interleaved codes whose subcodes would have different minimum distances can be list decodable up to radius of minimum of list decoding radiuses of subcodes. Specifically, we present a list decoding algorithm for $C$, which is interleaving of $C_1,\ldots, C_b$ whose minimum distances would be different, decoding up to radius of minimum of list decoding radiuses of $C_1,\ldots, C_b$ with list size polynomial in the maximum of list sizes of $C_1,\ldots, C_b$ and with time complexity polynomial in list size of $C$ and $b$. Next, by using this list decoding algorithm for interleaved codes, we obtained new list decoding algorithm for $qh$-folded Hermitian codes for $q$ standing for field size the code defined and $h$ is any positive integer. The decoding algorithm list decodes $qh$-folded Hermitian codes for radius that is generally better than radius of Guruswami-Sudan algorithm, with time complexity and list size polynomial in list size of $h$-folded Reed-Solomon codes defined over $\F_{q^2}$.
Benzer Tezler
- Performance analysis of concatenated coding schemes
Kademeli kodlama sistemlerinin performans analizi
GÜN AKKOR
Yüksek Lisans
İngilizce
1999
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ERDAL ARIKAN
- Polar reed-solomon concatenated codes for optical communications
Optik haberleşme için uç uca eklemeli kutupsal reed-solomon kodlar
YİĞİT ERTUĞRUL
Yüksek Lisans
İngilizce
2020
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ERDAL ARIKAN
- Bit interleaved coded spatial modulation
Bit serpiştirmeli kodlamalı uzamsal kipleme
FURKAN KERİM KADI
Yüksek Lisans
İngilizce
2019
Elektrik ve Elektronik MühendisliğiBoğaziçi ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. MUTLU KOCA
- Performance of space time block coded bit interleaved coded modulation systems for mobile communication channels
Uzay zaman kodlamalı ve bit serpiştirilmiş kodlamalı modülasyon içeren iletişim sistemlerinin gezgin iletişim kanalları için başarımları
OMAR KHAZ'AL ISMAEIL
Yüksek Lisans
İngilizce
2014
Elektrik ve Elektronik MühendisliğiÇankaya ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DOÇ. DR. ORHAN GAZİ
- Bilişsel radyo için uzay zaman kodlamaya dayalı girişimsiz spektrum paylaşımı
Interference-free spectrum sharing in cognitive radio based on space time coding
MOHAMMADREZA BABAEI
Yüksek Lisans
İngilizce
2016
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. HASAN ÜMİT AYGÖLÜ