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. ઈરીડ્યુસિબલ પરિબળોમાં પરિબળ Q. પગલું 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 શૂન્ય છે. ધારો કે https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig3.jpg તેથી, (0,0) પર ગુણાકાર 2 શૂન્ય છે. તેવી જ રીતે, જો પછી, ગુણાકાર 2 પર શૂન્ય છે. ગુણાકારની સામાન્ય વ્યાખ્યાના મૂળિયા હોય છે, જો તેમાં ક્યારે ગુણાકાર શૂન્ય હોય. એલ્ગોરિધમ ટ્રાન્સમિટ કરેલ કોડવર્ડને ટ્રાન્સમિટ કરેલ કોડવર્ડનો આધાર સમૂહ અને પ્રાપ્ત કરેલ શબ્દ હોવો જોઈએ અલ્ગોરિધમ નીચે મુજબ છેઃ પ્રાપ્ત વેક્ટર માટે, મહત્તમ ભારિત ડિગ્રી સાથે બિન-શૂન્ય દ્વિ-ચલ બહુપદી બનાવો જેમાં દરેક બિંદુ પર ગુણાકાર શૂન્ય હોય જ્યાં ફેક્ટરાઇઝેશન પગલું ફોર્મના તમામ પરિબળો શોધો અને ઓછામાં ઓછા ક્યાં અને ક્યાં ડિગ્રીની બહુપદી છે તેના મૂલ્યો માટે યાદ કરો કે ડિગ્રીની બહુપદીઓ કોડવર્ડ્સ સાથે 1 થી 1 પત્રવ્યવહારમાં છે. તેથી, આ પગલું કોડવર્ડ્સની સૂચિનું આઉટપુટ આપે છે. વિશ્લેષણ ઇન્ટરપોલેશન પગલું લેમ્માઃ ઇન્ટરપોલેશન પગલું લેટ્સ વ્હેયર એન્ડ થેન, (સમીકરણ 1) ના ગુણાંક પર મર્યાદાઓ સૂચવે છે જ્યાં સમીકરણ 1 નો પુરાવોઃ. દ્વિપદી વિસ્તરણનો ઉપયોગ લેમ્માનો પુરાવોઃ બહુપદીમાં ગુણાકાર શૂન્ય હોય છે, જો કે તે મૂલ્યોને આ રીતે લઈ શકે છે. આમ, અવરોધોની કુલ સંખ્યા છે આમ, પસંદગીઓની સંખ્યા માટે કરી શકાય છે અને દરેક પસંદગી ફેક્ટરાઇઝેશન પગલું દરખાસ્તના ગુણાંક પર અવરોધો સૂચવે છેઃ જો તે સાબિતીનું પરિબળ છેઃ કારણ કે, તે એક પરિબળ છે, તેને આ રીતે રજૂ કરી શકાય છે કે જ્યાં, જ્યારે તેને વિભાજીત કરવામાં આવે ત્યારે મેળવેલ ભાગાંશ બાકી છે. ઉપર દર્શાવ્યા મુજબ, જ્યાં એલ. એચ. એસ. એ ગુણાંકની સંખ્યા પર ઉપલી સીમા છે અને આર. એચ. એસ. એ અગાઉ સાબિત થયેલ લેમ્મા છે. તેથી, અવેજી, તેથી સાબિત થયું કે, ગુરુસ્વામી-સુદાન સૂચિ ડીકોડિંગ અલ્ગોરિધમ ભૂલો સુધી રીડ-સોલોમન કોડને ડીકોડ કરી શકે છે. સંદર્ભો https://web.archive.org/web/20100702120650/http:// સી. એસ. ઈ. બફેલો. એડુ/~ એટ્રી/અભ્યાસક્રમો/કોડિંગ-થિયરી/https://www.cs.cmu.edu ~ વેન્કટગ/પબ્સ/કાગળો/લિસ્ટકોડિંગ-NOW.pdf http://www.mendeley.com/research/algebraic-softdecision-decoding-reedsolomon-codes આર. જે. મેકઈલીસ. રીડ-સોલોમન કોડ્સ માટે ગુરુસ્વામી-સુદાન ડીકોડિંગ અલ્ગોરિધમ. એમ. સુદાન. રીડ સોલોમન કોડનું ડીકોડિંગ ભૂલ-સુધારણા બાઉન્ડની બહાર છે. કોડિંગ સિદ્ધાંત