Çevrimiçi kodlar - Online codes

Gelen bilgisayar bilimleri , çevrimiçi kodlar bir örnektir rateless silme kodları . Bu kodlar, bir mesajı bir dizi sembole kodlayabilir, öyle ki bunların herhangi bir kısmının bilgisi, orijinal mesajı kurtarmaya izin verir (yüksek olasılıkla). Sınırsız kodlar, alıcılar yeterli simgeye sahip olana kadar yayınlanabilen, keyfi olarak çok sayıda simge üretir.

Çevrimiçi kodların kullanımının üst düzey görünümü

Çevrimiçi kodlama algoritması birkaç aşamadan oluşur. İlk olarak mesaj, n adet sabit boyutlu mesaj bloğuna bölünür . Daha sonra dış kodlama , birleşik bir mesaj oluşturmak için mesaj bloklarına eklenen yardımcı bloklar üreten bir silme kodudur .

Bundan, iç kodlama kontrol blokları oluşturur. Belli sayıda kontrol bloğu alındığında, bileşik mesajın bir kısmı kurtarılabilir. Yeterince kurtarıldıktan sonra, dış kod çözme orijinal mesajı kurtarmak için kullanılabilir.

Ayrıntılı tartışma

Çevrimiçi kodlar, blok boyutu ve iki skaler , q ve ε ile parametrelendirilir . Yazarlar q = 3 ve ε = 0.01 önermektedir . Bu parametreler, kodlamanın karmaşıklığı ve performansı arasındaki dengeyi ayarlar. (1 + 3ε) n kontrol bloğundan yüksek olasılıkla n blokluk bir mesaj kurtarılabilir . Başarısızlık olasılığı (ε / 2) ^{q + 1'dir} .

Dış kodlama

Dış kodlama olarak herhangi bir silme kodu kullanılabilir, ancak çevrimiçi kodların yazarı aşağıdakileri önerir.

Her bir mesaj bloğu için, eklenecek q yardımcı blokları (toplam 0.55 q ε n yardımcı bloktan) sözde rastgele seçin . Her bir yardımcı blok, kendisine bağlı olan tüm mesaj bloklarının XOR'udur.

İç kodlama

10000 blok mesaj için sabitlenmiş mesaj bloklarının sayısına karşı alınan kontrol bloklarının bir grafiği.

İç kodlama, bileşik mesajı alır ve bir kontrol blokları akışı oluşturur. Bir kontrol bloğu , eklendiği bileşik mesajdaki tüm blokların XOR'udur .

Derece bir kontrol bloğunun bağlı olduğu blokların sayısıdır. Derecesi, aşağıdaki gibi tanımlanan rastgele bir dağılım p örneklenerek belirlenir :

${\ displaystyle F = \ sol \ lceil {\ frac {\ ln (\ epsilon ^ {2} / 4)} {\ ln (1- \ epsilon / 2)}} \ sağ \ rceil}$

${\ displaystyle p_ {1} = 1 - {\ frac {1 + 1 / F} {1+ \ epsilon}}}$

${\ displaystyle p_ {i} = {\ frac {(1-p_ {1}) F} {(F-1) i (i-1)}}}$ için ${\ displaystyle 2 \ leq i \ leq F}$

Kontrol bloğunun derecesi bilindikten sonra, eklendiği bileşik mesajdaki bloklar muntazam bir şekilde seçilir.

Kod çözme

Açıktır ki, iç aşamadaki kod çözücü, halihazırda kodunu çözemediği kontrol bloklarını tutmalıdır . Bir kontrol bloğunun kodu, yalnızca bağlı olduğu bloklardan biri hariç tümü bilindiğinde çözülebilir. Soldaki grafik, bir iç kod çözücünün ilerlemesini gösterir. X ekseni, alınan kontrol bloklarının sayısını gösterir ve kesikli çizgi, halihazırda kullanılamayan kontrol bloklarının sayısını gösterir. Bu, ilk başta, derece> 1 olan birçok kontrol bloğu alındığı, ancak kullanılamadığı için neredeyse doğrusal olarak tırmanır. Belirli bir noktada, bazı kontrol blokları aniden kullanılabilir hale gelir ve daha fazla blok çözülür ve bu da daha fazla kontrol bloğunun kullanılabilir olmasına neden olur. Çok hızlı bir şekilde tüm dosyanın kodu çözülebilir.

Grafikte de gösterildiği gibi, iç kod çözücü, n kontrol bloğunu aldıktan sonra kısa bir süre için her şeyin kodunu çözmekten çekiniyor . Dış kodlama, dosya onlar olmadan kurtarılabildiğinden, iç kod çözücüden birkaç zor bloğun sorun olmamasını sağlar.

Dış bağlantılar

• Orjinal kağıt
• Rateless Codes and Big Downloads (Aynı yazar tarafından daha erişilebilir bir makale)
• Petar Maymounkov'un makaleleri
• RubyForge'da barındırılan ve Çevrimiçi Kodlama için bir Ruby kitaplığı içeren bir Ruby projesi