รหัสน้ำพุ

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

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

รหัส LTเป็นการนำรหัส Fountain มาใช้งานจริงเป็นครั้งแรกต่อมาได้มีการนำรหัส Raptorและรหัสออนไลน์ มาใช้ ซึ่งสามารถเข้ารหัสและ ถอดรหัส ได้ในเวลาเชิงเส้น ผ่านขั้นตอนการเข้ารหัสล่วงหน้าของสัญลักษณ์อินพุต การเข้ารหัสเครือข่ายสามเหลี่ยม (Triangular network coding ) สามารถเข้ารหัสและถอดรหัสได้ในเวลาเชิงเส้นโดยใช้การเข้ารหัสแบบไม่เชิงเส้น และถอดรหัสโดยใช้วิธีการแทนที่ย้อนกลับ (back-substitution method)

แอปพลิเคชัน

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

ตัวอย่างหนึ่งคือข้อมูลแบบหมุนเวียน (data carousel ) ซึ่งไฟล์ขนาดใหญ่บางไฟล์จะถูกส่งออกอากาศอย่างต่อเนื่องไปยังชุดผู้รับ^{[ 1 ]}เมื่อใช้รหัสลบแบบอัตราคงที่ ผู้รับที่ขาดสัญลักษณ์ต้นทาง (เนื่องจากข้อผิดพลาดในการส่ง) จะเผชิญกับปัญหาของตัวเก็บคูปอง : ผู้รับจะต้องรับสัญลักษณ์การเข้ารหัสที่ตนเองยังไม่มีให้สำเร็จ ปัญหานี้จะชัดเจนมากขึ้นเมื่อใช้รหัสลบแบบความยาวสั้นแบบดั้งเดิม เนื่องจากไฟล์จะต้องถูกแบ่งออกเป็นหลายบล็อก โดยแต่ละบล็อกจะถูกเข้ารหัสแยกกัน: ผู้รับจะต้องรวบรวมสัญลักษณ์การเข้ารหัสที่ขาดหายไปตามจำนวนที่ต้องการสำหรับแต่ละบล็อก เมื่อใช้รหัสน้ำพุ (fountain code) ผู้รับเพียงแค่ดึงชุดย่อยของสัญลักษณ์การเข้ารหัสที่มีขนาดใหญ่กว่าชุดของสัญลักษณ์ต้นทางเล็กน้อยก็เพียงพอแล้ว(ในทางปฏิบัติ การออกอากาศมักจะถูกกำหนดเวลาไว้เป็นระยะเวลาคงที่โดยผู้ดำเนินการตามลักษณะของเครือข่ายและผู้รับและความน่าเชื่อถือในการส่งมอบที่ต้องการ ดังนั้นรหัสน้ำพุจึงถูกใช้ในอัตราการเข้ารหัสที่กำหนดแบบไดนามิกในขณะที่กำหนดเวลาออกอากาศไฟล์)

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

ตามมาตรฐาน

