आगे त्रुटि सुधार

Sep 29 2020

मेरे पास निम्नलिखित गुणों के साथ एक डेटा स्ट्रीम है:

  • बाइनरी
  • गतिशील लंबाई
  • 20 बिट्स के ब्लॉक में आता है
  • कोई भी यादृच्छिक बिट्स एक त्रुटि बनाते हुए फ्लिप हो सकता है (अधिक संभावना नहीं है कि एक साथ फ्लिप करने के लिए आसन्न बिट्स)
  • मैं डेटा के रूप में लगभग 16 बिट्स का उपयोग करना चाहूंगा और प्रति ब्लॉक अतिरेक के लिए 4, लेकिन मैं उस नंबर को बदलने के लिए खुला हूं
  • थोड़ी सी सही होने की संभावना 97% के आसपास है
  • आदर्श रूप से, कोड प्रति ब्लॉक 2 बिट्स को सही करने में सक्षम होगा
  • ब्लॉकों की मात्रा बल्कि छोटी होगी, आमतौर पर 1-6।

इस परिदृश्य में उपयोग करने के लिए एक अच्छा कोड क्या होगा? मैंने रीड-सोलोमन के बारे में सोचा, लेकिन इस लेख के अनुसार यह एक खराब विकल्प होगा:

if a data stream is not characterized by error bursts or drop-outs but by random single bit errors, 
a Reed-Solomon code is usually a poor choice. More effective codes are available for this case. 

मैंने भी देखा है Bossen's b-adjacent algorithm, लेकिन यह ध्यान में रखते हुए डिज़ाइन किया गया है कि आसन्न बिट-फ़्लिप होने की संभावना अधिक है।

जवाब

1 kodlu Sep 30 2020 at 18:40

अपनी त्रुटियों को द्विपद के रूप में दर्शाते हुए, आइए देखें कि एक त्रुटि को सही करने पर क्या होता है:

0 या 1 त्रुटियों की संभावना है $$q=(1-p)^{20}+20(1-p)^{19}p$$ जो लगभग है $0.88$ के लिये $p=0.03,$ तो एक त्रुटि को सुधारते समय आपकी कोडित त्रुटि की संभावना है $0.12$।

बिना कोडिंग के त्रुटि की संभावना है $1-(1-p)^{20}$ जो आसपास है $0.456$ इसलिए यदि आप कोडिंग का उपयोग करते हैं तो आपको काफी सुधार मिलता है।

इस कागज के अनुसार यहाँ दिया गया है$r\geq 3,$ तथा $2^{r-1}+1\leq n\leq 2^r-1,$ वहां एक $[n,n-r,3]$कुछ अच्छा डबल त्रुटि का पता लगाने के गुणों के साथ छोटा हैमिंग कोड। कब$n=20,$ यह देता है $r=5,$ तो आपके पास ए $[n,n-r,3]=[20,15,3]$ शॉर्ट हैमिंग कोड को ठीक करने में एक त्रुटि और आप संचारित कर सकते हैं $k=15$ लंबाई प्रति ब्लॉक बिट्स $n=20.$