รหัสแรปเตอร์

ในวิทยาการคอมพิวเตอร์รหัสแรปเตอร์ ( rap id tor nado ; ^{[ 1 ]}ดูรหัสทอร์นาโด ) เป็น รหัสน้ำพุประเภทแรกที่รู้จักกันซึ่งมีการเข้ารหัสและถอดรหัสแบบเชิงเส้น รหัสเหล่านี้ถูกคิดค้นโดยAmin Shokrollahiในปี 2000/2001 และตีพิมพ์ครั้งแรกในปี 2004 ในรูปแบบบทคัดย่อขยาย รหัสแรปเตอร์เป็นการปรับปรุงทางทฤษฎีและเชิงปฏิบัติที่สำคัญเหนือกว่ารหัส LT ซึ่งเป็น รหัสน้ำพุประเภทแรกที่ใช้งานได้จริง

รหัส Raptor เช่นเดียวกับรหัส Fountain โดยทั่วไป จะเข้ารหัสบล็อกข้อมูลต้นทางที่ประกอบด้วยสัญลักษณ์ต้นทางขนาดเท่ากันจำนวนkตัว ให้เป็นลำดับของสัญลักษณ์การเข้ารหัสที่อาจไม่มีที่สิ้นสุด โดยที่การรับ สัญลักษณ์การเข้ารหัส kตัวขึ้นไปจะทำให้สามารถกู้คืนบล็อกข้อมูลต้นทางได้ด้วยความน่าจะเป็นที่ไม่เป็นศูนย์ ความน่าจะเป็นที่สามารถกู้คืนบล็อกข้อมูลต้นทางได้จะเพิ่มขึ้นตามจำนวนสัญลักษณ์การเข้ารหัสที่ได้รับมากกว่าkโดยจะเข้าใกล้ 1 มาก เมื่อจำนวนสัญลักษณ์การเข้ารหัสที่ได้รับมากกว่าk เพียงเล็กน้อย ตัวอย่างเช่น รหัส Raptor รุ่นล่าสุด คือ รหัส RaptorQ โอกาสที่จะเกิดความล้มเหลวในการถอดรหัสเมื่อ ได้รับสัญลักษณ์การเข้ารหัส k ตัวจะน้อยกว่า 1% และโอกาสที่จะเกิดความล้มเหลวในการถอดรหัสเมื่อ ได้รับสัญลักษณ์การเข้ารหัส k+2 ตัวจะน้อยกว่าหนึ่งในล้าน สัญลักษณ์สามารถมีขนาดใดก็ได้ ตั้งแต่หนึ่งไบต์ไปจนถึงหลายร้อยหรือหลายพันไบต์

รหัส Raptor อาจเป็นแบบเป็นระบบหรือไม่เป็นระบบก็ได้ ในกรณีที่เป็นระบบ สัญลักษณ์ของบล็อกต้นฉบับ กล่าวคือ สัญลักษณ์ต้นฉบับ จะถูกรวมอยู่ในชุดของสัญลักษณ์การเข้ารหัส ตัวอย่างของรหัส Raptor แบบเป็นระบบ ได้แก่ การใช้งานโดยโครงการความร่วมมือรุ่นที่ 3 (3rd Generation Partnership Project)ใน การออกอากาศและการส่งแบบมัลติแคส ต์ไร้สายผ่านเครือข่ายโทรศัพท์มือถือและมาตรฐาน DVB-Hสำหรับการส่งข้อมูล IP ไปยังอุปกรณ์พกพา รหัส Raptor ที่ใช้ในมาตรฐานเหล่านี้ยังถูกกำหนดไว้ในIETF RFC 5053ด้วย

รหัสออนไลน์เป็นตัวอย่างของรหัสน้ำพุที่ไม่เป็นระบบ

รหัส RaptorQ

เวอร์ชันที่ทันสมัยที่สุดของ Raptor คือโค้ด RaptorQ ที่กำหนดไว้ในIETF RFC 6330โค้ด RaptorQ เป็นโค้ดที่เป็นระบบ สามารถนำไปใช้งานเพื่อให้ได้ประสิทธิภาพการเข้ารหัสและถอดรหัสในเวลาเชิงเส้น มีคุณสมบัติการกู้คืนที่ใกล้เคียงกับค่าที่เหมาะสมที่สุด รองรับสัญลักษณ์ต้นทางได้มากถึง 56,403 สัญลักษณ์ และสามารถรองรับสัญลักษณ์การเข้ารหัสได้จำนวนมากอย่างไม่จำกัด

