आगे त्रुटि सुधार
मेरे पास निम्नलिखित गुणों के साथ एक डेटा स्ट्रीम है:
- बाइनरी
- गतिशील लंबाई
- 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, लेकिन यह ध्यान में रखते हुए डिज़ाइन किया गया है कि आसन्न बिट-फ़्लिप होने की संभावना अधिक है।
जवाब
अपनी त्रुटियों को द्विपद के रूप में दर्शाते हुए, आइए देखें कि एक त्रुटि को सही करने पर क्या होता है:
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.$