รหัส Raptorเป็นรหัส Fountain ที่มีประสิทธิภาพมากที่สุดในขณะนี้^{[ 2 ]}โดยมีอัลกอริทึมการเข้ารหัสและถอดรหัสแบบเชิงเส้นที่มีประสิทธิภาพสูงมาก และต้องการเพียง การดำเนินการ XOR จำนวนเล็กน้อยคงที่ ต่อสัญลักษณ์ที่สร้างขึ้นสำหรับการเข้ารหัสและการถอดรหัส^{[ 3 ]} IETF RFC 5053 ระบุรายละเอียดของ รหัส Raptor ที่เป็นระบบซึ่งได้รับการนำไปใช้ในมาตรฐานหลายมาตรฐานนอกเหนือจาก IETF เช่น ใน มาตรฐาน 3GPP MBMSสำหรับการส่งไฟล์ออกอากาศและบริการสตรีมมิ่ง มาตรฐาน DVB-H IPDCสำหรับการส่งบริการ IP ผ่าน เครือข่าย DVBและDVB-IPTVสำหรับการส่งบริการโทรทัศน์เชิงพาณิชย์ผ่านเครือข่าย IP รหัสนี้สามารถใช้กับสัญลักษณ์ต้นทางได้สูงสุด 8,192 สัญลักษณ์ในบล็อกต้นทาง และสัญลักษณ์ที่เข้ารหัสทั้งหมดได้สูงสุด 65,536 สัญลักษณ์ที่สร้างขึ้นสำหรับบล็อกต้นทาง รหัสนี้มีค่าใช้จ่ายการรับข้อมูลโดยเฉลี่ย 0.2% เมื่อนำไปใช้กับบล็อกแหล่งที่มาที่มีสัญลักษณ์แหล่งที่มา 1,000 ตัว และมีค่าใช้จ่ายการรับข้อมูลน้อยกว่า 2% ด้วยความน่าจะเป็น 99.9999% ^{[ 4 ]}ค่าใช้จ่ายการรับข้อมูลถูกกำหนดให้เป็นข้อมูลการเข้ารหัสเพิ่มเติมที่จำเป็นนอกเหนือจากความยาวของข้อมูลแหล่งที่มาเพื่อกู้คืนข้อมูลแหล่งที่มาดั้งเดิม โดยวัดเป็นเปอร์เซ็นต์ของขนาดของข้อมูลแหล่งที่มา ตัวอย่างเช่น หากค่าใช้จ่ายการรับข้อมูลคือ 0.2% นั่นหมายความว่าข้อมูลแหล่งที่มาขนาด 1 เมกะไบต์สามารถกู้คืนได้จากข้อมูลการเข้ารหัสขนาด 1.002 เมกะไบต์

รหัส Raptor ที่ล้ำหน้ากว่า มีความยืดหยุ่นมากกว่า และปรับปรุงประสิทธิภาพการรับสัญญาณให้ดีขึ้น เรียกว่า RaptorQ ได้รับการกำหนดไว้ในIETF RFC 6330 รหัส RaptorQ ที่กำหนดไว้นี้สามารถใช้กับสัญลักษณ์ต้นทางได้สูงสุด 56,403 สัญลักษณ์ในบล็อกต้นทาง และสัญลักษณ์ที่เข้ารหัสทั้งหมดได้สูงสุด 16,777,216 สัญลักษณ์ที่สร้างขึ้นสำหรับบล็อกต้นทาง รหัสนี้สามารถกู้คืนบล็อกต้นทางจากชุดสัญลักษณ์ที่เข้ารหัสใดๆ ที่เท่ากับจำนวนสัญลักษณ์ต้นทางในบล็อกต้นทางได้ด้วยความน่าจะเป็นสูง และในบางกรณีที่หายาก อาจกู้คืนได้จากจำนวนสัญลักษณ์ที่มากกว่าจำนวนสัญลักษณ์ต้นทางในบล็อกต้นทางเล็กน้อย รหัส RaptorQ เป็นส่วนสำคัญของการสร้างอินสแตนซ์ ROUTE ที่กำหนดไว้ใน ATSC A-331 (ATSC 3.0)

สำหรับการจัดเก็บข้อมูล