รหัส RaptorQ ที่กำหนดไว้ในIETF RFC 6330 ได้รับการระบุเป็นส่วนหนึ่งของมาตรฐาน Next Gen TV ( ATSC 3.0 ) เพื่อให้สามารถสตรีมวิดีโอออกอากาศคุณภาพสูง (โทรทัศน์เคลื่อนที่ที่มีความทนทาน) และส่งไฟล์ออกอากาศที่มีประสิทธิภาพและเชื่อถือได้ (การส่งข้อมูล) โดยเฉพาะอย่างยิ่ง รหัส RaptorQ ได้รับการระบุใน A/331 ภายใน ATSC 3.0 ^{[ 2 ]}ดูรายการมาตรฐาน ATSCสำหรับรายการส่วนต่างๆ ของมาตรฐาน ATSC 3.0 Next Gen TV (ATSC 3.0) ก้าวไปไกลกว่าโทรทัศน์แบบดั้งเดิมเพื่อให้บริการอินเทอร์เน็ตแบบออกอากาศที่ช่วยให้สามารถให้บริการส่งข้อมูลทั่วไปได้

ภาพรวม

รหัส Raptor เกิดจากการรวมกันของรหัสสองรหัส

รหัสลบข้อมูลแบบอัตราคงที่ซึ่งโดยปกติจะมีอัตราค่อนข้างสูง จะถูกนำมาใช้เป็น 'รหัสเบื้องต้น' หรือ 'รหัสภายนอก' รหัสเบื้องต้นนี้อาจเป็นการรวมกันของรหัสหลายรหัส ตัวอย่างเช่น ในรหัสที่กำหนดมาตรฐานโดย 3GPP รหัสตรวจสอบความเท่าเทียมกันความหนาแน่นสูงที่ได้มาจากลำดับ Gray แบบไบนารี จะถูกรวมกับ รหัสตรวจสอบความเท่าเทียมกันความหนาแน่นต่ำแบบธรรมดาอีกความเป็นไปได้หนึ่งคือการรวมรหัส Hammingเข้ากับรหัสตรวจสอบความเท่าเทียมกันความหนาแน่นต่ำ

รหัสภายในจะนำผลลัพธ์จากการดำเนินการก่อนการเข้ารหัสมาสร้างลำดับของสัญลักษณ์การเข้ารหัส รหัสภายในเป็นรูปแบบหนึ่งของรหัส LTโดยแต่ละสัญลักษณ์การเข้ารหัสเป็นผล XORของชุดสัญลักษณ์ที่เลือกแบบสุ่มจากผลลัพธ์ก่อนการเข้ารหัส จำนวนสัญลักษณ์ที่นำมา XOR กันเพื่อสร้างสัญลักษณ์เอาต์พุตจะถูกเลือกแบบสุ่มสำหรับแต่ละสัญลักษณ์เอาต์พุตตามการกระจายความน่าจะเป็นเฉพาะ

การแจกแจงนี้ รวมถึงกลไกในการสร้างตัวเลขสุ่มเทียมสำหรับการสุ่มตัวอย่างจากการแจกแจงนี้ และสำหรับการเลือกสัญลักษณ์ที่จะนำมาทำการ XOR นั้น จะต้องเป็นที่ทราบกันทั้งผู้ส่งและผู้รับ ในแนวทางหนึ่ง สัญลักษณ์แต่ละตัวจะมาพร้อมกับตัวระบุซึ่งสามารถใช้เป็นค่าเริ่มต้น (seed) สำหรับตัวสร้างตัวเลขสุ่มเทียมเพื่อสร้างข้อมูลนี้ โดยทั้งผู้ส่งและผู้รับจะใช้กระบวนการเดียวกัน

ในกรณีของรหัส Raptor ที่ไม่มีระบบ ข้อมูลต้นฉบับที่จะถูกเข้ารหัสจะถูกใช้เป็นข้อมูลป้อนเข้าในขั้นตอนก่อนการเข้ารหัส

