Guruswami–Sudan list decoding algorithm
குறியீட்டு கோட்பாட்டில், பட்டியல் டிகோடிங் என்பது பல பிழைகளின் முன்னிலையில் பிழை-திருத்த குறியீடுகளின் தனித்துவமான டிகோடிங்கிற்கு மாற்றாகும். ஒரு குறியீட்டில் ஒப்பீட்டு தூரம் இருந்தால், குறியீட்டு வார்த்தை சின்னங்களின் ஒரு பகுதி வரை சிதைந்திருக்கும் போது குறியிடப்பட்ட செய்தியை மீட்டெடுப்பது கொள்கையளவில் சாத்தியமாகும். ஆனால் பிழை விகிதம் அதிகமாக இருக்கும்போது, இது பொதுவாக சாத்தியமில்லை. குறியிடப்பட்ட செய்திகளின் குறுகிய பட்டியலை வெளியிட டிகோடரை அனுமதிப்பதன் மூலம் பட்டியல் டிகோடிங் அந்த சிக்கலை முறியடிக்கிறது. பட்டியல் டிகோடிங் பிழைகளின் பகுதியை விட அதிகமாக சரிசெய்ய முடியும். பட்டியல் டிகோடிங்கிற்கு பல பல்லுறுப்புக்கோவை நேர வழிமுறைகள் உள்ளன. இந்த கட்டுரையில், ரீட்-சாலமன் (ஆர்எஸ்) குறியீடுகளுக்கான ஒரு வழிமுறையை முதலில் வழங்குகிறோம், இது பிழைகளை சரிசெய்கிறது மற்றும் மது சூடான் காரணமாகும். அதைத் தொடர்ந்து, மேம்பட்ட குருசாமி-சுதன் பட்டியல் டிகோடிங் வழிமுறையை விவரிக்கிறோம், இது பிழைகள் வரை சரிசெய்ய முடியும். வெவ்வேறு வழிமுறைகளுக்கான விகிதம் ஆர் மற்றும் தூரத்தின் ஒரு வரைபடம் இங்கே. https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/81/Graph.jpg அல்காரிதம் 1 (சூடானின் பட்டியல் டிகோடிங் அல்காரிதம்) சிக்கல் அறிக்கை உள்ளீடுஃ ஒரு புலம்; n தனித்துவமான ஜோடி உறுப்புகள்; மற்றும் முழு எண்கள் மற்றும். வெளியீடுஃ திருப்திகரமான அனைத்து செயல்பாடுகளின் பட்டியலும் அதிகபட்சமாக ஒரு பல்லுறுப்புக்கோவை ஆகும். சூடானின் வழிமுறையை நன்கு புரிந்துகொள்ள, ஒருவர் முதலில் மற்றொரு வழிமுறையை தெரிந்து கொள்ள விரும்பலாம், இது முந்தைய பதிப்பாகவோ அல்லது ஆர்எஸ் குறியீடுகளை டிகோடிங் செய்வதற்கான வழிமுறைகளின் அடிப்படை பதிப்பாகவோ கருதப்படலாம்-பெர்லெகாம்ப்-வெல்ச் வழிமுறை. வெல்ச் மற்றும் பெர்லெகாம்ப் ஆரம்பத்தில் ஒரு வழிமுறையுடன் வந்தனர், இது பல்லுறுப்புக்கோவை நேரத்தில் சிறந்த வரம்புடன் சிக்கலை தீர்க்க முடியும். சூடானின் வழிமுறையின் வழிமுறை கிட்டத்தட்ட பெர்லெகாம்ப்-வெல்ச் வழிமுறையின் வழிமுறையைப் போன்றது, படி 1 இல் தவிர, ஒருவர் வரம்புக்குட்பட்ட டிகிரியின் இரு மாறுபட்ட பல்லுறுப்புக்கோவையை கணக்கிட விரும்புகிறார். ரீட்-சாலமன் குறியீட்டிற்கான சூடானின் பட்டியல் டிகோடிங் வழிமுறை, இது பெர்லெகாம்ப் மற்றும் வெல்ச் வழிமுறையின் முன்னேற்றமாகும், இது சிக்கலை தீர்க்க முடியும். இந்த பிணைப்பு தனித்துவமான டிகோடிங் பிணைப்பை விட சிறந்தது. அல்காரிதம் வரையறை 1 (எடையுள்ள டிகிரி) எடைகளுக்கு, மோனோமியலின் எடையுள்ள டிகிரி ஆகும். ஒரு பல்லுறுப்புக்கோவையின்-எடையுள்ள டிகிரி என்பது, பூஜ்ஜியமற்ற குணகங்களைக் கொண்ட மோனாமியல்களின் மீது, மோனாமியலின்-எடையுள்ள டிகிரியின் அதிகபட்சமாகும். எடுத்துக்காட்டாக,-டிகிரி 7 அல்காரிதம் உள்ளதுஃ உள்ளீடுகள்ஃ; {}/* அளவுருக்கள் l, m பின்னர் அமைக்கப்படும். படி 1: பூஜ்ஜியமற்ற இருவேறு பல்லுறுப்புக்கோவை திருப்திகரமான-எடையுள்ள டிகிரியைக் கண்டறியவும் ஒவ்வொருவருக்கும், படி 2. பகுக்கமுடியாத காரணிகளாக க்யூ காரணி. படி 3. அனைத்து பல்லுறுப்புக்கோவைகளையும் வெளியீடு செய்யுங்கள், அதாவது Q இன் ஒரு காரணி மற்றும் பகுப்பாய்வின் குறைந்தபட்சம் t மதிப்புகளுக்கு மேலே உள்ள வழிமுறை பல்லுறுப்புக்கோவை நேரத்தில் இயங்குகிறது மற்றும் சரியான முடிவை வெளியிடுகிறது என்பதை நிரூபிக்க வேண்டும். பின்வரும் உரிமைகோரல்களை நிரூபிப்பதன் மூலம் அதைச் செய்யலாம். கூற்று 1: (2) ஐ திருப்திப்படுத்தும் ஒரு சார்பு இருந்தால், ஒருவர் அதை பல்லுறுப்புக்கோவை நேரத்தில் காணலாம். ஆதாரம்ஃ-எடையுள்ள டிகிரியின் இரு மாறுபட்ட பல்லுறுப்புக்கோவையை தனித்துவமாக இவ்வாறு எழுதலாம் என்பதை நினைவில் கொள்க. பின்னர் ஒவ்வொருவருக்கும், கட்டுப்பாடுகளை பூர்த்தி செய்யும் குணகங்களைக் கண்டறிய வேண்டும். இது அறியப்படாத {} களில் உள்ள சமன்பாடுகளின் நேரியல் தொகுப்பாகும். பல்லுறுப்புக்கோவை நேரத்தில் காஸியன் நீக்குதலைப் பயன்படுத்தி ஒரு தீர்வைக் காணலாம். உரிமைகோரல் 2: திருப்திகரமான ஒரு செயல்பாடு இருந்தால் (2) ஆதாரம்ஃ பூஜ்ஜியமற்ற தீர்வு இருப்பதை உறுதிப்படுத்த, உள்ள குணகங்களின் எண்ணிக்கை கட்டுப்பாடுகளின் எண்ணிக்கையை விட அதிகமாக இருக்க வேண்டும். அதிகபட்ச டிகிரி இன் m என்றும் அதிகபட்ச டிகிரி இன் என்றும் வைத்துக்கொள்வோம். பின்னர் அதன் அளவு அதிகபட்சமாக இருக்கும். நேரியல் அமைப்பு ஒரே மாதிரியானது என்பதை ஒருவர் பார்க்க வேண்டும். இந்த அமைப்பு அனைத்து நேரியல் கட்டுப்பாடுகளையும் பூர்த்தி செய்கிறது. இருப்பினும் இது (2) ஐ திருப்திப்படுத்தாது, ஏனெனில் தீர்வு ஒரே மாதிரியாக பூஜ்ஜியமாக இருக்கலாம். பூஜ்ஜியமற்ற தீர்வு இருப்பதை உறுதி செய்ய, நேரியல் அமைப்பில் அறியப்படாதவர்களின் எண்ணிக்கை இருப்பதை உறுதி செய்ய வேண்டும், இதனால் ஒருவர் பூஜ்ஜியமற்றதைக் கொண்டிருக்க முடியும். இந்த மதிப்பு n ஐ விட அதிகமாக இருப்பதால், கட்டுப்பாடுகளை விட அதிக மாறிகள் உள்ளன, எனவே பூஜ்ஜியமற்ற தீர்வு உள்ளது. கூற்று 3: ஒரு செயல்பாடு திருப்திகரமாக இருந்தால் (2) மற்றும் செயல்பாடு திருப்திகரமாக இருந்தால் (1), பின்னர் ஆதாரத்தைப் பிரிக்கிறதுஃ ஒரு செயல்பாட்டைக் கவனியுங்கள். இது ஒரு பல்லுறுப்புக்கோவை, மேலும் இது அதிகபட்சமாக டிகிரியைக் கொண்டுள்ளது என்று வாதிடுகிறது. எந்த மோனோமியலையும் கருத்தில் கொள்ளுங்கள். அதிகபட்சமாக-எடையுள்ள பட்டம் இருப்பதால், ஒருவர் அதைச் சொல்லலாம். எனவே இந்த சொல் அதிகபட்சமாக ஒரு பல்லுறுப்புக்கோவை ஆகும். எனவே அதிகபட்சமாக டிகிரி உள்ளது அடுத்தது ஒரே மாதிரியான பூஜ்ஜியமாக வாதிடுகிறது. எந்த நேரத்திலும் பூஜ்ஜியமாக இருப்பதால், கண்டிப்பாக புள்ளிகளை விட அதிகமாக இருந்தால் அது பூஜ்ஜியம் என்று ஒருவர் கூறலாம். எனவே அதன் டிகிரியை விட அதிக பூஜ்ஜியங்களைக் கொண்டுள்ளது, எனவே ஒரே மாதிரியாக பூஜ்ஜியமாக உள்ளது, இது மற்றும் உகந்த மதிப்புகளைக் கண்டுபிடிப்பதைக் குறிக்கிறது. கொடுக்கப்பட்ட மதிப்புக்கு, இரண்டாவது நிபந்தனை வைத்திருக்கும் மிகச்சிறியதை ஒருவர் கணக்கிட முடியும் என்பதை நினைவில் கொள்க இரண்டாவது நிபந்தனையை மாற்றுவதன் மூலம் ஒருவர் அதிகபட்சமாக இந்த மதிப்பை முதல் நிபந்தனையாக மாற்றலாம். சமன்பாட்டின் வழித்தோன்றலை எடுத்து அதை பூஜ்ஜியத்துடன் சமன் செய்வதன் மூலம் ஒருவர் பெறுவார், மதிப்பை மீண்டும் மாற்றுவதன் மூலம் ஒருவர் அல்காரிதம் 2 ஐப் பெறுவார் (குருசாமி-சுதன் பட்டியல் டிகோடிங் அல்காரிதம்) வரையறை மதிப்பீடு தொகுப்பு மற்றும் நேர்மறை முழு எண்ணுடன் வரையறுக்கப்பட்ட புலத்தின் மீது ஒரு ரீட்-சாலமன் குறியீட்டைக் கருத்தில் கொண்டு, குருசாமி-சுதன் பட்டியல் டிகோடர் ஒரு திசையனை உள்ளீடாக ஏற்றுக்கொள்கிறது, மேலும் குறியீட்டு சொற்களுடன் 1 முதல் 1 வரை தொடர்புடைய டிகிரியின் பல்லுறுப்புக்கோவைகளின் பட்டியலை வெளியிடுகிறது. இரு மாறுபட்ட பல்லுறுப்புக்கோவையில் கூடுதல் கட்டுப்பாடுகளைச் சேர்ப்பதே யோசனை, இதன் விளைவாக வேர்களின் எண்ணிக்கையுடன் கட்டுப்பாடுகளும் அதிகரிக்கின்றன. பெருக்கம் ஒரு இரு-மாறுபாடு பல்லுறுப்புக்கோவை எந்த டிகிரி காலமும் இல்லாத வழிமுறையில் பெருக்கத்தின் பூஜ்ஜியத்தைக் கொண்டுள்ளது, இதில் x-டிகிரி எந்த x காலத்தின் அதிகபட்ச டிகிரியாக வரையறுக்கப்படுகிறது எடுத்துக்காட்டாகஃ https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig1.jpg எனவே, (0,0) இல் பெருக்கம் 1 இன் பூஜ்ஜியத்தைக் கொண்டுள்ளது. விடுங்கள். https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig2.jpg எனவே, (0,0) இல் பெருக்கம் 1 இன் பூஜ்ஜியத்தைக் கொண்டுள்ளது. எனவே, (0,0) இல் பெருக்கம் 2 இன் பூஜ்ஜியத்தைக் கொண்டிருக்கட்டும். இதேபோல், பின்னர் என்றால், பெருக்கம் 2 இல் பூஜ்ஜியத்தைக் கொண்டுள்ளது. பெருக்கத்தின் பொதுவான வரையறை எந்த நேரத்தில் பெருக்கத்தின் பூஜ்ஜியத்தைக் கொண்டிருந்தால் அதன் வேர்களைக் கொண்டுள்ளது. அல்காரிதம் கடத்தப்பட்ட குறியீட்டுப் சொல் அனுப்பப்பட்ட குறியீட்டுப் வார்த்தையின் ஆதரவு தொகுப்பாகவும் பெறப்பட்ட வார்த்தையாகவும் இருக்கட்டும் அல்காரிதம் பின்வருமாறுஃ பெறப்பட்ட திசையனுக்கு, பூஜ்ஜியமற்ற இரு-மாறுபாடு பல்லுறுப்புக்கோவையை அதிகபட்சமாக எடையுள்ள டிகிரியுடன் உருவாக்குங்கள், இது ஒவ்வொரு புள்ளியிலும் பூஜ்ஜிய பெருக்கத்தைக் கொண்டுள்ளது. எனவே, இந்த படி குறியீட்டு சொற்களின் பட்டியலை வெளியிடுகிறது. பகுப்பாய்வு இன்டர்பொலேஷன் படி லெம்மாஃ இன்டர்பொலேஷன் படி என்பது லெட் வேர் அண்ட் தேன், (சமன்பாடு 1) இன் குணகங்களின் மீதான கட்டுப்பாடுகளைக் குறிக்கிறது, அங்கு சமன்பாடு 1 இன் ஆதாரம்ஃ. லெம்மாவின் இருபடி விரிவாக்க ஆதாரத்தைப் பயன்படுத்துதல்ஃ பல்லுறுப்புக்கோவை பெருக்கத்தின் பூஜ்ஜியத்தைக் கொண்டுள்ளது என்றால் அது மதிப்புகளை எடுக்க முடியும். எனவே, கட்டுப்பாடுகளின் மொத்த எண்ணிக்கை இவ்வாறு, தேர்வுகளின் எண்ணிக்கையை உருவாக்க முடியும் மற்றும் ஒவ்வொரு தேர்வும் காரணிமயமாக்கல் படி முன்மொழிவுகளின் குணகங்களின் மீதான கட்டுப்பாடுகளைக் குறிக்கிறதுஃ ஆதாரத்தின் ஒரு காரணியாக இருந்தால்ஃ ஒரு காரணி என்பதால், எங்கு, மீதமுள்ளதை வகுக்கும்போது பெறப்பட்ட ஈவு என்பதைக் குறிக்க முடியும். மேலே நிரூபிக்கப்பட்டபடி, LHS என்பது குணகங்களின் எண்ணிக்கையின் மேல் வரம்பாகும் மற்றும் RHS என்பது முன்பு நிரூபிக்கப்பட்ட லெம்மாவாகும். எனவே, குருசாமி-சூடான் பட்டியல் டிகோடிங் அல்காரிதம் ரீட்-சாலமன் குறியீடுகளை பிழைகள் வரை டிகோட் செய்ய முடியும் என்பதை நிரூபித்தது. குறிப்புகள் https://web.archive.org/web/20100702120650/http:// www. cse. buffalo. edu/~ atri/courses/quoting-theory/https://www.cs.cmu.edu ~ venkatg/pubs/پیپر்கள்/லிஸ்ட்டிகோடிங்-NOW.pdf http://www.mendeley.com/research/algebraic-softdecision-decoding-reedsolomon-codes R. J. மெக்லிஸ். ரீட்-சாலமன் குறியீடுகளுக்கான குருசாமி-சுதன் டிகோடிங் அல்காரிதம். எம் சூடான். பிழை-திருத்த வரம்பிற்கு அப்பால் ரீட் சாலமன் குறியீடுகளின் டிகோடிங். குறியீட்டு கோட்பாடு