2009-12-09 13 views
9

मैं एक आगे त्रुटि-सुधार कोड की तलाश में हूं जो माइक्रोकंट्रोलर पर अपेक्षाकृत आसान/तेज़ है; एक पीसी पर डीकोड किया जाएगा ताकि यह अधिक जटिल हो सके।तेजी से CPUs को प्रेषित धीमी CPUs के उद्देश्य से कोड को सही करने में त्रुटि

मुझे त्रुटि-सुधार कोड के बारे में बहुत कुछ पता नहीं है और सरल हैमिंग कोड को छोड़कर वे सभी संभाल सकते हैं जितना मैं संभाल सकता हूं।

कोई सिफारिशें?

संपादित: मैं चीजों को ही समाप्त हो और कार्ल जवाब को स्वीकार करने के लिए जा रहा हूँ ... मुझे लगता है कि दो बातें मैं उल्लेख नहीं था वहाँ थे:

(1) मैं क्या सख्ती से नहीं जरूरत त्रुटि सुधार, यह मेरे लिए फायदेमंद है, और मुझे लगा कि कुछ त्रुटि सुधार एल्गोरिदम हो सकता है जो न्यूनतम लागत के लिए उचित लाभ था। हैमिंग कोड शायद सही फिट के बारे में हैं और यहां तक ​​कि ऐसा लगता है कि वे मेरे एन्कोडिंग एप्लिकेशन के लिए बहुत महंगा हो सकते हैं।

(2) त्रुटि सुधार की तुलना में अधिक लाभ एक त्रुटि का पालन करने वाले पैकेटों को ठीक से पुन: संसाधित करने की क्षमता है। (यदि मैं लंबे समय तक सिंक से बाहर निकलता हूं, तो यह बुरा है) तो मुझे लगता है कि अगर मैं चीजों को सरल रखता हूं तो यह बेहतर होता है।

+0

उपरोक्त, क्योंकि यह एक दिलचस्प सवाल है, और क्योंकि मुझे समझदार लोगों से मदद की आवश्यकता हो सकती है। इसके अलावा, मेरी टिप्पणियों में अद्यतन सुझाव। –

उत्तर

3

कोड को सही करने में त्रुटि के साथ समस्या यह है कि वे आपको एकल बिट या शायद 2 बिट त्रुटियों से पुनर्प्राप्त करने देंगे, लेकिन आम तौर पर बड़े नुकसान का पता लगाने या पैच नहीं करते हैं।

इस प्रकार, मेरी सिफारिश आपके डेटा स्ट्रीम को ब्लॉक में विभाजित करने के बजाय होगी (1 केबी, 10 केबी, ... 1 एमबी अधिकतर) और प्रत्येक ब्लॉक के लिए चेकसम की गणना करें। फिर, जब डेटा अन्य सीपीयू पर आता है, तो आप यह सुनिश्चित कर सकते हैं कि यह सही है या नहीं, और उस ब्लॉक के पुन: प्रेषण का अनुरोध करें। तो प्राप्तकर्ता कंप्यूटर या तो अगले ब्लॉक, या नकारात्मक-स्वीकृति के लिए स्वीकार करेगा और प्रतीक्षा करेगा और फिर से भेजने की उम्मीद करेगा।

हां, हम यहां टीसीपी/आईपी का सबसेट लागू कर रहे हैं। लेकिन एक कारण यह प्रोटोकॉल इतना सफल था: यह काम करता है!

चेकसम के लिए, मैं सीआरसी -32 की सिफारिश करता हूं। इसके लिए (मुझे लगता है) 256 32-बिट संख्याओं और कुछ उचित रूप से आसान गणना (सरणी अनुक्रमण, OR और XOR, अधिकतर) की एक तालिका की आवश्यकता होती है, इसलिए यह "गूंगा" CPU की गणना करने के लिए काफी आसान है।

+1

दूसरे शब्दों में, आप आगे त्रुटि सुधार के खिलाफ वकालत कर रहे हैं, और इसके बजाय चेकसम के साथ एक अधिक पारंपरिक "इंटरैक्टिव" प्रोटोकॉल और स्वीकृति और क्या नहीं। इस एप्लिकेशन में स्पष्ट स्वीकृति का उपयोग व्यावहारिक नहीं है (लूप विलंबता मुझे आवश्यक थ्रूपुट की तुलना में असहिष्णु होगी), इसलिए यह वही नहीं है जो मैं ढूंढ रहा हूं, लेकिन इस तरह की सलाह अन्य अनुप्रयोगों के लिए उपयोगी है। –

+0

ओह, ठीक है। इससे चीजों को थोड़ा सा बदल जाता है। मेरे अनुभव में, और मैंने वास्तव में एम्बेडेड माइक्रो कंप्यूटर सिस्टम पर आईओ प्रोग्राम किया है, संचार या तो बेकार ढंग से चला जाता है या नहीं। जब तक कि आप बहुत शोर वातावरण में न हों, आपको एकल-बिट सुधार द्वारा नियंत्रित त्रुटियों की तरह नहीं मिलेगी। मुझे पता है कि यह अभी भी आपके मूल प्रश्न में मदद नहीं कर रहा है ... मैं देखता हूं कि मैं क्या खोद सकता हूं। –