ในกรณีของรหัส Raptor แบบเป็นระบบ ข้อมูลป้อนเข้าสู่ขั้นตอนการเข้ารหัสเบื้องต้นจะได้รับโดยการใช้การดำเนินการเข้ารหัสแบบผกผันที่สร้าง สัญลักษณ์เอาต์พุต k ตัวแรก กับข้อมูลต้นฉบับก่อน ดังนั้น การใช้การดำเนินการเข้ารหัสแบบปกติกับสัญลักษณ์ที่ได้จะทำให้สัญลักษณ์ต้นฉบับถูกสร้างขึ้นใหม่เป็น สัญลักษณ์เอาต์พุต k ตัวแรก ของรหัส จำเป็นต้องตรวจสอบให้แน่ใจว่ากระบวนการสุ่มเทียมที่สร้าง สัญลักษณ์เอาต์พุต k ตัวแรกนั้น สร้างการดำเนินการที่สามารถผกผันได้

การถอดรหัส

มีสองแนวทางที่เป็นไปได้สำหรับการถอดรหัส Raptor ในแนวทางแบบต่อกัน ขั้นแรกจะถอดรหัสภายในก่อน โดยใช้อัลกอริธึมการแพร่กระจายความเชื่อ (belief propagation algorithm) เช่นเดียวกับที่ใช้สำหรับรหัส LT การถอดรหัสจะสำเร็จหากการดำเนินการนี้สามารถกู้คืนสัญลักษณ์ได้มากพอ เพื่อให้รหัสภายนอกสามารถกู้คืนสัญลักษณ์ที่เหลือได้โดยใช้อัลกอริธึมการถอดรหัสที่เหมาะสมสำหรับรหัสนั้น

ในแนวทางแบบผสมผสาน ความสัมพันธ์ระหว่างสัญลักษณ์ที่กำหนดโดยทั้งรหัสภายในและภายนอกจะถูกพิจารณาว่าเป็นชุดสมการเชิงเส้นพร้อมกันชุดเดียว ซึ่งสามารถแก้ไขได้ด้วยวิธีการปกติ โดยทั่วไปคือวิธีการกำจัดแบบเกาส์เซียน

ความซับซ้อนในการคำนวณ

รหัส Raptor ต้องการ เวลา O(ขนาดสัญลักษณ์)ในการสร้างสัญลักษณ์การเข้ารหัสจากบล็อกต้นฉบับ และต้องการ เวลา O(ขนาดบล็อกต้นฉบับ)ในการกู้คืนบล็อกต้นฉบับจากสัญลักษณ์การเข้ารหัส อย่างน้อย k ตัว

ความน่าจะเป็นในการฟื้นตัวและค่าใช้จ่ายส่วนเกิน

ค่าใช้จ่ายเพิ่มเติม (Overhead) คือจำนวนสัญลักษณ์การเข้ารหัสเพิ่มเติมที่มากกว่าจำนวนkของสัญลักษณ์ต้นทางในบล็อกต้นทางเดิมที่จำเป็นต้องได้รับเพื่อให้สามารถกู้คืนบล็อกต้นทางได้อย่างสมบูรณ์ (จากการพิจารณาตามทฤษฎีสารสนเทศ เบื้องต้น การกู้คืนบล็อกต้นทางที่มี สัญลักษณ์ต้นทาง k ตัวอย่างสมบูรณ์ นั้นเป็นไปไม่ได้หากได้รับสัญลักษณ์การเข้ารหัสน้อยกว่าk ตัว ) ความน่าจะเป็นในการกู้คืน (Recovery Probability) คือความน่าจะเป็นที่บล็อกต้นทางจะถูกกู้คืนอย่างสมบูรณ์เมื่อได้รับสัญลักษณ์การเข้ารหัสแบบสุ่มจำนวนหนึ่งที่สร้างขึ้นจากบล็อกต้นทาง

โค้ด RaptorQ ที่ระบุไว้ในIETF RFC 6330 มีความสมดุลระหว่างความน่าจะเป็นในการกู้คืนและค่าใช้จ่ายในการกู้คืนดังต่อไปนี้:

