Guruswami–Sudan list decoding algorithm
کوڈنگ تھیوری میں، لسٹ ڈیکوڈنگ بہت سی غلطیوں کی موجودگی میں غلطی کو درست کرنے والے کوڈز کی منفرد ڈیکوڈنگ کا ایک متبادل ہے۔ اگر کسی کوڈ کا رشتہ دار فاصلہ ہے، تو یہ اصولی طور پر ممکن ہے کہ انکوڈ شدہ پیغام کو بازیافت کیا جائے جب کوڈ ورڈ کی علامتوں کا ایک حصہ خراب ہو جائے۔ لیکن جب غلطی کی شرح اس سے زیادہ ہو تو یہ عام طور پر ممکن نہیں ہوگا۔ لسٹ ڈیکوڈنگ ڈیکوڈر کو ان پیغامات کی ایک مختصر فہرست آؤٹ پٹ کرنے کی اجازت دے کر اس مسئلے پر قابو پا لیتی ہے جو شاید انکوڈ کیے گئے ہوں۔ لسٹ ڈیکوڈنگ غلطیوں کے ایک سے زیادہ حصوں کو درست کر سکتی ہے۔ لسٹ ڈیکوڈنگ کے لیے بہت سے کثیر الجہتی وقت کے الگورتھم ہیں۔ اس مضمون میں، ہم سب سے پہلے ریڈ سولومن (آر ایس) کوڈز کے لیے ایک الگورتھم پیش کرتے ہیں جو غلطیوں کو درست کرتا ہے اور مدھو سوڈان کی وجہ سے ہے۔ اس کے بعد، ہم بہتر گروسوامی-سودان لسٹ ڈیکوڈنگ الگورتھم کی وضاحت کرتے ہیں، جو غلطیوں کو درست کر سکتا ہے۔ یہاں مختلف الگورتھم کے لیے شرح R اور فاصلے کا ایک پلاٹ ہے۔ https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/81/Graph.jpg الگورتھم 1 (سوڈان کا لسٹ ڈیکوڈنگ الگورتھم) مسئلہ بیان ان پٹ: ایک فیلڈ ؛ عناصر کے مختلف جوڑے ؛ اور انٹیجرز اور۔ آؤٹ پٹ: تمام افعال کی تسلی بخش فہرست زیادہ سے زیادہ ڈگری میں ایک کثیر الجہتی ہے۔ سوڈان کے الگورتھم کو بہتر طور پر سمجھنے کے لیے، کوئی بھی پہلے ایک اور الگورتھم جاننا چاہے گا جسے سابقہ ورژن یا لسٹ ڈیکوڈنگ آر ایس کوڈز کے لیے الگورتھم کا بنیادی ورژن سمجھا جا سکتا ہے-برلیکمپ-ویلچ الگورتھم۔ ویلچ اور برلیکمپ ابتدائی طور پر ایک الگورتھم کے ساتھ آئے تھے جو کثیر الجہتی وقت میں مسئلے کو بہترین حد کے ساتھ حل کر سکتا ہے۔ سوڈان کے الگورتھم کا طریقہ کار تقریبا برلیکمپ-ویلچ الگورتھم کے الگورتھم جیسا ہی ہے، سوائے اس کے کہ مرحلہ 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:// www. cse. buffalo. edu/~ atri/courses/coding-theory/https://www.cs.cmu.edu ~ वेनکٹگ/پبس/پیپرز/لسٹ ڈیکوڈنگ-NOW.pdf http://www.mendeley.com/research/algebraic-softdecision-decoding-reedsolomon-codes R. J. میک ایلیس۔ ریڈ سولومن کوڈز کے لیے گروسوامی-سودان ڈیکوڈنگ الگورتھم۔ ایم سوڈان۔ ریڈ سولومن کوڈز کی ڈیکوڈنگ غلطی کی اصلاح کے پابند سے باہر ہے۔ کوڈنگ تھیوری