Score:1

การแก้ไขข้อผิดพลาด "ย้อนกลับ" รีด-โซโลมอน ให้คำนำหน้าอินพุต

ธง ua

ฉันมีสตริง $S$ ของความยาว (พูด) 34 ที่ฉันรู้ (พูด) 24 ไบต์แรก แต่ไม่ใช่ 10 สุดท้าย ฉันยังมีรหัสแก้ไขข้อผิดพลาด 10 ไบต์ $RS_{44,34}(S)$ เต็ม. ฉันมีความหวังที่จะฟื้นตัวหรือไม่ $S$?

จำนวนข้อมูลของ $S$ ที่ฉันพลาดไปมากเกินกว่าการรับประกันทางทฤษฎีของ Reed-Solomon (ซึ่งฉันคิดว่าในกรณีนี้คือ 3 ไบต์) แต่ในขณะเดียวกันก็มี $2^{80}$ ค่าที่เป็นไปได้สำหรับส่วนที่ไม่รู้จักของ $S$, และนอกจากนี้ยังมี $2^{80}$ ผลลัพธ์ที่เป็นไปได้สำหรับการแก้ไขข้อผิดพลาด หากเราต้องวนซ้ำค่าที่เป็นไปได้ทั้งหมดสำหรับส่วนที่ไม่รู้จักของ $S$ฉันคาดหวังอย่างไร้เดียงสาว่าจะมีประมาณ 1 รายการที่ตรงกับการแก้ไขข้อผิดพลาด แต่ $2^{80}$ มากเกินไปที่จะดุร้ายกำลัง

มีเทคนิคใดบ้างที่สามารถกู้คืน (หรืออย่างน้อยก็ลดพื้นที่สถานะสำหรับ) อินพุตโดยพิจารณาจาก Reed-Solomon EC มีเหตุผลใดที่จะคิดไม่ทางใดก็ทางหนึ่งว่า RS มีความปลอดภัยในการเข้ารหัสในแง่นี้หรือไม่?

สำหรับพื้นหลัง แอปพลิเคชัน "ในโลกแห่งความเป็นจริง" ที่นี่คือฉันมีโค้ด QR (เวอร์ชัน 2, L-level EC) ที่ฉันไม่มีบิตข้อมูลหลัก แต่ฉันมีบิต EC ฉันรู้ว่าข้อมูลคือ URL ของโดเมนใดโดเมนหนึ่ง ดังนั้นคำนำหน้า

Score:1
ธง my

มีเทคนิคใดบ้างที่สามารถกู้คืน (หรืออย่างน้อยก็ลดพื้นที่สถานะสำหรับ) อินพุตโดยพิจารณาจาก Reed-Solomon EC

คุณโชคดี Reed-Solomon เป็นโค้ดเชิงเส้น นั่นคือส่วนแก้ไขข้อผิดพลาดเป็นฟังก์ชันเชิงเส้นของอินพุต และอันที่จริงแล้ว การแก้ไขอินพุตทั้งหมดยกเว้น 10 ไบต์ถือเป็น Bijection

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

Score:0
ธง sa

ไม่ใช่รหัสทั้งหมดที่มีคุณสมบัติที่ดีที่รหัส RS มี ซึ่งก็คือทุกรหัส $k$ สัญลักษณ์เป็นชุดข้อมูลที่สามารถใช้สร้างโค้ดเวิร์ดเดิมขึ้นใหม่ได้

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

ตัวอย่างเช่นสิ่งนี้ กระดาษล่าสุด นำเสนออัลกอริธึมการถอดรหัสที่มีประสิทธิภาพสำหรับรหัส RS บนฟิลด์จำกัดด้วย $คิว$ องค์ประกอบ, $\mathbb{F}_q$ กับ $q=2^m,$ ใน $O(q \log_q q^2)$ เวลา. มันใช้การแปลงวอลช์เพื่อทำการแก้ไขแบบลากรองจ์

โพสต์คำตอบ

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