รหัสลบ (Erasure code) ถูกนำมาใช้ในแอปพลิเคชันการจัดเก็บข้อมูลเนื่องจากช่วยประหยัดจำนวนหน่วยจัดเก็บข้อมูลได้อย่างมหาศาลสำหรับระดับความซ้ำซ้อนและความน่าเชื่อถือที่กำหนดไว้ ข้อกำหนดในการออกแบบรหัสลบสำหรับการจัดเก็บข้อมูล โดยเฉพาะอย่างยิ่งสำหรับแอปพลิเคชันการจัดเก็บข้อมูลแบบกระจาย อาจแตกต่างกันอย่างมากเมื่อเทียบกับสถานการณ์การสื่อสารหรือการสตรีมข้อมูล หนึ่งในข้อกำหนดของการเข้ารหัสสำหรับระบบจัดเก็บข้อมูลคือรูปแบบที่เป็นระบบ กล่าวคือ สัญลักษณ์ข้อความดั้งเดิมเป็นส่วนหนึ่งของสัญลักษณ์ที่เข้ารหัส รูปแบบที่เป็นระบบช่วยให้สามารถอ่านสัญลักษณ์ข้อความได้โดยไม่ต้องถอดรหัสจากหน่วยจัดเก็บข้อมูล นอกจากนี้ เนื่องจากแบนด์วิดท์และภาระการสื่อสารระหว่างโหนดจัดเก็บข้อมูลอาจเป็นคอขวด รหัสที่อนุญาตให้มีการสื่อสารน้อยที่สุดจึงมีประโยชน์อย่างมาก โดยเฉพาะอย่างยิ่งเมื่อโหนดล้มเหลวและจำเป็นต้องสร้างระบบใหม่เพื่อให้ได้ระดับความซ้ำซ้อนเริ่มต้น ในแง่นั้น รหัส Fountain คาดว่าจะช่วยให้กระบวนการซ่อมแซมมีประสิทธิภาพในกรณีที่เกิดความล้มเหลว: เมื่อสัญลักษณ์ที่เข้ารหัสเพียงตัวเดียวหายไป ไม่ควรต้องมีการสื่อสารและการคำนวณมากเกินไประหว่างสัญลักษณ์ที่เข้ารหัสอื่นๆ เพื่อกู้คืนสัญลักษณ์ที่หายไป ในความเป็นจริง ความล่าช้าในการซ่อมแซมอาจมีความสำคัญมากกว่าการประหยัดพื้นที่จัดเก็บข้อมูลในบางครั้ง รหัสน้ำพุที่ซ่อมแซมได้^{[ 5 ]}คาดว่าจะตอบสนองวัตถุประสงค์การออกแบบรหัสน้ำพุสำหรับระบบจัดเก็บ การสำรวจโดยละเอียดเกี่ยวกับรหัสน้ำพุและการใช้งานสามารถพบได้ที่^{[ 6 ]}

มีการเสนอแนวทางที่แตกต่างในการจัดเก็บข้อมูลแบบกระจายโดยใช้รหัสน้ำพุใน Liquid Cloud Storage ^{[ 7 ]}^{[ 8 ]} Liquid Cloud Storage ใช้รหัสการลบขนาดใหญ่ เช่น รหัส RaptorQ ที่ระบุไว้ในIETF RFC 6330 (ซึ่งให้การปกป้องข้อมูลที่ดีกว่าระบบอื่นๆ อย่างมาก) โดยใช้กระบวนการซ่อมแซมพื้นหลัง (ซึ่งช่วยลดความต้องการแบนด์วิดท์ในการซ่อมแซมเมื่อเทียบกับระบบอื่นๆ อย่างมาก) และใช้การจัดระเบียบข้อมูลแบบสตรีม (ซึ่งช่วยให้เข้าถึงข้อมูลได้อย่างรวดเร็วแม้ว่าสัญลักษณ์ที่เข้ารหัสทั้งหมดจะไม่พร้อมใช้งานก็ตาม)

ดูเพิ่มเติม

รหัสออนไลน์
การเข้ารหัสเครือข่ายเชิงเส้น
การแบ่งปันความลับ
รหัสพายุทอร์นาโดซึ่งเป็นต้นกำเนิดของรหัสน้ำพุ

หมายเหตุ

