Raptor kód - Raptor code
A számítástechnika , Raptor kódokat ( rap id tor NADO lásd Tornado kódok ) az első ismert csoportját szökőkút kódok lineáris idő kódolás és dekódolás. Amin Shokrollahi találta ki őket 2000/2001 -ben , és először 2004 -ben tették közzé kiterjesztett kivonatként . A Raptor kódok jelentős elméleti és gyakorlati fejlesztést jelentenek az LT kódokhoz képest , amelyek a szökőkút kódok első gyakorlati osztálya voltak .
Raptor kódokat, mint a Fountain kódok általában kódolnak egy adott forrásból adatblokkot, amely számos k egyenlő méretű forrás szimbólumoknak egy potenciálisan korlátlan szekvenciát kódoló szimbólumok például, hogy a vétel bármely k vagy több kódoló szimbólumot lehetővé teszi a forrás blokk némi nullától eltérő valószínűséggel kell visszanyerni. Annak a valószínűsége, hogy a forrásblokk helyreállítható, növekszik, ha a k felett kapott kódoló szimbólumok száma nagyon közel lesz az 1 -hez, ha a fogadott kódoló szimbólumok száma csak nagyon kicsi nagyobb, mint k . Például, a legújabb generációs Raptor kódokat, a RaptorQ kódok, az esélye, hogy a dekódolás kudarc, ha k kódoló szimbólumok érkezett kevesebb, mint 1%, és az esélyt a dekódolás kudarc, ha k + 2 -t kódoló szimbólumok érkezett kevesebb mint egy millióból. (Erről bővebben lásd alább a Helyreállítási valószínűség és a rezsi című részt.) A szimbólum bármilyen méretű lehet, egyetlen bájttól több száz vagy ezer bájtig.
A Raptor kódok lehetnek szisztematikusak vagy nem szisztematikusak. Szisztematikus esetben az eredeti forrásblokk szimbólumai, azaz a forrásszimbólumok szerepelnek a kódoló szimbólumok készletében. Néhány példa a szisztematikus raptor kód használata a 3rd Generation Partnership Project a mobil cellás, vezeték nélküli műsorszóró és multicast, mind pedig a DVB-H szabványok IP datacast a kézi eszközök (lásd külső hivatkozások). Az ezekben a szabványokban használt Raptor kódokat az IETF RFC 5053 is meghatározza .
Az online kódok egy példa a nem szisztematikus forráskódra.
RaptorQ kód
A Raptor legfejlettebb verziója az IETF RFC 6330-ban meghatározott RaptorQ kód. A RaptorQ kód egy szisztematikus kód, amelyet lineáris időkódolási és dekódolási teljesítmény elérése érdekében lehet megvalósítani, közel optimális helyreállítási tulajdonságokkal rendelkezik (lásd: Helyreállítási valószínűség és a fejléc alatt, további részletekért), legfeljebb 56 403 forrásszimbólumot támogat, és lényegében korlátlan számú kódoló szimbólumot támogat.
Az IETF RFC 6330 -ban meghatározott RaptorQ kódot a Next Gen TV ( ATSC 3.0 ) szabvány részeként határozták meg, hogy lehetővé tegye a kiváló minőségű sugárzott videó streaminget (robusztus mobil TV), valamint a hatékony és megbízható adásfájlok továbbítását (adattovábbítás). Különösen a RaptorQ kódot határozza meg az A/331: Jelzés, kézbesítés, szinkronizálás és hibavédelem az ATSC 3.0 -n belül (lásd az ATSC szabványok listáját az ATSC 3.0 szabványos alkatrészek listájához). A Next Gen TV (ATSC 3.0) jóval túlmutat a hagyományos TV-n, és széles körű internet-hozzáférést biztosít, amely lehetővé teszi az általános adatszolgáltatásokat.
Áttekintés
A Raptor kódok két kód összekapcsolásával jönnek létre.
Rögzített , általában meglehetősen magas arányú törlési kódot alkalmaznak „előkódként” vagy „külső kódként”. Ez az előkód maga is több kód összefűzése lehet, például a 3GPP által szabványosított kódban a bináris Grey szekvenciából származtatott nagy sűrűségű paritásellenőrző kód egyszerű egyszerű, kis sűrűségű paritásellenőrző kóddal van összefűzve . Egy másik lehetőség egy Hamming -kód összekapcsolása alacsony sűrűségű paritásellenőrző kóddal.
A belső kód az előkódolási művelet eredményét veszi fel, és kódoló szimbólumok sorozatát generálja. A belső kód az LT kódok egy formája . Minden kódoló szimbólum egy ál-véletlenszerűen kiválasztott szimbólumkészlet XOR- ja az előkód kimenetből. A szimbólumok számát, amelyek XOR'-val együtt kimeneti szimbólumot képeznek, ál-véletlenszerűen választják ki minden kimeneti szimbólumhoz, egy adott valószínűségi eloszlás szerint.
Ezt az eloszlást, valamint az ál-véletlen számok generálásának mechanizmusát az eloszlás mintavételezéséhez és az XOR-hoz szimbólumok kiválasztásához mind a feladónak, mind a fogadónak ismernie kell. Az egyik megközelítésben minden szimbólumhoz tartozik egy azonosító, amely felhasználható az ál-véletlenszám-generátor vetőmagjává ezen információk előállításához, és ugyanazt a folyamatot követi mind a küldő, mind a fogadó.
Nem szisztematikus Raptor-kódok esetén a kódolni kívánt forrásadatokat használják az előkódolási szakasz bemenetének.
Szisztematikus Raptor-kódok esetén az előkódolási szakasz bemenetét úgy kapjuk meg, hogy először alkalmazzuk az első k kimeneti szimbólumokat generáló kódolási művelet inverzét a forrásadatokra. Így a normál kódolási művelet alkalmazása a kapott szimbólumokra az eredeti forrásszimbólumok újbóli létrehozását eredményezi a kód első k kimeneti szimbólumaként. Biztosítani kell, hogy az első k kimeneti szimbólumokat generáló ál-véletlen folyamatok invertálható műveletet hozzanak létre.
Dekódolás
A Raptor -kódok dekódolásához két megközelítés lehetséges. Összekapcsolt megközelítésben először a belső kódot dekódolják, egy hitterjesztési algoritmus használatával, ahogy az LT kódoknál használják. A dekódolás sikeres, ha ez a művelet elegendő számú szimbólumot állít helyre, így a külső kód vissza tudja állítani a fennmaradó szimbólumokat az adott kódnak megfelelő dekódoló algoritmus segítségével.
Kombinált megközelítésben a belső és a külső kód által meghatározott szimbólumok közötti kapcsolatokat egyetlen kombinált szimultán egyenlethalmaznak tekintik, amelyek a szokásos eszközökkel, jellemzően Gauss -eliminációval oldhatók meg .
Számítási komplexitás
A Raptor kódoknak O (szimbólumméret) időre van szükségük ahhoz, hogy kódoló szimbólumot generáljanak egy forrásblokkból, és O (forrásblokk méret) időre van szükségük ahhoz, hogy a forrásblokkot legalább k kódoló szimbólumból helyreállítsák .
A helyreállítás valószínűsége és a rezsi
A rezsi az, hogy hány további kódoló szimbólumot kell fogadni az eredeti forrásblokk k számú forrásszimbólumán kívül, hogy a forrásblokk teljesen helyreálljon. (Az elemi információelméleti megfontolások alapján a k forrásszimbólummal rendelkező forrásblokk teljes helyreállítása nem lehetséges, ha kevesebb mint k kódoló szimbólum érkezik.) A helyreállítási valószínűség annak a valószínűsége, hogy a forrásblokk teljesen helyreáll, miután megkapta a megadott számú a forrásblokkból generált véletlenszerű kódolási szimbólumok.
Az IETF RFC 6330-ban megadott RaptorQ kód a következő kompromisszummal rendelkezik a helyreállítási valószínűség és a helyreállítási költségek között:
- Nagyobb mint 99% -os helyreállítási valószínűség 0 szimbólum fölött (helyreállítás k kapott kódoló szimbólumból).
- Több mint 99,99% helyreállítási valószínűség 1 szimbólum fölött (helyreállítás k+1 kapott kódoló szimbólumokból).
- Több mint 99,9999% helyreállítási valószínűség 2 szimbólum fölött (helyreállítás k+2 kapott kódoló szimbólumból).
Ezek az állítások érvényesek az IETF RFC 6330 által támogatott k teljes tartományára , azaz k = 1, ..., 56403. További részletekért lásd az IETF RFC 6330 -at.
Jogi státusz
A Qualcomm, Inc. közzétett egy IPR -nyilatkozatot az IETF RFC 5053 -ban meghatározott Raptor -kódról, és egy IPR -nyilatkozatot az IETF RFC 6330 -ban meghatározott, fejlettebb RaptorQ -kódról. Ezek a nyilatkozatok tükrözik a Qualcomm, Inc. által a az MPEG DASH szabványt . Az MPEG DASH szabványt sokféle vállalat telepítette, köztük a DASH Industry Forum tagvállalatai.
Lásd még
Megjegyzések
Hivatkozások
- Shokrollahi, Amin, "Raptor Codes", IEEE Transactions on Information Theory, vol. 52., 2551-2567, 2006. PDF (bejelentkezés szükséges)
- ATSC 3.0 (Advanced Television Standards Committee 3.0)
- 3GPP (3. generációs partnerségi projekt)
- DVB (digitális videóközvetítés)
- 3GPP TS26.346 3GPP Technikai specifikáció a multimédiás műsorszóráshoz/multicast szolgáltatáshoz: Protokollok és kodekek.
- RFC5053 Raptor Forward Error Correction Scheme for Object Delivery
- DVB-H IP adattovábbítási specifikációk
- RFC6330 RaptorQ továbbító hibajavító séma az objektumkézbesítéshez
- [1] "IPR" keresési eredmény az RFC 5053 -ra, néhány szabadalmi tulajdonos nyilatkozatával
- [2] "IPR" keresési eredmény az RFC 6330 esetében, néhány szabadalmi tulajdonos nyilatkozatával