มีโอกาสกู้คืนข้อมูลได้มากกว่า 99% โดยมีค่าใช้จ่ายเพิ่มเติม 0 สัญลักษณ์ (กู้คืนจาก สัญลักษณ์การเข้ารหัสที่ได้รับ k ตัว )
มีโอกาสกู้คืนข้อมูลได้มากกว่า 99.99% โดยมีค่าใช้จ่ายเพิ่มเติม 1 สัญลักษณ์ (กู้คืนจาก สัญลักษณ์การเข้ารหัสที่ได้รับ k+1 ตัว )
มีโอกาสกู้คืนข้อมูลได้มากกว่า 99.9999% โดยมีค่าใช้จ่ายเพิ่มเติม 2 สัญลักษณ์ (กู้คืนจาก สัญลักษณ์การเข้ารหัสที่ได้รับ k+2 ตัว )

ข้อความเหล่านี้ใช้ได้กับค่าk ทั้งหมด ที่รองรับในIETF RFC 6330 กล่าวคือk = 1,...,56403 ดูรายละเอียดเพิ่มเติมได้ใน IETF RFC 6330 ^{[ 3 ]}

สถานะทางกฎหมาย

บริษัท Qualcomm , Inc. ได้เผยแพร่แถลงการณ์เกี่ยวกับสิทธิในทรัพย์สินทางปัญญา (IPR) สำหรับโค้ด Raptor ที่ระบุไว้ในIETF RFC 5053 และแถลงการณ์เกี่ยวกับสิทธิในทรัพย์สินทางปัญญาสำหรับโค้ด RaptorQ ที่มีความซับซ้อนกว่า ซึ่งระบุไว้ในIETF RFC 6330 แถลงการณ์เหล่านี้สะท้อนถึงพันธสัญญาด้านการอนุญาตให้ใช้สิทธิที่ Qualcomm, Inc. มีต่อ มาตรฐาน MPEG DASHมาตรฐาน MPEG DASH ได้ถูกนำไปใช้งานโดยบริษัทต่างๆ มากมาย รวมถึงบริษัทสมาชิกของ DASH Industry Forum ด้วย

ดูเพิ่มเติม

หมายเหตุ

↑อามิน โชคโรลลาฮี (31 มกราคม พ.ศ. 2554) การพัฒนารหัส Raptor (คำพูด) เชิญพูดคุยที่Kungliga Tekniska högskolan สืบค้นเมื่อ 24 กุมภาพันธ์ 2555 .
^ มาตรฐานผู้สมัคร ATSC: การส่งสัญญาณ การส่งมอบ การซิงโครไนซ์ และการป้องกันข้อผิดพลาด (A/331) (PDF) (รายงาน) คณะกรรมการระบบโทรทัศน์ขั้นสูง 22 มีนาคม 2017 ATSC S33-174r6
^ Luby M, Shokrollahi A, Watson M, Stockhammer T, Minder L (สิงหาคม 2011). คำขอความคิดเห็น: 6330. โครงการแก้ไขข้อผิดพลาดล่วงหน้า RaptorQ สำหรับการส่งมอบวัตถุ (รายงาน). ISSN 2070-1721 .

อ่านเพิ่มเติม

Shokrollahi, Amin (มิถุนายน 2549). "รหัสแรปเตอร์" . IEEE Transactions on Information Theory . 52 : 2551– 2567. doi : 10.1109/TIT.2006.874390 .
ผลการค้นหา "IPR" สำหรับ RFC 5053พร้อมคำแถลงจากเจ้าของสิทธิบัตรบางราย
ผลการค้นหา "IPR" สำหรับ RFC 6330พร้อมคำแถลงจากเจ้าของสิทธิบัตรบางราย

[1] อามิน โชคโรลลาฮี (31 มกราคม พ.ศ. 2554) การพัฒนารหัส Raptor (คำพูด) เชิญพูดคุยที่Kungliga Tekniska högskolan สืบค้นเมื่อ 24 กุมภาพันธ์ 2555 .

[2] มาตรฐานผู้สมัคร ATSC: การส่งสัญญาณ การส่งมอบ การซิงโครไนซ์ และการป้องกันข้อผิดพลาด (A/331) (PDF) (รายงาน) คณะกรรมการระบบโทรทัศน์ขั้นสูง 22 มีนาคม 2017 ATSC S33-174r6

[RFC_6330-3] Luby M, Shokrollahi A, Watson M, Stockhammer T, Minder L (สิงหาคม 2011). คำขอความคิดเห็น: 6330. โครงการแก้ไขข้อผิดพลาดล่วงหน้า RaptorQ สำหรับการส่งมอบวัตถุ (รายงาน). ISSN 2070-1721 .

[ 1 ]

[ 2 ]

[ 3 ]