+0

ठीक है, मैंने विकिपीडिया लेख और संदर्भों को देखा है ... मैं शायद प्रस्तावित एल्गोरिदम में से एक को कार्यान्वित कर सकता हूं, लेकिन यह गर्दन में दर्द होगा। क्या आपके पास पर्याप्त बैंडविड्थ है कि आप कुछ बेवकूफ और सरल कर सकते हैं? ब्लॉक में अपना डेटा भेजें, और प्रत्येक ब्लॉक को 3 बार भेजें। हर बिट के लिए, 3 जीत में से 2 सर्वश्रेष्ठ। एक पूर्ण आगे ईसीसी एल्गोरिदम, 2 वाक्यों में वर्णित :) –

4

मुझे काफी आसानी से नहीं मिला है कि आप कितना ओवरहेड कर सकते हैं। आपकी टिप्पणी में आप कहते हैं कि 16-बिट त्रुटि का पता लगाने/सुधार कोड सही है, लेकिन आप यह निर्दिष्ट नहीं करते कि आप कितने ब्लॉक को जोड़ रहे हैं। सार्थक होने के लिए, आपको शायद प्रतिशत के रूप में स्वीकार्य ओवरहेड व्यक्त करना चाहिए। 64 बिट्स डेटा के लिए त्रुटि सुधार के 16 बिट्स डेटा के किलोबाइट के त्रुटि सुधार के 16 बिट्स से बहुत अलग हैं ..

यदि आप 15-20% ओवरहेड की तरह कुछ ले सकते हैं, तो आप शायद विटरबी डीकोडर के साथ संकल्पक कोड। यह बेहद आक्रामक है - संक्रामक कोडर काफी सरल है (मूल रूप से एक शिफ्ट रजिस्टर, एक्सओआर के लिए उत्पादन आउटपुट के साथ)। वास्तव में एक बड़ा 16-बिट रजिस्टर का उपयोग आधा दर्जन या तो एक्सओआर के साथ कर सकता है।

सौभाग्य से आपके पास डिकोडिंग को संभालने के लिए एक भारी ड्यूटी कंप्यूटर है, क्योंकि एक विटरबी डिकोडर एक डरावना जानवर हो सकता है। विशेष रूप से जब आप ओवरहेड को कम करने के लिए एक बड़े एन्कोडर का उपयोग करते हैं, तो डिकोडर विस्फोट का आकार। कोड समूह के आकार के संबंध में डिकोडर का आकार घातीय है।

टर्बो कोड का उल्लेख किया गया था।ये विदरबी डीकोडर्स के साथ संकल्पक कोडों की तुलना में उपलब्ध बैंडविड्थ का बेहतर उपयोग कर सकते हैं - लेकिन वे एक बहुत अधिक जटिल एन्कोडर का उपयोग करते हैं - एक विशिष्ट प्रकार (रिकर्सिव व्यवस्थित संक्रामक एन्कोडर्स) के कम से कम दो संकल्पक कोडर। ऐसे में, वे आपके विनिर्देश को भी फिट नहीं लगते हैं।

+0

पुन: ओवरहेड: डेटा या गणना में या तो बहुत कुछ नहीं। पैकेट छोटे होते हैं, 8-16 बाइट सामान्य होते हैं, और मैं प्रति पैकेट ओवरहेड से 16 बिट्स से अधिक नहीं देखना चाहता हूं। एक पैकेट इकाई से अलग कोड इकाई रखने की कम्प्यूटेशनल जटिलता (उदा। प्रति कोड एकाधिक पैकेट या प्रति पैकेट एकाधिक कोड) शायद अस्वीकार्य है।और दुर्भाग्यवश एक हार्डवेयर समाधान समाप्त हो गया है, इसलिए एक संकल्पक कोडर भी, यदि मैं आपको सही समझता हूं, तो शायद सॉफ्टवेयर में बहुत अधिक काम है। लेकिन कुछ अच्छे स्पष्टीकरण + सुझावों के लिए +1। –

0

मैं आगे-त्रुटि सुधार के पैकेट-आधारित रूप का उपयोग करने का सुझाव देना चाहता हूं। यदि आपको छह बराबर लंबाई वाले पैकेट भेजना है, तो उनमें से प्रत्येक को "6 का ​​पैकेट 1", "6 में से 2" आदि के रूप में पहचानने के लिए पर्याप्त जानकारी के साथ भेजें, एक और पैकेट के साथ जिसका पहला पेलोड बाइट xor है पैकेट 1-6 का पहला पेलोड बाइट, जिसका दूसरा पेलोड बाइट पैकेट 1-6, आदि के दूसरे बाइट का xor है। कोड जो सात कुल में से कोई भी छह पैकेट प्राप्त करता है, वह गायब व्यक्ति को पुनर्निर्माण करने में सक्षम होगा। मामूली वृद्धि के रूप में, "विषम" पैकेट के लिए एक "समानता" पैकेट और "विषम" लोगों के लिए दूसरा उपयोग करें। यदि आप ऐसा करते हैं, तो सिस्टम किसी भी विस्फोट त्रुटि से पुनर्प्राप्त करने में सक्षम होगा जो पैकेट से अधिक नहीं है।