^ J. Byers, M. Luby , M. Mitzenmacher , A. Rege (1998). "แนวทางน้ำพุดิจิทัลเพื่อการกระจายข้อมูลจำนวนมากอย่างน่าเชื่อถือ" (PDF ){{cite web}}: CS1 maint: multiple names: authors list ( link )
^ "เทคโนโลยี Qualcomm Raptor - การแก้ไขข้อผิดพลาดล่วงหน้า" 30 พฤษภาคม 2014 เก็บถาวรจากต้นฉบับเมื่อ 29 ธันวาคม 2010 เรียกดูเมื่อ 7 มิถุนายน2011
^ ( Shokrollahi 2006 )
^ T. Stockhammer, A. Shokrollahi, M. Watson, M. Luby, T. Gasiba (มีนาคม 2008). Furht, B.; Ahson, S. (บรรณาธิการ). "การแก้ไขข้อผิดพลาดล่วงหน้าของเลเยอร์แอปพลิเคชันสำหรับการออกอากาศมัลติมีเดียเคลื่อนที่" คู่มือการออกอากาศเคลื่อนที่: DVB-H, DMB, ISDB-T และ Media FLO . สำนักพิมพ์ CRC .{{cite journal}}: CS1 maint: multiple names: authors list ( link )
^ Asteris, Megasthenis; Dimakis, Alexandros G. (2012). "รหัส Fountain ที่ซ่อมแซมได้". IEEE Journal on Selected Areas in Communications . 32 (5): 1037– 1047. arXiv : 1401.0734 . doi : 10.1109/JSAC.2014.140522 . S2CID 1300984 .
^ Arslan, Suayb S. (2014). "ความซ้ำซ้อนแบบเพิ่มขึ้น รหัส Fountain และหัวข้อขั้นสูง". arXiv : 1402.6016 [ cs.IT ].
^ Luby, Michael; Padovani, Roberto; Richardson, Thomas J.; Minder, Lorenz; Aggarwal, Pooja (2019). "Liquid Cloud Storage". ACM Transactions on Storage . 15 : 1–49 . arXiv : 1705.07983 . doi : 10.1145/3281276 . S2CID 738764 .
↑ลูบี, ม.; ปาโดวานี ร.; ริชาร์ดสัน ต.; มายด์เดอร์ ล.; อัคการ์วาล, พี. (2017). "ที่เก็บข้อมูลคลาวด์เหลว" arXiv : 1705.07983v1 [ cs.DC ]

[1] J. Byers, M. Luby , M. Mitzenmacher , A. Rege (1998). "แนวทางน้ำพุดิจิทัลเพื่อการกระจายข้อมูลจำนวนมากอย่างน่าเชื่อถือ" (PDF ){{cite web}}: CS1 maint: multiple names: authors list ( link )

[2] "เทคโนโลยี Qualcomm Raptor - การแก้ไขข้อผิดพลาดล่วงหน้า" 30 พฤษภาคม 2014 เก็บถาวรจากต้นฉบับเมื่อ 29 ธันวาคม 2010 เรียกดูเมื่อ 7 มิถุนายน2011

[3] ( Shokrollahi 2006 )

[4] T. Stockhammer, A. Shokrollahi, M. Watson, M. Luby, T. Gasiba (มีนาคม 2008). Furht, B.; Ahson, S. (บรรณาธิการ). "การแก้ไขข้อผิดพลาดล่วงหน้าของเลเยอร์แอปพลิเคชันสำหรับการออกอากาศมัลติมีเดียเคลื่อนที่" คู่มือการออกอากาศเคลื่อนที่: DVB-H, DMB, ISDB-T และ Media FLO . สำนักพิมพ์ CRC .{{cite journal}}: CS1 maint: multiple names: authors list ( link )

[5] Asteris, Megasthenis; Dimakis, Alexandros G. (2012). "รหัส Fountain ที่ซ่อมแซมได้". IEEE Journal on Selected Areas in Communications . 32 (5): 1037– 1047. arXiv : 1401.0734 . doi : 10.1109/JSAC.2014.140522 . S2CID 1300984 .

[6] Arslan, Suayb S. (2014). "ความซ้ำซ้อนแบบเพิ่มขึ้น รหัส Fountain และหัวข้อขั้นสูง". arXiv : 1402.6016 [ cs.IT ].

[7] Luby, Michael; Padovani, Roberto; Richardson, Thomas J.; Minder, Lorenz; Aggarwal, Pooja (2019). "Liquid Cloud Storage". ACM Transactions on Storage . 15 : 1–49 . arXiv : 1705.07983 . doi : 10.1145/3281276 . S2CID 738764 .

[8] ลูบี, ม.; ปาโดวานี ร.; ริชาร์ดสัน ต.; มายด์เดอร์ ล.; อัคการ์วาล, พี. (2017). "ที่เก็บข้อมูลคลาวด์เหลว" arXiv : 1705.07983v1 [ cs.DC ]

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]